Развитие Алгоритмов шифрования

1. Развитие Алгоритмов шифрования

2. Недостатки DES

• Так как длина ключа равна 56 битам,
существует 256 возможных ключей. На сегодня
такая длина ключа недостаточна, поскольку
допускает успешное применение лобовых
атак.
• Альтернативой DES можно считать тройной
DES, IDEA, а также алгоритм Rijndael, принятый
в качестве нового стандарта на алгоритмы
симметричного шифрования.

3. Тройной DES с двумя ключами

Использование трех стадии шифрования с тремя различными ключамио
поднимает стоимость лобовой атаки до 2168, которая на сегодняшний день
считается выше практических возможностей. Но при этом длина ключа равна
56 * 3 = 168 бит, что иногда бывает громоздко.
В качестве альтернативы предлагается метод тройного шифрования,
использующий только два ключа. В этом случае выполняется
последовательность зашифрование-расшифрование-зашифрование (EDE).
C = EK1 [DK2 [EK1 [P]]]
Не имеет большого значения, что используется на второй стадии:
шифрование или дешифрование.
В случае использования дешифрования существует только то преимущество,
что можно тройной DES свести к обычному одиночному DES, используя K1 =
K2:
C = EK1 [DK1 [EK1 [P]]] = EK1 [P]
Известных криптографических атак на тройной DES не существует. Цена
подбора ключа в тройном DES равна 2112.

4.

Шифрование тройным DES
Дешифрование тройным DES

5. Advanced Encryption Standard (AES)

Известен также как Rijndael.
Симметричный алгоритм блочного шифрования
(размер блока 128 бит, ключ 128/192/256 бит),
принятый в качестве стандарта шифрования
правительством США по результатам конкурса AES.
Национальный институт стандартов и технологий США
(National Institute of Standards and Technology, NIST)
опубликовал спецификацию AES 26 ноября 2001 года.
26 мая 2002 года AES был объявлен стандартом
шифрования.
Rijndael блочный алгоритм шифрования с переменной
длиной блока и переменной длиной ключа. Длина
блока и длина ключа могут быть независимо
установлены в 128, 192 или 256 бит.

6. Состояние

• Преобразования выполняются над промежуточным
результатом, называемым состоянием.
• Состояние можно рассматривать как двумерный массив байтов.
Этот массив имеет четыре строки и различное число столбцов,
обозначаемое как Nb, равное длине блока, деленной на 32.
Ключ также можно рассматривать как двумерный массив с
четырьмя строками. Число столбцов ключа шифрования,
обозначаемое как Nk, равно длине ключа, деленной на 32.
• В некоторых случаях эти блоки также рассматриваются как
одномерные массивы четырехбайтных векторов, где каждый
вектор состоит из соответствующего столбца. Такие массивы
имеют длину 4, 6 или 8 соответственно, и индексы в диапазонах
0 … 3, 0 … 5 или 0 … 7. Четырехбайтные вектора иногда мы
будем называть словами.
• Если необходимо указать четыре отдельных байта в
четырехбайтном векторе, будет использоваться нотация (a, b, c,
d), где a, b, c и d являются байтами в позициях 0, 1, 2 и 3,
соответственно, в рассматриваемом столбце, векторе или
слове.

7. Преобразования алгоритма Rijndael

Алгоритм Rijndael состоит из четырёх последовательных преобразований:
• BS (ByteSub) – табличная замена каждого байта массива.
• SR (ShiftRow) – сдвиг строк массива.
• MixColumn – операция над независимыми столбцами массива.
• AK (AddRoundKey) – добавление ключа.
Преобразования над шифруемыми данными поочередно выполняются в каждом
раунде
Исключения касаются первого и последнего раундов: перед первым раундом
дополнительно выполняется операция AK, а в последнем раунде отсутствует
MC.
AK, {BS, SR, MC, AK} (повторяется R-1 раз), BS, SR, AK.
В алгоритме Rijndael количество раундов шифрования (R) переменное (10, 12 или
14 раундов) и зависит от размеров блока и ключа шифрования (для ключа
также предусмотрено несколько фиксированных размеров).

8. BS (ByteSub)

