Алгоритмы криптографии

Наука о шифрах получила название криптология, слово образова¬но из двух греческих: "criptos" - тайный и "logos" - сообщение (слово). С самого начала криптология включала две взаимодополняющие ветви: крип¬тографию, в которой изучались методы шифрования сообщений, и криптоана¬лиз, где разрабатывались методы раскрытия шифров.

Возникновение шифров относится к глубокой древности, когда воз¬никла потребность в обеспечении секретности некоторых ценных сведений или важных сообщений. Один из самых древних зашифрованных текстов был найден при раскопках в Месопотамии. Глиняная табличка, относящаяся к 20 веку до н. э., содержала рецепт глазури для покрытия гончарных изделий. Долгое время она была уделом талантливых одиночек и считалась искусством на грани черной магии.
До середины 20 века криптология выступала скорее как искусное ремес¬ло, а не наука, как удел узкого круга избранных лиц. Однако большое количе¬ство эмпирического материала в области разработки, применения и раскрытия шифров, накопленного к этому времени, особенно в ходе мировых войн, соз¬дали предпосылки для научного обобщения криптологических знаний. Ос¬новополагающей работой криптологии считается работа американского учено¬го Клода Шеннона "Теория связи в секретных системах", опубликованная в 1949 году .
Все древние шифры были ручными, а значит весьма трудоемкими при шифровании длинных текстов. В 19-м веке появились сначала механические, а в 20-м - электромеханические и электронные устройства шифрова¬ния/дешифрования, а затем и компьютерные реализации таких алгоритмов. С широким распространением ЭВМ в начале 70-х годов появилась новая разновидность шифров - блочные, ориентированные на операции с машинны¬ми словами. До этого все шифры предполагали последовательную позначную обработку информации (их стали называть поточными шифрами).
Шифр - это множество обратимых преобразований формы сообщения с целью его защиты от несанкционированного прочтения. Исходное сообще¬ние, которое подвергается шифрованию, называется открытым текстом, а ре¬зультат, полученный применением преобразования шифра к исходному сооб¬щению, называется шифртекстом или криптограммой. Переход от открытого текста к шифртексту называется зашифрованием, а обратный переход - рас¬шифрованием.
Принцип построения преобразования шифра (или просто шифра) все¬гда предполагает множество вариантов его реализации, а для конкретных случаев использования шифра выбирается вполне определенный вариант. Совокупность данных, определяющих конкретное преобразование шифра из множества возможных, называется ключом.
Стойкость шифра - это способность противостоять попыткам посто¬роннего лица восстановить (дешифровать) открытый текст по перехваченно¬му шифртексту. В этих попытках криптоаналитик сначала пытается предуга¬дать принцип построения шифра, а затем определить ключ. Сравнительная стойкость шифров оценивается ориентировочно по времени, необходимому противнику, вооруженному современными средствами вычислительной техники, чтобы каким-либо способом (например, полным перебором вариан¬тов), дешифровать сообщение. Чем больше вариантов ключей возможно, тем более трудным для дешифрования является шифр.
Однако получателю зашифрованного сообщения ключ должен быть из¬вестен, чтобы он имел возможность восстановить открытый текст. Очевидно, для нормального функционирования такой системы ключ должен храниться в секрете, поэтому она получила название криптосистемы (или шифроси-стемы) с секретным ключом. Иными словами: К.Шеннон рассматривает шиф¬рование как отображение исходного сообщения в зашифрованное
С= FjM,
где С - криптограмма, F; - отображение, М - исходное состояние. Индекс i соответствует конкретному используемому ключу. Для того, чтобы была воз¬можность однозначного дешифрования сообщения отображение Ft должно иметь обратное отображение. Тогда
M=Ft-1C

Источник сообщений порождает открытый текст Х. Источник ключей определяет ключ шифра Z, и шифратор источника с его помощью преобразует открытый текст Х в шифртекст Y, который передается по открытому каналу. Шифратор приемника делает обратное преобразование, получая с помощью ключа Z открытый текст Х из шифртекста Y. Важнейшей частью модели криптографической системы с секретным ключом является "защищенный" ка¬нал, по которому передается ключ. Это канал повышенной надежности и секретности, за которым может стоять некоторое устройство или даже спе¬циальный курьер. Строго говоря, защищенными должны быть все элементы системы, в которых используется секретный ключ.
Прежде чем переходить к рассмотрению современного состояния криптологии, заглянем немного в историю ее раннего развития.

