Системы гарантированной секретности (теоретически стойкие криптосистемы)

1. СИСТЕМЫ ГАРАНТИРОВАННОЙ СЕКРЕТНОСТИ (ТЕОРЕТИЧЕСКИ СТОЙКИЕ КРИПТОСИСТЕМЫ)

2. Понятие стойкости

• Теоретическая стойкость
(принципиальная невозможность атаки)
• Практическая стойкость (необходимость
для атаки таких ресурсов, стоимость
которых многократно превышает
стоимость приобретаемой в случае
успеха выгоды)
2

3. Криптосистема Цезаря (Вижинера)

k
ai i 1, 2, , n
ri i 1, 2, , n
m
m A
M
ai* ai ri
ai a ri
*
i
m
m
ai A, i 1, 2,
A
ri R (0) , i 1, 2,
R (0)
,n
,n
m R (0)
, i 1, 2,
,n
a m ri
*
i
m
, i 1, 2,
,n
3

4. Короткопериодический ключ

a1 a2 a3 a4 a5 a6 a7 a8 a9 a10 a11
r1 r2 r3
an 3 an 2 an 1 an
r1 r2 r3
r1 r2 r3
r1 r2 r3
r1 r2
a1* a2* a3* a4* a5* a6* a7* a8* a9* a10* a11*
r3
an* 3 an* 2 an* 1 an*
Бородин А. В., МиСЗКИ, 2010
4

5. Системы гарантированной секретности

1) R
(0)
A
2) ri i 1, 2,
,n
3) ri i 1, 2,
,n
R
(0)
5

6. Проблема получения случайных равномерно распределенных над заданным алфавитом последовательностей на компьютерах с фон

Проблема получения
случайных равномерно
распределенных
над заданным алфавитом
последовательностей
на компьютерах с фон
Немановской архитектурой
6

7. Принципы фон Неймана

Принцип двоичности
Принцип программного управления
Принцип однородности памяти
Принцип адресуемости памяти
Принцип последовательного
программного управления
6. Принцип условного перехода
1.
2.
3.
4.
5.
Burks A. W., Goldstine H. H., Neumann J. Preliminary Discussion of the Logical
Design of an Electronic Computing Instrument. — Institute for Advanced
Study, Princeton, N. J., July 1946.
7

8. Принстонская и гарвардская архитектуры компьютеров

• Принстонская архитектура (фон Неймана)
• Гарвардская архитектура — архитектура
ЭВМ, отличительным признаком которой
является раздельное хранение и обработка
команд и данных. Архитектура была
разработана Говардом Эйкеном в конце 1930х годов в Гарвардском университете.
8

9. На компьютерах с полностью фон Неймановской архитектурой генерация случайности не возможна!!!

9

10. Все ли компьютеры имют архитектуру фон Неймана?

10

11. Наивные подходы к получению случайности в вычислительных системах

• Использование «не фон Неймановости»
человеко-машинных систем
• Использование векового таймера
11

12. Физические источники случайности

• Сцинтилляционные источники
12

13. Спинтарископ

13

14.

• Механические источники случайности
Лототроны
14

15.

• Электрические источники
- Шум газового разряда
15

16.

- Шумовые вакуумные диоды
Шумовой
вакуумный
диод 2Д2С
16

17.

- Шумовые полупроводниковые диоды
17

18.

18

19. ФЛИККЕР-шум

Фликкер-шум (фликкерный шум, 1/f шум,
иногда розовый шум в узком прикладном
понимании такого термина)
Спектральная плотность
розового шума
определяется
формулой ~1 / f
(плотность обратно
пропорциональна
частоте), то есть он
является равномерным
в логарифмической
шкале частот.
19

20.

- Тепловой шум проволочных резисторов
R3
R1
R2
R1 = R 2
Бородин А. В., МиСЗКИ, 2010
20

21. Математические основы и системотехнические решения извлечения случайности в условиях наличия ЭМП различной природы

Математические основы
и системотехнические решения
извлечения случайности в условиях
наличия ЭМП различной природы
21

22. Решение «в лоб»

ЭМП
ИШ
БП
ИУ
АЦП
И
u u
Бородин А. В., МиСЗКИ, 2010
22

23. Решение с компенсацией ЭМП

ИШ1
ИУ1
ЭМП
ИШ2
БП
s1 t e1 t
В
ИУ2
s t
АЦП
И
s2 t e2 t
u u
Бородин А. В., МиСЗКИ, 2010
23

24. Решение с компенсацией ЭМП

s t s1 t e1 t s2 t e2 t
s1 t s2 t e1 t e2 t
s t s1 t s2 t e1 t e2 t
s t s1 t s2 t
e1 t e2 t
24

25. Математическое обоснование выбора принципа АЦП

Проблемы:
1) Переход от нормального
распределения к равномерному
2) «Качания» питающих напряжений
25

26. Теорема

k k Z
xk 1 xk b 0
2
1
1 x
x
exp
2
2
k Z
k Z
x
x
2 k 1
2k
, x2 k
, x2 k 1
26

27. Геометрическая интерпретация теоремы

x
x
x 4
x 3
x 2
x 1
x1
x0
x3
x2
x5
x4
a
b
b
b
b
b
b
b
b
b
Бородин А. В., МиСЗКИ, 2010
27

28. План доказательства теоремы

F P x k Z x2 k , x2 k 1 P x
xk k b a, k Z
k Z
x
2 k 1
, x2 k
F 0 0
F
0
a
F a 0 a
28

29. АЦП принадлежности

Z
Z n n, n 1,
, 1, 0, 1, 2,
, n 1, n
29

30. Криптоанализ систем гарантированной секретности

ВОЗМОЖНО или НЕ ВОЗМОЖНО ?
30

31.

Два подхода:
1) Ни что не случайно.
2) Идея модуляции среды.
О попытках:
источник 22 по «старым» лекциям!
31

32. Памятка о формате файлов для сдачи лабораторных работ

• Синтаксис именования
• Семантика содержания
32

33. Формальная грамматика именования

<Имя архивного файла> ::= <Идентификатор лабораторной работы>.zip
<Имя файла пояснительной записки> ::= <Идентификатор лабораторной работы>.rtf
<Идентификатор лабораторной работы> ::= <Группа>.<Работа>.<ФИО>.<Версия>
<Группа> ::= <Поток><Номер>
<Работа> ::= LR<Номер>
<ФИО> ::= <Фамилия><И><О><Полный тезка>
<Версия> ::= v<Номер>
<Поток> ::= PS | VM | IVT
<Номер> ::= <Цифра><Цифра>
<Фамилия> ::= <Прописная буква><Последовательность строчных букв>
<И> ::= <Прописная буква>
<О> ::= <Прописная буква>
<Полный тезка> ::= | <Цифра>
<Последовательность строчных букв> ::= | <Последовательность строчных букв><Строчная буква>
<Прописная буква> ::= A | B | ... | Z
<Строчная буква> ::= a | b | ... | z
<Цифра> ::= 0 | 1 | ... | 9
Здесь: – «пустой» символ
33