табличная замена каждого байта массива.
Преобразование SubByte() является нелинейной
подстановкой байтов, которое работает независимо для
каждого байта State и использует таблицу подстановок S.
Эта замена включает в себя две операции:
• Каждый байт заменяется на обратный
мультипликативный
{b}-1 ={b} mod m(x)
Байт {00} преобразуется сам в себя.
Для каждого байта осуществляется аффинное
преобразование в поле GF(2), задаваемое формулой

9. Таблицы подстановки для S-Box и InvS-Box

Преобразования S-Box и InvS-Box могут быть представлены в виде таблицы
подстановки.
Если на входе есть байт B [7-0], а x и y – его старшая и младшая часть (x [3-0] =
B [7-4], y [3-0] = B [3-0]), то на выходе байт получается кодированным в две
шестнадцатиричные цифры.
Например, применение таблицы подстановки S-Box для числа 85 (x=8; y=5 в
шестнадцатиричном виде) дает на выходе шестнадцатиричное 97. А
применение таблицы InvS-Box для 97 дает 85.

10. Таблица S-Box

х ------------------ y ---------------------->
0 1 2 3 4 5 6 7 8 9 a b c d e f
0 63 7c 77 7b f2 6b 6f c5 30 01 67 2b fe d7 ab 76
1 ca 82 c9 7d fa 59 47 f0 ad d4 a2 af 9c a4 72 c0
2 b7 fd 93 26 36 3f f7 cc 34 a5 e5 f1 71 d8 31 15
3 04 c7 23 c3 18 96 05 9a 07 12 80 e2 eb 27 b2 75
4 09 83 2c 1a 1b 6e 5a a0 52 3b d6 b3 29 e3 2f 84
5 53 d1 00 ed 20 fc b1 5b 6a cb be 39 4a 4c 58 cf
6 d0 ef aa fb 43 4d 33 85 45 f9 02 7f 50 3c 9f a8
7 51 a3 40 8f 92 9d 38 f5 bc b6 da 21 10 ff f3 d2
8 cd 0c 13 ec 5f 97 44 17 c4 a7 7e 3d 64 5d 19 73
9 60 81 4f dc 22 2a 90 88 46 ee b8 14 de 5e 0b db
a e0 32 3a 0a 49 06 24 5c c2 d3 ac 62 91 95 e4 79
b e7 c8 37 6d 8d d5 4e a9 6c 56 f4 ea 65 7a ae 08
c ba 78 25 2e 1c a6 b4 c6 e8 dd 74 1f 4b bd 8b 8a
d 70 3e b5 66 48 03 f6 0e 61 35 57 b9 86 c1 1d 9e
e e1 f8 98 11 69 d9 8e 94 9b 1e 87 e9 ce 55 28 df
f 8c a1 89 0d bf e6 42 68 41 99 2d 0f b0 54 bb 16

11. Таблица InvS-Box

Х
------------------ y ---------------------->
0 1 2 3 4 5 6 7 8 9 a b c d e f
0 52 09 6a d5 30 36 a5 38 bf 40 a3 9e 81 f3 d7 fb
1 7c e3 39 82 9b 2f ff 87 34 8e 43 44 c4 de e9 cb
2 54 7b 94 32 a6 c2 23 3d ee 4c 95 0b 42 fa c3 4e
3 08 2e a1 66 28 d9 24 b2 76 5b a2 49 6d 8b d1 25
4 72 f8 f6 64 86 68 98 16 d4 a4 5c cc 5d 65 b6 92
5 6c 70 48 50 fd ed b9 da 5e 15 46 57 a7 8d 9d 84
6 90 d8 ab 00 8c bc d3 0a f7 e4 58 05 b8 b3 45 06
7 d0 2c 1e 8f ca 3f 0f 02 c1 af bd 03 01 13 8a 6b
8 3a 91 11 41 4f 67 dc ea 97 f2 cf ce f0 b4 e6 73
9 96 ac 74 22 e7 ad 35 85 e2 f9 37 e8 1c 75 df 6e
a 47 f1 1a 71 1d 29 c5 89 6f b7 62 0e aa 18 be 1b
b fc 56 3e 4b c6 d2 79 20 9a db c0 fe 78 cd 5a f4
c 1f dd a8 33 88 07 c7 31 b1 12 10 59 27 80 ec 5f
d 60 51 7f a9 19 b5 4a 0d 2d e5 7a 9f 93 c9 9c ef
e a0 e0 3b 4d ae 2a f5 b0 c8 eb bb 3c 83 53 99 61
f 17 2b 04 7e ba 77 d6 26 e1 69 14 63 55 21 0c 7d

