ПРОСТЕЙШИЕ КРИПТОГРАФИЧЕСКИЕ ШИФРЫ

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

Основные способы защиты информации:

· защита ее только силовыми методами: охрана документа (носителя информации) физическими лицами, передача его специальным курьером и т.д.

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

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

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

Определение.Криптография – обеспечивает сокрытие смысла сообщения с помощью шифрования и открытия его расшифрованием, которые выполняются по специальным алгоритмам с помощью ключей.

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

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

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

Определение.Кодированием называется замена слова, группы слов, а также целых фраз каким-либо условным словом или знаком, группой символов.

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

Набор кодовых символов обычно составляет кодовый алфавит (словарь).

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

Определение.Под шифрованием имеется в виду перевод открытого текста в закрытый шифротекст посредством применения вполне определенных правил (алгоритмов).

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

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

В криптографии используются следующие основные алгоритмы шифрования:

· алгоритм замены (подстановки) – символы шифруемого текста заменяются символами того же или другого алфавита в соответствии с заранее обусловленной схемой замены;

· алгоритм перестановки – символы шифруемого текста переставляются по определенному правилу в пределах некоторого блока этого текста;

· гаммирование – символы шифруемого текста складываются с символами некоторой случайной последовательности;

· аналитическое преобразование – преобразование шифруемого текста по некоторому аналитическому правилу (формуле).

Рассмотрим классические шифры, известные еще со времен древности.

В шифрах перестановки буквы (или другие символы) исходного сообщения нисколько не меняются, а лишь переставляются по некоему закону, делая весь текст стандартно нечитаемым. Такие шифры хороши для подстраховки закодированного текста или отдельных криптограмм многоалфавитного шифрования. Шифры перестановки не сложны для опытного дешифровщика (а тем более для ЭВМ!), хотя при кратких текстах возможно и неправильное осмысленное прочтение.

Простой столбцевой перестановочный шифр. В данном виде шифра текст пишется на горизонтально разграфленном листе бумаги фиксированной ширины, а шифротекст считывается по вертикали. Дешифрирование заключается в записи шифротекста вертикально на листе разграфленной бумаги фиксированной ширины и затем считывании открытого текста горизонтально. Открытый текст: ИНСТИТУТ СВЯЗИ И ИНФОРМАТИКИ (28 символов)

И Н С Т И Т У

Т С В Я З И

И И Н Ф О

Р М А Т И К И

Зашифрованный текст: ИТ РН ИМСС АТВИТИЯНИТЗФКУИОИ

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

Открытый текст: Дискретная математика Ключ: Шифр приведен в таблице 14

Таблица 14

Криптограмма: иеяеикнааастммкдратт

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

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

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

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

Таблица 15

Для получения шифрованного сообщения текст считывается по строкам и группируется по 5 букв: НОНСБ НЯЕЕО ЯОЕТЯ СВЕЛП НСТИЩ ЕОЫНА ТЕЕНМ

Несколько большей стойкостью к раскрытию обладает метод одиночной перестановки по ключу. Он отличается от предыдущего тем, что столбцы таблицы переставляются по ключевому слову, фразе или набору чисел длиной в строку таблицы. Используя в качестве ключа слово ЛУНАТИК, получим следующую таблицу 16.

Таблица 16

До перестановки После перестановки

В верхней строке левой таблицы записан ключ, а номера под буквами ключа определены в соответствии с естественным порядком соответствующих букв ключа в алфавите. Если в ключе встретились бы одинаковые буквы, они бы нумеровались слева направо. Получается шифровка: СНЯНН БОЯЕТ ЕООЕЕ ПНЯВЛ СЩОЫС ИЕТЕН МНТЕА. Для обеспечения дополнительной скрытности можно повторно шифровать сообщение, которое уже было зашифровано. Для этого размер второй таблицы подбирают так, чтобы длины ее строк и столбцов отличались от длин строк и столбцов первой таблицы. Лучше всего, если они будут взаимно простыми.

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

Таблица 17

Двойная перестановка столбцов и строк

В результате перестановки получена шифровка АЗЮЖЕ_СШГТООИПЕР. Ключом к шифру служат номера столбцов 2413 и номера строк 4123 исходной таблицы.

Число вариантов двойной перестановки достаточно быстро возрастает с увеличением размера таблицы: для таблицы 3 х 3 их 36, для 4 х 4 их 576, а для 5*5 их 14400.

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

