RSA KeyPairGenerator с BouncyCastleProvider e * d (φ (n)), не равным одному

Question

Я использовал BouncyCastleProvider (версия 1.54) для генерации пары ключей RSA, и я хочу проверить, действительно ли ключ. Согласно википедии ключ алгоритма RSA, как показано ниже:

1. Выберите два различных простых чисел р и д
2. Compute п = рд
3. вычислить ф (п) = φ (р) φ (Q) = (p - 1) (q - 1) = n - (p + q - 1)
4. Выберите целое число e такое, что 1 < e < φ (n) и gcd (e, φ (n)) = 1; , т. Е. E и φ (n) являются взаимно простыми
5. Определить d как d ≡ e-1 (mod φ (n)); Это более четко указано как: решить для d заданного d⋅e ≡ 1 (mod φ (n))

Затем я генерирую 1000 ключей, которые я нашел только около 30% клавиш, соответствующих d⋅e ≡ 1 (mod φ (n)). Тем не менее, я получил 100% d⋅e ≡ 1 (mod φ (n)), когда я не использую поставщика BC. Это что-то не так с BC 1.54version? И в чем проблема, если e * d (φ (n)) не равно единице. Может ли кто-нибудь помочь? Большое спасибо. и мой тестовый код Java, как показано ниже:

public void testRSAKey() throws NoSuchAlgorithmException { 
     KeyPairGenerator rsa = KeyPairGenerator.getInstance("RSA", new BouncyCastleProvider()); 
     rsa.initialize(1024,new SecureRandom()); 
     int total=0; 
     int isOne=0,notOne=0; 
     BigInteger one= new BigInteger("1"); 
     while (total<1000) { 
      KeyPair keyPair = rsa.generateKeyPair(); 
      PrivateKey privateKey = keyPair.getPrivate(); 
      BCRSAPrivateCrtKey privateCrtKey = (BCRSAPrivateCrtKey) privateKey; 
      BigInteger primeP = privateCrtKey.getPrimeP(); 
      BigInteger primeQ = privateCrtKey.getPrimeQ(); 
      BigInteger p1 = primeP.add(new BigInteger("-1")); 
      BigInteger q1 = primeQ.add(new BigInteger("-1")); 
      BigInteger fn = p1.multiply(q1); 
      BigInteger publicExponent = privateCrtKey.getPublicExponent(); 
      BigInteger privateExponent = privateCrtKey.getPrivateExponent(); 
      BigInteger mod = publicExponent.multiply(privateExponent).mod(fn);//mod ought to be one 
      if(mod.equals(one)) { 
       System.out.println("e*d(mod fn)=" + mod); 
       isOne++; 
      }else { 
       System.out.println("e*d(mod fn) not equal to one"); 
       notOne++; 
      } 
      total++; 
     } 
     System.out.println("total=" + total); 
     System.out.println("isOne=" + isOne); 
     System.out.println("notOne=" + notOne); 
    } 

Answer 1

Наконец я обнаружил, что BC может использовать X (п) = LCM (р-1, д-1) λ (п) = LCM (р -1, q-1) вместо φ (n). и я изменить мой код:

BigInteger fn = (p1.multiply(q1)).divide(p1.gcd(q1)); 

И это работает отлично, и все результаты «е * d (мод п) = 1». Хотя сейчас я не понимаю самую глубокую из теории, алгоритм RSA от Википедии не является последним, может быть,