Шифры подстановки (замены)
Самыми древними шифрами являются шифры подстановки (или шифры замены), когда буквы сообщения по какому-либо правилу заменяются другимии символами. Например, следующее сообщение получено шифром замены (только букв)

Сказать о нем что-то определенно трудно, так как мало информации. Но ключ здесь очень простой, достаточно увидеть открытый текст. П о с ы л а ю _ к г _ в з р ы в ч а т к и.
Если кто не догадался, то каждая буква здесь была заменена на ее предшественницу в алфавите ("о" вместо "п", "н" вместо "o", "p" вместо "с", "к" вместо "л", "я" вместо "а" и т.п.).
Подобные шифры широко использовались в древности, достоверно из¬вестно, что Ю.Цезарь применял шифр замены со сдвигом на три буквы впе¬ред при шифровании. Метод дешифрования шифра подстановки описан у Ко¬нан-Дойля в рассказе "Пляшущие человечки": достаточно сначала догадаться хотя бы об одном слове - появляются несколько известных букв, подставляя их в зашифрованный текст, можно угадать другие слова и узнать новые буквы и т.д.
Более формальный подход к дешифрованию основан на исполь¬зовании средней частоты появления букв в текстах. Впервые похожий метод был предложен в конце 15-го века (итальянский математик Леон Баттиста Альберти) и использовал свойство неравномерности встречаемости разных букв алфавита.
Теперь, имея шифртексты, можно было провести в них частотный ана¬лиз использования символов и на его основе получить (при неограниченном количестве шифрсообщений) точные значения всех букв. Но так как мате¬риала, как правило, не очень много, то частотный анализ дает приблизи¬тельные результаты, поэтому можно лишь с высокой долей вероятности пред¬положить буквенное значение самых частоупотребимых символов, а далее -необходимо подставлять их в шифртексты и пытаться угадывать слова, одна¬ко результаты появляются достаточно быстро. Увлекательно на эту тему пове¬ствовал Эдгар По в своем «Золотом жуке».
На слабость шифров однозначной замены обратили внимание еще в 15-м веке. Случайные догадки - кто и кому пишет, названия городов и селений, часто употребляемые слова, вроде предлогов, - могли привести к почти мгно¬венному раскрытию шифра. Попытки модификации основывались на много¬значной замене букв открытого текста с использованием ключевой после¬довательности (ключевого слова или ключа).
В наиболее чистом виде этот подход можно изложить так. Пусть мы хотим получить 10 вариантов (0, 1, 9) замены каждой буквы исходного тек¬ста (в таблице 1.2 вариант замены определяет величину сдвига по алфавиту).
Придумаем ключевую последовательность из цифр 0...9 произвольной длины (например, 190 277 321 856 403). Для открытого текста надпишем над буквами цифры ключа (периодически) и выполним зашифрование, вы¬бирая вариант замены по цифре ключа.
Идея фактически была предложена в 16-м веке французским дипло¬матом Блезом де Вижинером. Вместо цифр им использовались буквы, и ключевая последовательность представляла собой слово.
Легко видеть, что алгоритм многозначной замены определяет сово¬купность преобразований шифра, отличающихся параметром - ключевой последовательностью шифрования (ключом). Это позволяет строить надеж¬ную криптосистему на основании фиксированного (несекретного) алго¬ритма шифрования, но секретного ключа, который регулярно меняется. Теоре¬тически такой шифр поддается дешифрованию на основе частотного анализа употребления букв, но для этого требуется, чтобы длина шифросообщений, сделанных с этим ключом, значительно превышала длину самого ключа.
На основе алгоритма многозначной замены были разработаны и на¬шли широкое применение (особенно во время второй мировой войны) диско¬вые шифровальные машины. Сконструированные на принципах, используе¬мых в арифмометрах, шифрмашины содержали 6-10 дисков на общей оси, которые могли дискретно поворачиваться один относительно другого, создавая на каждом такте уникальное сочетание из всех возможных сочета¬ний угловых положений.
Принцип работы дисков был одновременно открыт четырьмя изобрета¬телями из разных стран (американец - 1918 г., голландец - 1919 г., швед -1919г., немец Артур Шербиус - 1927 г.). Именно он сконструировал энигму (в переводе с немецкого - «загадка»).
В диски из электроизоляционного материала были впрессованы ла¬тунные контактные площадки (соответствующие отдельным буквам) с каждой стороны, которые попарно соединялись внутри диска. Таких дисков (разных) в комплект шифрмашины входило больше, чем использовалось в работе. Кроме изменения набора рабочих дисков, они могли нанизываться на ось в произвольном порядке, начальный угол установки каждого диска также можно было менять.
При шифровании на контакты одного из крайних дисков подается на¬пряжение, которое последовательно передается на связанный контакт по¬следнего диска, чем осуществляется замена буквы исходного текста на другую букву. Затем выполняется дискретный угловой поворот первого диска, и возможно, связанных с ним других дисков, устанавливая следующие сочета¬ния замены. Для дешифровки сообщения на шифрмашине достаточно было поменять местами вход и выход.
Такие шифрмашины использовались в войсковых соединениях и по¬сольствах для взаимного обмена секретными сообщениями. Для работы ут¬верждался секретный график их модификации, например:
- еженедельно устанавливается новый набор рабочих дисков;
- ежедневно устанавливается новый порядок дисков на оси;
- для каждого нового сообщения некоторому получателю в течении дня устанавливается новое начальное угловое положение дисков.
Этим фактически неявно определялось множество ключей, используе¬мых в алгоритме шифрования.
Оригинальный вариант алгоритма многозначной замены был пред¬ложен в 1917 году американским инженером Г.С.Вернамом. Он предназна¬чался для шифрования текстов, представленных в двоичном (телеграфном) коде (код Бодо). Главным элементом был секретный (двоичный) ключ, циф¬ры которого как бы надписывались над исходным кодом, а шифрсообщение (также в двоичном коде) формировалось применением операции «исклю¬чающее ИЛИ» (сложение по модулю два) к двоичным цифрам исходного текста и ключа. Как было установлено значительно позднее (доказал К.Шеннон), стойкость шифра Г.С. Вернама очень высока, если длина ключа не меньше длины сообщения (практически нераскрываемый шифр). Казалось бы про¬блема решена, но здесь имеются трудности с ключами (их качество, хране¬ние, уничтожение, транспортировка). На каждом этапе существует угроза их безопасности. Поэтому этот метод используют в исключительных случаях.
Шифры перестановки
Другой разновидностью используемых с давних времен шифров яв¬ляются так называемые шифры перестановки. Суть их в том, что буквы ис¬ходного сообщения остаются прежними, но их порядок меняется по какому-либо «хитрому» закону.
Простейший вариант перестановки - прямоугольная таблица с сек¬ретным размером столбца (показана на рисунке 1.2), куда исходный текст записывается по столбцам, а шифрсообщение считывается по строкам.