12. SR (ShiftRow)

– сдвиг строк массива.
При этой операции первая строка остается без изменений, а остальные
циклически побайтно сдвигаются влево на фиксированное число байт,
зависящее от размера массива.
Например, для массива размером 4X4 строки 2, 3 и 4 сдвигаются
соответственно на 1, 2 и 3 байта.

13. MixColumn

операция над независимыми столбцами массива , когда каждый столбец по
определенному правилу умножается на фиксированную матрицу c(x).
каждая из колонок представляет собой 4-битный код. Колонки
рассматриваются как полиномы над полем GF(28). Колонка умножается на
фиксированный полином {a}={03}x3+{01}x2+{01}x+ {02} по модулю x4+1

14. Уравнения преобразования MixColumns

A' = ({02} • A) + ({03} • B) + C + D
B' = A + ({02} • B) + ({03} • C) + D
C' = A + B + ({02} • C) + ({03} • D)
D' = ({03} • A) + B + C + ({02} • D)
E' = ({02} • E) + ({03} • F) + G + H
F' = E + ({02} • F) + ({03} • G) + H
G' = E + F + ({02} • G) + ({03} • H)
H' = ({03} • E) + F + G + ({02} • H)
I' = ({02} • I) + ({03} • J) + K + L
J' = I + ({02} • J) + ({03} • K) + L
K' = I + J + ({02} • K) + ({03} • L)
L' = ({03} • I) + J + K + ({02} • L)
M' = ({02} • M) + ({03} • N) + O + P
N' = M + ({02} • N) + ({03} • O) + P
O' = M + N + ({02} • O) + ({03} • P)
P' = ({03} • M) + N + O + ({02} • P)

15. AK (AddRoundKey)

добавление ключа.
Каждый бит массива складывается по модулю 2 с соответствующим битом ключа
раунда, который, в свою очередь, определенным образом вычисляется из ключа
шифрования.
Для шифрования текста AES применяет не пароль или хеш от пароля, а так называемое
«расписание ключей» получаемое из ключа. Это расписание можно представить как Nr
+ 1 матриц размера 4×Nb. Алгоритм шифрования делает Nr + 1 шагов и на каждом шаге
он, помимо других действий, берёт одну матрицу 4×Nb из «расписания» и поэлементно
добавляет её к блоку данных.
Nk
AES-128 4
AES-192 6
AES-256 8
Nb
4
4
4
Nr
10
12
14

16. Алгоритм ГОСТ 28147

Алгоритм ГОСТ 28147 - отечественный
стандарт для алгоритмов симметричного
шифрования.
ГОСТ 28147 разработан в 1989 году, является
блочным алгоритмом шифрования, длина
блока равна 64 битам, длина ключа равна 256
битам, количество раундов равно 32.

17.

Алгоритм представляет собой классическую сеть
Фейстеля.
Li = Ri-1
Ri = Li +f (Ri-1, Ki)
Функция F.
Сначала правая половина и i-ый подключ
складываются по модулю 232. Затем результат
разбивается на восемь 4-битовых значений,
каждое из которых подается на вход S-box.
ГОСТ 28147 использует восемь различных S-boxes,
каждый из которых имеет 4-битовый вход и 4битовый выход.
Выходы всех S-boxes объединяются в 32-битное
слово, которое затем циклически сдвигается на
11 битов влево. Наконец, с помощью XOR
результат объединяется с левой половиной, в
результате чего получается новая правая
половина.

18. Генерация ключей

256-битный ключ разбивается на восемь 32-битных подключей. Алгоритм
имеет 32 раунда, поэтому каждый подключ используется в четырех раундах .
Раунд
1
2
3
4
5
6
7
8
Подключ
1
2
3
4
5
6
7
8
Раунд
9
10
11
12
13
14
15
16
Подключ
1
2
3
4
5
6
7
8
Раунд
17
18
19
20
21
22
23
24
Подключ
1
2
3
4
5
6
7
8
Раунд
25
26
27
28
29
30
31
32
Подключ
8
7
6
5
4
3
2
1

19. S-box

