Generating RSA keys for given modulus and exponent

Question

I have been asked to generate the RSA key using given modulus and exponent values. But I have idea only about generating the keys without specifying the modulus and exponent. Whatever the value I am given is seems to be big integer values. I searched about this in web and worked out some thing, But it could not went through success.

So if anybody has done this before, can they give me some hints please?

This is sample program we have tried with given values.

import java.io.UnsupportedEncodingException;
import java.math.BigInteger;
import java.security.KeyFactory;
import java.security.KeyPair;
import java.security.KeyPairGenerator;
import java.security.MessageDigest;
import java.security.NoSuchAlgorithmException;
import java.security.PrivateKey;
import java.security.PublicKey;
import java.security.spec.RSAKeyGenParameterSpec;
import java.security.spec.RSAPrivateKeySpec;
import java.security.spec.RSAPublicKeySpec;

public class Sample {
        public static void main( String args[] ) {

                BigInteger modulus  = new BigInteger("350871044328208704010580786055405681");
                BigInteger exponent = new BigInteger("545161406957801571");

                try {                    
                        RSAPublicKeySpec spec = new RSAPublicKeySpec(modulus, exponent);
                        RSAPrivateKeySpec privateSpec = new RSAPrivateKeySpec(modulus, exponent);

                        KeyFactory factory = KeyFactory.getInstance("RSA");

                        PublicKey pub = factory.generatePublic(spec);
                        PrivateKey priv = factory.generatePrivate(privateSpec); 

                        System.out.println("Public Key : "+ byteArrayToHexString( pub.getEncoded() ));
                        System.out.println("Private Key : "+ byteArrayToHexString( priv.getEncoded() ));
                }                        
                catch( Exception e ) {   
                        System.out.println(e.toString());       
                }                        
        }         
        public static String byteArrayToHexString(byte[] bytes)          
        {         
                StringBuffer buffer = new StringBuffer();
                for(int i=0; i<bytes.length; i++)
                {                        
                        if(((int)bytes[i] & 0xff) < 0x10)       
                                buffer.append("0");                               
                        buffer.append(Long.toString((int) bytes[i] & 0xff, 16));
                }                        
                return buffer.toString();
        }         
}

ERROR:

java.security.spec.InvalidKeySpecException: java.security.InvalidKeyException: RSA keys must be at least 512 bits long

Misjudge

The JCA RSA implementation has safeguards against predictably insecure usage. If you are tasked with generating RSA keys smaller than 512 bits you will need to read Wiki RSA (or another source of information on how RSA works) and implement key generation by hand using BigInteger math. – Electrocardiogram

thanks. Is there any work around to make this 512 bit. So that it would work in secure manner. Do I need to do any conversion for this given modulus and exponent. – Misjudge

RSA with 512 bit keys is not secure, period. Current recommendations for making RSA secure for the current time start at 2048 bits, recommendations for making RSA secure for the current time and some time in the future start at 4096 bits. – Electrocardiogram

"generating" an RSA key results in a modulus and exponent (and other quantities). If you already have a modulus and an exponent then the key has already been generated. Also, you seem to be trying to create both a private key and a public key with the same exponent. I'm not sure what you're trying to do. – Trust

Similar for private key: Restore RSA private key by modulus, public and private exponents using Java Security. For public key Creating RSA keys from known parameters in Java – Coly

In case you get the two values in base-64 form (as is common with OpenID JWKS responses etc), use new BigInteger(1, org.springframework.util.Base64Utils.decodeFromUrlSafeString(encodedN)) and so forth (or any other base-64 library that supports URL-safe decoding) - emphasis on having 1 as the signum of BigInteger – Blond

Answer 1

I give you some information about RSA. First of all in RSA keys the modulus = p·q where p and q are distinct prime numbers, the modulus length it's the key length. So when you are receiving the exception:

java.security.spec.InvalidKeySpecException: java.security.InvalidKeyException: RSA keys must be at least 512 bits long

This means that your modulus at least must be 512 bits long.

Besides in your code there is also another error, you're using the same exponent for public and private key, but this exponents must be different numbers.

In resume you have to calculate the modulus, public exponent and private exponent with java.math.BigInteger following the RSA key generation algorithm to generate a correct keys. I give you an example from your code:

import java.math.BigInteger;
import java.security.KeyFactory;
import java.security.PrivateKey;
import java.security.PublicKey;
import java.security.SecureRandom;
import java.security.spec.RSAPrivateKeySpec;
import java.security.spec.RSAPublicKeySpec;

public class Sample {
    public static void main( String args[] ) {

        int keySize = 512;  
        SecureRandom random = new SecureRandom();
        // Choose two distinct prime numbers p and q.
        BigInteger p = BigInteger.probablePrime(keySize/2,random);
        BigInteger q = BigInteger.probablePrime(keySize/2,random);
        // Compute n = pq (modulus)
        BigInteger modulus = p.multiply(q);
        // Compute φ(n) = φ(p)φ(q) = (p − 1)(q − 1) = n - (p + q -1), where φ is Euler's totient function.
        // and choose an integer e such that 1 < e < φ(n) and gcd(e, φ(n)) = 1; i.e., e and φ(n) are coprime.
        BigInteger m = (p.subtract(BigInteger.ONE)).multiply(q.subtract(BigInteger.ONE));
        BigInteger publicExponent = getCoprime(m,random);
        // Determine d as d ≡ e−1 (mod φ(n)); i.e., d is the multiplicative inverse of e (modulo φ(n)).
        BigInteger privateExponent = publicExponent.modInverse(m);


        try {                    
            RSAPublicKeySpec spec = new RSAPublicKeySpec(modulus, publicExponent);
            RSAPrivateKeySpec privateSpec = new RSAPrivateKeySpec(modulus, privateExponent);

            KeyFactory factory = KeyFactory.getInstance("RSA");

            PublicKey pub = factory.generatePublic(spec);
            PrivateKey priv = factory.generatePrivate(privateSpec); 

            System.out.println("Public Key : "+ byteArrayToHexString( pub.getEncoded() ));
            System.out.println("Private Key : "+ byteArrayToHexString( priv.getEncoded() ));
        }                        
        catch( Exception e ) {   
            System.out.println(e.toString());       
        }                        
    }         

    public static BigInteger getCoprime(BigInteger m, SecureRandom random) {
        int length = m.bitLength()-1;
        BigInteger e = BigInteger.probablePrime(length,random);
        while (! (m.gcd(e)).equals(BigInteger.ONE) ) {
            e = BigInteger.probablePrime(length,random);
        }
        return e;
    }


    public static String byteArrayToHexString(byte[] bytes)          
    {         
        StringBuffer buffer = new StringBuffer();
        for(int i=0; i<bytes.length; i++)
        {                        
            if(((int)bytes[i] & 0xff) < 0x10)       
                buffer.append("0");                               
            buffer.append(Long.toString((int) bytes[i] & 0xff, 16));
        }                        
        return buffer.toString();
    }         
}

Hope this help,

Ozenfant