Криптография Цуга Н.А

Федеральное государственное бюджетное образовательное учреждение высшего профессионального образования

НОВОСИБИРСКИЙ ГОСУДАРСТВЕННЫЙ АРХИТЕКТУРНО-СТРОИТЕЛЬНЫЙ УНИВЕРСИТЕТ (СИБСТРИН)

Кафедра прикладной математики

Реферат по теме:

Криптография и криптоанализ. Криптоалгоритмы.

Выполнила: Цуга Н.А.

Группа №223

Проверила: Федорова Н.Н.

Дата сдачи: 07.12.14

Новосибирск 2014

Оглавление

Введение ..............................................................................................................................................		3
1.	Что есть криптография ее значения и функции..................................................................	4
2.	Первые методы криптографии ...............................................................................................	5
2.1	Скитала........................................................................................................................................................	5
	Алгоритм шифрования ................................................................................................................................	6
	Алгоритм дешифровки ................................................................................................................................	7
2.2	Доска Полибия ...........................................................................................................................................	8
3.	Криптоалгоритмы......................................................................................................................	9
3.1	Симметричные алгоритмы шифрования.................................................................................................	9
	Шифр Цезаря..................................................................................................................................................	9
3.2	Асимметричные алгоритмы шифрования .............................................................................................	10
4.	Криптоанализ ...........................................................................................................................	12
4.1	Частотный анализ ....................................................................................................................................	12
4.2	Дифференциальный криптоанализ........................................................................................................	13
4.3	Радужная таблица....................................................................................................................................	14
4.4	Статистичекий криптоанализ..................................................................................................................	14
Заключение.......................................................................................................................................		16
Список используемой литературы: .............................................................................................		17

Введение

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

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

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

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

1. Что есть криптография ее значения и функции

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

Криптосистема - семейство выбираемых с помощью ключа обратимых преобразований,

которые преобразуют защищаемый открытый текст в шифрограмму и обратно.

Желательно, чтобы методы шифрования обладали минимум двумя свойствами:

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

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

2. Первые методы криптографии

2.1 Скитала

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

Согласно Томасу Келли самое первое известное упоминание этого слова в письменном источнике датируется 650 гг до н. э. и принадлежит греческому поэту Архилоху. Сохранилось всего несколько строк, из которых можно сделать вывод, что слово «скитала» употребляется либо в значении письменного сообщения, обмотанного вокруг палки для удобства транспортировки, либо вообще не имеет отношения к рукописному посланию.

Шифруемый текст писался на пергаментной ленте по длине палочки, после того как длина палочки оказывалась исчерпанной, она поворачивалась и текст писался далее, пока либо не заканчивался текст, либо не исписывалась вся пергаментная лента. В последнем случае использовался очередной кусок пергаментной ленты. Дешифровка выполнялась с использованием палочки такого же диаметра.

Таким образом, длина блока n определялась длиной и диаметром палочки, а

само шифрование заключалось в перестановке символов исходного текста в соответствии с длиной окружности палочки. Например, используя палочку, по длине окружности которой помещается 4 символа, а длина палочки позволяет записать 6 символов, исходный текст: «это шифр древней спарты» превратится в шифрограмму: «эфвптрнаодершрйтиесы».

Схематически это можно изобразить так:

_________________________________________

| | | | | | |

| | Э | Т | О | Ш | И | |__| Ф | Р | Д | Р | Е |__

| В | Н | Е | Й | С | | | П | А | Р | Т | Ы | |

| | | | | | |

_________________________________________

Таким образом, после разматывания ленты, шифротекст будет следующим

«ЭФВПТРНАОДЕРШРЙТИЕСЫ». Как видно из примера получается таблица, у которой ксть два параметра: n -- количество столбцов, m --количество строчек. Поскольку при регелярном обмене данными, сообщения часто имеют разную длину, то оба этих параметра за неизменяющийся ключ взять неудобно. Поэтому обычно в качестве известного каждой стороне ключа выбирается один из них(часто это m), а воторой вычисляется на основе известного и длины сообщения:

n = [(k-1)/m]+1, где [x] - целая часть

Алгоритм шифрования

Теперь в данных обозначениях алгоритм шифрования выглядит так:

1. Первые n символов выписываются в первую строку слева направо(в примере выше:

ЭТОШИ).

2.Следующие n символов выписываем во вторую строчку пока ее не заполним и т.д.

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

символами по договоренности(например для сообщения "НАС АТАКУЮТ" мы получаем таблицу(см. ниже), где n = 4,m = 3

и звездочка стоит на месте недостающего символа).

4.Если выписаны не все символы, а таблица заполнена, значит, при выборе размеров допущена ошибка.

