RSA key size less than 512 bits in Java

Question

I have a legacy application that has hardcoded RSA key size to 384 bits and I need to be able to verify the signature of these keys in my Java application. Question: Is there a way to create and use RSA keys in Java with key-size less than 512?

(I am fully aware that there is a reason to the restriction of 512 bit, but I cannot change the legacy application).

Answer 1

If you want to hand-write code to create smaller keys, I can provide source code for a C# program I wrote that does this. It should be easy enough for you to port to Java. Bear in mind that there are good reasons for the general warnings about implementing your own crypto routines even with established algorithms. Because unless the programmer is very careful, the software may be susceptible to side channel attacks even if the algorithm itself is fine. Having said that, at 384 bits, your security is already low enough that side channel attacks aren't even necessary and should not be a major concern (a direct factoring attack would be cheaper and easier to do).

All that said, here is the source code. It interacts with windows that are not there, but at least it should give you a pretty good idea how RSA keygen works. I just tried it out for 384 bit keys, and even in C# it can generate them in under a second. Also please forgive any inefficiencies in the code. I mainly wrote it just to make sure I understood how it all works. Here is the code.

Also, I will share the project in Dropbox in case anyone wants to have a look at it there.

using System;
using System.Numerics;
using System.Security.Cryptography;
using System.Text;
using System.Threading.Tasks;
using System.Windows.Forms;

namespace RSAinCS
{
    public partial class Form1 : Form
    {
        RNGCryptoServiceProvider rng = new RNGCryptoServiceProvider();
        struct RSAKey
        {
            internal BigInteger p; // one prime factor of the modulus
            internal BigInteger q; // another prime factor of the modulus
            internal BigInteger n; // modulus, a part of both the public key and the private key
            internal BigInteger totient; // product of p-1 and q-1.  Must be kept secret.  We calculate it because we need to confirm our public exponent (65537) doesn't divide it evenly
            internal BigInteger e; // public exponent.  Together with n forms the public key
            internal BigInteger d; // private exponent.  Together with n forms the private key.  Must be kept secret
        }

        struct EGCDReturnStruct
        {
            internal BigInteger g;
            internal BigInteger x;
            internal BigInteger y;
        }

        public Form1()
        {
            InitializeComponent();
        }

        private void button1_Click(object sender, EventArgs e)
        {
            int bitLength = 0;
            Int32.TryParse(comboBox1.Text, out bitLength);
            if (bitLength == 0) return;
            Task.Run(() => { doWork(bitLength); });
        }

        void doWork(int bitLength)
        {
            RSAKey rsaKey = generateKey(bitLength);
            BeginInvoke(new Action(() => textBox2.Text = rsaKey.p.ToString()));
            BeginInvoke(new Action(() => textBox3.Text = rsaKey.q.ToString()));
            BeginInvoke(new Action(() => textBox4.Text = rsaKey.n.ToString()));
            BeginInvoke(new Action(() => textBox5.Text = rsaKey.totient.ToString()));
            BeginInvoke(new Action(() => textBox6.Text = rsaKey.e.ToString()));
            BeginInvoke(new Action(() => textBox7.Text = rsaKey.d.ToString()));
            BeginInvoke(new Action(() => textBox8.Text = textBox1.Text));
            BigInteger message = convertTextToBigInteger(textBox8.Text);
            BeginInvoke(new Action(() => textBox9.Text = message.ToString()));
            BigInteger cipherText = BigInteger.ModPow (message,rsaKey.e,rsaKey.n);
            BeginInvoke(new Action(() => textBox10.Text = cipherText.ToString()));
            BigInteger decryptedCipherText = BigInteger.ModPow(cipherText, rsaKey.d, rsaKey.n);
            BeginInvoke(new Action(() => textBox11.Text = decryptedCipherText.ToString()));
            BeginInvoke(new Action(() => textBox12.Text = convertBigIntegerToText(decryptedCipherText)));
        }

        string convertBigIntegerToText(BigInteger b)
        {
            StringBuilder sb = new StringBuilder();
            byte[] letterByte = new byte[1];
            string letter;
            while (b > 0)
            {
                letterByte[0] = (byte)(b % 256);
                letter = ASCIIEncoding.UTF8.GetString(letterByte);
                sb.Append(letter);
                b /= 256;
            }
            return sb.ToString();
        }

        BigInteger convertTextToBigInteger(string s)
        {
            BigInteger textInteger = 0;
            byte[] textBytes = ASCIIEncoding.UTF8.GetBytes(s);
            for (int i = 0; i < textBytes.Length; i++)
            {
                textInteger += textBytes[textBytes.Length-1-i];
                if (i < textBytes.Length - 1) textInteger *= 256;
            }
            return textInteger;
        }

