Лекция 8. шифрование RSA 1 (1)

1. Асимметричные криптосистемы. Шифрование по RSA Лекция 8

LOGO
Асимметричные
криптосистемы. Шифрование
по RSA
Лекция 8

2. Асимметричная криптография

М
2

3. Обобщенная схема асимметричного шифрования с открытым ключом

Отправитель А
Незащищенный канал
M
C
Получатель В
DB
EB
Генератор
ключей
Противник
EB : M→ C
DB : C→ M

4. Шифрование открытым ключом (рис. Вильяма Столингса)

5. Шифрование секретным ключом (рис. Вильяма Столингса)

6. Алгоритм RSA (RIVEST R., SHAMIR A., ADLEMAN L.)

Вычислительно не осуществимая операция – разложение n (n > 21024) на
простые множители.
Этапы реализации алгоритма RSA.
1. Получатель вычисляет n = p х q и φ(n) = (p-1)(q-1),
где φ(n) – функция Эйлера; p, q – простые числа.
2. Затем он выбирает случайное целое число K BO (открытый ключ), взаимно
простое с φ(n) и вычисляет K BC (секретный ключ), удовлетворяющее условию
K BO K BC mod (φ(n)) = 1 (mod φ(n)).
Два числа являются взаимно простыми, если их HOD =1. Числа а и b имеют
HOD d, если d делит и а и b и максимальный среди таких чисел.
3. После этого он публикует K BO и n как свой открытый ключ шифрования,
сохраняя K BC, как закрытый (секретный) ключ.
4. Отправляемое сообщение необходимо представить как векторы (блоки)
M= (M1,M2...,Ml), 0<Mi< n;.
5. Каждое Mi возвести в степень K BO по mod n
K
K
K
6. Прислать нам С=(M1 (mod n), M2 (mod n),...,Ml (mod n)).
7. Расшифровать М= С KBC mod n.
O
B
O
B
O
B

7. Вычеты

Для любого положительного целого числа n и
любого целого a при делении а на n мы
получим некоторое целое частное q и остаток
r, удовлетворяющие соотношению
н
a=qn+r, 0 ≤ r <n; q -
наибольшее целое число, не превышающее
a/n. Остаток r часто называют вычетом.
a=11;
n=7;
11=1x7+4;
r=4,
а= -11;
n=7;
- 11= (-2x7)+3; r=3.

8. Операция приведения по модулю

Операцию нахождения вычета числа а по
модулю n
а(mod n)
Называют приведением числа а по модулю n
или приведением по модулю.
Приведение
по
модулю
n
является
гомоморфным отображением из кольца
целых в кольцо целых по модулю n.

9. Формулы для модулярной арифметики

(a+b) mod n=[a(mod n)+b(mod n)]mod n,
(a-b) mod n=[a(mod n)-b(mod n)]mod n,
(a*b) mod n=[a(mod n)*b(mod n)]mod n,
[a*(b+c)]mod n={[a*b(mod n)]+[a*c(mod n)]}mod n

10. Теоремы

Теорема Ферма: если p является простым и a
является положительным целым числом, которое не
делится на р, т.е. НОД (а, p) = 1, то
ар-1≡ 1 mod p
Теорема Эйлера: для любых взаимно-простых чисел
aиn
аф(n) ≡ 1 mod n.
Ф(n)функция
Эйлера–число
положительных целых значений, которое
меньше n и взаимно простое с n.
a=3, n=10, ф (10) =4, 34=81=1 mod10
а=2,n=11, ф (11)=10, 210=1024≡1 mod11

11. Доказательство обратимости односторонней функции с секретом (1)

Обозначим Сi=Мie (mod n) и рассмотрим
расшифрование полученной информации.
Mi = (Mi e (mod n))d(mod n) = Mi ed (mod n).
В соответствие с п.2 соотношение ed (mod
φ(n)) =1(mod φ(n )), а это означает, что ed-1
делится нацело на (p-1)(q-1), т.е. ed=1+a(p1)(q-1), где а - целое число.
Утверждается, что Mied(mod n) =Мi.

12. Доказательство обратимости односторонней функции с секретом (2)

Действительно, Mi ed(mod n) = Mi 1+a(p-1)(q-1) (mod n).
Учитывая, что для любых взаимно простых чисел
Mi и n действует теорема Эйлера в основной
формулировке
Mi φ(n) mod n = 1 mod n,
после возведения в степень а: Miаφ(n)modn=1 mod n,
и умножения на Mi:
Mi аφ(n)+1= Mi mod n.
Miа(р -1)(q -1)+1 (mod n)= Mi аφ(n)+1= Mi mod n.
Mi mod n = Mi, так как М i<n.
Что и требовалось доказать.

13. Пример шифрования по RSA

