Криптография

 

 

Содержание

От автора___________________________________________________________________ 1

Введение____________________________________________________________________ 2

Терминология______________________________________________________________ 3

Требования к криптосистемам________________________________________________ 4

Симметричные криптосистемы________________________________________________ 6

Перестановки______________________________________________________________ 7

Системы подстановок_______________________________________________________ 7

Гаммирование_____________________________________________________________ 13

Датчики ПСЧ_____________________________________________________________ 13

Стандарт шифрования данных ГОСТ 28147-89_________________________________ 15

Системы с открытым ключом________________________________________________ 19

Алгоритм RSA____________________________________________________________ 20

Криптосистема Эль-Гамаля__________________________________________________ 24

Криптосистемы на основе эллиптических уравнений___________________________ 25

Электронная подпись________________________________________________________ 26

Электронная подпись на основе алгоритма RSA________________________________ 27

Цифровая сигнатура________________________________________________________ 29

Управление ключами________________________________________________________ 32

Генерация ключей_________________________________________________________ 32

Накопление ключей________________________________________________________ 32

Распределение ключей______________________________________________________ 33

Проблемы и перспективы криптографических систем___________________________ 36

Шифрование больших сообщений и потоков данных____________________________ 36

Использование “блуждающих ключей”________________________________________ 37

Шифрование, кодирование и сжатие информации______________________________ 39

Реализация криптографических методов______________________________________ 40

Заключение_________________________________________________________________ 42

От автора

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

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

Многие вопросы к сожалению остались за обложками этой книги. В частности после долгих сомнений Автор решил отказаться от рассмотрения DES, ввиду его крайней непрактичности и неуживчивости на российской почве[1].

Массу полезной информации можно найти на сервере ftp.rsa.com. В faq5.doc Вы если и не найдете ответ на любой вопрос по криптографии, то обнаружите большое количество ссылок на другие источники.

Автор будет признателен за любые замечания и вопросы, которые проще всего направить по адресу: bar@glasnet.ru

Баричев Сергей

Введение

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

С широким распространением письменности криптография стала формироваться как самостоятельная наука. Первые криптосистемы встречаются уже в начале нашей эры. Так, Цезарь в своей переписке использовал уже более менее систематический шифр, получивший его имя.

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

По­че­му про­бле­ма ис­поль­зо­ва­ния крип­то­гра­фи­че­ских ме­то­дов в информационных системах (ИС) ста­ла в на­стоя­щий мо­мент осо­бо ак­ту­аль­на?

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

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

Про­бле­мой защиты информации путем ее преобразования за­ни­ма­ет­ся крип­то­ло­гия (kryptos - тай­ный, logos - нау­ка). Криптология раз­де­ля­ет­ся на два на­прав­ле­ния - крип­то­гра­фию и крип­тоа­на­лиз. Це­ли этих на­прав­ле­ний прямо про­ти­во­по­лож­ны.

Крип­то­гра­фия за­ни­ма­ет­ся по­ис­ком и ис­сле­до­ва­ни­ем ма­те­ма­ти­че­ских ме­то­дов пре­об­ра­зо­ва­ния ин­фор­ма­ции.

Сфе­ра ин­те­ре­сов криптоанализа - ис­сле­до­ва­ние воз­мож­но­сти рас­шиф­ро­вы­ва­ния ин­фор­ма­ции без зна­ния клю­чей.

В этой книге ос­нов­ное вни­ма­ние бу­дет уде­ле­но крип­то­гра­фи­че­ским ме­то­дам.

Современная криптография включает в себя четыре крупных раздела:

1. Симметричные криптосистемы.

2. Криптосистемы с открытым ключом.

3. Системы электронной подписи.

4. Управление ключами.

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

Тер­ми­но­ло­гия

Итак, криптография дает возможность преобразовать информацию таким образом, что ее прочтение (восстановление) возможно только при знании ключа.

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

Алфавит - конечное множество используемых для кодирования информации знаков.

Текст - упорядоченный набор из элементов алфавита.

В качестве примеров алфавитов, используемых в современных ИС можно привести следующие:

*            алфавит Z₃₃ - 32 буквы русского алфавита и пробел;

*            алфавит Z₂₅₆ - символы, входящие в стандартные коды ASCII и КОИ-8;

*            бинарный алфавит - Z₂ = {0,1};

*            восьмеричный алфавит или шестнадцатеричный алфавит;

