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

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

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

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

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

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

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

14.2.2. Энтропия и неопределенность

14.2.3. Интенсивность и избыточность языка

14.2.4. Расстояние единственности и идеальная секретность

14.3. Практическая защищенность

14.3.1. Смешение и диффузия

14.3.2. Подстановка

14.3.3. Перестановка

14.3.4. Продукционный шифр

14.3.5. Стандарт шифрования данных

14.3.5.1. Выбор ключа

14.4. Поточное шифрование

14.4.1. Пример генерирования ключа с использованием линейного регистра сдвига с обратной связью

14.4.2. Слабые места линейных регистров сдвига с обратной связью

14.4.3. Синхронные и самосинхронизирующиеся системы поточного шифрования

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

14.5.1. Проверка подлинности подписи с использованием криптосистемы с открытым ключом

14.5.2. Односторонняя функция с «лазейкой»

14.5.3. Схема RSA

14.5.3.1. Использование схемы RSA

14.5.3.2. Как вычислить е

14.5.4. Задача о рюкзаке

14.5.5. Криптосистема с открытым ключом, основанная на «лазейке» в рюкзаке

14.5.5.1. Использование схемы Меркла-Хэллмана

14.6. Pretty Good Privacy

14.6.1. «Тройной» DES, CAST и IDEA

14.6.1.1. Описание "тройного" DES

14.6.1.2. Описание CAST

14.6.1.3. Описание IDEA

14.6.2. Алгоритмы Диффи-Хэллмана (вариант Элгемала) и RSA

14.6.2.1. Описание алгоритма Диффи-Хэллмана, вариант Элгемала

14.6.3. Шифрование сообщения в системе PGP

14.6.4. Аутентификация с помощью PGP и создание подписи

14.6.4.1. МD5 и SНА-1

14.6.4.2. Стандарт цифровой подписи и алгоритм RSA

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

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

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

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

(14.1)

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

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

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

В общем случае схема шифрования существенно отличается от схемы канального кодирования. Например, при шифровании данные открытого текста не должны явно фигурировать в шифрованном тексте, а при канальном кодировании в систематической форме коды часто содержат неизмененные биты сообщения плюс биты четности (см. раздел 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), глава военной разведки, решил использовать метод атаки выбранного открытого текста, чтобы обманным путем вынудить японцев дать конкретное доказательство. По его приказу гарнизон острова Мидэуй выдал в эфир характерное открытое сообщение, в котором остров Мидуэй сообщал, что его завод по очистке воды вышел из строя. Американским криптоаналитикам пришлось подождать всего два дня, после чего они перехватили японское шифрованное сообщение, в котором говорилось, что на AF не хватает чистой воды [1].

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

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

открытый текст

A

B

C

D

E

F

G

H

I

J

K

L

M

N

O

P

Q

R

S

T

U

V

W

X

Y

Z

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

D

E

F

G

H

I

J

K

L

M

N

O

P

Q

R

S

T

U

V

W

X

Y

Z

A

B

C

а)

	1	2	3	4	5
1	A	B	C	D	E
2	F	G	H	IJ	K
3	L	M	N	O	P
4	Q	R	S	T	U
5	V	W	X	Y	Z

б)

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

Исходный текст: N O W I S T H E T I M E

Шифрованный Q R Z L V W K H W L P H

текст:

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

Исходный текст: N O W I S Т Н Е Т I M E

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

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

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

открытый текст

a

b

c

d

e

f

g

h

i

j

k

l

m

n

o

p

q

r

t

u

v

w

x

y

z

сдвиг

0

A

B

C

D

E

F

G

H

I

J

K

L

M

N

O

P

Q

R

S

T

U

V

W

X

Y

Z

1

B

C

D

E

F

G

H

I

J

K

L

M

N

O

P

Q

R

S

T

U

V

W

X

Y

Z

A

2

C

D

E

F

G

H

I

J

K

L

M

N

O

P

Q

R

S

T

U

V

W

X

Y

Z

A

B

3

D

E

F

G

H

I

J

K

L

M

N

O

P

Q

R

S

T

U

V

W

X

Y

Z

A

B

C

4

E

F

G

H

I

J

K

L

M

N

O

P

Q

R

S

T

U

V

W

X

Y

Z

A

B

C

D

5

F

G

H

I

J

K

L

M

N

O

P

Q

R

S

T

U

V

W

X

Y

Z

A

B

C

D

E

6

G

H

I

J

K

L

M

N

O

P

Q

R

S

T

U

V

W

X

Y

Z

A

B

C

D

E

F

7

H

I

J

K

L

M

N

O

P

Q

R

S

T

U

V

W

X

Y

Z

A

B

C

D

E

F

G

8

I

J

K

L

M

N

O

P

Q

R

S

T

U

V

W

X

Y

Z

A

B

C

D

E

F

G

H

9

J

K

L

M

N

O

P

Q

R

S

T

U

V

W

X

Y

Z

A

B

C

D

E

F

G

H

I

10

K

L

M

N

O

P

Q

R

S

T

U

V

W

X

Y

Z

A

B

C

D

E

F

G

H

I

J

11

L

M

N

O

P

Q

R

S

T

U

V

W

X

Y

Z

A

B

C

D

E

F

G

H

I

J

K

12

M

N

O

P

Q

R

S

T

U

V

W

X

Y

Z

A

B

C

D

E

F

G

H

I

J

K

L

13

N

O

P

Q

R

S

T

U

V

W

X

Y

Z

A

B

C

D

E

F

G

H

I

J

K

L

M

14

O

P

Q

R

S

T

U

V

W

X

Y

Z

A

B

C

D

E

F

G

H

I

J

K

L

M

N

15

P

Q

R

S

T

U

V

W

X

Y

Z

A

B

C

D

E

F

G

H

I

J

K

L

M

N

O

16

Q

R

S

T

U

V

W

X

Y

Z

A

B

C

D

E

F

G

H

I

J

K

L

M

N

O

P

17

R

S

T

U

V

W

X

Y

Z

A

B

C

D

E

F

G

H

I

J

K

L

M

N

O

P

Q

18

S

T

U

V

W

X

Y

Z

A

B

C

D

E

F

G

H

I

J

K

L

M

N

O

P

Q

R

19

T

U

V

W

X

Y

Z

A

B

C

D

E

F

G

H

I

J

K

L

M

N

O

P

Q

R

S

20

U

V

W

X

Y

Z

A

B

C

D

E

F

G

H

I

J

K

L

M

N

O

P

Q

R

S

T

21

V

W

X

Y

Z

A

B

C

D

E

F

G

H

I

J

K

L

M

N

O

P

Q

R

S

T

U

22

W

X

Y

Z

A

B

C

D

E

F

G

H

I

J

K

L

M

N

O

P

Q

R

S

T

U

V

23

X

Y

Z

A

B

C

D

E

F

G

H

I

J

K

L

M

N

O

P

Q

R

S

T

U

V

W

24

Y

Z

A

B

C

D

E

F

G

H

I

J

K

L

M

N

O

P

Q

R

S

T

U

V

W

X

25

Z

A

B

C

D

E

F

G

H

I

J

K

L

M

N

O

P

Q

R

S

T

U

V

W

X

Y

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

Исходный текст: N O W I S Т Н Е Т I M E Шифрованный текст: O Q Z M X Z O M C S X Q

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

Ключ: T Y P E T Y P E T Y P E

Исходный текст: N O W I S T H E T I M E

Шифрованный G M L M L R W I M G B I текст:

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

Ключ: F N O W I S T H E T I М

Исходный текст: N O W I S T H E T I M E

Шифрованный S B K E A L A L X B U Q

текст:

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

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

Ключ: F S G C K C V C G Z H T

Исходный текст: N O W I S T H E T I M E

Шифрованный S G C K C V C G Z H T X текст:

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

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

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

Рассмотрим систему шифрования с конечной областью сообщений {М}= М0, М1 ..., MN-1 и конечной областью шифрованных текстов {С} = С0, С1 ..., CU-1,. Для любого Мi априорная вероятность передачи сообщения Мi, равна Р(Мi). Апостериорная вероятность принятия сообщения Cj при переданном сообщении М, равна P(Мi/Cj). Говорят, что система шифрования имеет совершенную секретность, если для любого сообщения Mi и любого шифрованного текста Cj апостериорная вероятность равна априорной.

(14.2)

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

(14.3)

На рис. 14.4 изображен пример схемы совершенной секретности. В этом примере {М}=М0, М1, М2, М3; {С} = С0, С1,С2, С3; {К} =K0, K1 K2,K3 ;N=U=4, Р(Мi)=Р(Сj) =1/4.

Преобразование сообщения в шифрованный текст выполняется следующим образом.

(14.4)

Рис.14.4. Совершенная секретность.

Здесь ТKj определяет преобразование с помощью ключа Kj, а «х по модулю y»— это остаток от деления х на y. Таким образом, s= 0, 1, 2, 3. Криптоаналитик, перехвативший одно из шифрованных сообщений Cs =С1, С1,С2или С3, не сможет определить, какой из четырех ключей использовался и, следовательно, какое из сообщений М0, М1, М2или М3является верным. Если в системе шифрования число сообщений, число ключей и число шифрованных сообщений равны между собой, то система имеет совершенную секретность тогда и только тогда, когда выполняются следующие два условия.

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

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

Если эти условия не выполняются, то будет существовать некоторое сообщение Мi , при котором для данного Сj, не существует ключа, который мог бы дешифровать Сj в Мi. Отсюда следует, что для некоторых i и j Р(Мi/Сj)=0. В этом случае криптоаналитик может исключить из рассмотрения определенные нешифрованные сообщения, упростив, таким образом, задачу. Вообще, совершенная секретность является очень желательным свойством, поскольку это означает, что система шифрования безусловно защищена. Должно быть очевидно, что в системах, передающих большое количество сообщений, для достижения совершенной секретности требуется распределить большое количество ключей, а это, в свою очередь, может привести к значительным практическим затруднениям, что делает такие системы нереализуемыми. В системе с совершенной секретностью число возможных ключей так же велико, как и число возможных сообщений, поэтому, если мы разрешим передавать сообщения неограниченной длины, совершенная секретность потребует бесконечного количества ключей.

Пример 14.1. Взлом системы шифрования, если область ключей меньше области сообщений

Рассмотрим шифрованный текст, состоящий из 29 символов.

G R O В О К В О D R O R O В Y O C Y P I O C D O B I O K B

Данный текст был получен с помощью шифра Цезаря (см. раздел 14.1.4); каждая буква получена сдвигом на K символов, где 1К25. Покажите, как криптоаналитик может взломать этот код.

Решение

Поскольку количество возможных ключей (их 25) меньше количества возможных осмысленных сообщений из 29 символов (их огромное множество), совершенная секретность не может быть достигнута. В исходном полиалфавитном шифре, показанном на рис. 14.3, символ открытого текста заменяется буквой некоторой строки, причем номер строки постоянно возрастает. Следовательно, в процессе анализа шифрованного текста мы обращаем процесс: теперь буквы шифрованного текста заменяются буквами строк, причем номер строки постоянно уменьшается. Путем перебора всех ключей от 1 до 25 (рис. 14.5) можно легко рассмотреть все возможности. В результате, этот процесс приводит к единственному ключу (K=10), дающему осмысленное сообщение (пробелы были добавлены вручную): WHERE ARE THE HEROES OF YESTERYEAR.

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

Для создания шифра, имеющего совершенную секретность, можно несколько модифицировать область ключей, описанную в примере 14.1. В этой новой системе шифрования каждый символ сообщения шифруется с использованием случайно выбранного ключевого значения. Теперь ключ K задается последовательностью k1, k2, ..., k29, где каждое ki— это случайно выбранное целое число из интервала (1,25), определяющее сдвиг, используемый для i-го символа. Таким образом, всего существует (25)²⁹ различных ключевых последовательностей. Значит, шифрованный текст из 29 символов, приведенный в примере 14.1, может соответствовать любому осмысленному сообщению из 29 символов. Например, шифрованный текст мог соответствовать следующему открытому тексту (пробелы были добавлены вручную).

ENGLISH AND FRENCH ARE SPOKEN HERE

Данный текст получен с помощью ключа 2, 4, 8, 16, 6, 18, 20, ... . Стоит отметить, что большинство возможных наборов из 29 символов можно исключить, поскольку они не являются осмысленными сообщениями. Совершенная секретность данного кода – результат того, что перехват шифрованного текста не дает никакой дополнительной информации об открытом сообщении.

Ключ Текст

0

G

R

O

B

O

K

B

O

D

R

O

R

O

B

Y

O

C

Y

P

I

O

C

D

O

B

I

O

K

B

1

F

Q

N

A

N

J

A

