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

История [ | ]

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Шифры замены

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

В своей работе «Математическая теория секретной связи» Клод Шеннон обобщил накопленный до него опыт разработки шифров.

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

14.1.Шифр замены

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

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

Шифр замены является простейшим, наиболее популярным шифром. Примерами являются: шифр Цезаря , « цифирная азбука» Петра Великого и « пляшущие человечки» А. Конан-Дойля .

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

Увеличив алфавиты, т.е. объявив «части» буквами, можно любой шифр замены свести к замене букв.

Дадим математическое описание шифра замены .

Пусть: X – алфавит открытого текста, а Y - алфавит шифрованног о текста, состоящие из одинакового числа символов .

Пусть также: g: X  Y – взаимнооднозначное отображение X в Y . Каждой буквех алфавита X сопоставляется однозначно определенная буква у алфавита Y , которую обозначаем символом g(х), причем разным буквам сопоставляются разные буквы .

Тогда шифр замены действует так: открытый текст x 1 x 2 ...x n преобразуется в шифрованный текст g (х 1 )g(x 2 )...g(x n ).

В криптографии рассматриваются 4 типа замены :

моноалфавитная;

гомофоническая;

полиалфавитная;

полиграммная.

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

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

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

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

Примером этого метода является шифр под названием Атбаш.

Правило шифрования состоит в замене i - ой буквы алфавита буквой с номером n= i + 1 , где n - число букв в алфавите. Пример для латинского алфавита выглядит так:

Исходный текст: abcdefghijklmnopqrstuvwxyz

Зашифрованный текст: ZYXWVUTSRQPONMLKJIHGFEDCBA

Гомофоническая замена

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

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

Полиграммная замена

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

Полиалфавитные подстановки

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

Известно несколько разновидностей полиалфавитной подстановки, наиболее известными из которых являются:

одноконтурная (обыкновенная и монофоническая)

и многоконтурная.

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

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

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

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

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

Частным случаем рассмотренной полиалфавитной замены является так называемая монофоническая замена .

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

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

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

одинаковых элементов. Множество называется множеством Шифр-обозначений для буквы а.

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

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

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

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

Часто состоит из одного элемента. Например, в романе Верна «Путешествие к центру Земли» в руки профессора Лиденброка попадает пергамент с рукописью из знаков рунического письма. Каждое множество состоит из одного элемента. Элемент каждого множества выбирается из набора символов вида

В рассказе А. Конан Дойла «Пляшущие человечки» каждый символ изображает пляшущего человечка в самых различных позах

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

Рассмотрим некоторые примеры шифров замены. Пусть каждое множество состоит из одной буквы. Например,

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

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

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

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

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

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

В данном случае число вариантов ключа существенно больше числа букв алфавита.

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

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

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

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

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

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

Любые особенности текста, которые могут быть вам известны, - ваши помощники. Например, в задаче 5.2 прямо сказано, что в тексте есть выражения «зпт», «тчк», как часто бывает в реальных телеграммах. И эта подсказка - путь к решению задачи.

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

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

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

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

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

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

4.1. Основы шифрования

Сущность шифрования методом замены заключается в следующем . Пусть шифруются сообщения на русском языке и замене подлежит каждая буква этих сообщений. Тогда, букве А исходного алфавита сопоставляется некоторое множество символов (шифрозамен) М А, Б – М Б, …, Я – М Я . Шифрозамены выбираются таким образом, чтобы любые два множества (М I и М J , i ≠ j ) не содержали одинаковых элементов (М I ∩ М J = Ø ).

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

А	Б	...	Я
М А	М Б	...	М Я

Рис.4.1. Таблица шифрозамен

При шифровании каждая буква А открытого сообщения заменяется любым символом из множества М А . Если в сообщении содержится несколько букв А , то каждая из них заменяется на любой символ из М А . За счет этого с помощью одного ключа можно получить различные варианты шифрограммы для одного и того же открытого сообщения. Так как множества М А, М Б, ..., М Я попарно не пересекаются, то по каждому символу шифрограммы можно однозначно определить, какому множеству он принадлежит, и, следовательно, какую букву открытого сообщения он заменяет. Поэтому расшифрование возможно и открытое сообщение определяется единственным образом.

Приведенное выше описание сущности шифров замены относится ко всем их разновидностям за исключением , в которых для зашифрования разных символов исходного алфавита могут использоваться одинаковые шифрозамены (т.е. М I ∩ М J ≠ Ø , i ≠ j ).

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

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

