Модуль 2. Алгебры и группы
Лекция 1 Математические методы криптографии 1. Основные понятия 2. Симметричные криптосистемы
Основные понятия криптология (kryptos - тайный, logos - наука). криптография криптоанализ. Криптография - поиск и исследование математических методов преобразования информации. Криптоанализ - исследование возможности расшифровывания информации без знания ключей.
Основные понятия разделы криптографии: Симметричные криптосистемы. Криптосистемы с открытым ключом. Системы электронной подписи. Управление ключами.
Основные понятия Основные направления использования криптографических методов передача конфиденциальной информации по каналам связи установление подлинности передаваемых сообщений хранение информации на носителях в зашифрованном виде.
Основные понятия информация, подлежащая шифрованию и дешифрованию - тексты, построенные на некотором алфавите. Алфавит - конечное множество используемых для кодирования информации знаков. Текст - упорядоченный набор из элементов алфавита. примеры алфавитов: алфавит Z буквы русского алфавита и пробел; алфавит Z256 – символы кодов ASCII и КОИ-8; бинарный алфавит - Z2 = {0,1}; восьмеричный алфавит или шестнадцатеричный алфавит;
Основные понятия Шифрование - преобразовательный процесс: исходный текст (открытый текст), заменяется шифрованным текстом. Дешифрование - обратный шифрованию процесс. На основе ключа шифрованный текст преобразуется в исходный.
Основные понятия шифрованный текст исходный текст Криптографическая система КЛЮЧ Процедура шифрования\дешифрования файлов
Основные понятия Ключ - информация, необходимая для шифрования и дешифрования текстов. Криптографическая система - семейство T преобразований открытого текста. Члены этого семейства индексируются, или обозначаются символом k; параметр k является ключом. Пространство ключей K - это набор возможных значений ключа. Обычно ключ представляет собой последовательный ряд букв алфавита.
Основные понятия Криптосистемы: симметричные с открытым ключом. В симметричных криптосистемах и для шифрования, и для дешифрования используется один и тот же ключ. В системах с открытым ключом используются два ключа - открытый и закрытый. Информация шифруется с помощью открытого ключа, который доступен всем желающим, а расшифровывается с помощью закрытого ключа, известного только получателю сообщения.
Основные понятия Электронная (цифровая) подпись - присоединяемое к тексту его криптографическое преобразование, которое позволяет при получении текста другим пользователем проверить авторство и подлинность сообщения. Криптостойкость - характеристика шифра, определяющая его стойкость к дешифрованию без знания ключа (т.е. криптоанализу). показатели криптостойкости: количество всех возможных ключей; среднее время, необходимое для криптоанализа.
Основные понятия требования к криптографическим системам защиты информации : зашифрованное сообщение должно поддаваться чтению только при наличии ключа; число операций, необходимых для определения ключа шифрования, должно быть не меньше общего числа возможных ключей; число операций, необходимых для расшифровывания информации путем перебора всевозможных ключей должно выходить за пределы возможностей современных компьютеров
Основные понятия требования к криптографическим системам защиты информации : знание алгоритма шифрования не должно влиять на надежность защиты; незначительное изменение ключа должно приводить к существенному изменению вида зашифрованного сообщения даже при использовании одного и того же ключа; структурные элементы алгоритма шифрования должны быть неизменными; дополнительные биты, вводимые в сообщение в процессе шифрования, должны быть полностью скрыты в шифрованном тексте;
Основные понятия требования к криптографическим системам защиты информации : длина шифрованного текста должна быть равной длине исходного текста; не должно быть простых и легко устанавливаемых зависимостей между ключами, последовательно используемыми в процессе шифрования; любой ключ из множества возможных должен обеспечивать надежную защиту информации; алгоритм должен допускать как программную, так и аппаратную реализацию
Симметричные криптосистемы Классификация криптографических методов Симметричные криптосистемы Гаммирование Блочные шифры Подста новки Подста новки Перестановки
Симметричные криптосистемы Многоалфавитная подстановка - замена символов исходного текста на другие (того же алфавита) Для обеспечения высокой криптостойкости требуется использование больших ключей. Перестановки – смена мест символов алфавита
Симметричные криптосистемы Гаммирование - наложение на исходный текст псевдослучайной последовательности, генерируемой на основе ключа. Блочные шифры - последовательность основных методов преобразования, применяемая к блоку (части) шифруемого текста.
Симметричные криптосистемы Перестановкой набора целых чисел (0,1,...,N-1) называется его переупорядочение. Для того чтобы показать, что целое i перемещено из позиции i в позицию (i), где 0 (i) < n, будем использовать Запись = ( (0), (1),..., (N-1)).
Симметричные криптосистемы Число перестановок из (0,1,...,N-1) равно n!=1*2*...*(N-1)*N. Введем обозначение для взаимно- однозначного отображения набора S={s0,s1,...,sN-1}, состоящего из n элементов, на себя. : S S : si s (i), 0 i < n
Симметричные криптосистемы Криптографическим преобразованием T для алфавита Zm называется Последовательность автоморфизмов: T={T(n):1 n< } T(n): Zm,n Zm,n, 1 n< Каждое T(n) является, таким образом, перестановкой n-грамм из Zm,n.
Симметричные криптосистемы Если T(i) и T(j) определены независимо при i j, число криптографических преобразований исходного текста размерности n равно (mn)! при m=33 и n=2 число различных криптографических преобразований равно 1089!.
Симметричные криптосистемы Системы подстановок Определение Подстановкой на алфавите Zm называется автоморфизм Zm, при котором буквы исходного текста t замещены буквами шифрованного текста (t): Zm Zm; : t (t). Набор всех подстановок называется симметрической группой Zm SYM(Zm).
Симметричные криптосистемы Системы подстановок Утверждение SYM(Zm) c операцией произведения является группой, т.е. операцией, обладающей свойствами: Замкнутость Ассоциативность Существование нейтрального элемента Существование обратного
Симметричные криптосистемы Системы подстановок Замкнутость произведение подстановок 1 2 является подстановкой: : t 1( 2(t)). Ассоциативность результат произведения не зависит от порядка расстановки скобок: ( 1 2) 3= 1( 2 3)
Симметричные криптосистемы Системы подстановок Существование нейтрального элемента постановка i, определяемая как i(t)=t, 0 t
Симметричные криптосистемы Системы подстановок Существование обратного для любой подстановки есть единственная обратная подстановка -1, удовлетворяющая условию 1 = 1 =i.
Симметричные криптосистемы Системы подстановок Число возможных подстановок в симметрической группе Zm называется порядком SYM(Zm) и равно m!
Симметричные криптосистемы Системы подстановок Определение. Ключом подстановки k для Zm называется последовательность элементов симметрической группы Zm: k=(p0,p1,...,p n-1,...), p n SYM(Zm), 0 n
Симметричные криптосистемы Системы подстановок Подстановка, определяемая ключом k - это криптографическое преобразованием Tk, при помощи которого осуществляется преобразование n-граммы исходного текста (x0,x1,..,xn-1) в n-грамму шифрованного текста (y0,y1,...,yn-1):
Симметричные криптосистемы Системы подстановок yi = p(xi), 0 i
Симметричные криптосистемы Системы подстановок особенности подстановки 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)
Симметричные криптосистемы Системы подстановок особенности подстановки Tk 2. Буква шифрованного текста yi является функцией только i-й компоненты ключа pi и i-й буквы исходного текста xi.
Симметричные криптосистемы Подстановка Цезаря Определение. Подмножество Cm={Ck: 0 k
Симметричные криптосистемы Подстановка Цезаря Умножение коммутативно, CkCj=CjCk=Cj+k, C0 – идентичная подстановка, а обратной к Cк является Ck-1=Cm-k, где 0
Симметричные криптосистемы Подстановка Цезаря Определение. Системой Цезаря - это моноалфавитная подстановка, преобразующая n- грамму исходного текста (x0, x1,..,xn-1) в n грамму шифрованного текста (y0,y1,...,yn-1) в соответствии с правилом Yi = Ck(xi), 0 i
Симметричные криптосистемы Подстановка Цезаря А гЙ мТ хЫ ю Б дК нУ цЬ я В еЛ оФ чЭ _ Г жМ пХ шЮ а Д зН рЦ щЯ б Е иО сЧ ъ_ в Ж йП тШ ы З кР уЩ ь И лС фЪ э
Симметричные криптосистемы Подстановка Цезаря ПРИВЕТ - тулеих