1 of 46

1

Practical Padding Oracle Attacks on RSA

2 of 46

2

Повторение: RSA

3 of 46

RSA

3

      • RSA (аббревиатура от фамилий Rivest, Shamir и Adleman) — криптографический алгоритм с открытым ключом, основывающийся на вычислительной сложности задачи факторизации больших целых чисел

​

​

4 of 46

RSA

4

      • RSA (аббревиатура от фамилий Rivest, Shamir и Adleman) — криптографический алгоритм с открытым ключом, основывающийся на вычислительной сложности задачи факторизации больших целых чисел

​

      • Криптосистема RSA пригодна как для шифрования, так и для цифровой подписи

​

5 of 46

5

В чём отличия между шифрованием и цифровой подписью?

6 of 46

6

7 of 46

RSA: алгоритм создания открытого и секретного ключей�

7

      • Выбираются два различных случайных простых числа p и q заданного размера (например, 2048 бит каждое)

​

8 of 46

RSA: алгоритм создания открытого и секретного ключей�

8

      • Выбираются два различных случайных простых числа p и q заданного размера (например, 2048 бит каждое)

​

      • Вычисляется их произведение n = p ⋅ q, которое называется модулем

​

​

9 of 46

RSA: алгоритм создания открытого и секретного ключей�

9

      • Выбираются два различных случайных простых числа p и q заданного размера (например, 2048 бит каждое)
      • Вычисляется их произведение n = p ⋅ q, которое называется модулем

​

      • Вычисляется значение функции Эйлера от числа n: 
            • φ(n) = (p − 1) ⋅ (q − 1) 

10 of 46

RSA: алгоритм создания открытого и секретного ключей�

10

      • Выбираются два различных случайных простых числа p и q заданного размера (например, 2048 бит каждое)
      • Вычисляется их произведение n = p ⋅ q, которое называется модулем
      • Вычисляется значение функции Эйлера от числа n: 
            • φ(n) = (p − 1) ⋅ (q − 1) 

​

      • Выбирается целое число e ( 1 < e < φ(n) ), взаимно простое со значением функции φ(n) 

​

​

​

11 of 46

RSA: алгоритм создания открытого и секретного ключей�

11

      • Вычисляется значение функции Эйлера от числа n: 
            • φ(n) = (p − 1) ⋅ (q − 1) 
      • Выбирается целое число e ( 1 < e < φ(n) ), взаимно простое со значением функции φ(n) 
            • число e называется открытой экспонентой
            • слишком малые значения e потенциально могут ослабить безопасность схемы RSA
            • обычно в качестве e берут простые числа, содержащие небольшое количество единичных бит в двоичной записи, так как это ускоряет шифрование

​

​

12 of 46

RSA: алгоритм создания открытого и секретного ключей�

12

      • Выбирается целое число e ( 1 < e < φ(n) ), взаимно простое со значением функции φ(n) (открытая экспонента)

​

      • Вычисляется число d, мультипликативно обратное к числу e по модулю φ ( n ) 
            • число d называется секретной экспонентой
            • d ⋅ e ≡ 1 ( mod φ ( n ) )
            • вычисляется при помощи расширенного алгоритма Евклида

​

​

13 of 46

RSA: алгоритм создания открытого и секретного ключей�

13

      • Выбирается целое число e ( 1 < e < φ(n) ), взаимно простое со значением функции φ(n) (открытая экспонента)
      • Вычисляется число d, мультипликативно обратное к числу e по модулю φ ( n )  (секретная экспонента)

​

      • Пара ( e , n ) публикуется в качестве открытого ключа RSA

​

​

14 of 46

RSA: алгоритм создания открытого и секретного ключей�

14

      • Выбирается целое число e ( 1 < e < φ(n) ), взаимно простое со значением функции φ(n) (открытая экспонента)
      • Вычисляется число d, мультипликативно обратное к числу e по модулю φ ( n )  (секретная экспонента)
      • пара ( e , n ) публикуется в качестве открытого ключа RSA

​

      • Пара ( d , n ) играет роль закрытого ключа RSA и держится в секрете

​

15 of 46

RSA: алгоритм создания открытого и секретного ключей�

15

      • n = p ⋅ q
      • φ(n) = (p − 1) ⋅ (q − 1) 
      • ( e , n ) - открытый ключ, где 1 < e < φ(n)
      • ( d , n ) - закрытый ключ, где d ⋅ e ≡ 1 ( mod φ ( n ) )

16 of 46

RSA: алгоритм шифрования�

16

17 of 46

RSA: алгоритм расшифрования ��

17

18 of 46

RSA

18

19 of 46

RSA: обоснование��

19

20 of 46

RSA: обоснование���

20

21 of 46

RSA: обоснование���

21

22 of 46

RSA: обоснование���

22

23 of 46

RSA: обоснование���

23

(Малая теорема Ферма)

24 of 46

RSA: обоснование���

24

25 of 46

RSA: обоснование���

25

26 of 46

RSA: обоснование���

26

27 of 46

RSA: обоснование���

27

Китайская теорема об остатках

28 of 46

The multiplicative property of RSA

29 of 46

The multiplicative property of RSA 

29

    E(m)E(s) mod n = E(ms mod n)

​

​

    E(m)E(s) = mese mod n = (ms)e mod n = (ms mod n)e mod n

30 of 46

Pairing Oracle

31 of 46

31

32 of 46

Pairing Oracle�

32

      • Ферма принимает заказы только в шифрованном виде
      • Можно заказать только четное число яиц
      • Надо восстановить заказ конкурентов

33 of 46

Pairing Oracle�

33

34 of 46

Pairing Oracle�

34

35 of 46

Pairing Oracle�

35

36 of 46

Pairing Oracle�

36

      • Похоже на Binary Search
      • На каждой итерации делим отрезок пополам
      • Последовательно восстанавливаем M

37 of 46

Pairing Oracle�

37

38 of 46

PKCS#1 v1.5

39 of 46

PKCS#1 v1.5 

39

      • 00023572e4bcc8df4c7e53f931c1d79addcc3d0412db8723e28c84a5f6340d0f95f9836b07907669f2527eda22e1f80e6e2e4dac062326f5716fca45004c65616b696e672070617269747920616c6c6f777320666f722064656372797074696e6720612077686f6c652052534120656e63727970746564206d6573736167650a

​

      • Первые два байта 0x00, 0x02 определяют тип падинга

​

​

40 of 46

PKCS#1 v1.5 

40

      • 00023572e4bcc8df4c7e53f931c1d79addcc3d0412db8723e28c84a5f6340d0f95f9836b07907669f2527eda22e1f80e6e2e4dac062326f5716fca45004c65616b696e672070617269747920616c6c6f777320666f722064656372797074696e6720612077686f6c652052534120656e63727970746564206d6573736167650a

​

      • Ненулевой случайный падинг

​

​

41 of 46

PKCS#1 v1.5 

41

      • 00023572e4bcc8df4c7e53f931c1d79addcc3d0412db8723e28c84a5f6340d0f95f9836b07907669f2527eda22e1f80e6e2e4dac062326f5716fca45004c65616b696e672070617269747920616c6c6f777320666f722064656372797074696e6720612077686f6c652052534120656e63727970746564206d6573736167650a

​

      • Сепаратор

​

​

42 of 46

PKCS#1 v1.5 

42

      • 00023572e4bcc8df4c7e53f931c1d79addcc3d0412db8723e28c84a5f6340d0f95f9836b07907669f2527eda22e1f80e6e2e4dac062326f5716fca45004c65616b696e672070617269747920616c6c6f777320666f722064656372797074696e6720612077686f6c652052534120656e63727970746564206d6573736167650a

​

      • Открытый текст

​

​

43 of 46

PKCS#1 v1.5 

43

      • 00023572e4bcc8df4c7e53f931c1d79addcc3d0412db8723e28c84a5f6340d0f95f9836b07907669f2527eda22e1f80e6e2e4dac062326f5716fca45004c65616b696e672070617269747920616c6c6f777320666f722064656372797074696e6720612077686f6c652052534120656e63727970746564206d6573736167650a

​

​

​

​

44 of 46

PKCS#1 v1.5 

44

45 of 46

The Bleichenbacher attack

46 of 46

Вопросы?