N

C

Q

N

Q

N

A

X

N

B

X

O

H

N

B

C

N

A

H

N

J

A

2

E

P

M

Z

M

I

Z

M

B

P

M

P

M

Z

W

M

A

W

N

G

M

A

B

M

Z

G

M

I

Z

3

D

O

L

Y

L

H

Y

L

O

A

L

O

L

Y

V

L

Z

V

M

F

L

Z

A

L

Y

F

L

H

Y

4

C

N

K

X

K

G

X

K

Z

N

K

N

K

X

U

K

Y

U

L

E

K

Y

Z

K

X

E

K

G

X

5

B

M

J

M

J

F

W

J

Y

M

J

M

J

W

T

J

X

T

K

D

J

X

Y

J

W

D

J

F

W

6

A

L

I

V

I

E

V

I

X

L

I

L

I

V

S

I

W

S

J

C

I

W

X

I

V

C

I

E

V

7

Z

K

H

U

H

D

U

H

W

K

H

K

H

U

R

H

V

R

I

B

H

V

W

H

U

B

H

D

U

8

Y

J

G

T

G

C

T

G

V

J

G

J

G

T

Q

G

U

Q

H

A

G

U

V

G

T

A

G

C

T

9

X

I

F

S

F

B

S

F

U

I

F

I

F

S

P

F

T

P

G

Z

F

T

U

F

S

Z

F

B

S

10

W

H

E

R

E

A

R

E

T

H

E

H

E

R

O

E

S

O

F

Y

E

S

T

E

R

Y

E

A

R

11

V

G

D

Q

D

Z

Q

D

S

G

D

G

D

Q

N

D

R

N

E

X

D

R

S

D

Q

X

D

Z

Q

12

U

F

C

P

C

Y

P

C

R

F

C

F

C

P

M

C

Q

M

D

W

C

Q

R

C

P

W

C

Y

P

13

T

E

B

O

B

X

O

B

Q

E

B

E

B

O

L

B

P

L

C

V

B

P

Q

B

O

V

B

X

O

14

S

D

A

N

A

W

N

A

P

D

A

D

A

N

K

A

O

K

B

U

A

O

P

A

N

U

A

W

N

15

R

C

Z

M

Z

V

M

Z

O

C

Z

C

Z

M

J

Z

N

J

A

T

Z

N

O

Z

M

T

Z

V

M

16

Q

B

Y

L

Y

U

L

Y

N

B

Y

B

Y

L

I

Y

M

I

Z

S

Y

M

N

Y

L

S

Y

U

L

17

P

A

X

K

X

T

K

X

M

A

X

A

X

K

H

X

L

H

Y

R

X

L

M

X

K

R

X

T

K

18

O

Z

W

J

W

S

J

W

L

Z

W

Z

W

J

G

W

K

G

X

Q

W

K

L

W

J

Q

W

S

J

19

N

Y

U

H

U

Q

H

U

J

X

U

X

U

H

E

U

I

E

V

O

U

I

J

U

H

O

U

Q

H

20

M

X

U

H

U

Q

H

U

J

X

U

X

U

H

E

U

I

E

V

O

U

I

J

U

H

O

U

Q

H

21

L

W

T

G

T

P

G

T

I

W

T

W

T

G

D

T

H

D

U

N

T

H

I

T

G

N

T

P

G

22

K

V

S

F

S

O

F

S

H

V

S

V

S

F

C

S

G

C

T

M

S

G

H

S

F

M

S

O

F

23

J

U

R

E

R

N

E

R

G

U

R

U

R

E

B

R

F

B

S

L

R

F

G

R

E

L

R

N

E

24

I

T

Q

D

Q

M

D

Q

F

T

Q

T

Q

D

A

Q

E

A

R

K

Q

E

F

Q

D

K

Q

M

D

25

H

S

P

C

P

L

C

P

E

S

P

S

P

C

Z

P

D

Z

Q

J

P

D

E

P

C

J

P

L

C

Рис. 14.5. Пример взлома системы шифрования, если область ключей меньше области сообщений

14.2.2. Энтропия и неопределенность

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

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

(14.5)

Если, как выше, логарифм берется по основанию 2, Н(Х) представляет собой математическое ожидание числа битов в оптимально закодированном сообщении X. Это все еще не та мера, которую хотел бы иметь криптоаналитик. Им будут перехвачены некоторые шифрованные тексты, и он захочет узнать, насколько достоверно он может предсказать сообщение (или ключ) при условии, что был отправлен именно этот конкретный шифрованный текст. Неопределенность, определенная как условная энтропия X при данном Y, является для криптоаналитика более полезной мерой при попытке взлома шифра. Она задается с помощью следующей формулы.

(14.6)

Неопределенность может рассматриваться как неуверенность в том, что отправлено было сообщение X, при условии получения Y. Желательным для криптоаналитика является приближение H(X|Y) к нулю при увеличении объема перехваченного шифрованного текста Y.

Пример 14.3. Энтропия и неопределенность

Рассмотрим выборочное множество сообщений, состоящее из восьми равновероятных сообщений {X} = Х1, Х2, ... Х8.

а) Найдите энтропию, связанную с сообщением из множества {X}.

б) Дано другое множество равновероятных сообщений {Y}=Y1, Y2. Пусть появление каждого сообщения Y сужает возможный выбор X следующим образом.

При наличии Y1 возможны только Х1, Х2, Х3или Х4

При наличии У2 возможны только Х5, Х6, Х7 или Х8

Найдите неопределенность сообщения X, обусловленную сообщением Y.

Решение

а) Р(Х)=

Н(Х) = = 3 бит/сообщение

б) Р(Y)=. Для каждого Y, P(X|Y)=для четырех сообщений из множества {X} и P(X|Y)=0 для оставшихся четырех. Используя уравнение (14.6), получим следующее.

H(X|Y)== 2 бит/сообщение

Видно, что знание Y сводит неопределенность X с 3 бит/сообщение до 2 бит/сообщение.

14.2.3. Интенсивность и избыточность языка

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

(14.7)

Здесь Н(Х) — энтропия сообщения, или число битов в оптимально закодированном сообщении. Для письменного английского языка при больших N оценки r дают значения между 1,0 и 1,5 бит/символ [4]. Абсолютная интенсивность или максимальная энтропия языка определяется как максимальное число информационных битов, содержащихся в каждом символе, в предположении, что все возможные последовательности символов одинаково вероятны. Абсолютная интенсивность задается следующим образом.

r' = log2L (14.8)

Здесь L - число знаков в языке. Для английского алфавита r'=log226 = =4,7 бит/символ. Истинная интенсивность английского языка, конечно, гораздо меньше его абсолютной интенсивности, поскольку, как и большинство языков, английский очень избыточен и структурирован.

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

D = r '- r (14.9)

Для английского языка, где r'=4,7 бит/символ и r=1,5 бит/символ, D= 3,2, а отношение D/r'= 0,68 - это мера избыточности языка.

14.2.4. Расстояние единственности и идеальная секретность

Ранее утверждалось, что если допускаются сообщения неограниченной длины, то совершенная секретность требует бесконечного количества ключей. При конечном размере ключа его неопределенность Н(К|С) обычно приближается к нулю, откуда следует, что ключ может быть определен единственным образом, а система шифрования может быть взломана. Расстояние единственности (unicity distance) определяется как наименьшая длина шифрованного текста N, при которой неопределенность ключа Н(К|С) близка к нулю. Следовательно, расстояние единственности — это количество шифрованного текста, необходимое для того, чтобы однозначно определить ключ и таким образом взломать систему шифрования. Шеннон (Shennon) [5] описал систему с идеальной секретностью как систему, в которой Н(К|С) не стремится к нулю, если количество шифрованного текста стремится к бесконечности. Иными словами, ключ не может быть определен, независимо от того, сколько шифрованного текста перехвачено. Термин «идеальная секретность» описывает систему, которая не достигает совершенной секретности, но, тем не менее, не поддается взлому (безусловно защищенная система), поскольку она не дает достаточно информации для определения ключа.

Большинство систем шифрования слишком сложны для определения вероятностей, необходимых для вычисления расстояния единственности. В то же время расстояние единственности иногда можно аппроксимировать, что было показано Шенноном [5] и Хэллманом (Hellman) [6]. Следуя Хэллману, предположим, что каждый открытый текст и шифрованное сообщение получены с помощью конечного алфавита из L символов. Таким образом, всего существует 2^r’N возможных сообщений длиной N, где r’ — абсолютная интенсивность языка. Всю область сообщений можно разделить на два класса - осмысленные сообщения M1 и бессмысленные сообщения М2. Тогда имеем

число осмысленных сообщений 2^r’N (14.10)

число бессмысленных сообщений 2^r’N - 2^rN, (14.11)

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

M1 – осмысленное (14.12)

Р(М2) = 0 М2 – бессмысленное (14.13)

Предположим, что существует 2^H(K) возможных ключа (размер алфавита ключей), где H(К) — энтропия ключа (бит в ключе). Предположим, что все ключи равновероятны.

Р(К) == 2^-Н(К) (14.14)

Определение расстояния единственности основано на модели случайного шифра, которая утверждает, что для каждого ключа К и шифрованного текста С операция дешифрования DK(С) дает независимую случайную переменную, распределенную по всем возможным 2^r’N сообщениям (как осмысленным, так и бессмысленным). Следовательно, для данных К и С операция DK(С) может с равной вероятностью давать любое из открытых сообщений.

При данном шифровании, описываемом как Сi=EKi(Mi), неверное решение F возникает всегда, когда шифрование с помощью другого ключа Kj может давать Сi из того же сообщения Mi или из некоторого другого сообщения Мj.

Ci=EKi(Mi) = EKj(Mi) = EKj(Mj) (14.15)

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

Для каждого верного решения конкретного шифрованного текста существует 2^H(K)-1 неверных ключа, каждый из которых имеет ту же вероятность P(F) получения неверного решения. Так как все осмысленные открытые сообщения предполагаются равновероятными, вероятность неверного решения равна вероятности получения осмысленного сообщения.

P(F)== 2^(r-r’) = 2 ^-DN (14.16)

Здесь D =r’-r — избыточность языка. Тогда ожидаемое число неверных решений F равно следующему.

(14.17)

Поскольку F быстро убывает с увеличением N, то

log2 = H(K)-DN= 0 (14.18)

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

N= (14.19)

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

Стоит отметить, что доминирование бессмысленных дешифровок позволяет взламывать криптограммы. Уравнение (14.19) показывает значение использования сжатия данных до шифрования. Сжатие данных устраняет избыточность языка, таким образом, увеличивая расстояние единственности. Совершенное сжатие данных даст D = 0 и N =для любого размера ключа.

Пример 14.4. Расстояние единственности

Вычислите расстояние единственности для системы шифрования, использующей письменный английский язык, ключ которой задается последовательностью k1, k2,..., k29, где каждое ki — случайное целое из интервала (1, 25), которое определяет номер сдвига (рис. 14.3) для i-го символа. Предположим, что все возможные ключевые последовательности равновероятны.

Решение

Существует (25)²⁹ возможных равновероятных ключевых последовательностей. Следовательно, используя равенства (14.5), (14.8) и (14.19), получаем следующее.

Энтропия ключа: Н(К) = log2 (25)²⁹ =135 бит

Абсолютная интенсивность английского языка: r’=log226= 4,7 бит/символ

Предполагаемая истинная интенсивность английского языка:

r=1,5 бит/символ

Избыточность: D = r’-r = 3,2 бит/символ

N = символа

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

14.3. Практическая защищенность

Для последовательностей шифрованного текста, размер которых больше расстояния единственности, любая система уравнений (определяющая ключ) может быть решена путем простого перебора всех возможных ключей, пока не будет получено единственное решение. Однако это совершенно непрактично, за исключением применения очень короткого ключа. Например, для ключа, полученного путем перестановки английского алфавита, существует 26!=410²⁶ возможных перестановок (в криптографическом смысле это считается малым). Будем считать, что в результате изнурительных поисков мы нашли правильный ключ, перебрав приблизительно половину возможных комбинаций. Если допустить, что каждая проверка потребует для вычисления 1 мкс, то полное время поиска превысит 10¹² лет. Следовательно, если криптоаналитик хочет иметь некоторую надежду на успех, то о «лобовых» методах перебора, следует забыть и применять какую-ту иную технологию (например, статистический анализ).

14.3.1. Смешение и диффузия