5.Теперь разворачиваем текст по столбцам(НАУАТЮСАТ_К* -- в примере ниже).

_________________________________________

| | | | | |

|__| Н | А | С |__ |__

|	А	|	Т	|	А	|	К	|	|
|	У	|	Ю	|	Т	|	*	|	|

_________________________________________

Дешифровка

Для расшифровки адресат использовал палочку такого же диаметра, на которую он наматывал пергамент, чтобы прочитать сообщение. Преимущество шифра скитала состоит в простоте и отсутствии ошибок — очень важное качество на поле боя. Однако такой шифр может быть легко взломан. Например, метод взлома скиталы был предложен Эдгаром Алланом По в своей работе "A Few Words on Secret Writing". Метод состоит в том, что не зная точного

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

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

Алгоритм дешифровки

Скажем у нас есть зашифрованный текст:

РНОАЫЙКЕСЕ_КТВА

Применялся шифр скитала с количеством строк 3, столбцов 5(т.е m = 3,n = 5). Мы знаем, что при шифровании считывание велось по столбцам, а в каждой столбце было по 3 символа.

1.Разобьем наш зашифрованный текст по m букв, учитывая пробелы(РНО АЫЙ КЕС Е_К

ТВА).

2.Сначала восстановим первый столбец, для этого первую группу букв запишем в первый столбец сверху вниз.

_________________________________________

| | Р | * | * | * | * | |__| Н | * | * | * | * |__

| О | * | * | * | * | |

_________________________________________

3.По следующим m символам восстановим второй столбец.

_________________________________________

| | Р | А | * | * | * | |__| Н | Ы | * | * | * |__

| О | Й | * | * | * | |

_________________________________________

4. После восстановления всех столбцов, можно будет прочитать текст -- РАКЕТНЫЕ ВОЙСКА.

_________________________________________

| | Р | А | К | Е | Т | |__| Н | Ы | Е | _ | В |__

| О | Й | С | К | А | |

_________________________________________

2.2 Доска Полибия

Тюремная азбука (или шифр Полибия, квадрат Полибия) — способ кодирования букв алфавита, с целью его приведения к виду, удобному для передачи по каналу связи (через стенку).

Одна из древнейших систем кодирования, предложенная Полибием (греческий историк,

полководец, государственный деятель, III век до н. э.). Данный вид кодирования изначально применялся для греческого алфавита, но затем был распространен на другие языки.

Для шифрования, прежде всего, необходимо составить таблицу, куда нужно вписать все буквы используемого алфавита. Нередко в таблице использовался именно алфавитный порядок расположения букв. В русском языке количество букв, как правило, сокращается до 28 (не использовались буквы: Ё, Й, Ъ, Ь, Э). Буквы вписываются в сетку 5Х6.

–	1	2	3	4	5
1	А	Б	В	Г	Д
2	Е	Ж	З	И	К
3	Л	М	Н	О	П
4	Р	С	Т	У	Ф
5	Х	Ц	Ч	Ш	Щ
6	Ы	Ю	Я	–	–

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

Первоначально редким стуком в стену камеры указывалась строка, а затем через краткую паузу частым стуком, отсчитывалась буква.

Например, для того, чтобы отстучать слово «кто», нужно дважды стукнуть редко, а затем пять раз ударить часто (буква К), затем четыре раза стукнуть редко и три часто (буква Т) и,

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

3. Криптоалгоритмы

3.1 Симметричные алгоритмы шифрования

Криптография существует со времён Древнего Мира. Тогда использовалась банальная перестановка букв или их замена другими буквами или цифрами. Юлий Цезарь применял подстановку, где буквы сдвигались циклически на три позиции вправо.

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

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

― определённой последовательности букв или цифр, определяющей способ шифрования/

дешифровки

Шифр Цезаря

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

Например, зашифруем сообщение «ЮРИСТ» классическим шифром Цезаря со сдвигом на 2,

используя русский алфавит из 33 букв, табл. 1.1.

Таблица 4.1.1 Числовые эквиваленты русских букв

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

18

19

20

21

22

23

24

25

26

27

28

29

30

31

32

33

АБВГДЕЁЖЗИ Й К Л М Н О П Р С Т У Ф Х Ц Ч ШЩЪ Ы Ь Э ЮЯ

На (рис. 4.1.1) показано, как получается шифрограмма «АТКУФ».

Рис. 4.1.1 Кодирование шифром Цезаря

Дешифрируем криптограмму «МВЦУК», зашифрованную тем же шифром, и получим исходное сообщение «КАФСИ» (рис. 1.2).

Рис. 4.1.2 Дешифровка шифра Цезаря

3.2 Асимметричные алгоритмы шифрования

Развитие основных типов криптографических протоколов (ключевой обмен, электронно-

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

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

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