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

Приведенный выше пример основан на использовании процедуры подстановки: ключ шифрования применялся для того, чтобы определить, какой символ зашифрованного тек­ста следует подставить вместо каждого символа открытого текста. Подстановка — один из двух основных традиционно используемых способов шифрования, в качестве второго выступает процедура перестановки, когда символы открытого текста просто переставля­ются в несколько иной последовательности. Ни один из этих способов не является безо­пасным сам по себе, но алгоритмы на основе их комбинации могут обеспечить достаточно высокую степень безопасности. Одним из таких алгоритмов является довольно общеизве­стный стандарт шифрования данных (Data Encryption Standard —DES), который был впервые принят в качестве федерального стандарта США в 1977 году [15.3].

Согласно этому стандарту открытый текст делится на блоки по 64 бита и каждый блок шифруется с помощью 64-битового ключа (в действительности этот ключ со­стоит из 56 бит данных плюс 8 бит четности, так что при этом существует не 2⁶⁴, а только 2⁵⁶ возможных ключей.) Сначала блок шифруется с помощью перестановки, затем уже перемешанный таким образом блок подвергается последовательности из 16 сложных шагов подстановки, и, наконец, к нему еще раз применяется процедура пере­становки, обратная начальной, которая и приводит к получению заключительного ре­зультата. Подстановка на i-м шаге контролируется непосредственно не исходным ключом шифрования К, а ключом Ki, который вычисляется на основе значений К и i. Более подробно этот материал излагается в [15.3].

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

Шифрование на основе открытого ключа

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

Первоначальная идея использования такой методики принадлежит Диффи и Хельману (Diffie and Hellman) [15.7], однако здесь для демонстрации этой методики будет описан подход, развитый Райвестом, Шамиром и Адлеманом (Rivest, Shamir, Adieman) [15.14]. В основе этого подхода, названного по первым буквам их фамилий RSA-схемой, лежит два приведенных ниже факта.

1. Существует быстрый алгоритм определения, является ли данное число простым.

2. Не существует быстрого алгоритма разложения данного составного числа (т.е. числа, которое не является простым) на простые множители.

В [15.10] приведен пример, в котором для определения, является ли данное число из 130 цифр простым числом, потребовалось 7 минут вычислений на некотором ком­пьютере, тогда как для поиска (на том же компьютере) двух простых множителей числа, получаемого умножением двух простых чисел, состоящих из 63 цифр, потре­буется около 40 квадрильонов лет (1 квадрильон = 1 000 000 000 000 000).

RSA-схема включает приведенную ниже последовательность действий.

1. Выберите два произвольных и разных больших простых числа p и q, а затем вы­числите их произведение r = р * q.

2. Выберите произвольное большое целое число е, которое является взаимно простым по отношению к произведению (р-1) * (q-1), а также служит ключом шифрования.

Замечание. Выбрать число е достаточно просто: например, для него подойдет лю­бое простое число, которое больше чисел р и q.

3. Выберите в качестве ключа расшифровки число d, которое является "обратным относительно умножения" на е по модулю (р-1) * (q-1), т.е. такое число, для ко­торого выполняется соотношение

d * е = 1 modulo (р - 1) * (q - 1).

Алгоритм вычисления d для заданных чисел е, р и q достаточно прост и полно­стью приведен в [15.14].

4. При этом могут быть преданы огласке числа r и е, но не d.

5. Для шифрования части открытого текста Р (который для простоты рассматривает­ся как целое число, меньше r) замените его зашифрованным текстом согласно формуле

С = P^e modulo r. //Р в степени е//

6. Для расшифровки части зашифрованного текста С замените его открытым тек­стом согласно формуле

Р = C^d modulo r.

В [15.14] доказывается работоспособность этой схемы, т.е. возможность расшиф­ровки текста С с использованием числа d для восстановления исходного открытого текста Р. Однако, как упоминалось ранее, вычисление (/для известных чисел r и е (а не р и q) практически неосуществимо. Поэтому любой пользователь может зашифро­вать открытый текст, но только пользователи с санкционированным доступом (обладающие числом d) могут расшифровать зашифрованный текст.

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

Пример. Пусть р = 3, q = 5, тогда r = 15, а произведение (р-1)* (q-1)=8. Пусть е = 11 (простое число, большее р и q). Вычисляя d согласно формуле

d * 11 = 1 modulo 8, получим d=3.

Теперь допустим, что открытый текст Р состоит из целого числа 13, тогда зашиф­рованный текст С будет иметь следующий вид:

С = 13¹¹ modulo 15 . = =1,792,160,394,037 modulo 15 =7

А исходный открытый текст Р может быть получен с помощью обратной процедуры:

Р = 7³ modulo 15 = 343 modulo 15 = 13

Поскольку числа е и d взаимно обратны, то в методах шифрования на основе открытого ключа также можно "подписывать" сообщения, чтобы получатель был уверен в том, что сообщение получено именно от того лица, которым оно отправ­лено (т.е. такая "подпись" не может быть подделана). Допустим, что пользователи А и В общаются друг с другом с помощью метода шифрования на основе открытого ключа. Пусть они предали гласности по одному алгоритму шифрования (с включе­нием в каждом из них соответствующего ключа шифрования), но хранят в секрете друг от друга алгоритм и ключ расшифровки. Например, пусть алгоритмы шифро­вания А и В названы соответственно АША и АШВ, а соответствующие алгоритмы расшифровки — АРА и АРВ. Следует отметить, что алгоритмы шифрования и расшифровки АША и АРА, так же как и алгоритмы АШВ и АРВ, являются взаимно обратными.

Теперь предположим, что пользователь А хочет послать часть открытого текста Р пользователю В. Вместо вычисления результата АШВ(Р) и отправки его пользо­вателю В, пользователь А применяет для открытого текста Р сначала алгоритм расшифровки АРА, а затем зашифровывает результат и в зашифрованном виде С передает его:

С = AШВ ( АРА ( Р ) ).

После получения зашифрованного текста С пользователь В применяет алгоритм расшифровки АРВ, а затем алгоритм шифрования АША с получением в результате части открытого текста Р:

АША ( АРВ ( С ) )

= АША ( АРВ ( АШВ ( АРА ( Р ) ) ) )

= АША ( АРА ( Р ) ) — поскольку AШВ и АРВ взаимно исключают друг друга

= Р — поскольку АРА и AША взаимно исключают друг друга

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