Шиф­ро­ва­ние - пре­об­ра­зо­ва­тель­ный про­цесс: ис­ход­ный текст, ко­то­рый но­сит так­же на­зва­ние от­кры­то­го тек­ста, за­ме­ня­ет­ся шиф­ро­ван­ным тек­стом.

 

 

 

 

 

Дешифрование - обратный шифрованию процесс. На основе ключа шифрованный текст преобразуется в исходный.

Ключ - ин­фор­ма­ция, не­об­хо­ди­мая для бес­пре­пят­ст­вен­но­го шиф­ро­ва­ния и де­шиф­ро­ва­ния тек­стов.

Крип­то­гра­фи­че­ская сис­те­ма пред­став­ля­ет со­бой се­мей­ст­во T пре­об­ра­зо­ва­ний от­кры­то­го тек­ста. Чле­ны это­го се­мей­ст­ва ин­дек­си­ру­ют­ся, или обо­зна­ча­ют­ся сим­во­лом k; па­ра­метр k яв­ля­ет­ся клю­чом. Про­стран­ст­во клю­чей K - это на­бор воз­мож­ных зна­че­ний клю­ча. Обыч­но ключ пред­став­ля­ет со­бой по­сле­до­ва­тель­ный ряд букв ал­фа­ви­та.

Криптосистемы разделяются на симметричные и с открытым ключом.

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

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

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

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

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

·   количество всех возможных ключей;

·   среднее время, необходимое для криптоанализа.

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

Требования к криптосистемам

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

Для со­вре­мен­ных крип­то­гра­фи­че­ских сис­тем за­щи­ты ин­фор­ма­ции сфор­му­ли­ро­ва­ны сле­дую­щие об­ще­при­ня­тые тре­бо­ва­ния:

·    за­шиф­ро­ван­ное сообщение дол­жно под­да­вать­ся чте­нию толь­ко при на­ли­чии клю­ча;

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

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

·    зна­ние ал­го­рит­ма шиф­ро­ва­ния не долж­но вли­ять на на­деж­ность за­щи­ты;

·    не­зна­чи­тель­ное из­ме­не­ние клю­ча долж­но при­во­дить к су­ще­ст­вен­но­му из­ме­не­нию ви­да за­шиф­ро­ван­но­го сообщения да­же при ис­поль­зо­ва­нии од­но­го и то­го же клю­ча;

·    струк­тур­ные эле­мен­ты ал­го­рит­ма шиф­ро­ва­ния долж­ны быть не­из­мен­ны­ми;

·    до­пол­ни­тель­ные би­ты, вво­ди­мые в сообщение в про­цес­се шиф­ро­ва­ния, должен быть пол­но­стью и на­деж­но скры­ты в шиф­ро­ван­ном тек­сте;

·    дли­на шиф­ро­ван­но­го тек­ста долж­на быть рав­ной дли­не ис­ход­но­го тек­ста;

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

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

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

Симметричные криптосистемы

Все мно­го­об­ра­зие су­ще­ст­вую­щих крип­то­гра­фи­че­ских ме­то­дов мож­но све­сти к сле­дую­щим клас­сам пре­об­ра­зо­ва­ний:

Мо­но- и мно­го­ал­фа­вит­ные под­ста­нов­ки.

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

Пе­ре­ста­нов­ки.

Так­же не­слож­ный ме­тод крип­то­гра­фи­че­ско­го пре­об­ра­зо­ва­ния. Ис­поль­зу­ет­ся как пра­ви­ло в со­че­та­нии с дру­ги­ми ме­то­да­ми.

Гам­ми­ро­ва­ние.

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

Блочные шифры.

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

Перестановки

Перестановкой s набора целых чисел (0,1,...,N-1) называется его переупорядочение. Для того чтобы показать, что целое i пере­мещено из позиции i в позицию s(i), где 0 £ (i) < n, будем использовать запись

s=(s(0), s(1),..., s(N-1)).

Число перестановок из (0,1,...,N-1) равно n!=1*2*...*(N-1)*N. Введем обозначение s для взаимно-однозначного отображения (гомо­морфизма) набора S={s₀,s₁, ...,s_N-1}, состоящего из n элементов, на себя.

s: S ® S

s: s_i ® s_s(i), 0 £ i < n

Будем говорить, что в этом смысле s является перестановкой элементов S. И, наоборот, автоморфизм S соответствует пере­становке целых чисел (0,1,2,.., n-1).

