Шифры замены

Шифры замены, или подстановки, являются самыми древними. В криптографии рассматриваются 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 символов. Однако не все «номенклаторы» были сломаны.

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

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

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

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

Шифр Плейфера

Криптоанализ

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

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

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

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

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

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

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

Одно из первых шифровальных устройств было придумано в пятнадцатом веке и осуществляло замену шифром Цезаря . Его автором являлся итальянский архитектор Леоном Баттиста Альберти , который внес ощутимый вклад в развитие шифров подстановки. Данное устройство состояло из двух медных дисков разного размера, скрепленных иглой. По краям каждого диска наносился алфавит. Оба диска могли вращаться независимо друг от друга, тем самым сопоставляя буквы открытого и шифрованного текста. Диск Альберти широко использовался пять столетий, в том числе во время Гражданской войны в США .

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

Роторные машины применялись различными странами в ходе Второй мировой войны . Наиболее известными из них были: американская машина SIGABA , немецкая ENIGMA , английская TYPEX и японская PURPLE.

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

Применение в наше время

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

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

Простейшим из шифров замены является одноалфавитная подстановка , называемая также шифром простой замены . Ключом такого шифра является взаимно однозначное отображение (подстановка ) F алфавита открытого текста (X ) в алфавит шифртекста (Y ): F : X ↔Y . Зафиксируем нумерацию символов в алфавитах X и Y : X = {x 1 , x 2 , … x n }, Y = {y 1 , y 2 , … y n }. Тогда отображение F фактически задается перестановкой p порядка n = |X | = |Y |: при шифровании символ x i открытого текста заменяется на символ y p ( i ) шифртекста. Эта перестановка может быть задана либо таблицей, либо с помощью формулы. При задании с помощью формулы значение p(i ) представляется в виде выражения, зависящего от i .

Типичным примером шифра замены является шифр Цезаря . Этот шифр реализует следующее преобразование текста, записанного с помощью латинского алфавита: каждая буква открытого текста заменяется буквой, стоящей на три позиции позже нее в алфавите (при этом алфавит считается записанным по кругу, то есть после буквы "z" идет буква "a"). Например, открытый текст "secret" будет преобразован в "vhfuhw". Ключ для шифра Цезаря можно задать в виде следующей таблицы (см. рис. 2.3). В первой строке записаны буквы открытого текста, во второй – соответствующие им буквы шифртекста.

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

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

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

Шифры простой замены в настоящее время не используются, поскольку их стойкость невелика. Методы взлома таких шифров основаны на анализе частотности отдельных символов и их комбинаций. Дело в том, что в любом языке различные буквы и комбинации из двух, трех или большего количества букв имеют характерные частоты повторений в текстах. Например, в текстах на русском языке чаще всего встречается буква "О", затем, в порядке убывания частоты, идут буквы "Е" (считая, что "Е" и "Ё" – одна и та же буква), "А", "И", "Т" и т.д. Для английского языка аналогичная последовательность самых частых букв: "E", "T", "A", "I", "N". Самым частым символом в текстах является, однако, не буква, а символ пробела.

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

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

Частным случаем многоалфавитной замены является шифр Виженера. Формально этот шифр можно описать следующим образом. В качестве ключа шифрования выберем набор из m целых чисел: k = (k 1 , k 2 , …, k m ). Процедуру преобразования открытого текста t = (t 1 , t 2 , …) в шифртекст c = (c 1 , c 2 , …) построим на основе обобщенного шифра Цезаря: c 1 = t 1 + k 1 (mod 26),
c 2 = t 2 + k 2 (mod 26), и т.д. Когда будут использованы все m компонент ключа k , для шифрования (m +1)-й буквы снова возьмем k 1 , и т.д. Фактически, в качестве ключа шифрования используется гамма шифра – бесконечная последовательность, образованная периодическим повторением исходного набора: k 1 ,k 2 ,…,k m , k 1 ,k 2 ,…,k m , k 1 ,k 2 ,…

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

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

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

Простейшим вариантом гомофонического шифра является следующий. Предположим, что нам известны частоты вхождений символов в открытый текст. Пусть f i - частота появления i –го символа в открытом текста (i - номер буквы в алфавите). Каждой букве t i исходного алфавита (т.е. алфавита, с помощью которого записывается открытое сообщение) сопоставим подмножество F i , содержащее f i символов выходного алфавита (т.е. алфавита, с помощью которого записывается шифртекст), причем никакие два подмножества F i и F j не пересекаются. При шифровании будем заменять каждое вхождение символа t i на случайный символ из множества F i . Ясно, что средняя частота появления в шифртексте любого из символов выходного алфавита одинакова, что существенно затрудняет криптоанализ.

Шифры гаммирования

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

Суть метода гаммирования заключается в следующем. С помощью секретного ключа k генерируется последовательность символов

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

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

Расшифрование осуществляется применением к символам шифртекста и гаммы обратной операции: , или (операция XOR является обратной к самой себе).

Стойкость систем шифрования, основанных на гаммировании, зависит от характеристик гаммы – ее длины и равномерности распределения вероятностей появления знаков гаммы.

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

1) все символы гаммы полностью случайны и появляются в гамме с равными вероятностями;

2) длина гаммы равна длине открытого текста или превышает ее;

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

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

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

