Галуев Г.А. Математические основы криптологии

Подождите немного. Документ загружается.

вопрос о свойствах линейных рекуррентных последовательно-

стей. Если суммировать все результаты, полученные при иссле-

довании этого вопроса в рамках теории конечного поля и других

прикладных дисциплин, то можно сказать следующие:

1. Наиболее важными и интересными свойствами обладают

ЛРП максимального периода, формируемые характеристически-

ми многочленами, являющиеся нормированными неприводимы-

ми многочленами над

соответствующими полями

F .

2.ЛРП максимальной длины имеют равномерный спектр и,

следовательно, статистическую равномерность

3. Предельно большая длина периода

1−

4. Отсутствие скрытой периодичности.

Отмеченные свойства делают ЛРП эффективным инстру-

ментом для создания генераторов псевдослучайных последова-

тельностей, на базе которых строится широкий класс поточных

криптосистем.

9. Дополнительные математические

элементы криптографии.

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

Понятие односторонней функции впервые было введено в

работе Нидхема (Needham R.M.) о защите входа в вычислитель-

ные системы.

Определение. Функция )(

называется односторонней,

если для всех

x из ее области определения легко вычислить

)(

y =

, но почти для всех y из ее области значений нахожде-

ние

x, для которого

)(

, вычислительно неосуществимо.

В данном определении фраза «почти для всех

y» необхо-

дима, т.к. можно легко вычислить и запомнить согласно первой

части определения целую таблицу значений

)(),...,()(

2211 nn

xfyxfyxfy

, если окажется, что вы-

бранное значение

y принадлежит этой таблице, то и соответст-

вующий

x можно легко определить. Фраза «вычислительно не-

осуществимо» означает с точки зрения теории сложности, что

неосуществимо за полиномиальное время, которое характеризу-

ет решаемые задачи.

До сих пор не доказано, что односторонние функции суще-

ствуют. Показано, что проблема существования односторонних

функций эквивалентна известной нерешенной проблеме совпа-

дения задач классов

Р и NP.

Тем не менее, предложено много функций, которые похо-

жи на односторонние.

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

предложил использовать показательную функцию следующего

вида:

)(mod)( naxf

, где a - (основание) принадлежит интер-

валу (

1, n-1), а умножение ведется по модулю n. Значение

)(mod na

вычисляется достаточно эффективно с помощью из-

вестной схемы Горнера «слева на право»

)(mod)...))((()(mod

222

naaaana

⋅⋅⋅⋅=

−−

или «справа налево»

)mod()(...)(

naaa

−

⋅⋅⋅

для числа

x при его двоичном разложении в виде

∑

−

Даже при больших числах

x из интервала (1, n) вычисление

)(mod)( naxf

можно осуществить за

][log0

операций. Об-

ратная к этой функции - операция вычисления дискретного ло-

гарифма

x: по данным a и y найти такое целое x, что

yna

=)(mod

. До настоящего времени не известно эффектив-

ных алгоритмов решения этой задачи. Известно лишь, что слож-

ность вычисления дискретного логарифма

x эквивалента слож-

ности разложения целого числа на произведение простых чисел

и оценивается как

)2(0

,т.е. экспоненциальная оценка времен-

ной сложности.

На основе такой показательной односторонней функции

Диффори и Хеллман разработали так называемую криптографи-

ческую схему открытого распределения ключей, о которой более

подробно поговорим на следующих лекциях.

В качестве односторонней функции Кнут Д. предложил

использовать функцию вида

2121

, pиpгдеppa ⋅=

простые

числа. Идея здесь заключается в том, что произведение двух

простых чисел вычислить достаточно просто, а вот разложение

числа

a на сомножители

pиp

достаточно трудная задача.

В ряде случаев в качестве односторонней функции предла-

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

эта задача имеет следующую формировку: дано множество

n це-

лых чисел

aa ,...,

и целое число S, требуется определить су-

ществует - ли множество чисел

a ni

≤

≤1 , такое что их сумма

равна числу

S. Эта задача принадлежит к числу NP полных за-

дач и имеет экспоненциальную временную сложность

)2(0

Следует отметить, что использование односторонних

функций в чистом виде для зашифрования информации не имеет

смысла, так как никто, даже законный адресат не сможет рас-

шифровать шифротекст

)(

, полученный с ее помощью.

Однако идея, лежащая в основе построения таких функций, мо-

жет быть использована для построения так называемых одно-

сторонних функций с секретом, которые уже имеют практиче-

ский смысл.

Рассмотрим принципы построения односторонних функ-

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

)(mod)( nxxf

Определение. Односторонней функцией с секретом на-

зывается зависящая от параметра

К функция

)(xf

, такая, что

при известном

К можно найти полиномиальные алгоритмы

ДиE

, позволяющие легко вычислить как

)(xf

, так и об-

ратную к ней функцию

)(

−

для всех x из области определе-

ния функции

)(xf

. При этом нахождение

)(

−

вычисли-

тельно неосуществимо без знания секретного параметра

К даже

при известном алгоритме

Степенная функция

)(mod)( nxyxf

достаточно лег-

ко, за

)(log0

операций может быть вычислена при известных

m и n. Преобразование возведения в степень

)(mod nxy

на-

зывается вычислением корня

m степени по модулю n. В настоя-

щее время вычисление такого

x, что

)(mod nxy

при извест-

ных

y,m,n относится классу трудных задач. Основная идея ис-

пользования односторонних функций с секретом сводится к сле-

дующему.

Получение шифрованного текста С из исходного текста М

осуществляется путем использования указанной степенной

функции в виде:

)(mod)(

),(

nMMEC

, где e,n - ключ

преобразования зашифрования.

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

M восстанавливается

путем использования преобразования расшифрования на базе

этой же функции но с другой степенью

d в качестве ключа:

ключndnCCДM

−== ),), ((mod)(

n)(d,

. Оба эти преобразова-

ния легко выполнить за

)(log0

операций.

Если теперь ключ (

e, n) преобразования зашифрования

сделать открытым, а параметр

d держать в секрете, то восста-

новление исходного текста

M из зашифрованного текста С даже

при известном алгоритме зашифрования потребует решения

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

шифрования т.е. вычисления корня степени

e по модулю n. Это

позволяет использовать принцип открытого шифрования, когда

преобразование расширения держится в секрете. В этом случае

(

e,n) - открытый ключ, а - (d,n) - секретный ключ. Более подроб-

но мы рассмотрим этот вопрос при описании блочной криптоси-

стемы

RSA.

Группы подстановок.

При построении криптографических систем широкое при-

менение получили так называемые перестановочные многочле-

ны конечных полей

F , которые индуцируют перестановки

элементов конечного поля

F и, следовательно, соответствуют

элементам симметрической группы

S , т.е. группы всех подста-

новок на множестве из

q элементов.

Дадим определение перестановочного многочлена конеч-

ного поля

F и приведем ряд теорем, позволяющих выяснить

является ли данный многочлен перестановочным или нет.

Определение. Многочлен

][)( xFxf

∈

называется пере-

становочным многочленом поля

F , если соответствующая

ему полиномиальная функция

FFf →:

, отображающая эле-

мент поля

Fc ∈

в элемент

Fcf ∈)(

, является перестановкой

элементов поля

F .

Если

)(

является перестановочным многочленом, то,

очевидно, для каждого элемента

Fa ∈

уравнение

)(

имеет одно решение в поле

F .

Заметим, что операция приведения некоторого многочлена

g(x) по модулю

)(

обозначается

)(mo

)(

и ее результа-

том является остаток

)(

от деления )(

на )(

Тогда можно установить критерий того, что данный мно-

гочлен является перестановочным. Для этого потребуется сле-

дующая лемма.

Лемма. Пусть

110

,...,,

−q

aaa

элементы поля

. Тогда сле-

дующие два условия эквивалентны:

110

,...,,

−q

aaa

все различны;

∑

−

⎩

⎨

⎧

1-qt 1,-

2-q0,1,..., t,0

для

С учетом этой леммы можно получить критерий Эрмита,

того, что данный многочлен является перестановочным.

Критерий Эрмита. Пусть р - характеристика поля

F .

Тогда многочлен

][)( xFxf

∈

является перестановочным мно-

гочленом поля

F в том и только в том случае, если выполня-

ются следующие два условия:

1. Многочлен

)(

имеет ровно один корень в

F .

2. Для каждого целого

t, такого, что

)(mo

0 21 p

иq

≡

−

≤≤

, результат приведения многочлена

xf )(

по модулю

)( xx

−

имеет степень

−

≤

Отсюда вытекает важное

следствие: Если число 0>d

является делителем числа

q -1, то над полем

F не существует

перестановочного многочлена степени

В теории конечного поля имеются и другие критерии того,

что данный многочлен является перестановочным и с ними

можно ознакомится в соответствующей литературе.

Пользуясь критерием Эрмита, можно получить все пере-

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

поля

F .

Примеры перестановочных многочленов можно получить

на основе следующего простого результата.

Теорема:

1. Каждый линейный многочлен над полем

F является

перестановочным многочленом поля

F .

2. Одночлен

является перестановочным многочленом

поля

F тогда и только тогда, когда

11)-q(n,

НОД

(т.е. чис-

ло

n и q -1 взаимно просты).

Например,

- перестановочный многочлен поля

F , ес-

ли

)3(mo

1≡

т.е.

−

Перестановочные многочлены поля

F , имеющие степень

меньшую чем

q, можно комбинировать друг с другом с помо-

щью операции композиции с последующим приведением по мо-

дулю

)( xx

−

. Эту операцию обозначают

>>=<><< )()()(

и под ней понимают

)))(mod(())(( xxxhxgf

−≡

Множество перестановочных многочленов поля

F , сте-

пень которых меньше

q, образуют группу относительно опера-

ции композиции. Эта группа изоморфна симметрической группе

S , т.е. группе всех перестановок на множестве из q элементов.

Таким образом, симметрическую группу

S , перестановок и ее

подгруппы можно представить в виде групп перестановочных

многочленов.

Например:

Теорема. Если q>2, то многочлен

−

вместе с линейны-

ми многочленами над полем

F порождает симметрическую

группу подстановок

S .

Математические элементы теории перестановочных мно-

гочленов над конечными полями и индуцируемых ими групп

подстановок находит применения при построении блочных

криптосистем для перестановки информационных блоков пере-

даваемых сообщений.

Хеш-функции.

Термин хеш-функция (или функция хеширования) возник

в теории сложности вычислений, где он обозначал функцию, ко-

торая сжимает строку чисел произвольного размера в строку чи-

сел фиксированного размера. Это понятие использовалось в ал-

горитмах поиска данных по значениям хеш-функции от них.

Рассмотрим это понятие применительно к криптографии.

Криптографические хеш-функции делятся на два класса:

ключом и без ключа. Значение хеш-функции с ключом может

вычислить лишь тот, кто знает некоторый секретный параметр -

ключ. В литературе она еще называется

МАС - кодами аутенти-

фикации сообщений.

Определение. Хеш-функцией с ключом (зависящей от

ключа) называется функция, имеющая следующие свойства:

1. Описание функции

Н(k,x) должно быть открыто, а сек-

ретная информация должна содержаться только в выборе ключа

k (правило Керкхофа).

2. Аргумент

х функции Н(k,x) может быть строкой чисел

произвольной длины, а значение функции должно быть строкой

чисел фиксированной длины.

3. При любых данных

k и х вычисление Н(k,x) должно

быть быстрым (за полиномиальное время)

4. По любому данному

х должно быть трудно угадать зна-

чение

Н(k,x) с вероятностью большей, чем

, где n - число бит

в выходной строке. Должно быть трудно определить ключ

k да-

же по большему числу известных пар

)},(,{ xkHx

или вычис-

лить по этой информации

Н(k,x’)для x’≠x

Хеш-функция без ключа называется МДС - код определе-

ния манипуляции. Эти функции делятся на два класса:

слабые

односторонние хеш-функции и сильные односторонние хеш-

функции.

Определение. Односторонней слабой хеш-функцией на-

зывается функции

Н(х), удовлетворяющая условием:

1. Аргумент

х функции может быть строкой чисел произ-

вольного размера

2. Значение функции

Н(х) представляет собой строкой

фиксированного размера

3. Значение функции

Н(х) легко вычисляется (за полино-

миальное время)

4. Почти для всех

y вычислительно невозможно найти та-

кое

х что Н(х)=y

5. Для любого фиксированного

х вычислительно невоз-

можно найти другое

x’≠x такое, что

)()'(

. Такое собы-

тие, т.е.

)()'(

называется коллизией.

Свойства 3 и 4 утверждают, что

)(

является односто-

ронней функцией. По свойствам 1 и 2 коллизии должны сущест-

вовать, однако свойство (5) требует, чтобы найти их было вы-

числительно невозможно.

Определение. Односторонней сильной хеш-функцией

)(

является функция, удовлетворяющая свойством 1 - 4 пре-

дыдущего определения, а свойств 5 заменяется следующим.

5. Вычислительно невозможно найти любую пару аргумен-

тов

≠' такую, что

)()'(