Таблица 18

Таблица 19

Число магических квадратов очень резко возрастает с увеличением размера его сторон: для таблицы 3*3 таких квадратов -1; для таблицы 4*4 - 880; а для таблицы 5*5-250000.

В шифрах замены каждая из букв в открытом тексте подменивается какой-то другой буквой или символом, причем порядок самих букв при этом не меняется. Замена может быть как однозначной (в шифрах простой замены, где каждой букве соответствует лишь один символ), так и многозначной (в шифрах многоалфавитной замены, где каждой букве соответствуют несколько символов); как однобуквенной (поочередная замена буквы на букву), так и многобуквенной (системы с зашифровыванием одновременно двух и более букв). Шифры простой замены легко дешифруются при длительности текста не менее двух-трех алфавитов путем анализа частот встречаемости букв и через знание типичных сдвоенных знаков, сочетаний и окончаний.

Шифры простой замены. При шифровании заменой (подстановкой) символы шифруемого текста заменяются символами того же или другого алфавита с заранее установленным правилом замены. В шифре простой замены каждый символ исходного текста заменяется символами того же алфавита одинаково на всем протяжении текста. Такие шифры называют шифрами одноалфавитной подстановки.

Шифр Цезаря является частным случаем шифра простой замены (одноалфавитной подстановки). Свое название этот шифр получил по имени римского императора Гая Юлия Цезаря, который использовал этот шифр при переписке с Цицероном (около 50 г. до н.э.).

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

В таблице 20 приведены одноалфавитные подстановки (К = 3, m = 26)

Таблица 20

Например, послание Цезаря VENI VIDI VICI в переводе на русский означает "Пришел, Увидел, Победил" выглядело бы в зашифрованном виде так: YHQL YLGL YLFL.

SBKF SFAF SFZF (при смещении на 5 символов).

Применительно к современному русскому языку, например, слово "РИМ" превращалось в слово "УЛП". Ключом в шифре Цезаря является величина сдвига 3-й нижней строки алфавита.

Достоинством системы шифрования Цезаря является простота шифрования и расшифрования.

К недостаткам системы Цезаря следует отнести следующие:

· подстановки, выполняемые в соответствии с системой Цезаря, не маскируют частот появления различных букв исходного открытого текста;

· сохраняется алфавитный порядок в последовательности заменяющих букв; при изменении значения k изменяются только начальные позиции такой последовательности;

· число возможных ключей k мало;

· шифр Цезаря легко вскрывается на основе анализа частот появления букв в шифртексте.

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

Шифр Полибия. Греческим писателем Полибием за 100 лет до н.э. был изобретен так называемый полибианский квадрат размером 5*5, заполненный алфавитом в случайном порядке. Греческий алфавит имеет 24 буквы, а 25-м символом является пробел. Для шифрования на квадрате находили букву текста и записывали в шифротекст букву, расположенную ниже ее в том же столбце. Если буква оказывалась в нижней строке таблицы, то брали верхнюю букву из того же столбца.

Система Цезаря не является старейшей. Возможно, что наиболее древней из известных является система греческого историка Полибия, умершего за 30 лет до рождения Цезаря. Его суть состоит в следующем: рассмотрим прямоугольник, часто называемый доской Полибия.

Таблица 21

Каждая буква может быть представлена парой букв, указывающих строку и столбец, в которых расположена данная буква. Так представления букв В, Г, П, У будут АВ, АГ, ВГ, ГБ соответственно, а сообщение ДИСКРЕТНАЯ МАТЕМАТИКА зашифруется как

АДБВВЕБДВДАЕГАВБФФЕБВАААГААЕВАААГАБВБДААЕЕ

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

