Бабаш А.В., Шанкин Г.П. Криптография (распознано не всё)

121

Сокращение времени обмена информацией. Используются стегано-

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

Постоянная работа системы передачи информации. Для сокрытия

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

Стеганографические приемы защиты программных продуктов.

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

Замаскированные закладки встречаются во встроенных системах криптографической защиты некоторых широко известных программных про­ дуктов, в частности, в электронной почте ЗрппГ Май и в известной системе управления базами данных Рагайох.

В конце шифрованного файла БрпШ Май просто записывает в замас­ кированном виде введенный пользователем пароль, при этом способ маски­ ровки очень прост и легко восстанавливается стандартными методами анализа программного обеспечения.

В СУБД Рагайох устроено несколько подругому. Вводимый пароль преобразуется по весьма сложному алгоритму. Провести обратные преобразо­ вания достаточно сложно. Для закрытия информации используется только преобразованный пароль - рабочий ключ. Этот рабочий ключ разработчики решили вписать в явном виде в заголовок файла таблицы базы данных. Вся­ кий знакомый с алгоритмом криптографических преобразований может из­ влечь рабочий ключ из заголовка и восстановить закрываемую информацию. Пароль, введенный пользователем, он скорее всего никогда не узнает, но содержание таблицы восстановит в полном объеме при минимальных затратах.

122

Параграф 1.6

Идея открытого ключа - революция в криптогра­

фии (/Три/)

Проблема распределения ключей.

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

Классическая модель криптографической системы (модель Шеннона)

1 Г

123

Но можно ли передавать ключи, если такого защищенного канала свя­ зи нет? Могут ли, например, два удаленных абонента обменяться секретными сообщениями, пользуясь лишь таким средством связи, как электронная почта?

Проблема цифровой подписи.

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

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

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

Считается, что криптография с открытым ключом родилась в 1976 го­ ду, когда была опубликована статья американских математиков У. Диффи и М.Э. Хеллмана «Новые направления в криптографии». Эта публикация не то­ лько положила начало новому направлению науки о шифрах, но и послужила

124

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

В своей основополагающей работе Диффи и Хеллман ввели в рассмо­ трение понятие однонаправленной функции с лазейкой (или с секретом), ста­ вшее центральным в криптографии с открытым ключом. Оно является обоб­ щением известного до 1976 года понятия однонаправленной функции.

Определение 1. Функция Р: X -> V называется однонаправленной

функцией (ОФ), если она обладает двумя свойствами:

1)функция Р легко вычислима;

2)почти для всех уеУ сложно найти такое хеХ, что Р(х) = у.

Определение 2. Функция Рх: X —» V, зависящая от параметра К, на­

зывается однонаправленной функцией с лазейкой (ОФЛ), если она обладает тремя свойствами:

1)при любом х функция Рх легко вычислима; при неизвестном %почти для всех уеУ сложно найти такое хеХ, что Рх(х) = у;

2)при известном %функцию Рх легко инвертировать (инвертировать -

значит решить уравнение Рх(х) = у относительно неизвестного х). Второй пункт определения 1 означает, что почти для всех уеУ функ­

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

Замечание. Определения 1 и 2 являются математически нестрогими.

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

В настоящее время не построено ни одной функции, для которой было бы доказано, что она является однонаправленной или однонаправленной функцией с лазейкой. Более того, не доказано даже их существование. Для практических целей криптографии построено несколько функций, которые могут оказаться ОФЛ. Для них пока строго не доказано второе свойство - от­ сутствие полиномиального алгоритма их инвертирования, но считается, что эта задача эквивалентна некоторой давно изучаемой трудной математической проблеме. Одним из самых известных и широко используемых «кандидатов» в однонаправленные функции с лазейкой является функция шифрования К.8А.

Наиболее распространенным «кандидатом» в однонаправленные можно счи-

125

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

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

Для решения проблемы распространения ключей было предложено два основных подхода.

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

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

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

Принципы построения криптосистем с открытым ключом.

Опишем сначала принцип построения криптосистемы с открытым ключом, предложенный Диффи и Хеллманом (XV. БИПе, М.Е. НеНтап, 1976). Пользователь А, который хочет получать шифрованные сообщения, выбирает однонаправленную функцию Рх: X—»У с лазейкой, алгоритм вычисления зна­ чений Рх публикует, а %оставляет в секрете. Любой пользователе В, желаю­

126

щий послать А сообщение хеХ, вычисляет у = Рх(х) и посылает у по незащи­ щенному каналу связи. Из второго и третьего пункта определения 2 следует, что только пользователь А может по у вычислить х, так как только А знает секрет %.

Определение 3. Криптографической системой с открытым ключом

