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

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]).