Блочные алгоритмы, системы шифрования

1. Блочные алгоритмы (системы шифрования)

Лекция

2. Учебные вопросы

Принципы построения блочных
шифров
Примеры блочных шифров

3. Введение

Блочные и поточные шифры
Энтропия текста
Сложность реализации
преобразования алфавитов большой
мощности

4. Принципы построения блочных шифров

Y=Ek(X)
X=Dk(Y)
n-1
N -> 2
128 -> 1021лет
Известные открытые и
зашифрованные части блоков

5. Условия стойкого блочного алгоритма

Функция Ek(X) должна быть обратимой.
Не должно существовать иных методов
прочтения сообщения X по известному
блоку Y, кроме как полным перебором
ключей k.
Не должно существовать иных методов
определения, каким ключом k было
произведено преобразование известного
сообщения X в сообщение Y, кроме как
полным перебором ключей.

6. Представление целых чисел

32 бита ->0… 4 294 967 295
16+16 -> 2 x 0…65 535
8+8+8+8 -> 4 x 0…256

7. Биективные математические функции

сложение (X'=X+V);
исключающее ИЛИ (X'=X XOR V);
умножение по модулю 2N+1(X'=(X*V)
mod (2N+1));
умножение по модулю 2N(X'=(X*V)
mod (2N));

8. Битовые сдвиги

арифметический сдвиг
влево/вправо(X'=X SHL/SHR V);
циклический сдвиг
влево/вправо(X'=X ROL/ROR V);

9. Табличные подстановки

S-box (англ. substitute)
(X'=Table[X,V]).

10. Параметр V

фиксированное число (например,
X'=X+125);
число, получаемое из ключа
(например, X'=X+F(k));
число, получаемое из независимой
части блока (например,
X2'=X2+F(X1)).

11. Сеть Фейстеля (Feistel Network)

12. Сеть Фейстеля (Feistel Network)

Y1 = X2,
Y2 = X1 i(X2,ki),
X – входной блок, разделённый на две
половины X1 и X2,
(Y1,Y2) – результат зашифрования блока
X на ключе ki с помощью функции i.

13. Сеть Фейстеля (Feistel Network)

X1 = Y2 i(Y1,ki),
X2 = Y1.

14. Примеры блочных шифров

Название
алгоритма
Автор
IDEA
Xuejia Lia
and James
Massey
CAST128
BlowFish
ГОСТ
TwoFish
Bruce
Schneier
НИИ ***
Bruce
Schneier
Размер блока Длина ключа
64 бита
128 бит
64 бита
128 бит
64 бита
128 – 448 бит
64 бита
256 бит
128 бит
128 – 256 бит

15. Американский стандарт шифрования DES

Национальное Бюро Стандартов
(National Bureau of Standards, NBS)
Национальным институтом
стандартов и технологий США
(National Institute of Standards and
Technology, NIST)

16. Критерии оценки алгоритма 1 часть из 2

алгоритм должен обеспечивать высокий
уровень безопасности;
алгоритм должен быть полностью
определён и легко понятен;
безопасность алгоритма должна
основываться на ключе и не
должна зависеть от сохранения в
тайне самого алгоритма;
алгоритм должен быть доступен
всем пользователям;

17. Критерии оценки алгоритма 2 часть из 2

алгоритм должен позволять адаптацию к
различным применениям;
алгоритм должен позволять экономичную
реализацию в виде электронных приборов;
алгоритм должен быть эффективным в
использовании;
алгоритм должен предоставлять
возможности проверки;
алгоритм должен быть разрешён для
экспорта.

18. DES (Data Encryption Standard)

опубликован Национальным бюро
стандартов США в 1977 г.
В 1980 г.алгоритм был принят NIST в
качестве первого стандарта шифрования
данных для защиты от
несанкционированного доступа к важной,
но несекретной информации в
государственных и коммерческих
организациях США.

19. Схема алгоритма DES

20.

21. Обозначения

Li и Ri - левая и правая половины 64битного блока LiRi;
- операция побитового сложения
векторов-блоков по модулю 2;
ki – 48-битовые ключи;
- функция шифрования;
IP – начальная перестановка степени
64.

22. Начальная перестановка

23. Начальная перестановка

бит 58 блока T становится битом 1,
бит 50 – битом 2 и т.д.
Полученный после перестановки блок
IP(T) разделяется на две половины:
L0, cостоящую из 32 старших бит, и
R0, состоящую из 32 младших бит.

24. Итеративный процесс шифрования

16 циклов преобразований Фейстеля.
Ti-1 = Li-1Ri-1 – результат (i-1)-й итерации.
Ti = LiRi
Li = Ri-1,
Ri = Li-1 (Ri-1, ki), i = 1…16.
- функция шифрования
Ri-1 – 32 бита
ki – 48 бит
K – 56 бит
T16 = R16L16.
IP-1

25. Расшифрование

Ri-1= Li,
Li-1 = Ri (Li, ki), i = 16…1.
от L16 и R16 к L0 и R0

26. схема вычисления значения функции (Ri-1, ki)

схема вычисления значения
функции (Ri-1, ki)

27. схема вычисления значения функции (Ri-1, ki)

схема вычисления значения
функции (Ri-1, ki)
функция расширения E;
преобразование S, составленное из
восьми преобразований S-блоков
S1,S2,…,S8;
перестановка P.

28. Перестановка с расширением

29. Перестановка с расширением

30. Формула

E(Ri-1) ki = B1…B8.

31. Таблица S-блоков

32. Преобразование блока Bj в B'j

B2 = 111010
a = 1….0 (двоичн.)
b= .1101. (двоичн.)
0 a 3,
0 b 15
a=2 (дес.)
b=13 (дес.)

33. Таблица S-блоков

B’2 = 0011
b
a

34. (Ri-1, ki)

(Ri-1, ki)
Перестановка P
B’1B’2…B’8

35. Обработка ключей

k – 56 бит
ki – 48 бит
8,16,24,32,40,48,56,64

36.

C0
D0

37. Сi-1 и Di-1 -> Ci и Di

Сi-1 и Di-1 -> Ci и Di

38. Ключи ki

1 i 16 ,
48 бит
CiDi

39. Перестановка со сжатием

9, 18, 22, 25, 35, 38, 43, 54 из CiDi
отсутствуют в ki

40.

41. Стандарт шифрования данных ГОСТ 28147-89

Алгоритм реализует шифрование 64битовых блоков данных с помощью
256-битового ключа.

42.

43. Стандарт шифрования данных ГОСТ 28147-89

N1 и N2 – 32-х разрядные накопители;
СМ1 – сумматор по модулю 232 (операция +);
СМ2 – сумматор по модулю 2 (операция );
R – 32-разрядный регистр циклического
сдвига;
КЗУ – ключевое запоминающее устройство
объёмом 256 бит, состоящее из восьми 32разрядных накопителей;
S – блок подстановки, состоящий из восьми
узлов замены (S-блоков замены) S1,S2,…S8.

44. Стандарт шифрования данных ГОСТ 28147-89

64-разрядный блок T0
32 цикла (j = 1…32).
256 бит ключа k,
Восемь 32-разрядных подключей ki
k=k7k6k5k4k3k2k1k0.

45. Стандарт шифрования данных ГОСТ 28147-89

T0=(a1(0),…,a32(0),
b1(0),…,b32(0))
a(0)=(a32(0),a31(0),…,a1(0)),
b(0)= (b32(0),b31(0),…,b1(0)).

46. Стандарт шифрования данных ГОСТ 28147-89

N1 и N2
N1 - a(0),
N2 - b(0).

47. Стандарт шифрования данных ГОСТ 28147-89

a(j)=(a32(j),…,a1(j)),
b(j)=(b32(j),…,b1(j))
N1 и N2 после j-го цикла
зашифрования
- обозначение функции
шифрования.

48. Стандарт шифрования данных ГОСТ 28147-89

a(j)= (a(j-1)+kj-1(mod8)) b(j-1),
b(j)=a(j-1),
при j=1…24

49. Стандарт шифрования данных ГОСТ 28147-89

a(j)= (a(j-1)+k32-j(mod8) ) b(j-1),
b(j)=a(j-1),
при j=25…31

50. Стандарт шифрования данных ГОСТ 28147-89

a(32)=a(31),
b(32)= (a(31)+k0) b(31).

51. Вычисление функции  1 этап

Вычисление функции
1 этап
32-битовый аргумент x,
S
восемь последовательных 4-битовых
вектора
узел замены Si, i=8...1
таблица перестановки – 16
32-битовый вектор S(x)

52. Вычисление функции  2 этап

Вычисление функции
2 этап
R
циклический сдвиг вектора влево на
11 позиций

53. Стандарт шифрования данных ГОСТ 28147-89

результатом зашифрования блока T0
является блок Tш
Tш = (а1(32),а2(32),...,а32(32),
b1(32),b2(32),...,b32 (32)).

54. Режимы использования блочных шифров

режим электронной кодовой книги
(ECB – Electronic Code Book);
режим сцепления блоков (CBC –
Cipher Block Chaining);
режим обратной связи по шифртексту
(CFB – Cipher Feed Back);
режим обратной связи по выходу
(OFB – Output Feed Back).

55. Режим сцепления блоков (CBC – Cipher Block Chaining)

Ci, i 1
Mi+1
С0 = IV (Initial Vector)
Ci=DESk(Ci-1 Mi)

56.

57. Режим обратной связи по шифртексту (CFB – Cipher Feed Back)

Z0,Z1,…
Z0 = IV
i 1
Zi = DESk(Ci-1)
Ci = Mi Zi, i 1

58.

59. Режим m-битовой обратной связи

1 m 64.
IV, выровненный по правому краю
Ci = Mi Pi
Pi – вектор, состоящий из старших
битов блока DESk(Ci-1)

60.

61. Режимы использования ГОСТ – 28147-89

режим простой замены
режим шифрования с обратной
связью
режим гаммирования с обратной
связью
ECB, CBC, CFB

62. Режим гаммирования

Ci = Мi F( i), i = 1,2,...,

63. Комбинирование алгоритмов блочного шифрования

С = Еk2 (Еk1 (М))
С = Еk1 (Dk20 (Еk1 (М)))
С = Еk3 (Dk2 (Еk1 (М)))