Шифрование сообщения САВ. Для простоты вычислений будут использоваться
небольшие числа.
Действия пользователя В.
1. Выбирает Р = 3 и Q = 11.
2. Вычисляет модуль N = Р*Q =3*11 = 33.
3. Вычисляет значение функции Эйлера для N = 33:
(N) = (33) = (Р-1)(Q-1) =2*10=20.
Выбирает в качестве открытого ключа КВо произвольное число с учетом
выполнения условий:
1< КВo 20, НОД(КВ, 20) = 1.
Пусть КВо = 7.
4. Вычисляет значение секретного ключа kВс = 3
5. Пересылает пользователю А пару чисел (N = 33, KВ = 7).
Действия пользователя А.
6. Представляет шифруемое сообщение как последовательность целых чисел в
диапазоне 0 ... 32. Пусть буква А представляется как число 1, буква В - как
число 2, буква С - как число 3. Тогда сообщение САВ можно Представить как
последовательность чисел 312, т.е. М1 = 3, М2 = 1, М3 = 2

14. Пример шифрования по RSA (2)

7. Шифрует текст, представленный в виде последовательности чисел М1, М2 и
М3, используя ключ KВо = 7 и N = 33, по формуле
Сi = Мi KВо (mod N) = Мi7 (mod 33).
Получает
С1 = 37 (mod 33) = 405 (mod 33) =9,
С2 = 17 (mod 33) = 1 (mod 33) =1,
С3 = 27 (mod 33) = (31х2) (mod 33) =29.
Отправляет пользователю В криптограмму
С1,С2,С3 = 9, 1, 29.
Действия пользователя В.
8. Расшифровывает принятую криптограмму С1,С2,С3, используя секретный
ключ kВс = 3, по формуле
Mi = Ci KВс (mod N) = Ci3 (mod 33).
Получает
M1 = 93 (mod 33) = 729 (mod 33) =3,
M2 = 13 (mod 33) = 1 (mod 33) =1,
M3 = 293 (mod 33) = (841х29) (mod 33) =2.
Таким образом, восстановлено исходное сообщение: С А В
3 1 2

15. Основные способы нахождения обратных величин

1.Проверить поочередно значения 1, 2, …, n-1, пока не будет найден
a-1(modn), такой, что a x a-1 (modn) ≡ 1. Пусть n=7, a=5. a-1 (modn) ≡ 3.
2.Если известна функция Эйлера φ(n), то можно вычислить
φ(n)-1
a-1(modn) ≡ a
(modn),
используя алгоритм быстрого возведения в степень.
Пусть n = 7, а=5. Найти х= a-1(modn)= 5-1(mod7). φ(n)=φ(7)=7-1=6.
a-1(modn) = 55(mod7)= 52(mod7) 53(mod7) (mod7)=
=(25 mod7)(125 mod7) = (4х 6) =(24 mod7) = 3.
Итак, х= 5-1(mod7)=3
3. Нахождение обратной величины a-1(modn) с помощью
расширенного алгоритма Евклида.

16. Расширенный алгоритм Евклида (1)

Если НОД (gcd) gcd (d, f)=1, то d имеет
мультипликативное обратное по модулю f. Это значит,
что для положит. целого числа d < f существует такое d -1
< f, что
dd -1 = 1 mod f.
EXTENDED EUCLID (d,f)
1. (X1,X2,X3)← (1,0,f); (Y1,Y2,Y3) ←(0,1,d)
2. if Y3=0 return X3= gcd (d,f); нет обратного
3. if Y3=1 return X3= gcd (d,f); Y2 = d -1 mod f
4. Q = ɭ X3/Y3˩
5. (T1,T2,T3) ← (X1 – QY1, X2 – QY2, X3 – QY3)
6. (X1,X2,X3) ← (Y1,Y2,Y3)
7. (Y1,Y2,Y3) ← (T1,T2,T3)
8. go to 2

17. Расширенный алгоритм Евклида (2)

18. Электронная цифровая подпись (ЭЦП)

Отправитель А
Незащищенный канал
M
S, M’
Получатель В
EA
DA
Генератор
ключей
Противник

19. Подписанное сообщение

20. ЭЦП RSA

Процедура подписывания сообщения M –
это возведение числа M в степень KAC по
modn: S = mKАC (mod n).
Процедура проверки подписи S ,
соответствующей сообщению M – это
возведение числа S в целую степень KAo
по mod n:
K AO
M= S (mod n)
Если M’= M, то сообщение M’ признается
целостным и подписанным пользователем,
который предоставил ранее открытый
ключ.

21. Обощенная схема ЭЦП (Исправить: справа вверху m, внизу m’ и передается M”

22. Обобщенная схема ЭЦП

Исправить: справа: вверху m, внизу m’ и передается M”

23. ЭЦП сжатого сообщения по RSA

Процедура подписывания сжатого сообщения
m=h(M) – это возведение числа m в степень
kac по mod n, где h – хэш-функция, m-хэшзначение: S = mKАC (mod n).
Процедура проверки подписи S ,
соответствующей сообщению M, – это
возведение значения S в целую степень kА o
по mod n: m= SкАО (mod n); вычисление
m'=h(M‘) из полученного сообщения M‘
Если m'= m, то сообщение M' признается
целостным и подписанным пользователем,
который предоставил ранее открытый ключ.

24.

c58yex