Основы теории принятая статистических решений 1051 77 страница

13.7. Часто слышим такое высказывание, как “картина стоит тысячи слов”. Действительно ли картина стоит тысячи слов (см. раздел 13.8.2)?

ГЛАВА 14

Шифрование и дешифрование

Символы сообщений

От других источников

14.1. Модели, цели и ранние системы шифрования

14.1.1. Модель процесса шифрования и дешифрования

Желание общаться конфиденциально уходит своими корнями в далекое прошлое. Ис­тория секретного общения богата уникальными изобретениями и красочными анекдо­тами [1]. Изучение путей передачи сообщений, которые не допускали бы посторон­него вмешательства, называется криптографией. Термины шифрование и кодирование обозначают преобразования сообщений, выполняемые передатчиком, а термины де­шифрование и декодирование — обратные преобразования, производимые приемником. Основными причинами использования криптосистем в общении являются (1) обеспе­чение конфиденциальности, т.е. предотвращение извлечения информации из канала посторонним лицом (подслушивание); (2) аутентификация, предотвращение внедре­ния в канал информации посторонними людьми (обманный доступ). Часто, как в случае электронной пересылки или договорных переговоров, важно обеспечить элек­тронный эквивалент письменной подписи. Это необходимо для того, чтобы устранить какие-либо недоразумения между отправителем и получателем относительного того, какое сообщение было отправлено и было ли оно вообще отправлено.

На рис. 14.1 изображена модель криптографического канала. Сообщение, или от­крытый текст М, шифруется с помощью обратимого преобразования Е_к, дающего шифрованный текст С = Е^М). Шифрованный текст пропускается через незащищен­ный, или общедоступный канал. После получения шифрованного сообщения С, его исходное значение восстанавливается с помощью операции дешифрования, описы­ваемой обратным преобразованием D_k = Е^¹, что выглядит следующим образом:

D_k(C) = E;'[E_k(M)]=M. (14.1)

Криптоаналитик

т

Рис. 14.1. Модель криптографического канала

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

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

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

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

14.1.2. Задачи системы шифрования

Основные требования к системе шифрования можно сформулировать следующим образом.

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

2. Задачу криптоаналитика по производству оценки нешифрованного текста без помощи ключа сделать максимально сложной и дорогой.

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

14.1.3. Классические угрозы

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

Более серьезной угрозой для системы является атака известного открытого текста (known plaintext attack). Она включает в себя знание открытого текста и его шифрованного эквивалента. Жесткая структура большинства бизнес-форм и языков программирования часто дает оппоненту множество априорных знаний об элементах открытого сообщения. Вооруженный этим знанием и шифрованным сообщением, криптоаналитик может прово­дить криптоанализ с помощью известного открытого текста. Рассмотрим пример из облас­ти дипломатии: если шифрованное сообщение обязывает министра иностранных дел сде­лать определенное публичное заявление и он делает это, не перефразируя сообщение, криптоаналитик может получить как шифрованный текст, так и его точный перевод в от­крытую версию. Несмотря на то что атака известного открытого текста не всегда возмож­на, она используется достаточно часто, чтобы система не считалась защищенной, если она не проектировалась для противостояния такому типу атак [2].

Если криптоаналитик должен выбирать открытый текст для данного шифрован­ного сообщения, угроза называется атакой выбранного открытого текста (chosen plaintext attack). Во время Второй мировой войны такая атака использовалась Соеди­ненными Штатами Америки для получения большей информации о японской крип­тосистеме. 20 мая 1942 года главнокомандующий Императорским Морским флотом адмирал Ямамото (Yamamoto) издал указ, детально излагающий тактику, которая должна была быть использована при атаке на острове Мидуэй. Этот указ был перехва­чен подслушивающими постами союзников. К тому времени американцы узнали дос­таточно о японских кодах, чтобы дешифровать большинство сообщений. Однако все еще под сомнением были некоторые важные моменты, такие как место атаки. Они подозревали, что символы “AF” обозначали остров Мидуэй, но для того, чтобы убе­диться, Джозеф Рошфор (Joseph Rochefort), глава военной разведки, решил использо­вать метод атаки выбранного открытого текста, чтобы обманным путем вынудить

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

14.1.4. Классические шифры

Одним из ранних примеров моноалфавитного шифра был шифр Цезаря, который ис­пользовался Юлием Цезарем во времена его Галльских походов. Каждая буква исход­ного текста заменяется новой, полученной путем сдвига алфавита. На рис. 14.2, а изображено такое шифрующее преобразование, состоящее из трех циклических сдвигов алфавита. Если использовать этот алфавит Цезаря, сообщение “now is the time” (“время пришло!”) шифруется следующим образом.

