Java Security - Big integer?? For RSA

Author

Big integer?? For RSA

niallmulhare

2005-01-27, 4:03 pm

hey, Im attempting to write a program which produces public keys for use
with rsa algorithm, also then I will implement the algorithm.
The problem is that to what type should I declare the two primes, bare in
mind for example one prime is 5915587277 but it could also be
2074722246773485207821695222107608587480
99647472111729275299258
9912196684750549658310084416732550077.

Another question is does anyone know what alogrithm I could you to find a
number relatively prime, and how to test it using the euclidean algorithm.

And last an algorithm for finding the modular inverse .

Thanking you in advance niall

Jan Peter Stotz

2005-01-27, 4:03 pm

niallmulhare schrieb:

> hey, Im attempting to write a program which produces public keys for use
> with rsa algorithm, also then I will implement the algorithm.

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();

> Another question is does anyone know what alogrithm I could you to find a
> number relatively prime, and how to test it using the euclidean algorithm.

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

Jan

Wannabee

2005-02-01, 4:01 pm

"Jan Peter Stotz" wrote
> niallmulhare schrieb:

a[color=darkred]
algorithm.[color=darkred]
>
> That isn't easy and pure mathematics. I do remember an algorithm called
> "Miller-Rabin-test" but I did never understand it completely.

Numbers are relatively prime if they have no common factors other than the
number 1. That is if GCD(a, b) == 1 then a and b are relatively prime.
Relatively prime numbers do not need to be _primes_ - these are a bit
different concepts. Miller-Rabin deals with probable primes, GCD -algorithm
deals with common factors.

java.math.BigInteger -class has the method gcd for finding greatest common
divisor (GCD).

java.math.BigInteger also has a constructor and a static method
probablePrime for creating (probably) prime numbers.

Multiplicative inverse can be calculated using the method
java.math.BigInteger.modInverse(BigInteger).

Tim Smith

2005-02-13, 4:02 pm

In article < 5777ba51c5ff96200c2ccbd7eab1d015@localho
st.talkaboutprogramming.com>, niallmulhare wrote:
> Another question is does anyone know what alogrithm I could you to find a
> number relatively prime, and how to test it using the euclidean algorithm.
>
> And last an algorithm for finding the modular inverse .

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 ------------------------------

--
--Tim Smith

Michael Amling

2005-02-13, 9:00 pm

Tim Smith wrote:
> In article < 5777ba51c5ff96200c2ccbd7eab1d015@localho
st.talkaboutprogramming.com>, niallmulhare wrote:
>
>
>
> 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() );

new Random() initializes from System.currentTimeMillis(), right? So
if P and Q are generated in the same millisecond (Don't know if that
happens or not), they'll be equal, which is not good. If your
P.modInverse(Q) hasn't blown up, I guess it hasn't happened to you.
Note: In real life, with SecureRandom, and this would not be a problem.

>
> 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.valueOf(3) allows for better efficiency. Note: If you're
not using gobs of these, you won't notice any difference.

--Mike Amling

Sponsored Links