Главная

Времена года

Пример шифра простой и сложной замены. Простейшие методы шифрования с закрытым ключом

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

Ключом такого шифра является взаимно однозначное отображение (подстановка ) F алфавита открытого текста (X ) в шифртекста (Y ): F: X Y. Зафиксируем нумерацию символов в алфавитах X и Y : X = { ,, … }, Y = { , , … }.

Тогда отображение F фактически задается перестановкой порядка n = |X | = |Y |: при шифровании символ xi открытого текста заменяется на символ шифртекста.

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

Пример. Типичным примером шифра замены является шифр Цезаря . Этот шифр реализует следующее преобразование текста, записанного с помощью латинского алфавита: каждая буква открытого текста заменяется буквой, стоящей на три позиции позже нее в алфавите (при этом алфавит считается записанным по кругу, то есть после буквы ‘z’ идет буква ‘a’).

Открытый текст ‘secret’ будет преобразован в ‘vhfuhw’. Ключ для шифра Цезаря можно задать в виде следующей таблицы (рис. 3). В первой строке записаны буквы открытого текста, во второй - соответствующие им буквы шифртекста.

Шифр Цезаря можно описать и в виде формулы. Для этого пронумеруем буквы латинского алфавита числами от 0 до 25: a = 0, b = 1, …, z = 25. Тогда правило замены можно описать следующим образом: буква с номером i i+3 (mod 26 ), где операция ‘mod 26’ означает вычисление остатка от деления на 26.

Возможен обобщенный вариант шифра Цезаря, при котором буква с номером i заменяется на букву с номером i +k (mod 26). В этом случае ключом шифра является число k .

Еще больше обобщив этот метод, придем к семейству аффинных шифров . Для алфавита из n символов { , , …, } аффинным шифром называется процедура, заменяющая входной символ на символ , где j = k ·i +l (mod n ).

Шифры простой замены в настоящее время не используются, поскольку их стойкость невелика. Методы взлома таких шифров основаны на анализе частотности отдельных символов и их комбинаций. Дело в том, что в любом языке различные буквы и комбинации из двух, трех или большего количества букв имеют характерные частоты повторений в текстах. Например, в текстах на русском языке чаще всего встречается буква ‘О ’, затем, в порядке убывания частоты, идут буквы ‘Е ’ (считая, что ‘Е ’ и ‘Ё ’ - одна и та же буква), ‘А ’, ‘И ’,

‘Т’ и т. д. Для английского языка аналогичная последовательность самых частых букв: ‘E’, ‘T’, ‘A’, ‘I’, ‘N’. Самым частым символом в текстах является, однако, не буква, а символ пробела.

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

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

Процедура шифрования для многоалфавитной замены включает набор подстановок {, , …, } и функцию - распределитель (k, i), задающую последовательность применения подстановок .

При шифровании i-го символа открытого текста применяется подстановка с номером (k,i), где k - ключ шифрования.

Частным случаем многоалфавитной замены является шифр Виженера. Формально этот шифр можно описать следующим образом.

В качестве ключа шифрования выберем набор из m целых чисел:

k = (, , …, ). Процедуру преобразования открытого текста t = (, , …) в шифртекст c = (, , …) построим на основе обобщенного шифра Цезаря:

= + (mod 26) , = + (mod 26) , и т.д. Когда будут использованы все m компонент ключа k, для шифрования (m+1) -й буквы снова возьмем , и т.д. Фактически, в качестве ключа шифрования используется бесконечная последовательность, образованная периодическим повторением исходного набора: , , …, , , , …, , , , … Такую последовательность принято называть гаммой.

Взломать шифр многоалфавитной замены немного сложнее, чем шифры простой замены, но тоже достаточно легко. Такой шифр на самом деле представляет собой одновременное применение m шифров простой замены (обобщенный шифр Цезаря), причем часть исходного текста, состоящая из букв , , , … шифруются с использованием «ключа» ki (i=1, …, m).

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

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

Такие шифры замены называются гомофоническими .

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

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

Одноалфавитная замена

Одним из важных подклассов методов замены являются одноалфавитные (или моноалфавитные) подстановки, в которых устанавливается однозначное соответствие между каждым знаком a i исходного алфавита сообщений A и соответствующим знаком e i зашифрованного текста E . Одноалфавитная подстановка иногда называется также простой заменой, так как является самым простым шифром замены.

Примером одноалфавитной замены является шифр Цезаря, рассмотренный ранее. В рассмотренном в "Основные понятия криптографии" примере первая строка является исходным алфавитом, вторая (с циклическим сдвигом на k влево) – вектором замен.

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

