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

Ваш ответ

Нажимая на кнопку «Отправить ответ», вы соглашаетесь с нашими условиями использования и подтверждаете, что прочитали и поняли наши политику конфиденциальности и нормы поведения.

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