При расшифровке многих систем шифрования может применяться статистический анализ, использующий частоту появления отдельных символов и их комбинаций. Шеннон [5] предложил две концепции шифрования, усложняющие задачу криптоаналитика. Он назвал эти преобразования «смешение» (confusion) и «диффузия» (diffusion). Смешение — это подстановки, которые делают взаимосвязь между ключом и шифрованным текстом как можно более сложной. Это усложняет применение статистического анализа, сужающего поиск практического подмножества области ключей. В результате смешения дешифрование даже очень короткой последовательности шифрованного текста требует большого числа ключей. Диффузия — это преобразования, сглаживающие статистические различия между символами и их комбинациями. Примером диффузии 26-буквенного алфавита является преобразование последовательности сообщений М=М0, M1, ... в новую последовательность сообщений Y=Y0, Y1, ... с помощью следующего соотношения.

по модулю 26 (14.20)

Здесь каждый символ в последовательности рассматривается как число по модулю 26, s — некоторое выбранное целое число и n = 1, 2, .... Новое сообщение Y будет иметь ту же избыточность, что и исходное сообщение М, но частота появления всех букв в Y будет более равномерной, чем в M. В результате, чтобы статистический анализ принес криптоаналитику какую-либо пользу, ему необходимо перехватить большую последовательность шифрованного текста.

14.3.2. Подстановка

Технология шифрования с помощью подстановки, например использование шифра Цезаря и прогрессивного ключа шифрования Тритемиуса, широко используется в головоломках. Такие простые подстановочные шифры дают малую защищенность. Чтобы к подстановочной технологии можно было применить концепцию смешения, требуется более сложное соотношение. На рис. 14.6 изображен пример создания большей подстановочной сложности с помощью использования нелинейного преобразования. В общем случае п входных битов сначала представляются как один из 2ⁿ различных символов (на приведенном рисунке п=2). Затем множество из 2ⁿ символов перемешивается так, чтобы каждый символ заменялся другим символом множества. После этого символ снова превращается в n-битовый.

Можно легко показать, что существует (2ⁿ)! различные подстановки или связанные с ними возможные модели. Задача криптоаналитика становится вычислительно невозможной для больших n. Пусть п = 128, тогда 2ⁿ = 10³⁸ и (2ⁿ)! представляет собой астрономическое число. Видим, что для n = 128 это преобразование с помощью блока подстановки (substitution block, S-блок) является сложным (запутывающим). Впрочем, хотя S-блок с п=128 можно считать идеальным, его реализация является невозможной, поскольку она потребует блока с 2n = 10³⁸ контактами.

Вход	000	001	010	011	100	101	110	111
Выход	011	111	000	110	010	100	101	001

Рис. 14.6. Блок подстановки

Чтобы убедиться, что S-блок, приведенный на рис. 14.6, представляет собой нелинейное преобразование, достаточно использовать теорему о суперпозиции, которая формулируется ниже. Предположим, что

С = Та + Tb (14.21)

С’ = Т(а + b),

где а и b — входные элементы, С и С' - выходные элементы, а Т - преобразование. Тогда

Если T линейно, С = С’ для всех входных элементов.

Если Т нелинейно, СС.

Предположим, а = 001 и b = 010; тогда, используя преобразование Т, показанное на рис. 14.6, получим следующее.

С = T(001)Т(010) = 111000 = 111

С = T(001010) = T(011) = 110

Здесь символ обозначает сложение по модулю 2. Поскольку СС, S-блок является нелинейным.

14.3.3. Перестановка

При перестановке (транспозиции) буквы исходного открытого текста в сообщении не заменяются другими буквами алфавита, как в классических шифрах, а просто переставляются. Например, слово «THINK» после перестановки может выглядеть как шифрованный текст HKTNL. На рис. 14.7 приведен пример бинарной перестановки данных (линейная операция). Видно, что входные данные, просто перемешиваются или переставляются. Преобразование выполняется с помощью блока перестановки (permutation block, Р-блок). Технология, используемая сама по себе, имеет один основной недостаток: она уязвима по отношению к обманным сообщениям. Обманное сообщение изображено на рис. 14.7. Подача на вход единственной 1 (при остальных 0) позволяет обнаружить одну из внутренних связей. Если криптоаналитику необходимо выполнить криптоанализ такой системы с помощью атаки открытого текста, он отправит последовательность таких обманных сообщений, при каждой передаче смещая единственную 1 на одну позицию. Таким образом, обнаруживаются все связи входа и выхода. Данный пример показывает, почему защищенность системы не должна зависеть от ее архитектуры.

Рис. 14.7. Блок перестановки

14.3.4. Продукционный шифр

Для преобразований, включающих значительное число n-символьных сообщений, желательным является применение обеих описанных выше схем (S-блока и Р-блока). Шеннон [5] предложил использовать продукционный шифр, или комбинацию преобразований S- и Р-блоков, которые вместе могут дать более мощную систему шифрования, чем каждый из них в отдельности. Этот подход, выборочно использующий преобразования замещения и перестановки, был использован IBM в системе LUCIFER [7, 8] и стал основой национального стандарта шифрования данных (Data Encryption Standard — DES) [9]. На рис. 14.8 изображены такие комбинации Р- и S-блоков. Дешифрование выполняется обратным прогоном данных, при котором используются преобразования, обратные к преобразованию каждого S -блока. Систему, изображенную на рис. 14.8, реализовать довольно трудно, поскольку все S -блоки являются различными, случайно генерируемый ключ неприменим и система не дает возможности повторить одну и ту же последовательность операций. Поэтому в системе LUCIFER [8] использовались два различных типа S -блоков, S1 и S0, которые могли быть общедоступными. Пример такой системы изображен на рис. 14.9. Входные данные преобразуются с помощью последовательности S- и Р-блоков, определяемой ключом. В приведенном примере ключ размером 25 бит определяет, какой из двух блоков (S1 или S0) следует выбрать на каждой из 25 позиций схемы. Таким образом, подробности аппарата шифрования могут быть открыты, поскольку защищенность системы обеспечивается ключом.

Рис. 14.8. Продукционная система шифрования

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

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

14.3.5. Стандарт шифрования данных

В 1977 году Национальное бюро стандартов США (National Bureau of Standards) приняло модифицированную систему LUCIFER в качестве Национального стандарта шифрования данных (Data Encryption Standard — DES) [9]. Как показано на рис. 14.10, с точки зрения системы ввода-вывода DES может считаться блочной системой шифрования с алфавитом в 2⁶⁴ символа. Входной блок из 64 бит, который является в этом алфавите символом открытого текста, заменяется новым символом шифрованного текста. На рис. 14.11 в виде блочной диаграммы показаны функции системы. Алгоритм шифрования начинается с начальной перестановки 64 бит открытого текста, описанной в таблице начальной перестановки (табл. 14.1). Таблица начальной перестановки читается слева направо и сверху вниз, так что после перестановки биты x1, х2, ..., х64 превращаются в х58, x50, ..., х7. После этой начальной перестановки начинается основная часть алгоритма шифрования, состоящая из 16 итераций, которые используют стандартный блок, показанный на рис. 14.12. Для преобразования 64 бит входных данных в 64 бит выходных, определенных как 32 бит левой половины и 32 бит правой, стандартный блок использует 48 бит ключа. Выход каждого стандартного блока становится входом следующего стандартного блока. Входные 32 бит правой половины (Ri-1) без изменений подаются на выход и становятся 32 бит левой половины (Li). Эти Ri-1 бит с помощью таблицы расширения (табл. 14.2) также расширяются и преобразуются в 48 бит, после чего суммируются по модулю 2 с 48 бит ключа. Как и в случае таблицы начальной перестановки, таблица расширения читается слева направо и сверху вниз.

Рис. 14.10. Стандарт шифрования данных (DES) в виде блочной системы шифрования

Рис. 14.11. Стандарт шифрования данных

Рис. 14.12. Стандартный компоновочный блок

Данная таблица отображает биты

Таблица 14.1. Начальная перестановка

58	50	42	34	26	18	10	2
60	52	44	36	28	20	12	4
62	54	46	38	30	22	14	6
64	56	48	40	32	24	16	8
57	49	41	33	25	17	9	1
59	51	43	35	27	19	11	3
61	53	45	37	29	21	13	5
63	55	47	39	31	23	15	7

Таблица 14.2. Таблица выбора бит

32	1	2	3	4	5
4	5	6	7	8	9
8	9	10	11	12	13
12	13	14	15	16	17
16	17	18	19	20	21
20	21	12	23	24	25
24	25	26	27	28	29
28	29	30	31	32	1

Ri-1 = x1, x2, …, x32

в биты

(Ri-1)E = x32, …, x1, x2, …, x32, x1. (14.22)

Отметим, что биты, обозначенные в первом и последнем столбцах таблицы расширения, — это те битовые разряды, которые дважды использовались для расширения из 32 до 48 бит.

Далее (Ri-1)E суммируется по модулю 2 с i-м ключом, выбор которого описывается позднее, а результат разделяется на восемь 6-битовых блоков.

B1, B2, …, B8

Иными словами,

(Ri-1)E Ki = B1, B2, …, B8 (14.23)

Каждый из восьми 6-битовых блоков Bj используется как вход функции S-блока, возвращающей 4-битовый блок Sj(Bj)). Таким образом, входные 48 бит с помощью функции S-блока преобразуются в 32 бит. Функция отображения S-блока Sj определена в табл. 14.3. Преобразование Вj=b1, b2, b3, b4, b5, b6, выполняется следующим образом. Нужная строка — это b1b6, а нужный столбец — b2b3b4b5. Например, если b1= 110001, то преобразование Si возвращает значение из строки 3, столбца 8, т.е. число 5 (в двоичной записи 0101). 32-битовый блок, полученный на выходе S-блока, переставляется с использованием таблицы перестановки (табл. 14.4). Как и другие таблицы, Р-таблица читается слева направо и сверху вниз, так что в результате перестановки битов х1, х2,..., х32 получаем х16, х7,..., х25. 32-битовый выход Р-таблицы суммируется по модулю 2 с 32 бит левой половины (Li-1), образуя выходные 32 бит правой половины (Ri).

Таблица 14.3. Функции выбора S-блока

Столбец
Строка	0	1	2	3	4	5	6	7	8	9	10	11	12	13	14	15
0	14	4	13	1	2	15	11	8	3	10	6	12	5	9	0	7
1	0	15	7	4	14	2	13	1	10	6	12	11	9	5	3	8
2	4	1	14	8	13	6	2	11	15	12	9	7	3	10	5	0	S1
3	15	12	8	2	4	9	1	7	5	11	3	14	10	0	6	13
0	15	1	8	14	6	11	3	4	9	7	2	13	12	0	5	10
1	3	13	4	7	15	2	8	14	12	0	1	10	6	9	11	5
2	0	14	7	11	10	4	13	1	5	8	12	6	9	3	2	15	S2
3	13	8	10	1	3	15	4	2	11	6	7	12	0	5	14	9
0	10	0	9	14	6	3	15	5	1	13	12	7	11	4	2	8
1	13	7	0	9	3	4	6	10	2	8	5	14	12	11	15	1
2	13	6	4	9	8	15	3	0	11	1	2	12	5	10	14	7	S3
3	1	10	13	0	6	9	8	7	4	15	14	3	11	5	2	12
0	7	13	14	3	0	6	9	10	1	2	8	5	11	12	4	15
1	13	8	11	5	6	15	0	3	4	7	2	12	1	10	14	9
2	10	6	9	0	12	11	7	13	15	1	3	14	5	2	8	4	S4
3	3	15	0	6	10	1	13	8	9	4	5	11	12	7	2	14
0	2	12	4	1	7	10	11	6	8	5	3	15	13	0	14	9
1	14	11	2	12	4	7	13	1	5	0	15	10	3	9	8	6
2	4	2	1	11	10	13	7	8	15	9	12	5	6	3	0	14	S5
3	11	8	12	7	1	14	2	13	6	15	0	9	10	4	5	3
0	12	1	10	15	9	2	6	8	0	13	3	4	14	7	5	11
1	10	15	4	2	7	12	9	5	6	1	13	14	0	11	3	8
2	9	14	15	5	2	8	12	3	7	0	4	10	1	13	11	6	S6
3	4	3	2	12	9	5	15	0	11	14	1	7	6	0	8	13
0	4	11	2	14	15	0	8	13	3	12	9	7	5	10	6	1
1	13	0	11	7	4	9	1	10	14	3	5	12	2	15	8	6
2	1	4	11	13	12	3	7	14	10	15	6	8	0	5	9	2	S7
3	6	11	13	8	1	4	10	7	9	5	0	15	14	2	3	12
0	13	2	8	4	6	15	11	1	10	9	3	14	5	0	12	7
1	1	15	13	8	10	3	7	4	12	5	6	11	0	14	9	2
2	7	11	4	1	9	12	14	2	0	6	10	13	15	3	5	8	S8
3	2	1	14	7	4	10	8	13	15	12	9	0	3	5	6	11

