Как найти d, заданные p, q и e в RSA?

Ответ 1

Ну, d выбирается таким, что d * e == 1 modulo (p-1)(q-1), поэтому вы можете использовать Евклидовой алгоритм для этого (нахождение модулярного мультипликативного обратного).

Если вы не заинтересованы в понимании алгоритма, вы можете просто позвонить BigInteger # modInverse напрямую.

 d = e.modInverse(p_1.multiply(q_1))

Ответ 2

Учитывая, что p = 11, q = 7, e = 17, n = 77, φ (n) = 60 и d =?

Сначала замените значения из формулы: -

ed mod φ (n) = 1

17 d mod 60 = 1

Следующий шаг: возьмите тотал n, который равен 60 с левой стороны, а [e] - с правой стороны.

60 = 17

Третий шаг: - спросите, сколько раз 17 идет до 60. Это 3.5..... Игнорируйте остаток и возьмите 3.

60 = 3 (17)

Шаг 4: теперь вам нужно сбалансировать это уравнение 60 = 3 (17), так что левая сторона равна правой стороне. Как?

60 = 3 (17) + 9 < == если вы умножаете 3 на 17, вы получаете 51, затем плюс 9, то есть 60. Это означает, что обе стороны теперь равны.

Шаг 5: - Теперь возьмите 17 с левой стороны и 9 с правой стороны.

17 = 9

Шаг 6: - спросите, сколько раз 9 идет до 17. Это 1.8.......

17 = 1 (9)

Шаг 7: - Шаг 4: теперь вам нужно сбалансировать это 17 = 1 (9)

17 = 1 (9) + 8 < == если вы умножаете 1 на 9, вы получаете 9, затем плюс 8, то есть 17. Это означает, что обе стороны теперь равны.

Шаг 8: снова возьмите 9 с левой стороны и 8 с правой стороны.

9 = 1 (8)

9 = 1 (8) + 1 < == как только вы достигли +1, чтобы сбалансировать свое уравнение, вы можете остановиться и начать отмену замещения.

Шаг A: -сладкое уравнение на шаге 8, которое равно 9 = 1 (8) + 1, может быть записано следующим образом: 1. = 9 - 1 (8)

Шаг B: -Мы знаем, что есть (8), простым высказыванием 8 = 17 - 1 (9) из шага 7. Теперь мы можем переписать шаг A как: -

1 = 9 -1 (17 - 1 (9)) < == здесь, поскольку 9 = 1 (9), мы можем переписать как: -

1 = 1 (9) -1 (17) +1 (9) < == аналогичные члены группы. В этом случае вы добавляете 1 (9) с 1 (9) - то есть 2 (9).

1 = 2 (9) -1 (17)

Шаг C: - Мы знаем, что есть (9) простым высказыванием 9 = 60 - 3 (17) из шага 4. Теперь мы можем переписать шаг B как: -

1 = 2 (60-3 (17) -1 (17)

1 = 2 (60) -6 (17) -1 (17) < == аналогичные члены группы. В этом случае вы добавляете 6 (17) с 1 (17) - то есть 7 (17).

1 = 2 (60) -7 (17) < == на этом этапе мы можем остановиться, не более того, чтобы заменить, поэтому принимаем значение next 17. Это 7. Вычтите его с помощью тотализатора.

60-7 = д

Тогда, следовательно, значение d = 53.

Ответ 3

Я просто хочу увеличить ответ Sidudozo и прояснить некоторые важные моменты.

Прежде всего, что мы должны передать Extended Euclidean Algorthim для вычисления d?

Помните, что ed mod φ(n) = 1 и cgd(e, φ(n)) = 1.

Зная, что Extended Euclidean Algorthim основано на формуле cgd(a,b) = as + bt, поэтому cgd(e, φ(n)) = es + φ(n)t = 1, где d должно быть равно s + φ(n), чтобы удовлетворить

ed mod φ(n) = 1.

Итак, учитывая e=17 и φ(n)=60 (взятые из ответа Sidudozo), мы подставляем соответствующие значения в упомянутой выше формуле: cgd(e, φ(n)) = es + φ(n)t = 1 ⇔ 17s + 60t = 1.

В конце ответа Sidudozo мы получим s = -7. Таким образом, d = s + φ(n) ⇔ d = -7 + 60 ⇒ d = 53.

Проверить результаты. Условие было ed mod φ(n) = 1.

Посмотрите 17 * 53 mod 60 = 1. Правильно!