Открытый текст: ABCDEFGH I JKLMNOPQRSTUVWXYZ Шифрованный текст. DEFGHI JKLMNOPQRSTUVWXYZABC

а)

	А	В	С	D	Е
	F	G	н	IJ	К
	L	М	N	О	Р
	Q	R	S	Т	и
	V	W	X	Y	Z

б)

Рис. 14.2 Примеры шифров: а) алфавит Цезаря со сдвигом 3; б) квадрат Полибиуса

Исходный текст: NOWI STHETI ME Шифрованный QRZLVWKHWLPH текст:

Дешифрующий ключ — это просто число сдвигов алфавита; с выбором нового ключа код изменяется. Еще одна классическая система шифрования, изображенная на рис. 14.2, б, называется квадратом Полибиуса (Polybius square). Вначале объединяются буквы I и J и трактуются как один символ (в дешифрованном сообщении значение этой “двойной буквы” легко определяется из контекста). Получившиеся 25 символов алфавита размещаются в таблицу размером 5x5. Шифрование любой буквы произво­дится с помощью выбора соответствующей пары чисел — строки и столбца (или столбца и строки). Ниже приведен пример шифрования того же сообщения “now is the time” с помощью квадрата Полибиуса.

Исходный текст: NOWI STHETI ME Шифрованный 33 43 25 42 34 44 32 51 44 42 23 51 текст:

Код изменяется путем перестановки букв в таблице 5x5.

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

1 символ, второго символа — из строки, полученной при сдвиге на 2 символа, и т.д. Ниже приведен пример сообщения, зашифрованного подобным образом.

Открытый

текст:

а

b

С

d

е

f

д

h

i

j

к

ш

П

о

Р

Я

г

S

t

и

V

W

X

У

Сдвиг: о

А

В

С

D

Е

F

G

Н

J

К

L

м

N

О

Р

Q

R

S

Т

и

V

W

X

Y

Z

В

С

D

Е

F

G

Н

J

К

L

М

N

О

Р

О

R

S

т

и

V

W

X

Y

Z

А

С

D

Е

F

G

Н

J

К

L

М

N

О

Р

О

R

S

Т

и

V

W

X

Y

Z

А

В

D

Е

F

G

Н

J

К

L

М

N

О

Р

Q

R

S

Т

и

V

W

X

Y

г

А

В

с

В

F

G

Н

J

К

L

М

N

О

Р

Q

R

S

Т

и

V

W

X

Y

Z

А

В

с

D

F

G

Н

J

К

L

М

N

О

Р

Q

R

S

т

и

V

W

X

Y

Z

А

в

С

D

Е

G

Н

J

К

L

М

N

О

Р

Q

R

S

Т

и

V

W

X

Y

Z

А

В

с

D

Е

F

Н

J

К

L

М

N

О

Р

Q

R

S

Т

и

V

W

X

Y

Z

А

В

С

D

Е

F

G

J

К

L

М

N

О

Р

Q

R

S

Т

и

V

W

X

Y

Z

А

В

с

Е

F

G

Н

J

К

L

М

N

О

Р

Q

R

S

Т

и

V

W

X

Y

Z

А

В

С

D

Е

F

G

Н

К

L

М

N

О

Р

Q

R

S

Т

и

V

W

X

Y

Z

А

В

с

D

Е

F

G

Н

J

L

М

N

О

Р

Q

R

S

Т

и

V

W

X

Y

Z

А

В

С

Е

F

G

Н

J

К

М

N

О

Р

Q

R

S

Т

и

V

W

X

Y

Z

А

В

С

Е

F

G

Н

J

К

L

N

О

Р

Q

R

S

Т

и

V

W

X

Y

Z

А

В

С

Е

F

G

Н

J

К

L

М

О

Р

Q

R

S

Т

и

V

W

X

Y

Z

А

В

С

D

Е

F

G

Н

J

К

L

М

N

Р

Q

R

S

Т

и

V

W

X

Y

Z

А

В

с

Е

F

G

Н

J

К

L

М

N

О

Q

R

S

Т

и

V

W

X

Y

г

А

В

С

Е

F

G

Н

J

К

L

М

N

О

Р

R

S

Т

и

V

W

X

Y

г

А

В

С

О

Е

F

G

Н

J

К

L

М

N

О

Р

Q

S

Т

и

V

W

X

Y

Z

А

В

С

D

Е

F

G

Н

J

К

L

М

N

О

Р

Q

R

Т

и

V

W

X

Y

Z

А

в

С

Е

F

G

Н

J

К

L

М

N

О

Р

Q

R

S

и

V

W

X

Y

Z

А

В

с

D

Е

F

G

Н

J

К

L

М

N

О

Р

Q

R

S

т

г\

V

W

X

Y

г

А

В

С

D

Е

F

G

Н

J

К

L

М

N

О

Р