Подстановка может быть задана с помощью таблицы, например, как показано на рис. 2.3 .

Рис. 2.3.

Рис. 2.4.

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

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

Известно, что в текстах на русском языке наиболее часто встречаются символы О, И . Немного реже встречаются буквы Е, А . Из согласных самые частые символы Т, Н, Р, С . В распоряжении криптоаналитиков имеются специальные таблицы частот встречаемости символов для текстов разных типов – научных, художественных и т.д.

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

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

ТНФЖ.ИПЩЪРЪ

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

Таблица 2.1. Варианты первого этапа криптоанализа

Зашифрованное сообщение
Т	Н	Ф	Ж	.	И	П	Щ	Ъ	Р	Ъ
После замены Ъ на О
								О		О
После замены Ъ на А
								А		А
После замены Ъ на И
								И		И
После замены Ъ на Е
								Е		Е

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

Таблица 2.2. Варианты второго этапа криптоанализа

Зашифрованное сообщение
Т	Н	Ф	Ж	.	И	П	Щ	Ъ	Р	Ъ
Варианты подобранных дешифрованных сообщений
Ж	Д	И		С	У	М	Р	А	К	А
Д	Ж	О	Н	А		У	Б	И	Л	И
В	С	Е	Х		П	О	Б	И	Л	И
М	Ы		П	О	Б	Е	Д	И	Л	И

Оценим размер такой таблицы замен. Если исходный алфавит содержит N символов, то вектор замен для биграммного шифра должен содержать N 2 пар "откр. текст – зашифр. текст" . Таблицу замен для такого шифра можно также записать и в другом виде: заголовки столбцов соответствуют первой букве биграммы, а заголовки строк – второй, причем ячейки таблицы заполнены заменяющими символами. В такой таблице будет N строк и N столбцов ( таблица 2.4).

Таблица 2.4. Другой вариант задания таблицы замен для биграммного шифра

	а	б	...	я
а	кх	цу	...	...
б	пу	пш	...	...
в	жа	вь	...	...
...	...	...	...	...
ю	...	...	...	ек
я	ис	...	...	рт

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

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

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

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

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

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

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

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

> Матрица букв

шифрограмм

Столбец ключа

Строка букв

открытого

Рис. 5.1. Таблица Вижинера

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

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

Задача 5.5

Пусть необходимо зашифровать следующий открытый текст : «ТО BE OR NOT ТО BE THAT IS THE QUESTION», используя секретный ключ «RELATIONS».

Решение.

Разобьем процесс шифрования на следующие этапы.

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

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

После шифрования получим криптограмму:

«КЗ МЕ НЕЕ ВВЬ КБ МЕ МРСЮ А1 ХЭЕ,Ю5ЕЕ78У».

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

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

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

Шифры замены

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

а	б	в	г	д	е	ж	З
ф	ы	в	а	п	р	о	Л

Тогда слово "багаж" будет заменено на слово "ыфафо". При расшифровании производится обратная операция.

Общая формула моноалфавитной замены выглядит следующим образом:

y i =k 1 x i +k 2 (mod n),

где y i – i-й символ алфавита; k 1 и k 2 – константы; x i – i-й символ открытого текста (номер буквы в алфавите); n – длина используемого алфавита.

Шифр, задаваемый формулой

y i =x i +k i (mod n),

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

Пример 2. Открытый текст: «ЗАМЕНА». Подстановка задана следующим образом:

З	А	М	Е	Н	А
К	Л	Ю	Ч	К	Л

y 1 = 8 + 11(mod 33) = 19 Т; y 2 =1 + 12(mod 33) = 13 М;

y 3 =13 + 31(mod ЗЗ) = 11 K; y 4 = 6 + 24(mod 33) = 30 Э;

y 5 = 14+ 11(mod 33) = 25 Щ; y 6 = 1 + 12(mod 33) = 13 М.

Шифртекст: «ТМКЭШМ».

Шифры Бофора используют формулы:

у i = k i – x i (mod n) и у i =x i – k i (mod n).

Основным недостатком является то, что статистические свойства открытого текста (частоты повторения букв) сохраняются и в шифртексте. Формальный подход к дешифрованию основан на использовании средней частоты появления букв в текстах. Впервые похожий метод был предложен в конце 15-го века (итальянский математик Леон Баттиста Альберти) и использовал свойство неравномерности встречаемости разных букв алфавита. Позднее были определены средние частоты использования букв языка в текстах:

Частота бyквосочетаний в английском языке:

TH, HE, IN, AN, EN, ER, OR, ES, ON, RE, AT, EA, ST, TI, ED, ND, NT, RR, LL, SS, MM.

QUI, ING, ION, ARE, TIO, ONE, ANT, MENT, TION, SION.

Частота бyквосочетаний в рyсском языке:

CТ, HО, ЕH, ТО, HА, ОВ, HИ, РА, ВО, КО, ОИ, ИИ, ИЕ, ЕИ, ОЕ, ИЯ, HH, CC.

CТО, ЕHО, HОВ, ТОВ, ОВО, HАЛ, РАЛ, HИC.

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

Гомофоническая замена одному символу открытого текста ставит всоответствие несколько символов шифртекста.

Пример 3. Открытый текст: «ЗАМЕНА». Подстановка задана следующей таблицей:

Шифртекст: «76 17 32 97 55 31» .

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

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

· если символы находятся в одной строке, то каждый из символов пары заменяется на стоящий правее его (за последним символом в строке следует первый);

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

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

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

Пример 4. Открытый текст: «ШИФР ПЛЭЙФЕРА». Матрица алфавита представлена в следующей таблице. Шифртекст: «РДЫИ,– СТ – И.ХЧС».

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

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

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

Пример 5. Открытый текст: «ШИФРОВАНИЕ ЗАМЕНОЙ». Первичный ключ: «КЛЮЧ». Схема шифрования с автоключом при использовании открытого текста представлена в следующей таблице:

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

Для повышения стойкости шифра используют так называемые полиалфавитные подстановки , которые для замены используют несколько алфавитов шифротекста. Пусть имеется k алфавитов. Тогда открытый текст

X= x 1 x 2 ...x k x k +1 ...x 2 k x 2 k+1 ...

заменяется шифротекстом

У =f 1 (x 1)f 2 (x 2)...f k (x k)f 1 (x k+1)...f k (x 2k)f 1 (x 2k+1)...,

где f i (x j) означает символ шифртекста алфавита i для символа открытого текста x j .

Пример 6. Открытый текст: «ЗАМЕНА», k = 3. Подстановка задана таблицей из примера 3. Шифртекст: «76 31 61 97 84 48».

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

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

В качестве примера рассмотрим шифрование с помощью таблицы Вижинера . Таблица Вижинера представляет собой квадратную матрицу с n 2 элементами, где n – число символов используемого алфавита. Ниже показана таблица Вижинера для русского языка. Каждая строка получена циклическим сдвигом алфавита на символ. Для шифрования выбирается буквенный ключ, в соответствии с которым формируется рабочая матрица шифрования. Осуществляется это следующим образом. Из полной таблицы выбирается первая строка и те строки, первые буквы которых соответствуют буквам ключа. Первой размещается первая строка, а под нею – строки, соответствующие буквам ключа в порядке следования этих букв в ключе.

Сам процесс шифрования осуществляется следующим образом:

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

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

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

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

Расшифрование текста производится в следующей последовательности:

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

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

3. полученный текст группируется в слова по смыслу.

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

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

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

1) во всех (кроме первой) строках таблицы буквы располагаются в произвольном порядке;

2) в качестве ключа используются случайные последовательности чисел. Из таблицы Вижинера выбираются десять произвольных строк, которые кодируются натуральными числами от 0 до 10. Эти строки используются в соответствии с чередованием цифр в выбранном ключе.

Частным случаем рассмотренной полиалфавитной замены является так называемая монофоническая замена. Особенность этого метода состоит в том, что количество и состав алфавитов выбираются таким образом, чтобы частоты появления всех символов в зашифрованном тексте были одинаковыми. При таком положении затрудняется криптоанализ зашифрованного текста с помощью его статистической обработки. Выравнивание частот появления символов достигается за счет того, что для часто встречающихся символов исходного текста предусматривается использование большего числа заменяющих элементов, чем для редко встречающихся. Шифрование осуществляется также, как и при простой замене (т. е. по шифрующему алфавиту № 1) с той лишь разницей, что после шифрования каждого знака соответствующий ему столбец алфавитов циклически сдвигается вверх на одну позицию. Таким образом, столбцы алфавита как бы образуют независимые друг от друга кольца, поворачиваемые вверх на один знак каждый раз после шифрования соответствующего знака. При увеличении объема текста частоты появления символов будут еще более выравниваться.

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

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

t i ш = t i о + mod(k -1),

где t i ш – символ зашифрованного текста; t i о – символ исходного текста; – целое число в диапазоне 0 – (k -1); k – число символов используемого алфавита.

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

История [ | ]

