Применение NP-полных задач в ассиметрично-ключевой криптографии

1. Классы сложности задач в теории алгоритмов

2. NP-задачи

3. NP-полные задачи

4. Общие сведения о симметричной и ассиметрично-ключевой криптографии

5. «Лазейка» в односторонней функции

6. Криптографическая система RSA

7. Атаки RSA

8. Рекомендации для RSA

9. Криптографическая система Эль-Гамаля

10. Безопасность криптосистемы Эль-Гамаля

11. Алгоритм обмена ключами Диффи-Хеллмана Заключение

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

В настоящее время существуют тысячи криптографических систем, реализованных как программно, так и аппаратно. Среди них можно выделить системы, сам криптографический принцип работы которых держится в секрете, как, например, микросхема Clipper, предлагаемая правительством США в качестве криптографического стандарта для телекоммуникаций, и системы, алгоритм которых открыт, а секретной является только определенная, как правило небольшая, порция информации, называемая (секретным) ключом — к ним относится большинство систем, реализуемых программно и предназначенных для широкого использования.

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

Математическое исследование надежности криптографических систем затруднено отсутствием универсального математического понятия сложности. По этой причине надежность большинства криптографических систем в настоящее время невозможно не только доказать, но даже адекватно сформулировать. Как правило, применение той или иной криптографической системы основано на результатах многолетнего практического криптоанализа систем данного типа, в той или иной степени подкрепленных математическим обоснованием. Это обоснование может сводить задачу раскрытия данной криптосистемы к какой-либо задаче теории чисел или комбинаторики, решение которой считается реально не осуществимым, или, что предпочтительнее, к классу NP-полных задач, сводимость к которому является «эталоном» практической неразрешимости. В то же время, понятие практической неразрешимости для конкретных практических задач не является четко определенным или стабильным, благодаря развитию вычислительной техники и методов криптоанализа.

1. Классы сложности задач в теории алгоритмов

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

В рамках классической теории осуществляется классификация задач по классам сложности (P-сложные, NP-сложные, экспоненциально сложные и др.). К классу P относятся задачи, которые могут быть решены за время, полиномиально зависящее от объёма исходных данных, с помощью детерминированной вычислительной машины (например, машины Тьюринга), а к классу NP — задачи, которые могут быть решены за полиномиально выраженное время с помощью недетерминированной вычислительной машины, то есть машины, следующее состояние которой не всегда однозначно определяется предыдущими. Работу такой машины можно представить как разветвляющийся на каждой неоднозначности процесс: задача считается решённой, если хотя бы одна ветвь процесса пришла к ответу. Другое определение класса NP: к классу NP относятся задачи, решение которых с помощью дополнительной информации полиномиальной длины, данной нам свыше, мы можем проверить за полиномиальное время. В частности, к классу NP относятся все задачи, решение которых можно проверить за полиномиальное время. Класс P содержится в классе NP. Классическим примером NP-задачи является задача о коммивояжёре.

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

2. NP-задачи

В теории алгоритмов классом NP (от англ. non-deterministic polynomial) называют множество алгоритмов, время работы которых существенно зависит от размера входных данных; в то же время, если предоставить алгоритму некоторые дополнительные сведения (так называемых свидетелей решения), то он сможет достаточно быстро (за время, не превосходящее многочлена от размера данных) решить задачу.

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

Класс сложности NP определяется для множества языков, т. е. множеств слов над конечным алфавитом У. Язык L называется принадлежащим классу NP, если существуют двуместный предикат из класса P (т.е. вычислимый за полиномиальное время) и многочлен n^c такие, что для всякого слова x условие «x принадлежит L» равносильно условию «найдётся y длины меньше n^c такой, что верно «(где n — длина слова x). Слово y называется свидетелем принадлежности x языку L. Таким образом, если у нас есть слово, принадлежащее языку, и ещё одно слово-свидетель ограниченной длины (которое бывает трудно найти), то мы быстро сможем удостовериться в том, что x действительно принадлежит L.

Эквивалентное определение можно получить, используя понятие недетерминированной машины Тьюринга (т. е. такой машины Тьюринга, у программы которой могут существовать разные строки с одинаковой левой частью). Если машина встретила «развилку», т. е. неоднозначность в программе, то дальше возможны разные варианты вычисления. Предикат R (x), который представляет данная недетерминированная машина Тьюринга, считается равным единице, если существует хоть один вариант вычисления, возвращающий 1, и нулю, если все варианты возвращают 0. Если длина вычисления, дающего 1, не превосходит некоторого многочлена от длины x, то предикат называется принадлежащим классу NP. Если у языка существует распознающий его предикат из класса NP, то язык называется принадлежащим классу NP. Это определение эквивалентно приведённому выше: в качестве свидетеля можно взять номера нужных веток при развилках в вычислении. Так как для x принадлежащему языку длина всего пути вычисления не превосходит многочлена от длины x, то и длина свидетеля также будет ограничена многочленом от длины x.

Всякую задачу, принадлежащую NP, можно решить за экспоненциальное время перебором всех возможных свидетелей длины меньше n^c.

Легко видеть, что множество языков из NP не замкнуто относительно дополнения. Класс языков, дополнение которых принадлежит NP, называется классом co-NP.

Примеры задач класса NP

Можно привести много задач, про которые на сегодняшний день неизвестно, принадлежат ли они P, но известно, что они принадлежат NP. Среди них:

· Задача выполнимости булевых формул: узнать по данной булевой формуле, существует ли набор входящих в неё переменных, обращающий её в 1. Свидетель — такой набор.

