niallmulhare schrieb:

Is it for education or do you want to reinvent the wheel?
Everything for generation RSA-Keys can be found in the JCE (Java
Cryptographic Extension) wich is included in Java 1.4 and higher:

KeyPairGenerator keygen;
keygen = KeyPairGenerator.getInstance("RSA");
keygen.initialize(1024);
KeyPair keypair = keygen.generateKeyPair();
BigInteger privexp =
((RSAPrivateKey)keypair.getprivate()).getPrivateExponent();

That isn't easy and pure mathematics. I do remember an algorithm called
"Miller-Rabin-test" but I did never understand it completely.

Jan

Java has all this stuff in the big integer library.  Here's a little program I
wrote to play with this stuff.  It generates the primes, computes all the RSA
parameters, prints them out for you, and then tests them 100 times on random
messages, veryifying decryption using both the straightforward method and CRT.

Note that I'm just using Random to get random numbers, so don't use this for
anything serious without first fixing that to use better random numbers.

Change numbits to whatever size you want for your primes.  Usage is:

   javac saRSA.java        # to compile
   java saRSA              # generate and test one set of RSA parameters

------------------------ BEGIN CODE ------------------------------
import java.math.*;
import java.util.Random;

class saRSA {
   public static void main(String args[])
   {
       int numbits = 256;  // size of primes
       int output_base = 10;

       BigInteger P = BigInteger.probablePrime( numbits, new Random() );
       BigInteger Q = BigInteger.probablePrime( numbits, new Random() );

       BigInteger P1 = P.subtract( BigInteger.ONE );
       BigInteger Q1 = Q.subtract( BigInteger.ONE );

       BigInteger N = P.multiply(Q);
       BigInteger T = P1.multiply(Q1);

       BigInteger E = new BigInteger("3");
       BigInteger D = BigInteger.ZERO;
       boolean found_d = false;
       while ( ! found_d )
       {
           try
           {
               D = E.modInverse(T);
               found_d = true;
           }
           catch ( ArithmeticException e )
           {
               E = E.add( new BigInteger("2") );
           }
       }

       System.out.println(" Bit length = " + N.bitLength());
       System.out.println("          N = " + N.toString(output_base));
       System.out.println("          E = " + E.toString(output_base));
       System.out.println("-----------------------------------------------");
       System.out.println("          D = " + D.toString(output_base));
       System.out.println("-----------------------------------------------");

       BigInteger Piq = P.modInverse(Q);
       BigInteger Qip = Q.modInverse(P);
       BigInteger Dp1 = D.mod(P1);
       BigInteger Dq1 = D.mod(Q1);

       System.out.println("          P = " + P.toString(output_base));
       System.out.println("          Q = " + Q.toString(output_base));
       System.out.println("   P' mod Q = " + Piq.toString(output_base));
       System.out.println("   Q' mod P = " + Qip.toString(output_base));
       System.out.println("D mod (P-1) = " + Dp1.toString(output_base));
       System.out.println("D mod (Q-1) = " + Dq1.toString(output_base));
       System.out.println("-----------------------------------------------");
       System.out.println("To encrypt message M:");
       System.out.println("    C = M**E mod N      (** is exponentiation)");
       System.out.println("To decrypt encrypted message C:");
       System.out.println("    M = C**D mod N");
       System.out.println("-----------------------------------------------");
       System.out.println("Faster decrypt using chinese remainder theorem:");
       System.out.println("    X = C**(D mod (P-1)) mod P");
       System.out.println("    Y = C**(D mod (Q-1)) mod Q");
       System.out.println("    M = (((Y-X) * P') mod Q) * P + X");
       System.out.println("-----------------------------------------------");

       int numchars = (N.bitLength() - 1) / 8;
       int pass = 0;
       int pass_CRT = 0;
       int pass_CRT2 = 0;
       int num_tests = 100;

       System.out.println("Testing..." + num_tests + " iterations...");
       for ( int i = 0; i < num_tests; ++i )
       {
           BigInteger M = new BigInteger( numchars*8, new Random() );

           // Encrypt
           BigInteger C = M.modPow( E, N );

           // Decrypt
           BigInteger M1 = C.modPow( D, N );

           // Decrypt using chinese remainder theorem
           BigInteger X = C.modPow( Dp1, P );
           BigInteger Y = C.modPow( Dq1, Q );
           Y = Y.subtract(X);
           Y = Y.multiply(Piq);
           Y = Y.mod(Q);
           Y = Y.multiply(P);
           BigInteger M2 = Y.add(X);

           // Decrypt using chinese remainder theorem
           X = C.modPow( Dq1, Q );
           Y = C.modPow( Dp1, P );
           Y = Y.subtract(X);
           Y = Y.multiply(Qip);
           Y = Y.mod(P);
           Y = Y.multiply(Q);
           BigInteger M3 = Y.add(X);

           if ( M1.compareTo(M) == 0 )
               ++pass;
           if ( M2.compareTo(M) == 0 )
               ++pass_CRT;
           if ( M3.compareTo(M) == 0 )
               ++pass_CRT2;
       }
       if ( pass == pass_CRT && pass_CRT == pass_CRT2 )
           System.out.println( "...done.  PASSED!");
       else
       {
           System.out.println( "...done.  FAILED!");
           System.out.println( "                 Standard decrypt passed " + pass + " times");
           System.out.println( "                Chinese remainder passed " + pass_CRT + " times");
           System.out.println( "   Chinese remainder (alt values) passed " + pass_CRT2 + " times");
       }

       System.out.println("          N = " + N.toString(10));
       System.out.println("          P = " + P.toString(10));
       System.out.println("          Q = " + Q.toString(10));
   }
}

------------------------ END CODE ------------------------------