Материал: Лекция 5 Квантовые вычисления и оценка стойкости криптоалгоритмов

Криптосистема РША

Рис. 1. Схематическое описание криптосистемы РША

26

Квантовый компьютер и криптосистема РША

•В ранних криптостойких системах использовались целые числа с 400 болеедвоичными числами. (1994г.)

•На компьютере 1994г. потребуется~109 лет для разложения такого числа на множители.

•Квантовый компьютер, равный по скорости счета такомукомпьютеру, справится с этой задачей за секунды (алгоритм Шора)

27

Пример длинного числа

Стойкость алгоритма РША основывается на вычислительной сложности решения задачи факторизации модуля n=nq

28

Сравнение классическогои квантового компьютера для RSA

Количество

Операции

факторизации

Современные

требования

Кол-во бит Модуля

29

Алгоритм факторизациичисла на квантовом компьютере Питера Шора, 1994г.

30