[МУЗЫКА] [МУЗЫКА] [МУЗЫКА] Нам будет полезно вспомнить алгоритм RSA. Итак. У нас есть какое-то большое число N, являющееся произведением двух простых, не равных друг другу больших чисел. Давайте рассмотрим какое-то число a меньшее чем N и взаимно простое с ним. Для этого a верно утверждение, [БЕЗ_ЗВУКА] известное как теорема Эйлера. φ(N) здесь — функция Эйлера. Количество чисел меньше, чем N и взаимно просты с ним. Частный случай теоремы Эйлера для простых модулей известен как малая теорема Ферма. Для нашего числа p, состоящего их двух простых чисел, φ(N) = (p- 1)(q- 1). Тогда мы можем в кольце Zφ(N) найти два взаимно простых числа e и d — таких, что e * d = 1 по модулю φ(N). Теперь число e и число N буде у нас открытый ключ; число N и число d — это закрытый ключ. Давайте посмотрим, как они работают. Если мы какое-то сообщение возведем в степень e по модулю N (что можно сделать, имея открытый ключ), то мы получим строку, из которой очень сложно получить число N. Если после этого мы возведем эту строку в степень d, тоже по модулю N, то мы вспоминаем, что e * d сравнимо с единицей по модулю φ(N). Это будет равно e в степени φ(N) умножить на какое-то число k плюс 1. по модулю N. Вот это вот у нас равно как мы помним по теореме Эйлера 1, и получается, что это у нас просто e(N). Таким образом, владея числом d, зная число d, мы можем расшифровать сообщение, которое зашифровано таким вот образом. Проблема в том, что для того, чтобы найти число e зная число d надо знать функцию Эйлера. Например, надо знать функцию Эйлера от N, и для того, чтобы знать функцию Эйлера, хорошо бы знать разложение числа N на простые множители. Задача разложения на простые множители, как мы знаем, сложна. Для демонстрации алгоритма давайте рассмотрим небольшой пример. Пусть у нас p будет равно 11, а q — 13. Тогда число N = 11 * 13, это 143. φ(N), соответственно, 10 * 12 = = 120. Ну и давайте возьмем какое-то число e, взаимно простое и со 120, и с 11, и с 13. Например, пускай это будет 17. 17 и 143 — это наш открытый ключ. [БЕЗ_ЗВУКА] Теперь нам нужно найти число d такое, что e * d = 1 + 120 * k. Можно сделать это, например, расширенным алгоритмом iii, а можно, например, заметить, что d равное- 7 нам подходит. Это равно 113 по модулю 120. Соответственно, число 113 будет нашим закрытым ключом. Давайте что-нибудь зашифруем. Например, пускай полезное сообщение у нас будет число 7. Тогда для того, чтобы зашифровать это полезное сообщение, нам надо возвести 7 в степень 17 по модулю 143. Это нет так сложно сделать, как кажется. 7 в степени 17 это 7 в степени 16 умножить на 7. Это 49 в 8-ой степени умножить на 7. 49 в квадрате, 2401 в 4-ой степени умножить на 7. Это число мы уже можем взять по модулю 143, получится 113 в 4-ой степени опять умножить на 7, ну и так далее. Я, как вы понимаете, знаю результат. У нас получится число 50 по модулю 143. Итак, число 50 — это наше зашифрованное сообщение из которого нам нужно теперь обратно получить число 7. Для того, чтобы получить число 7, нам нужно знать закрытый ключ, число d, и теперь число 50 нам надо возвести в 113-ую степень. Естественно, опять же по модулю 143. Мы можем честно это делать, а можем не делать, потому что только что мы с вами доказали, что это число будет равно 7 по модулю 143. Для собственного удовольствия вы можете проделать эту операцию честно. Как мы видим, вся надежность алгоритма основана на том, что злоумышленник, зная число N, не может за разумное время узнать числа p и q. Все изменилось с появлением алгоритма Шора.
