В видео Khan Academy объясняют RSA шифрование. После всех вычислений мы получаем формулу закрытый ключ d = (k*Phi(n)+1)/e
, причем было сказано что k это любое число. Однако потом в примере берется конкретный k = 2
. Не до конца понял, мы действительно можем брать разные k и получить несколько закрытых ключей? Или мы выбираем такой k чтобы наш d был целым числом и т.п.? И всегда ли такое k существует?
1 ответ
У вас вопрос состоит из нескольких подвопросов.
Начну с вопроса о том, сколько может быть приватных ключей.
Да, теоретически может быть несколько d
таких, что (m**e)**d == 1 (mod pq)
для всех m
из диапазона [1,pq-1]
Пример. Возьмём p = 11
и q = 31
. Для это пары N = 341
и phi(N) = 300
. Возьмём в качестве публичного ключа e = 7
. Если брать традиционное описание RSA, приведённое в русской Википедии, то мы должны взять d = 43
. Действительно, 7*43 = 301 == 1 mod 300
. Можно в лоб проверить, что для любого m
из диапазона [1, 340] выполняется шифрование-расшифрование RSA: (m**7)**43 == m (mod 341)
А теперь попробуем провести ту же проверку для числа d1 = 13
. Возьмем пайтон и посчитаем все возможные значения (m**7)**13 - m (mod 341)
:
>>> set([((m**7)**13) % 341 - m for m in range(1,341)])
{0}
Что означает этот ноль? Что d1
так же является приватным ключом для e=7
. Более того, приватными ключами будут числа 73, 103, 133 и так далее. Все эти числа объединяет тот факт, что они отстоят от 13 на число, кратное 30-ти. А что такое 30? Это наименьшее общее кратное чисел 10 (т.е. p-1
) и 30 (т.е. q-1
)
В реальной жизни в качестве d
выбирают такое число, что d*e == 1 mod( lcm(p-1,q-1) )
. Ссылка ведёт на функцию генерации приватных ключей RSA в openssl. Можете убедиться, относительно какого модуля инвертируют e
.
Теперь про то, как считают d
в видео.
Более строго там должно быть так - давайте подберём k
таким, чтобы k*Phi(n)+1
нацело делится на e
. То есть k=2
справедливо только для их примера. В моём примере с 11 и 31 k=1
.
Почему так. Если d = (k*Phi(n)+1)/e
- целое, то d*e = k*Phi(n)+1
, что означает d*e
сравнимо с единицей по модулю Phi(n)
. Другими словами, d
есть инвертированное e
по модулю функции Эйлера.
Такое k
существует всегда, если e
и Phi(n)
взаимно просты.
Так инвертировать можно, но чудовищно неэффективно.
UPDATE
Как же инвертировать эффективно.
Алгоритм с перебором k
имеет среднюю сложность порядка n
, где n
- модуль, относительно которого производится инвертирование. В случае больших n
этот процесс не закончится никогда.
На практике пользуются расширенным алгоритмом Евклида. Его сложность в худшем случае порядка логарифма большего числа. По этой ссылке я взял реализацию для Python и выполнил код bezout(30,7)
. Получил (-3, 13, 1)
, что означает -3*30 + 13*7 = 1
.
Заменяем равенство на сравнение по модулю и получаем, что 13*7
сравнимо с 1 по модулю 30. Следовательно, 13 - обратное к 7 число по модулю 30. Ответ найден за 3 шага, перебор за 13. В случае инвертирования 7 по модулю 300 (значение функции Эйлера для 11*31) обратное находится тоже за 3 шага, а перебором за 43. Ещё пример неэффективности перебора k
: инвертирование 7 по модулю 1009 (первое простое большее 1000) алгоритмом Евклида выполняется за 2 шага, а перебором с единицы 865. Перебирать можно, но не нужно.
-
Подскажите, а как вы получили 13? И что значит неэффективно инвертировать, имеется ввиду что находить методом перебора k ? Нужно использовать специальный алгоритм?– Betflop14 апр 2021 в 20:33
-