        RSAKey generateKey(int bitLength)
        {
            RSAKey rsaKey = new RSAKey();
            // Generate 2 large primes.  The first will be p, and the second will be q.
            for (int i = 0; i < 2; i++)
            {
                // The bit length of each prime, p and q, is half the bit length of the whole modulus, and we divide by 8 for byte length
                byte[] primeBytes = new byte[bitLength / 16];
                rng.GetBytes(primeBytes);
                BigInteger primeNumber = 0;
                for (int j = 0; j < primeBytes.Length; j++)
                {
                    primeNumber += primeBytes[j];
                    if (j < primeBytes.Length - 1) primeNumber *= 256;
                }
                if (primeNumber % 2 == 0) primeNumber++; // Make our prime odd

                // This next bit of code ensures zeros in the high bits don't give us small (less secure) prime factors of the modulus
                BigInteger highBitValue = BigInteger.Pow(2, (bitLength / 2) - 1);
                BigInteger secondBitValue = BigInteger.Pow(2, (bitLength / 2) - 2);
                if (primeNumber < secondBitValue) primeNumber += secondBitValue;
                if (primeNumber < highBitValue) primeNumber += highBitValue;

                if (isProbablyPrime(primeNumber, 100) == true)
                {
                    if (i == 0) rsaKey.p = primeNumber;
                    else rsaKey.q = primeNumber;
                }
                else
                {
                    i--;
                    continue;
                }
            }
            rsaKey.n = rsaKey.p * rsaKey.q;
            rsaKey.totient = (rsaKey.p - 1) * (rsaKey.q - 1);
            // A little recursion.  Checks if totient is OK for use with our chose public exponent.  If not, runs method again
            // I also have it repeat if the modInv method returns a value less than 0.  This may be fixable in the modInv or egcd method, not sure
            if (rsaKey.totient % 65537 == 0 || modInv(65537, rsaKey.totient) < 0) return generateKey(bitLength);
            //if (rsaKey.totient % 65537 == 0) return generateKey(bitLength);
            else
            {
                rsaKey.e = 65537;
                rsaKey.d = modInv(rsaKey.e, rsaKey.totient);
                return rsaKey;
            }
        }

        BigInteger modInv(BigInteger a, BigInteger m)
        {
            EGCDReturnStruct eGCDReturnStruct = new EGCDReturnStruct();
            eGCDReturnStruct = egcd(a, m);
            if (eGCDReturnStruct.g != 1) throw new Exception("Modular Inverse Does Not Exist");
            else return eGCDReturnStruct.x % m;
        }

        EGCDReturnStruct egcd(BigInteger a, BigInteger b)
        {
            EGCDReturnStruct eGCDReturnStruct = new EGCDReturnStruct();
            if (a == 0)
            {
                eGCDReturnStruct.g = b;
                eGCDReturnStruct.x = 0;
                eGCDReturnStruct.y = 1;
                return eGCDReturnStruct;
            }
            else
            {
                eGCDReturnStruct = egcd(b % a, a);
                BigInteger temp = eGCDReturnStruct.x;
                eGCDReturnStruct.x = eGCDReturnStruct.y;
                eGCDReturnStruct.y = temp;
                eGCDReturnStruct.x -= (b / a) * eGCDReturnStruct.y;
                return eGCDReturnStruct;
            }
        }

        bool isProbablyPrime(BigInteger testNumber, int confidence)
        {
            int[] firstPrimes = {2,3,5,7,11,13,17,19};

            for (int i = 0; i < firstPrimes.Length; i++)
            {
                if ((testNumber % firstPrimes[i]) == 0) return false;
            }
            for (int i = 2; i < 101; i++)
            {
                if (BigInteger.ModPow(i, testNumber - 1, testNumber) != 1) return false;
            }
            BigInteger nMinusOne = testNumber - 1;
            BigInteger nMinusOneTemp = nMinusOne;
            int s = 0;
            while (nMinusOneTemp % 2 == 0)
            {
                s++;
                nMinusOneTemp /= 2;
            }
            BigInteger d = nMinusOneTemp;
            bool probablyPrime = true;
            int counter = 0;
            int a = 2;
            while ((counter < confidence) & (probablyPrime == true) & (a < testNumber))
            {
                counter++;
                probablyPrime = false;
                if (BigInteger.ModPow(a, d, testNumber) == 1)
                {
                    probablyPrime = true;
                }
                else
                {
                    for (int r = 0; r < s; r++)
                    {
                        BigInteger j = BigInteger.ModPow(a, d, testNumber);
                        for (BigInteger t = 0; t < r; t++)
                        {
                            j = (j * BigInteger.ModPow(j, 2, testNumber)) % testNumber;
                        }
                        if (j == nMinusOne)
                        {
                            probablyPrime = true;
                            break;
                        }
                    }
                }
                if (probablyPrime == true)
                {
                    a++;
                }
                else
                {
                    return false;
                }
            }
            return true;
        }
    }
}

Answer 2

Yes, but you must use another provider for that. Both the Sun RSAKeyFactory (the underlying service provider implementation of KeyFactory) and RSAKeyPairGenerator return an exception when you try and use a 384 bit RSA key.

After installing the Bouncy Castle provider correctly this will however work:

Security.addProvider(new BouncyCastleProvider());

KeyPairGenerator kpg = KeyPairGenerator.getInstance("RSA", "BC");
kpg.initialize(384);
KeyPair kp = kpg.generateKeyPair();
PublicKey genPub = kp.getPublic();

byte[] enc = genPub.getEncoded();

KeyFactory kf = KeyFactory.getInstance("RSA", "BC");
X509EncodedKeySpec ks = new X509EncodedKeySpec(enc);
PublicKey decPub = kf.generatePublic(ks);

Signature sig = Signature.getInstance("SHA1withRSA", "BC");
sig.initVerify(decPub);
byte[] faultySig = new byte[384 / Byte.SIZE];
boolean verifies = sig.verify(faultySig);

System.out.println(verifies + " for " + decPub.getAlgorithm());

Note that because of the type of key generated by the KeyFactory the init method of the Signature instance will silently use the Bouncy Castle provider even if "BC" is not specified.