Краткие теоретические сведения о шифрах замены

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

Для определения исходного текста по шифрованному при неизвестном ключе возможны два подхода:

1) определить ключ и затем найти исходное сообщение расшифрованием;

2) найти исходное сообщение без определения ключа.

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

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

Нельзя смешивать два понятия: шифрование и кодирование. При кодировании нет ничего секретного, есть только определенная замена букв или слов на заранее определенные символы. Методы кодирования направлены не на то, чтобы скрыть открытое сообщение, а на то, чтобы представить его в более удобном виде для передачи по техническим средствам связи, для уменьшения длины сообщения и т.д.

В принципе, кодирование можно рассматривать как шифр замены, для которого «набор» возможных ключей состоит только из одного ключа (например, буква «а» в азбуке Морзе всегда кодируется знаками (·•) (0-), и это не является секретом).

 

В классической криптографии различают 4 разновидности шифров замены:

Простая замена, или одноалфавитный шифр. Каждая буква открытого текста заменяется на один и тот же символ шифртекста.

Омофонная замена. Аналогична простой замене с единственным отличием: каждой букве открытого текста ставятся в соответствие несколько символов шифртекста. Например, буква "А" заменяется на цифру 5, 13, 25 или 57, а буква "Б" — на 7, 19, 31 или 43 и так далее.

Блочная замена. Шифрование открытого текста производится блоками. Например, блоку "АБА" может соответствовать "РТК", а блоку "АББ" — "СЛЛ".

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

Примеры простейших шифров замены.

Формально, шифр замены можно описать следующим образом. Для каждой буквы a исходного алфавита строится некоторое множество символов М_a так, что множества М_a и М_b попарно не пересекаются при a¹b, то есть два различных множества не содержат одинаковых элементов. Множество М_a называется множеством шифрообозначений для буквы a.

Таблица 1.1

а	б	в	…	я
Ма	Мб	Мв	…	Мя

 

Таблица вида 1.1 является ключом шифра замены. Зная ее, можно осуществлять как зашифрование, так и расшифрование информации. Причем каждому α можно поставить в соответствие несколько вариантов М_α:

Таблица 1.2

а	б	в	г	…
				…
				…
				…

 

В этом случае сообщение можно зашифровать тремя способами, а расшифрование осуществляется однозначно.

Если каждой букве алфавита поставлена в соответствие буква алфавита замены, то такой шифр называется шифром простой однобуквенной замены.

 

Одним из известных шифров замены является шифр Цезаря. Такой шифр обладает недостатком: число различных ключей равно числу букв в алфавите.

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

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

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

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

Пример шифра замены – это шифр Атбаш. Алгоритм этого шифра прост: первая буква алфавита заменялась на последнюю, вторая на предпоследнюю в алфавите и т.д. Для успешной дешифрации необходимо было знать только алфавит сообщения. По смыслу алгоритма функция, реализующая шифровку и зашифровку одна и та же: , где n – мощность алфавита. Например, слово «ЗАМЕНА» выглядело бы после шифрования как «ХЮРЩПЮ».

Исходный текст алгоритма Атбаш для ASCII таблицы на языке С++:

// Функция шифрования/дешифрования

// char* toCode – кодируемое сообщение

// ret char* - закодированное сообщение

char* Atbash(char* toCode)

{

int i;

for (i = 0; toCode[i]!= 0; i++)

{

toCode[i] = (256 - toCode[i]);

}

return toCode;

}

Греческим писателем Полибием за 100 лет до н.э. был изобретен так называемый полибианский квадрат размером, например, 5*5. В каждую клетку этого квадрата вписывалась буква в порядке её следования в алфавите.

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

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

В такой прямоугольник записывается алфавит, причем схема записи держится в тайне и составляет ключ шифрования. Для того чтобы получались приближенные к квадрату матрицы (6х6, 5х7, 6х5), в алфавит могут включаться знаки препинания или исключаться редко используемые символы (такие как ‘ё’, ‘й’).

В процессе шифрования каждой букве ставилась в соответствие пара чисел – это номер столбца и номер строки, на пересечении которых располагалась шифруемая буква. Так для латинского алфавита буква «O» представлялась как 34 (3 – это номер строки, в которой находится буква «O», 4 – это номер столбца), а для русского алфавита буква «Т» – это 36. Таким образом, зашифрованное сообщение представлялось в виде последовательности цифр, для расшифровки которого необходимо знать язык сообщения, порядок следования букв в алфавите и размер квадрата.

 

Шифр Цезаря представляет простую замену, в которой каждая буква сообщения сдвигается вперед на фиксированное число мест по алфавиту. Это число является ключом и оно может быть любым от 0 до мощности алфавита -1. В шифре Цезаря каждый символ открытого английского текста заменяется символом, находящегося тремя символами правее по модулю 26 ("A" заменяется на "D," "B" - на "E",... "W" - на " Z ", "X" - на "A", "Y" - на "B", "Z" - на "C"). Применительно к современному русскому языку построение алфавита выглядит так (ключ равен 3):

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

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