Использовались и более сложные (ручные) системы, также группо¬вые. Например, в квадрате (рис.1.4), состоящем из 4 малых квадратов с опре¬деленной нумерацией клеток, вырезают 4 клетки под разными номерами. Квадрат кладется в начальное положение («1» - вверху) и в отверстия (слева направо/сверху вниз) вписываются буквы открытого сообщения. Затем квад¬рат поворачивается против часовой стрелки на 90 градусов («2» - вверху) и также вписываются следующие буквы, потом повторяем процесс для положе¬ния «3» и «4». Если остаются свободные клетки - они заполняются произ¬вольными символами. Шифрсообщение получают, считав по столбцам или по строкам последовательность записанных в прямоугольнике букв.
Фактически, рассмотренные выше и другие шифры перестановки с со¬временной точки зрения абсолютно единообразны, так как представляют собой последовательность элементарных процедур перестановки группы символов вида
Дешифровка сообщений, полученных шифром перестановки, значи¬тельно труднее, чем при использовании шифров замены. Какой-либо теорети¬ческой предпосылки, кроме перебора вариантов, не существует, хотя отдельные догадки могут упростить задачу.

Современные блочные шифры.
Современные криптосистемы ориентированы на программно-аппаратные методы реализации. Блочные криптосистемы представляют собой блочные (групповые) шифрпреобразования. Блочная криптосистема разбивает открытый текст М на последовательные блоки M1, M2,... и зашифровывает каж¬дый блок с помощью одного и того же обратимого преобразования Ек, выпол¬ненного с помощью ключа К. Ек(М)=Ек(М1), Ek(M2),.... Любое из них можно рассматривать как последовательность операций, проводимых с элементами ключа и открытого текста, а так же производными от них величинами. Произ¬вол в выборе элементов алгоритма шифрования достаточно велик, однако " элементарные" операции должны обладать хорошим криптографическими свойствами и допускать удобную техническую или программную реали¬зацию /1-6/. Обычно используются операции:
Практическая стойкость алгоритмов шифрования зависит и от особен¬ностей соединения операций в последовательности. Примерами блочных сис¬тем являются алгоритмы блочного шифрования, принятые в качестве стандар¬тов шифрования данных в США и России - DES-алгоритм и ГОСТ-28147-89 соответственно.
В 1973 году Национальное Бюро Стандартов США начало работы по созданию стандарта шифрования данных на ЭВМ. Был объявлен конкурс, кото¬рый выиграла фирма IBM, представившая алгоритм шифрования, сейчас
известный как DES-алгоритм (Data Encryption Standard) [1].
Рассмотрим работу DES-алгоритма в простейшем (базовом) режиме ЕСВ - электронной кодовой книги. Алгоритм работы показан на рисунке 1.5.
Входные 64-битовые векторы, называемые блоками открытого текста, преобразуются в выходные 64-битовые векторы, называемые блоками шиф-ртекста, с помощью 56-битового ключа К (число различных ключей равно 256=7.106)
Алгоритм реализуется в 16 аналогичных циклах шифрования, где в i-ом цикле используется цикловой ключ Ki, предоставляющий собой выборку 48 битов из 56 битов ключа К. Реализация алгоритма функции f показана на ри¬сунке 1.6. Здесь операция Е - расширение 32-битового вектора до 48-битового, операция SJ(S-боксы) - замена 6-битовых векторов на 4 - битовые.
Основным недостатком алгоритма считается 56-битовый ключ, слиш¬ком короткий для противостояния полному перебору ключей на специализиро¬ванном компьютере. Недавние результаты показали, что современное устройст¬во стоимостью 1 млн. долл. способно вскрыть секретный ключ с помощью пол¬ного перебора в среднем за 3.5 часа. Поэтому было принято решение использо¬вать DES-алгоритм для закрытия коммерческой (несекретной) информации. В этих случаях практическая реализация перебора всех ключей экономически нецелесообразна, так как затраты не соответствуют ценности зашифрованной информации.
В ходе открытого обсуждения алгоритма в прессе, рассматривались пу¬ти усиления его криптографических свойств. Наиболее простой вариант пред¬полагал использовать независимые 48-битовые векторы в качестве цифровых ключей, что позволит увеличить общее число ключей до 2768.
Режим электронной кодовой книги (ЕСВ) используется в основном для шифрования коротких сообщений служебного содержания - паролей, ключей и т.п. Наиболее общий режим - режим сцепления блоков (СВС), (Cifer Block Chaining) схема которого показана на рисунке 1.7. Здесь каждый входной блок зависит от всех предыдущих. Начальный вектор bo (случайный начальный век¬тор) вырабатывается для каждого сообщения и может передаваться в линию связи, как в открытом, так и в шифрованном виде, что препятствует атакам на шифротекст, основанным на наличии стандартов в начале сообщения (вспомни¬те "Семнадцать мгновений весны": Центр - Юстасу... ).
??? как дешифровать ???
DES алгоритм является первым примером широкого производства и внедрения технических средств в область защиты информации. К настоящему времени выпускается несколько десятков устройств аппаратно - программной реализации DES-алгоритма. Для выпуска такого рода устройства необходимо получить сертификат Национального Бюро Стандартов на право реализации продукта, который выдается только после всесторонней проверки по специаль¬ным тестирующим процедурам.
Достигнута высокая скорость шифрования. По некоторым сообщениям, в одном из устройств на основе специализированной микросхемы она составля¬ет около 45 Мбит/сек.
Основные области применения DES-алгоритма:
- хранение данных в ЭВМ (шифрование файлов, паролей);
- электронная система платежей (между клиентом и банком);
- электронный обмен коммерческой информацией (между покупателем и продавцом).

