Факторизация и RSA

Loading...

Из курса от партнера Saint Petersburg State University

Квантовые вычисления (Quantum computing)

20 оценки

Saint Petersburg State University

Квантовые вычисления (Quantum computing)

20 оценки

О квантовых вычислениях много пишут и говорят, особенно в последнее время. Причины такого интереса вполне очевидны - потребность в новом поколении вычислительных устройств назрела уже давно, и квантовый компьютер - первый кандидат на то, чтобы стать этим новым поколением. Для работы с новыми, только возникающими технологиями требуются специалисты, разбирающиеся в основах этих технологий - инженеры, физики, математики, алгоритмисты... Это - те люди, которые, возможно, станут у истоков новой эры и смогут поучаствовать в осуществлении очередного грандиозного шага в развитии человечества. Затронуть все аспекты темы квантовых вычислений в рамках одного MOOC не представляется возможным, поэтому данный курс охватывает только одну их область - анализ и проектирование квантовых алгоритмов. Прослушав курс, вы: 1. Разберетесь с моделью квантовых вычислений и поймете, что такое квантовый компьютер с точки зрения алгоритмиста и математика. 2. Познакомитесь с простыми (и не очень простыми) квантовыми алгоритмами и получите начальные навыки их проектирования. 3. Просто получите удовольствие, всегда сопровождающее познание чего-то нового. Команда курса желает вам успехов в освоении материала. Мы будем искренне рады, если знания, полученные вами здесь, помогут вам в достижении новых теоретических и практических результатов.

Из урока

Алгоритм Шора

В этом модуле мы разберем самый известный квантовый алгоритм - алгоритм Шора, позволяющий эффективно раскладывать составное число на множители.

Вступление4:32

Факторизация и RSA6:54

Поиск периода и факторизация14:48

Познакомьтесь с преподавателями

Сысоев Сергей Сергеевич
кандидат физико-математических наук
Кафедра системного программирования

[МУЗЫКА]

[МУЗЫКА] [МУЗЫКА]

Нам будет полезно вспомнить алгоритм 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.

Все изменилось с появлением алгоритма Шора.

Ознакомьтесь с нашим каталогом

Присоединяйтесь бесплатно и получайте персонализированные рекомендации, обновления и предложения.

Coursera делает лучшее в мире образование доступным каждому, предлагая онлайн-курсы от ведущих университетов и организаций.

© Coursera Inc., 2018 Все права защищены.

Загрузить из App Store

Загрузить в Google Play