Иванов М.А. КМЗИ сети

10.В каком виде надежнее хранить пароли пользователей: в шифрованном или хешированном?

11.Как осуществляется контроль целостности потока сообщений?

12.Что такое одноразовый пароль?

152

ГЛАВА 5. КРИПТОСИСТЕМЫ С ОТКРЫТЫМ КЛЮЧОМ

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

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

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

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

153

5.1. Односторонние функции

Базовым в новом направлении криптографии является понятие односторонней функции [4]. По заданному аргументу x легко вычислить значение этой функции F(x), в то же время определение x из F(x) трудновычислимо, иначе говоря, нет алгоритма для решения этой задачи с полиномиальным временем работы. Теоретически x по известному значению F(x) можно найти всегда, используя метод полного перебора, т.е. проверяя по очереди все возможные значения x до тех пор, пока соответствующее значение F(x) не совпадет с заданным. Однако практически при значительной размерности множества X такой подход неосуществим.

Итак, односторонней функцией называется функция F : X ο Y , обладающая двумя свойствами:

1)существует полиномиальный алгоритм вычисления значений F(x), иначе говоря, задача нахождения значений y = F(x) при известных значениях x вычислительно разрешима;

2)не существует полиномиального алгоритма инвертирования функции F, т.е. задача нахождения значений x по известным значениям y = F(x) вычислительно неразре-

шима.

До сих пор ни для одной функции кандидата на звание односторонней не доказано, что она действительно является односторонней.

Пример кандидата на звание односторонней функции –

модульное возведение в степень, т.е. функция

F x Ζx modp ,

где p – большое простое число, Ζ – примитивный элемент поля GF p . То, что эта функция может быть эффективно вычислена даже при разрядности параметров в несколько сотен знаков,

можно показать на примере: Ζ25 можно вычислить с помощью всего лишь шести операций умножения (умножением считается и возведение в квадрат), так как

154

Z25 Z2 Z 2 2 2 Z.

При вычислении Zx modp взятие модуля во избежания получе-

ния очень больших чисел следует делать после каждого умножения. Пусть l – разрядность экспоненты x, тогда при вычислении

Zx modp по приведенному в [3] рекурсивному алгоритму потребуется выполнить от l до 2l модульных операций умножения:

function expmod (Z, x, p) if x = 0 then return 1

if x = 0 mod2 then return

else return (Z expmod (Z, x – 1, p) mod p

Задача вычисления функции, обратной модульному возведе-

нию в степень, называется задачей дискретного логарифмирова-

ния. На сегодняшний день неизвестно ни одного эффективного алгоритма вычисления дискретных логарифмов больших чисел.

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

сторонней функции с секретом (one-way trapdoor function). Та-

кова, например, функция Ek : X ο Y , имеющая обратную Dk :Y ο X , однако узнать обратную функцию только по Ek без

знания секрета k невозможно.

Таким образом, односторонней функцией с секретом k называется функция Ek : X ο Y , зависящая от параметра k и обладающая тремя свойствами:

1)при любом k существует полиномиальный алгоритм вычисления значений Ek x ;

2)при неизвестном k не существует полиномиального алгоритма инвертирования Ek ;

155

3)при известном k существует полиномиальный алгоритма инвертирования Ek .

Функцию Ek можно использовать для зашифрования информации, а обратную ей функцию Dk – для расшифрования, так

как при всех x X справедливо

Dk Ek x x.

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

Применение рассмотренных функций для шифрования информации позволяет [3, 4, 29]:

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

5.2. Модель криптосистемы с открытым ключом

Криптосистема с открытым ключом (public key cryptosystem) (рис. 5.1), основанную на применении односторонних функций с секретом, можно реализовать следующим образом. Пользователь B, который хочет получать конфиденциальные сообщения,

156

должен выбрать одностороннюю функцию EB с секретом (ключом) kB . Он сообщает всем заинтересованным описание своей функции зашифрования EB , например, публикует его в справочнике открытых ключей. При этом ключ kB , а, следовательно, и алгоритм расшифрования DB держатся в секрете. Если теперь пользователь A хочет послать B секретное сообщение

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

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

рование.

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

157

ственно Ek и Dk (например, ECB и CBC, при этом, очевидно, что второй вариант предпочтительней).

Рис. 5.1. Модель криптосистемы с открытым ключом

Наиболее известные системы с открытым ключом: рюкзачная криптосистема (Knapsack Cryptosystem); криптосистема RSA;

криптосистема Эль-Гамаля (ElGamal Cryptosystem); криптосистема, основанная на свойствах эллиптических кривых.(Elliptic Curve Cryptosystem (ECCS)).

Криптосистема Т. Эль-Гамаля, основанная на сложности решения задачи дискретного логарифмирования, послужила основой для создания старых российского и американского стандартов электронной подписи. Остальные криптосистемы будут рассмотрены ниже.

5.3. Открытое распределение ключей

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

158

му каналу связи удаленных абонентов A и B, обладающую следующими свойствами:

в конце процедуры у A и B появляется общая секретная информация (общий секретный ключ kAB ), которой до на-

чала действия протокола не было; противник, способный перехватывать все сообщения и

знающий цель протокола, не может восстановить сформированный секретный ключ.

Этот протокол, на первый взгляд невозможный, основывается на задаче дискретного логарифмирования, рассмотренной выше. Противник, который хочет узнать формируемый секретный ключ, вынужден решать именно эту трудную математическую задачу. Пусть p – большое простое число, Ζ – примитивный элемент поля GF p (основы теории конечных полей даны

в гл. 8). Числа p и Ζ считаются общедоступными. Тогда процедура получения общей секретной информации имеет следующий вид.

Протокол выработки общего секретного ключа Диффи–Хеллмана

1.Абоненты A и B независимо друг от друга вырабатывают два случайных числа соответственно xA и xB , которые держат в секрете.

2. Абоненты A и B вычисляют значения yA ΖxA modp и yB ΖxB modp .

3.Абоненты A и B обмениваются сообщениями yA и yB .

4.A, получив сообщение yB , вычисляет значение

yB xA mod p ΖxB xA mod p ;

5.B, получив сообщение yA , вычисляет значение

yA xB mod p ΖxA xB mod p .

6. Элемент GF p , равный ΖxA xB mod p , объявляется общим секретным ключом.

159

5.4. Электронная цифровая подпись

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

Если Ek – односторонняя функция с секретом, то подписан-

ное сообщение можно представить в виде пары

m, Dk m ,

где m – подписываемый документ, а Dk – функция, обратная Ek . Из определения односторонней функции с секретом следу-

ет, что для такой подписи характерны следующие особенности: подписать сообщение m может только обладатель секрета k, т.е. подделать подпись практически невозможно; проверить подпись может любой абонент, знающий функцию Ek , так как проверка подписи заключается в проверке

равенства

m Ek Dk m ;

при возникновении споров относительно авторства сообщений отказаться от подписи нельзя из-за невозможности ее подделки; подпись позволяет контролировать целостность подпи-

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

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

160