называется пятерка А=<Х,К,У,Е,0>, где Х,У - конечные множества, соответ­ ственно, открытых и шифрованных текстов, К - множество ключей (откры­ тых и секретных), Е = (ЕХ}Х€К , О = {Ох}Хек - семейства алгоритмов зашиф­ рования ирасшифрования соответственно, определяющих отображения:

	Ех: Х->У,
	Вх: У->Х,	*
такие что
1)	для каждого %еК Бх обратно к Ех, то есть для любых %еК, хеУ
	°х(Ех(х)) = х;
2)	для каждого	функции Ех и Эх легко вычислимы;

3)для почти каждого %еК вычислительно труднб по данному Ех найти какой-либо легко вычислимый алгоритм, эквивалентный Эх;

4)по каждому заданному %еК можно легко получить соответствую­ щую пару (ЕХ,Б Х);

5)существует легко вычислимый алгоритм генерации ключей.

Поясним данное определение. В нем третье свойство можно сформу­ лировать по-другому: почти для каждого %еК вычислительно невозможно по данному случайному уе Уопределить хеУ, такой, что Ех(х)=у, то есть не су­ ществует полиномиального алгоритма (алгоритма со сложностью переделяе­ мой некоторым полиномом от размера входных данных), находящего какоелибо решение х уравнения Ех(х)=у. Это свойство означает, что можно не засе­ кречивать алгоритм зашифрования Ех. При этом алгоритм расшифрования Бх скомпрометирован не будет. Ясно, что алгоритм Ох имеет в качестве парамет­ ров элементы ключа %, не являющиеся параметрами алгоритма Ех (иначе по Ех можно было бы восстановить Ох). Эти элементы ключа являются секретными и образуют секретный ключ Хг криптосистемы А. Остальные элементы ключа X являются параметрами алгоритма Ех и образуют открытый ключ %\ крип­ тосистемы А.

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

может подать ему на вход случайную строку г (например, двоичную строку достаточной длины) и получить ключ х и соответствующую этому ключу па­ ру (Ех, Ох). Строка г может также вырабатываться генератором случайных чи­ сел.

Замечание. Выше было определено, какие элементы ключа асиммет­

ричной криптографической системы называются открытыми, а какие секрет­ ными. Согласно этому определению далеко не во всякой криптосистеме с от­ крытыми ключами алгоритм расшифрования определяется только секретным ключом хгТо есть не всегда, зная лишь секретную часть ключа %, можно вос­ становить алгоритм Бх (например, этого нельзя сделать в криптосистеме ЭльГамаля). Существуют также и такие асимметричные криптосистемы, в кото­ рых знание %2 позволяет восстановить весь ключ (например, К.8А), а значит, и

алгоритм Ох. Будем в дальнейшем для удобства алгоритм зашифрования обо­ значать через Ехь а алгоритм расшифрования через Охг, где х 1 и у! - (соот­

ветственно открытый и секретный ключи. При этом необходимо помнить, что алгоритм Т)гг может иметь в качестве параметров элементы ключа х1- В от­ личие от него алгоритм зашифрования ЕХ1 всегда можно восстановить, зная лишь х 1 -

Опишем теперь, каким образом два пользователя А и В могут с помо­ щью криптосистемы с открытым ключом организовать передачу секретных сообщений. Пусть пользователь А хочет послать секретное сообщение поль­ зователю В. Для этого В строит ключ х = (хЬ Х2) и посылает х1 пользователю

А. Получив хЕ пользователь А шифрует сообщение х с помощью алгоритма ЕХ|. Полученный шифртекст у=ЕХ](х) он посылает В. Используя алгоритм расшифрования Т)г2, пользователь В из полученного у вычисляет открытое сообщение х=Охг(у). Заметим, что только В может по у найти х, так как только он знает секретный ключ. Криптоаналитику, в распоряжение которого попа­ дают %1 и у, для определения открытого сообщения необходимо решить урав­ нение ЕХ](х)=у. Но по третьему пункту определения 3 эта задача практически неразрешима.

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

128

