Курс "Защита информации", кафедра радиотехники, Московский физико-технический институт (МФТИ)

2010: Главная Экзамен Лекции Семинары Проекты Эссе | Преподаватели Литература | Архив: 2009 2008-fall 2008 2007 2006 2005 2004 2003 | English
HTML-версия эссе "Security of RSA factorization problem quantum computer", Chernyshev, 2004, сгенерированная из pdf/rtf.
Конвертация не вcегда корректна. Смотрите исходный pdf.

МОСКОВСКИЙ ФИЗИКО-ТЕХНИЧЕСКИЙ ИНСТИТУТ

Криптостойкость RSA, задача факторизации, квантовый компьютер

Чернышев М.Н. гр. 016

2004 г.

Введение

Алгоритм RSA является самым распространенным алгоритмом шифрования с открытым ключом. Фирмой RSA Data Security, Inc. было продано около 450 миллионов лицензий на программный продукт, реализующий данный алгоритм. Его популярность вполне объяснима. С бурным развитием телекоммуникационных технологий возникла потребность в быстром и безопасном обмене данными. Симметричные системы шифрования плохо решали эти задачи из-за проблемы безопасной передачи ключей.

Впервые идея криптографии с открытым ключом была предложена в 1976 г У. Диффи (Whitefield Diffie ) и M. Хеллманом (Martin Hellman). Основным тезисом их концепции было предложение использовать два типа ключей: ключи для шифрования и ключи для расшифрования. Причем ключ расшифрования нельзя найти по ключу шифрования.

С 1976 года было создано большое количество подобных алгоритмов. Многие из них оказались нестойкими, многие стойкие оказались труднореалезуемыми из-за слишком большой длины ключа или криптотекста. И лишь очень небольшая часть алгоритмов оказались достаточно защищенными и пригодными для практической реализации. Как правило, эти алгоритмы основываются на решении трудных математических задач. В частности, в алгоритме RSA (Ron Rivest, Adi Shamir, Leonard Adleman) такой задачей является разложение больших чисел на простые множители.

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

Описание алгоритма RSA

Для генерации ключей (открытого и секретного) применяются два случайных простых числа p и q. Для обеспечения необходимой безопасности они должны быть достаточно большими и иметь равную длину. Затем рассчитывается произведение n=pq

После этого случайным образом выбирается число e, взаимно простое с (p-1)(q-1). Пара чисел e и n является открытым ключом (ключом шифрования). Теперь с помощью расширенного алгоритма Евклида вычисляется секретный ключ (ключ расшифрования) d, такой, что:

Для шифрования сообщение разбивается на цифровые блоки, размерами меньше n. Криптотекст c будет состоять из блоков той же длины

Шифрование происходит по следующей формуле:

Расшифровка происходит так:

Стойкость алгоритма RSA.

До сих пор математически не доказано, что для восстановления m по e и n обязательно нужно раскладывать число n на множители. Но если будет открыт метод криптоанализа RSA, позволяющий получить d, то этот метод можно будет также использовать для разложения на простые множители числа n. Такие алгоритмы в настоящее время не найдены. Существует несколько достаточно эффективных способов взлома, но они работают только при выборе определенных параметров n, e и d, а также при неосторожном обращении с секретными ключами. Грамотным выборов параметров и четкой системой использования секретных ключей эффективность подобного рода атак сводится к нулю. Таким образом, считается, что стойкость рассматриваемого алгоритма полностью зависит от трудоемкости разложения на множители больших чисел.

Задача факторизации.

Задача разложения на простые множители является одной из древнейшей задач теории чисел. Все существующие алгоритмы не очень сложны, но их выполнение занимает много времени. На настоящее время самым лучшим алгоритмом факторизации считается метод «Общее решето числового поля». Эвристическая оценка времени его выполнения такова:

В таблице приведены рекорды разложения на множители чисел RSA-k. Каждое число RSA-k имеет k десятичных разрядов и состоит из двух близких простых множителей.

Число

Дата

Сложность, MIPS-лет

Алгоритм

RSA-100

Апрель 1991

7

Квадратичного решета

RSA-110

Апрель 1992

75

Квадратичного решета

RSA-120

Июнь 1993

830

Квадратичного решета

RSA-129

Апрель 1994

5000

Квадратичного решета

RSA-130

Апрель 1996

500

Обобщенного квадратичного решета

RSA-140

Февраль 1999

2000

Обобщенного квадратичного решета

RSA-155

Август 1999

8000

Обобщенного квадратичного решета

Данные о трудности проекта RSA – 140 позволяют спрогнозировать сложность разложения более длинных чисел:

Разрядность (бит)

512

768

1024

Сложность (относительно RSA-140)

6.5

4104

49106

Требуемая оперативная память (относительно RSA-140)

2.5

2102

7103

Таким образом, 512-битные ключи уже не обеспечивают хорошей защищенности (группа ученых за несколько месяцев, используя большой вычислительный кластер, потратив несколько миллионов долларов, могут вскрыть наше сообщение). Но вскрытие 1024-битных ключей все еще недоступно современной вычислительной технике. Дальнейшее развитие алгоритмов факторизации приведет, по видимому, к уменьшению константы 1,923 в показателе экспоненты сложности. При уменьшении этого показателя до 1,5 уже сегодня можно раскладывать на множители 1024-битные числа. Тем не менее из-за экспоненциальности сложности данной задачи стойкость можно обеспечить выбором достаточно длинного ключа. Современные алгоритмы позволяют эффективно получать простые числа практически любой длины (до миллиона десятичных разрядов).

Квантовый компьютер.

Задача факторизации, вычислительно трудная для современной компьютерной техники, могла бы быть легко решена при использовании устройств, называемых квантовыми компьютерами. Кратко рассмотрим их устройство.