· Задача о клике: по данному графу узнать, есть ли в нём клики (полные подграфы) данного размера. Свидетель — номера вершин, образующих клику.

· Проблема существования гамильтонова цикла в графе. Свидетель — последовательность вершин, образующих гамильтонов цикл.

· Задача о коммивояжёре — расширенный и более приближенный к реальности вариант предыдущей задачи.

· Существование целочисленного решения системы линейных неравенств. Свидетель — решение.

Среди всех задач класса NP можно выделить «самые сложные» — NP-полные задачи. Если мы научимся решать любую из них за полиномиальное время, то все задачи класса NP можно будет решить за полиномиальное время. (См. также список таких задач.)

3. NP-полные задачи

В теории алгоритмов NP-полная задача — это такая задача из класса NP, к которой можно свести любую другую задачу из класса NP. Таким образом, NP-полные задачи образуют в некотором смысле подмножество «самых сложных» задач в классе NP; и если для какой-то из них будет найден «быстрый» алгоритм решения, то и любая другая задача из класса NP может быть решена так же «быстро».

Алфавитом называется всякое конечное множество символов (например, {0,1} или {a, b, c}). Множество всех возможных слов (конечных строк, составленных из символов этого алфавита) над некоторым алфавитом У обозначается У ^*. Языком L над алфавитом У называется всякое подмножество множества У ^*, то есть .

Задачей распознавания слова для языка L называется определение того, принадлежит ли данное слово языку L.

Язык L₁ называется сводимым (по Карпу) к языку L₂, если существует функция,, вычислимая за полиномиальное время, и обладающая следующим свойством: тогда и только тогда, когда .

Сводимость по Карпу обозначается как или .

Язык L₂ называется NP-трудным, если любой язык из класса NP сводится к нему. Язык называют NP-полным, если он NP-труден, и при этом сам лежит в классе NP.

Таким образом, если будет найден алгоритм, решающий некоторую (любую) NP-полную задачу за полиномиальное время, то все NP-задачи окажутся в классе P, то есть будут решаться за полиномиальное время.

Примеры NP-полных задач

· Задача о выполнимости булевых формул

· Кратчайшее решение «пятнашек» размера

· Задача коммивояжёра

· Проблема раскраски графа

· Задача о вершинном покрытии

· Задача о покрытии множества

· Задача о клике

· Задача о независимом множестве

· Сапер (игра)

· Тетрис

4. Общие сведения о симметричной и ассиметрично-ключевой криптографии

Симметричная и асимметрично-ключевая криптографии будут существовать параллельно и продолжать обслуживать общество. Они дополняют друг друга; преимущества одной компенсируют недостатки другой.

Концептуальные отличия между этими двумя системами базируются на том, как эти системы сохраняют секретность. В криптографии с симметричными ключами задача секретности должна быть разделена между двумя людьми. В асимметрично-ключевой криптографии секретность — персональная задача (неразделенная); человек создает и сохраняет свою собственную тайну.

В сообществе n людей при криптографии с симметричными ключами для сохранения секретности требуется n (n — 1)/2 общедоступных ключей. В асимметрично-ключевой криптографии необходимы только n персональных ключей. Сообщество с количеством участников 1 миллион при криптографии с симметричными ключами требовало бы пятисот миллионов общедоступных ключей; асимметрично-ключевая криптография требовала бы 1 миллион персональных ключей.

Криптография с симметричными ключами базируется на совместном использовании ключей; асимметрично-ключевая криптография базируется на персональном ключе.

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

Обратим внимание на то, что криптография с симметричными ключами базируется на подстановке и перестановке символов (символов или бит), а асимметрично-ключевая криптография — на применении математических функций к числам. В криптографии с симметричными ключами исходный текст и зашифрованный текст представляют как комбинацию символов. Шифрование и дешифрование здесь — это перестановка этих символов или замена одного символа другим. В асимметрично-ключевой криптографии исходный текст и зашифрованный текст — числа; их шифрование и дешифрование — это математические функции, которые применяются к числам, чтобы создать другие числа.

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

Асимметричная ключевая криптография использует два отдельных ключа: один секретный (частный) и один открытый (общедоступный); шифрование и дешифрование представляют процесс запирания и отпирания замков ключами. В этом случае замок, запертый открытым ключом доступа, можно отпереть только с соответствующим секретным ключом. Рис. 1 показывает, что если Алиса запирает замок открытым ключом доступа Боба, то только секретный ключ Боба может отпереть его.

Рис. 1. Закрытие и открытие в асимметрично — ключевой криптосистеме Рис. 2 показывает общую идею асимметрично-ключевой криптографии при использовании для шифрования. Как показывают рисунки, в отличие от криптографии с симметричными ключами при асимметрично-ключевой криптографии ключи отличаются: существует секретный ключ и открытый ключи доступа.

Рис. 2. Общая идея асимметрично-ключевой криптосистемы Первый ключ работает обычно со строкой символов (например, биты), второй — с числами или множеством чисел. Рис. 2 иллюстрирует несколько важных фактов.

Первый: подчеркивает асимметричный характер криптографической системы. Ответственность за обеспечение безопасности находится, главным образом, на плечах приемника (в данном случае это Боб). Боб должен создать два ключа: один секретный (частный) и один открытый (общедоступный). Боб не несет ответственность за распределение открытого ключа доступа всему сообществу. Это может быть сделано через канал распределения открытого ключа доступа. Хотя этот канал не обязан обеспечивать секретность, он должен обеспечить установление подлинности и целостность информации о ключе. Ева не должна иметь возможности распространять свой открытый ключ сообществу, представляя его как открытый ключ доступа Боба. На данный момент мы принимаем, что такой канал существует.