Криптографическим преобразованием T для алфавита Z_m называется последовательность автоморфизмов: T={T⁽ⁿ⁾:1£n<¥}

T⁽ⁿ⁾: Z_m,n®Z_m,n, 1£n<¥

Каждое T⁽ⁿ⁾ является, таким образом, перестановкой n-грамм из Z_m,n.

Поскольку T⁽ⁱ⁾ и T^(j) могут быть определены независимо при i¹j, число криптографических преобразований исходного текста размерности n равно (mⁿ)![2]. Оно возрастает непропорционально при увеличении m и n: так, при m=33 и n=2 число различных криптографических преобразований равно 1089!. Отсюда следует, что потенциально существует большое число отображений исходного текста в шифрованный.

Практическая реализация криптогра­фических систем требует, чтобы преобразо­вания {T_k: kÎK} были определены алгоритмами, зависящими от относительно небольшого числа параметров (ключей).

Сис­те­мы под­ста­но­вок

Определение Подстановкой p на алфавите Z_m называется автоморфизм Z_m, при котором буквы исходного текста t замещены буквами шифрованного текста p(t):

Z_m à Z_m; p: t à p(t).

Набор всех подстановок называется симметрической группой Z_m è будет в дальнейшем обозначаться как SYM(Z_m).

Утверждение SYM(Z_m) c операцией произведения является группой, т.е. операцией, обладающей следующими свойствами:

   Замкнутость: произведение подстановок p₁p₂ является подста­новкой:

p: tàp₁(p₂(t)).

   Ассоциативность: результат произведения p₁p₂p₃ не зависит от порядка расстановки скобок:

(p₁p₂)p₃=p₁(p₂p₃)

   Существование нейтрального элемента: постановка i, опре­деляемая как i(t)=t, 0£t<m, является нейтральным элементом SYM(Z_m) по операции умножения: ip=pi для "pÎSYM(Z_m).

   Существование обратного: для любой подстановки p существует единственная обратная подстановка p^-1, удовлетворя­ющая условию

pp^‑1=p^‑1p=i.

Число возможных подстановок в симметрической группе Z_m называется порядком SYM(Z_m) и равно m! .

Определение. Ключом подстановки k для Z_m называется последовательность элементов симметрической группы Z_m:

k=(p₀,p₁,...,p_n-1,...), p_nÎSYM(Z_m), 0£n<¥

Подстановка, определяемая ключом k, является крипто­гра­фи­ческим преобразованием T_k, при помощи которого осуществляется преоб­разование n-граммы исходного текста (x₀ ,x₁ ,..,x_n-1) в n-грамму шифрованного текста (y₀ ,y₁ ,...,y_n-1):

y_i=p(x_i), 0£i<n

где n – произвольное (n=1,2,..). T_k называется моноалфавитной под­ста­новкой, если p неизменно при любом i, i=0,1,..., в противном случае T_k называется многоалфавитной подстановкой.

Примечание. К наиболее существенным особенностям подста­новки T_k относятся следующие:

1. Исходный текст шифруется посимвольно. Шифрования n-граммы (x₀ ,x₁ ,..,x_n-1) и ее префикса (x₀ ,x₁ ,..,x_s-1) связаны соотношениями

T_k(x₀ ,x₁ ,..,x_n-1)=(y₀ ,y₁ ,...,y_n-1)

T_k(x₀ ,x₁ ,..,x_s-1)=(y₀ ,y₁ ,...,y_s-1)

2. Буква шифрованного текста y_i является функцией только i-й компоненты ключа p_i и i-й буквы исходного текста x_i.

Подстановка Цезаря

Подстановка Цезаря является самым простым вариантом подстановки. Она относится к группе моноалфавитных подстановок.

Определение. Подмножество C_m={C_k: 0£k<m} симметрической группы SYM(Z_m), содержащее m подстановок

C_k: j®(j+k) (mod m), 0£k < m,

называется подстановкой Цезаря.

Умножение коммутативно, C_kC_j=C_jC_k=C_j+k, C₀ – идентичная подстановка, а обратной к C_к является C_k^-1=C_m-k, где 0<k<m. Семейство подстановок Цезаря названо по имени римского императора Гая Юлия Цезаря, который поручал Марку Туллию Цицерону составлять послания с использованием 50-буквенного алфавита и подстановки C₃.

