Модуль 2. Алгебры и группы. Лекция 1 Математические методы криптографии 1. Основные понятия 2. Симметричные криптосистемы. - презентация

1 Модуль 2. Алгебры и группы

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

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

4 Основные понятия разделы криптографии: Симметричные криптосистемы. Криптосистемы с открытым ключом. Системы электронной подписи. Управление ключами.

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

6 Основные понятия информация, подлежащая шифрованию и дешифрованию - тексты, построенные на некотором алфавите. Алфавит - конечное множество используемых для кодирования информации знаков. Текст - упорядоченный набор из элементов алфавита. примеры алфавитов: алфавит Z буквы русского алфавита и пробел; алфавит Z256 – символы кодов ASCII и КОИ-8; бинарный алфавит - Z2 = {0,1}; восьмеричный алфавит или шестнадцатеричный алфавит;

7 Основные понятия Шифрование - преобразовательный процесс: исходный текст (открытый текст), заменяется шифрованным текстом. Дешифрование - обратный шифрованию процесс. На основе ключа шифрованный текст преобразуется в исходный.

8 Основные понятия шифрованный текст исходный текст Криптографическая система КЛЮЧ Процедура шифрования\дешифрования файлов

9 Основные понятия Ключ - информация, необходимая для шифрования и дешифрования текстов. Криптографическая система - семейство T преобразований открытого текста. Члены этого семейства индексируются, или обозначаются символом k; параметр k является ключом. Пространство ключей K - это набор возможных значений ключа. Обычно ключ представляет собой последовательный ряд букв алфавита.

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

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

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

13 Основные понятия требования к криптографическим системам защиты информации : знание алгоритма шифрования не должно влиять на надежность защиты; незначительное изменение ключа долж­но приводить к существенному изменению вида зашифрованного сообщения даже при использовании одного и того же ключа; структурные элементы алгоритма шифрования должны быть неизменными; дополнительные биты, вводимые в сообщение в процессе шифрования, должны быть полностью скрыты в шифрованном тексте;

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

15 Симметричные криптосистемы Классификация криптографических методов Симметричные криптосистемы Гаммирование Блочные шифры Подста новки Подста новки Перестановки

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

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

18 Симметричные криптосистемы Перестановкой набора целых чисел (0,1,...,N-1) называется его переупорядочение. Для того чтобы показать, что целое i перемещено из позиции i в позицию (i), где 0 (i) < n, будем использовать Запись = ( (0), (1),..., (N-1)).

19 Симметричные криптосистемы Число перестановок из (0,1,...,N-1) равно n!=1*2*...*(N-1)*N. Введем обозначение для взаимно- однозначного отображения набора S={s0,s1,...,sN-1}, состоящего из n элементов, на себя. : S S : si s (i), 0 i < n

20 Симметричные криптосистемы Криптографическим преобразованием T для алфавита Zm называется Последовательность автоморфизмов: T={T(n):1 n< } T(n): Zm,n Zm,n, 1 n< Каждое T(n) является, таким образом, перестановкой n-грамм из Zm,n.

21 Симметричные криптосистемы Если T(i) и T(j) определены независимо при i j, число криптографических преобразований исходного текста размерности n равно (mn)! при m=33 и n=2 число различных криптографических преобразований равно 1089!.

22 Симметричные криптосистемы Системы подстановок Определение Подстановкой на алфавите Zm называется автоморфизм Zm, при котором буквы исходного текста t замещены буквами шифрованного текста (t): Zm Zm; : t (t). Набор всех подстановок называется симметрической группой Zm SYM(Zm).

23 Симметричные криптосистемы Системы подстановок Утверждение SYM(Zm) c операцией произведения является группой, т.е. операцией, обладающей свойствами: Замкнутость Ассоциативность Существование нейтрального элемента Существование обратного

24 Симметричные криптосистемы Системы подстановок Замкнутость произведение подстановок 1 2 является подстановкой: : t 1( 2(t)). Ассоциативность результат произведения не зависит от порядка расстановки скобок: ( 1 2) 3= 1( 2 3)

25 Симметричные криптосистемы Системы подстановок Существование нейтрального элемента постановка i, определяемая как i(t)=t, 0 t

26 Симметричные криптосистемы Системы подстановок Существование обратного для любой подстановки есть единственная обратная подстановка -1, удовлетворяющая условию 1 = 1 =i.

27 Симметричные криптосистемы Системы подстановок Число возможных подстановок в симметрической группе Zm называется порядком SYM(Zm) и равно m!

28 Симметричные криптосистемы Системы подстановок Определение. Ключом подстановки k для Zm называется последовательность элементов симметрической группы Zm: k=(p0,p1,...,p n-1,...), p n SYM(Zm), 0 n

29 Симметричные криптосистемы Системы подстановок Подстановка, определяемая ключом k - это криптографическое преобразованием Tk, при помощи которого осуществляется преобразование n-граммы исходного текста (x0,x1,..,xn-1) в n-грамму шифрованного текста (y0,y1,...,yn-1):

30 Симметричные криптосистемы Системы подстановок yi = p(xi), 0 i

31 Симметричные криптосистемы Системы подстановок особенности подстановки Tk 1. Исходный текст шифруется посимвольно. Шифрования n-граммы (x0,x1,..,xn-1) и ее префикса (x0,x1,..,xs-1) связаны соотношениями Tk(x0,x1,..,xn-1)=(y0,y1,...,yn-1) Tk(x0,x1,..,xs-1)=(y0,y1,...,ys-1)

32 Симметричные криптосистемы Системы подстановок особенности подстановки Tk 2. Буква шифрованного текста yi является функцией только i-й компоненты ключа pi и i-й буквы исходного текста xi.

33 Симметричные криптосистемы Подстановка Цезаря Определение. Подмножество Cm={Ck: 0 k

34 Симметричные криптосистемы Подстановка Цезаря Умножение коммутативно, CkCj=CjCk=Cj+k, C0 – идентичная подстановка, а обратной к Cк является Ck-1=Cm-k, где 0

35 Симметричные криптосистемы Подстановка Цезаря Определение. Системой Цезаря - это моноалфавитная подстановка, преобразующая n- грамму исходного текста (x0, x1,..,xn-1) в n грамму шифрованного текста (y0,y1,...,yn-1) в соответствии с правилом Yi = Ck(xi), 0 i

36 Симметричные криптосистемы Подстановка Цезаря А гЙ мТ хЫ ю Б дК нУ цЬ я В еЛ оФ чЭ _ Г жМ пХ шЮ а Д зН рЦ щЯ б Е иО сЧ ъ_ в Ж йП тШ ы З кР уЩ ь И лС фЪ э

37 Симметричные криптосистемы Подстановка Цезаря ПРИВЕТ - тулеих