Шифры замены можно разделить на следующие подклассы (разновидности).

Рис.4.2. Классификация шифров замены

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

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

Рис.4.4. Таблица шифрозамен для лозунгового шифра

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

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

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

Рис.4.5. Таблица шифрозамен для полибианского квадрата

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

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

№ п/п	Буква	Частота, %	№ п/п	Буква	Частота, %
1	О	10.97	18	Ь	1.74
2	Е	8.45	19	Г	1.70
3	А	8.01	20	З	1.65
4	И	7.35	21	Б	1.59
5	Н	6.70	22	Ч	1.44
6	Т	6.26	23	Й	1.21
7	С	5.47	24	Х	0.97
8	Р	4.73	25	Ж	0.94
9	В	4.54	26	Ш	0.73
10	Л	4.40	27	Ю	0.64
11	К	3.49	28	Ц	0.48
12	М	3.21	29	Щ	0.36
13	Д	2.98	30	Э	0.32
14	П	2.81	31	Ф	0.26
15	У	2.62	32	Ъ	0.04
16	Я	2.01	33	Ё	0.04
17	Ы	1.90

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

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

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

Полиграммные шифры замены - это шифры, в которых одна шифрозамена соответствует сразу нескольким символам исходного текста.

Биграммный шифр Порты . Шифр Порты, представленный им в виде таблицы, является первым известным биграммным шифром. Размер его таблицы составлял 20 х 20 ячеек; наверху горизонтально и слева вертикально записывался стандартный алфавит (в нем не было букв J, К, U, W, X и Z). В ячейках таблицы могли быть записаны любые числа, буквы или символы - сам Джованни Порта пользовался символами - при условии, что содержимое ни одной из ячеек не повторялось. Применительно к русскому языку таблица шифрозамен может выглядеть следующим образом.

	А	Б	В	Г	Д	Е (Ё)	Ж	З	И (Й)	К	Л	М	Н	О	П	Р	С	Т	У	Ф	Х	Ц	Ч	Ш	Щ	Ъ	Ы	Ь	Э	Ю	Я