Подстановка определяется по таблице замещения, содержащей пары соответствующих букв “исходный текст – шифрованный текст”. Для C₃ подстановки приведены в Табл. 1. Стрелка (à) означает, что буква исходного текста (слева) шифруется при помощи C₃ в букву шифрованного текста (справа).

Определение. Системой Цезаря называется моноалфа­витная подстановка, преобразующая n-грамму исходного текста (x₀, x₁ ,..,x_n-1) в n‑грамму шифрованного текста (y₀ ,y₁ ,...,y_n-1) в соответствии с правилом

y_i=C_k(x_i), 0£i<n.

Например, ВЫШЛИТЕ_НОВЫЕ_УКАЗАНИЯ посредством подстановки C₃ преобразуется в еюыолхиврсеюивцнгкгрлб.

Таблица 1.

Аàг	Йàм	Тàх	Ыàю
Бàд	Кàн	Уàц	Ьàя
Вàе	Лàо	Фàч	Эà_
Гàж	Мàп	Хàш	Юàа
Дàз	Нàр	Цàщ	Яàб
Еàи	Оàс	Чàъ	_àв
Жàй	Пàт	Шàы
Зàк	Рàу	Щàь
Иàл	Сàф	Ъàэ

При своей несложности система легко уязвима. Если злоумышленник имеет

1) шифрованный и соответ­ствующий исходный текст или

2) шифрованный текст выбранного злоумыш­ленником исходного текста,

то определение ключа и дешифрование исходного текста тривиальны.

Более эффективны обобщения подстановки Цезаря - шифр Хилла и шифр Плэйфера. Они основаны на подстановке не отдельных символов, а 2-грамм (шифр Плэйфера) или n-грамм[3] (шифр Хилла). При более высокой криптостойкости они значительно сложнее для реализации и требуют достаточно большого количества ключевой информации.

Многоалфавитные системы. Системы одноразового использования.

Слабая криптостойкость моноалфавитных подстановок преодолевается с применением подстановок многоалфавитных.

Многоалфавитная подстановка определяется ключом p=(p₁,
p₂, ...), содержащим не менее двух различных подстановок. В начале рассмотрим многоалфавитные системы подстановок с нулевым начальным смещением.

Пусть {K_i: 0£i<n} - независимые случайные переменные с одинаковым распределением вероятностей, принимающие значения на множестве Z_m

Pкл{(K₀, K₁, ..., K_n-1)=(k₀, k₁, ..., k_n-1)}=(1/m)ⁿ

Система одноразового использования преобразует исходный текст

X=(X₀, x₁, ..., x_n-1)

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

Y=(Y₀, y₁, ..., y_n-1)

при помощи подстановки Цезаря

Y_i=C_Ki(x_i)=(K_i+X_i) (mod m) i=0...n-1 (1)

Для такой системы подстановки используют также термин “одноразовая лента” и “одноразовый блокнот”. Пространство ключей К системы одноразовой подстановки является вектором рангов (K₀, K₁, ..., K_n-1) и содержит mⁿ точек.

Рассмотрим небольшой пример шифрования с бесконечным ключом. В качестве ключа примем текст

 “БЕСКОНЕЧНЫЙ_КЛЮЧ....”.

Зашифруем с его помощью текст “ШИФР_НЕРАСКРЫВАЕМ”. Шифрование оформим в таблицу:

ШИФРУЕМЫЙ_ТЕКСТ	24	8	20	16	19	5	12	27	9	32	18	5	10	17	18
БЕСКОНЕЧНЫЙ_КЛЮЧ	1	5	17	10	14	13	5	23	13	27	9	32	10	11	30
ЩРДЪАТТССЦЪЫДФЬП	25	13	4	26	0	18	17	17	22	26	27	4	20	28	15

Исходный текст невозможно восстановить без ключа.

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

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

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

Системы шифрования Вижинера

Начнем с конечной последовательности ключа

 k = (k₀ ,k₁ ,...,k_n),

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

k = (k₀ ,k₁ ,...,k_n), k_j = k_{(j mod r}, 0 £ j < ¥ .

Например, при r = ¥ и ключе пользователя 15 8 2 10 11 4 18 рабочий ключ будет периодической последовательностью:

15 8 2 10 11 4 18 15 8 2 10 11 4 18 15 8 2 10 11 4 18 ...

 

Определение. Подстановка Вижинера VIG_k определяется как

 VIG_k : (x₀, x₁, ..., x_n-1) ® (y₀, y₁, ..., y_n-1) = (x₀+k, x₁+k,. .., x_n-1+k).

Таким образом:

1) исходный текст x делится на r фрагментов

 x_i = (x_i , x_i+r , ..., x_i+r(n-1)), 0 £ i < r;

