7.1.6. Стандарты шифрования. Российский стандарт гост 28147-89.

В Российской Федерации установлен государственный стандарт (ГОСТ 28147—89) на алгоритмы криптографического преобразования информации в ЭВМ, вычислительных комплексах и вычислительных сетях. Эти алгоритмы допускается использовать без ограничений для шифрования информации любого уровня секретности. Алгоритмы могут быть реализованы аппаратными и программными способами.

Стандартом определены следующие алгоритмы криптографического преобразования информации:

• простая замена;

• гаммирование;

• гаммирование с обратной связью;

• выработка имитовставки.

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

Криптосистема rsa

Название криптосистемы образовано из первых букв фамилий предложивших ее авторов (Rivest R., Shamir A., Adleman L. A method for obtaining digital signatures and pablic-key cryptosystems. Commun. ACM, v.21, N2, 1978).

Система относится к блочным экспоненциальным системам, так как каждый блок М открытого текста рассматривается как целое число в интервале (0,..., n-1) и преобразуется в блок С следующим открытым преобразованием

C = E (e,n) (M) = M^e (mod n),

где E(e,n) - преобразование, а (e,n) - ключ зашифрования.

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

M = D (d,n) (C) = C^d (mod n),

где D(d,n) - преобразование, а (d,n) - ключ расшифрования.

В основе этого метода лежит довольно сложное теоретическое обоснование. Числа e и d связаны с n определенной зависимостью и существуют рекомендации по выбору ключевых элементов на основе простых чисел. Если взять два простых числа p и g, определить n = pхq, то можно определить пару чисел e и d, удовлетворяющих заданным условиям. Если сделать открытыми числа e и n, а ключ d (и обязательно p и g) держать в секрете - то предложенная система является RSA-криптосистемой открытого шифрования. Очевидно, ее стойкость определяется сложностью операции извлечения из С корня степени е по модулю n.

Рассмотрим основные этапы реализации алгоритма RSA.

1. Отправитель вычисляет n = p х qи M=(p-1)(q-1).

2. Затем он выбирает случайное целое число e, взаимно простое с М и вычисляет d, удовлетворяющее условию

ed = 1 (mod M).

Напомним, что два числа являются взаимно простыми, если их HOD =1. Числа а и b имеют HOD d, если d делит и а и b и максимальный среди таких чисел.

3. После этого он публикует е и n как свой открытый ключ шифрования, сохраняя d, как закрытый (секретный) ключ.

4. Рассмотрим теперь числа eиd. Предположим, что мы знаем одно из них и знаем соотношение, которым они связаны. Мы могли бы легко вычислить второе число, однако мы не знаем чиселpиq. Следовательно можно одно из чисел подарить кому-нибудь вместе с n и попросить его посылать нам сообщения следующим образом.

5. Сообщение представить как векторы (блоки) длины l

X= (x₁,x₂...,x_l)

0<x_i< M;

6. Каждое x_iвозвести в степень e по mod n.

7. Прислать нам Y=(x₁^e(mod n), x₂^e(mod n),...,x_l^e(mod n)).

Обозначим t=y_i=х_i^e(mod n) и рассмотрим расшифрование полученной информации.

Для этого возведем полученное число t в степень второго числа пары - d:

R=t^d(mod n) = x^e (mod n)^d(mod n) = x^ed (mod n).

В соответствие с п.2 соотношение ed=1(mod M). а это означает, что ed-1 делится нацело на (p-1)(q-1), т.е. ed=1+a(p-1)(q-1),

где а - целое число.

Утверждается, что

х^ed(mod n) =x.

Действительно,

x^ed(mod n) = x^{1+a(p-1)(q-1)} (mod n)

Учитывая,что

x^p-1= 1 mod p, x^q-1= 1 modq(эти соотношения доказываются как малая теорема Ферма, например в /10/) получим

x^(p-1)(q-1) = 1(mod pq)

x^{1+a(p-1) (g-1)}(mod n) = x, т.к.

x^{a(p-1) (q-1)}= 1(mod pq), из-за того,

что x^{(p-1) (q-1)}= 1(mod pq),

x mod n = x, так как x<M.

Что и требовалось доказать.