Память или регистры квантового компьютера, так же как и в случае обычного компьютера, состоят из двухуровневых ячеек. Простейшим примером такой квантовой ячейки является частица со спином . Проекция спина на выбранное направление может принимать значения и . По аналогии с обычной классической ячейкой памяти обозначим одно из состояний нулем, а другое – единицей. Фундаментальным отличием квантовой ячейки от классической является то, что состояние квантовой ячейки является вероятностным. Это означает, что квантовая ячейка может принимать не только «чистые» состояния и , но «смешанные» состояния , где| и определяют вероятность обнаружить систему в нулевом единичном состоянии соответственно. Таким образом, квантовый регистр, состоящий из L квантовых ячеек, имеет 2L базисных состояний. Именно возможность принимать смешанные значения придает квантовому компьютеру его уникальные свойства.

Допустим, у нас есть квантовый регистр, находящийся в некотором состоянии, например, |10110001010010…> = |a>, состояния всех его бит являются чистыми. Осуществляя некоторую вычислительную процедуру |a,0> → |a,f(a)> над двумя регистрами, мы находим значение некой функции от содержимого рассматриваемого регистра. В этом случае квантовый компьютер ничем не отличается от классического и не проявляет своих уникальных свойств. Переведем теперь исходный регистр |a> в состояние, при котором каждый квантовый бит будет равновероятно принимать значения нуля и единицы, т.е. . При этом состояние всего регистра будет описываться следующим образом: , . Проведя ту же самую вычислительную процедуру, на выходе мы получим уже значение функции для всевозможных значений входного аргумента:. Таким образом, за один такт работы квантовый компьютер параллельно выполняет экспоненциально большой объем вычислений.

В качестве примера использования квантового параллелизма рассмотрим задачу нахождения периода последовательности f(0), f(1), … , f(q-1). Для этого введем операцию квантового дискретного преобразования Фурье: . Проведя данное преобразование над суперпозицией , получим: . Пусть последовательность f(a) имеет период r, то есть f(a + r) = f(a), тогда при суммировании по a конструктивная интерференция происходит при условии, что кратно . При всех других значениях происходит в большей или меньшей степени деструктивная интерференция. Таким образом, распределение вероятностей состояний регистра с будет носить следующий характер:

Одиночное вычисление и измерение c даст нам случайное значение, соответствующее одному из пиков максимума вероятности W(с). Таким образом, решение задачи нахождения периода последовательности носит вероятностный характер. Но ничто не мешает сделать эту вероятность сколь угодно близкой к единице.

При решении подобной задачи с помощью обычного компьютера, нам понадобилось бы вычислить, по крайней мере, r значений функции f. То есть, объем вычислений экспоненциально увеличивается при увеличении разрядности входных данных. При решении же данной задачи на квантовом компьютере разрядность входных данных слабо влияет на длительность вычислений (полиномиально).

Перейдем теперь к интересующей нас задаче факторизации чисел. Мы хотим факторизовать число N. Выберем некоторое число x, взаимно простое с N. Взаимную простоту можно установить с помощью достаточно эффективного алгоритма Евклида. Рассмотрим последовательность, образованную функцией . Последовательности { и { имеют следующий вид:

r-минимальная степень, для которой

Видно, что последовательность имеет периодическую структуру. При использовании стандартных алгоритмов задача нахождения периода длинной последовательности является трудной. Но применив квантовый компьютер, мы можем достаточно быстро найти ее период r.

Далее подбираем такое значение x, что последовательность имеет четный период r.

Это означает, что произведение в левой части равенства кратно N, то есть одна из скобок должна иметь общий множитель с N. Для завершения факторизации вычислим НОД каждого из сомножителей с N (эта процедура достаточно эффективна). Найденный общий делитель и будет решением задачи.

В качестве примера реализации данного алгоритма разложим на множители число 133. Примем x=2 .

Период последовательности r =18.

Находим НОД(513, 133):

W(c)

3

Таким образом, мы нашли делители исходного числа и тем самым, решили поставленную задачу.

Заключение

Уже доказано, что теоретических преград на пути конструирования квантового компьютера нет. Но технологически эта задача очень сложна. И трудности заключаются в чрезвычайной подверженности квантовых систем к внешнему воздействию. Достаточно всего мизерного нежелательного воздействия (поглощение одного кванта электромагнитного излучения или кратковременное включение сверхслабого магнитного поля), чтобы коренным образом исказить результаты вычислений. В настоящее время высшим результатом в этой области является создание 4-битного подобного устройства в исследовательской лаборатории компании IBM. Программирование устройства осуществлялось электромагнитными импульсами, а считывание данных ЯМР-сканером. Этот прототип квантового компьютера смог разложить на простые множители число 15. Но технологии не стоят на месте, и возможно, в скором будущем эти устройства станут достаточно совершенными, чтобы быстро решать задачу факторизации больших чисел.

Литература

1. Брюс Шнайер. «Прикладная криптография». М. «Издательство Триумф», 2003 г. Bruce Schneier «Applied Cryptography»
2. Харин Ю.С., Берник В.И, Матвеев Г.В., Агиевич С.В. «Математические и компьютерные основы криптологии». Минск, «Издательство «Белорусский Дом печати», 2003 г.
3. С. Браунштейн (Samuel L. Braunstein) «Квантовые вычисления: учебное руководство»
4. Л. Федичкин «Квантовые компьютеры» http://phys.web.ru/db/msg.html?mid=1168929&uri=page1.html


Page last update: Fri Jun 10 10:12:30 2005 MSD.
Website last update:
Rambler's Top100 Рейтинг@Mail.ru