Второй факт: асимметрично-ключевая криптография означает, что Боб и Алиса не могут использовать одно и то же множество ключей для двухсторонней связи. Каждый объект в сообществе создает свой собственный секретный и открытый ключи доступа. Рис. 2 показывает, как Алиса может использовать открытый ключ доступа Боба, чтобы передать Бобу зашифрованные сообщения. Если Боб хочет ответить, Алиса устанавливает свои собственные секретный и открытый ключи доступа.

Третий: асимметрично-ключевая криптография означает, что Боб нуждается только в одном секретном ключе, чтобы получать всю корреспонденцию от любого участника сообщества. Алиса нуждается в ключах, чтобы связаться с n объектами в сообществе — один ключ доступа для каждого. Другими словами, Алиса нуждается в кольце ключей доступа.

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

Шифрование и дешифрование в асимметрично-ключевой криптографии — математические функции, которые применяются к числам, представляющим исходный текст и зашифрованный текст. Зашифрованный текст можно представлять себе как C = f (K _public, P). Исходный текст можно представлять себе как P = g (K _private, С). Функция f шифрования используется только для шифрования; функция дешифрования g используется для дешифрования. Далее мы покажем, что функция f нуждается в «лазейке» односторонней функции, чтобы позволить Бобу расшифровывать сообщение, но препятствовать Еве делать то же самое.

Есть очень важный факт, который иногда неправильно истолковывается. Появление асимметрично-ключевой криптографии (открытый ключ доступа) не устраняет потребность в криптографии с симметричными ключами (секретный ключ). Причина в том, что криптография с асимметричными ключами использует математические функции для шифрования и дешифрования намного медленнее, чем криптография с симметричными ключами. Для шифровки больших сообщений криптография с симметричными ключами необходима. С другой стороны, скорость криптографии с симметричными ключами не устраняет потребность в асимметрично-ключевой криптографии. Асимметрично-ключевая криптография необходима для установления подлинности цифровых подписей и работы станций по рассылке ключей засекречивания. Это означает способность системы использовать все аспекты безопасности. Сегодня мы нуждаемся в обеих системах криптографии. Одна криптосистема дополняет другую.

5. «Лазейка» в односторонней функции

Главная идея асимметрично-ключевой криптографии — понятие «лазейки» в односторонней функции.

Хотя понятие функции знакомо из математики, мы дадим неофициальное определение здесь. Функция — правило, по которому связывают (отображают) один элемент во множестве A, называемый доменом, и один элемент во множестве B, называемый диапазоном, как показано на рис. 3.

Рис. 3. Функция отображения домена в диапазон Обратимая функция — функция, которая связывает каждый элемент в диапазоне с точно одним элементом в домене.

Односторонняя функция — функция, которая обладает следующими двумя свойствами:

1. f вычисляется просто. Другими словами, при данном x может быть легко вычислен y = f (x).

2. f ^-1 вычисляется трудно. Другими словами, при данном y, вычислить x= f ^~1 (y) неосуществимо.

«Лазейка» в односторонней функции — односторонняя функция с третьим свойством:

3. При данном y и ловушке (секретной) x может быть легко вычислен.

Пример 1

Когда n является большим, — односторонняя функция. Обратите внимание, что в этой функции x — кортеж (p, q) двух простых чисел, а y в данном случаеэто n. При заданных p и q всегда просто вычислить n. При данном n очень трудно вычислить p и q. Это — проблема разложения на множители. В этом случае для нахождения функции f ^-1 нет решения с полиномиальным временем.

Пример 2

Когда n является большим, функция y = x^k mod n — «лазейка» в односторонней функции. При заданных x, k и n просто вычислить y, используя алгоритм быстрого возведения в степень. При заданных y, k и n очень трудно вычислить y. Это — проблема дискретного логарифма. В этом случае нет решения с полиномиальным временем для функции f ^-1. Однако если мы знаем «лазейку» и k', такое, что, мы можем использовать x = y^k mod n, чтобы найти x. Это — известный алгоритм (RSA — Riverst-Shamir-Adelman), который будет рассмотрен позже.

6. Криптографическая система RSA

Самый общий алгоритм открытого ключа доступа — криптографическая система RSА, названная по имени его изобретателей Ривеста, Шамира, Эделмана (Rivest, Shamir и Adelman).

RSА использует два типа ключей — e и d, где e — открытый, a d — секретный. Предположим, что P — исходный текст и C — зашифрованный текст. Алиса использует C = P^e mod n, чтобы создать зашифрованный текст C из исходного текста P; Боб использует P = C^d mod n, чтобы извлечь исходный текст (файл), переданный Алисой. Модулей n создается очень большое количество с помощью процесса генерации ключей, который мы обсудим позже.

Для шифрования и дешифрования применяют возведение в степень по модулю. При использовании быстрого алгоритма возведение в степень по модулю выполнимо в полиномиальное время. Однако нахождение модульного логарифма так же сложно, как и разложение числа по модулю. Для него нет алгоритма с полиномиальным временем. Это означает, что Алиса может зашифровать сообщение общедоступным ключом (e) в полиномиальное время. Боб также может расшифровать его в полиномиальное время (потому что он знает d). Но Ева не может расшифровать это сообщение, потому что она должна была бы вычислить корень e-той степени из C с использованием модульной арифметики. Рис. 4 показывает идею RSA.

