Лекция по алгоритму RSA и немного математики

1. Корабельников Владислав Аркадьевич к.т.н.

Прикладная информатика
ЗАЩИТА ИНФОРМАЦИИ (Второй семестр)
ЛЕКЦИЯ N 1
Краткое повторение. Алгоритмы RSA.
RSA (аббревиатура от фамилий Rivest, Shamir и Adleman)
1

2.

НЕМНОГО ИЗ МАТЕМАТИКИ
2

3.

3

4.

Алгоритм Евклида нахождения НОД
Пример
4

5. Алгоритм RSA (Rivest, Shamir и Adleman ) и DH

Алгоритм RSA во многом схож с алгоритмом Диффи-Хеллмана.
Принципиальное различие:
1) Алгоритм DH основан на использовании односторонней функции;
2) Алгоритм RSA основан на использовании односторонней функции с
«лазейкой/потайным входов» (Trapdoor).
Односторонняя функция с потайным входом (англ. trapdoor function, TDF).
RSA — криптографический алгоритм с открытым ключом, основывающийся
на вычислительной сложности задачи факторизации больших полупростых чисел.
Криптосистема RSA стала первой системой, пригодной и для шифрования , и
для цифровой подписи.
Алгоритм используется в большом числе криптографических приложений,
включая PGP, S/MIME, TLS/SSL, IPSEC/IKE и других

6.

Односторонняя функция с потайным входом (лазейкой) — это особый вид
односторонней функции. Она становится легко обратимой, если известен специальный
секрет — «лазейка».
Без лазейки: Вычислить обратное значение функции сложно.
С лазейкой: Обладая секретной информацией, обратить функцию становится
легко.
6

7.

«Лазейка» в RSA позволяет создать систему с двумя ключами:
Открытый (публичный) ключ — известен всем ключ, используется
для шифрования или проверки подписи.
Обозначается буквой e - открытой экспонентой (англ. public exponent).
Закрытый (приватный) ключ — хранится в секрете владельцем, используется
для расшифрования или создания подписи. Является той самой «лазейкой».
d называется секретной экспонентой. Он используется для расшифровки и должен
храниться в секрете получателем.
d — число, мультипликативно обратное к числу e по модулю φ(n)-(функцияс Эйлера), то
есть число, удовлетворяющее сравнению: d ⋅ e ≡ 1 (mod φ(n)).
Обычно d вычисляется при помощи расширенного алгоритма Евклида. Пара (d, n) играет
роль закрытого ключа RSA (англ. RSA private key)
Безопасность всей системы держится на том, что
ключу невозможно вычислить закрытый за приемлемое время.
по
открытому
7

8.

RSA-ключи генерируются получателем следующим образом (1)
8

9.

RSA-ключи генерируются получателем следующим образом (2)
8) Шифрование сообщения m происходит с помощью открытого ключа (e , n) и
реализуется по формуле
c=me mod n.
9) Дешифрование происходит с помощью закрытого ключа (d , n) и реализуется
по формуле
m=cd mod n.
9

10. Пример 1 генерации ключей RSA.

1. Выбрать два простых числа, например,
2. Вычислить
p 3, q 7
n p q 3 7 21,
( p 1) (q 1) 2 6 12
3. Выбрать число e (1< e < ), которое не имеет общих делителей с :
e 5
4. Найти число d, для которого при некотором целом k выполняется
d e k 1
условие:
d 17 :
• Открытый ключ:
• Секретный ключ:
17 5 7 12 1
(e, n) (5,21)
(d , n) (17,21)
10

11. Применение алгоритм RSA

(e, n)
Шифрование: открытый ключ
1. Сообщение – последовательность чисел в интервале [0,n – 1].
2. Для каждого числа вычислить код
y x mod n
e
Расшифровка: секретный ключ
( d , n)
Для каждого кода вычислить число исходного сообщения:
x y mod n
d
11

12.

Шифрование и расшифрование
Предположим, Боб хочет послать Алисе сообщение m. Сообщениями являются целыми числами от 1 до n-1.
12

13. Пример шифрования и расшифровки алгоритмом RSA. Сгенерированы открытый ключ и закрытый ключ

