Симметричные криптосистемы. Лекция 1. Основные понятия и определения криптографии

1. Дисциплина: Основы криптографии

Подготовил
д.т.н. профессор кафедры ЗСС
Яковлев Виктор Алексеевич
E-mail:[email protected]
1

2. Часть 1 Симметричные криптосистемы Лекция 1. Основные понятия и определения криптографии

2

3. 1. Организация курса

Слово криптография в переводе с греческого означает тайное письмо.
Примитивная криптография возникла с появлением письменности у
разных народов.
Задача курса “Основы криптографии” состоит в
изложении основных понятий современной
криптографии в ориентации на студентов, обучающихся
по направлению 210700.62 «Инфокоммуникационные
технологии и системы связи» , Профиль №2
При обучении по этому направлению не ставится задача подготовить
будущих профессиональных криптографов, а с другой стороны, это не
является поверхностным изложением основных определений и
параметров современных криптосистем. Обучаемые должны усвоить их
основные функции, возможные способы нападения на них со стороны
злоумышленников, а также принципы построения современных
алгоритмов шифрования, аутентификации и обеспечения целостности
сообщений.
3

4.

Невозможно изучать стойкость криптосистем без рассмотрения методов их
криптоанализа (т. е. дешифрования без знания ключа). Однако
криптоанализ требует весьма обширных знаний в области математики
и вычислительной техники, что выходит за рамки базовых курсов для
студентов. По этой причине в данном курсе рассматриваются лишь
некоторые (хотя и вполне современные) методы криптоанализа,
которые помогают пояснить необходимость тех или иных усложнений
криптоалгоритмов.
Значительное внимание в курсе уделяется побочным атакам на шифры,
поскольку они часто не требуют для своего пояснения привлечения
серьезного математического аппарата, однако пренебрежение этими
атаками приводит к простому дешифрованию криптосистем без знания
ключа.
Курс состоит из двух частей, . Первая часть посвящена традиционной
(симметричной или одноключевой) криптографии, включая также
некоторые вопросы аутентификации. Вторая часть посвящена
несимметричной (двухключевой) криптографии, называемой иначе
криптографией с открытым ключом, а также вопросам выполнения
цифровой подписи и криптографических протоколов.
4

5.

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

6.

Основная терминология по курсу приведена в последующих разделах.
Здесь же будет дано лишь несколько общих определений:
- законные (или легальные) пользователи криптосистемы, которые
обладают секретными ключами, и незаконные (или нелегальные)
пользователи, которые не обладают этими ключами и стремятся их
найти, а также прочитать зашифрованное сообщение или нарушить его
целостность (т. е. подделать его или фальсифицировать авторство), а
также нарушить секретность выполняемых протоколов,
-криптоаналитиком будем называть пользователя, который пытается
разработать методы для нарушения секретности криптосистемы.
(Заметим, что криптоаналитик не обязательно является
недружественным пользователем, поскольку он может применять свои
методы для проверки стойкости существующих или разрабатываемых
легальных криптосистем).
-взломом или атакой на криптосистему будем называть попытку
дешифрования (криптоанализа) криптосистемы без знания ключа или
попытку подделки цифровой подписи , а также нарушения секретности
криптопротокола .
-нарушитель называется пассивным, если он только пытается прочитать
сообщение, и активным, если он стремится изменить (подделать)
сообщение или криптопротокол.
При подготовке куса использовано учебное пособие В.И.Коржик ,
В.П.Просихин , “Основы криптографии “, Линк, 2008.
6

7. Программа курса Часть I. Симметричные криптосистемы

Модель криптосистемы
Принцип Керхгоффа
Типы криптосистем
Влияние ошибок в криптограмме на дешифрование
Идеальные (безусловно стойкие) КС
Необходимые и достаточные условия для построения идеальных КС
КС с единственным и неединственным дешифрованием сообщений при
заданной криптограмме. Расстояние единственности
Вывод формулы расстояния единственности для произвольного шифра
Пояснения к теореме Шеннона–Хеллмана
Вычислительно стойкие шифры
Способы построения вычислительно стойких блоковых шифров и их
криптоанализ
Принцип построения блоковых шифров
Схема Фейстеля
Подстановочно-перестановочные шифры (ППШ)
7