Линейный конгруэнтный генератор задается рекуррентной формулой: g i = a ×g i – 1 + b (mod m ), где g i – i -й член последовательности псевдослучайных чисел; a , b , m и g 0 – ключевые параметры. Данная последовательность состоит из целых чисел от 0 до m – 1, и если элементы g i и g j совпадут, то последующие участки последовательности также совпадут: g i +1 = g j +1 , g i +2 = g j +2 , и т.д. Поэтому последовательность {g i } является периодической, и ее период не превышает m . Для того чтобы период последовательности псевдослучайных чисел, сгенерированной по указанной рекуррентной формуле, был максимальным (равным m), параметры данной формулы должны удовлетворять следующим условиям:

· b и m -взаимно простые числа;

· a – 1 делится на любой простой делитель числа m ;

· a – 1 кратно 4, если m кратно 4.

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

, i = 0,1…,

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

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

Последовательности такого вида легко реализуются программными или аппаратными средствами. Основу этой реализации составляет регистр сдвига с линейной обратной связью (РСЛОС).

РСЛОС представляет собой простое в реализации, недорогое устройство, способное формировать последовательности и обеспечить такие требования как:

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

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

· сбалансированность структуры;

· максимальность периода для данной длины регистра сдвига.

Обобщенная схема РСЛОС приведена на рис. 2.4.

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

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

Любой n -битовый РСЛОС может находиться в одном из 2 n –1 внутренних состояний. Это означает, что теоретически такой регистр может генерировать псевдослучайную последовательность с периодом 2 n –1 битов. (Число внутренних состояний и максимальный период равны 2 n –1, потому что заполнение РСЛОС нулями, приведет к тому, что сдвиговый регистр будет выдавать бесконечную последовательность нулей, что абсолютно бесполезно.) Только при определенных отводных последовательностях РСЛОС циклически пройдет через все 2 n –1 внутренних состояний, такие РСЛОС являются регистрами с максимальным периодом. Получившийся результат называется М – последовательностью .

Для того, чтобы конкретный n -битовый РСЛОС имел максимальный период 2 n –1, двоичный полином f (x ) = h n x n + h n – 1 x n – 1 + … + h 1 x + 1, образованный из отводной последовательности и константы 1, должен быть примитивным. Полином f (x ) степени n называется примитивным , если его нельзя представить в виде произведения двух полиномов с меньшими степенями (свойство неприводимости) и, если x является генератором всех ненулевых полиномов со степенями не выше n , умножение которых осуществляется по модулю f (x ).

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

История [ | ]

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Максимальное количество ключей для любого шифра этого вида не превышает n!, где n - количество символов в алфавите. С увеличением числа n значение n! растет очень быстро (1! = 1, 5! = 120, 10! = 3628800, 15! = 1307674368000). При больших n для приближенного вычисления n! можно воспользоваться формулой Стирлинга

Шифр Цезаря. Данный шифр был придуман Гаем Юлием Цезарем и использовался им в своей переписке (1 век до н.э.). Применительно к русскому языку суть его состоит в следующем. Выписывается исходный алфавит (А, Б, ..., Я), затем под ним выписывается тот же алфавит, но с циклическим сдвигом на 3 буквы влево.

Рис.3.

При зашифровке буква А заменяется буквой Г, Б - на Д и т. д. Так, например, исходное сообщение «АБРАМОВ» после шифрования будет выглядеть «ГДУГПСЕ». Получатель сообщения «ГДУГПСЕ» ищет эти буквы в нижней строке и по буквам над ними восстанавливает исходное сообщение «АБРАМОВ».

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

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

Рис.4.

При шифровании исходного сообщения «АБРАМОВ» по приведенному выше ключу шифрограмма будет выглядеть «ДЯПДКМИ».

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

Шифруемая буква заменяется на координаты квадрата (строка-столбец), в котором она записана. Например, если исходное сообщение «АБРАМОВ», то шифрограмма - «11 12 36 11 32 34 13». В Древней Греции сообщения передавались с помощью оптического телеграфа (с помощью факелов). Для каждой буквы сообщения в начале поднималось количество факелов, соответствующее номеру строки буквы, а затем номеру столбца.

Шифрующая система Трисемуса (Тритемия). В 1508 г. аббат из Германии Иоганн Трисемус написал печатную работу по криптологии под названием «Полиграфия». В этой книге он впервые систематически описал применение шифрующих таблиц, заполненных алфавитом в случайном порядке. Для получения такого шифра замены обычно использовались таблица для записи букв алфавита и ключевое слово (или фраза). В таблицу сначала вписывалось по строкам ключевое слово, причем повторяющиеся буквы отбрасывались (рис. 6). Затем эта таблица дополнялась не вошедшими в нее буквами алфавита по порядку. На рис.6 изображена таблица с ключевым словом «ДЯДИНА».

Рис.5.

полибианского квадрата для шифра Трисемуса

Каждая буква открытого сообщения заменяется буквой, расположенной под ней в том же столбце. Если буква находится в последней строке таблицы, то для ее шифрования берут самую верхнюю букву столбца. Например, исходное сообщение «АБРАМОВ», зашифрованное - «ИЙЪИХШК».

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

Таблица 1. Вероятности появления букв русского языка в текстах*

*) В таблице приведены оценки вероятностей появления букв русского языка и пробела, полученные на основе анализа научно-технических и художественных текстов общим объемом более 1000000 символов.

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

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