RSA KeyPairGenerator с BouncyCastleProvider e*d(φ(n)) не равно единице

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

  1. Выберите два различных простых числа p и q
  2. Вычислить n = pq
  3. Вычислить φ(n) = φ(p)φ(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.54? А в чем проблема, если 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);
    }

введите здесь описание изображения


person Jswq    schedule 23.01.2017    source источник
comment
если e * d (φ (n)) не равно единице, вы не можете расшифровать с помощью частного показателя. Так что это означает серьезную проблему с сгенерированным ключом. Может быть проблема только в извлечении ключевых параметров (обычно это не нужно) и работает для циклов шифрования/дешифрования?   -  person Henry    schedule 23.01.2017
comment
@Henry Это работает нормально, и на самом деле я обнаружил, что φ(n) может равняться LCM(q-1,p-1), что меньше, чем φ(p)φ(q), а в новой версии BC используется λ (n)=lcm(p−1,q−1)λ(n)=lcm(p−1,q−1) вместо φ(n).   -  person Jswq    schedule 23.01.2017
comment
Хорошо, вам нужно (a^e)^d == a (mod pq) и e * d==1 (mod (p-1)*(q-1)) является достаточным условием для этого, но на самом деле, если e * d==1 (mod λ(n)) это тоже работает.   -  person Henry    schedule 23.01.2017


Ответы (1)


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

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

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

person Jswq    schedule 23.01.2017
comment
Когда я запускал ваш код в версии 1.46, он не отображал поведение, которое вы задокументировали. Кажется, это изменилось в 1.47. - person teppic; 23.01.2017