Для примера шифра перестановки выберем целое положительное число, скажем 5; расположим числа от 1 до 5 в двустрочной записи. Зашифруем фразу "СВЯЩЕННАЯ РИМСКАЯ ИМПЕРИЯ". В этой фразе 23 буквы. Дополним ее двумя произвольными буквами (например,Ь.Э) до ближайшего числа, кратного 5, то есть 25. Выпишем эту дополненную фразу без пропусков, одновременно разбив ее на пятизначные группы: СВЯЩЕ ННАЯР ИМСКА ЯИМПЕ РИЯЬЭ Буквы каждой группы переставим в соответствии с указанной двухстрочной записью по следующему правилу: первая буква встает на третье место, вторая – на второе, третья на пятое, четвертая на первое и пятая на четвертое. Полученный текст выписывается без пропусков: ВСЕЯЯННРАКМИАСПИЯЕМЬИРЭЯ При расшифровании текст 1 разбивается на группы по 5 букв и буквы переставляются в обратном порядке: 1 на 4 место, 2 на 2,3 на 1, 4 на 5 и 5 на3. Ключом шифра является выбранное число 5 и порядок расположения чисел в нижнем ряду двухстрочной записи.

"Узелковое письмо" получило распространение у индейцев Центральной Америки. Свои сообщения они передавали в виде нитки, на которой завязывались разноцветные узелки, определявшие содержание сообщения. Было предложено прокалывать малозаметные дырки в книге или в другом документе над буквами (или под ними) секретного сообщения. В первой мировой войне германские шпионы использовали аналогичный шифр, заменив дырки на точки, наносимые симпатическими чернилами на буквы газетного текста.

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

Шифр Виженера. Одной из старейших и наиболее известных многоалфавитных криптосистем является система Виженера, названная в честь французского криптографа Блейза Виженера (Vigenere). Этот метод был впервые опубликован в 1586 году. В данном шифре ключ задается набором из d букв. Такие наборы подписываются с повторением под сообщением, а, затем, полученную последовательность складывают с открытым текстом по модулю n (мощность алфавита). Т.е. получается следующая ф-ла: Vig_d(m_i)=(m_i+k_{i mod d})(mod n)

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

А Б В Г Д Е Ж З И Й К Л М Н О П Р С Т У Ф Х Ц Ч Ш Щ Ъ Ы Ь Э Ю Я
Б В Г Д Е Ж З И Й К Л М Н О П Р С Т У Ф Х Ц Ч Ш Щ Ъ Ы Ь Э Ю Я А
В Г Д Е Ж З И Й К Л М Н О П Р С Т У Ф Х Ц Ч Ш Щ Ъ Ы Ь Э Ю Я А Б
Г Д Е Ж З И Й К Л М Н О П Р С Т У Ф Х Ц Ч Ш Щ Ъ Ы Ь Э Ю Я А Б В
Д Е Ж З И Й К Л М Н О П Р С Т У Ф Х Ц Ч Ш Щ Ъ Ы Ь Э Ю Я А Б В Г
Е Ж З И Й К Л М Н О П Р С Т У Ф Х Ц Ч Ш Щ Ъ Ы Ь Э Ю Я А Б В Г Д
Ж З И Й К Л М Н О П Р С Т У Ф Х Ц Ч Ш Щ Ъ Ы Ь Э Ю Я А Б В Г Д Е
З И Й К Л М Н О П Р С Т У Ф Х Ц Ч Ш Щ Ъ Ы Ь Э Ю Я А Б В Г Д Е Ж
И Й К Л М Н О П Р С Т У Ф Х Ц Ч Ш Щ Ъ Ы Ь Э Ю Я А Б В Г Д Е Ж З
Й К Л М Н О П Р С Т У Ф Х Ц Ч Ш Щ Ъ Ы Ь Э Ю Я А Б В Г Д Е Ж З И
К Л М Н О П Р С Т У Ф Х Ц Ч Ш Щ Ъ Ы Ь Э Ю Я А Б В Г Д Е Ж З И Й
Л М Н О П Р С Т У Ф Х Ц Ч Ш Щ Ъ Ы Ь Э Ю Я А Б В Г Д Е Ж З И Й К
М Н О П Р С Т У Ф Х Ц Ч Ш Щ Ъ Ы Ь Э Ю Я А Б В Г Д Е Ж З И Й К Л
Н О П Р С Т У Ф Х Ц Ч Ш Щ Ъ Ы Ь Э Ю Я А Б В Г Д Е Ж З И Й К Л М
О П Р С Т У Ф Х Ц Ч Ш Щ Ъ Ы Ь Э Ю Я А Б В Г Д Е Ж З И Й К Л М Н
П Р С Т У Ф Х Ц Ч Ш Щ Ъ Ы Ь Э Ю Я А Б В Г Д Е Ж З И Й К Л М Н О
Р С Т У Ф Х Ц Ч Ш Щ Ъ Ы Ь Э Ю Я А Б В Г Д Е Ж З И Й К Л М Н О П
С Т У Ф Х Ц Ч Ш Щ Ъ Ы Ь Э Ю Я А Б В Г Д Е Ж З И Й К Л М Н О П Р
Т У Ф Х Ц Ч Ш Щ Ъ Ы Ь Э Ю Я А Б В Г Д Е Ж З И Й К Л М Н О П Р С
У Ф Х Ц Ч Ш Щ Ъ Ы Ь Э Ю Я А Б В Г Д Е Ж З И Й К Л М Н О П Р С Т
Ф Х Ц Ч Ш Щ Ъ Ы Ь Э Ю Я А Б В Г Д Е Ж З И Й К Л М Н О П Р С Т У
Х Ц Ч Ш Щ Ъ Ы Ь Э Ю Я А Б В Г Д Е Ж З И Й К Л М Н О П Р С Т У Ф
Ц Ч Ш Щ Ъ Ы Ь Э Ю Я А Б В Г Д Е Ж З И Й К Л М Н О П Р С Т У Ф Х
Ч Ш Щ Ъ Ы Ь Э Ю Я А Б В Г Д Е Ж З И Й К Л М Н О П Р С Т У Ф Х Ц
Ш Щ Ъ Ы Ь Э Ю Я А Б В Г Д Е Ж З И Й К Л М Н О П Р С Т У Ф Х Ц Ч
Щ Ъ Ы Ь Э Ю Я А Б В Г Д Е Ж З И Й К Л М Н О П Р С Т У Ф Х Ц Ч Ш
Ъ Ы Ь Э Ю Я А Б В Г Д Е Ж З И Й К Л М Н О П Р С Т У Ф Х Ц Ч Ш Щ
Ы Ь Э Ю Я А Б В Г Д Е Ж З И Й К Л М Н О П Р С Т У Ф Х Ц Ч Ш Щ Ъ
Ь Э Ю Я А Б В Г Д Е Ж З И Й К Л М Н О П Р С Т У Ф Х Ц Ч Ш Щ Ъ Ы
Э Ю Я А Б В Г Д Е Ж З И Й К Л М Н О П Р С Т У Ф Х Ц Ч Ш Щ Ъ Ы Ь
Ю Я А Б В Г Д Е Ж З И Й К Л М Н О П Р С Т У Ф Х Ц Ч Ш Щ Ъ Ы Ь Э
Я А Б В Г Д Е Ж З И Й К Л М Н О П Р С Т У Ф Х Ц Ч Ш Щ Ъ Ы Ь Э Ю
Таблица Виженера для русского алфавита