Рис. 4 Сложность операций в RSA

Другими словами, Алиса использует одностороннюю функцию (возведение в степень по модулю) с лазейкой, известной только Бобу. Ева не знает лазейку, поэтому не может расшифровать сообщение. Если когда-нибудь найдут полиномиальный алгоритм для модуля вычисления корня e-той степени из n, то возведение в степень по модулю n не будет больше односторонней функцией.

Рис. 5 показывает общую идею процедуры, используемой в RSA.

RSA использует возведение в степень по модулю для шифрования/дешифрования. Для того чтобы атаковать закрытый текст, Ева должна вычислить

Рис. 5 Шифрование, дешифрование и генерация ключей в RSA

RSA использует две алгебраических структуры: кольцо и группу.

Кольца шифрования/дешифрования. Шифрование и дешифрование сделаны с использованием коммутативного кольца с двумя арифметическими операциями: сложение и умножение. В RSA это кольцо общедоступно, потому что модуль n общедоступен. Любой может послать сообщение Бобу, используя это кольцо для шифрования.

Группы генерирования ключей. RSA использует мультипликативную группу для генерации ключей. Группа поддерживает только умножение и деление (мультипликативную инверсию), которые необходимы для того, чтобы создать открытые и секретные ключи. Эту группу надо скрыть, потому что ее модуль является секретным. Мы увидим, что если Ева найдет этот модуль, она сможет легко атаковать криптографическую систему.

RSA использует две алгебраических структуры: открытое кольцо R = < Z_n, +,? > и секретную группу G = < Z_(n)*,? >.

Алгоритм создания открытого и секретного ключей.

• Выбираются два случайных простых числа p и q

• Вычисляется их произведение n=p*q, которое называется модулем.

• Вычисляется значение функции Эйлера от числа n:

ц (n)=(p-1)(q-1)

• Выбирается открытый ключ е с учетом условий:

• Определяется секретный ключ d, удовлетворяющего условию:

e*d?1 (mod ц (n)), где d

• Пара P=(e, n) публикуется в качестве открытого ключа RSA

• Пара S=(d, n) играет роль секретного ключа RSA и держится в секрете

Боб использует шаги, показанные в данном алгоритме, чтобы создать свои открытый и секретный ключи. После генерации ключей Боб объявляет кортеж (e, n) как свой открытый ключ доступа: Боб сохраняет d как свой секретный ключ. Боб может отказаться от p, q и; они не могут изменить его секретный ключ, не изменяя модуль. Для безопасности рекомендуется размер для каждого простого p или q — 512 бит (почти 154 десятичные цифры). Это определяет размер модуля, n 1024 бита (309 цифр).

В RSA кортеж (e, n) — открытый ключ доступа; целое число d — секретный ключ.

Алгоритм шифрования сообщения P

· Разбиваем исходный текст на блоки P₁, P₂, …, P_m

· Шифруем текст сообщения в виде последовательности блоков

C_j= P_j^е mod n (j =1,n)

Алгоритм расшифрования

Чтобы расшифровать эти данные, используя секретный ключ (d, n), необходимо выполнить следующие вычисления: P_j= C_j^d mod n (j =1,n) В результате будет получено множество чисел P (j), которые представляют собой исходный текст.

В RSA p и q должны быть по крайней мере 512 битов; n должны быть по крайней мере 1024 бит.

Пример 3

Боб выбирает 7 и 11 как p и q и вычисляет. Значение или 60. Теперь он выбирает два ключа, e и d, из Z₆₀^*. Если он выбирает e = 13, то d = 37. Обратите внимание, что (они инверсны друг другу). Теперь предположим, что Алиса хочет передать исходный текст 5 Бобу. Она использует общедоступный ключ 13, чтобы зашифровать 5.

Исходный текст:5

C = 5¹³ = 26 mod 77

Зашифрованный текст: 26

Боб получает зашифрованный текст 26 и использует секретный ключ 37, чтобы расшифровать зашифрованный текст.

Зашифрованный текст: 26

P = от 26³⁷ до 5 mod 77

Исходный текст 5

Переданный Алисой текст получен Бобом как исходный текст 5.

Пример 4

Теперь предположим, что другой человек, Джон, хочет передать сообщение Бобу. Джон может использовать открытый ключ доступа, объявленный Бобом (вероятно, на его сайте), — 13; исходный текст Джона — 63. Джон делает следующие вычисления:

Исходный текст: 63

C = 63¹³ = 28 mod 77

Зашифрованный текст: 28

Боб получает зашифрованный текст 28 и использует свой секретный ключ 37, чтобы расшифровать зашифрованный текст.

Зашифрованный текст: 28

P = 28³⁷ = 63 mod 77

Исходный текст: 63

Пример 5

Дженнифер создает пару ключей для себя. Она выбирает p = 397 и q = 401. Она вычисляет. Затем она вычисляет. Затем она выбирает e = 343 и d = 12 007. Покажите, как Тэд может передать сообщение «No» Дженнифер, если он знает e и n.

Решение Предположим, что Тэд хочет передать сообщение «No» Дженнифер. Он изменяет каждый символ на число (от 00 до 25), сопоставляет каждой букве число, содержащее две цифры. Затем он связывает два кодированных символа и получает четырехзначное число. Исходный текст — 1314. Затем Тэд использует e и n, чтобы зашифровать сообщение. Зашифрованный текст 1314³⁴³ = 33 677 mod 159 197. Дженнифер получает сообщение 33 677 и использует d ключ дешифрования, чтобы расшифровать это сообщение: 33 677^12 007 = 1314 mod 159 197. Затем Дженнифер расшифровывает 1314 как сообщение «No». Рисунок 14.7 показывает этот процесс.