входом и выходом S-box являются 4-битные числа, поэтому каждый S-box
может быть представлен в виде строки чисел от 0 до 15
1-ый S-box
2-ой S-box
3-ий S-box
4-ый S-box
5-ый S-box
6-ой S-box
7-ой S-box
8-ой S-box
4
10
9
2
13
8
0
14
6
11
1
12
7
15
5
3
14
11
4
12
6
13
15
10
2
3
8
1
0
7
5
9
5
8
1
13
10
3
4
2
14
15
12
7
6
0
9
11
7
13
10
1
0
8
9
15
14
4
6
12
11
2
5
3
6
12
7
1
5
15
13
8
4
10
9
14
0
3
11
2
4
11
10
0
7
2
1
13
3
6
8
5
9
12
15
14
13
11
4
1
3
15
5
9
0
10
14
7
6
8
2
12
1
15
13
0
5
7
10
4
9
2
3
14
6
11
8
12

20. Алгоритм шифрования RSA

• На данный момент асимметричное шифрование на основе открытого
ключа RSA (расшифровывается, как Rivest, Shamir and Aldeman создатели алгоритма) использует большинство продуктов на рынке
информационной безопасности.
• Его криптостойкость основывается на сложности разложения на
множители больших чисел, а именно - на исключительной трудности
задачи определить секретный ключ на основании открытого, так как
для этого потребуется решить задачу о существовании делителей
целого числа. Наиболее криптостойкие системы используют 1024битовые и большие числа.

21. Ключи RSA