В 1989 году был разработан блочный шифр для использования в каче¬стве государственного стандарта шифрования (зарегистрирован как ГОСТ 28147-89)/7/. В основном алгоритм применяется в банковской системе, судя по публикациям - несколько медлителен, но обладает весьма высокой стойкостью.
Его общая схема близка к схеме DES-алгоритма, лишь отсутствует на¬чальная перестановка и число циклов шифрования равно 32 (вместо 16 в DES-алгоритме). Ключом считается набор из 8 элементарных 32-битовых ключей X1, Х2,...,Х8(общее число ключей 2256). В циклах шифрования трижды используется прямая последовательность элементарных ключей и один раз - обратная: X8, X7,...,X1.
Основное отличие - в реализации функции f стандарта шифрования (приведена на рисунке 1.8). Элементы S1, S2, ... , S8 - представляют собой табли¬цы замены 4-битовых векторов и могут рассматриваться как долговременные ключи
ГОСТ 28147-89, как DES-алгоритм, предусматривает различные режи¬мы использования и только базовый (режим простой замены) совпадает, по су¬ти, с базовым режимом DES-алгоритма, остальные - в той или иной мере отли¬чаются.
Известна специальная реализация алгоритма шифрования ГОСТ 28147¬89 аппаратная плата шифрования данных «Криптон-3» для IBM PC, ее произво¬дительность - 50 Кбит/сек.
Здесь уделяется внимание получению из ключа программно длинных случайных или псевдослучайных рядов чисел, называемых на жаргоне отечест¬венных криптографов гаммой, по названию^ - буквы греческого алфавита, которой в математических записях обозначаются случайные величины.
Эти программы, хотя они и называются генераторами случайных чисел, на самом деле выдают детерминированные числовые ряды, которые только ка¬жутся случайными по своим свойствам. От них требуется, чтобы, даже зная закон формирования, но не зная ключа в виде начальных условий, никто не смог бы отличить числовой ряд от случайного.
Можно сформулировать 3 основных требования к криптографически стойкому генератору псевдослучайной последовательности или гаммы:
1. Период гаммы должен быть достаточно большим для шифрования сообщений различной длины.
2. Гамма должна быть труднопредсказуемой. Это значит, что если из¬вестны тип генератора и кусок гаммы, то невозможно предсказать следующий за этим куском бит гаммы с вероятностью выше заданной.
3. Генерирование гаммы не должно быть связано с большими техниче¬скими и организационными трудностями.
Режим гаммирования ГОСТ 28147-89
Схема реализации режима гаммирования приведена на рисунке 1.9.
Открытые данные, разбитые на 64-разрядные блоки T0(i) зашифровыва¬ются в режиме гаммирования путем поразрядного суммирования по модулю 2 в сумматоре СМ5 с гаммой шифра Гд^-1, которая вырабатывается блоками по 64 бита. Число двоичных разрядов в блоке Т0(М), где М определяется объемом шифруемых данных может быть меньше 64, при этом неиспользованная для зашифрования часть гаммы шифра из блока Гш(М) отбрасывается.
В КЗУ вводятся 256 бит ключа. В накопители N1, N2 вводится 64-разрядная двоичная последовательность (синхропосылка) S=(S1,S2,...,S64), яв¬ляющаяся исходным заполнением этих накопителей для последующей выра¬ботки М блоков гаммы шифра. Синхропосылка вводится в N1 и N2 так, что значение S1 вводится в 1-ый разряд N1, значение S33 - в 1-ый разряд N2, S64 - в 32-й разряд N2.
Исходное заполнение накопителей N1 и N2 (синхропосылка S) зашифро¬вывается в режиме простой замены (нижняя часть рисунка). Результат зашиф¬рования A(S)=(Y0,Z0) переписывается в 32-разрядные накопители N3 и N4 так, что заполнение N1 переписывается в N3, а N2 - в N4.
Заполнение накопителя N4 суммируется по модулю (232-1) в сумматоре СМ4 с 32-разрядной константой С1 из накопителя N6, результат записывается в
N4.
Заполнение накопителя N3 суммируется по модулю 232 в сумматоре СМ3 с 32- разрядной константой С2 из накопителя N5, результат записывается в N3.
Заполнение N3 переписывается в N1, а заполнение N4 - в N2. При этом заполнение N3, N4 сохраняется.
Заполнение N1 и N2 зашифровывается в режиме простой замены. Полу¬ченное в результате в N1, N2 зашифрование образует первый 64-рарядный блок гаммы шифра Гш(1), который суммируется в СМ5 с первым 64- разрядным бло¬ком открытых данных Т0(1).
В результате получается 64 - разрядный блок зашифрования данных Гш(1).
Для получения следующего 64-разрядного блока гаммы шифра Гш(2) заполнение N4 суммируется по модулю (232-1) в СМ4. С константой С1 из N6, заполнение N3 суммируется по модулю 232 в сумматоре СМ3 с С2 (в N5). Новое заполнение N3 переписывается в N1, а новое заполнение N4 переписывается в N2., при этом заполнение N3, N4 сохраняется.
Заполнение N1 и N2 зашифровывается в режиме простой замены. Полу¬ченное в результате зашифрования заполнение N1, N2 образует второй 64-разрядный блок гаммы шифра Гш(2), который поразрядно суммируется по моду¬лю 2 в СМ5 со вторым блоком открытых данных Т0(2).
Аналогично вырабатываются блоки гаммы шифра Гш(3), ... , Гш(М) и за¬шифровываются блоки открытых данных Т0(3), Т0(М).
В канал связи (или память ЭВМ) передается синхропосылка S и блоки зашифрованных данных Тш(1), Тш(2), ... , Тш(М).