Рис. 6 Шифрование и дешифрование в примере 5

7. Атаки RSA

До настоящего момента не было обнаружено никаких разрушительных атак RSА. Несколько атак были предсказаны. Они основаны на слабом исходном тексте, слабом выборе параметра или несоответствующей реализации. Рис. 7 показывает категории потенциальных атак.

Рис. 7 Диаграмма возможных атак на RSA

· Атака разложения на множители Безопасность RSА базируется на следующей идее: модуль настолько большой, что разложение на множители в разумное время неосуществимо. Боб выбирает p и q и вычисляет. Число n общедоступно, p и q являются секретными. Если Ева сможет разложить на множители n и получить p и q, то она может вычислить. Затем Ева тогда может вычислить, потому что e общедоступен. Секретный ключ d — лазейка, которую Ева может использовать, чтобы расшифровать зашифрованное сообщение.

Существует много алгоритмов разложения на множители, но ни один из них не может найти сомножители большого целого числа с полиномиальной сложностью времени. Для того чтобы обеспечить безопасность, RSA требует, чтобы n был больше чем 300 десятичных цифр. Это означает, что модуль должен быть по крайней мере 1024 бита. Даже при использовании мощнейшего и самого быстрого компьютера, доступного на сегодня, разложение на множители целого числа такого размера требует неосуществимо большого времени. Это означает, что RSA безопасен, пока не будет найден эффективный алгоритм разложения на множители.

· Атака с выборкой зашифрованного текста Потенциальная атака RSА базируется на мультипликативном свойстве RSA. Предположим, Алиса создает зашифрованный текст C = P^e mod n и передает C Бобу. Также предположим, что Боб расшифрует произвольный зашифрованный текст для Евы — С₁, отличный от C. Ева перехватывает C и использует следующие шаги, чтобы найти P:

а. Ева выбирает случайное целое число X в Z_n*.

б. Ева вычисляет .

в. Ева передает Y Бобу для дешифрования и получает Z = Y^d mod n; это шаг атаки выборкой зашифрованного текста.

г. Ева может легко найти P, потому что

Z = Y^d mod n = (C? X^e)^d mod n = (C^d? X^ed) mod n = (C^d? X) mod n = (P? X) mod n

Z = (P? X) mod n P=Z? X^-1 mod n

Ева использует расширенный евклидов алгоритм для того, чтобы найти мультипликативную инверсию X, и в конечном счете значение P.

· Атаки на показатель степени шифрования Чтобы уменьшить время шифрования, можно попытаться использовать короткий ключ шифрования — малое значение числа e, например, значение для e, такое как e = 3 (второе простое число). Однако есть некоторые потенциальные атаки на показатель при его малом значении степени шифрования, которые мы здесь кратко обсуждаем. Эти атаки вообще не кончаются вскрытием системы, но они все-таки должны быть предотвращены. Для того чтобы сорвать эти виды атак, рекомендуется использовать e = 2¹⁶ + 1 = 65 537 (или простое число, близкое к этому значению).

· Атака теоремы Куперcмита (Coppersmith) может быть главной для атаки малого показателя степени на ключ шифрования. Основное положение этой теоремы: для полинома f (x) степени e по модулю n, чтобы найти корни, если один из корней является меньшим чем n^1/e, можно использовать алгоритм сложности, log n. Эта теорема может быть применена к RSA-криптосистеме C = f (P) = P^e mod n. Если e = 3 и известны хотя бы две трети битов в исходном тексте P, алгоритм может найти все биты в исходном тексте.

· Атака широковещательной передачи может быть начата, если один объект передает одно и то же сообщение группе получателей с тем же самым ключом шифрования. Например, предположим следующий сценарий: Алиса хочет передать одно и то же сообщение трем получателям с тем же самым общедоступным ключом e = 3 и модулями n₁, n₂ и n₃.

C₁ = P³ mod n₁

C₂ = P³ mod n₂

C₃ = P³ mod n₃

Применяя китайскую теорему об остатках к этим трем уравнениям, Ева может найти уравнение формы C' = P³ mod n₁n₂n₃. Это означает, что P³ < n₁n₂n₃ и что C' = P³ решается с помощью обычной арифметики (не модульной). Ева может найти значение C' = P^1/3.

· Атака связанных между собой сообщений была обнаружена Франклином Рейтером (Franklin Reiter). Она может быть кратко описана следующим образом. Алиса зашифровала два исходных текста, P₁ и P₂, с помощью e = 3 и передает C₁ и C₂ Бобу. Если P₁ связан с P₂ линейной функцией, то Ева может восстановить P₁ и P₂ в выполнимое время вычисления.

· Атака короткого списка, обнаруженная Куперсмитом, может быть кратко описана следующим образом. Алиса имеет сообщение М для передачи Бобу. Она записывает сообщение и зашифровывает его как сообщение r₁, а результат записывает как C₁ и передает C₁ (Бобу). Ева перехватывает C₁ и удаляет его. Боб сообщает Алисе, что он не получил сообщение, так что Алиса заполняет сообщение, снова зашифровывает как сообщение r₂ и передает это Бобу. Ева также перехватывает и это сообщение. Ева теперь имеет C₁ и C₂, и она знает, что оба зашифрованных текста принадлежат одному и тому же исходному тексту. Куперсмит доказал, что если r₁ и r₂ короткие, то Ева способна восстановить первоначальное сообщение М.