Таблица 14.4. Таблица перестановки

16	7	20	21
29	12	28	17
1	15	23	26
5	18	31	10
2	8	24	14
32	27	3	9
19	13	30	6
22	11	4	25

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

Li = Ri-1 (14.24)

Ri = Li-1f (Ri-1,Ki) (14.25)

Здесь f (Ri-1,Ki) обозначает функциональное соотношение, включающее описанные выше расширение, преобразование в S-блоке и перестановку. После 16 итераций в таких стандартных блоках данные размещаются согласно окончательной обратной перестановке, описанной в табл. 14.5, где, как и ранее, выходные биты читаются слева направо и сверху вниз.

Таблица 14.5. Окончательная перестановка

40	8	48	16	56	24	64	32
39	7	47	15	55	23	63	31
38	6	46	14	54	22	62	30
37	5	45	13	53	21	61	29
36	4	44	12	52	20	60	28
35	3	43	11	51	19	59	27
34	2	42	10	50	18	58	26
33	1	41	9	49	17	57	25

Для дешифрования применяется тот же алгоритм, но ключевая последовательность, используемая в стандартном блоке, берется в обратном порядке. Отметим, что значение f(Ri-1, Ki), которое может быть также выражено через выход i-ro блока как f(Li, Ki), делает процесс дешифрования возможным.

14.3.5.1. Выбор ключа

Выбор ключа также происходит в течение 16 итераций, как показано в соответствующей части рис. 14.11. Входной ключ состоит из 64-битового блока с 8 бит четности в разрядах 8, 16..... 64. Перестановочный выбор 1 отбрасывает биты четности и переставляет оставшиеся 56 бит согласно табл. 14.6. Выход данной процедуры делится пополам на два элемента — С и D, каждый из которых состоит из 28 бит. Выбор ключа проходит за 16 итераций, проводимых для создания различных множеств 48 ключевых бит для каждой итерации шифрования. Блоки С и D последовательно сдвигаются согласно следующим выражениям.

Таблица 14.6. Круговая перестановка

57	49	41	33	25	17	9
1	58	50	42	14	26	18
10	2	59	51	43	35	27
19	11	3	60	52	44	36
63	55	47	39	31	23	15
7	62	54	46	38	30	22
14	6	61	53	45	37	29
21	13	5	28	20	12	4

Ci = LSi(Ci-1) и Di = LSi(Di-1) (14.26)

Здесь LSi - левый циклический сдвиг на число позиций, показанных в табл. 14.7. Затем последовательность Ci, Di переставляется согласно перестановочному выбору 2, показанному в табл. 14.8. Результатом является ключевая последовательность Ki, которая используется в i-й итерации алгоритма шифрования.

Таблица 14.7. Ключевая последовательность сдвигов влево

Итерация i	Количество сдвигов влево
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16	1 1 2 2 2 2 2 2 1 2 2 2 2 2 2 1

Таблица 14.8. Ключевая перестановка 2

14	17	11	24	1	5
3	28	15	6	21	10
23	19	12	4	26	8
16	7	27	20	13	2
41	52	31	37	47	55
30	40	51	45	33	48
44	49	39	56	34	53
46	42	50	36	29	32

DES может реализовываться подобно блочной системе шифрования (см. рис. 14.11), что иногда называют методом шифровальной книги. Основным недостатком этого метода является то, что (при использовании одного ключа) данный блок входного открытого текста будет всегда давать тот же выходной шифрованный блок. Еще один способ шифрования, называемый способом шифрования с обратной связью, приводит к шифрованию отдельных битов, а не символов, что дает поточное шифрование [3]. В системе шифрования с обратной связью (описанной ниже) шифрование сегмента открытого текста зависит не только от ключа и текущих данных, но и от некоторых предшествующих данных.

С конца 1970-х широко обсуждались два спорных момента, связанных с DES [10]. Первый касается длины ключа. Некоторые исследователи считали, что 56 бит не достаточно, чтобы исключить взлом путем перебора. Второй момент касается внутренней структуры S-блоков, которые никогда не выпускались IBM. Агентство национальной безопасности США, которое было привлечено к тестированию алгоритма DES, потребовало, чтобы эта информация не обсуждалась публично. Критики опасаются, что АНБ участвовало в проектировании этих схем и теперь способно «проникать» в любое сообщение, шифрованное согласно DES [10]. В настоящее время стандарт DES больше не является приемлемым выбором, обеспечивающим надежное шифрование. Поиск 56-битового ключа с помощью недорогих компьютерных методов является делом нескольких дней [11].

14.4. Поточное шифрование

Ранее мы определили разовое заполнение как систему шифрования со случайным одноразовым ключом, который обеспечивает безусловную защищенность. Реализовать разовое поточное заполнение можно с использованием действительно случайного потока ключей (ключевая последовательность никогда не повторяется). Таким образом, совершенная секретность может достигаться для бесконечного числа сообщений, так как каждое сообщение шифруется с помощью разных частей случайного ключевого потока. Развитие схем поточного шифрования — это попытка имитации схем одномоментного заполнения. Большой упор делается на генерации ключевых потоков, которые должны выглядеть случайными. Реализовать такие последовательности можно с помощью соответствующих алгоритмов. Названная технология поточного шифрования использует псевдослучайные последовательности; их название отражает тот факт, что они выглядят случайными для случайного наблюдателя. Статистические свойства двоичных псевдослучайных последовательностей подобны получаемым при случайном подбрасывании симметричной монеты. В то же время, разумеется, эти последовательности являются детерминистическими (см. раздел 12.2). Данные технологии популярны, поскольку алгоритмы шифрования и дешифрования воплощаются с использованием регистров сдвига с обратной связью. На первый взгляд может показаться, что поточный псевдослучайный ключ может обеспечивать ту же защищенность, что и метод одномоментного заполнения, поскольку период последовательности, порожденной линейным регистром сдвига, составляет 2^n-1 бит, где п — количество разрядов в регистре. Если псевдослучайная последовательность воплощается с помощью 50-разрядного регистра и дискретности в 1 МГц, последовательность будет повторяться каждые 2⁵⁰-1 микросекунды, или каждые 35 лет. В эпоху больших интегральных схем совсем несложно реализовать схему с 100 разрядами. В этом случае последовательность будет повторяться каждые 410¹⁶ лет. Следовательно, можно предположить, что поскольку псевдослучайная последовательность не повторяется в течение такого длительного периода, она может казаться действительно случайной и давать совершенную секретность. Но все же существует одно важное отличие псевдослучайной последовательности от действительно случайной последовательности, используемой в методе одномоментного заполнения. Псевдослучайная последовательность генерируется алгоритмом. Таким образом, если известен алгоритм, то известна и сама последовательность.

14.4.1. Пример генерирования ключа с использованием линейного регистра сдвига с обратной связью

В технологии поточного шифрования для генерации псевдослучайной ключевой последовательности обычно используются регистры сдвига. Регистр сдвига может быть превращен в генератор псевдослучайной последовательности путем введения контура обратной связи, который вычисляет новый элемент для первого разряда, основываясь на предыдущих п элементах. Говорят, что регистр является линейным, если линейна операция, производимая в контуре обратной связи. В разделе 12.2 мы уже рассматривали пример генератора псевдослучайной последовательности. На рис. 14.13 этот генератор приведен повторно. В данном случае разряды регистра удобно нумеровать так, как показано на рис. 14.13, где n =4, а выходы разрядов 1 и 2 суммируются по модулю 2 (линейная операция) и передаются обратно на разряд 4. Если начальное состояние разрядов (x4, x3, x2, x1,) — это 1000, то следующие состояния будут выглядеть как 1000, 0100, 1001, 1100 и т.д. Выходная последовательность составлена из битов, снимаемых с крайнего правого разряда регистра, т.е. 111101011001000, где крайний правый бит в последовательности является самым ранним, а крайний левый — наиболее поздним. При данном произвольном n-разрядном линейном регистре сдвига с обратной связью выходная последовательность в конечном счете периодична.

Рис. 14.13. Пример линейного регистра сдвига с обратной связью

14.4.2. Слабые места линейных регистров сдвига с обратной связью

Схема шифрования, в которой для порождения ключевого потока применяются линейные регистры сдвига с обратной связью (linear feedback shift register — LFSR), является очень уязвимой по отношению к атакам. Чтобы определить отводы обратной связи, начальное состояние регистра и всю последовательность кода, криптоаналитику требуется всего 2п бит открытого текста и соответствующий им шифрованный текст. Как правило, 2n намного меньше периода 2ⁿ-1. Проиллюстрируем эту уязвимость с помощью примера регистра, изображенного на рис. 14.13. Пусть криптоаналитику, который ничего не знает о внутренних связях регистра, удалось получить 2п = 8 бит шифрованного текста и их открытый эквивалент.

Открытый текст: 01010101

Шифрованный текст: 00001100

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

Чтобы получить фрагмент ключевого потока 01011001 (рис. 14.14), криптоаналитик складывает обе последовательности по модулю 2. Ключевой поток показывает содержание регистров в различные моменты времени. Крайние правые четыре ключевых бита показывают содержание регистра сдвига в момент t1. Если последовательно «сдвигать» эту четверку на один символ влево, то получим содержимое регистра в моменты t2, t3, t4. Используя линейную структуру регистра сдвига, можно записать следующее.

g4x4 + g3x3 + g2x2 + gixi= x5 (14.27)

Рис. 14.14. Пример уязвимости линейного регистра сдвига с обратной связью

Здесь x5 — цифра, которая через контур обратной связи подана обратно на вход, а gi (i= 1 или 0) определяет i-e соединение обратной связи. Таким образом, изучая содержание регистра в четыре момента времени, изображенных на рис. 14.14, можно написать следующие четыре уравнения с четырьмя неизвестными.

g4 (1) + g3 (0) + g2 (0) + g1 (1) = 1

g4 (1) + g3 (1) + g2 (0) + g1 (0) = 0

g4 (0) + g3 (1) + g2 (1) + g1 (0) = 1 (14.28)

g4 (1) + g3 (0) + g2 (1) + g1 (1) = 1

Решение уравнений (14.28), соответствующих регистру, изображенному на рис. 14.13, является g1 = l, g2 = l, g3 = 0, g4 = 0. Таким образом, криптоаналитик узнал связи регистра, а также его начальное состояние в момент t1. Следовательно, он может узнать последовательность в любой момент времени [3]. Обобщив этот пример на любой регистр сдвига с п разрядами, можно переписать уравнение (14.27) следующим образом.

(14.29)

Уравнение (14.29) можно записать в матричной форме.

х = Хg (14.30)

где

x = g =

и

Х = .

Можно показать [3], что столбцы X линейно независимы; таким образом, матрица X невырождена (ее определитель отличен от нуля) и имеет обратную. Следовательно,

g = X^-1 x (14.31)

Обращение матрицы требует порядка n³ операций и, таким образом, легко выполняется на компьютере для любого разумного значения п. Например, если n = 100, то n³ = 10⁶, и компьютеру со скоростью работы одна операция за 1 мкс для обращения матрицы понадобится 1с. Слабость регистра сдвига с обратной связью обусловлена линейностью уравнения (14.31). Использование нелинейной обратной связи в регистре сдвига делает задачу криптоаналитика гораздо сложнее, если не вычислительно трудноосуществимой.

14.4.3. Синхронные и самосинхронизирующиеся системы поточного шифрования

Системы поточного шифрования можно разделить на синхронные и самосинхронизирующиеся. В первых ключевой поток генерируется независимо от сообщения; так что потеря символа во время передачи неизбежно требует повторной синхронизации передачи и генераторов ключей приёмника. Синхронный поточный шифр изображен на рис. 14.15. Начальное состояние генератора ключа инициализируется с помощью известного входа I0. Шифрованный текст получается путем сложения по модулю 2 i-го символа ключа ki и i-го символа сообщения mi. Такие синхронные шифры обычно создаются для смешения, но не диффузии. Иными словами, шифрование символа не распространяется вдоль некоторого блока сообщения. По этой причине синхронные поточные шифры не имеют накопления ошибки.

Рис. 14.15. Синхронный поточный шифр

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

В разделе 14.1.4 приводился пример обратной связи для шифрования с помощью автоматического ключа Вигнера. Показывалось, что преимуществом такой системы является: (1) генерация неповторяющегося ключа и (2) диффузия статистик открытого сообщения в шифрованном тексте. В то же время был и недостаток — ключ проявлялся в шифрованном тексте. Этой проблемы можно избежать, если при получении ключа пропустить символы шифрованного текста через нелинейный блок шифрования. На рис. 14.16 изображен регистр сдвига генератора ключа, работающий в режиме обратной связи по шифру. Каждый выходной символ шифрованного текста сi (образованный путем сложения по модулю 2 символа сообщения mi и символа ключа ki) подается обратно на вход регистра сдвига. Как и ранее, инициализация происходит с помощью известного входа I0. При каждой итерации выход регистра сдвига используется как вход (нелинейного) блочного алгоритма шифрования ЕВ. Символ младшего разряда на выходе ЕB становится следующим символом ключа ki+1, который используется в следующем символе сообщения mi+1. Поскольку после нескольких первых итераций вход алгоритма зависит только от шифрованного текста, система является самосинхронизирующейся.