Одной из основных характеристик ключа является его размер, опреде¬ляющий число всевозможных ключевых установок шифра. Если размер ключа чрезмерно велик, то это приводит к удорожанию изготовления ключей, услож¬нению процедуры установки ключа, понижению надежности работы шифрую¬щего устройства.
Важнейшей частью практической работы с ключами является обеспе¬чение секретности ключа. К основным мерам по защите ключей относятся сле¬дующие:
- ограничение круга лиц, допущенных к работе с ключами;
- регламентация рассылки, хранения и уничтожения ключей;
- регламентация порядка смены ключей;
- применение технических мер защиты ключевой информации от несан¬кционированного доступа.
Рассмотрим один из принципов распределения ключей (на основе од¬носторонней функции), проработка которого имела весьма неожиданные последствия - была изобретена система шифрования с открытым ключом. Сначала небольшое отступление.
Понятие односторонней функции было введено в теоретическом иссле¬довании о защите входа в вычислительные системы . Функция f(x) называется односторонней (one-way function), если для всех x из ее области определения легко вычислить y=f(x), но нахождение по заданному y0 такого x0, для которого f(x0)=y0, вычислительно неосуществимо, то есть требуется настолько огромный объем вычислений, что за них просто и не стоит браться.
Однако существование односторонних функций не доказано. В качест¬ве приближения была предложена Гиллом Дж. целочисленная показательная функция f(x)=ax(mod n), где основание a и показатель степени x принадлежат интервалу (1,n-1), а умножение ведется по модулю n (3*4 mod 10=2; 7*8mod 9=2). Функция вычисляется достаточно эффективно по схеме Горнера. Если представление числа x в двоичной форме имеет вид xk-12k-1 + xk-22k-2 + ...+ x121 + x020,
то
y = f(x) = ax mod n = ((...(axk-1 )2*axk-2)2*...*ax1 )2*ax0 mod n.
Операция, обратная к этой, известна как операция вычисления дискрет¬ного логарифма: по заданным y, a и n найти такое целое x, что a>c( mod n) = y. До настоящего времени не найдено достаточно эффективных алгоритмов реше¬ния этой задачи.
Американские криптологи Диффи и Хеллман (Diffi W., Hellman M.E. New direction in criptography. IEEE Trans. Inf. Theory, v. IT-22, 1976) предложили схему распространения (рассылки) ключей для секретной связи на основе одно¬сторонней показательной функции. Ее суть состоит в следующем.
В протоколе обмена секретными ключами предполагается, что все пользователи знают некоторые числа n и a (1< a < n). Для выработки общего секретного ключа пользователи A и B должны проделать следующую процеду¬ру:
1. Определить секретные ключи пользователей КА и КВ.
Для этого каждый пользователь независимо выбирает случайные числа из интервала (1,..., n-1).
2. Вычислить открытые ключи пользователей YA и YB.
Для этого каждый использует одностороннюю показательную функцию Y=ak mod n со своим секретным ключом.
3. Обменяться ключами YA и YB по открытому каналу связи.
4. Независимо определить общий секретный ключ К.
Для этого пользователи выполняют вычисления с помощью той же од¬носторонней функции
A: YBKA(mod n) = taKB ]KA mod n = aKA*KB mod n = K.
B: YAKB(mod n) = taKA ]KB mod n = aKB*KA mod n = K.
Здесь каждый имеет показатель степени, а основание получает от парт¬нера
Безопасность (секретность) изложенной схемы зависит от сложности вычисления секретных ключей пользователей (КА и КВ). Пока не найдено удов¬летворительных быстрых алгоритмов нахождения К из а, YA и YB без явного определения КА или КВ.
1.5. Криптосистемы с открытым ключом
Дальнейшим развитием идеи односторонней функции стало введение односторонней функции с секретом, а затем и системы шифрования с открытым ключом.
Под односторонней функцией с секретом (с лазейкой, с потайной две¬рью - a trap-door one-way) называется зависящая от параметра к фукция y=fk(x), такая, что знание k дает возможность легко построить обратное преобразование x=f-1(y), тогда как без знания k определение х по известному y вычислительно не осуществимо.
В принципе, основой таких функций является некоторая базовая функ¬ция, имеющая параметр n, который может принимать множество значений из широкого диапазона. Известен некоторый способ определения обратной базо¬вой функции, основанный на определенном сочетании свойств параметра n. Важно, чтобы определение сочетания свойств параметра n по его значению бы¬ло вычислительно неосуществимо. Тогда, задав сочетание, определяем n, пря¬мую и обратную базовые функции, причем последнюю держим в секрете. Зна¬чит, n выступает как открытый ключ, а обратное преобразование - как секрет¬ный ключ.
Один из первых предложенных примеров таких функций основан на степенной функции f(x)=xm (mod n), вычисление которой по известным n и m производится достаточно эффективно. Преобразование, обратное к возведению в степень xm (mod n) называется вычислением корня m-й степени по модулю n. Например, 54 mod 21 = 16, поэтому 5 является корнем 4-й степени из 16 по мо¬дулю 21; 45 mod 25 = 24, 4 - есть корень 5-й степени из 24 по mod 25. В на¬стоящее время эффективный алгоритм этой операции известен, но требует зна¬ния специального разложения n по степеням простых чисел. Эта информация и является секретным ключом. Определить такое разложение по значению n дос¬таточно сложно, но задав такое разложение мы однозначно определяем n.
Таким образом, криптосистема с открытым ключом включает откры¬тый алгоритм Ek шифрования и секретный алгоритм дешифрования Dk, обрат¬ный к Ek, но определение которого по Ek вычислительно не осуществимо.
Иногда принято секретное преобразование Dk называть секретным клю-чем (private key), а открытое преобразование Ek - открытым ключем (public key), поэтому сами системы называют также двухключевыми криптосистемами (two key cryptosystem). Другое название таких криптосистем - асимметричные крип¬тосистемы (asymmetric cryptosystem), в то время как обычные криптосистемы с секретным ключом называются симметричными (symmetric criptosystem).
Так как в силу открытости любой злоумышленник имеет доступ к пре¬образованию зашифрования Ek, то он может всегда выбрать любой открытый текст и получить соответствующий ему шифртекст. Поэтому криптосистемы с открытым ключом должны быть устойчивы к методам дешифрования по вы¬бранным открытому и шифрованному тексту.
Криптосистема RSA
Название криптосистемы образовано из первых букв фамилий предло¬живших ее авторов (Rivest R., Shamir A., Adleman L. A method for obtaining digital signatures and pablic-key cryptosystems. Commun. ACM, v.21, N2, 1978).
Система относится к блочным экспоненциальным системам, так как каждый блок М открытого текста рассматривается как целое число в интервале (0,..., n-1) и преобразуется в блок С следующим открытым преобразованием
C = E (e,n) (M) = Me (mod n),
где E(e,n) - преобразование, а (e,n) - ключ зашифрования. При расшифровании блок открытого текста М восстанавливается таким же преобразованием, но с другим показателем степени. M = D (d,n) (C) = Cd (mod n),
где D(d,n) - преобразование, а (d,n) - ключ расшифрования.
В основе этого метода лежит довольно сложное теоретическое обосно¬вание. Числа e и d связаны с n определенной зависимостью и существуют реко¬мендации по выбору ключевых элементов на основе простых чисел. Если взять два простых числа p и g, определить n = p х q, то можно определить пару чисел e и d, удовлетворяющих заданным условиям. Если сделать открытыми числа e и n, а ключ d (и обязательно p и g) держать в секрете - то предложенная система является RSA-криптосистемой открытого шифрования. Очевидно, ее стойкость определяется сложностью операции извлечения из С корня степени е по моду¬лю n.
Рассмотрим основные этапы реализации алгоритма RSA.
1. Отправитель вычисляет n = p х q и M=(p-1)(q-1).
2. Затем он выбирает случайное целое число e, взаимно простое с М и вычисляет d, удовлетворяющее условию
ed = 1 (mod M).
Напомним, что два числа являются взаимно простыми, если их HOD = 1. Числа а и b имеют HOD d, если d делит и а и b и максимальный среди таких чисел.
3. После этого он публикует е и n как свой открытый ключ шифрова¬ния, сохраняя d, как закрытый (секретный) ключ.
4. Рассмотрим теперь числа e и d. Предположим, что мы знаем одно из них и знаем соотношение, которым они связаны. Мы могли бы легко вычислить второе число, однако мы не знаем чисел p и q. Следовательно можно одно из чисел подарить кому-нибудь вместе с n и попросить его посылать нам сообще¬ния следующим образом.
5. Сообщение представить как векторы (блоки) длины l
6. Каждое xi возвести в степень e по mod n.
7. Прислать нам Y=(x1e (mod n), x2e (mod n),...,xle (mod n)).
Обозначим t=yi =х^ (mod n) и рассмотрим расшифрование полученной
информации.
Для этого возведем полученное число t в степень второго числа пары -
d:
R=td(mod n) = xe (mod n)d(mod n) = xed (mod n).
В соответствие с п.2 соотношение ed=1(mod M). а это означает, что ed-1 делится нацело на (p-1)(q-1), т.е. ed=1+a(p-1)(q-1), где а - целое число. Утверждается, что х^пк^ n) =x. Действительно, xed(mod n) = x1+a(p-1)(q-1) (mod n) Учитывая,что
xp-1 = 1 mod p, xq-1 = 1 mod q (эти соотношения доказываются как малая теорема Ферма, например в /10/) получим x(p-1)(q-1) = 1(mod pq) x1+a(p-1) (g-1)(mod n) = x, т.к.
xa(p-1) (q-1) = 1(mod pq), из-за того,
что x(p-1) (q-1) = 1(mod pq), x mod n = x, так как x < M. Что и требовалось доказать.
Цифровая (электронная) подпись
Одним из основных применений криптосистем с открытым ключом яв¬ляется их использование при создании так называемой цифровой или электрон¬ной подписи (digital signature). Впервые идея цифровой подписи была высказана в работе Диффи и Хеллмана.
Один из вариантов изложения принципа электронной подписи выгля¬дит так. Требуется, чтобы существовали взаимообратные преобразования Ek и Dk, для которых выполняется
Ek[Dk(M)] =M для любого открытого текста М.
Тогда Dk считается секретным преобразованием, с помощью которого пользователь может зашифровать исходный текст C=Dk(M) и послать это зна¬чение в качестве цифровой подписи к сообщению М другим пользователям, обладающим знанием открытого преобразования Ek. Очевидно, что определение Dk при знании Ek должно быть вычислительно неразрешимой задачей. Система RSA широко используется в системе цифровой подписи, так как ее преобразования обладают всеми необходимыми свойствами. Использо¬вание цифровой подписи предполагает существование двух процедур: подписывания и проверки /8.9/.
Процедура подписывания сообщения M - это возведение числа M в сте¬пень d по mod n:
S = Md (mod n).
Число S есть цифровая подпись, которую может выработать только владелец секретного ключа.
Процедура проверки подписи S , соответствующей сообщению M - это возведение числа S в целую степень e по mod n:
M'= Se (mod n).
Если M'= M, то сообщение M признается подписанным пользователем, который предоставил ранее открытый ключ e.
В реализации для сокращения времени подписывания и размера подпи¬си, в качестве источника для подписи служит не само исходное сообщение М (произвольной длины), а некоторая производная от него (фиксированной дли¬ны). Для ее получения используется общеизвестная функция Н, отображающая любое сообщение М в сообщение Н(М) фиксированного малого размера, кото¬рое далее преобразуется в цифровую подпись. Функция Н называется функцией хеширования (hash function), в простейшем случае это может быть, например, функция вычисления контрольной суммы текста сообщения по модулю 232, раз¬мер приведенного для электронного подписывания сообщения тогда будет ра¬вен 32 двоичным разрядам (четырем байтам).