А	001	002	003	004	005	006	007	008	009	010	011	012	013	014	015	016	017	018	019	020	021	022	023	024	025	026	027	028	029	030	031
Б	032	033	034	035	036	037	038	039	040	041	042	043	044	045	046	047	048	049	050	051	052	053	054	055	056	057	058	059	060	061	062
В	063	064	065	066	067	068	069	070	071	072	073	074	075	076	077	078	079	080	081	082	083	084	085	086	087	088	089	090	091	092	093
Г	094	095	096	097	098	099	100	101	102	103	104	105	106	107	108	109	110	111	112	113	114	115	116	117	118	119	120	121	122	123	124
Д	125	126	127	128	129	130	131	132	133	134	135	136	137	138	139	140	141	142	143	144	145	146	147	148	149	150	151	152	153	154	155
Е (Ё)	156	157	158	159	160	161	162	163	164	165	166	167	168	169	170	171	172	173	174	175	176	177	178	179	180	181	182	183	184	185	186
Ж	187	188	189	190	191	192	193	194	195	196	197	198	199	200	201	202	203	204	205	206	207	208	209	210	211	212	213	214	215	216	217
З	218	219	220	221	222	223	224	225	226	227	228	229	230	231	232	233	234	235	236	237	238	239	240	241	242	243	244	245	246	247	248
И (Й)	249	250	251	252	253	254	255	256	257	258	259	260	261	262	263	264	265	266	267	268	269	270	271	272	273	274	275	276	277	278	279
К	280	281	282	283	284	285	286	287	288	289	290	291	292	293	294	295	296	297	298	299	300	301	302	303	304	305	306	307	308	309	310
Л	311	312	313	314	315	316	317	318	319	320	321	322	323	324	325	326	327	328	329	330	331	332	333	334	335	336	337	338	339	340	341
М	342	343	344	345	346	347	348	349	350	351	352	353	354	355	356	357	358	359	360	361	362	363	364	365	366	367	368	369	370	371	372
Н	373	374	375	376	377	378	379	380	381	382	383	384	385	386	387	388	389	390	391	392	393	394	395	396	397	398	399	400	401	402	403
О	404	405	406	407	408	409	410	411	412	413	414	415	416	417	418	419	420	421	422	423	424	425	426	427	428	429	430	431	432	433	434
П	435	436	437	438	439	440	441	442	443	444	445	446	447	448	449	450	451	452	453	454	455	456	457	458	459	460	461	462	463	464	465
Р	466	467	468	469	470	471	472	473	474	475	476	477	478	479	480	481	482	483	484	485	486	487	488	489	490	491	492	493	494	495	496
С	497	498	499	500	501	502	503	504	505	506	507	508	509	510	511	512	513	514	515	516	517	518	519	520	521	522	523	524	525	526	527
Т	528	529	530	531	532	533	534	535	536	537	538	539	540	541	542	543	544	545	546	547	548	549	550	551	552	553	554	555	556	557	558
У	559	560	561	562	563	564	565	566	567	568	569	570	571	572	573	574	575	576	577	578	579	580	581	582	583	584	585	586	587	588	589
Ф	590	591	592	593	594	595	596	597	598	599	600	601	602	603	604	605	606	607	608	609	610	611	612	613	614	615	616	617	618	619	620
Х	621	622	623	624	625	626	627	628	629	630	631	632	633	634	635	636	637	638	639	640	641	642	643	644	645	646	647	648	649	650	651
Ц	652	653	654	655	656	657	658	659	660	661	662	663	664	665	666	667	668	669	670	671	672	673	674	675	676	677	678	679	680	681	682
Ч	683	684	685	686	687	688	689	690	691	692	693	694	695	696	697	698	699	700	701	702	703	704	705	706	707	708	709	710	711	712	713
Ш	714	715	716	717	718	719	720	721	722	723	724	725	726	727	728	729	730	731	732	733	734	735	736	737	738	739	740	741	742	743	744
Щ	745	746	747	748	749	750	751	752	753	754	755	756	757	758	759	760	761	762	763	764	765	766	767	768	769	770	771	772	773	774	775
Ъ	776	777	778	779	780	781	782	783	784	785	786	787	788	789	790	791	792	793	794	795	796	797	798	799	800	801	802	803	804	805	806
Ы	807	808	809	810	811	812	813	814	815	816	817	818	819	820	821	822	823	824	825	826	827	828	829	830	831	832	833	834	835	836	837
Ь	838	839	840	841	842	843	844	845	846	847	848	849	850	851	852	853	854	855	856	857	858	859	860	861	862	863	864	865	866	867	868
Э	869	870	871	872	873	874	875	876	877	878	879	880	881	882	883	884	885	886	887	888	889	890	891	892	893	894	895	896	897	898	899
Ю	900	901	902	903	904	905	906	907	908	909	910	911	912	913	914	915	916	917	918	919	920	921	922	923	924	925	926	927	928	929	930
Я	931	932	933	934	935	936	937	938	939	940	941	942	943	944	945	946	947	948	949	950	951	952	953	954	955	956	957	958	959	960	961

Рис.4.10. Таблица шифрозамен для шифра Порты

Шифрование выполняется парами букв исходного сообщения. Первая буква пары указывает на строку шифрозамены, вторая - на столбец. В случае нечетного количества букв в исходном сообщении к нему добавляется вспомогательный символ («пустой знак»). Например, исходное сообщение «АБ РА МО В», зашифрованное – «002 466 355 093». В качестве вспомогательного символа использована буква «Я».

Шифр Playfair (англ. «Честная игра»). В начале 1850-х гг. Чарлз Уитстон придумал так называемый «прямоугольный шифр». Леон Плейфер, близкий друг Уитстона, рассказал об этом шифре во время официального обеда в 1854 г. министру внутренних дел лорду Пальмерстону и принцу Альберту. А поскольку Плейфер был хорошо известен в военных и дипломатических кругах, то за творением Уитстона навечно закрепилось название «шифр Плейфера».

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

Шифр предусматривает шифрование пар символов (биграмм). Таким образом, этот шифр более устойчив к взлому по сравнению с шифром простой замены, так как затрудняется частотный анализ. Он может быть проведен, но не для 26 возможных символов (латинский алфавит), а для 26 х 26 = 676 возможных биграмм. Анализ частоты биграмм возможен, но является значительно более трудным и требует намного большего объема зашифрованного текста.

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

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

Рис.4.11. Ключевая таблица для шифра Playfair

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

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

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

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