2) i-й фрагмент исходного текста x_i шифруется при помощи подстановки Цезаря C_k :

(x_i , x_i+r , ..., x_i+r(n-1)) ® (y_i , y_i+r , ..., y_i+r(n-1)),

Вариант системы подстановок Вижинера при m=2 называется системой Вернама (1917 г).

В то время ключ k=(k₀ ,k₁ ,...,k_к-1) записывался на бумажной ленте. Каждая буква исходного текста в алфавите, расширенном некоторыми дополнительными знаками, сначала переводилась с использованием кода Бодо в пятибитовый символ. К исходному тексту Бодо добавлялся ключ (по модулю 2). Старинный телетайп фирмы AT&T со считывающим устройством Вернама и оборудованием для шифрования, использовался корпусом связи армии США.

Очень распространена плохая с точки зрения секретности практика использовать слово или фразу в качестве ключа для того, чтобы k=(k₀ ,k₁ ,...,k_к-1) было легко запомнить. В ИС для обеспечения безопасности информации это недопустимо. Для получения ключей должны использоваться программные или аппаратные средства случайной генерации ключей.

 

Пример. Преобразование текста с помощью подстановки Вижинера (r=4)

Исходный текст (ИТ1):

НЕ_СЛЕДУЕТ_ВЫБИРАТЬ_НЕСЛУЧАЙНЫЙ_КЛЮЧ

Ключ: КЛЮЧ

Разобьем исходный текст на блоки по 4 символа:

НЕ_С ЛЕДУ ЕТ_В ЫБИР АТЬ_ НЕСЛ УЧАЙ НЫЙ_ КЛЮЧ

и наложим на них ключ (используя таблицу Вижинера):

H+К=Ч, Е+Л=Р и т.д.

Получаем зашифрованный (ЗТ1) текст:

ЧРЭЗ ХРБЙ ПЭЭЩ ДМЕЖ КЭЩЦ ЧРОБ ЭБЮ_ ЧЕЖЦ ФЦЫН

Можно выдвинуть и обобщенную систему Вижинера. ЕЕ можно сформулировать не только при помощи подстановки Цезаря.

Пусть x - подмножество симметрической группы SYM(Z_m).

Определение. r-многоалфавитный ключ шифрования есть r-набор p = (p₀, p₁, ..., p_r-1) с элементами в x.

Обобщенная система Вижинера преобразует исходный текст (x₀, x₁ ,..., x_n-1) в шифрованный текст (y₀ ,y₁ ,...,y_n-1) при помощи ключа p = (p₀, p₁, ..., p_r-1) по правилу

VIG_k : (x₀ ,x₁ ,...,x_n-1) ® (y₀ ,y₁ ,...,y_n-1) = (p₀(х₀), p₁(х₁), ..., p_n-1(x_n-1)),

где используется условие p_i = p_{i mod r} .

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

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

Гам­ми­ро­ва­ние

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

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

Про­цесс дешифрования дан­ных сво­дит­ся к по­втор­ной ге­не­ра­ции гам­мы шиф­ра при из­вест­ном клю­че и на­ло­же­нии та­кой гам­мы на за­шиф­ро­ван­ные дан­ные.

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

Ме­тод гам­ми­ро­ва­ния ста­но­вит­ся бес­силь­ным, ес­ли зло­умыш­лен­ни­ку ста­но­вит­ся из­вес­тен фраг­мент ис­ход­но­го тек­ста и со­от­вет­ст­вую­щая ему шиф­ро­грам­ма. Про­стым вы­чи­та­ни­ем по мо­ду­лю по­лу­ча­ет­ся от­ре­зок ПСП и по не­му вос­ста­нав­ли­ва­ет­ся вся по­сле­до­ва­тель­ность. Зло­умыш­лен­ни­ки мо­жет сде­лать это на ос­но­ве до­га­док о со­дер­жа­нии ис­ход­но­го тек­ста. Так, ес­ли боль­шин­ст­во по­сы­лае­мых со­об­ще­ний на­чи­на­ет­ся со слов “СОВ.СЕК­РЕТ­НО”, то крип­тоа­на­лиз все­го тек­ста зна­чи­тель­но об­лег­ча­ет­ся. Это сле­ду­ет учи­ты­вать при соз­да­нии ре­аль­ных сис­тем ин­фор­ма­ци­он­ной безо­пас­но­сти.

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