Рис. 14.16. Шифрование в режиме обратной связи

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

Понятие систем с открытыми ключами было введено в 1976 году Диффи (Diffie) и Хэллманом (Hellman) [12]. В общепринятых криптосистемах алгоритм шифрования может быть обнаружен, поскольку защищенность системы зависит от сохранности ключа. Один и тот же ключ применяется как для шифрования, так и для дешифрования. Криптосистемы с открытыми ключами используют два разных ключа: один — для шифрования, другой — для дешифрования. В таких криптосистемах общедоступными (без потери защищенности системы) могут быть не только алгоритм шифрования, но и ключ, применяемый для шифрования. Фактически это общедоступный каталог, подобный телефонному каталогу, который содержит ключи шифрования всех абонентов. Держатся в секрете только ключи дешифрования. Пример такой системы приведен на рис. 14.17. Перечислим важные особенности криптосистемы с открытым ключом.

Рис. 14.17. Криптосистема с открытым ключом

1. Алгоритм шифрования ЕK и алгоритм дешифрования DK являются обратимыми преобразованиями открытого текста M или шифрованного текста С, определяемыми ключом К.

2. Для каждого ключа К алгоритмы ЕK и DK легко вычисляемы.

3. Для каждого ключа К определение DK из ЕK вычислительно трудноосуществимо.

Такая система обычно способна обеспечивать защищенность переговоров между пользователями, которые никогда ранее не встречались или не общались. Например, как показано на рис. 14.17, пользователь А может послать сообщение пользователю В, найдя ключ шифрования пользователя В в каталоге и используя алгоритм шифрования ЕB. Получив таким образом шифрованный текст С = ЕB(М), он передает его через общедоступный канал. Пользователь В - это единственный человек, который может дешифровать сообщение С, чтобы в результате получилось M = DB(C), с помощью своего алгоритма дешифрования DB.

14.5.1. Проверка подлинности подписи с использованием криптосистемы с открытым ключом

На рис. 14.18 изображено применение криптосистемы с открытым ключом для проверки подлинности подписи. Пользователь А «подписывает» свое сообщение, используя свой алгоритм дешифрования DA, что дает S=DA(M) = =EA^-1(M). Затем для шифрования S он воспользуется алгоритмом шифрования ЕВпользователя В и в результате получит сообщение С=ЕВ(S) = ЕB[ЕА^-1(М)], которое он передает через общедоступный канал. Когда пользователь В получает сообщение С, он сначала дешифрует его с помощью собственного алгоритма дешифрования DB, что дает DB(C) = ЕА^-1(М). Затем он использует алгоритм шифрования пользователя А, в результате чего получает ЕА [EA^-1(M)] =М.

Если в результате получается вразумительное сообщение, оно точно было послано пользователем А, поскольку больше никто не знает секретного кода шифрования пользователя А, с помощью которого выполняется преобразование S = DA(M). Отметим, что сообщение S зависит и от сообщения, и от подписи, а это означает, что не только В может быть уверен, что сообщения действительно приходят от А, но и А уверен, что никто, кроме В, не сможет прочесть это сообщение.

Рис. 14.18. Проверка подлинности подписи с использованием криптосистемы с открытым ключом

14.5.2. Односторонняя функция с «лазейкой»

Криптосистемы с открытым ключом основаны на понятии односторонних функций с «лазейками». Определим одностороннюю функцию как легко вычисляемую, для которой невозможно вычислить обратную. Рассмотрим, например, функцию у = х⁵+ 12х³ + 107х + 123. Должно быть очевидно, что при данном х легко вычислить у, но при данном у относительно сложно вычислить х. Односторонняя функция с «лазейкой» — это односторонняя функция, для которой легко вычислить обратную, если известны некоторые особенности, используемые для создания функции. Как и лазейка, такие функции легко проходимы в одном направлении. Обратный процесс без специальной информации занимает невероятно много времени. Понятие «лазейки» будет применено в разделе 14.5.5, когда будет обсуждаться схема Меркла-Хэллмана (Merkle-Hellman).

14.5.3. Схема RSA

Сообщения в схеме Ривеста-Шамира-Дцельмана (Riyest- Shamir-Adelman -RSA) сначала представляются как целые числа из интервала (0, n-1). Каждый пользователь выбирает собственное значение п и пару положительных целых чисел е и d описанным ниже способом. Пользователь помещает свой ключ шифрования, числовую пару (п, е), в общедоступный каталог. Ключ дешифрования состоит из числовой пары (n, d), в которой d держится в секрете. Шифрование сообщения М и дешифрование шифрованного текста С определяются следующим образом.

Шифрование: С = Е(М) = (М)^епо модулю n (14.32)

Дешифрование: М =D(C)= (C)^d по модулю n

Это легко вычислить. Результатом каждой операции являются целые числа из интервала (0, n-1). В схеме RSA п получается в результате перемножения двух больших простых чисел р и q.

n=pq (14.33)

Несмотря на то что п общедоступно, p иq являются скрытыми из-за большой сложности в разложении п на множители. Затем определяется функция, называемая функцией Эйлера.

(14.34)

Параметр (п) имеет интересное свойство [12]: для любого целого X из интервала (0, n-1) и любого целого k имеет место, следующее соотношение.

по модулю n (14.35)

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

НОД [, d]= 1 (14.36)

В данном случае НОД означает «наибольший общий делитель». Этому условию будет удовлетворять любое простое число, большее наибольшего из (р, q). Далее находится целое е, 0 < е <,

ed по модулю = 1, (14.37)

что, вследствие равенства (14.35), равносильно выбору е и d, которые удовлетворяют следующему условию.

X = X^ed по модулю n (14.38)

Следовательно,

E[D(X)] = D[E(X)]=X (14.39)

и возможно корректное дешифрование. Один из возможных способов взлома шифра при данном ключе (п, е) — это разложить п на множители р и q, вычислить = (р-1)(q-1) и вычислить d из равенства (14.37). Все это, за исключением разложения п на множители, представляет собой простые действия.

Схема RSA основывается на том, что два больших простых целых числа р и q легко выбрать и перемножить, но гораздо сложнее разложить на множители результат. Следовательно, произведение, как часть ключа шифрования, может быть сделано общедоступным, в то время как множители, которые могут «разоблачить» ключ дешифрования, соответствующий ключу шифрования, остаются скрытыми. Если длина каждого множителя составляет порядка 100 разрядов, умножение может быть выполнено в доли секунды, а изнурительное разложение на множители результата может потребовать миллиарды лет [2].

14.5.3.1. Использование схемы RSA

Используя пример из работы [13], положим р=47, q=59. Следовательно, п- pq = = 1773 и = (р - 1)(q - 1) = 2668. Параметр d выбирается взаимно простым с . Например, выберем d=157. Затем вычислим значение е следующим образом (подробности приведены в следующем разделе).

ed по модулю = 1

157е по модулю 2688 = 1

Следовательно, е = 17. Рассмотрим пример открытого текста.

ITS ALL GREEK TO ME

Если заменить каждую букву двухразрядным числом из интервала (01, 26), соответствующим ее позиции в алфавите, и закодировать пробел как 00, открытое сообщение можно записать следующим образом.

0920 1900 0112 1200 0718 0505 1100 2015 0013 0500

Каждый символ выражается целым числом из интервала (0, п-1). Поэтому в данном примере шифрование может быть представлено в виде блоков по четыре разряда, так как это максимальное число разрядов, которое всегда дает число, меньшее п-1 = 2772. Первые четыре разряда (0920) открытого текста шифруются следующим образом.

С = (М)^епо модулю п = (920)¹⁷ по модулю 2773 = 948

Продолжая этот процесс для оставшихся разрядов открытого текста, получим следующее.

С = 0948 2342 1084 1444 2663 2390 0778 0774 0229 1655

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

М = (С)¹⁵⁷ по модулю 2773

14.5.3.2. Как вычислить е

Для вычисления е используется разновидность алгоритма Евклида вычисления НОД и d. Сначала вычисляем последовательность значений x0, x1, х2, ..., где x0 =, x1= d, а хi+1= хi-1 по модулю xi, пока не будет получено xk = 0. Тогда НОД (x0, x1) = хk-1. Для каждого xi вычисляются числа аi и bi, при которых хi= аi x0 + bi x1 . Если xk-1= 1, то bk-1 — мультипликативное обратное к х1по модулю х0. Если bk-1 — отрицательное число, решением является bk+1+.

Пример 14.5. Вычисление е с помощью d и

Для предыдущего примера, в котором р = 47, q = 59, п = 2773 и d выбрано равным 157, примените алгоритм Евклида для проверки, что е = 17.

Решение

i	xi	ai	bi	yi
0	2668	1	0
1	157	0	1	16
2	156	1	-16	1
3	1	-1	17

Здесь

Следовательно,

e = b3=17.

14.5.4. Задача о рюкзаке

Классическая задача о рюкзаке изображена на рис. 14.19. Рюкзак наполнен множеством предметов с указанием их веса в граммах. Зная вес наполненного рюкзака (шкала весов градуирована так, что вес пустого рюкзака вычитается), нужно определить содержимое рюкзака. В этом простом примере решение легко найти методом проб и ошибок. Однако если в заданном множестве не 10, а 100 возможных единиц, задача может стать вычислительно неосуществимой.

Рис. 14.19. Задача о рюкзаке

Опишем задачу о рюкзаке через вектор рюкзака и вектор данных. Вектор рюкзака представляет собой n-кортеж разных целых чисел (аналогично множеству разных предметов содержимого рюкзака).

a = a1, a2, …, an

Вектор данных — это n-кортеж двоичных символов.

x = x1, x2, …, xn

Рюкзак S — это сумма подмножества компонентов вектора рюкзака.

ax, где xi = 0,1 (14.40)

Задачу о рюкзаке можно сформулировать следующим образом: при данном S и известном а определите х.

Пример 14.6. Пример рюкзака

Дано а = 1, 2, 4, 8, 16, 32 и S = ах =26. Найдите х.

Решение

Видно, что в этом примере х — это двоичное представление S. Преобразование из десятичного в двоичное окажется более, знакомым, если представить а как 2⁰, 2¹, 2², 2³, 2⁴, 2⁵, 2⁶. Вектор данных х находится легко, поскольку а в этом примере является быстровозрастающим; это означает, что каждый компонент набора n-кортежа а больше суммы предыдущих компонентов. Другими словами,

i = 2,3, ..., п (14.41)

Если а является быстровозрастающим, то первый элемент х - хn = 1, если Sаn (в противном случае, хn=0); следующий элемент находится согласно соотношению

, (14.42)

где i = п-1, п-2,..., 1. С помощью равенства (14.42) легко вычисляется х = 010110.

Пример 14.7. Пример рюкзака

Дано а = 171, 197, 459, 1191, 2410, 4517 и S = ах = 3798. Найдите х.

Решение

Как и в примере 14.6, а является быстровозрастающим. Поэтому с помощью равенства (14.42) можно вычислить х.

х = 010110

14.5.5. Криптосистема с открытым ключом, основанная на «лазейке» в рюкзаке

Эта схема, известная также как схема Меркла-Хэллмана [15], основана на образовании вектора рюкзака, который не является быстровозрастающим. Следовательно, задача не является легкоразрешимой. При этом данная задача о рюкзаке обязательно включает лазейку, позволяющую разрешенным пользователям решить задачу.

Сначала образуем быстровозрастающий п-кортеж. Затем выберем простое число М, при котором имеет место следующее неравенство.

(14.43)

Выберем также случайное число W (1<W<M) и сформируем W^-1, удовлетворяющее следующему соотношению.

WW^-1 по модулю М = 1 (14.44)

Вектор а' и числа М, W и W^-1 удерживаются скрытыми. Затем из элементов а' формируем а.

ai= Waj’ по модулю М (14.45)

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

S = ах = (14.46)

Разрешенный пользователь получает S и, используя равенство (14.44), превращает его в S’.

=

= (14.47)

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

14.5.5.1. Использование схемы Меркла-Хэллмана

Предположим, пользователь А желает создать общедоступную и конфиденциальную функции шифрования. Сначала он рассматривает быстровозрастающий вектор а' = (171, 197, 459, 1191, 2410, 4517).

