import java.math.*;
import java.util.*;

/*This program implements the RSA public key
cryptosystem. It was written for educational purposes.
Nevertheless, it really works: No-one can break it.

written by Sieuwert van Otterloo 2000
smotterl@cs.uu.nl 
go.to/sieuwert
*/

/*the public key is the public part of the key. Anyone
can have it. It can only encrypt data, not decrypt.*/
class publickey{
 BigInteger n,e;
 String owner;
 
 /*make a public key. Do not do it yourself, but
 make a public key from a private key.*/
 publickey(String iowner,BigInteger in,BigInteger ie){
  owner=iowner;
  n=in;
  e=ie;
 }
 
 /*read the key back from a string.*/
 publickey(String from){
  StringTokenizer st=new StringTokenizer(from," ");
  owner=st.nextToken();
  n=readBI(st.nextToken());
  e=readBI(st.nextToken());
 }

 /*use the key to encrypt a 'message' m. m should be a
 number from 1 to n (n not included).
 use makemessage to convert your message to a BigInteger.
 */
 BigInteger encrypt(BigInteger m){
  return m.modPow(e,n);
 }
 
 /*make a string from this key.*/
 public String toString(){
  return owner+" "+printBI(n)+" "+printBI(e);
 }
 
 /*help methods for reading and writing:*/
 final static int radix=36;
 
 static String printBI(BigInteger b){
  return b.toString(radix);
 }
 static BigInteger readBI(String s){
  return new BigInteger(s,radix);  
 }   
 
 
 /* these methods convert an arbitrary message,
 in the form of an array of bytes, to a message
 suitable for encryption. To do this random bits
 are added (this is needed to make cracking of the
 system harder), and it is converted to a BigInteger.*/

 BigInteger makemessage(byte[] input){
  /*to understand this part of the program,
  read the description of the BigInteger constructor
  (in the standard java help). */
  
  if(input.length>128 ||
     input.length*8+24>=n.bitLength())
    return new BigInteger("0"); //error! message to long.
  byte[] paddedinput=new byte[n.bitLength()/8-1];
  for(int i=0;i<input.length;i++)  
   paddedinput[i+1]=input[i];
  paddedinput[0]=(byte)input.length;
  for(int i=input.length+1;i<paddedinput.length;i++)
    paddedinput[i]=(byte)(Math.random()*256);
  return new BigInteger(paddedinput);
 }
 
 /*the inverse of makemessage.*/
 static byte[] getmessage(BigInteger b){
  byte[] paddedoutput=b.toByteArray();
  byte[] output=new byte[paddedoutput[0]];
  for(int i=0;i<output.length;i++)  
   output[i]=paddedoutput[i+1];
  return output;
 }

}



class privatekey{
 /*the data of a key*/
 BigInteger n,e,d;
 String owner;
 int bits;
 Random ran;

 /*unimportant things, needed for calculations:*/
 static int certainty=32;
 static BigInteger  one=new BigInteger("1"),
                    three=new BigInteger("3"),
                    seventeen=new BigInteger("17"),
                    k65=new BigInteger("65537");

 /*make a new key. supply the name of the owner of the
 key, and the number of bits.
 owner: all spaces will be replaced with underscores.
 bits: the more bits the better the security. Every
 value above 500 is 'safe'. If you are a really paranoid 
 person, you should use 2000.*/
 privatekey(String iowner,int ibits){
  BigInteger p,q;
  bits=ibits;
  owner=iowner.replace(' ','_');//remove spaces from owner name.
  ran=new Random();
  p=new BigInteger(bits/2,certainty,ran);
  q=new BigInteger((bits+1)/2,certainty,ran);
  n=p.multiply(q);
  BigInteger fi_n=fi(p,q);
  e=chooseprimeto(fi_n);
  d=e.modInverse(fi_n);
 }
 
 /*read the key back from a string*/
 privatekey(String from){
  StringTokenizer st=new StringTokenizer(from," ");
  st.nextToken();
  n=readBI(st.nextToken());
  e=readBI(st.nextToken());
  d=readBI(st.nextToken());
 }

 /*some help methods:*/
 static BigInteger fi(BigInteger prime1,BigInteger prime2){
  return prime1.subtract(one).multiply(prime2.subtract(one));
 }
 
 static BigInteger BI(String s)
    {return new BigInteger(s);}
 
 BigInteger chooseprimeto(BigInteger f){
 /*returns a number relatively prime to f.
 this number is not chosen at random, it first
 tries a few primes with few 1's in it. This
 doesn't matter for security, but speeds up computations.*/
  if(f.gcd(three).equals(one))
    return three;
  if(f.gcd(seventeen).equals(one))
    return seventeen;
  if(f.gcd(k65).equals(one))
    return k65;
  BigInteger num;
  do{
   num=new BigInteger(16,ran);
  }while(!f.gcd(num).equals(one));
  return num;
 }
final static int radix=36;
 
 static String printBI(BigInteger b){
  return b.toString(radix);
 }
 
 static BigInteger readBI(String s){
  return new BigInteger(s,radix);  
 }   

 /*********************************************/

 /*returns the public key of this private key.*/
 publickey getpublickey(){
  return new publickey(owner,n,e);
 }

 /*the same encryption that the public key does.*/
 BigInteger encrypt(BigInteger m){
  return m.modPow(e,n);
 }
 
 /*decryption is the opposite of encryption: it 
 brings the original message back.*/
 BigInteger decrypt(BigInteger m){
  return m.modPow(d,n);
 }
 
 public String toString(){
  return owner+" "+printBI(n)+" "+printBI(e)+" "+printBI(d);
 }
 
 
 
 /*this main demonstrates the use of this program.*/
 
 public static void main(String[] ps){
  say("************ make key:");
  privatekey priv=new privatekey("sieuwert",92);
  publickey pub=priv.getpublickey();
  say("the public key:"+priv);
  
  say("************ encrypt message:");
  byte[] P="RUOK?".getBytes();
  BigInteger Pc=pub.makemessage(P);
  say("converted:\t"+printBI(Pc));
  BigInteger C=pub.encrypt(Pc);
  say("coded message: "+printBI(C));
  
  say("************ decrypt message:");
  BigInteger Pc2=priv.decrypt(C);
  say("decoded:\t"+printBI(Pc2));  
  byte[] P2=publickey.getmessage(Pc2);
  say("deconverted: "+new String(P2));  
 }
 
 
 static void say(String s){
  System.out.println(s);
 }
}