8.

Основные методы криптоанализа блоковых шифров
Элементы теории конечных полей [8, 9]
Модификации блоковых шифров
Многократное шифрование
Примеры практически используемых блоковых шифров
DES,AES,RC. ГОСТ 28147-89
8

9.

способы построения и криптоанализ потоковых шифров на основе
использования линейных рекуррентных регистров сдвига
Линейный рекуррентный регистр и его основные свойства
Нелинейные узлы усложнения, используемые для построения потоковых
шифров
Построение датчика шифрующей гаммы на основе использования ЛРР с
управляемым тактированием
Основные способы криптоанализа потоковых шифров
Пример практически используемого в стандарте GSM потокового шифра
A5/1
Аутентификация сообщений:
Общая структура (техника) аутентификации
Классификация систем аутентификации и характеристики их
эффективности
Безусловно стойкие системы аутентификации
Вычислительно стойкие системы аутентификации
Пример практически используемой вычислительно стойкой системы
аутентификации (режим выработки имитовставки для ГОСТ 28147)
9

10. Часть II. Криптосистемы с открытым ключом

Идея построения криптографии с открытым ключом (ОК)
Математический базис КОК:
Основы теории чисел
Представление чисел в различных позиционных системах Битовые
операции
Делимость. Алгоритм Евклида
Операции по числовому модулю (сравнения, конгруэнтность)
Возведение в степень
Вычисление дискретного логарифма
Малая теорема Ферма
Теорема Эйлера (обобщение теоремы Ферма)
10

11.

Генерирование простых чисел
Важнейшие тесты по проверке простоты чисел
Построение криптосистем с открытым ключом
Криптосистема РША (Райвеста–Шамирa–Адлемана)
( Метод формирования пар открытых/закрытых ключей для КС РША
Шифрование в КС РША, Дешифрование в КС РША)
Стойкость КС РША
11

12.

Метод распределения ключей Диффи–Хеллмана
КС Эль-Гамаля
Построение КС на основе использования эллиптических кривых
Элементы теории эллиптических кривых над конечными полями
Задание КС над эллиптическими кривыми
Обобщение КС Эль-Гамаля на случай эллиптических кривых
Построение системы распределения ключей Диффи– Хеллмана над
эллиптическими кривыми
12

13.

Цифровые подписи с использованием КС ОК
Основные требования, предъявляемые к ЦП
ЦП на основе различных КС ОК
ЦП на основе КС РША
ЦП на основе КС Эль-Гамаля
Обобщение ЦП на случай эллиптических кривых
Бесключевые хеш-функции
Основные требования, предъявляемые к криптографическим ХФ
Способы построения стойких криптографических бесключевых ХФ
Выводы о возможности построения стойких ЦП
13

14. Основная литература по курсу

В.И.Коржик , В.П.Просихин , “Основы криптографии “,
Линк, 2008.
Дополнительная литература по курсу
1.Б.Шнейер , “Прикладная криптография “, Триумф , 2002.
2.Menezes A.J.,et all “Handbook of applied cryptography”,CRC,1996.
3.Молдавян Н.А.. Молдавян А.А. .”Введение в криптосистемы с
открытым
ключом”, БХВ, 2005.
4.Бабаш А.В.,Шанкин Г.П.. “История криптографии “, Гелиос , 2002.
5.Henk C.A. van Tilborg ,”Fundamentals of Cryptography”, Kluwer, 2001.
6.Болотов А.А. и др. “Элементарное введение в эллиптическую
криптографию”,КомКнига, 2006
14

15. Перечень основных лабораторных работ по курсу (часть из них может не использоваться или объединяться)