В частном случае, при d=1, получаем шифр Цезаря.

Шифр Виженера реализует кодирование фразы путем «индивидуального сдвига» букв, причем величина сдвигов определяется номерами (положением) букв в ключевом слове (фразе). Возьмем, например, ключевое слово «leonid» (латиница) и кодируемую фразу «i remember that september». Буквы ключевого слова имеют следующие номера в латинском алфавите: 12,5,15,14,9,4. Шифрование по Виженеру состоит в «сдвиге» первой буквы кодируемой фразы на 12 позиций, т.е. в замене буквы «i» (9-я позиция) на букву «u», находящуюся в 9+12=21-й позиции, в замене пробела « » (второй буквы кодируемой фразы, 0-я позиция) на букву «e», находящуюся в 0+5=5-й позиции и т.д. При «исчерпании» букв ключевого слова, последнее используется снова и снова до тех пор, пока не будут закодированы все буквы кодируемой фразы. Результаты шифрования указанной выше фразы показаны ниже в таблице 22.

Таблица 22

Пояснения к таблице.

1-я строка – фраза для шифрования;

2-я строка – номера букв фразы для шифрования в латинском алфавите;

3-я строка – ключевое слово с длиной равной длине фразы;

4-я строка – номера букв ключевого слова в алфавите;

5-я строка – сумма номеров 2-й и 4-й строк в соответствующих столбцах;

6-я строка – результат «деления по модулю 27» чисел 5-й строки;

7-я строка – зашифрованная фраза.

Таким образом, «шифровка» будет иметь вид «uefsviygteixtfhnaiayt kic».

Декодирование «шифровки» проводим «аналогично» кодированию фразы.