Основы криптологии

БОЛЬШАЯ ЛЕНИНГРАДСКАЯ БИБЛИОТЕКА - РЕФЕРАТЫ - Основы криптологии

Основы криптологии

Содержание:

Содержание

Введение

1 Метод одиночной перестановки

1.1 Шифрование методом одиночной перестановки

1.2 Дешифрование методом одиночной перестановки

2 Метод двойной перестановки

2.1 Шифрование методом двойной перестановки

2.2 Дешифрование методом двойной перестановки

3 Решетка Кардано

3.1 Шифрование методом решетки Кардано

3.2 Дешифрование методом решетки Кардано

4 Метод Гронсфельда

4.1 Шифрование методом Гронсфельда

4.2 Дешифрование методом Гронсфельда

Заключение

Список литературы

ВВЕДЕНИЕ:

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

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

Криптография лишь предоставляет алгоритмы и некоторые приемы для аутентификации клиента и шифрования информации. А как вообще появилось шифрование?

НЕМНОГО ИСТОРИИ:

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

Точных дат и бесспорных сведений о секретном письме в древности сохранилось очень мало. Однако вместе с шифрами были, само собой разумеется, и попытки скрытия текста. В древней Греции для этого однажды обрили раба, написали на его голове, и, когда волосы отросли, отправили с поручением к адресату. Приведем пример укрытия открытого текста, указанный Александром Сергеевичем Пушкиным в поэме "Полтава":

«Червонцы нужны для гонца,

Булат - потеха молодца,

Ретивый конь - потеха тоже,

Но шапка для него дороже,

За шапку он оставить рад

Коня, червонцы и булат,

Но шапку выдаст только с бою

И то лишь с буйной головою.

Зачем он шапкой дорожит?

Затем, что в ней донос зашит,

Донос на гетмана-злодея

Царю Петру от Кочубея».

Хотя здесь описаны не события седой древности, а начала XVIII века, однако это подтверждает живучесть таких методов защиты передаваемой секретной информации. Отзвук этой истории можно встретить в "Гиперболоиде инженера Гарина" Алексея Толстого, где текст нанесли на спину мальчика. Если же гонец был надежен и даже под пытками не выдал бы послания, то его изложение могло быть изустным.

Ряд систем шифрования дошел до нас из глубокой древности. Скорее всего они появились одновременно с письменностью в 4 тысячелетии до нашей эры. Методы секретной переписки были изобретены независимо во многих древних обществах, таких как Египет, Шумер и Китай, но детальное состояние криптологии в них неизвестно. Криптограммы выискиваются даже в древние времена, хотя из-за применяемого в древнем мире идеографического письма в виде стилизованных картинок были примитивны. Шумеры, по-видимому, пользовались тайнописью. Археологами найдены глиняные клинописные таблички, где первая запись замазывалась слоем глины, на котором делалась вторая запись. Происхождение таких странных таблиц могло быть вызвано и тайнописью, и утилизацией. Оттого что число знаков идеографического письма было более тысячи, то запоминание их представляло собой трудную задачу - тут не до шифрования. Тем не менее, коды, появившиеся вместе со словарями, были хорошо известны в Вавилоне и Ассирии, а древние египтяне применяли по меньшей мере 3 системы шифрования. С развитием фонетического письма письменность резко упростилась. В древнем семитском алфавите во втором тысячелетии до нашей эры было всего около 30 знаков. Ими обозначались согласные звуки, а также некоторые гласные и слоги.

Даже в Библии можно найти примеры шифровок, хотя мало кто это замечает. В книге пророка Иеремии (25,26) читаем: "...а царь Сессаха выпьет после них". Такого царя или царства не было - неужели ошибка писца? Нет, просто порой священные иудейские тексты шифровались простой заменой. Вместо первой буквы алфавита писалась последняя, вместо второй - предпоследняя и так далее. Этот древний метод шифрования назывался атбаш. Читая по нему слово СЕССАХ, на языке оригинала получаем слово ВАВИЛОН, и смысл библейского текста может быть принят даже не верящим слепо в истинность писания.

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

Зачем обращаться к столь древней истории? Монтень в своих философских опытах утверждает: "Невежество бывает двоякого рода: одно, безграмотное, предшествует науке; другое, чванное, следует за нею". Поэтому не нужно смеяться над простотой и наивностью первых шифров - опыты пионеров всегда неуклюжи. Однако вовсе не до смеха, когда, стараясь защитить свой труд, современные программисты воспроизводят пороки Гая Юлия.