Часть 1
1. Исследование идеальной системы шифрования
2.Криптоанализ блокового шифра тотальным перебором ключей
6. Основы теории конечных полей
7.Исследование блокового шифра AES.
8.Исследование свойств линейного рекуррентного регистра (ЛРР)
9.Криптоанализ потокового шифра на основе использования алгоритма
Месси-Берлекэмпа
10.Криптоанализ потокового шифра на основе корреляционного метода
11.Исследование датчика шифрующей гаммы , реализованного основе
ЛРР с управляемым тактированием
12.Исследование потокового шифра A5/1.
13.Исследование метода безусловно стойкой аутентификации сообщений
15

16. Часть 2

1.Основы теории чисел
2.Тестирование простых чисел и нахождение квадратичных вычетов
3.Исследование криптосистемы с открытым ключом РША
4.Исследование криптосистемы с открытым ключом на основе
эллиптических кривых
5.Исследование бесключевой хеш-функции , построенной по схеме
Матиаса-Мейера-Осеаса
6.Исследование криптопротокола с разделением секретных данных между
пользователями
7.Исследование протокола идентификации на основе концепции нулевых
знаний.
16

17. Отчетность по курсу

Выполнение всех лабораторных работ .
Экзамен по теоретическому курсу .
17

18. В результате освоения дисциплины студент должен

знать:
• основные математические методы и алгоритмы шифрования, и
дешифрования сообщений (ОК-1, ОК-2, ОК-9, ПК-1);
• основы электронной (цифровой) подписи в телекоммуникационных
системах (ОК-1, ОК-9, ПК-1);
• принципы работы, структурные схемы, протоколы и способы систем
электронной подписи (ОК-1, ОК-2, ОК-5, ОК-6, ОК-9, ПК-17);;
уметь:
• пользоваться методами теории чисел (ОК-1, ОК-9, ПК-1);
• составлять протоколы шифрования и расшифрования сообщений (ОК-1,
ОК-9, ПК-16, ПК-3);
• рассчитывать основные характеристики и параметры криптографических
алгоритмов защиты информации (ОК-1, ОК-9, ПК-1);
• оценивать теоретическую и практическую стойкость шифров (ОК-9, ПК);
18

19.

владеть:
приемами проектирования типовых алгоритмов криптозащиты и
криптоанализа сообщений (ОК-1, ОК-9, ПК-18);
методами компьютерного моделирования алгоритмов шифрования и
расшифрования сообщений (ОК-1, ПК-2)
навыками экспериментального исследования данных алгоритмов (ОК9)
методами оценки криптостойкости систем защиты информации (ОК-9,
ПК-17).
19

20. 2. Основные этапы исторического развития криптографии

4-й в. до н.э. Шифр «Сцитала»
1-й в. до н.э. Шифр Цезаря
17-й в. н.э. Шифр Виженера
1917 г. Шифр Вернама
1926 г. Энигма
1948 г. Теория Шеннона
1976 г. Криптография с открытым ключом
1977 г. Стандарт шифрования DES (США)
1989 г. ГОСТ 28147
1994г. ГОСТ Р 34.10, Р 34.11
2000 г. Усиленный стандарт шифрования
AES (США)
2001 г. ГОСТ Р 34.10
ГОСТ Р 34.11-2013, ГОСТ Р 34.10-2013

21. Количество пользователей, использующих криптографическую защиту

Сцитала

22. Сцитала

Шифр Цезаря: Mi→Mi+1
Защита информации
Ибьйубайнхпснбчйй
АБВГД
ЕЖЗИЙ
КЛМНО
ПРСТУ
ФХЦЧШ
ЩЬЫЭЮ
Я_

23.

Шифр Виженера
Ei=Мi +Кi
Защита информации
ПриветПриветПривет
чсвлшу….
Нумерация символов русского алфавита
ПробелА
Б
В
Г
Д
Е
Ж З
И
Й
0
2
3
4
5
6
7
8
9
10 11 12 13 14 15
Ц
Ч
П
1
Р
С
Т
У
Ф
Х
Ш Щ
К
Ь,
Л
М Н
Ы Э
О
Ю Я
Ъ
16
17
18
19
20
21
22
23
24
25
26
27 28 29 30 31

