4.2.2. Асимметричные криптосистемы (открытого ключа)

Понятие криптосистем открытого ключа было впервые введено Диффи и Хеллманом в 1976 г. Согласно этим схемам, каждый пользователь помещает в открытый каталог процедуру шифрования Е (чтобы другие подписчики использовали ее для кодирования сообщений, адресованных этому пользователю), но держит в секрете детали соответствующей процедуры D дешифровки. [Представляют интерес статьи (Ecker, 1982; Heilman, 1979; Simmons, 1979).] Очевидно, что эти методы основаны на наблюдении, что процедура шифрования и соответствующий ключ не должны быть такими же, как процедура дешифровки и соответствующий ей ключ. Чтобы такая система имела право на существование, должен найтись простой метод, позволяющий получать процедуры Е и D друг из друга. Желательно, чтобы процедуры Е и D обладали следующими свойствами:

1. Если М — открытый текст сообщения, то Е и D должны быть такими, что

т.е. дешифровка зашифрованного текста М дает М.

2. Как Е, так и D могут быть легко вычислены.

3. Знание Е не приводит к легкому способу вычисления D. [Очень неэффективный способ вычисления D состоит в том, чтобы проверять для всех возможных сообщений

3. Для каждого сообщения М должно быть Это полезно для реализации подписей и будет разъяснено ниже.

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

Пользователь В может также «подписать» сообщение, посылаемое пользователю А, так, чтобы А убедился в его подлинности. Чтобы подписать сообщение М, пользователь В сначала вычисляет зависящую от сообщения подпись

затем он находит в каталоге и передает Теперь только А может извлечь S из С, вычислив Да и затем использовав из каталога, чтобы получить сообщение М, т.е.

Поскольку только пользователь В мог создать текст S, который декодируется в М процедурой пользователь А знает, что сообщение М могло быть послано только пользователем В. Криптосистема RSA (названная в честь ее создателей Ривеста, Шамира и Адлемана (Rivest, Shamir, Adleman, 1978), описанная ниже, представляет очень хорошую технику для подписей.

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

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

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

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

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

Первая криптосистема открытого ключа (Merkle, Heilman, 1978) базировалась на -задаче рюкзака пли подмножеств, которая мажет быть сформулирована следующим образом: даны число N и к чисел найти подмножество в сумма которого равна N, если такое подмножество существует.

Пример. Рассмотрим множество из чисел и Какие из этих чисел дают в сумме . В общем, и худшем, случае мы должны сделать 2 проб; в нашем случае методом проб и ошибок мы находим, что

Отметим характеристическое свойство -пробле; именно, в то время как трудно найти числа 2110, 2460 и 3759, как только они найдены, мы можем легко проверить (просто сложив их), что они действительно решают нашу проблему. Более того, проблема рюкзака также -полна. (Очевидно, что при стремлении к к бесконечности в приведенном выше примере невозможно решить проблему рюкзака методом поиска.)

В общем случае, если мы определим скалярное произведение любых двух -мерных векторов как то проблема рюкзака мажет

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

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

Пример. Рассмотрим множество из семи чисел ) Решить эту проблему рюкзака — все равно, что найти решение или уравнения

Это, однако, тривиально, поскольку легко видеть, что (Поскольку сумма всех предшествующих чисел меньше должен равняться 1, в противном случае мы никогда не получим сумму 305.) Проблема принимает вид

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

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

Подведем итоги:

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

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

Неизвестно, насколько надежными являются системы, основанные на проблеме рюкзака. Надежность этих криптосистем базируется на анализе времени вычислений худшего случая проблемы рюкзака. Например, если то понадобится самое большее 21000 проб для решения проблемы. Однако может также случиться, что решение будет найдено после всего нескольких проб, в случае чего система не будет так надежна, как мы думаем. Первоначально считалось, что повторная шифровка увеличивает надежность рюкзака с ловушкой. Однако в настоящее время известны атаки на простые и дважды итерированные рюкзаки. (Чтобы получить дважды итерированный рюкзак, выбираем другую пару чисел и получаем из новый вектор; процесс мажет быть повторен сколько угодно раз.) Представляет интерес статья Меркля и Хеллмана (Merkle, Heilman, 1981).

Операции этого типа для криптосистем разъяснены ниже. Однако следует помнить, что выбранные значения слишком малы, чтобы обеспечить какую-либо надежность, т.е. они слишком малы, чтобы убедить, что вычислительная часть недоступна для несанкционированного перехватчика.

Пример. Выберем следующее соответствие между буквами алфавита и двоичными -наборами:

где обозначает пробел. Мы выберем также секретную информацию в случае чего тогда открытый ключ — это , где . Теперь сообщение «computer algebra», представляемое двоичной последовательностью передается как последовательность чисел 97, 198, 101, 283, 104, 237, 49, 140, 0, 234, 146, 49, 85, 140, 0, где и т. д. Отметим, что в общем случае каждое передаваемое число равно т.е. первоначальное сообщение в двоичном виде разбивается на группы из к битов. Несанкционированный перехватчик знает - и открытый ключ , но для больших к он должен перепробовать огромное число случаев, чтобы расшифровать сообщение (2 в худшем случае).

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

и решить легкую задачу рюкзака Это так, потому что если выбрать

Так, продолжая наш пример, мы сначала заметим, что в нашем случае и получатель вычисляет 15 величин которые равны 28, 48, 20, 100, 14, 81, 13, 53, 0, 87, 41, 13, 52, 53, 0. Затем он без труда решает соответствующие проблемы рюкзака с вектором и получает переданное сообщение; например, 28 соответствует двоичному соответствует соответствует и т.д.

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

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

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

Для лучшего понимания RSA-криптосистем читателю следует еще раз просмотреть разд. 2.3; в частности, полезными являются определение функции в разд. 2.3.1 и теорема Эйлера 2.3.14, утверждающая, что если . Кроме того, в разд. 2.3.1 мы видели, что Для любого целого где — простые числа, входящие в разложение числа в произведение степеней простых чисел. Для нас представляет интерес частный случай где и q — два различных простых числа. Из последней формулы мы получаем . Покажем, как работает RSA-криптосистема. Получатель вычисляет следующие величины:

Выбраны два больших простых числа, которые держатся в секрете.

Произведение которое помещается в открытый каталог.

Е: Случайное целое число, также размещаемое в открытом каталоге. [Е используется для кодирования сообщений, посылаемых получателю, который должен убедиться, что Е взаимно просто с числом . Это сделать легко, поскольку получатель знает числа вычисляется

Целое число, используемое получателем для декодирования. D — мультипликативное обратное числа Е по модулю также держится в секрете, т. е. Обратное существует, поскольку . Снова эти вычисления быстрые, поскольку получатель знает

Причины, накладывающие технические ограничения на различные целые числа, будут разъяснены ниже.

Подведем итоги.

Получатель знает и D, образующие секретный ключ, отправитель знает сообщение М, казадый знает открытый ключ .

Сообщение М, передаваемое получателю, прежде всего преобразуется в цифровую форму некоторой стандартной несекретной процедурой. В частности, можно использовать присвоения ; т.е. каждая буква заменяется двузначным числом. Например, сообщение «computer algebra» должно быть переписано в виде Конечно, если сообщение длинное, то оно разбивается на блоки; длина каждого блока такова, что его численное значение не превосходит п. Важно, чтобы каждый блок сообщения находился в области поскольку в противном случае невозможно отличить его от любого большего целого числа, сравнимого с ним по модулю п. Практически модуль выбирается большим, порядка 200 цифр, так что могут использоваться блоки размером до

Отправитель берет каждый блок сообщения смотрит на открытые ключи передает , где

Получатель получает - и вычисляет . Заметим, однако, что по определению мы имеем откуда следует, что для некоторого целого к. Таким образом,

где последнее равенство получено из теоремы Эйлера 2.3.14. Таким образом, получатель определил блок первоначального сообщения

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

Пример. Как упоминалось выше, используя присвоения сообщение «computer algebra» мы переписываем в виде Выбирая мы имеем более того, мы выбираем и в этом случае Теперь каждый блок сообщения состоит из двузначного числа, и зашифрованное сообщение получается по формуле . А именно, мы получаем последовательность чисел которая и передается. Для того чтобы восстановить блок переданного сообщения (который в нашем случае представляет просто букву), получатель должен возвести каждое двузначное число в куб (modulo 33); это мы оставляем читателю в качестве упражнения. (В разд. 2.3.2 мы рассматривали эффективные алгоритмы для возведения целых чисел в степень, а также как для вычисления мультипликативного обратного целого числа по моду другого целого числа; читателю следует еще раз просмотреть эти алгоритмы.)

Несанкционированный перехватчик сообщения в рассмотренном примере должен вычислить D, мультипликативное обратное числа Е по модулю Однако, чтобы сделать это, перехватчик должен найти по находящемуся в открытом каталоге. Таким образом ему требуется алгоритм с полиномиальным временем для разложения больших целых чисел. Отметим, что выбираются так, чтобы у них было одинаковое количество цифр, поэтому цифр вдвое больше. Более того, они должны быть выбраны так, чтобы был достаточно большой сомножитель, обозначим его также должен быть достаточно большой сомножитель. Аналогичные ограничения накладываются на q. Это гарантирует, что открытый текст не может быть найден с помощью итераций шифрования быстрее, чем случайным поиском; см. (Blakley et al., 1979; Herlestam, 1978; Williams et al., 1979). (Дешифрование итерациями — это процесс, когда шифрованный текст С последовательно шифруется снова, до тех пор, пока не получим вновь С, т.е. полагаем и вычисляем , пока не получим . Тогда

Другой способ, которым перехватчик может пытаться решить проблему, состоит в нахождении поскольку в этом случае D может быть легко вычислено из соотношения Однако следующие соображения показывают, что этот подход не проще, чем попытки разложить я; если известно то

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

Таким образом, любая попытка найти эквивалентна решению сложной проблемы разложения на множители.

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

Существует также криптосистема с открытым ключом, основанная на сложности общей проблемы декодирования для линейных кодов, исправляющих ошибки; более подробно см. (Lempel, 1979, pp. 297-298). Более того, существуют распределенные системы с открытым ключом. Назначение такой системы состоит в том, чтобы позволить каждой паре пользователей надежно обменяться собственным ключом на ненадежном канале для использования в стандартной криптосистеме; см. (Merkle, 1978; Pohlig et al., 1978).