Q

R

S

Т

и

W

X

Y

Z

А

В

с

D

Е

F

G

Н

J

К

L

М

N

О

Р

Q

R

S

Т

и

V

X

Y

Z

А

в

С

D

Е

F

G

Н

J

К

L

М

N

О

Р

Q

R

S

т

и

V

W

Y

Z

А

В

с

D

Е

F

G

Н

J

К

L

М

N

О

Р

Q

R

S

Т

и

V

W

X

Z

А

В

С

D

Е

F

G

Н

J

К

L

М

N

О

Р

Q

R

S

Т

и

V

W

X

Y

Рис. 14.3. Прогрессивный ключ Тритемиуса

Исходный текст: NOWI STHETI ME Шифрованный OQZMXZOMCS XQ текст:

Существует несколько интересных способов использования прогрессивного шифра Тритемиуса. В одном из них, называемом методом ключа Вигнера (Vigener key method), применяется ключевое слово (keyword). Этот ключ диктует выбор строк для шифрования и дешифрования каждого последующего символа в сообщении. Предпо­ложим, что в качестве ключа выбрано слово “TYPE”; тогда сообщение, зашифрован­ное с применением метода Вигнера, выглядит следующим образом.

Ключ:

Т

Y

Р

Е

Т

Y

Р

Е

Т

Y

Р

Е

Исходный текст:

N

О

W

I

S

Т

Н

Е

т

I

М

Е

Шифрованный

G

М

L

М

L

R

W

I

м

G

В

I

текст:

Здесь первая буква ключа (Т) указывает, что в качестве'строки для шифрования первой бу­квы открытого текста выбирается строка, начинающаяся с Т (сдвиг 19). Следующей выби­рается строка, начинающаяся с Y (сдвиг 24), и т. д. Разновидностью этого метода является так называемый метод автоматического (явного) ключа Вигнера (Vigener auto (plain) key method), когда в качестве образующего ключа используется единственная буква или слою. Этот ключ дает начальную строку или строки для шифрования первого или нескольких первых символов открытого текста аналогично предыдущему примеру. Затем в качестве ключа для выбора шифрующей строки используются символы исходного текста. В приве­денном ниже примере в качестве образующего ключа использована буква “F”.

Ключ:

F

N

О

W

I

S

Т

Н

Е

Т

I

м

Исходный текст:

N

О

W

I

S

т

Н

Е

Т

I

М

Е

Шифрованный

S

В

к

Е

А

L

А

L

X

В

и

Q

текст:

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

Последняя разновидность метода Вигнера — это метод автоматического (шифрованного) ключа Вигнера (Vigenere auto (cipher) key method), подобный простому методу ключа; в нем также используются образующий ключ и обратная связь. Отли­чие состоит в том, что после шифрования с помощью образующего ключа, каждый последующий символ ключа в последовательности берется не из символа исходного текста, а из символа шифрованного текста. Ниже приведен пример, который должен помочь понять принцип работы данного метода; как и ранее, в качестве начального ключа используется буква “F”.

Ключ:

F

S

G

С

К

С

V

с

G

Z

н

т

Исходный текст:

N

О

W

I

S

т

н

Е

Т

I

м

Е

Шифрованный

S

G

С

К

С

V

С

G

Z

н

т

X

текст:

Хотя каждый символ ключа может быть найден из предшествующего ему символа шифрованного текста, функционально он зависит от всех предшествующих символов в сообщении и плюс основного ключа. Таким образом, имеется эффект рассеивания статистических свойств исходного текста вдоль шифрованного текста, что делает ста­тистический анализ очень сложным для криптоаналитика. Слабым звеном описанного здесь примера шифрования с использованием ключа является то, что шифрованный текст содержит знаки ключа, которые будут публично выставлены через общедоступ­ный канал “на всеобщее обозрение”. Для того чтобы предотвратить такое публичное разоблачение, можно использовать вариации этого метода [3]. По нынешним стандар­там схема шифрования Вигнера не является очень защищенной; основным вкладом Вигнера было открытие того, что неповторяющиеся ключевые последовательности можно создавать с использованием самих сообщений или функций от сообщений.

14.2. Секретность системы шифрования

14.2.1. Совершенная секретность

Рассмотрим систему шифрования с конечной областью сообщений {М} = М₀, М_и..., M_N_i и конечной областью шифрованных текстов {С} = С₀, С_и..., Q/_i. Для любого М,
априорная вероятность передачи сообщения M_t равна Р(М,). Апостериорная вероят­ность принятия сообщения С, при переданном сообщении М, равна Р(ЩС£. Говорят, что система шифрования имеет совершенную секретность, если для любого сообщения Mj и любого шифрованного текста С, апостериорная вероятность равна априорной.

Дата добавления: 2015-10-28