Java RSA key generation

Question

I was trying to understand how the RSA key generation works and therefore tried to implement it in Java. It's generating keys already, but when I'm encrypting and decrypting something using my generated keys it seems like my keys are wrong. This is my code to generate keys:

public void generateNewKeypair(int bit) {
    BigInteger[] primes = generatePrimes(2, bit / 2);
    BigInteger p = primes[0];
    BigInteger q = primes[1];
    modulo = q.multiply(p);
    BigInteger pN = (q.subtract(BigInteger.valueOf(1))).multiply(p.subtract(BigInteger.valueOf(1)));
    publicKey = BigInteger.ZERO;
    while (publicKey.equals(BigInteger.ZERO)) {
        BigInteger rnd = new BigInteger(pN.bitLength(), random);
        if (rnd.compareTo(pN) <= 0 && rnd.gcd(pN).equals(BigInteger.ONE)) {
            publicKey = rnd;
        }
    }
    privateKey = publicKey.modInverse(modulo);
}

and thats the entire class: http://pastebin.com/DDQh2Q3n

President James K. Polk · Accepted Answer · 2014-07-17 01:26:49Z

1

Here is your error:

    privateKey = publicKey.modInverse(modulo);

You need to compute this inverse mod (p-1)(q-1), which is your variable pN. So try

    privateKey = publicKey.modInverse(pN);

and see if you don't get better results.

answered Jul 17, 2014 at 1:26

President James K. Polk

42.3k34 gold badges113 silver badges149 bronze badges

Sign up to request clarification or add additional context in comments.

2 Comments

Joba Over a year ago

Thanks alot, that fixed it :) Another question, do you have any idea how I could optimize my code?

President James K. Polk Over a year ago

Optimize? What part needs optimizing?

Udnaan Y · Accepted Answer · 2014-07-17 00:50:58Z

0

Please clarify what are you trying to do. Are you trying to understand how RSA key generation works or are you simply trying to write code to generate keys for an app?

For the second, I would highly recommend not trying to write your own code to generate keys as cryptography is very easy to get wrong. Use OpenSSL/Android NDK or such.

For the first, instead of handcoding a prime calculating function, use BigInteger.probablePrime and BigInteger.nextProbablePrime(lastprime). See an implementation here: http://www.herongyang.com/Cryptography/RSA-BigInteger-RsaKeyGenerator-java.html

edited Jul 17, 2014 at 0:50

answered Jul 16, 2014 at 23:56

Udnaan Y

1195 bronze badges

1 Comment

Joba Over a year ago

I want to understand how it works and therefore I would like to know why my code is not working

Collectives™ on Stack Overflow

Java RSA key generation

2 Answers 2

2 Comments

1 Comment

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

2 Answers 2

2 Comments

1 Comment

Your Answer

Sign up or log in

Post as a guest

Related