Информационная безопасность. Современные алгоритмы шифрования

1. Информационная безопасность

1
Информационная
безопасность
§ 80. Современные алгоритмы
шифрования
К.Ю. Поляков, Е.А. Ерёмин, 2018
http://kpolyakov.spb.ru

2. Алгоритм RSA

Информационная безопасность, 10 класс
2
Алгоритм RSA
Р. Райвест (R. Rivest), А. Шамир (A. Shamir) и
Л. Адлеман (L. Adleman), 1977.
Шифрование с открытым ключом:
открытый ключ
Lorem ipsum dolor sit amet,
consectetur adipiscing elit.
Curabitur ultrices vulputate
hendrerit. Sed odio mauris,
tempor quis euismod ac, rutrum
at lacus. Sed augue justo, suscipit
non interdum quis, tempor in
sem. Integer a hendrerit ligula.
Phasellus tortor lacus, porttitor in
tincidunt quis, pellentesque id
nunc. Curabitur turpis mauris,
tempus accumsan suscipit vitae,
iaculis id risus. Sed non ipsum
magna. Suspendisse quis lacus
sem, vel placerat neque. Nunc
vitae enim elit. Proin suscipit
fringilla cursus. Cras facilisis
связаны!
секретный ключ
1010100101010101010111
Lorem ipsum dolor sit amet,
consectetur adipiscing elit.
Curabitur ultrices vulputate
hendrerit. Sed odio mauris,
tempor quis euismod ac, rutrum
at lacus. Sed augue justo, suscipit
non interdum quis, tempor in
sem. Integer a hendrerit ligula.
Phasellus tortor lacus, porttitor in
tincidunt quis, pellentesque id
nunc. Curabitur turpis mauris,
tempus accumsan suscipit vitae,
iaculis id risus. Sed non ipsum
magna. Suspendisse quis lacus
sem, vel placerat neque. Nunc
vitae enim elit. Proin suscipit
fringilla cursus. Cras facilisis
Идея: применение открытого и секретного ключа
восстанавливает сообщение:
открытый ключ
секретный ключ
связаны!
Lorem ipsum dolor sit amet,
consectetur adipiscing elit.
Curabitur ultrices vulputate
hendrerit. Sed odio mauris,
tempor quis euismod ac, rutrum
at lacus. Sed augue justo, suscipit
non interdum quis, tempor in
sem. Integer a hendrerit ligula.
Phasellus tortor lacus, porttitor in
tincidunt quis, pellentesque id
nunc. Curabitur turpis mauris,
tempus accumsan suscipit vitae,
iaculis id risus. Sed non ipsum
magna. Suspendisse quis lacus
sem, vel placerat neque. Nunc
vitae enim elit. Proin suscipit
fringilla cursus. Cras facilisis
1010100101010101010111
Lorem ipsum dolor sit amet,
consectetur adipiscing elit.
Curabitur ultrices vulputate
hendrerit. Sed odio mauris,
tempor quis euismod ac, rutrum
at lacus. Sed augue justo, suscipit
non interdum quis, tempor in
sem. Integer a hendrerit ligula.
Phasellus tortor lacus, porttitor in
tincidunt quis, pellentesque id
nunc. Curabitur turpis mauris,
tempus accumsan suscipit vitae,
iaculis id risus. Sed non ipsum
magna. Suspendisse quis lacus
sem, vel placerat neque. Nunc
vitae enim elit. Proin suscipit
fringilla cursus. Cras facilisis
электронная цифровая подпись
К.Ю. Поляков, Е.А. Ерёмин, 2018
http://kpolyakov.spb.ru

3. Как построить ключи RSA?

Информационная безопасность, 10 класс
3
Как построить ключи RSA?
1. Выбрать два простых числа, например,
p 3, q 7
2. Вычислить
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
5. Открытый ключ: (e, n) (5,21)
6. Секретный ключ: (d , n) (17,21)
К.Ю. Поляков, Е.А. Ерёмин, 2018
http://kpolyakov.spb.ru

4. Алгоритм RSA

Информационная безопасность, 10 класс
4
Алгоритм RSA
Шифрование: открытый ключ (e, n)
1. Сообщение – последовательность чисел в
интервале [0,n – 1].
2. Для каждого числа вычислить код
y x mod n
e
Расшифровка: секретный ключ ( d , n)
Для каждого кода вычислить число исходного
сообщения:
x y mod n
d
К.Ю. Поляков, Е.А. Ерёмин, 2018
http://kpolyakov.spb.ru

5. Алгоритм RSA: вычисление

Информационная безопасность, 10 класс
5
Алгоритм RSA: вычисление
Проблема:
очень большое число
y x mod n
e
Упрощающая формула:
(a b) mod n (a mod n b mod n) mod n
Доказательство:
a доказать?
mod n r
?r Как
a
a k n ra ,
b
b mod n
b n rb
(a b) mod n (k ) n ra rb mod n
(ra rb ) mod n
К.Ю. Поляков, Е.А. Ерёмин, 2018
http://kpolyakov.spb.ru