= 8945

Затем он выбирает простое число М, большее 8945, случайное число W, такое, что 1W< М, и вычисляет W^-1, при котором WW^-1 = 1 по модулю М.

После этого он образует вектор, который оставляет «лазейку» в рюкзаке.

аi = аi’ 2251 по модулю 9109

а = 2343, 6215, 3892, 2895, 5055,2123

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

Если х = 010110 — сообщение, которое нужно передать, то пользователь В создает следующее число.

S = ах = 14 165 и передает его пользователю А

Пользователь А получает S и превращает его в S'.

S'= а'х = W^-1S по модулю М= 138814 165 по модулю 9109 = 3798

Используя S' = 3798 и быстровозрастающий вектор а', пользователь А легко находит х.

Схема Меркла-Хэллмана сейчас считается взломанной [16], поэтому для реализации криптосистем с открытыми ключами используется алгоритм RSA (равно как и другие рассмотренные позднее).

14.6. Pretty Good Privacy

PGP (Pretty Good Privacy, буквально: «весьма хорошая секретность») — это программа обеспечения секретности, которая была создана Филиппом Циммерманом (Philip Zimmerman) [17] и опубликована в 1991 году как бесплатное программное обеспечение. Затем она «де-факто» стала стандартом для электронной почты и шифрования файлов. PGP версии 2.6 (наиболее широко используемая) оставалась неизменной вплоть до появления версии 5.0 (совместимой с версией 2.6). В табл. 14.9 приведены алгоритмы, используемые в версиях 2.6, 5.0 и более поздних.

Таблица 14.9. Сравнение PGP 2.6 и PGP 5.0

Функция	PGP версии 2.6 Используемый алгоритм [17]	PGP версии 5.0 и более поздних Используемый алгоритм [18]
Шифрование сообщения с использованием алгоритма частного ключа с помощью ключа частного сеанса Шифрование ключа частного сеанса с помощью алгоритма частного ключа Цифровая подпись Хэш-функция, используемая при создании профиля сообщения для цифровых подписей	IDEA RSA RSA MD5	«Тройной» DES, CAST или IDEA RSA или алгоритм Диффи- Хэллмана (вариант Элгемала) RSA и DSS[1] (от NIST[2]) SHA-1

Как показано в табл. 14.9, PGP использует множество алгоритмов шифрования, включающих как схемы частного ключа, так и схемы открытого ключа. При шифровании сообщения применяется алгоритм частного ключа (для каждого сеанса генерируется новый ключ сеанса). В качестве алгоритмов частного ключа, предлагаемых PGP, представлены Международный алгоритм шифрования данных (International -Desalination and Environmental Association — IDEA), "тройной" DES и алгоритм CAST (названный в честь авторов Карлайла Адамса (Carlisle Adams) и Стэффорда Тевереса (Stafford Tavares) [19]). Для шифрования ключа каждого сеанса используется алгоритм открытого ключа. В качестве алгоритмов, использующих открытые ключи, PGP предлагает алгоритм RSA, описанный в разделе 14.5.3, и алгоритм Диффи-Хэллмана (Diffie-Hellman).

Алгоритмы с открытыми ключами применяются также для создания цифровых подписей. PGP версии 5.0 использует алгоритм цифровой подписи (Digital Signature Algorithm — DSA), заданный в стандартах цифровой подписи (Digital Signature Standard — DSS) института NIST. PGP версии 2.6 в своих цифровых подписях использует алгоритм RSA. Если имеющийся канал не защищен от изменений ключа, он более безопасен для использования алгоритма с ключом общего доступа. Для защищенного канала предпочтительно шифрование с частным ключом, поскольку это, как правило, дает лучшее быстродействие по сравнению с системами, использующими открытые ключи.

Технология шифрования сообщения, применяемая PGP версии 2.6, изображена на рис. 14.20. Перед шифрованием открытый текст сжимается с помощью ZIP-алгоритма. Система PGP использует ZIP-метод, описанный Жаном-Лупом Гейли (Jean-Loup Gaily), Марком Элдером (Mark Alder) и Ричардом Б. Уэльсом (Richard В. Wales) [18]. Если сжатый текст короче несжатого, то шифроваться будет сжатый текст, в противном случае будет шифроваться несжатый.

Небольшие файлы (приблизительно 30 символов для файлов ASCII) не выигрывают от сжатия. К тому же, PGP распознает файлы, ранее сжатые с помощью распространенных технологий сжатия, таких как PKZIP, и не будет пытаться сжать их. Сжатие данных устраняет избыточные строки символов и приводит к более равномерному распределению символов. С помощью сжатия получаем более короткий файл для шифрования и дешифрования (что сокращает время, необходимое для шифрования, дешифрования и передачи файла). Сжатие также создает препятствия некоторым криптоаналитическим атакам, использующим избыточность. Необходимо отметить, что сжатие файла должно предшествовать шифрованию (а не наоборот). Почему стоит следовать этому правилу? Хороший алгоритм шифрования дает шифрованный текст с практически статистически равномерным распределением символов. Следовательно, если алгоритм сжатия данных следует после такого шифрования, он не будет давать никакого сжатия вообще. Если некоторый шифрованный текст может быть сжат, то алгоритм шифрования, с помощью которого получен шифрованный текст, был неудачным. Алгоритм сжатия не должен обнаруживать избыточные фрагменты в тексте, зашифрованном с помощью хорошего алгоритма.

Как показано на рис. 14.20, PGP начинает шифрование файла с создания 128-битового ключа сеанса, используя генератор псевдослучайных чисел. Затем с помощью этого случайного ключа сеанса шифруется сжатый файл открытого текста, для чего применяется алгоритм частного ключа IDEA.

Рис. 14.20. Метод PGP

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

14.6.1. "Тройной" DES, CAST и IDEA

Как показано в табл. 14.9, PGP предлагает три блочных шифра для шифрования сообщения — "тройной" DES, CAST и IDEA. Все три шифра оперируют 64-битовыми блоками открытого и шифрованного текстов. Размер ключа "тройного" DES составляет 168 бит, в то время как CAST и IDEA используют ключи длиной 128 бит.

14.6.1.1. Описание "тройного" DES

Стандарт шифрования данных (Data Encryption Standard — DES), описанный в разделе 14.3.5, использовался с конца 1970-х годов. Однако у многих вызывала беспокойство его защищенность, так как в нем применялся ключ относительно малого размера (56 бит). При использовании "тройного" алгоритма DES, шифруемое сообщение трижды пропускается через алгоритм DES (вторая операция проводится в режиме дешифрования). Каждая операция производится с помощью разных 56-битовых ключей. Как показано на рис. 14.21, это равносильно использованию ключа длиной 168 бит.

Рис. 14.21. Шифрование/дешифрование с помощью "тройного" алгоритма DES

14.6.1.2. Описание CAST

CAST — это семейство блочных шифров, разработанных Адамсом (Adams) и Тевересом (Tavares) [19]. PGP 5.0 использует версию CAST, известную как CASTS или CAST-128. В этой версии размер блока составляет 64 бит, а длина ключа — 128 бит. Алгоритм CAST использует шесть S-блоков с 8-битовым входом и 32-битовым выходом. Для сравнения, DES применяет восемь S-блоков с 6-битовым входом и 4-битовым выходом. S-блоки в CAST-128 были созданы для обеспечения существенно нелинейных преобразований, которые делают этот алгоритм практически не поддающимся криптоанализу [11].

14.6.1.3. Описание IDEA

Международный алгоритм шифрования данных (International Data Encryption Algorithm — IDEA) представляет собой блочный шифр, разработанный Ксуэйя Лай (Xuejia Lai) и Джеймсом Мэсси (James Massey) [19]. Это 64-битовый итерационный блочный шифр (включающий восемь итераций или циклов) с 128-битовым ключом. Защищенность IDEA зависит от использования трех типов арифметических операций над 16-битовыми символами: сложение по модулю 2¹⁶, умножение по модулю 2¹⁶ + 1 и побитовое исключающее ИЛИ. Для итерационных операций шифрования и дешифрования используется 128-битовый ключ. Как показано в табл. 14.10, начальный ключ К0делится на восемь 16-битовых подключей Zx^(R), где х — номер подключа цикла R. Шесть из этих подключей используются в цикле 1, а оставшиеся два — в цикле 2. Затем К0 циклически сдвигается на 25 бит влево, в результате чего образуется ключ К1, который, в свою очередь, делится на восемь подключей. Первые 4 из этих подключей используются в цикле 2, а последние четыре — в цикле 3. Процесс продолжается, как показано в табл. 14.10, в результате чего в общей сложности появляется 52 подключа.

Таблица 14.10. Образование подключей в алгоритме IDEA

128-битовый ключ (делится на восемь 16-битовых подключей)	Строка битов, из которой выводятся ключи
Z11Z21Z31Z41Z51Z61Z12Z22 Z32Z42Z52Z62Z13Z23Z33Z43 Z53Z63Z14Z24Z34Z44Z54Z64 Z15Z25Z35Z45Z55Z65Z16Z26 Z36Z46Z56Z66Z17Z27Z37Z47 Z57Z67Z18Z28Z38Z48Z58Z68 Z1out Z2out Z3out Z4out	K0 = исходный 128-битовый ключ К1 = сдвиг K0 на 25 бит К0 = сдвиг K1 на 25 бит К0= сдвиг К2на 25 бит К0= сдвиг К3на 25 бит К0= сдвиг К4 на 25 бит Первые 64 бит К6, где К6 = сдвиг К5на 25 бит

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

Таблица 14.11. Эволюция подключа алгоритма IDEA

Цикл	Набор подключей шифрования	Набор ключей дешифрования
1 2 3 4 5 6 7 8 Выходное преобразование	Z11Z21Z31Z41Z51Z61 Z12Z22Z32Z42Z52Z62 Z13Z23Z33Z43Z53Z63 Z14Z24Z34Z44Z54Z64 Z15Z25Z35Z45Z55Z65 Z16Z26Z36Z46Z56Z66 Z17Z27Z37Z47Z57Z67 Z18Z28Z38Z48Z58Z68 Z1out Z2out Z3out Z4out	(Z1out)-1- Z2out -Z3out (Z4out)-1 Z58Z68 (Z18 )-1 -Z28 -Z38 (Z48 )-1Z57Z67 (Z17 )-1 -Z27 -Z37 (Z47 )-1Z55Z66 (Z16 )-1 -Z26 -Z36 (Z46 )-1Z55Z65 (Z15 )-1 -Z25 -Z35 (Z45 )-1Z55Z65 (Z14 )-1 -Z24 -Z34 (Z44 )-1Z54Z64 (Z13 )-1 -Z23 -Z33 (Z43 )-1Z53Z63 (Z12)-1 -Z22 -Z32 (Z42 )-1Z52Z62 (Z11 )-1 -Z21 -Z31 (Z41 )-1

Сообщение делится на 64-битовые блоки данных. Затем эти блоки делятся на четыре 16-битовых подблока: М1, М2, М3и М4. Последовательность таких четырех подблоков становится входом первого цикла алгоритма IDEA. Эти данные используются для всех восьми циклов. Как показано в табл. 14.11, в каждом цикле применяются разные множества из шести подключей. После завершения цикла второй и третий 16-битовые блоки данных переставляются. После завершения восьмого цикла четыре подблока дают окончательное выходное преобразование. Для упрощения записи в представлении Zx^(R) в табл. 14.10 и 14.11 опущены круглые скобки.

Каждый цикл состоит из шагов, показанных в табл. 14.12. Окончательные значения, полученные на шагах 11-14, образуют выход цикла. Два внутренних 16-битовых подблока данных переставляются (за исключением последнего цикла), затем эти четыре подблока составляют вход следующего цикла. Этот метод в общей сложности включает 8 циклов. После восьмого цикла окончательное выходное преобразование имеет следующий вид.

1. М1Z1^out (первый подключ выходного преобразования)

2. М2Z2^out

3. М3Z3^out

4. М4Z4^out

Таблица 14.12. Шаги каждого цикла алгоритма IDEA

1. М1Z1(R). 2. М2Z2(R). 3. М3Z3(R). 4. М4Z4(R). 5. К результатам шагов (1) и (3) применяется операция XOR[3]. 6. К результатам шагов (2) и (4) — операция XOR. 7. Результат шага (5) умножается на Z5(R). 8. Складываются результаты шагов (6) и (7). 9. Результат шага (8) умножается на Z6(R). 10. Складываются результаты шагов (7) и (9). 11. К результатам шагов (1) и (9) применяется операция XOR. 12. К результатам шагов (3) и (9) — операция XOR. 13. К результатам шагов (2) и (10) — операция XOR. 14. К результатам шагов (4) и (10) — операция XOR.

