rsa.java

Go to the documentation of this file.

 
public class rsa {
    static private long n;
    static private long d;
    static private long e;
 
  private long fixRemainder (long a, long b) {
    long r = a % b;
 
    if ((r * b) < 0)
        r += b;
 
    return r;
  }
 
  private long egcd(long a, long b, long[]last) {
    long x = 0;
    last[0] = 1;
    long y = 1;
    last[1] = 0;
 
    long quotient, t;
    while ( b != 0 ) {
        quotient = a / b;      // integer division
        t = b;
        b = a % b;
        a = t;
        t = x;
        x = last[0] - quotient * x;
        last[0] = t;
        t = y;
        y = last[1] - quotient * y;
        last[1] = t;
    }
    return a;
  }
 
  private long modinv(long a, long m) {
    long x, y, g;
    long[] xy = {0,0};
    g = egcd(a, m, xy);
    x = xy[0];
    if (g != 1)
        return 0; // None: modular inverse does not exist
    else
        return fixRemainder (x, m);
  }
 
  private long modinv2(long a, long b, long c) {
 
    long r = b%a;
 
    if ( r == 0 )
        return (c / a) % (b / a);
 
    return (modinv2(r, a, -c) * b + c) / a%b;
  }
 
  private long power_mod_n(long c, long d, long n) {
 
    long e, r = c % n;
    long drev = baseConverter.reverseBits(d);
 
    drev >>>= 1;
    while ( drev != 0 ) {
       e = (drev & 1)==1 ? c : 1;  // get the bits of d in reversed order
       drev >>>= 1;
       r = (e * r*r) % n;
    }
 
    return r;
  }
 
  public long generateKeys ( long p, long q ) {
    e = 17;
 
    n = p*q;
    long phi = (p-1)*(q-1);
    d = modinv(e,phi);               // modinv2(e,phi,1)
    if (d==0) return phi;
    return 0;
  }
 
  public long encrypt(long val) {
       return power_mod_n(val,e,n);
  }
  public long decrypt(long val) {
       return power_mod_n(val,d,n);
  }
 
  public static void main ( String[] args ) {
    long a = 0, b = 0;
 
    int psize = 1;
    if (args.length < 3) {
        System.out.print ( String.format("usage: %s <number1> <number2> <prime size(small=0,medium=1,large=2)>\n", "rsa"));
        System.exit(1);
    }
    else {
        a = Integer.parseInt(args[0]);
        b = Integer.parseInt(args[1]);
        psize = Integer.parseInt(args[2]);
    }
 
    rsa r = new rsa();
    long[] xy = new long[2];
    long gcd = r.egcd(a, b, xy);
    long x = xy[0]; long y = xy[1];
    System.out.print(String.format("The GCD of %d and %d is %d\n", a, b, gcd));
    System.out.print(String.format("%d * %d + %d * %d = %d\n", a, x, b, y, gcd));
    System.out.print(String.format("The modular inverse of %d and %d is %d\n", a, b, r.modinv(a,b)));
 
    long p, q;
    if (psize == 0) {
       p = 131;
       q = 139;
    }
    else {
        p = 1217;
        q = 1223;
    }
 
    long phi = r.generateKeys ( p, q );
    if (phi > 0) System.out.print (String.format("gcd(%d,%d) is not 1 (modular inverse does not exist)", r.e, phi));
 
    System.out.print(String.format("Public key is: n = %d and e = %d\n", r.n, r.e));
    System.out.print(String.format("Private key is: n = %d and d = %d\n", r.n, r.d));
 
    long tnumber = n;
    long tmin = -n+2;
    while ((tnumber >= n) || (tnumber < tmin)) {
          System.out.print (String.format("Enter number to be encrypted (%d <= n <= %d): ", tmin, n-1));
          tnumber = Integer.parseInt(System.console().readLine());
    }
     
    long c = r.encrypt(tnumber);    // pow(tnumber,e) % n
    long m = r.decrypt(c);          // pow(c,d) % n
 
    System.out.print(String.format("%d encrypted is: %d\n", tnumber, c));
    System.out.print(String.format("%d decrypted is: %d\n", c, m));
  }
}