2.5. Асимметричные криптосистемы

2.5.1. Схема шифрования Эль Гамаля

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

Последовательность действий пользователя:

1. Получатель сообщения выбирает большое, простое число P и большое целое число G, причем P > G.

2. Получатель выбирает секретный ключ - случайное целое число X < P.

3. Вычисляется открытый ключ Y= G ^x mod P.

4. Получатель выбирает случайное целое число K, 1< K< P-1, такое, что числа К и (Р-1) являются взаимно простыми.

5. Шифрование сообщения (M): a= G^K mod P, b=Y ^K M mod P, где пара чисел (a,b) является шифротекстом.

6. Надо придумать сообщение М, зашифровать его, а потом с помощью секретного ключа Х расшифровать сообщение.

Шифрование

1. Допустим что нужно зашифровать сообщение .

2. Произведем генерацию ключей :

   1. пусть . Выберем- случайное целое числотакое,что.

   2. Вычислим .

   3. Итак , открытым является тройка ,а закрытым ключом является число.

3. Выбираем случайное целое число такое, что 1 < k < (p − 1). Пусть.

4. Вычисляем число .

5. Вычисляем число .

6. Полученная пара является шифротекстом.

Расшифрование

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

2. Вычисляем M по формуле :

3. Получили исходное сообщение .

2.5.2. Криптосистема шифрования данных rsa

Предложена в 1978 году авторами Rivest, Shamir и Aldeman и основана на трудности разложения больших целых чисел на простые сомножители.

Последовательность действий пользователя:

1. Получатель выбирает 2 больших простых целых числа p и q, на основе которых вычисляет N=pq; M=(p-1)(q-1).

2. Получатель выбирает целое случайное число d, которое является взаимопростым со значением М, и вычисляет значение е из условия ed=1/(mod M).

3. d и N публикуются как открытый ключ, е и М являются закрытым ключом.

4. Если S –сообщение и его длина: 1<Len(S)<N, то зашифровать этот текст можно как S’=S^d(mod N), то есть шифруется открытым ключом.

5. Получатель расшифровывает с помощью закрытого ключа: S=S’^e(mod N).

6. Представить шифруемое сообщение как последовательность целых чисел в диапазоне 0…32. Пусть буква А изображается числом 1, буква Б- числом 2, буква В- числом 3 и т.д. Тогда сообщение будет принимать вид числовой последовательности, которое зашифровывается с помощью открытого ключа. Надо расшифровать его с помощью закрытого ключа.

Зашифруем сообщение «САВ». Для простоты будем использовать маленькие числа (на практике применяются гораздо большие).

1. Выберем p=3 и q=11.

2. Определим n=3*11=33.

3. Найдем (p-1)(q-1)=20. Следовательно, в качестве d, взаимнопростое с 20, например, d=3.

4. Выберем число е. В качестве такого числа может быть взято любое число, для которого удовлетворяет соотношение (е*3)(mod20)=1, например 7.

5. Представим шифруемое сообщение как последовательность целых чисел с помощью отображения: А1, В2, С3. Тогда сообщение принимает вид (3,1,2). Зашифруем сообщение с помощью ключа {7,33}. ШТ1 = (3⁷) (mod 33) = 2187 (mod 33) = 9, ШТ2 = (1⁷) (mod 33) = 1 (mod 33) = 1, ШТ3 = (2⁷) (mod 33) = 128 (mod 33) = 29.

6. Расшифруем полученное зашифрованное сообщение (9,1,29) на основе закрытого ключа {3,33}: ИТ1 = (9³) (mod 33) = 729 (mod 33) = 3, ИТ2 = (1³) (mod 33) = 1 (mod 33) = 1, ИТ3 = (29³) (mod 33) = 24389 (mod 33) = 2.

Итак в реальных системах алгоритм RSA реализуется следующим образом: каждый пользователь выбирает два больших числа, и в соответствии с описанным выше алгоритмом выбирает два простых числа e и d. Как результат умножения первых двух чисел (p и q) устанавливается n.

{e,n} образует открытый ключ, а {d,n} – закрытый (хотя можно взять и наоборот).

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