их комбинации, способны обеспечить достаточно высокую степень безопасности. Одним из таких алгоритмов является Data Encryption Standard (DES), разработанный фирмой IBM и принятый в 1977 году в качестве Федерального стандарта шифрования данных США [16.18].

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

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

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

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

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

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

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

В [16.10] приведен пример, в котором для определения, является ли число из 130 цифр простым, потребовалось 7 минут вычислений на некотором компьютере, тогда как для поиска (на том же компьютере) двух простых множителей числа, получаемого

умножением двух простых чисел, состоящих из 63 цифр, потребуется около 40 квадрильонов лет (1 квадрильон = 1 ООО ООО ООО ООО 000).

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

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

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

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

d * е = 1 modulo (р - 1) * (g - 1)

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

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

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

С - Р modulo г

6. Для расшифровки части зашифрованного текста С замените его открытым текстом Р, определяемым согласно следующей формуле.

Р ~ modulo г

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

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

Несмотря на это некоторые сомнения существуют и в отношении RSA-схемы. Работа [16.10] была опубликована в 1977 году, а в 1990 году Арьену .Пенстра (Arjen Lenstra) и Мару Ма-нассе (Mark Manasse) удалось успешно разложить на простые множители число из 155 цифр [16.22]. Они оценили, что выполненные вычисления, в которых участвовала тысяча компьютеров, эквивалентны расчету на одном компьютере со скоростью 1 млн инструкций в секунду в течение 273 лет. Данное число из 155 цифр было девятым числом Ферма: 2+1 (обратите внимание, что 512 = 2). См. также работу [16.12], в которой сообщается о совершенно другом - и успешном - подходе к расшифровке алгоритма RSA.

Пример. Y[yсть р = 3, g = 5; тогда г = 15, а произведение (р-1) * (g-l) = 8. Пусть е = 11 (простое число, большее р и q). Вычислим d согласно следующей формуле.

d * 11 = 1 modulo 8

В результате получим d = 3.

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

С = modulo г = 13 modulo 15 = 1 792 160 394 037 modulo 15 = 7

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

Р = modulo г = 7 modulo 15 = 343 modulo 15

- 13 I

Поскольку числа evid взаимно обратны, в методах шифрования на основе открытого ключа также можно подписывать отсылаемые сообщения, что позволит получателю иметь уверенность в том, что данное сообщение было получено именно от того лица, которое объявлено его отправителем (т.е. такая подпись не может быть подделана). Допустим, что пользователи А и В общаются друг с другом с помощью метода шифрования на основе открытого ключа. Пусть они предали гласности по одному алгоритму шифрования (с включением в каждый из них соответствующего ключа шифрования), но хранят в секрете друг от друга алгоритм и ключ расшифровки. Пусть алгоритмы шифрования сообщений ЕСА и ЕСВ используются для шифрования сообщений, посылаемых пользователям Л и В соответственно, а отвечающими им алгоритмами расшифровки являются алгоритмы DCA и DCB. Следует отметить, что алгоритмы шифрования и расшифровки ЕСА и DCA, как и алгоритмы ЕСВ и DCB, являются взаимно обратными.

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

С = ЕСВ ( DCA ( Р ) )

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

ЕСА ( DCB ( С ) )

= ЕСА ( DCB ( ЕСВ ( DCA ( Р ) ) ) )

= ЕСА ( DCA ( Р ) ) поскольку DCB и ЕСВ взаимно исключаются = Р поскольку ЕСА и DCA взаимно исключаются