обеспечивает стойкость. Криптоаналитик может построить свою пару ключей %=(% 1,х'2) и послать А ключ %' 1 от имени пользователя В. Ничего не подо­ зревающий пользователь А зашифрует сообщение х, предназначенное для В, на ключе криптоаналитика и затем, послав его, даст возможность последнему без труда восстановить х.

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

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

Определение 5. Аутентификация сообщения - это подтверждение под­ линности источника сообщения.

Определение 6. Цифровая подпись - это криптографическое средство,

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

Схема цифровой подписи. Диффи и Хеллман предложили следующий принцип построения схемы цифровой подписи. Пользователь А выбирает од­ нонаправленную функцию с секретом Рх: У -> X, алгоритм вычисления зна­ чений Рх публикует, х оставляет в секрете. Для того чтобы подписать сообще­ ние хеХ, он находит такое уеУ, что Рх(у) = х, и посылает его вместе с х. По­ лучив пару (х,у), пользователь В проверяет равенство Рх(у) = х. Выполнение этого равенства означает, что источником сообщения х является пользователь А, владеющий секретом %.

Криптографические системы с открытым ключом обеспечивают реше­ ние проблемы цифровой подписи, если они удовлетворяют следующему усло­ вию:

129

Х=У и для каждого %еК Ех обратно к Эх, то есть для любых %еК, хвХ

Ех(°х(х)) = х-

\

Пусть пользователь А хочет послать подписанное несекретное сообще­ ние пользователю В. Для этого А строит ключ х=(х!>Х^) и посылает у1 поль­ зователю В. Сообщение х пользователь А шифрует с помощью своего лично­ го ключа %2, получая таким образом подпись у=Ох2(х), и посылает ее В. Ра­

ньше, когда при передаче информации требовалась только секретность, с по­ мощью алгоритма Ох2 владелец ключа %расшифровывал получаемые им соо­

бщения, теперь же он использует этот алгоритм для зашифрования или по­ дписи. Используя алгоритм ЕхЬ пользователь В может вычислить х из полу­ ченного у и убедиться таким образом, что отправителем сообщения х является А. Подпись у он сохраняет как доказательство того, что пользователь А при­ слал ему сообщение х. Если позднее А откажется от факта посылки этого соо­ бщения, то В может предъявить суду подпись у. Суд возьмет открытый ключ %\ пользователя А и установит, что Ех1(у) является осмысленным сообщени­ ем: Так как только А знает секретный ключ / 2, то только он может быть исто­

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

Открытое распределение ключей Диффи-Хеллмана.

Рассмотрим теперь другой подход к решению проблемы распростра­ нения ключей, а именно: открытое распределение ключей. Под открытым распределением ключей понимают последовательность действий двух или бо­ лее пользователей, в результате выполнения которой им становится доступна некоторая общая секретная информация (ключ). При этом любой другой пользователь, следящий за передаваемыми по каналу связи сообщениями, эту секретную информацию определить не в состоянии. В работе ЮН. ^.БШ е, М.Е. НеИшап. Ые\у сйгесйопз т сгурЮ^гарЬу, 1ЕЕЕ Тгапзасбопз оп 1пйгшапоп ТЬеогу, У.1Т-22, N .6,1ЧоуетЪег,1976, рр.644-654/ был предложен так называе­

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

тивной группе простого поля: Г(х) = а х ш оёр , где р - простое число, а -

примитивный элемент поля ОР(р), 1<х< р - 1. Эта фукнция является канди­ датом в однонаправленные. Действительно, она легко вычислима, так как, ис­ пользуя метод квадратов, значения этой функции можно вычислять с полино­ миальной сложностью, оцениваемой величиной 0 ((1о§ р)3), в то время как об­

ратная задача - задача инвертирования функции - является сложной. Для ин-

5 Зак . 5

130

вертирования функции Дх) необходимо уметь решать уравнение

у = а х т о ё р , то есть уметь решать задачу дискретного логарифмирования в

мультипликативной группе простого поля. В настоящее время не известно достаточно эффективных (полиномиальных относительно 1о§р) алгоритмов

дискретного логарифмирования в мультипликативной группе СР(р) поля. Этот факт и лежит в основе стойкости данной схемы открытого распределе­ ния ключей. Опишем ее.

Пусть два пользователя А и В хотят выработать общий ключ. Для это­ го они заранее определяют элементы р и а, которые считаются общедоступ­ ными. Оба пользователя случайно выбирают по одному натуральному числу хА и Хв: 1 < хА, хв < р - 1 и оставляют их в секрете. После этого выполняется следующая последовательность шагов.

1)А вычисляет элемент уА = а Хд пкхЗр и посылает его В;

2)В вычисляет элемент ув = а х®ш оёр и посылает его А;

Таким образом, А и В. получают общий элемент поля ОР(р), равный

ахАхв щос1р, который и объявляется их общим ключом. Пассивный крипто­ аналитик получает в свое распоряжение величины р, а, а Хд пкхЗр,

аХв тос!р и хочет определить а ХдХв ш оёр . Эта задача называется пробле­

мой Диффи-Хеллмана. В настоящее время не найдено более эффективного решения этой проблемы, чем дискретное логарифмирование.

Параграф 1.7 Недостатки модели шифра Шеннона. Обобщенная

модель шифра

В классической модели шифра два абонента используют для связи один ключ, хранящийся от всех других абонентов в секрете. Такой ключ на­ зывают секретным, а криптографические системы с секретными ключами на­ зывают еще одноключевыми или симметричными шифрами (криптосистема­ ми). При использовании симметричных криптосистем возникает проблема рассылки ключей. Если два человека, которые никогда ранее не встречались,