. Оба определения предпола-

гают выполнение правила Керкхофа , т.е. описание функции

)(

открыто.

Применение криптографических хеш-функций исключи-

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

ются схемы и алгоритмы цифровой подписи сообщений. Об

этом мы поговорим ниже.

10. Общая характеристика различных типов

шифров и классов криптосистем.

Ранее (на первой лекции) уже сообщалось об основных ти-

пах шифров (шифры замены и перестановки) и классах крипто-

систем (поточные, блочные), используемых в современной

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

Шифры замены. Шифры этого типа делятся на две груп-

пы:

шифры простой замены и шифры сложной или многоал-

фавитной замены, например, система Виженера, шифр Гронс-

фельза. В настоящее время для шифрования используют ЭВМ,

где каждый знак исходного текста представлен двоичным кодом

заданной длины. Самый простой и эффективный шифр замены в

этом случае - это модификация шифра Вернама т.е. когда исход-

ное сообщение в виде последовательности бит смешивается при

помощи операции

XOR (сложение по модулю 2) со случайной

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

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

исходном сообщении, прячется в шуме, т.е. самом информатив-

ном по определению К. Шеннона сигнале. (Песчинку лучше пря-

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

формацию в шуме). Специфика

этого шифра состоит в том, что

процедура шифрования совпадает с процедурой расшифрования.

Если последовательность бит исходного сообщения -

m, случай-

ная последовательность -

, где k - секретный ключ, а шифро-

ванный текст

с, то имеем

;

cm mc

⊕=⊕

Такая обратимость шифра может в ряде случаев быть ис-

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

не прибегая к раскрытию секретного ключа. Например, если ли-

ния связи недозагружена, но в тоже время аппаратура шифрова-

ния не выключается и в канал связи достаточно длительное вре-

мя поступает чистая случайная последовательность

. Если в

это время перехватить шифровку в виде чистого ключа

и на-

ложить на нее свое сообщение, то получатель получит передан-

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

этот текст будет получен в шифрованном виде, то его содержи-

мому могут поверить, что недопустимо. Даже если перехвачен-

ное сообщение не будет чистым ключом

, и будут, конечно,

некоторые искажения ложного шифрования, получатель может

их интерпретировать как помехи в канале связи.

Шифры перестановки.

При применении шифра замены символы исходного сооб-

щения могут превращаться во что угодно, но сохраняют в шиф-

ротексте своё первоначальное положение, т.е. местоположение

символа в исходном тексте такое же, как и в шифрованном тек-

сте. Если теперь к шифротексту применить шифр перестановки,

то местоположение символов в шифротексте может стать произ

вольным по отношению к расположению этих символов в ис-

ходном тексте. Это позволяет существенно увеличить стойкость

шифра. Примерами шифров перестановки являются скиталь, ма-

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

лекции. Перестановка символов текста может осуществляться

двумя способами:

1. Перестановка может делаться до наложения на сообще-

ние случайной последовательности

(т.е. до применения

шифра замены). В этом случае шифрованное сообщение имеет

вид

mpc

+⋅=

, где р - перестановка заданного типа. При та-

ком, способе, если в канале связи отсутствует сообщение, т.е.

m=0, то в канал попадает чистый ключ

2. Перестановка может делаться после наложения на ис-

ходный текст случайной последовательности

В этом случае

)(

mpc

+⋅

и при отсутствии сообще-

ния, т.е. при

m=0, в канал связи поступает ключ

⋅

, подверг-

нутый шифрованию перестановкой.

Перестановка может осуществляться отдельными битами

или такими группами бит, как байт или блок. Временная слож-

ность перестановки оценивается квадратом числа переставляе-

мых элементов. Поэтому перестановка бит будет в 64 раза слож-

нее, чем перестановка байтами. Вычислительных способов пере-

становок существует очень много. Например, широко применя-

ется

перестановка по номерам N от 0 до L-1 на основе рекур-

рентного соотношения

LMkNN

mod)(

где

а)