· Атаки показателя степени дешифрации Две формы атак могут быть проведены на показатель степени дешифрации: атака раскрытой степени дешифрации и атака малого показателя степени дешифровации. Они обсуждаются ниже.

· Атака раскрытого показателя степени дешифрации. Очевидно, что если Ева может найти показатель степени дешифрации, d, она сможет расшифровать текущее зашифрованное сообщение. Однако на этом атака не останавливается. Если Ева знает значение d, она может использовать вероятностный алгоритм (не обсуждаемый здесь) к числу n и найти значения p и q. Следовательно, если Боб изменит только угрожающий безопасности показатель степени дешифрования, но сохранит тот же самый модуль n, Ева сможет расшифровать будущие сообщения, потому что она сможет разложить на множители n. Поэтому если Боб узнает, что показатель степени скомпрометирован, он должен выбрать новое значение для p и q, вычислить n и создать полностью новые секретный и открытый ключи доступа.

В RSA, если показатель степени d скомпрометирован, тогда p, q, n, e и d должны быть сгенерированы заново.

· Атака малого значения показателя степени дешифрации. Боб может подумать, что использование малого значения степени секретного ключа d приводит к более быстрой работе алгоритма дешифрации. Винер показал, что в случае d < 1/3n^¼ возможен специальный тип атаки, основанной на цепной дроби, — тема, которая рассматривается в теории чисел. Этот тип атаки может подвергнуть риску безопасность RSА. Для того чтобы это произошло, должно выполняться условие, что q < p < 2q; если эти два условия существуют, Ева может разложить n на сомножители в полиномиальное время.

В RSA рекомендовано, что d должно иметь величину d > 1/3 n^¼, чтобы предотвратить атаку малого значения ключа дешифрации.

· Атаки исходного текста Исходный текст и зашифрованный текст в RSA — это перестановки друг друга, потому что это целые числа в том же самом интервале (от 0 до n — 1). Другими словами, Ева уже знает кое-что об исходном тексте. Эти характеристики могут позволить некоторые атаки исходного текста. Три атаки были уже упомянуты в литературе: атака короткого сообщения, атака циклического повторения и явная атака.

· Атака короткого сообщения. В атаке короткого сообщения, если Ева знает множество возможных исходных текстов, то ей известна еще одна информация и дополнительный факт, что зашифрованный текст — перестановка исходного текста. Ева может зашифровать все возможные сообщения, пока результат не будет совпадать с перехваченным зашифрованным текстом. Например, если известно, что Алиса посылает число с четырьмя цифрами Бобу, Ева может легко испытать числа исходного текста 0000 к 9999, чтобы найти исходный текст. По этой причине короткие сообщения должны быть дополнены случайными битами в начале и конце, чтобы сорвать этот тип атаки. Настоятельно рекомендуется заполнять исходный текст случайными битами прежде начала шифрования. Здесь используется метод, называемый OAEP, который будет позже обсужден в этой лекции.

· Атака циклического повторения построена на факте, что если переставлять зашифрованный текст (перестановка исходного текста), то непрерывное шифрование зашифрованного текста в конечном счете кончится исходным текстом. Другими словами, если Ева непрерывно шифрует перехваченный зашифрованный текст C, она в итоге получит исходный текст. Однако сама Ева не знает, каков исходный текст, так что ей неизвестно, когда пора остановиться. Она должна пройти один шаг далее. Когда она получает зашифрованный текст C снова, она возвращается на один шаг, чтобы найти исходный текст.

Перехваченный зашифрованный текст C

C₁ = C^e mod n

C₂ = C₁^e mod n

…

C_k = C_k-1^e mod n, если C_k = C, останов: исходный текст — P = C_k-1

Может ли это быть серьезной атакой на криптосистему RSA? Показано, что сложность алгоритма эквивалентна сложности разложения на множители n. Другими словами, нет никакого эффективного алгоритма, который может завершить эту атаку в полиномиальное время, если n является большим.

· Явная атака сообщения. Другая атака, которая базируется на отношениях перестановки между исходным текстом и зашифрованным текстом, — явная атака сообщения. Явное сообщение — сообщение, которое зашифровано само в себя (не может быть скрыто). Было доказано, что есть всегда некоторые сообщения, которые шифруются сами в себя. Поскольку ключ шифрования обычно нечетен, имеются некоторые исходные тексты, которые зашифрованы сами в себя, такие как P = 0 и P = 1. Но если ключ шифровки выбран тщательно, число их незначительно. Программа шифровки может всегда проверить, является ли вычисленный зашифрованный текст таким же, как исходный текст, и отклонить исходный текст перед передачей зашифрованного текста.

· Атаки модуля Главной атакой RSA является атака разложения на множители. Ее можно рассматривать как атаку малого модуля. Однако поскольку мы уже обсудили эту атаку, мы концентрируемся на другой атаке модуля: общей атаке модуля.

· Общая атака модуля. Она может быть начата, если сообщество использует общий модуль, n. Например, люди в сообществе могли бы позволить третьей стороне, которой они доверяют, выбирать p и q, вычислять n и и создать пару образцов (e_i, d_i) для каждого объекта. Теперь предположим, что Алиса должна передать сообщение Бобу. Зашифрованный текст Бобу — это Боб использует свой секретный ключ, d_B, чтобы расшифровывать сообщение:. Проблема в том, что Ева может также расшифровать сообщение, если она — член сообщества и ей была назначена пара образцов (e_E и d_E), как мы узнали в разделе «атака малого значения ключа дешифрации». Используя свои собственные ключи (e_E и d_E), Ева может начать вероятностную атаку на сомножители n и найти d_B Боба. Чтобы сорвать этот тип атаки, модуль не должен быть в совместном пользовании. Каждый объект должен вычислить свой собственный модуль.

