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

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

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

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

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

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

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

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

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

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

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

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

ЦП на основе различных КС ОК
ЦП на основе КС РША
ЦП на основе КС Эль-Гамаля
Обобщение ЦП на случай эллиптических кривых


Бесключевые хеш-функции
Основные требования, предъявляемые к криптографическим ХФ
Способы построения стойких криптографических бесключевых ХФ
Выводы о возможности построения стойких ЦП

Линк, 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

использоваться или объединяться)

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

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

.

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

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

до н.э. Шифр Цезаря

1976 г. Криптография с открытым ключом

1977 г. Стандарт шифрования DES (США)

1948 г. Теория Шеннона

1926 г. Энигма

1917 г. Шифр Вернама

1994г. ГОСТ Р 34.10, Р 34.11

2001 г. ГОСТ Р 34.10

2000 г. Усиленный стандарт шифрования AES (США)

ГОСТ Р 34.11-2013, ГОСТ Р 34.10-2013

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

любому пользователю известно все, за исключением ключа расшифрования Крш.

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

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

Рис. 1.1. Блоковое шифрование

нахождение (вычисление) ключа или открытого сообщения в предположении выполнения ряда условий.

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

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

Лучшим способом дешифрования криптограммы БССШ является угадывание
одного из возможных сообщений источника Математически условие АССШ может
быть записано в виде.
.

- условная вероятность того, что сообщение Mi было зашифровано криптограммой Ej;

– априорная (при неизвестной криптограмме) вероятность присутствия сообщения Mi.

источника сообщений

- энтропия источника сообщений

,

– двоичные цепочки длины N. Криптограмма

где каждый бит сообщения складывается с каждым битом ключа по mod 2, имеет вид

Дешифрование :

.

.

.

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

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

криптоанализу:

Тотальный перебор ключей
Анализ статистических особенностей криптограмм
Линейный криптоанализ
Дифференциальный криптоанализ
Другие

Быстродействие вычислительных устройств 1010- 1012 операций/с

Быстродействие ЭВМ увеличивается в 4 раза каждые 3 года

каждое сообщение M преобразуется в каждую криптограмму E при помощи одного и того же числа ключей SK и все ключи равновероятны, т.е.

М1

М2

Е1

Е2

сообщения

N=c*n

T=1сутки
Условия передачи - АССШ
Требуется найти длину ключа N.

Решение
Определим длину переданного сообщения за время 1сутки
N=1сутки*10Мбит/с=24*60*60*107=8,54*1011бит≈1011байт.
Если в качестве носителей ключа использовать CD емкостью
700Мбайт, то для обеспечения шифрованной связи (пересылки
и хранения ключа) необходимо расходовать 154 CD в сутки!.

КN

КN

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

.

H(M)=

n*=NlogL/(logm-H(M))

lim H(Mn)/n – энтропия источника

n→∞

L=2.

Тогда расстояние единственности
n*=37-51 символ.