24. Шифр Виженера

Основные виды криптографических
преобразований
Шифрование
- сохранение тайны
передаваемого сообщения;
Аутентификация - установление
подлинности переданного сообщения или
пользователя информационновычислительной системы;
Электронная цифровая подпись подтверждение подлинности электронного
документа и его авторства.

25. Основные виды криптографических преобразований

4. Модель системы шифрования
Нарушитель
Отправитель
А
Е
М
Шифрование f
Е
Канал
связи
Расшифрование g
КРШ
КШ
ЦРК
М – сообщение
Е – криптограмма
К – ключ
Е
М
Получатель
В

26. 4. Модель системы шифрования

Описание модели шифрования
Описание источника
сообщений
M n M 1 , M 2 , , M n
n
Описание источникаОписание источника
криптограмм
ключей
En=E1,E2,….En
m {M }
{En}
n
{P(E
{P ( M )}
SM m
n
KN=K1 K2 …KN
{KN}
)}
{P(KN)}
SE=mn
SK=LN
n
K L

27. Описание модели шифрования

Статистика букв русского языка
пробел
0.175
О
0.090
Е,Ё
0.072
А
0.062
И
0.062
Т
0.053
Н
0.053
С
0.045
Р
0.040
В
0.038
Л
0.035
К
0.028
М
0.026
Д
0.025
П
0.023
У
0.021
Я
0.018
Ы
0.016
3
0.016
Ь,Ъ
0.014
Б
0.014
Г
0.013
Ч
0.012
Й
0.010
Х
0.009
Ж
0.007
Ю
0.006
Ш
0.006
Ц
0.004
Щ
0.003
Э
0.003
Ф
0.002

28. Статистика букв русского языка

Основные уравнения системы
шифрования
En=f(Mn,KNш)- уравнение шифрования
Mn=g(En,KNрш)- уравнение
дешифрования

29. Основные уравнения системы шифрования

Принцип Керхгоффа
Согласно этому принципу предполагается, что в данной модели
любому пользователю известно все, за исключением ключа
расшифрования Крш.
Основные типы криптографических атак:
1) только при известной криптограмме Е;
2) при известной криптограмме Е и соответствующей ей части
сообщения M;
3) при специально выбранном сообщении M и соответствующей
ему криптограмме E.
30

30. Принцип Керхгоффа

Типы криптосистем
По типу ключа криптосистемы делятся на симметричные (kш = kд = k) и
несимметричные (kш kд). Несимметричные криптосистемы называют также
криптосистемами с открытым ключом. В этой части пособия будут
рассматриваться только симметричные криптосистемы.
По способу формирования криптограммы из сообщения :
блоковые криптосистемы и потоковые криптосистемы.
Криптосистема называется блоковой, если каждый блок сообщения
определенной длины шифруется по одному и тому же правилу; блок
криптограммы имеет обычно ту же длину, что и блок сообщения (рис. 1.1).
Рис. 1.1. Блоковое шифрование
31

31. Типы криптосистем

Граф системы шифрования
а)
L
n
{M }
M
{K }
1
M
n
{E }
E
1
K
M
M
E
2
i
2
в)
K s
E
M
i
m n
E
I
K
M
г)
M
E
K
I
K
E
I
K
E
M
m n
E
K
I
I

32. Граф системы шифрования

Пример системы шифрования
M1=0
M2=1
K1
E1=0
K2
E2=1

33. Пример системы шифрования

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

34. Стойкость систем шифрования

Атаки нарушителя
1. Криптоанализ ведется, только на
основе, перехваченных криптограмм;
2.Криптоанализ ведется на основе,
перехваченных криптограмм и
соответствующих им открытых
сообщений.
3.Криптоанализ ведется на основе
выбираемого противником открытого
сообщения;

35. Атаки нарушителя

Классы систем шифрования
Бузусловно стойкие
или идеальные,
совершенные
Вычислительно
стойкие

36. Классы систем шифрования

