CODEWITHSUNDEEP
javarsabiginteger
mrQWERTY
mrQWERTY

Reputation: 4149

BigInteger implementation of RSA's key generation

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?

Upvotes: 0

Views: 966

Answers (2)

Artjom B.
Artjom B.

Reputation: 61892

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

Upvotes: 1

Elliott Frisch
Elliott Frisch

Reputation: 201437

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

Upvotes: 0

Related Questions