Принципиально иной шифр, более древний, связан с перестановкой букв сообщения по определенному, известному отправителю и получателю правилу. Древние рассказывали: какой-то хитрец из спартанцев обнаружил, что если полоску пергамента намотать спиралью на палочку и написать на нем вдоль палочки текст сообщения, то, после снятия полоски буквы на ней расположатся хаотично. Это то же самое, будто буквы писать не подряд, а через условленное число по кольцу до тех пор, пока весь текст не будет исчерпан. Сообщение ВЫСТУПАЙТЕ при окружности палочки в 3 буквы даст шифровку ВУТЫПЕСАТЙ. Текст ее не понятен, не так ли?

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

1 Метод одиночной перестановки

1.1 Шифрование методом одиночной перестановки

Более практический метод шифрования, называемый одиночной перестановкой по ключу очень похож на ключ простой перестановки. Он отличается лишь тем, что колонки таблицы переставляются по ключевому слову, фразе или набору чисел длиной в строку таблицы. Использовав в виде ключа слово КУРИЦА, получим таблицу №1

Таблица №1 до перестановки

Таблица №2 после перестановки

В верхней строке ее записан ключ, а номера под ключом определены по естественному порядку соответствующих букв ключа в алфавите. Если в ключе встретились бы одинаковые буквы, они бы нумеровались слева направо. Получается шифровка: МДТМАЕ ВЦЕНЗС ОАКАМТ ЛТСТЕЬ ОЬТРРС ВШРИОИ.

1.2 Дешифрование методом одиночной перестановки

Преподавателем выдан следующий текст: ЕДВЕДЬ ВЫГЛЯД УЖАСНО ДНЫЙРУ ССКНЙМ ИТТОЛО . Шифртекст содержит 36 символов, значит необходимо взять таблицу из шести столбцов и шести строк. Получаем таблицу №3

Таблица №3

Попытаемся прочитать шифровку по столбцам. В первом столбце легко читается слово МЕДВЕДЬ, во втором - ВЫГЛЯДИТ, в третьем - УЖАСНО.Таким образом, можно предположить, что столбцы располагаются в порядке: 621453

Таблица №4

Получаем открытый текст, читая сообщение по столбцам: УЖАСНО ВЫГЛЯДИТ ГОЛОДНЫЙ РУССКИЙ МЕДВЕДЬ.

2 Метод двойной перестановки

2.1 Шифрование методом двойной перестановки

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

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

Таблица №5

Перестановка строк:

Таблица №6

Перестановка столбцов:

Таблица №7

Получается шифровка НДОАООХЛЛМ ИНЙДЫ. Ключом к этому шифру служат номера столбцов 2413 и номера строк 4123 исходной таблицы. Число вариантов двойной перестановки тоже велико: для таблицы 3х3 их 36, для 4х4 их 576, а для 5х5 их уже 14400. Однако двойная перестановка очень слабый вид шифра, легко читаемый при любом размере таблицы шифрования

2.2 Дешифрование методом двойной перестановки

Сначала возьмем тот пример шифровки двойной перестановки, что изложен. Пусть имеется шифровка ЕН__ЕТСНЮЛКЧВЗИЕ, которая так укладывается в таблицу 4 х 4:

Таблица №8

Рассматривая маловероятные сочетания букв, легко найти истинную последовательность столбцов. Так, сочетание ГТ в 3 строке шифровки указывает на то, что после 1 столбца вряд ли следует 2 столбец. Рассчитаем статистически, какой столбец скорее всего следует за 1. Для этого воспользуемся таблицей логарифмов вероятностей биграмм русского текста, приведенной в приложении. Вероятность следования одного столбца за другим равна произведению вероятностей биграмм в строках этих столбцов. Поскольку в таблице даны логарифмы биграмм, то их достаточно суммировать, а потом выбрать сочетание столбцов с максимальной вероятностью. Для вероятностей следования за первым столбцом 2, 3 и 4 имеем выражения:

1 р (1-2) =р(ЕН) р(ЕТ ) р(ЮЛ) р(ВЗ)=9+9+3+3=24

р (1-3) =р(Е_) р(ЕС) р(ЮК) р(ВИ)=9+8+1+7=25

р (1-4 )=р(Е_) р(ЕН) р(ЮЧ) р(ВЕ)=9+9+6+8=32

2 р (2-1) =р(НЕ) р(ТЕ ) р(ЛЮ) р(ЗВ)=8+8+7+6=29

р (2-3) =р(Н_) р(ТС) р(ЛК) р(ЗИ)=7+8+4+6=25

р (2-4 )=р(Н_) р(ТН) р(ЛЧ) р(ЗЕ)=7+6+3+4=20

3 р (3-1) =р(_Е) р(СЕ ) р(КЮ) р(ИВ)=7+7+0+7=21

р (3-2) =р(_Н) р(СТ) р(КЛ) р(ИЗ)=9+9+7+7=32

р (3-4 )=р(__) р(СН) р(КЧ) р(ИЕ)=0+6+0+8=14

