Вычислите начала p и q от частной экспоненты (d), общедоступная экспонента (e) и модуль (n)
Как я вычисляю p и q параметры от e (открытый ключ), d (закрытый ключ) и модуль?
У меня есть ключи BigInteger под рукой, я могу скопировать вставку в код. Один открытый ключ, один закрытый ключ и модуль.
Я должен вычислить параметры RSA p и q от этого. Но я подозреваю, что существует библиотека для того, что я не мог найти с Google. Какие-либо идеи?Спасибо.
Это не должно быть грубой силой, так как я не после закрытого ключа. У меня просто есть унаследованная система, которая хранит общественность, пару с закрытым ключом и модуль, и я должен заставить их в c# использовать с RSACryptoServiceProvider.
Таким образом, это сводится к вычислению (p+q)
public BigInteger _pPlusq()
{
int k = (this.getExponent() * this.getD() / this.getModulus()).IntValue();
BigInteger phiN = (this.getExponent() * this.getD() - 1) / k;
return phiN - this.getModulus() - 1;
}
но это, кажется, не работает. Можно ли определить проблему?
5 часов спустя... :)
Хорошо. Как я могу выбрать случайное число из Цинка* (http://en.wikipedia.org/wiki/Multiplicative_group_of_integers_modulo_n) в C#?
1 ответ
Предположим, что e мало (это обычный случай; Традиционный публичный показатель степени равен 65537). Также предположим, что ed = 1 mod phi (n) , где phi (n) = (p-1) (q-1) (это не обязательно так; требования RSA таковы, что ed = 1 mod lcm (p-1, q-1) и phi (n) только кратно см (p-1, q-1) ).
Теперь у вас есть ed = k * phi (n) +1 для некоторого целого k . Поскольку d меньше, чем phi (n) , вы знаете, что k
Учитывая k , вы легко получите phi (n) = (ed-1) / k .Так получилось, что:
phi (n) = (p-1) (q-1) = pq - (p + q) + 1 = n + 1 - (p + q)
Таким образом, вы получите p + q = n + 1 - phi (n) . У вас также есть pq . Пора вспомнить, что для всех действительных чисел a и b , a и b являются двумя решениями квадратного уравнения X 2 - (a + b) X + ab . Итак, для заданных p + q и pq , p и q получаются путем решения квадратного уравнения:
p = ( (p + q) + sqrt ((p + q) 2 - 4 * pq)) / 2
q = ((p + q) - sqrt ((p + q) 2 - 4 * pq)) / 2
В общем случае e и d могут иметь произвольные размеры (возможно, больше, чем n ), потому что все, что требуется RSA, - это ed = 1 mod (p-1) и ed = 1 mod (q-1) . Существует общий (и быстрый) метод, который немного похож на тест простоты Миллера-Рабина. Он описан в Справочнике по прикладной криптографии (глава 8, раздел 8.2.2, стр. 287). Этот метод концептуально немного сложнее (он включает в себя модульное возведение в степень), но может быть проще в реализации (поскольку квадратный корень отсутствует).