3

В видео Khan Academy объясняют RSA шифрование. После всех вычислений мы получаем формулу закрытый ключ d = (k*Phi(n)+1)/e, причем было сказано что k это любое число. Однако потом в примере берется конкретный k = 2. Не до конца понял, мы действительно можем брать разные k и получить несколько закрытых ключей? Или мы выбираем такой k чтобы наш d был целым числом и т.п.? И всегда ли такое k существует?

1 ответ 1

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. Перебирать можно, но не нужно.

2
  • Подскажите, а как вы получили 13? И что значит неэффективно инвертировать, имеется ввиду что находить методом перебора k ? Нужно использовать специальный алгоритм?
    – Betflop
    14 апр 2021 в 20:33
  • @ПавелКозлов добавил про инвертирование.
    – Pak Uula
    15 апр 2021 в 4:11

Ваш ответ

By clicking “Отправить ответ”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Всё ещё ищете ответ? Посмотрите другие вопросы с метками или задайте свой вопрос.