Для начала необходимо сгенерировать открытый и секретные ключи:
• Берутся два больших простых числа p и q.
• Определяется n, как результат умножения p и q (n= p*q).
• Выбирается случайное число d. Это число должно быть взаимно простым (не
иметь ни одного общего делителя, кроме «1» с результатом умножения (p1)*(q-1).
• Находится такое число е, для которого является истинным следующее
соотношение (e*d) mod ((p-1)*(q-1))=1.
• Числа e и n определяются как открытый ключ, а - d и n как секретный.

22. Работа RSA

Для того, чтобы зашифровать данные по открытому ключу {e,n}, необходимо следующее:
• разбить шифруемый текст на блоки, каждый из которых может быть представлен в виде
числа M(i)=0,1,2..., n-1( т.е. только до n-1).
зашифровать текст, рассматриваемый как последовательность чисел M(i) по формуле
C(i)=(M(I)^e)mod n.
Чтобы расшифровать эти данные, используя секретный ключ {d,n}, необходимо
выполнить следующие вычисления: M(i) = (C(i)^d) mod n. В результате будет получено
множество чисел M(i), которые представляют собой исходный текст.

23. Пример работы RSA

Зашифруем и расшифруем сообщение "САВ" по алгоритму RSA. Для простоты возьмем
небольшие числа - это сократит наши расчеты.
Выберем p=3 and q=11.
Определим n= 3*11=33.
Hайдем (p-1)*(q-1)=20.
d будет равно, например, 3: (d=3).
Определим число е по следующей формуле: (e*3) mod 20=1. Значит е будет равно 7: (e=7).
Представим шифруемое сообщение как последовательность чисел в диапазоне от 0 до 32
(n-1).
Пусть буква А =1, В=2, С=3.
Теперь зашифруем сообщение, используя открытый ключ {7,33}
C1 = (3^7) mod 33 = 2187 mod 33 = 9;
C2 = (1^7) mod 33 = 1 mod 33 = 1;
C3 = (2^7) mod 33 = 128 mod 33 = 29;
Теперь расшифруем данные, используя закрытый ключ {3,33}.
M1=(9^3) mod 33 =729 mod 33 = 3(С);
M2=(1^3) mod 33 =1 mod 33 = 1(А);
M3=(29^3) mod 33 = 24389 mod 33 = 2(В);

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

Электронная цифровая подпись - реквизит электронного документа,
позволяющий установить отсутствие искажения информации в электронном
документе с момента формирования ЭЦП и проверить принадлежность подписи
владельцу сертификата ключа ЭЦП.
Использование ЭЦП позволяет защититься от злонамеренных действий:
• отказ - отправитель впоследствии отказывается от переданного сообщения;
• фальсификация - получатель подделывает сообщение;
• изменение - получатель вносит изменения в сообщение;
• маскировка - нарушитель маскируется под другого пользователя.
Поскольку подписываемые документы — переменного (и как правило
достаточно большого) объёма, в схемах ЭЦП зачастую подпись ставится не на сам
документ, а на его хэш. Для вычисления хэша используются криптографические
хэш-функции, что гарантирует выявление изменений документа при проверке
подписи. Хэш-функции не являются частью алгоритма ЭЦП, поэтому в схеме
может быть использована любая надёжная хэш-функция.

25. Схемы построения цифровой подписи

• На основе алгоритмов симметричного шифрования. Данная схема
предусматривает наличие в системе третьего лица — арбитра,
пользующегося доверием обеих сторон. Авторизацией документа
является сам факт зашифрования его секретным ключом и передача
его арбитру.
• На основе алгоритмов асимметричного шифрования. На данный
момент такие схемы ЭЦП наиболее распространены и находят
широкое применение.

26. Асимметричная схема

Асимметричные схемы ЭЦП относятся к криптосистемам с открытым ключом.
В отличие от асимметричных алгоритмов шифрования, в которых зашифрование
производится с помощью открытого ключа, а расшифрование — с помощью
закрытого, в схемах цифровой подписи подписывание производится с
применением закрытого ключа, а проверка — с применением открытого.

27. Общая схема цифровой подписи

Генерация ключевой пары. При помощи алгоритма генерации ключа
равновероятным образом из набора возможных закрытых ключей
выбирается закрытый ключ, вычисляется соответствующий ему открытый
ключ.
Формирование подписи. Для заданного электронного документа с помощью
закрытого ключа вычисляется подпись.
Проверка (верификация) подписи. Для данных документа и подписи с
помощью открытого ключа определяется действительность подписи.

28.

29.

30. Алгоритм DSA (Digital Signature Algorithm)

DSA - алгоритм с использованием открытого ключа для создания
электронной подписи, но не для шифрования. Вместе с криптографической
хеш-функцией SHA-1 является частью DSS (Digital Signature Standard), впервые
опубликованного в 1994.
Для построения системы цифровой подписи нужно произвести следующие
действия:
• Выбор криптографической хеш-функции H(x).
• Выбор большого простого числа q, размерность которого в битах совпадает с
размерностью в битах значений хэш-функции H(x).
• Выбор простого числа p, такого, что (p-1) делится на q.
• Выбор числа g такого, что его мультипликативный порядок по модулю p равен
q. Для его вычисления используется формула g = h^((p - 1)/q) mod p,
где h ϵ (1; p - 1), такое, что g ≠ 1. В большинстве случаев значение h = 2
удовлетворяет этому требованию.

31. Открытый и секретный ключи

Секретный ключ представляет собой число x ϵ (0; q)
Открытый ключ вычисляется по формуле y = g^x mod p
Открытыми параметрами являются числа (p, q, g, y).
Закрытый параметр только один — число x.
При этом числа (p, q, g) могут быть общими для группы пользователей, а числа x
и y являются соответственно закрытым и открытым ключами конкретного
пользователя. При подписании сообщения используются секретные числа x и k,
причем число k должно выбираться случайным образом (на практике
псевдослучайным) при подписывании каждого следующего сообщения.

32. Подпись сообщения

Подпись сообщения выполняется по следующему алгоритму:
1.
2.
3.
4.
Выбор случайного числа k ϵ (0; q);
Вычисление r = (g^k mod p) mod q;
Вычисление s = k^(-1)(H(m) + x * r) mod q, где H(m) - хэш сообщения;
Выбор другого k, если r = 0 или s = 0.
Подписью является пара чисел (r, s).

33. Пример выполнения

Исходные данные:
hash = 64433; q = 34939; p = 69879; h = 2; x = 13;
Генерация числа g:
g = h^((p - 1)/q) mod p = 2^((69879 - 1) /34939) mod 69879 = 4
Генерация открытого ключа y:
y = g^x mod p = 4^13 mod 69879 = 67108864 mod 69879 = 25024
Выбираем k = 1. Вычисляем r:
r = (g^k mod p) mod q = (4^1 mod 69879) mod 34939 = 4
Вычисляем s:
s = k^(-1)(H(m) + x * r) mod q = 1 (64433 + 13 * 4) mod 34939 = 64485 mod 34939 =
29546.