Размер ключа RSA менее 512 бит в Java

Question

У меня есть устаревшее приложение с жестко закодированным размером ключа RSA до 384 бит, и мне нужно проверить подпись этих ключей в моем приложении Java. Вопрос: Существует ли способ создания и использования ключей RSA на Java с размером ключа менее 512?

(Я полностью знаю, что есть причина ограничения 512 бит, но я не могу изменить устаревшее приложение).

Answer 1

Да, но для этого вы должны использовать другого поставщика. Как Sun RSAKeyFactory (основная реализация поставщика услуг KeyFactory), так и RSAKeyPairGenerator возвращают исключение при попытке использования 384-битного ключа RSA.

После установки поставщика Надувной замок правильно это будет, однако работать:

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

Следует отметить, что из-типа ключа, генерируемого KeyFactory в init методом экземпляра Signature будет молча использовать поставщик Надувной замок даже если "BC" не указан.

Answer 2

Если вы хотите написать код для создания меньших ключей, я могу предоставить исходный код для программы на C#, которую я написал, которая делает это. Вам должно быть достаточно легко переносить на Java. Имейте в виду, что есть общие причины для общих предупреждений о реализации ваших собственных криптопрограмм даже с установленными алгоритмами. Потому что, если программист не очень осторожен, программное обеспечение может быть восприимчиво к атакам с боковым каналом, даже если сам алгоритм в порядке. Сказав, что на 384 бит ваша безопасность уже достаточно низкая, атаки на боковые каналы даже не нужны и не должны быть серьезной проблемой (прямая факторинговая атака будет дешевле и проще делать).

Все, что сказано, вот исходный код. Он взаимодействует с окнами, которых там нет, но по крайней мере это должно дать вам довольно хорошую идею о том, как работает RSA-кейген. Я просто попробовал это для 384-битных ключей, и даже в C# он может генерировать их в течение секунды. Также прошу простить любую неэффективность кода. Я в основном писал это, чтобы убедиться, что я понял, как все это работает. Вот код.

Кроме того, я поделюсь проектом in Dropbox, если кто-то захочет его посмотреть.

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