Пример шифрования.

Биграмма «за» формирует прямоугольник – заменяется на «жб»;

Биграмма «ши» находятся в одном столбце – заменяется на «юе»;

Биграмма «фр» находятся в одной строке – заменяется на «хс»;

Биграмма «ов» формирует прямоугольник – заменяется на «йж»;

Биграмма «ан» находятся в одной строке – заменяется на «ба»;

Биграмма «но» формирует прямоугольник – заменяется на «ам»;

Биграмма «ес» формирует прямоугольник – заменяется на «гт»;

Биграмма «оя» формирует прямоугольник – заменяется на «ка»;

Биграмма «об» формирует прямоугольник – заменяется на «па»;

Биграмма «ще» формирует прямоугольник – заменяется на «шё»;

Биграмма «ни» формирует прямоугольник – заменяется на «ан»;

Биграмма «ея» формирует прямоугольник – заменяется на «ги».

Шифрограмма – «жб юе хс йж ба ам гт ка па шё ан ги».

Для расшифровки необходимо использовать инверсию этих правил, откидывая символы Я (или Х ), если они не несут смысла в исходном сообщении.

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

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

Рис.4.17. Таблица Трисемуса

Первая строка является одновременно и алфавитом для букв открытого текста. Первая буква текста шифруется по первой строке, вторая буква по второй и так далее. После использования последней строки вновь возвращаются к первой. Так сообщение «АБРАМОВ» приобретет вид «АВТГРУЗ».

Система шифрования Виженера. В 1586 г. французский дипломат Блез Виженер представил перед комиссией Генриха III описание простого, но довольно стойкого шифра, в основе которого лежит таблица Трисемуса.

Перед шифрованием выбирается ключ из символов алфавита. Сама процедура шифрования заключается в следующем. По i-ому символу открытого сообщения в первой строке определяется столбец, а по i-ому символу ключа в крайнем левом столбце – строка. На пересечении строки и столбца будет находиться i-ый символ, помещаемый в шифрограмму. Если длина ключа меньше сообщения, то он используется повторно. Например, исходное сообщение «АБРАМОВ», ключ – «ДЯДИНА», шифрограмма – «ДАФИЪОЁ».

Справедливости ради, следует отметить, что авторство данного шифра принадлежит итальянцу Джованни Батиста Беллазо, который описал его в 1553 г. История «проигнорировала важный факт и назвала шифр именем Виженера, несмотря на то, что он ничего не сделал для его создания» . Беллазо предложил называть секретное слово или фразу паролем (ит. password; фр. parole - слово).

В 1863 г. Фридрих Касиски опубликовал алгоритм атаки на этот шифр, хотя известны случаи его взлома шифра некоторыми опытными криптоаналитиками и ранее. В частности, в 1854 г. шифр был взломан изобретателем первой аналитической вычислительной машины Чарльзом Бэббиджем, хотя этот факт стал известен только в XX в., когда группа ученых разбирала вычисления и личные заметки Бэббиджа . Несмотря на это шифр Виженера имел репутацию исключительно стойкого к «ручному» взлому еще долгое время. Так, известный писатель и математик Чарльз Лютвидж Доджсон (Льюис Кэрролл) в своей статье «Алфавитный шифр», опубликованной в детском журнале в 1868 г., назвал шифр Виженера невзламываемым. В 1917 г. научно-популярный журнал «Scientific American» также отозвался о шифре Виженера, как о неподдающемся взлому .

Роторные машины. Идеи Альберти и Беллазо использовались при создании электромеханических роторных машин первой половины ХХ века. Некоторые из них использовались в разных странах вплоть до 1980-х годов. В большинстве из них использовались роторы (механические колеса), взаимное расположение которых определяло текущий алфавит шифрозамен, используемый для выполнения подстановки. Наиболее известной из роторных машин является немецкая машина времен Второй мировой войны «Энигма» .

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

Рис.4.19. Роторная система Энигмы [www.cryptomuseum.com ]

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

Рис.4.20. Схема шифрования

Примечание. Серыми линиями показаны другие возможные электрические цепи внутри каждого ротора. Буква A шифруется по-разному при последовательных нажатиях одной клавиши, сначала в G , затем в C . Сигнал идет по другому маршруту за счёт поворота одного из роторов после нажатия предыдущей буквы исходного сообщения.

3. Дайте характеристику разновидностям шифров замены.