Пример 14.8. Первый цикл шифра ШЕЛ

Пусть сообщение (слово "HI") сначала нужно записать в шестнадцатеричной форме. Начнем с ASCII-кода, представленного на рис. 2.3, на котором бит 1 представляет собой самый младший разряд. Затем добавим равный нулю восьмой бит старшего разряда, который обычно используется для проверки четности, и выполним необходимое преобразование, взяв по четыре бита (порядок — от старшего разряда до младшего). Таким образом, буква "Н" в сообщении преобразуется в 0048, а буква "I" — в 0049. Для этого примера выберем 128-битовый ключ К0, выраженный восемью группами подключен из 4-разрядных шестнадцатеричных чисел: К0 = 0008 0007 0006 0005 0004 0003 0002 0001, где крайний правый подключ представляет самый младший разряд. Используя этот ключ и шифр IDEA, найдите выход цикла 1.

Решение

Сначала сообщение делится на 64-битовые блоки данных. Каждый из этих блоков затем делится на подблоки Mi, где i = 1, ..., 46, каждый из которых содержит 16-битовые или 4-значные шестнадцатеричные цифры. В этом примере длина сообщения "HI" равна всего 16 бит; следовательно, (используя шестнадцатеричное обозначение) М1 = 4849 и М =М3 =М4 = 0000. Сложение производится по модулю 2¹⁶, а умножение - по модулю 2¹⁶ + 1.128 - битовый ключ, определенный для первого цикла, делится на восемь 16-битовых подключен, начиная с младшей группы шестнадцатеричных кодов: Z1⁽¹⁾ = 0001, Z2⁽¹⁾ = 0002, Z3⁽¹⁾ = 0003, Z4⁽¹⁾ = 0004, Z5⁽¹⁾ = 0005, Z6⁽¹⁾ = 0006, Z1⁽²⁾ = 0007 и Z2⁽²⁾ = 0008.

Шаги, обозначенные в табл. 14.11, дают следующие результаты.

1. М1 Z1 = 48490001 = 4849.

2. М2 Z2 = 0000 + 0002 = 0002.

3. М3 Z3 = 0000 + 0003 = 0003.

4. М4 Z4 = 00000004 = 0000.

5. К результатам шагов (1) и (3) применяется операция XOR, в результате чего получится следующее: 4849 XOR 0003 = 484А.

0100 1000 0100 1001 (4849 из шестнадцатеричной системы переведено в двоичную)

XOR 0000 0000 0000 0011 (0003 из шестнадцатеричной системы переведено в двоичную)

_________________

0100 1000 0100 1010

Обратное преобразование в шестнадцатеричную систему дает следующее: 484А (где А — шестнадцатеричное обозначение двоичного числа 1010).

6. К результатам шагов (2) и (4) применяется операция XOR: 0002 XOR 0000 = 0002.

7. Результат шага (5) умножается на Z5: 484A0005 = 6971.

8. Результаты шагов (6) и (7) складываются: 0002 + 6971 = 6973.

9. Результат шага (8) умножается на Z6: 69730006 = 78В0.

10. Результаты шагов (7) и (9) складываются: 6971 + 78В0 = Е221.

11. К результатам шагов (1) и (9) применяется операция XOR: 4849 XOR 78B0 = 30F9.

12. К результатам шагов (3) и (9) применяется операция XOR: 0003 XOR 78B0 = 78В3.

13. К результатам шагов (2) и (10) применяется операция XOR: 0002 XOR E221 = Е223.

14. К результатам шагов (2) и (10) применяется операция XOR: 0000 XOR E221 = Е221.

Выход цикла 1 (результат шагов 11-14): 30F9 78ВЗ Е223 Е221. Перед началом цикла 2 переставляются два внутренних слова выхода цикла 1. Затем производится еще семь циклов и выполняется окончательное выходное преобразование.

14.6.2. Алгоритмы Диффи-Хэллмана (вариант Элгемала) и RSA

Для шифрования ключа сеанса PGP предлагает на выбор два алгоритма ключа шифрования общего доступа, RSA и протокол Диффи-Хэллмана (Diffie-Hellman) (вариант Элгемала (Elgamal)). Для алгоритмов RSA и Диффи-Хэллмана допустимый размер ключа составляет от 1024 до 4096 бит. Ключ размером 1024 бит считается безопасным для большинства сеансов обмена информацией. Защищенность алгоритма RSA (см. раздел 14.5.3) основана на сложности разложения на множители больших чисел.

Протокол Диффи-Хэллмана был разработан Вайтфилдом Диффи (Whitefield Diffe), Мартином Е. Хэллманом (Martin E. Hellman) и Ральфом С. Мерклем (Raph С Merkle) в 1976 году [19, 20] для обмена информацией по незащищенному каналу с помощью открытого ключа. Данный протокол основан на сложности задачи нахождения дискретного логарифма для конечных полей [21]. Он предполагает, что вычислить g^ab, зная только g^a и g^b, практически невозможно. Патент №4 200 770 (США), срок которого истек в 1997 году, содержит протокол Диффи-Хэллмана и его разновидности, такие как вариант Элгемала. Данный вариант, разработанный Тахером Элгемалом (Taher Elgamal), расширяет протокол Диффи-Хэллмана на шифрование сообщений. В PGP вариант Элгемала алгоритма Диффи-Хэллмана применяется для шифрования ключа сеанса.

14.6.2.1. Описание алгоритма Диффи-Хэллмана, вариант Элгемала

Протокол имеет два системных параметра п и g, которые являются общедоступными. Параметр n — это большое простое число, а параметр g — целое число, меньшее n, которое обладает следующим свойством: для любого числа р, лежащего между 1 и n -1 включительно, существует степень k числа g, при которой g^k = р mod п. Ниже описывается схема шифрования Элгемала [19, 21], позволяющая пользователю В посылать сообщение пользователю А.

• Пользователь А случайным образом выбирает большое целое число а (это частный ключ пользователя А).

• Открытый ключ пользователя А вычисляется следующим образом: у = g^a mod n.

• Пользователь В желает послать пользователю А сообщение M. Сначала пользователь В генерирует случайное число k, меньшее и.

• Пользователь В вычисляет следующие величины:

у1 = g^k mod n

у2= М (у^k mod n) (напомним, что у — это открытый ключ пользователя А).

• Пользователь В посылает пользователю А шифрованный текст '(уг, у2).

• После получения шифрованного текста (у1, у2) пользователь А вычисляет открытое сообщение M.

Пример 14.9. Применение алгоритма Диффи-Хэллмана (вариант Элгемала) для шифрования сообщения

Пусть общедоступными системными параметрами являются n=11 и g = 7. Предположим, что пользователь А в качестве частного ключа выбрал а = 2. Покажите, как вычисляется открытый ключ пользователя А. Покажите также, как пользователь В будет шифровать сообщение M = 13, которое должно быть отправлено пользователю А, и как пользователь А последовательно дешифрует полученный шифрованный текст.

Решение

Открытый ключ пользователя А (у = g^a mod n) вычисляется следующим образом: у = 7²mod 11 =5. Пользователь 5 желает послать пользователю А сообщение М= 13. В данном примере пусть пользователь В в качестве случайного значения k (меньшего п = 11) выбирает k = 1. Далее пользователь В вычисляет шифрованную пару.

y1= g^kmod n = 7¹ mod 11 = 7

y2 = M(y ^k mod n) = 13(5¹mod 11) = 135 = 65

Пользователь А получает шифрованный текст (7, 65) и вычисляет сообщение М.

14.6.3. Шифрование сообщения в системе PGP

Алгоритмы с частным ключом, применяемые PGP для шифрования сообщения, были представлены в разделе 14.6.1. Алгоритмы с открытым ключом, используемые PGP для шифрования ключа частного сеанса, были представлены в разделе 14.6.2. Чтобы проиллюстрировать технологию шифрования PGP, изображенную на рис. 14.20, рассмотрим следующий пример, объединяющий алгоритмы двух типов.

Пример 14.10. Использование алгоритмов RSA и IDEA для шифрования в PGP

Для шифрования ключа сеанса используем алгоритм RSA с открытым ключом с параметрами из раздела 14.5.3.1: п= pq = 2773, ключ шифрования е = 17, а ключ дешифрования d= 157. Ключом шифрования является открытый ключ получателя, а ключом дешифрования — частный ключ получателя. Используем ключ сеанса К0 = 0008 0007 0006 0005 0004 0003 0002 0001 и шифрованный текст 30F9 78ВЗ Е223 Е2216, представляющий сообщение "HI", из примера 14.8 (все величины представлены в шестнадцатеричной записи). (Отметим, что шифрованный текст был создан с использованием только одного цикла алгоритма IDEA. В реальной системе производится 8 циклов плюс выходное преобразование.) Зашифруйте ключ сеанса и покажите, какое сообщение должно передаваться.

Решение

Следуя описанию, приведенному в разделе 14.5.3.1, ключ сеанса будет шифроваться с помощью алгоритма RSA с открытым ключом получателя 17. Для удобства вычисления при помощи простого калькулятора преобразуем сначала ключ сеанса в группы, составленные из величин в десятичной записи. Согласно требованиям алгоритма RSA, значения, приписанные каждой группе, не должны превышать п-1 = 2772. Следовательно, выразим 128-битовый ключ в терминах 4-разрядных групп, где самая старшая (самая левая) группа будет представлять 7 бит и 11 групп будут представлять 11 бит каждая. Преобразование чисел из шестнадцатеричных в десятеричные можно рассматривать как двухэтапный процесс: (1) преобразование в двоичную систему и (2) переход к основанию 10. В результате получаем К0 = 0000 0032 0000 1792 0048 0001 0512 0064 0001 1024 0064 0001. Напомним, из уравнения (14.32) следует, что С = (М)' по модулю п, где М — одна из 4-разрядных групп К0. Левые крайние четыре группы шифруются следующим образом.

С12 = (0000)¹⁷mod 2773 = 0.

С11 = (0032)¹⁷mod 2773 = 2227.

С10 = (0000)¹⁷mod 2773 = 0.

С9 = (1792)¹⁷mod 2773 = 2704.

Эффективным способом модульного возведения в степень является использование алгоритма "Возведение в квадрат и умножение" (Square-and-Multiply — SM). Этот алгоритм [21] сводит число необходимых модульных умножений с е-1 почти до 2l, где l - число бит в двоичном представлении. Покажем использование алгоритма SM, шифруя одну из десятичных групп ключа сеанса (одиннадцатую группу справа М11 = 0032), где п = 2773 и е = 17. Для применения этого алгоритма сначала запишем число е в его двоичном представлении (1710 = 100012).

Вычисления даны в табл. 14.13. Используется математика по модулю n, в этом примере п = 2773. Второй столбец содержит двоичный код, где старший бит находится в строке 1. Каждая двоичная величина в этом столбце используется для контроля результата в столбце 3. Начальное значение, расположенное в столбце 3, строка 0, всегда равно 1. Далее результат в каждой строке столбца 3 зависит от бита в соответствующей строке столбца 2. Если этот бит равен "1", то результат предыдущей строки возводится в квадрат и умножается на открытый текст (для этого примера — 32). Если строка во втором столбце содержит "0", то значение соответствующей строки в столбце 3 равно квадрату значения в предыдущей строке. Окончательным значением является зашифрованный текст (С = 2227). Повторение этого метода для каждой из двенадцати десятичных групп, составляющих К0, дает шифрованный текст ключа сеанса: С = 0000 2227 0000 2704 0753 0001 1278 0272 0001 1405 0272 0001. Этот ключ сеанса (здесь он представлен в десятичной форме), зашифрованный с помощью алгоритма RSA, вместе с зашифрованным с помощью IDEA сообщением вида 30F9 78ВЗ Е223 Е221 (здесь оно представлено в шестнадцатеричной форме) может теперь передаваться через незащищенный канал.

Таблица 14.13. Алгоритм SM с открытым текстом = 32

Номер строки	Двоичное представление е (первым идет старший разряд)	Модульное умножение (модуль 2773)
0 1 2 3 4 5	1 0 0 0 1	1 1232= 32 322 = 1024 10242 = 328 3282 = 1728 1728232 = 2227

14.6.4. Аутентификация с помощью PGP и создание подписи

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

Поскольку алгоритмы с открытыми ключами работают достаточно медленно, PGP допускает разные методы проверки подлинности отправителя. Вместо трудоемкого процесса шифрования всего открытого сообщения, PGP предлагает шифрование профиля сообщения (message digest) фиксированной длины, созданного с помощью односторонней хэш-функции. Шифрование профиля сообщения производится посредством алгоритма открытого ключа. Этот метод, называемый цифровой подписью, изображен на рис. 14.22. Цифровая подпись используется для проверки подлинности как отправителя, так и сообщения. Проверка подлинности сообщения обеспечивает проверку того, что сообщение не было некоторым образом изменено. Данная технология основана на том, что если сообщение было изменено (т.е. было постороннее вмешательство), его профиль будет другим.