· Атаки реализации Предыдущие атаки базировались на основной структуре RSА. Как показал Дэн Бонех (Dan Boneh), есть несколько атак реализации RSА. Мы приведем две из них: атака анализом времени и атака мощности.

· Атака анализом времени (Timing attack). Пауль Кочер (Paul Kocher) демонстрировал атаку только зашифрованного текста, называемую атака анализом времени. Атака основана на быстром алгоритме с показательным временем. Использует только возведение во вторую степень, если соответствующий бит в секретном показателе степени d есть 0; он используется и при возведении во вторую степень и умножении, если соответствующий бит — 1. Другими словами, синхронизация требует сделать каждую итерацию более длинной, если соответствующий бит — 1. Эта разность синхронизации позволяет Еве находить значение битов в d, один за другим.

Есть два метода сорвать атаку анализом времени:

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

2. Ривест рекомендовал «ослепление». По этой идее зашифрованный текст умножается на случайное число перед дешифрованием. Процедура содержит следующие шаги:

a. Выбрать секретное случайное число r между 1 и (n — 1).

b. Вычислить .

c. Вычислить P₁ = C₁^d mod n.

d. Вычислить .

· Атака анализом мощности подобна атаке анализом времени. Было показано, что если Ева может точно измерить мощность, использованную в течение дешифрования, она может начать атаку анализа мощности на основании принципов, рассмотренных для атаки анализом времени. Итеративное умножение и возведение в квадрат потребляют больше мощности, чем только итеративное возведение в квадрат. Та же самая группа методов, которая предотвращает атаки анализом времени, может сорвать атаки анализа мощности.

8. Рекомендации для RSA

Следующие рекомендации основаны на теоретических и экспериментальных результатах.

1. Число битов для n должно быть, по крайней мере, 1024. Это означает, что n должно быть приблизительно 2¹⁰²⁴, или 309 десятичных цифр.

2. Два простых числа p и q должны каждый быть по крайней мере 512 битов. Это означает, что p и q должны быть приблизительно 2⁵¹² или 154 десятичными цифрами.

3. Значения p и q не должен быть очень близки друг к другу.

4. p — 1 и q — 1 должны иметь по крайней мере один большой простой сомножитель.

5. Отношение p/q не должно быть близко к рациональному числу с маленьким числителем или знаменателем.

6. Модуль n не должен использоваться совместно.

7. Значение e должно быть 2¹⁶ + 1 или целым числом, близким к этому значению.

8. Если произошла утечка частного ключа d, Боб должен немедленно изменить n так же, как e и d. Было доказано, что знание n и одной пары (e, d) может привести к открытию других пар того же самого модуля.

9. Сообщения должны быть дополнены, используя OAEP, который рассматривается далее.

9. Криптографическая система Эль-Гамаля

Помимо RSA есть другая криптосистема с открытым ключом Эль-Гамаля (ElGamal), которая названа по имени ее изобретателя, Тахира Эль-Гамаля (Taher ElGamal).

Если p — очень большое простое число, e₁ — первообразный корень в группе и r — целое число, тогда e₂ = e₁^r mod p просто вычисляется с использованием быстрого показательного алгоритма (метод «возведения в квадрат и умножения»). Но по данным e₂, e₁ и p, невозможно вычислить r = log_e1e2 mod p (проблема дискретного логарифма).

Рис. 8 показывает генерацию ключей, шифрование и дешифрование в криптосистеме Эль-Гамаля.

Рис. 8 Генерация ключей, шифрование, и дешифрование в криптосистеме Эль-Гамаля Определение общедоступного и частного ключей

• Выбор двух взаимно простых чисел p и e₁, e₁

• Выбор значения секретного ключа d, d

• Определение значения открытого ключа e₂ из выражения:

e₂=e₁^d (mod p)

• Общедоступный ключ (e₁, e₂, p) может быть объявлен публично

Боб использует данный алгоритм, чтобы создать свой общедоступный и частный ключи. Любой может передавать сообщение Бобу, используя открытый ключ. Процесс шифрования сообщения представлен ниже.

Алгоритм шифрования сообщения P

• Выбор случайного числа r, удовлетворяющего условию:

0?r

• Определение значения C₁ из выражения: C₁=e₁^r (mod p)

• Определение значения C₂ из выражения: C₂=e₂^r P (mod p)

• Криптограмма С, состоящая из C₁ и C₂, отправляется получателю

• Получатель расшифровывает криптограмму с помощью выражения:

P = [C₂(C₁^d)^-1]mod p

Пример 6

Боб выбирает 11 в качестве p. Затем он выбирает e₁ = 2. Обратите внимание, что 2 — первообразный корень в Z_11* (см. приложение J). Затем Боб выбирает d = 3 и вычисляет e₂ = e₁^d = 8. Получены открытые ключи доступа — (2, 8, 11) и секретный ключ — 3. Алиса выбирает r = 4 и вычисляет C₁ и C₂ для исходного текста 7.

Исходный текст: 7

C₁ = e₁^r mod 11 = 16 mod 11= 5 mod 11

C₂ = (P? e₂^r) mod 11 = (7? 4096) mod 11 = 6 mod 111

