BigInteger implementation of RSA's key generation

Question

I am having a bit of trouble getting the modulus's size to be consistently 128 bytes big. Sometimes the modulus's byte array has a size of 129 or even 130. I've searched for implementation online, and my implementation is really close to the one from this link: http://introcs.cs.princeton.edu/java/78crypto/RSA.java.html

Here is my implementation:

public static void genKey() throws NoSuchAlgorithmException, NoSuchProviderException {
    int bitLength = 512;
    SecureRandom srand = new SecureRandom();
    BigInteger one  = new BigInteger("1");
    BigInteger p = BigInteger.probablePrime(bitLength, srand);
    BigInteger q = BigInteger.probablePrime(bitLength, srand);
    BigInteger phi = (p.subtract(one)).multiply(q.subtract(one));

    BigInteger modulus    = p.multiply(q); //Varies here                                  
    BigInteger publicKey  = new BigInteger("65537");     
    BigInteger privateKey = publicKey.modInverse(phi);

    byte[] modulusArray = modulus.toByteArray();
    byte[] publicKeyArray = publicKey.toByteArray();
    byte[] privateKeyArray = privateKey.toByteArray();
    byte[] tmpArray = new byte[128];
    for (int i = 0; i < publicKeyArray.length; i++) {
        tmpArray[i] = publicKeyArray[i];
    }
    publicKeyArray = tmpArray;
    byte[] publicKeyAndModulus = concat(modulusArray, publicKeyArray);
    byte[] privateKeyAndModulus = concat(modulusArray, privateKeyArray);
}

In addition, the privateKey length would vary a bit too. Can I get more consistency with the size using java.Security library or is this not possible to achieve?

A BigInteger implementation of RSA would be really slow; why not use BouncyCastle? In fact, please use BouncyCastle. — Elliott Frisch
– Elliott Frisch, Commented Mar 14, 2015 at 2:45
I was thinking of that. However, I need to store the modulus along with the keys in file. How are the key pairs stored in PublicKey and PrivateKey? Can I obtain the modulus value through PublicKey and PrivateKey? — mrQWERTY
– mrQWERTY, Commented Mar 14, 2015 at 2:48
You generally create a AsymmetricCipherKeyPair. This blog post gives an example. — Elliott Frisch
– Elliott Frisch, Commented Mar 14, 2015 at 2:58
I hope this is only for academic purposes. Raw RSA is horribly insecure, you would have to implement a secure padding like OAEP or simply use the one provided by Java's Cipher class. — Artjom B.
– Artjom B., Commented Mar 14, 2015 at 3:14
@ArtjomB. Sorry, I mistyped there. The actual code has 512 value. Yes this is only for study purposes. — mrQWERTY
– mrQWERTY, Commented Mar 14, 2015 at 3:14

Artjom B. · Accepted Answer · 2015-03-14 03:38:28Z

The BigInteger#bitLength() function has the necessary documentation:

Returns the number of bits in the minimal two's-complement representation of this BigInteger, excluding a sign bit.

When you generate a BigInteger with bitLength 512, the most significant bit will be 0 ~50% of the time in which case the sign bit will take its place and it will fit into 64 bytes, but in the other cases the most significant bit will be 1 which means that the sign bit will be put into a new byte.

This means that using 511 as the bitLength always results BigIntegers of 64 bytes and 128 bytes for the modulus.

You shouldn't really generate p, q, the modulus and all the other values yourself. It is best to use existing APIs such as Java's Cipher class which also provides proper padding to be used with RSA such as OAEP (PKCS#1 v1.5 is not good anymore): "RSA/ECB/OAEPWithSHA-256AndMGF1Padding".

Elliott Frisch · Accepted Answer · 2015-03-14 03:38:13Z

0

I suggest you use BouncyCastle and create an AsymmetricCipherKeyPair; here is an example I adapted from RSA using BouncyCastle

public static AsymmetricCipherKeyPair generateKeys(int keySizeInBits) {
    RSAKeyPairGenerator kpg = new RSAKeyPairGenerator();
    kpg.init(new KeyGenerationParameters(new SecureRandom(), keySizeInBits));
    return kpg.generateKeyPair();
}

answered Mar 14, 2015 at 3:38

Elliott Frisch

202k20 gold badges166 silver badges265 bronze badges

Collectives™ on Stack Overflow

BigInteger implementation of RSA's key generation

2 Answers 2

Comments

Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

2 Answers 2

Comments

Comments

Your Answer

Sign up or log in

Post as a guest

Related