6. Алгоритм RSA: вычисление

Информационная безопасность, 10 класс
6
Алгоритм RSA: вычисление
Вычисление
y x mod n
e
y := 1;
k:= 1,e
конец
y := (y*x) mod n;
?
К.Ю. Поляков, Е.А. Ерёмин, 2018
Как быстрее?
http://kpolyakov.spb.ru

7. Быстрое возведение в степень

Информационная безопасность, 10 класс
7
Быстрое возведение в степень
x x , e – чётное
x e 1
x x, e – нечётное
e/2
e/2
e
Пример:
100
x
x x x
64
32
x [x ]
4
4
3 умножения
x [[[x ] ] ]
32
4 2 2 2
2 умножения
2 2
!
Вместо 99!
1 умножение
x [x ]
64
32 2
x [b] p
2 3
2 2
3
7
7
6
x [ x ] 1 [ x ] x [ x ] x [ x ] x
4 1
3
4 0
7
7
[x ] x [x ] x x
Программирование:
К.Ю. Поляков, Е.А. Ерёмин, 2018
e
k
http://kpolyakov.spb.ru

8. Быстрое возведение в степень (+ mod)

Информационная безопасность, 10 класс
8
Быстрое возведение в степень (+ mod)
def quickPowMod( x, e, n ):
b, k, y = x, e, 1
while k:
if k % 2 == 0:
k //= 2
def powMod( x, e, n ):
b = (b * b) % n
y = 1
else:
for k in range(e):
k -= 1
y = (y*x) % n
y = (b * y) % n
return y
return y
28,5 сек
123456789
y 123
mod 1023
0,0000257 сек
К.Ю. Поляков, Е.А. Ерёмин, 2018
http://kpolyakov.spb.ru

9. Алгоритм RSA: пример

Информационная безопасность, 10 класс
9
Алгоритм 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
К.Ю. Поляков, Е.А. Ерёмин, 2018
http://kpolyakov.spb.ru

10. Алгоритм RSA: вскрытие

Информационная безопасность, 10 класс
10
Алгоритм RSA: вскрытие
Задача: при известном открытом ключе (e, n)
найти секретный ключ d
Способ:
1) разложить n на взаимно-простые множители:
n p q
2) вычислить
( p 1) (q 1)
3) найти d, такое что при некотором k
d e k 1
Проблема: разложение большого числа на простые
множители требует недостижимого объема
вычислений (при длине n > 1024 бита)
К.Ю. Поляков, Е.А. Ерёмин, 2018
http://kpolyakov.spb.ru

11. Алгоритм RSA

Информационная безопасность, 10 класс
11
Алгоритм RSA
для обмена открытыми ключами можно
использовать незащищенный канал
много готовых реализаций
криптостойкость (при длине n > 1024 бита)
медленная шифровка и (особенно)
расшифровка
при малом n взламывается
К.Ю. Поляков, Е.А. Ерёмин, 2018
http://kpolyakov.spb.ru

12. Электронная цифровая подпись

Информационная безопасность, 10 класс
12
Электронная цифровая подпись
Электронная цифровая подпись (ЭЦП) – это
набор символов, который получен в результате
шифрования сообщения (или его хэш-кода) с
помощью секретного ключа отправителя.
секретный ключ
Lorem ipsum dolor sit amet,
consectetur adipiscing elit.
Curabitur ultrices vulputate
hendrerit. Sed odio mauris,
tempor quis euismod ac, rutrum
at lacus. Sed augue justo, suscipit
non interdum quis, tempor in
sem. Integer a hendrerit ligula.
Phasellus tortor lacus, porttitor in
tincidunt quis, pellentesque id
nunc. Curabitur turpis mauris,
tempus accumsan suscipit vitae,
iaculis id risus. Sed non ipsum
magna. Suspendisse quis lacus
sem, vel placerat neque. Nunc
vitae enim elit. Proin suscipit
fringilla cursus. Cras facilisis
открытый ключ
1010100101010101010111
Lorem ipsum dolor sit amet,
consectetur adipiscing elit.
Curabitur ultrices vulputate
hendrerit. Sed odio mauris,
tempor quis euismod ac, rutrum
at lacus. Sed augue justo, suscipit
non interdum quis, tempor in
sem. Integer a hendrerit ligula.
Phasellus tortor lacus, porttitor in
tincidunt quis, pellentesque id
nunc. Curabitur turpis mauris,
tempus accumsan suscipit vitae,
iaculis id risus. Sed non ipsum
magna. Suspendisse quis lacus
sem, vel placerat neque. Nunc
vitae enim elit. Proin suscipit
fringilla cursus. Cras facilisis
Применение:
• доказательство авторства
• невозможность отказа от авторства
• защита от изменений (проверка целостности)
К.Ю. Поляков, Е.А. Ерёмин, 2018
http://kpolyakov.spb.ru