Сообщение: 1 2 3
Шифрование:
открытый ключ
(e, n)
(5,21)
1 15 mod 21 1
2 25 mod 21 32 mod 21 11
5
3 3 mod 21 243 mod 21 12
зашифрованное сообщение: 1 11 12
Расшифровка:
секретный ключ
(d , n) (17,21)
1 117 mod 21 1
17
11 11 mod 21 2
12 1217 mod 21 3
расшифрованное сообщение: 1 2 3
13

14.

Данная схема на практике не используется по причине того, что она не
является практически надёжной (semantically secured).
Действительно, односторонняя функция E(m) является детерминированной —
при одних и тех же значениях входных параметров (ключа и сообщения) выдаёт
одинаковый результат. Это значит, что не выполняется необходимое условие
практической (семантической) надёжности шифра.
14

15.

Алгоритм шифрования RSA с использованием сеансового ключа
Более надёжным является смешанный алгоритм шифрования, в котором сначала
шифруется сеансовый ключ, а потом уже с его помощью участники шифруют свои
сообщения симметричными системами.
После завершения сеанса сеансовый ключ, как правило, уничтожается.
15

16.

Алгоритм шифрования RSA с использованием сеансового ключа
16

17.

Пример использование RSA в системах клиент-банк
1) Первый шаг делает получатель сообщения, генерируя два огромных простых числа p и q и устанавливая
значение N = pq, причем p − 1 и q − 1 не делились на 3.
2) Получатель хранит p и q в строжайшем секрете, но выдает N любому , кто спросит.
3) У отправителя есть секретное сообщение x, которое он хочет отправить получателю. Отправитель вычисляет x3
по модулю N и отправляет его получателю. x3 mod N
4) Получателя может восстановить сообщение. Он знает p и q, коэффициенты N. Получатель сначала находит
целое число k, такое, что 3k = 1 mod (p − 1) (q − 1) с помощью алгоритма Евклида, а затем принимает
(x3)k mod N = x3k mod N = x.
17

18. Пример 2 генерации ключей.

1) Выберем р=3 и q=11.
2) Определим n=3*11=33.
3) Найдем (р-1)*(q-1)=20. Следовательно в качестве e выберем любое число, которое
является взаимно простым с числом 20, например e=3.
4) Выберем число d. В качестве такого числа может быть взято любое число, для
которого выполняется равенство (d*3)mod 20=1, например d=7.
5) Пара (33, 3) образует открытый ключ.
6) Значения (3, 11, 20, 7) образуют закрытый ключ

19. Пример. Шифрование.

В качестве n берем число 33 из примера выше.
Тогда можем шифровать буквы русского алфавита производя вычисления по модулю 33.
Зашифруем слово «бал», переведем буквы в соответствующие числовые значения (2,1,13)
C1=(2^3)mod33=8mod33=8;
C2=(1^3)mod33=1mod33=1;
C3=(13^3)mod33=2197mod33=19.
Зашифрованное слово (8,1,12) или «жас».

20.

Сравнение алгоритмы Диффи-Хелмана и RSA
1) Обмен ключами против шифрования: алгоритм Диффи-Хеллмана — это
алгоритм обмена ключами, а RSA — алгоритм шифрования.
Алгоритм Диффи-Хеллмана используется для безопасного установления общего
секретного ключа между двумя сторонами по незащищенному каналу связи, тогда как
RSA используется для шифрования и расшифровки сообщений.
2) Симметричные и асимметричные алгоритмы: алгоритм Диффи-Хеллмана —
симметричный алгоритм, а RSA — асимметричный.
Алгоритм Диффи-Хеллман использует один и тот же ключ для шифрования и
дешифрования, в то время как RSA использует разные ключи для шифрования и
дешифрования.
20

21. Домашнее задание по лекции

1. Записать открытый и закрытый ключи алгоритма RSA, если
• р=2;
• q=13;
• e=5.
2. Зашифровать (и расшифровать) с помощью алгоритма RSA слово
«bit» используя английский алфавит и данные п.1.

22.

Koda……………………………………………………………
22