При зашифровке буква А заменяется буквой Г, буква Б заменяется на Д и так далее. Например, слово «РИМ» заменяется на слово «УЛП». Получатель сообщения «УЛП» искал эти буквы в нижней строке и по буквам над ними восстанавливал исходное слово «РИМ». Ключом в шифре Цезаря является величина сдвига нижней строки алфавита. В нашем случае – это число 3.

Можно построить математическую модель шифрования: C_k(j) = (j + k) (mod n), где j - порядковый номер буквы в алфавите, C_k(j) – порядковый номер замещающей буквы, n – мощность входного алфавита (количество букв в используемом алфавите), а k - ключ (количество букв для сдвига).

Очевидно, что обратной подстановкой является C_k ^-1(j) = С_n-k = (j + n - k) (mod n).

Известная фраза Юлия Цезаря VENI VINI VICI - "пришел, увидел, победил" зашифрованная с помощью данного метода, преобразуется в YNQL YLGL YLFL (при смещении на 3 символа), или в SBKF SFAF SFZF (при смещении на 4 символа).

Реализация алгоритма Цезаря на языке С++ для ASCII таблицы будет следующей:

// Функция шифрования

// char* toCode – кодируемое сообщение

// int key – ключ

// ret char* - закодированное сообщение

char* CesarCrypt (char* toCode, int key)

{

int i;

for (i = 0; toCode[i]!=0; i++)

{

int tmp;

tmp = (toCode[i] + key);

// Нормализация

if (tmp >= 256). tmp -= 256;

toCode[i] = tmp;

}

return toCode;

}

 

// Функция дешифрования

// char* toDeCode – сообщение, подлежащее раскодированию

// int key – ключ

// ret char* - раскодированное сообщение

 

char* CesarEnCrypt (char* toDeCode, int key)

{

int i;

for (i = 0;t oDeCode[i]!= 0; i++)

{

int tmp;

tmp = (toDeCode[i] - key);

// Нормализация

if (tmp < 0) tmp += 256;

toDeCode[i] = tmp;

}

return toDeCode;

}

 

Шифр Ришелье.

Совершенно “естественно” выглядит криптотекст, полученный с помощью криптосистемы Ришелье. Соответственно, защищенность этого алгоритма гораздо выше предыдущих. В основе лежит “замешивание” по определенным законам исходного текста в “мусоре”, или посторонних символах. Зашифрованный текст получается гораздо длиннее исходного, причем эта разница и определяет реальную криптостойкость системы. Суть метода Ришелье в следующем. Создается подобная решетка с прорезями вместо крестов (рис. 1.3):

Х	Х						Х		Х
Х	Х				Х			Х
						Х
Х		Х	Х	Х					Х
							Х		Х
	Х			Х	Х		Х		Х

Рисунок 1.3 – Пример решетки Ришелье

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

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

Пусть в качестве ключа используется группа из тpex цифр - 314, тогда Сообщение СОВЕРШЕННО СЕКРЕТНО

Ключ 3 14 31 4 314314314314 3

Шифровка ФПИСЬИОССАХИЛФИУСС

 

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

где К_i - буква ключа, полученная сокращением числа i по модулю d; m_i – буква сообщения; l_i – буква криптограммы.

Например, с помощью ключа GAH исходное сообщение преобразуется в криптограмму:

Сообщение	N	O	W	I	S	T	H	E
Повторяемый ключ	G	A	H	G	A	H	G	A
Криптограмма	T	O	D	O	S	A	N	E

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

 

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

Для примера возьмем фразу “ОТРЯД ЖДЕТ УКАЗАНИЙ” и исключим из нее пробелы: “ОТРЯДЖДЕТУКАЗАНИЙ” – исходный текст, “ГРАФДРАКУЛАГРАФДР” – циклический ключ. Преобразование производится так: шифруемому символу соответствует символ, находящийся на пересечении буквы ключа (столбец) и буквы исходного текста (строка). Получим: “СВРУИЦДПЕЮКГЧАБМЩ”.

Шифр Виженера с периодом 1 является шифром Цезаря.

Так называемый шифр Бофора подобен шифру Виженера. В них сообщение зашифровывают с помощью равенств:

и соответственно.

Повторное применение двух или более шифров Виженера называтется составным шифром Виженера и имеет уравнение:

где k_i, l_i,...,s_i могут иметь разные периоды. Период их суммы (k_i+ l_i+...+s_i) будет наименьшим общим кратным отдельных периодов.

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

и K_i выбирают случайно и независимо среди чисел 0,1,..., d. Если ключом служит текст, имеющий смысл, то имеем шифр "бегущего ключа".

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

Шифр Виженера с перемешанным один раз алфавитом. Такой шифр представляет собой простую подстановку с последующим применением шифра Виженера:

.

"Обратным" к такому шифру является шифр Виженера с последующей простой подстановкой:

.

Метрическая система. Имеется один метод подстановки n -грамм, который заключается в применении к последовательным n -граммам некоторой матрицы, имеющей обратную. Предполагается, что буквы занумерованы от 0 до d и рассматриваются как элементы некоторого алгебраического кольца.

Если к n -грамме сообщения применить матрицу a_ij, то получится n-грамма криптограммы:

Матрица a_ij является ключом, а расшифровка выполняется с помощью обратной матрицы. Обратная матрица будет существовать тогда и только тогда, когда определитель | a_ij | имеет обратный элемент в кольце.1

1. Наиболее известный шифр биграммами называется Playfair. Он применялся Великобританией в Первую мировую войну. Шифр Плейфера. Этот шифр является частным видом диграммной подстановки, которая производится с помощью алфавита из d букв, записанного в виде квадрата, например, для латинского алфавита 5*5. Шифрование производится с помощью квадрата (или прямоугольника), в который занесены буквы соответствующего алфавита. Буквы записываются в квадрат или прямоугольник в произвольном порядке. Этот порядок и конфигурация таблицы являются секретным ключом. Для определенности возьмем прямоугольную таблицу 8x4, в качестве букв

алфавита – кириллицу, а буквы расположим в алфавитном порядке. Т.к. число русских букв 33, а число клеток – 32, исключим из таблицы букву Ё.	А	Б	В	Г	Д	Е	Ж	З
И	Й	К	Л	М	Н	О	П
Р	С	Т	У	Ф	Х	Ц	Ч
Ш	Щ	Ъ	Ы	Ь	Э	Ю	Я

Рассмотрим правила шифрования:

1) открытый текст делится на блоки по две буквы. Буквы в одном блоке не должны быть одинаковыми.

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

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

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

При шифровании слова «КР ИП ТО ГР АФ ИЯ» получаем «ИТ ЙИ ЦК АУ ДР ПШ».

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

Перемешивание алфавита с помощью многократной подстановки. В этом шифре используют последовательно d простых подстановок. Так, если d=4, то заменяется на

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

 

Сообщение	S	E	N	D	S	U	P	P	L	I	…
Ключ	C	O	M	E	T	S	E	N	D	S	…
Криптограмма	U	S	Z	H	L	M	T	C	O	A	…

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

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

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

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

 

Практическое задание

4.1P. Используя криптографические алгоритмы замены, составить программу на языке программирования для шифрования и дешифрования текстов.

4.1E. Реализация шифрования в Microsoft Excel формулами по квадрату Виженера:

Если использовать готовый квадрат Виженера, то реализовать шифрование можно одной формулой с помощью функций ИНДЕКС (INDEX) и ПОИСКПОЗ (MATCH).

Выглядеть это может примерно так:

Логика этой формулы следующая:

Первая функция ПОИСКПОЗ (подсвечена зеленым) ищет первую букву ключа (З) в зеленом столбце (B9:B40) и выдает порядковый номер ячейки, где она ее нашла, т.е. номер строки в квадрате Виженера по которому идет шифрование.

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

Функция ИНДЕКС выдает содержимое ячейки из квадрата (C9:AH40) с пересечения строки и столбца с найденными номерами.

 

Возможно выполнить реализацию формулами по кодам символов.

В реальной жизни в документах могут использоваться не только буквы русского языка, но и латиница, цифры, знаки препинания и т.д. Создавать вручную квадрат Виженера с участием всех этих символов - та еще эпопея, но есть другой, гораздо более простой способ. Внутри компьютера и операционной системы каждый символ имеет свой числовой код от 0 до 255 (его еще называют ASCII-кодом). Microsoft Excel имеет в своем стандартном наборе две функции, которые умеют с ними работать:

Функция КОДСИМВ (CODE) - выдает числовой код символа, указанного в качестве аргумента. Например КОДСИМВ("Ж") выдаст 198.

Функция СИМВОЛ (CHAR) - выдает символ, соответствующий указанному в аргументе коду, т.е. наоборот СИМВОЛ(198) даст нам букву Ж.

Расшифровка производится совершенно аналогично, только знак "плюс" в формуле меняется на "минус":

 

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

5. Содержание отчета:

· название и цель лабораторной работы;

· описание алгоритма и блок-схемы программы;

· результаты выполнения программы: исходный, зашифрованный и дешифрованный тексты;

· расчеты статистических характеристик;

· выводы, отражающие достоинства и недостатки исследуемых алгоритмов.

 

Контрольные вопросы

1. Что называют шифрами замены?

2. Каков общий алгоритм шифров замены?

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

4. Описать разновидности шифра Виженера.

5. Каковы особенности шифра Плейфера?

6. Что является ключом шифра замены? Чему равен ключ составных шифров замены?

7. В чем слабость шифров замены?

8. Как можно увеличить стойкость шифра замены?