Использование шифров подстановки берет свое начало в Месопотамии . С целью сокрытия информации о рецепте производства глазури для гончарных изделий автор заменял часть слов на цифры и клинописные знаки . Римский император Гай Юлий Цезарь при написании секретных сообщений смещал каждую букву алфавита на 3 позиции. Данный вид шифров подстановки впоследствии назвали его именем, шифр Цезаря . Другой не менее известный шифр античности , Атбаш , применялся в Библии для создания скрытых посланий. Каждая буква слова заменялась её зеркальным отражением в алфавите.

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

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

Шифры простой замены [ | ]

Шифр с использованием кодового слова [ | ]

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

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

Метод записи зашифрованных текстов [ | ]

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

Безопасность шифров простой замены [ | ]

Главный недостаток этого метода шифрования - это то, что последние буквы алфавита (которые имеют низкие коэффициенты при частотном анализе) имеют тенденцию оставаться в конце. Более защищённый способ построить алфавит замены состоит в том, чтобы выполнить колоночное перемещение (перемещение столбцов) в алфавите, используя ключевое слово, но это нечасто делается. Несмотря на то, что число возможных ключей является очень большим (26! = 2 88.4), этот вид шифра может быть легко взломанным. При условии, что сообщение имеет достаточную длину (см. ниже), криптоаналитик может предположить значения некоторых самых распространённых букв исходя из анализа частотного распределения символов в зашифрованном тексте. Это позволяет формировать отдельные слова, которые могут быть предварительно использованы, для последующего получения более полного решения (см. частотный анализ). Согласно расстоянию уникальности английского языка 27.6 букв от зашифрованного текста должно быть достаточно, чтобы взломать шифр простой замены. На практике обычно достаточно около 50 символов для взлома, хотя некоторые шифротексты могут быть взломаны и с меньшим количеством символов, если найдены какие-либо нестандартные структуры. Но при равномерном распределении символов в тексте могут потребоваться куда более длинные шифротексты для взлома.

Омофоническая замена [ | ]

Ранние попытки увеличить сложность частотного анализа шифротекстов состояли в том, чтобы замаскировать реальные частоты появления символов обычного текста с помощью омофонии. В этих шифрах буквы исходного алфавита соответствуют более чем одному символу из алфавита замены. Обычно символам исходного текста с наивысшей частотой дают большее количество эквивалентов , чем более редким символам. Таким образом, распределение частоты становится более равномерным, сильно затрудняя частотный анализ. С тех пор, как для алфавита замены стало требоваться больше чем 26 символов, появилась необходимость в расширенных алфавитах. Одним из самых простых решений является замена алфавита на цифры . Другой метод состоит из простых изменений существующего алфавита: прописные буквы , строчные буквы , перевернутые и т. д. Более художественными, хотя не обязательно более надежными, будут омофонические шифры, которые используют полностью изобретённые (вымышленные) алфавиты (как например, шифр в книге «Золотой жук» Э. По, или «Рукопись Войнича ». Впрочем, эти шифры не являются примерами омофонической замены).

Примеры омофонических шифров [ | ]

Номенклатор [ | ]

Шифр, изданный средневековым чиновником, представляющий собой маленькую книгу с большими омофоническими таблицами замены. Первоначально шифр был ограничен именами важных людей того времени, отсюда и последовало название шифра; в более поздних изданиях этот шифр дополнился большим количеством распространённых слов и географических названий. На основе этого «номенклатора» был составлен Великий Шифр Россиньоля, использовавшийся королём Франции Людовиком XIV . И действительно, после того как этот шифр перестал использоваться, французские архивы были закрытыми ещё в течение нескольких сотен лет. «Номенклаторы» были стандартом для дипломатической корреспонденции, шпионских сообщений и являлись основным средством антиполитической конспирации с начала пятнадцатого столетия до конца восемнадцатого столетия. Хотя правительственные криптоаналитики систематически взламывали «номенклаторы» к середине шестнадцатого столетия. Обычным выходом из этой ситуации было увеличение объёмов таблиц. Но к концу восемнадцатого столетия, когда система начала выходить из употребления, некоторые «номенклаторы» имели до 50 000 символов. Однако не все «номенклаторы» были сломаны.

Великий Шифр Россиньоля [ | ]

Полиграммные шифры [ | ]

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

Примеры полиграммных шифров [ | ]

Шифр Плейфера [ | ]

Криптоанализ [ | ]

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

Атаки на основе открытых текстов [ | ]

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

Атаки на основе подобранного открытого текста [ | ]

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

В шифровальных машинах [ | ]

Разделы

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

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

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