 |
|
Шифры простой замены
ФЕДЕРАЛЬНОЕ ГОСУДАРСТВЕННОЕ БЮДЖЕТНОЕ
ОБРАЗОВАТЕЛЬНОЕ УЧРЕЖДЕНИЕ
ВЫСШЕГО ПРОФЕССИОНАЛЬНОГО ОБРАЗОВАНИЯ
«ДОНСКОЙ ГОСУДАРСТВЕННЫЙ ТЕХНИЧЕСКИЙ УНИВЕРСИТЕТ»
(ДГТУ)
Факультет: Информатика и вычислительная техника
Кафедра: Программное обеспечение вычислительной техники и автоматизированных систем
МЕТОДИЧЕСКИЕ УКАЗАНИЯ
По лабораторной работе «Простые шифры»
Ростов-на-Дону, 2013 г.
Составитель: к.т.н. Алиев А.Т.
Методические указания по лабораторной работе «Простые шифры» Методические указания – Ростов н/Д: Издательский центр ДГТУ, 2010. – 16 с.
В данных методических указаниях приводятся сведения о принципах и алгоритмах работы просты шифров. Дается краткое введение в историю криптографии, приводятся примеры простых шифров замены, перестановки и многоалфавитных шифров. Методические указания предназначены для студентов специальности 230105 «Программное обеспечение вычислительной техники и автоматизированных систем».
Ответственный редактор: д.т.н., профессор Р.А. Нейдорф
Введение
История человечества неразрывно связана с криптографией. С самого появления письменности люди уже начали использовать криптографию при записи рецептов производства и ведении учетных записей. Само слово криптография не означает непосредственно шифрование как таковое, слово криптография произошло от древне греческих слов κρυπτός – «тайный» и γράφω – «писать». Таким образом, криптография это наука о методах тайного письма или тайнописи. В текстах Индии, Египта, Месопотамии, Китая встречаются зашифрованные фрагменты, и даже описания самих методов шифрования. Наиболее древние свидетельства относят к третьему тысячелетию до н.э., по сути, ко времени появления самой письменности. В древних индийских текстах использовалось множество различных способов записи информации, часть из которых можно уверенно рассматривать как тайнопись. Например, известен способ письма, при котором гласные буквы заменялись согласными и наоборот. Из наиболее известных древних текстов, в которых использовались элементы криптографии, можно назвать Библию. Отдельные фрагменты в ней были зашифрованы шифром Атбаш.
В более позднее время различные методы шифрования сообщений стали применяться уже повсеместно. Средние века и эпоха Возрождения считаются периодом расцвета криптографии и криптоанализа. В это время шифры становятся популярны не только у военных, политиков и дипломатов, но и среди обычных граждан, появляется множество различных шифров и их описаний. Первая европейская книга, в которой описываются различные шифры, появляется в XIII веке - «Послание монаха Роджера Бэкона о тайных действиях искусства и природы и ничтожестве магии». Несколько позже в XV веке публикуется работа Габриэля де Левинда «Трактат о шифрах».
Если рассматривать простые способы тайнописи (простые шифры), то их можно разделить на два основных типа: шифры замены (подстановки) и шифры перестановки. В первом случае символы исходного алфавита заменяются символами другого алфавита или просто непонятными символами, во втором символы исходного текста меняются местами – переставляются. Известным примером шифров замены является шифр «Пляшущие Человечки» из одноименного рассказа Артура Конан Дойла о легендарном сыщике Шерлоке Холмсе. В этом шифре символы текста заменялись фигурками пляшущих человечков.
Параллельно с развитием криптографии во все времена развивались и совершенствовались методы дешифрования – криптоанализа. Хотя термин «криптоанализ» и был введён лишь в 1920 году американским криптографом Уильямом Ф. Фридманом, как таковой криптоанализ существовал уже давно. Так первым письменным упоминанием можно считать «Манускрипт о дешифровке криптографических сообщений», написанный арабским учёным Ал-Кинди в IX веке. В работе приводится первое описание частотного криптоанализа зашифрованных сообщений. В XV веке данный метод анализа стали использовать и в Европе. Появление первых эффективных методов криптоанализа подтолкнуло развитее криптографии и привело к усложнению алгоритмов шифрования. Так на место моноалфавитных шифров замены, использовавшим для замены символов сообщения один алфавит, пришли более сложные – полиалфавитные шифры, в которых уже использовалось несколько различных алфавитов. Использование большего количества алфавитов позволило повысить стойкость шифров к частотному криптоанализу, но в тоже время значительно усложнило сами шифры.
С начала XX века на место простых шифров пришли специальные механические шифровальные устройства. С конца 70-х годов в основу криптографии были положены математические методы и для шифрования сообщений стали применять электронные вычислительные машины.
Шифры простой замены
Шифр простой замены, шифр однозначной замены – шифр, в котором каждому символу алфавита открытого текста ставится в соответствие один символ алфавита шифротекста. Правило шифрования/расшифрования может быть представлено в виде простой таблицы замены символов. Первая строка такой таблицы содержит алфавит открытого текста, вторая символы из алфавита шифротекста. В большинстве случаев алфавиты открытого текста и шифротекста совпадают и отличаются лишь перестановкой символов.
Шифр Цезаря. Сегодня считается одним из типичных представителей шифров простой замены. В свое время именно этот шифр использовал Гай Юлий Цезарь. Согласно дошедшим до нас описаниям для того, чтобы расшифровать сообщение необходимо вместо первой буквы читать четвертую букву алфавита, вместо второй пятую и т.д. В табличном виде правило шифрования можно представить следующим образом: выписывается алфавит в обычном виде, а под ним выписывался тот же алфавит, но смещенный на 3 буквы влево. Применительно к русскому алфавиту, таблица шифрования выглядит следующим образом:
АБВГДЕЁЖЗИЙКЛМНОПРСТУФХЦШЩЫЬЪЭЮЯ
ГДЕЁЖЗИЙКЛМНОПРСТУФХЦШЩЫЬЪЭЮЯАБВ
В процессе шифрования буква «А» меняется на «Г», буква «Б» меняется на «Д» и т. д. Например, слово «РИМ» превращается в «УЛП».
В качестве ключа шифрования k в шифре Цезаря можно считать величину сдвига алфавита в нижней строке таблицы. Так в приведенном примере величина сдвига равна трем (k = 3). Если пронумеровать символы алфавита с нуля, то для произвольного ключа k правило шифрования можно представить в следующем виде: j = (i + k) mod n, где i – номер буквы в исходном алфавите, j – номер буквы зашифрованного текста в исходном алфавите, n – число символов в алфавите. Правило расшифрования в этом случае будет выглядеть следующим образом: i = (j – k + n) mod n.
Шифр Атбаш. Название шифра состоит из четырех букв «алеф», «тае», «бет», «шин». Эти буквы являются соответственно первой, последней, второй и предпоследней буквами древнесемитского алфавита. Эта последовательность букв в названии шифра выбрана не случайно и определяет правило шифрования: для алфавита, состоящего из n символов, i-ая буква заменяется буквой с номером n – i + 1.
Аффинная перестановка. В классическом шифре Цезаря использовалась только одна операция – сложение. Добавлением операции умножения можно получить новый шифр – аффинную перестановку. Возьмет два взаимно простых числа a и b таких, что 0 £ a, b £ n – 1, где n –мощность алфавита. Тогда правило перестановки символов в исходном алфавите можно описать следующим выражением: j = (a × i + b) mod n. Правило перестановки для расшифрования сообщения: i = (j - b) a -1mod n, где a -1 – обратное к a по модулю n, т.е.: a × a -1 mod n = 1.
Шифр подстановки. В рассмотренных выше примерах шифров простой замены использовались определенные правила позволяющие запомнить правило замены и порядок следования символов в алфавите шифрования. Помимо правила шифрования шифр подстановки может быть задан просто таблице подстановки. Как было отмечено ранее, такая таблица состоит из двух строк. Первая строка таблиц содержит символы исходного алфавита, вторая – некоторую их перестановку (или перестановку символов другого алфавита). Когда правило выбора символов из алфавита замены не задано или не известно используют непосредственно только таблицу замены.
| Исходн. алфавит | АБВГДЕЁЖЗИЙКЛМНОПРСТУФХЦШЩЫЬЪЭЮЯ |
| Алфавит шифр. | КАЛЕСПВОУГНЗЦРЩФШЭЧЫМИЯТЮХЪЖБЬДЁ |
Процесс шифрования состоит в том, чтобы найти букву исходного слова в верхней строке таблицы и выписать соответствующую ей букву из нижней строки. Так, используя приведенную выше таблицу подстановки слов «ПОНЕДЕЛЬНИК» можно зашифровать как «ШФЩПСПЦЖЩГЗ».
Квадрат Полибия. Греческий историк, известный государственный деятель и военачальник Полибий предложил использовать специальную сигнальную систему для передачи сообщений с помощью факелов или даже просто «на пальцах». Для кодирования текста использовалась простая табличка представлявшая собой квадрат из пяти строк и пяти столбцов. В ячейках квадрата были записаны символы используемого алфавита.
| 5 | |||||
| A | B | C | D | E | |
| F | G | H | I, J | K | |
| L | M | N | O | P | |
| Q | R | S | T | U | |
| 5 | V | W | X | Y | Z |
В процессе кодирования каждому символу сообщения ставилась в соответствие пара чисел: номер строки и номер столбца. В результате шифрования сообщение «WAR» превращается в строку чисел: 52 11 42. Имея таблицу, расшифровать данное сообщение не составит труда.
Несмотря на то, что данный метод кодирования сообщений изначально был предложен для использования в сигнальных системах, более широкое применение квадрат Полибия нашел именно в криптографии. В данную систему шифрования можно добавить и ключ шифрования – особый порядок следования символов в таблице.
Тюремный шифр. Одна из модификаций шифра на основе квадрата Полибия получила название – «тюремный шифр». Способ кодирования сообщений предложенный Полибием оказался очень удобным для передачи их стуком через стены. Так, для того, чтобы передать букву «H» нужно было стукнуть по стене два раза, и с небольшой паузой еще три раза. Но такой способ кодирования был известен и охранникам. Для того чтобы усложнить шифр использовали произвольный порядок расположения букв. Но запомнить его было сложно, а передать таблицу на бумажке тоже было нельзя. Поэтому в качестве ключа использовали не целую таблицу, а некоторое простое и легко запоминаемое слово. Если в слове встречались повторы букв, они удалялись. Например, возьмем слов «PRISON». Выбранное слово записывается в начальные клетки квадрата. Затем, в оставшиеся клетки в обычном порядке записываются все остальные буквы.
| 5 | |||||
| P | R | I, J | S | O | |
| N | A | B | C | D | |
| E | F | G | H | K | |
| L | M | Q | T | U | |
| 5 | V | W | X | Y | Z |
Вместо короткого слова может быть использована целая фраза. Использование фразы позволяет лучше перемешать буквы в таблице, а запомнить её также легко, как и одно слово.
Шифры перестановки
Шифры, которые меняют только порядок следования символов сообщения, но не меняет сами символы, называют шифрами перестановки. Эти шифры не использую дополнительный алфавит шифрования и замену символов. Большинство шифров перестановки построено на основе использования таблиц перестановки. Открытое сообщение разбивается на блоки, длина которых равна количеству ячеек в таблице. Если последний фрагмент сообщения оказывается короче необходимой длины, он дополняется до нужной длины случайными символами. Каждый фрагмент (блок) сообщения записывается в такую таблицу перестановки в прямом порядке, а затем считывается из нее в соответствии с заданным правилом.
Одиночная перестановка.Простая перестановка осуществляется по квадратной или прямоугольной таблице с фиксированными размерами. Ключом шифра является пара чисел: количество строк и столбцов. Например, используя таблицу размером 3×3 можно закодировать сообщение «ПОСЛАНИЕ СКРЫТО В ТЕКСТЕ ЗАПИСКИ» следующим образом:
| П | О | С | С | К | Р | Т | Е | К | П | И | С | |||
| Л | А | Н | Ы | Т | О | С | Т | Е | К | И | Н | |||
| И | Е | _ | _ | В | _ | _ | З | А | Г | Ш | Ц |
Если выписать сообщение по столбцам, то получим зашифрованное сообщение: «ПЛИОАЕСН_СЫ_КТВРО_ТС_ЕТЗКЕАПКГИИШСНЦ».
В случае квадратной таблицы порядок начальной записи фрагмента сообщения в таблицу (по строкам или по столбцам) не имеет значения. Если же используется прямоугольная таблица, то порядок записи сообщения в таблицу необходимо обговорить заранее.
Шифр вертикальной перестановки. В отличие от предыдущего шифра в данном шифре добавляется еще один параметр, который можно менять от сообщения к сообщению – ключевое слов. В качестве ключевого слова выбирается произвольное слово небольшой длины. Например, слов «ВОСХОД». Буквы слова нумеруются в соответствии с порядком их следования в алфавите. Повторяющиеся буквы нумеруются слева направо.
Ключевое слово выписывается в первой строке таблицы, под ним записываются номера упорядоченных букв. Ниже, строка за строкой записывается текст сообщения. После того, как будет записано все сообщение, столбцы таблицы переставляются в соответствии с порядковыми номерами букв сообщения.
| В | О | С | Х | О | Д | В | Д | О | О | С | Х | |
| 1 | 3 | 5 | 6 | 4 | 2 | 1 | 2 | 3 | 4 | 5 | 6 | |
| П | О | С | Л | А | Н | П | Н | О | А | С | Л | |
| И | Е | _ | С | К | Р | И | Р | Е | К | _ | С | |
| Ы | Т | О | _ | В | _ | Ы | _ | Т | В | О | _ | |
| Т | Е | К | С | Т | Е | Т | Е | Е | Т | К | С | |
| _ | З | А | П | И | С | _ | С | З | И | А | П | |
| К | И | Н | Г | О | К | К | К | И | О | Н | Г |
Зашифрованное сообщение выписывается из таблицы по столбцам сверху вниз. В нашем примере получаем зашифрованное сообщение: «ПИЫТ_КНР_ЕСКОЕТЕЗИАКВТИОС_ОКАНЛС_СПГ».
Двойная перестановка. Шифр двойной перестановки во многом аналогичен шифру вертикальной перестановки. Основное отличие заключается в том, что вместо прямоугольника, высота которого не фиксирована (для шифра вертикальной перестановки), выбирается квадрат с длиной стороны равной длине ключевого слова. После того, как сообщение (или его фрагмент) будет записано в квадрат, выполняется перестановка столбцов точно также как в шифре вертикальной перестановки. Затем, аналогичным образом переставляются строки. После двух последовательных перестановок зашифрованное сообщение может быть выписано из квадрата либо по столбцам, либо по строкам.
Магический квадрат. Рассмотрим квадратную таблицу с длиной стороны L. В ячейки таблицы можно записать все целые числа от 1 до L2. Если в результате получается таблица, у которой суммы чисел по всем строка и всем столбцам равны, то такая таблица называется Магическим квадратом. В качестве примера магического квадрата можно привести квадрат с гравюры Альбрехта Дюрера «Меланхолия». Что интересно, так это то, что в двух нижних ячейках квадрата записан год создания гравюры - 1514.
В средние века использование магических квадратов для шифрования сообщений было очень популярно. Процесс шифрования заключался в том, что шифруемое сообщение записывалось в ячейки квадрата согласно числам в этих ячейках. Зашифрованное сообщение считывалось по строкам. Считалось, что магический квадрат передает часть своей неведомой силы шифру и от этого взломать его, как тогда казалось, будет гораздо сложнее.
Магический квадрат является ярким примером шифров маршрутной перестановки, когда сообщение записывается или считывается из таблицы по определенному маршруту. В случае магического квадрата этот маршрут задается числами, записанными в его ячейках.