Некоторые алгоритмы ручного шифрования (по материалам открытой печати)
Общество не может развиваться без производства и накопления информации, а также без обмена ею. В то же время всегда существовала необходимость ограничивать круг лиц, для которых предназначена конкретная информация. Поэтому и появилась криптография — наука о способах сокрытия информации от лиц, для которых она не предназначена. Фактически криптография является ровесницей письменности.
настоящее время криптографическая защита информации из тайнописи, доступной
лишь посвященным, превращается в общенародное достояние. Вследствие развития
информационных технологий и особенно в связи с широким распространением Интернета
защита конфиденциальной информации стала одной из актуальнейших задач современности.
До 60-70-х годов ХХ века криптография во всех странах находилась в ведении структур,
отвечающих за безопасность связи и информации. Развитие средств связи, таких
как телеграф, телефон, радио, обусловливало изменение характера криптографии,
а с применением электронных средств передачи информации задачи криптографии
усложнились и расширились. Широкое распространение компьютерных технологий стало
причиной того, что сфера действия криптографии видоизменилась и пополнилась
разного рода задачами, не связанными непосредственно с засекречиванием информации,
— это и разработка систем электронной цифровой подписи, протоколов выборов,
подписания контрактов, и идентификация удаленных пользователей; и появление
методов, позволяющих избежать получения ложных сообщений, и создание средств
защиты систем электронных платежей.
В настоящее время применение криптографических алгоритмов для закрытия информации уже не является особо сложной задачей. В процессе компьютерной обработки информация может подвергаться шифрованию несколько раз, причем не всегда с ведома создателя или потребителя этой информации. Однако до сих пор существует вероятность несанкционированного просмотра информации, обусловленная определенными недостатками алгоритмов шифрования. Поэтому даже в наши дни следует дополнительно позаботиться о конфиденциальности информации, например с помощью алгоритмов ручного шифрования, речь о которых пойдет ниже.
Любое повторное шифрование изменяет статистику исходного, так называемого открытого, текста, которую использует криптоаналитик для вскрытия шифра. Это может позволить повысить хотя бы временную стойкость передаваемой информации. Впервые понятие стойкости было сформулировано Антуаном Россиньолем, начальником шифровального отделения, созданного кардиналом Ришелье во Франции: «Стойкость военного шифра должна обеспечивать секретность в течение срока, необходимого для выполнения приказа. Стойкость дипломатического шифра должна обеспечивать секретность в течение нескольких десятков лет».
В исторических документах древних цивилизаций Индии, Египта, Месопотамии имеются сведения о системах и способах составления шифровального письма. В древнеиндийских рукописях изложены 64 способа преобразования текста, в частности написание знаков не по порядку, а по определенным правилам. Многие из таких способов можно рассматривать как криптографические. Более достоверные сведения о применяемых системах шифров относятся к периоду возникновения древнегреческих государств. Потребителями криптографии в этот период являлись структуры административной и религиозной власти. Плутарх сообщает, что жрецы хранили тексты прорицателей в зашифрованном виде. Э.Шюре в книге «Великие посвященные» пишет, что «с великим трудом и большой ценой добыл Платон один из манускриптов Пифагора, который никогда не записывал свое эзотерическое учение иначе, как тайными знаками и под различными символами». Там же отмечается, что Аристотель получил от Платона шифрованный текст Пифагора.
В период расцвета арабских государств (VIII век н.э.) криптография получила новое развитие. Да и само слово «шифр» арабского происхождения, как и «цифра». В 855 году появилась «Книга о большом стремлении человека разгадать загадки древней письменности», в которой приводится описание систем шифров, в том числе и с применением нескольких шифроалфавитов. В 1412 году была издана 14-томная энциклопедия, составителем которой являлся Шехаб аль-Кашканди. В данной энциклопедии содержится раздел о криптографии, где дано описание всех известных автору способов шифрования, а также упоминается о криптоанализе системы шифра, который основан на частотных характеристиках открытого и шифрованного текста. Приводится также частота встречаемости букв арабского языка на основе маркировки текста Корана.
Шифр простой замены, когда буквам алфавита ставятся в соответствие другие буквы того же алфавита, был известен до Рождества Христова. Так, в Спарте в V-VI веке до н.э. существовала хорошо развитая криптография. К этому же времени относится возникновение специального жезла для шифрования — «сцитала», применяемого для шифра перестановки.
Алгоритм шифрования следующий: на жезл наматывают ленту и пишут открытый текст вдоль палочки по намотанной ленте (в высоте жезла умещалось три буквы). На смотанной ленте получается шифротекст — удобно и быстро, что, кстати, в наши дни имеет большое значение. Толщина жезла и алфавит являются ключом шифра. Приведенный на рис. 1 открытый текст ВЫСТУПАЙТЕ, а соответствующий ему шифротекст ВУТЫПЕСАТЙ. Возможны разновидности шифров такого вида, заключающиеся в варьировании (изменении) числа букв, умещающихся по высоте и длине сцитала.
Аристотель (384 — 322 до н.э.), древнегреческий ученый, ученик Платона и учитель Александра Македонского, обладал почти всеми доступными в то время знаниями. В криптографии он известен как автор способа вскрытия шифра сцитала: не зная точного диаметра жезла, Аристотель наматывал зашифрованную ленту на коническую палку и перемещал ее по длине до тех пор, пока текст не начинал читаться.
Шифр древнегреческого историка Полибия (около 200 — около 120 до н.э.), или полибийский квадрат, имел следующий алгоритм шифрования. Квадрат размером 5Ѕ5 ячеек заполнялся случайным образом символами греческого алфавита. Заполнение квадрата и является ключом шифра. При шифровании берется буква, лежащая под буквой открытого текста. Если это буква нижней строки, то выбор осуществляется из верхней строки таблицы. При расшифровке — все наоборот: берется буква, расположенная строкой выше. Для приведенного на рис. 2 квадрата открытый текст audrou превращается в шифротекст xlsdbl.
Шифр Гая Юлия Цезаря (102 или 100 — 44 до н.э.), описанный в книге «Записки о галльской войне», является разновидностью шифра простой замены и построен по алгоритму: читать четвертую букву вместо первой. При открытом тексте VENI VIDI VICI (пришел, увидел, победил) при алфавите, состоящем из 26 букв, получается шифротекст SBKF SFAF SFZF (рис. 3). Алфавит замкнут на себя, то есть если при сдвиге не хватает букв слева, то смещение продолжается от крайнего правого знака (на рисунке переход показан красным цветом). Величина сдвига и сам алфавит являются ключом шифра. Из примера видно, что биграммные зависимости (зависимости рядом стоящих букв) сохраняются, поэтому для таких шифров легко найти соответствие. Как это сделать, очень талантливо описано в рассказе Эдгара По «Золотой жук».
Алгоритм шифра одиночной перестановки похож на алгоритм шифра сцитала, только запись открытого текста осуществляется не горизонтально, а вертикально. Ленту на жезле заменяет таблица, а ключом шифра является размер таблицы. Открытый текст НЕЯСНОЕ СТАНОВИТСЯ ЕЩЕ БОЛЕЕ НЕПОНЯТНЫМ превращается по таблице в шифротекст НОНСБНЯЕЕОЯОЕТЯСВЕЛПНСТИЩЕОЫНАТЕЕНМ при чтении по строкам (рис. 4).
Возможно также усложнение подобного шифра после добавления ключевого слова в первую строку таблицы и перестановки столбцов в соответствии с порядковыми номерами букв ключа (рис. 5).
После этого таблица становится такой, как показано на рис. 6, а шифротекст приобретает вид СНЯННБОЯЕТЕООЕЕПНЯВЛСЩОЫСИЕТЕНМНТЕА.
Если в ключевом слове встречаются одинаковые буквы, нумерация производится слева направо. Допускается повторное шифрование. При выборе размеров таблицы рекомендуется делать количество строк и столбцов взаимно простыми числами.
В алгоритме шифрования двойной перестановкой (строк и столбцов) ключами являются перестановки. Сначала, например, переставляются строки, затем столбцы. Средневековые ученые приписывали магическую силу квадратам, у которых сумма чисел по строкам и столбцам равнялась одному числу. Считая их волшебными, они пытались применить магические квадраты для шифрования данных (рис. 7).
Алгоритм шифрования, изображенный на рис. 8, заключается в перестановке символов открытого текста в соответствии с числами из магического квадрата. Для таблицы размерностью 3Ѕ3 существует один магический квадрат, для 4Ѕ4 — 880 различных магических квадратов, для 5Ѕ5 — 25 тыс. В этом смысле алгоритм шифрования не представляется удачным, так как все возможные комбинации легко перебрать. Тем не менее швейцарский математик, физик и астроном Леонард Эйлер (1707-1783), принимавший участие в разработке шифров в России, проводил исследования по перечислению и построению латинских квадратов, то есть шифров многоалфавитной замены.
Алгоритм шифра Гронсфельда (созданный в 1734 году бельгийцем Хосе де Бронкхором, графом де Гронсфельд, военным и дипломатом), является модификацией шифра Цезаря, заключающейся в том, что величина сдвига не является постоянной, а задается ключом (гаммой). При открытом тексте СОВЕРШЕННО СЕКРЕТНО и значениях ключа 3143143143143143143 получается шифротекст ФПЖИСЬИОССАХИЛФИУСС. Переходы некоторых букв открытого текста в буквы шифротекста при русском алфавите представлены на рис. 9. Такой способ шифрования также называется короткопериодической гаммой.
Шифр многоалфавитной замены предложен Леоном Батиста Альберти (1404-1472), итальянским ученым, архитектором, писателем и музыкантом, который в 1466 году представил в папскую канцелярию трактат о шифрах, где рассматривались различные способы шифрования, в том числе маскировка открытого текста в некотором вспомогательном тексте. Альберти изобрел, по его собственным словам, «шифр, достойный королей», — многоалфавитный шифр, реализованный в виде шифровального диска. Многоалфавитная замена может быть описана таблицей шифрования. Суть алгоритма шифрования заключается в том, что здесь используется несколько замен в соответствии с ключом. Позднее Альберти изобрел код с перешифровкой. Его изобретение значительно опередило свое время, поскольку такой тип шифра стал применяться в странах Европы спустя 400 лет. При входном открытом тексте (рис. 10) ПРИЕЗЖАЮ ШЕСТОГО и ключе шифрования АГАВААГАВААГАВАА алгоритм дает шифротекст ПНИГЗЖЮЮЮАЕОТМТО. Красным цветом выделены буквы, способ образования которых представлен на рисунке.
В начале XVI века Маттео Арженти, криптограф папской канцелярии, изобрел код, представляющий собой шифр замены, в котором заменяются буквы, слоги, слова и целые фразы. Необходимым количеством словарных величин в коде считалось 1200; в то же время появляется и числовой код. Дипломат Блез Виженер использовал идею алгоритма многоалфавитной замены для создания шифрующего устройства, состоящего из вращающихся колес.
В 1518 году в развитии криптографии был сделан новый шаг благодаря появлению в Германии первой печатной книги по криптографии. Аббат Иоганнес Трисемус, настоятель монастыря в Вюрцбурге, написал книгу «Полиграфия», в которой дается описание ряда шифров, один из которых развивает идею многоалфавитной замены. Шифрование осуществляется так: заготавливается таблица замены, где первая строка — это алфавит, вторая — алфавит, сдвинутый на один символ, и т.д. При шифровании первая буква открытого текста заменяется на букву, стоящую в первой строке, вторая — на букву, стоящую во второй строке, и т.д.
В 1553 году в Италии вышла небольшая книга «Шифр синьора Белазо». О ее авторе известно немного, но вклад его состоял в том, что он предложил использовать слово или группу слов, назвав это «паролем», выписывая его над (под) открытым текстом. Буква пароля означает номер применяемой замены к букве открытого текста.
Следующий шаг в развитии криптографии был сделан итальянцем Джованни Порта. В 1563 году он написал книгу «О тайной переписке», в которой дается описание биграммного шифра, основанного на замене пар букв. Порта предвосхитил то, что сегодня называют «методом вероятного слова», и привел примеры списков вероятных слов из различных областей. Примерно в это же время итальянский математик и философ Джераломо Кардано предложил использовать открытый текст в качестве ключа (книжная гамма).
При реализации в приложениях алгоритма лозунгового шифра, предложенного Трисемусом, с помощью языков, поддерживающих объектно-ориентированное программирование, можно создавать класс-наследник от класса, реализующего шифр Полибия. Различие между этими алгоритмами состоит в способе заполнения таблицы. В первой строке записывается лозунг (ключевое слово), о котором договариваются переписывающиеся стороны (размер таблицы также является ключом). Сначала в таблицу заносится лозунг (в данном случае РЕСПУБЛИКА), остальные ячейки таблицы заполняются по порядку оставшимися буквами алфавита. Для правильного заполнения достаточно знать лозунг, размер таблицы, алфавит. Шифрование и расшифровка производятся в соответствии с правилами алгоритма Полибия. Для открытого текста ОТПЛЫВАЕМ (в соответствии с таблицей на рис. 11) — шифротекст ШЩАДСНМИЦ (все переходы представлены на рисунке).
В XV-XVIII веках в математике были заложены основы аппарата, применяемого в криптографии для анализа шифров и дешифрования. Основным средством для шифрования становятся коды.
А теперь перейдем к не столь отдаленным временам. Известно, что главным шифросредством во время Первой мировой войны были коды, которых не удавалось сохранить в тайне, вследствие чего участники военных действий читали переписку друг друга. В полевых условиях применялись: решетка Кардано (Германия и Австро-Венгрия), шифр Плейфера (Великобритания), шифр двойной перестановки (Франция), шифр гаммирования цифровой гаммой (Россия). Результатом плохой организации шифросвязи стал разгром двух русских армий — Ранненкампа и Самсонова в Восточной Пруссии в августе 1914 года, когда русские войска были вынуждены связываться между собой по радио без всякого шифра.
Биграммный шифр (Playfair), применявшийся Великобританией, был основан на лозунговом способе заполнения шифротаблицы. Способ шифрования состоял в разбивке входного текста на биграммы. Переход от биграмм входного текста к биграммам выходного текста осуществляется по следующим правилам: если буквы входной биграммы оказались в одном столбце таблицы, шифрование и расшифровка происходит в соответствии с алгоритмом Полибия; если же буквы входной биграммы оказались в одной строке таблицы, то шифрование осуществляется слева направо, а дешифрование — наоборот. Буквы биграмм могут совпадать. Если буквы входной биграммы оказались в разных столбцах и строках таблицы, то рисуется воображаемый прямоугольник, а выходная биграмма берется как его альтернативные вершины. Для приведенной на рис. 12 таблицы открытый текст ПУ СТ ЬК ОН СУ ЛЫ БУ ДУ ТБ ДИ ТЕ ЛЬ НЫ, записанный без пробелов, имеет шифротекст УБ РХ ЫИ ДО ПБ КЩ РБ НР ШР ЖЛ ФР ИЩ ЗЮ (движение некоторых букв показано стрелками).
Первая мировая война преобразила криптографию, поскольку применение радиосвязи для управления войсками расширило возможности добычи шифротекстов противника. В этот период получили развитие методы дешифрования, основанные на парах открытых и шифрованных текстов, на шифротекстах, полученных на одном ключе, на использовании вероятных ключей. Криптографы часто использовали в качестве лозунгов пословицы, поговорки, патриотические призывы. У криптоаналитиков получили развитие вероятностно-статистические методы, использующие частоту знаков, биграмм, триграмм и т.д. Тогда же возникла и специализация в криптоаналитической деятельности: создавались особые группы и отделы по дешифрованию кодов и по дешифрованию полевых кодов, по добыче перехвата, по обработке информации, полученной из открытых и агентурных источников, и т.д.
Шифр «двойной квадрат», придуманный Чарльзом Уитсоном в 1854 году, активно применялся немцами во время Второй мировой войны (секретная переписка на уровне батальона). Алгоритм шифрования состоял в случайном заполнении двух таблиц символами алфавита, а сами таблицы являлись секретным ключом. При шифровании открытый текст разбивался на биграммы (рис. 13). Буквы биграммы разносились в разные квадраты, шифрование осуществлялось аналогично алгоритму биграммного шифра, только воображаемый прямоугольник строился между двумя таблицами (выделено серым цветом). Если буквы входной биграммы случайно оказывались в одинаковых строках таблиц, то буквы выходной биграммы выбирались в той же строке, но с противоположными номерами (отмечено красным и зеленым цветами соответственно). Посредством этого шифра открытый текст ПР ИЕ ЗЖ АЮ _Ш ЕС ТО ГО превращается в шифротекст ПЕ МВ КИ ФМ ЕШ РФ ЖБ ДЦ. Удобство этого алгоритма шифрования состоит в том, что размер алфавита ничем не ограничен, вследствие чего можно строить таблицы любых нужных для конкретного алфавита размеров.
Следует отметить, что хотя при анализе и создании шифров издавна использовались математические методы, только качественный скачок, произошедший в развитии прикладной математики в сороковые годы ХХ века, позволил говорить о криптографии как о науке.
Между мировыми войнами во всех ведущих странах появились электромеханические шифраторы. Они были двух типов — на коммутационных дисках (или роторах) и на цевочных дисках. Примером шифратора первого типа является известная шифромашина «Энигма», а второго типа — американская шифромашина М-209, распространяемая Б.Хагелином.
В период Второй мировой войны для секретной стратегической переписки немцы использовали шифратор «Энигма», изобретенный Эдвардом Хеберном в 1917 году. Это колесный шифратор. Секретными ключами являлись содержимое барабанов и их взаимное угловое расположение (рис. 14). На каждой стороне барабана располагалось 25 контактов, по числу букв в алфавите. Контакты с обеих сторон барабана попарно соединялись 25 проводами случайным образом. Перед началом работы барабаны устанавливались в ключевое слово, а при нажатии клавиши и кодировании очередного символа правый барабан поворачивался на один шаг. После того как он делал полный оборот, на один шаг поворачивался следующий барабан (как в счетчике). Таким образом получался ключ заведомо больший, чем текст сообщения.
«Энигма» состояла из четырех коммутационных дисков, а М-209 — из шести колес размера 26, 25, 23, 21, 19, 17, каждое из которых имело выступы по окружности. Такая шестимерная комбинация выступов (их число равно 64) с помощью механического устройства превращалась в число, на которое сдвигается буква открытого текста. Изменение угловых положений дисков осуществлялось их равномерным вращением. Таким образом шифратор реализовал шифр гаммирования. Советский Союз производил шифромашины обоих типов, а японцы использовали трехколесную шифромашину — «пурпурный ящик».
Перед Второй мировой войной все ведущие страны мира имели на вооружении электромеханические шифросистемы, обладавшие как высокой скоростью обработки информации, так и высокой стойкостью. Считалось, что данные системы невозможно дешифровать и что наступил конец успехам криптоаналитиков, однако впоследствии это мнение было опровергнуто. Все воюющие стороны достигли значительных успехов во взломе шифросистем противника, а шифровальные службы стали непосредственными участниками военных действий. Поучительная история дешифрования «Энигмы» описана у Д.Кана и у других авторов; теперь о драматических событиях того времени можно узнать из одноименного художественного фильма. Аналогичные успехи были и у других стран, например у американцев в отношении японцев.
Теоретическое открытие, оказавшее серьезное влияние на развитие криптографии, было сделано в работе американского инженера К.Шеннона «Теория связи в секретных системах», выполненной в 1945 году и опубликованной в 1949 году, и в работе советского ученого-радиотехника В.А.Котельникова «Основные положения автоматической шифровки» от 19 июня 1941 года. В данных работах были сформулированы и доказаны необходимые и достаточные условия недешифруемости системы шифра. Они заключаются в том, что получение противником шифротекста не изменяет вероятностей используемых ключей. При этом было установлено, что единственным недешифруемым шифром является так называемая лента одноразового использования, когда открытый текст шифруется с помощью случайного ключа такой же длины. Однако это делает абсолютно стойкий шифр очень дорогим в эксплуатации.
Ситуация складывается так, что в недалеком будущем знакомство с криптографией потребуется каждому пользователю электронных средств обмена информацией. Поэтому вскоре криптография станет «третьей грамотностью» — по аналогии со «второй грамотностью», как называют владение компьютером и информационными технологиями.