Безусловно стойкие (идеальные)
системы шифрования
Безусловно стойкой системой шифрования (БССШ) называется
система шифрования, в которой любая криптограмма (в отсутствии у
злоумыщленника ключа) не содержит дополнительных сведений к
априорно известным о сообщении, зашифрованном в эту криптограмму.
Лучшим способом дешифрования криптограммы БССШ является угадывание
одного из возможных сообщений источника Математически условие АССШ может
быть записано в виде.
.
P Mi E j
P( M E ) P( M )
- условная вероятность того,
зашифровано криптограммой Ej;
P M i – априорная (при неизвестной
присутствия сообщения Mi.
что
сообщение
криптограмме)
Mi
было
вероятность

37. Безусловно стойкие (идеальные) системы шифрования

Эквивалентное определение БССШ
I ( E; M ) 0
информация
I ( E ; M ) H ( M ) H ( M E ) шенноновская
криптограмме E о сообщении M ).
j
H (M )
H (M E)
в
i
- энтропия источника сообщений
- энтропия источника сообщений
38

38. Эквивалентное определение БССШ

n = P ( M n ) log P ( M n )
H (M ) å i 2 i
M in
max H ( M n )
1
n
lim
H
(
M
)
H (M ) n n
=
n log 2 m
Энтропия источника
H ( M n ) nH (M )
D log2 m H ( M )
Избыточность источника
D
H (M )
1
r
log 2 m
log 2 m
Относительная избыточность источника

39.

Пример идеальной КС с гаммированием по mod 2
.
Пусть
N
M , K ,E 0,1
– двоичные цепочки длины N.
Криптограмма
E M K
где каждый бит сообщения складывается с каждым битом ключа по mod 2, имеет вид
M 000111
K 100101
E 100010
Дешифрование : M E K

40.

Вычислительно стойкие
системы шифрования
Система шифрования называется вычислительно стойкой (ВССШ),
если вскрытие такой системы возможно, но даже наилучший
алгоритм вскрытия требует необозримо большого времени
или необозримо большой памяти устройств, с помощью которых
проводится криптоанализ
Время криптоанализа определяется:
1. Сложностью алгоритма дешифрования;
2. Быстродействием вычислительных устройств,
осуществляющих дешифрование

41. Вычислительно стойкие системы шифрования

Сложность алгоритмов криптоанализа должна соответствовать
сложности решения сложной задачи
Основные подходы к криптоанализу:
1.
2.
3.
4.
5.
Тотальный перебор ключей
Анализ статистических особенностей криптограмм
Линейный криптоанализ
Дифференциальный криптоанализ
Другие
Быстродействие вычислительных устройств 1010- 1012 операций/с
Быстродействие ЭВМ увеличивается в 4 раза каждые 3 года

42.

Понятие расстояния единственности
Ключ (длина L)
Криптограмма (длина n)
Определение: Расстоянием единственности (РЕ)
называется минимальное количество символов
криптограммы, необходимое дляn.однозначного восстановления
истинного ключа (сообщения) (без каких- либо ограничений
на время его нахождения)
n*=NlogL/(logm-H(M))
H(M)=
lim H(Mn)/n – энтропия источника
n→∞

43. Достаточное условие существования АССШ

Пример расчета расстояния
единственности
Для русского языка m=32
Энтропия H(M)=1,5-2,5 бит/символ
N=128, L=2.
Тогда расстояние единственности
n*=37-51 символ.

44. Условия существования АССШ

Статистика букв русского языка
пробел
0.175
О
0.090
Е,Ё
0.072
А
0.062
И
0.062
Т
0.053
Н
0.053
С
0.045
Р
0.040
В
0.038
Л
0.035
К
0.028
М
0.026
Д
0.025
П
0.023
У
0.021
Я
0.018
Ы
0.016
3
0.016
Ь,Ъ
0.014
Б
0.014
Г
0.013
Ч
0.012
Й
0.010
Х
0.009
Ж
0.007
Ю
0.006
Ш
0.006
Ц
0.004
Щ
0.003
Э
0.003
Ф
0.002