4 р (4-1) =р(_Е) р(НЕ ) р(ЧЮ) р(ЕВ)=7+8+0+6=21

р (4-2) =р(_Н) р(НТ) р(ЧЛ) р(ЕЗ)=9+7+1+6=23

р (4-3 )=р(__) р(НС) р(ЧК) р(ЕИ)=0+5+6+4=15

В нашем случае наиболее вероятно, что после столбца 3 следует столбец 2. Для такой небольшой таблицы шифрования, которую имеем, можно перебрать все варианты перестановок - их всего лишь 24. В случае большого числа столбцов целесообразно оценить вероятности пар сочетаний разных столбцов и решить оптимизационную задачу, которая укажет перестановку столбцов, дающую фрагменты естественного текста с большей вероятностью. В нашем случае наилучший результат достигается при расстановке столбцов (3214), что примерно вдвое по вероятностной оценке достовернее ближайшей к ней по вероятности расстановки (2413). После того, как столбцы шифровки расставлены, не составит труда правильно расставить и ее строки по смыслу фрагментов текста:

Таблица №9

Текст в ней уже читается и, расставив строки в порядке (2413), получим расшифровку КЛЮЧ НЕ ИЗВЕСТЕН

3 Решетка Кардано

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

В 1550 году, Джироламо Кардано (1501--1576), предложил простую решетку для шифрования сообщений. Он планировал маскировать сообщения под обычное послание, так что в целом они не были полностью похожи на шифрованные. Такое замаскированное сообщение считается примером стеганографии, которая является подразделом криптографии. Но имя Кардано относилось к решеткам, которые могли и не быть зобретением Кардано, тем не менее, шифры, реализованные с использованием картонных решеток, принято называть решётками Кардано.

Известно, что Кардинал Ришелье (1585--1642) был приверженцем решетки Кардано и использовал её в личной и деловой переписке. Образованные жители Европы XVII века были знакомы с игрой слов в литературе, в том числе с акростихом, анаграммой и шифрами. К концу XVII века первые решетки Кардано уже почти не использовались, но иногда они всё же появлялись в виде зашифрованных посланий и в качестве литературных диковинок. Например, Джордж Гордон Байрон пользовался решеткой Кардано, но скорее для демонстрации литературных навыков, чем для серьёзного шифрования. Решетка содержит отверстия для отдельных символов, а сообщение заполняется набором букв или цифр и представляет собой, очевидно, криптограмму, в то время как Кардано намеревался сделать стеганограмму. Эти решетки с прорезями для букв можно назвать в честь Кардано, но их также называют просто картонными шифровальными решетками.

Одна из разновидностей решётки Кардано -- вращающаяся решетка или сетка, в основе которой лежит шахматная доска, которая использовалась в конце XVI века. Вращающаяся решетка снова появилась в более сложной форме в конце XIX века, но, к этому времени, какая-либо связь с Кардано осталась только в названии.

3.1 Шифрование методом решетки Кардано

Описание решетки Кардано.

Решетка Кардано сделана из листа картона или пергамента, или же из тонкого металла. Чтобы обозначить линии письма, бумагу разлиновывают, и между этими линиями вырезают прямоугольные области через интервалы произвольной длины.

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

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

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

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

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

Таблица № 10 0° Таблица № 11 90°

Таблица № 12 180 ° Таблица № 13 270 °

При зашифровке таким способом, мы получили шифр текст: СЗДО_ЕИКТБОМАРУ_.

Таблица № 14

3.2 Дешифрование методом решетки Кардано

Преподавателем выдан шифртекст: НШКАТРЕАЫЬДСТЦ_С

Предположим, что биграмма ЗР входит в одно из слов текста. Так как З располагается выше Р, это значит, что между ними произошел поворот решетки. С учетом того, что эти буквы принадлежат различным прорезям решетки, получаем такой вид разгаданных частей таблицы. Обозначим клетку с буквой З цифрой 1, а клетку буквы Р цифрой 2. Предположим, что при составлении решеток прорези разместили так, что в каждой колонке и каждом столбце имеется всего одна прорезь. Таким образом, имеются только 2 варианта: 1234 и 123'4', изображенных в таблице №15

Таблица № 14

Вариант 123'4' не подходит, так как не покрывается весь квадрат при поворотах решетки. Остается вариант 1234, что дает открытый текст: ЧАЕТСЯ_ТЕКСТПОЛУ. Сообщение уже ясно, хотя расшифровка начата с неправильного поворота решетки. С учетом этого замечания получается сообщение: ПОЛУЧАЕТСЯ_ТЕКСТ. Таким образом, ключ представлен в следующей таблице №16

Таблица № 16

Недостатки решетки Кардано

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

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