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

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

Зашифруем сообщение "ANASTASIA".

Сначала получим ключи:

1. Случайным образом выбираются два секретных простых числа p и q

таких, что p ≈ q

p = 5, q = 7.

2. Вычисляется их произведение r = p*q

r = 5*7 = 35.

3. Вычисляется функция Эйлера для r. Функция Эйлера для

произвольного x представляет собой число взаимно простых с x чисел меньших, чем x. Для простого x φ(x) = x–1, а для числа представляющего собойпроизведение двух простых чисел x = p*q: φ(x) = (p–1)*(q–1)

φ(r) = (p–1)*(q–1) = 4*6 = 24.

4. Выбирается целое значения открытой экспоненты e такой, что 1<e<φ(r)

и (e, φ(r)) = 1, например е=5.

5. Вычисляется значение секретной экспоненты d, которая должна

удовлетворять условию (e*d) mod φ(r) = 1 (т.е., d является мультипликативной инверсной по модулю φ(r) для e)

(5*5)mod24=1.

Таким образом, ключом шифрования Ko является пара значений (5,35), а

ключом дешифрования Kc – (5, 35).

Перед шифрованием исходное сообщения M необходимо разбить на

блоки M = m1, m2, m3…, где mi   представляет собой число в диапазоне от 3 до 28.

Сам процесс шифрования открытым ключом Ko = (e, r) последовательности

чисел mi происходит согласно формуле:

= () mod r, где последовательность чисел ci представляет собой шифротекст.

=mod35=33

= mod35=11

==33

= mod35=21

= mod35=22

===33

==21

= mod35=16

===33

Чтобы расшифровать эти данные секретным ключом Kc = (d, r),необходимо выполнить следующие вычисления:

mi = () mod r.

= mod35=3

= mod35=16

==3

= mod35=21

= mod35=22

==3

==21

= mod35=11

==3

В результате будет получено множество чисел mi, которые представляют

собой исходный текст ANASTASIA.

Криптосистема Эль-Гамаля

Зашифровать первые три буквы моего имени:

=3                     =16                    =3

Данная криптосистема, предложенная в 1984 году, лежит в основе стандартов электронной цифровой подписи в США и России.

Как и для алгоритма RSA, для криптосистемы Эль-Гамаля необходимо

перед шифрованием вычислить пару открытый/закрытый ключ. Это

происходит по следующему алгоритму:

1. Генерируется случайное простое число p

p=11.

2. Выбирается произвольное целое число g, являющееся первообразным

корнем по модулю p. Первообразным корнем по модулю некоторого числа p

является целое число g такое, что gφ(p) = 1 mod p и gl ≠ 1 mod p при 1≤l≤φ(p)–1

g=2.

3. Выбирается случайное целое положительное число x< p−1, не равное 1

x=5.

4. Вычисляется y = mod p=mod11=10.

Открытым ключом Ko является тройка (11, 2, 10), закрытым ключом Kc −

число x=5.

Далее зашифруем сообщения =3, =16, =3, для чего сгенерируем случайное

число k = 3, взаимно простое с p−1, и вычислим  значения a и b:

a = mod p

b = m mod p

=mod11=8    =*3mod11=8

=8                     =*16mod11=6

=8                     =*3mod11=8

где m является исходным сообщением, а пара чисел (a, b) – шифротекстом.

Зная закрытый ключ x, исходное сообщение можно вычислить из

шифротекста (a, b) по формуле:

=[*]modp=8*mod11=3

=6*mod11=16

==3

Криптосистема Рабина

Зашифровать 9-ю букву моего имени:

m=11

Генерация ключей в криптосистеме Рабина происходит следующим

образом:

1. Выберем два простых числа p = 19 и q = 23. При этом 19 mod 4 = 3 и

23 mod 4 = 3. Т.е. условие p ≡ q ≡ 3 mod 4 выполняется.

2. Вычислим наш открытый ключ: n = p*q = 19*23 = 437.

Далее зашифруем сообщение m = 11. Для этого вычислим по формуле

c = m*(m+b) mod n = 11*(11+213) mod437 = 279. Таким образом, получили

шифротекст c = 279.

Для расшифровки сначала вычислим D по формуле:

D = + 4c(mod n) = + 4*279(mod 437) = 163.

Далее для вычисления квадратного корня из D=163 по модулю составного

числа n = p*q выполним следующие действия:

1. Вычислим mp и mq :

modp=mod19=7

modq=mod23=18

2. Вычислим значения yp и yq таких, что yp*19+yq*23 = 1 по расширенному

алгоритму Евклида. Для этого принимаем a = 11, b = 19. Тогда на выходе

получим, что yp = x1 = -6, а yq = y1 = 5.

3. Далее вычисляем квадратные корни из D по модулю n :

Тогда получим, что d1 = 373, d2 = 64, d3 = 235, d4 = 202. При подстановке

третьего значения в получаем исходный текст:

m=modn=mod437=11.

Министерство образования Республики Беларусь

Учреждение образования

«Белорусский государственный университет информатики и радиоэлектроники»

Отчет по дисциплине «Криптография и охрана коммерческой информации»

на тему «Криптографические системы с открытым ключом»

                                                                                                     Выполнила:

ст. гр. 772202

Смирнова А.В.

Минск 2011