Датчики ПСЧ

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

Конгруэнтные датчики

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

Од­ним из хо­ро­ших кон­гру­энт­ных ге­не­ра­то­ров яв­ля­ет­ся ли­ней­ный кон­гру­энт­ный дат­чик ПСЧ. Он вы­ра­ба­ты­ва­ет по­сле­до­ва­тель­но­сти псев­до­слу­чай­ных чи­сел T(i), опи­сы­вае­мые со­от­но­ше­ни­ем

T(i+1) = (A*T(i)+C) mod m,

где А и С - кон­стан­ты, Т(0) - ис­ход­ная ве­ли­чи­на, вы­бран­ная в ка­че­ст­ве по­ро­ж­даю­ще­го чис­ла. Оче­вид­но, что эти три ве­ли­чи­ны и об­ра­зу­ют ключ.

Та­кой дат­чик ПСЧ ге­не­ри­ру­ет псев­до­слу­чай­ные чис­ла с оп­ре­де­лен­ным пе­рио­дом по­вто­ре­ния, за­ви­ся­щим от вы­бран­ных зна­че­ний А и С. Зна­че­ние m обыч­но ус­та­нав­ли­ва­ет­ся рав­ным 2n , где n - дли­на машинного сло­ва в би­тах. Дат­чик име­ет мак­си­маль­ный пе­ри­од М до то­го, как ге­не­ри­руе­мая по­сле­до­ва­тель­ность нач­нет по­вто­рять­ся. По при­чи­не, от­ме­чен­ной ра­нее, не­об­хо­ди­мо вы­би­рать чис­ла А и С та­кие, что­бы пе­ри­од М был мак­си­маль­ным. Как по­ка­за­но Д. Кну­том, ли­ней­ный кон­гру­энт­ный дат­чик ПСЧ име­ет мак­си­маль­ную дли­ну М то­гда и толь­ко то­гда, ко­гда С - не­чет­ное, и А mod 4 = 1.

Для шиф­ро­ва­ния дан­ных с по­мо­щью дат­чи­ка ПСЧ мо­жет быть вы­бран ключ лю­бо­го раз­ме­ра. На­при­мер, пусть ключ со­сто­ит из на­бо­ра чи­сел x(j) раз­мер­но­стью b, где j=1, 2, ..., n. То­гда соз­да­вае­мую гам­му шиф­ра G мож­но пред­ста­вить как объ­е­ди­не­ние не­пе­ре­се­каю­щих­ся мно­жеств H(j).

Датчики М-последовательностей[5]

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

М-последовательности представляют собой линейные рекуррентные последовательности максимального периода, формируемые k-разрядными генераторами на основе регистров сдвига. На каждом такте поступивший бит сдвигает k предыдущих и к нему добавляется их сумма по модулю 2. Вытесняемый бит добавляется к гамме.

Строго это можно представить в виде следующих отношений:

r₁:=r₀ r₂:=r₁ ... r_k-1:=r_k-2

r₀:=a₀ r₁ Å a₁ r₂ Å ... Å a_k-2 r_k-1

Г_i:=r_k-

Здесь r₀ r₁ ... r_k-1- k однобитных регистров, a₀ a₁ ... a_k-1 - коэффициенты неприводимого двоичного полинома степени k-1. Г_i - i-е значение выходной гаммы.

Период М-последовательности исходя из ее свойств равен 2^k-1.

Другим важным свойством М-последовательности является объем ансамбля, т.е. количество различных М-последовательностей для заданного k. Эта характеристика приведена в таблице:

k	Объем ансамбля
5	6
6	8
7	18
8	16
9	48
10	60
16	2048

Очевидно, что такие объемы ансамблей последовательности неприемлемы.

Поэтому на практике часто используют последовательности Голда, образующиеся суммированием нескольких М-последовательно­стей. Объем ансамблей этих последовательностей на несколько порядков превосходят объемы ансамблей порождающих М-последовательностей. Так при k=10 ансамбль увеличивается от 1023 (М-последовательности) до 388000.

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

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

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

Стан­дарт шиф­ро­ва­ния дан­ных ГОСТ 28147-89[6]

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