Зашифрованный текст: (5, 6)

Боб получает зашифрованные тексты (5 и 6) и вычисляет исходный текст.

Зашифрованный текст: [C₁? (C₂^d)^-1] mod 11 = 6? (5³)^-1 mod 11 = 6? 3 mod 11 = 7 mod 11

Исходный текст: 7

10. Безопасность криптосистемы Эль-Гамаля

· Атаки малого модуля Если значение модуля p не является достаточно большим, Ева может использовать некоторые эффективные алгоритмы, чтобы решить проблему дискретного логарифма и найти d или r. Если p мало, Ева может просто найти d = log_e1e₂ mod p и сохранить его, чтобы расшифровать любое сообщение, передаваемое Бобу. Это может быть сделано единожды и работать, пока Боб использует те же самые ключи. Ева может также использовать значение случайного числа r, применяемого Алисой в каждой передаче r = log_e1C₁ mod p. Оба этих случая подчеркивают, что безопасность криптосистемы Эль-Гамаля зависит от решения проблемы дискретного логарифма с очень большим модулем. Поэтому рекомендовано, что p должны быть по крайней мере 1024 бита (300 десятичных цифр).

· Атака знания исходного текста Когда Алиса использует одно и то же значение случайного показателя степени r для того, чтобы зашифровать два исходных текста P и P', Ева обнаруживает P', если она знает P. Предположим, что и. Ева находит P', используя следующие шаги:

1. .

2. .

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

Чтобы криптосистема Эль-Гамаля была безопасной, модуль p должен содержать по крайней мере 300 десятичных цифр, новых для каждой шифровки.

11. Алгоритм обмена ключами Диффи-Хеллмана

Алгоримтм Димффи — Хемллмана — алгоритм, позволяющий двум сторонам получить общий секретный ключ, используя незащищенный от прослушивания, но защищённый от подмены, канал связи. Этот ключ может быть использован для шифрования дальнейшего обмена с помощью алгоритма симметричного шифрования.

Алгоритм был впервые опубликован Уитфилдом Диффи и Мартином Хеллманом в 1976 году.

Пускай мы хотим переслать сообщение приятелю так, чтобы никто не подслушал. У нас есть достаточно стойкий способ шифрования: мы знаем, что если даже перехватят зашифрованное сообщение, то без ключа они ни о чем не догадаются. Но чтобы расшифровать сообщение, приятель тоже должен знать ключ — как его передать? Долго считалось, что задача передачи ключа не разрешима принципально, то есть нам придётся встретиться заранее в укромном месте и придумать общий ключ: по открытому каналу мы не договоримся. Что же придумали Диффи и Хеллман: это вообще был крупнейший переворот в истории шифрования.

Во-первых, допустим, у меня есть шкатулка. Я хочу её переслать посылкой, чтобы никто не мог открыть (в границах аналогии — без грубой силы), а приятель мог бы. Как переслать ключ от шкатулки? Я повешу на шкатулку висячий замок и отправлю её без ключа. Приятель, получив посылку, не сможет её открыть, но повесит туда свой собственный замок (от которого ключ только у него) и отправит обратно мне. Я сниму свой замок и снова отправлю приятелю. И теперь он получит шкатулку, которую сможет открыть он, и только он.

Вариант 2. Допустим, мы хотим с приятелем загадать какой-нибудь цвет так, чтобы мы оба его знали, а никто кроме — нет, но у нас нет надёжного канала. У меня есть банка жёлтой краски известного объёма, и у приятеля тоже. Я загадаю какой-нибудь цвет, налью какое-то количество такой краски в банку и хорошо перемешаю. Приятель тоже. Мы обменяемся банками, и каждый повторит с полученной банкой ту же операцию. В результате у каждого будет в банке одинаковый цвет, но никто, перехватив в пути банку, или даже обе, не сможет ничего поделать.

Предположим, что обоим абонентам известны некоторые два числа g и p (например, они могут быть «зашиты» в программное обеспечение), которые не являются секретными и могут быть известны также другим заинтересованным лицам. Для того, чтобы создать неизвестный более никому секретный ключ, оба абонента генерируют большие случайные числа: первый абонент — число a, второй абонент — число b. Затем первый абонент вычисляет значение A = g^amod p и пересылает его второму, а второй вычисляет B = g^bmod p и передаёт первому. Предполагается, что злоумышленник может получить оба этих значения, но не модифицировать их (то есть у него нет возможности вмешаться в процесс передачи). На втором этапе первый абонент на основе имеющегося у него a и полученного по сети B вычисляет значение B^amod p = g^abmod p, а второй абонент на основе имеющегося у него b и полученного по сети A вычисляет значение A^bmod p = g^abmod p. Как нетрудно видеть, у обоих абонентов получилось одно и то же число: K = g^abmod p. Его они и могут использовать в качестве секретного ключа, поскольку здесь злоумышленник встретится с практически неразрешимой (за разумное время) проблемой вычисления g^abmod p по перехваченным g^amod p и g^bmod p, если числа p, a, b выбраны достаточно большими.

Рис. 9 Алгоритм Диффи-Хеллмана Алгоритм Диффи — Хеллмана, где K — итоговый общий секретный ключ При работе алгоритма, каждая сторона:

1. генерирует случайное натуральное число a — закрытый ключ

2. совместно с удалённой стороной устанавливает открытые параметры p и g (обычно значения p и g генерируются на одной стороне и передаются другой), где

· p является случайным простым числом

· g является первообразным корнем по модулю p