К и М берутся из интервала (1,L -1)

б)

М - взаимно простое L

в)

К -1 делится на любой простой делитель L

г)

К -1 делится на 4,если L делится на 4.

Для хорошего запутывания такую перестановку делают не-

сколько раз, выбирая каждый раз

K и М случайным образом.

Шифр замены, осложненный перестановкой, обладает дос-

таточно высокой стойкостью. Его вскрытие без знания ключа

неоднозначно, что не позволяет сколько-нибудь уверенно рас-

шифровать сообщение. Существенно повысить стойкость шифра

можно, если вместо перестановки использовать линейное преоб-

разование вида

с=Lm, где L -невырожденная матрица случайно-

го линейного преобразования (или, что тоже самое, детерминант

L не равен нулю). Шифры на основе этого преобразования полу-

чили название

скремблеров или взбивалок.

Шифры взбивания.

Для шифров этого типа характерным является зависимость

каждого бита шифротекста от каждого бита исходного текста.

Детерминант случайной матрицы

L, также как и её элементы

может принимать два значения

0 и 1. Если

0)det(

, матрица

является

вырожденной. Основной проблемой использования

шифра взбивания является стремительное убывание числа невы-

рожденных матриц с увеличением их размера. Для получения

случайных невырожденных матриц специалистами фирмы

IBM

при сознании криптосистемы

Lucifer, ставшей впоследствии

(1976 год) национальным стандартам шифрования США под

именем DEC, был предложен достаточно эффективный способ,

не требующий много вычислений. Суть одного шага этого спо-

соба сводится к следующему:

Входной блок данных делится на две равные части: левую

L и правую

R . После этого формируется выходной массив

так, что его правая часть

R представляется левой частью

исходного массива данных, а левая часть

L формируется как

сумма по модулю 2

⊕

. Далее выходной массив шифруется

перестановкой. Все проведенные операции обратимы и расшиф-

рование осуществляется за число операций, линейно зависящих

от размерности задачи. После нескольких таких шагов взбивания

можно считать, что каждый бит выходного блока шифровки мо-

жет зависеть от каждого бита исходного сообщения. Существен-

ным недостатком шифра взбивания является тот факт,

что с уве-

личением числа шагов взбивания искажение (порча) единствен-

ного бита в шифротексте делает нечитаемым половину текста

при побайтной перестановке. Если перестановку осуществлять

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

текст.

Шифры с открытым ключом.

В традиционных криптографических системах одним и тем

же секретным ключом осуществляется как шифрование, так и

расшифрование сообщений. Это предполагает, что отправитель

и получатель сообщения получают идентичные копии ключа

курьером. Это достаточно дорогостоящий способ и он почти не-

применим для коммерческих фирм и практически недоступен

для частных лиц. В 1976 году Диффи

и Хеллман предложили

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

шить указанную проблему. Эта схема предполагает независимое

генерирование каждым из пары связывающихся пользователей

своего случайного числа, преобразование его посредствам опре-

деленной процедуры (об этом мы более подробно поговорим на

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

крытому каналу связи и

вычисление каждым пользователем об-

щего секретного ключа. Такой секретный ключ существует

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

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

паре абонентов самим выбирать свой общий секретный ключ и

тем самым упрощает процедуру распределения секретных клю-

чей. Вместе с тем, такая схема не устраняет

необходимости ау-

тентификации, т.е. подтверждения того, что, скажем, абонент

получил сообщение именно от абонента

B, а не от какого-либо

нарушителя. Поэтому каждый абонент все же должен иметь свой

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

щий его от всех остальных абонентов. Необходимость в систе-

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

страненные из центра индивидуальные секретные пароли не вы-

глядит столь уже

дорогостоящей задачей как изготовление и

распределение из центра секретных ключей. Во-первых, срок

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

1 год. Кроме того, в некоторых видах связи подтверждение под-

линности партнера может достигаться за счет узнавания его по

физическим признакам (по голосу при телефонной связи, по

внешнему виду и

голосу в системах телевизионной связи и т.д.).

Наряду с этим в системах с открытым ключом в каждом узле

связи (т.е. у каждого абонента) достаточно иметь один секрет-

ный ключ, в то время как в классических криптосистемах в каж-

дом узле находится столько ключей, сколько этот узел имеет

абонентов. В

качестве индивидуального секретного ключа в со-

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

вая подпись, о которой более подробно будем говорить на сле-

дующих лекциях.

Представленное выше рассмотрение различных типов

шифров позволяет сделать ряд выводов.

Крайне желательно, чтобы как можно меньший объем ин-

формации шел по закрытому каналу, требующему больших за-

трат и являющемуся наименее надежным участком системы свя-

зи. Однако совсем обойтись без него нельзя, так как он необхо-

дим для передачи секретных ключей

. Сложность подбора ключа

зависит лишь от объема информации, которую он занимает. Чем

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

Таким образом, существует объективное противоречие

между сокращением информации, передаваемой по секретному

каналу и увеличением информации в секретном ключе, чтобы

повысить сложность его раскрытия. Это ставит серьезную про-

блему поиска оптимального

объема информации содержащегося

в секретном ключе.

Нераскрываемых шифров не существует. Все шифры про-

сто делают процедуру взламывание шифротекстов либо заведо-

мо дороже содержащейся в сообщении информации, либо затя-

гивают время расшифрования до неприемлемых размеров. При

разработки шифров устанавливают требуемые цену или время

взламывания, и затем уже не обращают внимание на очень

бога-

тых или терпеливых взломщиков. Необходимую сложность

ключа вычислить можно, если знать технические возможности

взломщика и плату за ошибку оценки надежности шифра. На-

пример, взломщик вручную не переберет и сотни ключей при

расшифровке ключа, поэтому скажем тысяча вариантов ключа в

этом случае вполне достаточно для его надежной защиты. Это

эквивалентно

информационной длине ключа десять бит (число

вариантов ключа при этом будет

2 =1024) или ключевому сло-

ву из 3 -5 букв. Подводя итоги сказанному, можно сказать, что в

настоящее время в криптографии используют два основных вида

шифров - шифры замены, шифры перестановки и различные их

комбинации. При этом операция шифрования редко применяется

ко всему сообщению в целом. Обычно сообщение разбивается

на большое число фрагментов, называемых блоками,

фиксиро-

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

независимо. Это существенно упрощает процедуру шифрования,

так как сообщение обычно имеют различную длину. Таким об-

разом, можно выделить три основных типа криптосистем ис-

пользуемых в современной криптографии:

поточные, блочные

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

Их основными различиями являются следующие.

1. При

поточном шифровании каждый знак шифротекста

является функцией значения и положения знака открытого тек-

ста. Знаками бывают биты, байты и редко единицы текста круп-

нее этих. Поточные криптосистемы обычно используют шифры

замены.

2. При

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

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

от ключа тип шифра для их преобразования в блоки шифровки

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

взбиванием.

3. Основное отличие криптосистем

с открытым ключом

состоит в том, что знание алгоритма и ключа шифрования не

достаточно для расшифровки сообщения.

Потоковые криптосистемы широко используются в воен-

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

рования данных и преобразованных в цифровую форму речевых

сигналов. Это связано, прежде всего, с относительной простотой

конструирования и реализации

генераторов псевдослучайных,

шифрующих последовательностей на базе теории линейных ре-

куррентных последовательностей над конечными полями и дру-

гих математических дисциплин. Однако главным фактором та-

кого применения поточных криптосистем является отсутствие

размножения ошибок. Так как при передаче данных и речевых

сообщений в стратегической связи используются каналы недос-

таточно высокого качества, то любая криптосистема

, которая

увеличивает и без того нередкие ошибки, неприменима. Кроме

указанных приложений поточные криптосистемы используются

и при передаче данных в локальных и глобальных сетях ЭВМ,

где их непрерывное действие препятствует эффективному крип-

тоанализу.

Главное свойство блочных криптосистем состоит в том,

что каждый бит текста шифровки является функцией почти всех

бит соответствующего блока открытого текста, и никакие два

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

тем же блоком шифротекста. Основное их преимущество состо-

ит в том, что даже небольшие изменения открытого текста

или

ключа вызывают большие и непредсказуемые изменения в шиф-

ротексте. Однако существенным их недостатком является рас-

пространение (размножение) ошибки внутри блока. Результатом

изменения одного бита в принятом блоке будет неправильное

расшифрование всего блока.

Возможно образование комбинированных криптосистем

поточного и блочного типа с использованием лучших свойств

каждой из них. В таких

системах поточное шифрование комби-

нируется с перестановками бит в блоках. Открытый текст снача-

ла шифруется на основе шифра замены, а затем полученный

шифротекст разбивается на блоки фиксированного размера и в

каждом блоке дополнительно реализуется под управлением

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

размножающий ошибки, в котором неизвестно, какому биту

от-

крытого текста соответствует бит шифровки, что существенно

повышает стойкость криптосистемы.

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

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

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

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

вычислить и составить таблицу соответствия блоков открытого

текста блокам шифровки. Если длина

блоков мала, то число воз-

можных блоков будет не слишком большим и может быть со-

ставлена полная таблица, дающая возможность мгновенного

расшифрования любого шифротекста с использованием извест-

ного отрытого ключа. Ни один алгоритм шифрования с откры-

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

скоростью. Это значит, что использование

таких систем для

блочного шифрования ограничено лишь распространением клю-

чей, аутентификацией и формированием цифровой подписи.

Общую характеристику существующих криптосистем

можно представить в виде следующей таблицы

Классы крипто-

систем

Размножение

ошибок

Аутенти-

фикация

Скорость

Поточные нет нет высокая

Блочные есть нет высокая

Системы с от-

крытым ключом

есть есть очень низкая

После характеристики в общем виде различных типов

шифров и классов криптосистем перейдем к непосредственному

рассмотрению алгоритмов криптографии.

11. Методы формирования псевдослучайных

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

распределения ключей Диффи и Хеллмана.

Подавляющее большинство современных криптографиче-

ских систем используют либо поточные, либо блочные алгорит-

мы, базирующиеся на различных типах шифрах замены и пере-

становки. К сожалению, практически все алгоритмы, используе-

мые в поточных криптосистемах, ориентированных на использо-

вание в военных и правительственных системах связи, а также, в

некоторых случаях, для защиты информации коммерческого

ха-

рактера, что вполне естественно делает их секретными и недос-

тупными для ознакомления. Единственными стандартными ал-

горитмами поточного шифрования являются уже упоминавший-

ся на прошлой лекции американский стандарт

DES (режимы

CFB и OFB) и российский стандарт ГОСТ 28147-89 (режим

гаммирования). При этом алгоритмы поточного шифрования,

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

Основу функционирования поточных криптосистем со-

ставляют генераторы случайных или псевдослучайных последо-

вательностей. Рассмотрим этот вопрос более подробно.

Псевдослучайные последовательности чисел для по-

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

Секретные ключи представляют собой основу криптогра-

фических преобразований, для которых согласно правилу Керк-

хоффа, стойкость криптосистемы определяется лишь секретно-

стью ключа. Основной проблемой классической криптографии

долгое время являлась трудность генерации секретного ключа.

Физическое моделирование случайности с помощью таких

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

или дробовой шум в электронной лампе является

довольно

сложным и дорогостоящим и к тому же не дают полностью на-

стоящих случайных процессов. Поэтому вместо физического

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

вания случайности и генерации случайных последовательностей

в виде программ для ЭВМ или специализированных устройств.

100

Эти программы и устройства хотя и называются генераторами

случайных чисел, на самом

деле генерируют детерминирован-

ные последовательности, которые только кажутся случайными

по своим свойствам и поэтому называются псевдослучайными

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

кон формирования, но не зная ключа в виде заданных начальных

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

тельность от случайной, как будто она получена путем бросания

идеальных игровых костей. Можно сформировать три основных

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

стойкие

генераторы псевдослучайных последовательностей

или

гаммы.

1. Период гаммы должен быть достаточно большим для

шифрования сообщений различной длины.

2. Гамма должна быть трудно предсказуемой. Это значит,

что если известны тип генератора и кусок гаммы, то невозможно

предсказать следующий за этим куском бит гаммы или предше-

ствующий этому куску бит гаммы.

3. Генерирование гаммы не должно быть связано с

боль-

шими техническими и организационными трудностями.

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

чисел - это

информационная длина его периода, после которого

числа будут либо просто повторяться, либо их можно будет

предсказать. Эта длина практически определяет возможное чис-

ло ключей криптосистемы. Чем эта длина больше, тем сложнее

подобрать ключ.

Второе из указанных выше требований связано со сле-

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

ние, что гамма конкретного

генератора действительно является

непредсказуемой? Пока в мире нет универсальных и практиче-

ски проверяемых критериев для проверки этого свойства. Ин-

туитивно случайность воспринимается как непредсказуемость.

Чтобы гамма считалась случайной и непредсказуемой как ми-

нимум необходимо, чтобы ее период был очень большим, а раз-

личные комбинации бит определенной длины равномерно рас-

пределялись

по всей ее длине. Это требование статистически