Бо­лее эф­фек­тив­ным яв­ля­ет­ся оте­че­ст­вен­ный стан­дарт шиф­ро­ва­ния дан­ных.

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

Вве­дем ас­со­циа­тив­ную опе­ра­цию кон­ка­те­на­ции, ис­поль­зуя для нее муль­ти­п­ли­ка­тив­ную за­пись. Кро­ме то­го бу­дем ис­поль­зо­вать сле­дую­щие опе­ра­ции сло­же­ния:

·    AÅB - побитовое сложение по модулю 2;

·    A[+]B - сложение по модулю 2³²;

·    A{+}B - сложение по модулю 2³²-1;.

Алгоритм криптографического преобразования предусматривает несколько режимов работы. Во всех режимах используется ключ W длиной 256 бит, представляемый в виде восьми 32-разрядных чисел x(i).

W=X(7)X(6)X(5)X(4)X(3)X(2)X(1)X(0)

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

Самый простой из возможных режимов - замена.

Пусть открытые блоки разбиты на блоки по 64 бит в каждом, которые обозначим как T(j).

Очередная последовательность бит T(j) разделяется на две последовательности B(0) и A(0) по 32 бита (правый и левый блоки). Далее выполняется итеративный процесс шифрования описываемый следующими формулами, вид который зависит от :i:

·    Для i=1, 2, ..., 24, j=(i-1) mod 8;

A(i) = f(A(i-1) [+] x(j)) Å B(i-1)

B(i) = A(i-1)

·    Для i=25, 26, ..., 31, j=32-i;

A(i) = f(A(i-1) [+] x(j)) Å B(i-1)

B(i) = A(i-1)

·    Для i=32

A(32) = A(31)

B(32) = f(A(31) [+] x(0)) Å B(31).

Здесь i обозначает номер итерации. Функция f – функция шифрования.

Функция шифрования включает две операции над 32-разрядным аргументом.

Первая операция является подстановкой K. Блок подстановки К состоит из 8 узлов замены К(1)...К(8) с памятью 64 бита каждый. Поступающий на блок подстановки 32-разрядный вектор разбивается на 8 последовательно идущих 4-разрядных вектора, каждый из который преобразуется в 4-разрядный вектор соответствующим узлом замены, представляющим из себя таблицу из 16 целых чисел в диапазоне 0...15. Входной вектор определяет адрес строки в таблице, число из которой является выходным вектором. Затем 4-разрядные векторы последовательно объединяются в 32-разрядный выходной.

Вторая операция - циклический сдвиг влево 32-разрядного вектора, полученного в результате подстановки К. 64-разрядный блок зашифрованных данных Т представляется в виде

Т=А(32)В(32).

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

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

Другой режим шифрования называется режимом гаммирования.

Открытые данные, разбитые на 64-разрядные блоки T(i) (i=1,2,...,m) (m определяется объемом шифруемых данных), зашифровываются в режиме гаммирования путем поразрядного сложения по модулю 2 с гаммой шифра Г_ш, которая вырабатывается блоками по 64 бит, т.е.

Г_ш=(Г(1),Г(2),....,Г(m)).

Уравнение шифрования данных в режиме гаммирования может быть представлено в следующем виде:

Ш(i)=A(Y(i-1) Å C2, Z(i-1)) {+} C(1) Å T(i)=Г(i) Å T(i)

В этом уравнении Ш(i) обозначает 64-разрядный блок зашифрованного текста, А - функцию шифрования в режиме простой замены (аргументами этой функции являются два 32-разрядных числа). С1 и С2 - константы, заданные в ГОСТ 28147-89. Величины y(i) и Z(i) определяются итерационно по мере формирования гаммы следующим образом:

(Y(0),Z(0))=A(S), S - 64-разрядная двоичная последовательность

(Y(i),Z(i))=(Y(i-1) [+] C2, Z(i-1) {+} C(1)), i=1, 2, ..., m.

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

Режим гаммирования с обратной связью очень похож на режим гаммирования. Как и в режиме гаммирования открытые данные, разбитые на 64-разрядные блоки T(i), зашифровываются путем поразрядного сложения по модулю 2 с гаммой шифра Г_ш, которая вырабатывается блоками по 64 бит:

Г_ш=(Г(1), Г(2), ..., Г(m)).

Уравнение шифрования данных в режиме гаммирования с обратной связью выглядят следующим образом:

Ш(1)=A(S)ÅT(1)=Г(1)ÅT(1),

Ш(i)=A(Ш(i-1)ÅT(i)=Г(i)ÅT(i), i=2, 3, ..., m.

В ГОСТ 28147-89 определяется процесс выработки имито­вставки, который единообразен для всех режимов шифрования. Имитовставка - это блок из р бит (имитовставка И_р), который вырабатывается либо перед шифрованием всего сообщения. либо параллельно с шифрованием по блокам. Параметр р выбирается в соответствии с необходимым уровнем имитозащищенности.

Для по­лу­че­ния ими­тов­став­ки от­кры­тые дан­ные пред­став­ля­ют­ся так­же в ви­де бло­ков по 64 бит. Пер­вый блок от­кры­тых дан­ных Т(1) под­вер­га­ет­ся пре­об­ра­зо­ва­нию, со­от­вет­ст­вую­ще­му пер­вым 16 цик­лам ал­го­рит­ма ре­жи­ма про­стой за­ме­ны. При­чем в ка­че­ст­ве клю­ча ис­поль­зу­ет­ся тот же ключ, что и для шиф­ро­ва­ния дан­ных. По­лу­чен­ное 64-раз­ряд­но чис­ло сум­ми­ру­ет­ся с от­кры­тым бло­ком Т(2) и сум­ма вновь под­вер­га­ет­ся 16 цик­лам шиф­ро­ва­ния для ре­жи­ма про­стой за­ме­ны. Дан­ная про­це­ду­ра по­вто­рят­ся для всех m бло­ков со­об­ще­ния. Из по­лу­чен­но­го 64-раз­ряд­но­го чис­ла вы­би­ра­ет­ся от­ре­зок И_р дли­ной р бит.

Ими­тов­став­ка пе­ре­да­ет­ся по ка­на­лу свя­зи по­сле за­шиф­ро­ван­ных дан­ных. На при­ем­ной сто­ро­не ана­ло­гич­ным об­ра­зом из при­ня­то­го со­об­ще­ния выделяется? ими­тов­став­ка и срав­ни­ва­ет­ся с по­лу­чен­ной откуда?. В слу­чае не­сов­па­де­ния ими­тов­ста­вок со­об­ще­ние счи­та­ет­ся лож­ным.

Сис­те­мы с от­кры­тым клю­чом

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

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

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

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

Крип­то­гра­фи­че­ские сис­те­мы с от­кры­тым клю­чом ис­поль­зу­ют так называемые не­об­ра­ти­мые или од­но­сто­рон­ние функ­ции, ко­то­рые об­ла­да­ют сле­дую­щим свой­ст­вом: при за­дан­ном зна­че­нии x от­но­си­тель­но про­сто вы­чис­лить зна­че­ние f(x), од­на­ко ес­ли y=f(x), то нет про­сто­го пу­ти для вы­чис­ле­ния зна­че­ния x.

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

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

По­это­му что­бы га­ран­ти­ро­вать на­деж­ную за­щи­ту ин­фор­ма­ции, к сис­те­мам с от­кры­тым клю­чом (СОК) предъ­яв­ля­ют­ся два важ­ных и оче­вид­ных тре­бо­ва­ния:

1. Пре­об­ра­зо­ва­ние ис­ход­но­го тек­ста долж­но быть не­об­ра­ти­мым и ис­клю­чать его вос­ста­нов­ле­ние на ос­но­ве от­кры­то­го клю­ча.

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

Ал­го­рит­мы шиф­ро­ва­ния с от­кры­тым клю­чом по­лу­чи­ли ши­ро­кое рас­про­стра­не­ние в со­вре­мен­ных ин­фор­ма­ци­он­ных сис­те­мах. Так, ал­го­ритм RSA стал ми­ро­вым стан­дар­том де-фак­то для от­кры­тых сис­тем и ре­ко­мен­до­ван МККТТ.

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

1. Разложение больших чисел ан простые множители.

2. Вычисление логарифма в конечном поле.

3. Вычисление корней алгебраических уравнений.

Здесь же сле­ду­ет от­ме­тить, что ал­го­рит­мы криптосистемы с открытым ключом (СОК) мож­но ис­поль­зо­вать в трех на­зна­че­ни­ях.

1. Как са­мо­стоя­тель­ные сред­ст­ва за­щи­ты пе­ре­да­вае­мых и хра­ни­мых дан­ных.

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