Рис. 14.22. Технология создания подписи, используемая PGP

PGP версии 2.6 использует алгоритм MD5 (Message Digest 5) для создания 128-битового профиля сообщения (или значения хэш-функции) открытого текста. Затем значение хэш-функции шифруется с помощью частного ключа отправителя и посылается с открытым текстом. Когда получатель принимает сообщение, он сначала дешифрует профиль сообщения, используя открытый ключ отправителя. Затем получатель действует на открытый текст хэш-функцией и сравнивает два профиля сообщения. Если они совпадают, подпись подлинная. На рис. 14.22 сообщение отправляется без шифрования (как открытый текст); впрочем, оно может быть зашифровано с помощью метода, изображенного на рис. 14.20.

14.6.4.1. МD5 и SНА-1

MD5 и SHA-1 являются хэш-функциями. Вообще, хэш-функция Н(х) принимает аргумент и возвращает строку h фиксированного размера, называемую значением хэш-функции (или профилем сообщения). Криптографическая хэш-функция обладает следующими свойствами.

1. Длина выхода фиксированна.

2. Значение хэш-функции относительно просто вычисляется.

3. Функция является односторонней; другими словами, ее трудно обратить. Для данного значения h вычислительно неосуществимо найти аргумент функции х.

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

Алгоритм MD-5, используемый PGP версии 2.6, создает 128-битовый профиль сообщения. За четыре цикла данный алгоритм разбивает текст на 512-битовые блоки. В каждом цикле используются разные нелинейные функции, включающие логические операторы И, ИЛИ, НЕ или исключающее ИЛИ. За цикл каждая функция применяется 16 раз. Кроме того, в каждом цикле используются сдвиги битов и скалярное сложение [19]. Ганс Доббертин (Hans Dobbertin) [18] определил, что в MD-5 возможны конфликты. В силу этих потенциальных недостатков PGP рекомендует Стандарт цифровой подписи (Digital Signature Standard — DSS), который использует алгоритм SHA-1 (Secure Hash Algorithm-1). Данный алгоритм (SHA-1) берет сообщение, длиной меньше 2⁶⁴ бит, и создает 160-битовый профиль сообщения. Алгоритм SHA-1 подобен MD-5 тем, что в каждом из 4 циклов используются различные нелинейные функции. В SHA-1 каждая функция применяется 20 раз в течение цикла. Кроме того, в SHA-1 используются разные скалярные сложения и сдвиги битов. Алгоритм имеет более медленное действие, чем MD-5, но больший профиль сообщения (160 бит в отличие от 128 бит) делает его более защищенным от криптоаналитических атак по методу грубой силы [19]. Метод грубой силы - это попытка подобрать профиль сообщения путем перебора входных комбинаций.

14.6.4.2. Стандарт цифровой подписи и алгоритм RSA

При создании цифровых подписей PGP версии 2.6 использует алгоритм RSA для шифрования значения, производимого хэш-функцией MD-5. Однако в версиях 5.0 и более поздних применяется стандарт цифровой подписи (DSS) института NIST [22]. Данный стандарт требует использования хэш-функции SHA-1. Значение этой функции затем шифруется с помощью алгоритма цифрового стандарта DSA (Digital Standard Algorithm). Подобно протоколу Диффи-Хэллмана, DSA основан на задаче взятия дискретного логарифма. (Подробно об алгоритме DSA рассказано в работе [22]).

Литература

1. Kahn D. The Codebreakers. Macmillan Publishing Company, New York, 1967.

2. Diffie W. and Hellman M. E. Privacy and Authentication: An Introduction to Cryptography. Proc. IEEE, vol. 67, n. 3, March, 1979, pp. 397-427.

3. Beker H. and Piper F. Cipher Systems. John Wiley & Sons, Inc., New York, 1982.

4. Denning D. E. R. Cryptography and Data Security. Addison-Wesley Publishing Company, Reading, Mass, 1982.

5. Shannon C. E. Communication Theory of Secrecy Systems. Bell Syst. Tech. J., vol. 28, October, 1949, pp. 656-715.

6. Hellman M. E. An Extension of the Shannon Theory Approach to Cryptography. IEEE Trans. Inf. Theory, vol. IT23, May, 1978, pp. 289-294.

7. Smith J. L. The Design of Lucifer, a Cryptographic Device for Data Communications. IBM Research Rep. RC-3326, 1971.

8. Feistel H. Cryptography and Computer Privacy. Sci. Am., vol. 228, n. 5, May, 1973, pp. 15-23.

9. National Bureau of Standards. Data Encryption Standard. Federal Information Processing Standard (FIPS), Publication n. 46, January, 1977.

10. United States Senate Select Committee in Intelligence. Unclassified Summary: Involvement of NSA in the Development of the Data Encryption Standard. IEEE Commun. Soc. Mag., vol. 16, n. 6, November, 1978, pp. 53-55.

11. Stallings W. Cryptography and Network Security. Second Addition, Prentice Hall, Upper Saddle River, NJ. 1998. (Столлингс В. Криптография и защита сетей. Принципы и практика, 2-е издание. М.: — Издательский дом "Вильямc", 2001. — 672 с.)

12. Diffie W. and Hellman M. E. New Directions in Cryptography. IEEE Trans. Inf. Theory, vol. 1722, November, 1976, pp. 644-654.

13. Rivest R. L., Shamir A. and Adelman L. On Digital Signature and Public Key Cryptosystems. Commun. ACM. Vol. 21, February, 1978, pp. 120-126.

14. Knuth D. E. The Art of Computer Programming, Vol. 2, Seminumerical Algorithms. 2nd ed., Addison-Wesley Publishing Company, Reading, Mass, 1981. (Кнут Д. Искусство программирования, т. 2. Получисленные алгоритмы, 3-е издание. — М.: Издательский дом "Вильяме", 2000. — 832 с.)

15. Mercal R. С. and Hellman M. E. Hiding Information and Signatures in Trap-Door Knapsacks. IEEE, Trans. Inf. Theory, vol. IT24, September, 1978, pp. 525-530.

16. Shamir A. A Polynomial Time Algorithm for Breaking the Basic Merkle-Hellman Cryptosystems. IEEE 23rd Ann. Symp. Found. Comput. Sci., 1982, pp. 145-153.

17. Zimmerman P. The Official PGP User's Guide. MIT Press, Cambridge, 1995.

18. PGP Freeware User's Guide, Version 6.5. Network Associates, Inc., 1999.

19. Schneier B. Applied Cryptography. John Wiley & Sons, New York, 1996.

20. Hellman M. E., Martin, Bailey, Diffie, W. and Merkle R. C. United States Patent 4, 200, 700: Cryptographic Apparatus and Method. United States Patent and Trademark Office, Washington, DC, 1980.

21. Stinson, Douglas. Cryptography Theory and Practice. CRC Press, Boca Raton, FL, 1995.

22. Digital Signature Standard (Federal Information Processing Standards Publication 186-1). Government Printing Office, Springfield, VA, December, 15, 1998.

Задачи

14.1. Пусть X — целая переменная, представленная 64 бит. Вероятность попадания X в интервал (0, 2¹⁶ - 1) равна 1/2, вероятность попадания X в интервал (2¹⁶, 2³² - 1) — 1/4, а вероятность попадания X в интервал (2³², 2⁶⁴ - 1) — 1/4. Внутри каждого интервала значения равновероятны. Вычислите энтропию X.

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

Утро: P(C) =, P(П)=, Р(Д) =, Р(Л) =

День: P(С) = , P(П) = , P(Д)= , P(Л)=

а) Найдите энтропию сообщения о погоде.

б) Найдите энтропию сообщения при указании времени дня.

14.3. Гавайский алфавит состоит только из 12 букв — гласные а, е, i, о, u и согласные h, k, l, m, n, p, w. Предположим, что каждая гласная встречается с вероятностью 0,116, а каждая согласная — с вероятностью 0,06. Предположим также, что среднее число бит информации, попадающих на каждую букву, такое же, как и в английском языке. Вычислите расстояние единственности для зашифрованного гавайского сообщения, если ключевая последовательность состоит из случайной перестановки 12 букв алфавита.

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

а) Каждый ключевой символ может представлять собой одну из 26 букв алфавита (повторения допускаются).

б) Ключевые символы не могут повторяться.

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

14.6.

а) Найдите расстояние единственности для системы DES, которая шифрует 64-битовые блоки (восемь символов алфавита) с помощью 56-битового ключа.

б) Как отразится на расстоянии единственности увеличение ключа до 128 бит?

14.7. На рис. 14.8 и 14.9 чередуются Р- и S-блоки. Является ли это более безопасным, нежели если бы сначала были сгруппированы все Р- блоки, а затем все S-блоки? Ответ аргументируйте.

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

14.9. Рассмотрим открытое 10-битовое сообщение в виде последовательности 0101101001 и соответствующую ему последовательность шифрованного текста 0111011010, где крайний правый бит является самым ранним. Опишите пятиразрядный линейный регистр сдвига с обратной связью, производящий ключевую последовательность, и укажите начальное состояние регистра. Имеет ли выходная последовательность максимальную длину?

14.10. Используя параметры примера 14.5 и следуя алгоритму RSA, вычислите ключ шифрования е, если в качестве ключа дешифрования выбрано число 151.

14.11. Даны e иd, такие, что ed по модулю = 1, и сообщение, которое зашифровано как целое число М из интервала (0, n-1), такое что НОД(М, n) = 1. Докажите, что (М^e по модулю п)^d по модулю n = М.

14.12. Используйте схему RSA для шифрования сообщения М = 3. В качестве простых чисел возьмите p = 5 и q = 7. Ключ дешифрования d=11. Вычислите значение ключа шифрования е.

14.13. Используется схема RSA.

а) Пусть простыми числами являются р=7 и q=11. Перечислите пять допустимых значений ключа дешифрования d.

б) Пусть простыми числами являются р = 13 и q = 31, а ключ дешифрования d=31. Найдите ключ шифрования е и опишите его использование для шифрования слова "DIGITAL".

14.14. Используйте схему Меркла-Хэллмана с открытым ключом и быстровозрастающим вектором а' = 1, 3, 5, 10, 20. Воспользуйтесь следующими дополнительными параметрами: большое простое число М = 51, случайное число W= 37.

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

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

14.15. С помощью протокола Диффи-Хэллмана (вариант Элгемала) зашифруйте сообщение М = 7. Параметры системы: n = 17 и g = 3. Частный ключ получателя: а = 4. Определите открытый ключ получателя. Для шифрования сообщения со случайно выбранным k используйте k = 2. Проверьте точность данного шифрования с помощью частного ключа получателя.

14.16. Найдите шестнадцатеричное значение сообщения "по" после одного цикла алгоритма IDEA. Ключ сеанса (шестнадцатеричная запись) = 0002 0003 0002 0003 0002 0003 0002 0003, где крайняя правая 4-разрядная группа представляет подключ Z1. Пусть каждый символ ASCII для сообщения "по" представлен 16-битовым подблоком данных, где "п" = 006Е и "о" = 006F.

14.17. В примере 14.10 ключ сеанса для алгоритма IDEA шифруется с использованием алгоритма RSA. Результирующим ключом сеанса шифрования (в десятичной записи) был 0000 2227 0000 2704 0753 0001 1278 0272 0001 1405 0272 0001, где наименее значимой (крайней правой) группой является 1. Используя ключ дешифрования, дешифруйте группу 11 этого ключа сеанса с помощью алгоритма SM (см. пример 14.10).

Вопросы для самопроверки

14.1. В чем состоят два основных требования, предъявляемые к полезным криптосистемам (см. раздел 14.1.2)?

14.2. Шеннон предложил две концепции шифрования — смешение (confusion) и диффузия (diffusion). Объясните значение этих терминов (см. раздел 14.3.1).

14.3. Объясните, почему при необходимости высокого уровня секретности не должен использоваться линейный регистр сдвига с обратной связью (см. раздел 14.4.2)?

14.4. Объясните основное отличие между общепринятыми криптосистемами и криптосистемами с открытым ключом (см. раздел 14.5).

14.5. Опишите шаги шифрования сообщения при использовании стандарта шифрования данных (DES). Насколько отличаются эти операции при "тройном" DES (см. разделы 14.3.5 и 14.6.1.1)?

14.6. Опишите этапы шифрования сообщения с помощью PGP версии 2.6 (см. раздел 14.6.1.3).