Криптология: подстановочно-перестановочный шифр и его применение

Седьмая научная конференция молодых исследователей «Шаг в будущее, Москва» регистрационный номер информационная безопасность криптография: подстановочно - перестановочный шифр и его применениеАвтор: КалашниковАлексей Александрович, Школа№1959, 11 класс «А»Научный руководитель: Троицкий Игорь Иванович,доцент Кафедры«ИнформационнаяБезопасность»(ИУ-8), МГТУ им. Н. Э. Баумана,кандидат технических наук. Москва - 2004 Содержание:Появление шрифтов………………………….…..…….….стр.3Становление науки криптологии…………………………стр.3Криптология в новое время…………….…………...……..стр.12Шифр Цезаря……………………………….…………..…..стр.15 -Программный код………………………...……..…….стр.15Появление шифровРяд систем шифрования дошел до нас из глубокой древности. Скорее всего, онипоявились одновременно с письменностью в 4 тысячелетии до нашей эры. Методысекретной переписки были изобретены независимо во многих древних обществах,таких как Египет, Шумер и Китай, но детальное состояние криптологии в нихнеизвестно. Криптограммы выискиваются даже в древние времена, хотя из-заприменяемого в древнем мире идеографического письма в виде стилизованныхкартинок были примитивны. Шумеры, по-видимому, пользовались тайнописью.Археологами найдены глиняные клинописные таблички, где первая записьзамазывалась слоем глины, на котором делалась вторая запись. Происхождениетаких странных таблиц могло быть вызвано и тайнописью, и утилизацией.Оттого что число знаков идеографического письма было более тысячи, тозапоминание их представляло собой трудную задачу - тут не до шифрования.Тем не менее, коды, появившиеся вместе со словарями, были хорошо известны вВавилоне и Ассирии, а древние египтяне применяли, по меньшей мере, 3системы шифрования. С развитием фонетического письма письменность резкоупростилась. В древнем семитском алфавите во 2-м тысячелетии до нашей эрыбыло всего около 30 знаков. Ими обозначались согласные звуки, а такженекоторые гласные и слоги. Упрощение письма стимулировало развитиекриптографии. Даже в Библии можно найти примеры шифровок, хотя мало кто этозамечает. В книге пророка Иеремии (25,26) читаем: "...а царь Сессаха выпьетпосле них". Такого царя или царства не было - неужели ошибка писца? Нет,просто порой священные иудейские тексты шифровались простой заменой. Вместопервой буквы алфавита писалась последняя, вместо второй - предпоследняя итак далее. Этот древний метод шифрования назывался атбаш. Читая по немуслово СЕССАХ, на языке оригинала получаем слово ВАВИЛОН, и смыслбиблейского текста может быть принят даже не верящим слепо в истинностьписания. Вот что об этом сообщает Гай Светоний: "Существуют и его письма кЦицерону и письма к близким о домашних делах: в них, если нужно былосообщить что-нибудь негласно, он пользовался тайнописью, то есть менялбуквы так, чтобы из них не складывалось ни одного слова. Чтобы разобрать ипрочитать их, нужно читать всякий раз четвертую букву вместо первой,например, D вместо А и так далее". Это означает, что каждая буква шифровкизаменялась четвертой по счету от нее в алфавите: А-В-С-D, или D вместо А.Послание сенату VENI VIDI VICI, то есть ПРИШЕЛ, УВИДЕЛ, ПОБЕДИЛ, сделанноеЦезарем после однодневной войны с понтийским царем Фарнаком, выглядело бышифровкой SBKF SFAF SFZF. Принципиально иной шифр, более древний, связан с перестановкой буквсообщения по определенному, известному отправителю и получателю правилу.Древние рассказывали: какой-то хитрец из спартанцев обнаружил, что еслиполоску пергамента намотать спиралью на палочку и написать на нем вдольпалочки текст сообщения, то, после снятия полоски буквы на ней расположатсяхаотично. Это то же самое, будто буквы писать не подряд, а черезусловленное число по кольцу до тех пор, пока весь текст не будет исчерпан.Сообщение ВЫСТУПАЙТЕ при окружности палочки в 3 буквы даст шифровкуВУТЫПЕСАТЙ. Текст ее не понятен, не так ли? Для прочтения шифровки нужно не только знать системузасекречивания, но и обладать ключом в виде палочки, принятого диаметра.Зная тип шифра, но, не имея ключа, расшифровать сообщение было сложно. Этотшифр именовался скитала по названию стержня, на который наматывались свиткипапируса, что указывает на его происхождение. Он был весьма популярен вСпарте и много раз совершенствовался в позднейшие времена. О его важномзначении и большом распространении говорит свидетельство Плутарха в"Сравнительных жизнеописаниях", когда историк сообщает о жизни греческогополководца Алкивиада: "Однако Лисандр обратил внимание на эти слова нераньше, чем получил из дома скиталу с приказанием отделаться отАлкивиада..." Упомянем, что греческий писатель и историк Полибий изобрел за двавека до нашей эры так называемый полибианский квадрат размером 5х5,заполненный алфавитом в случайном порядке. Для шифрования на квадратенаходили букву текста и вставляли в шифровку нижнюю от нее в том жестолбце. Если буква была в нижней строке, то брали верхнюю из того жестолбца. Такого рода квадраты широко употреблялись в позднейшихкриптографических системах и будут детально описаны ниже.Приборы для шифрования тоже существовали с древних времен. Спарта, наиболеевоинственная из греческих государств, имела хорошо проработанную системусекретной военной связи еще в V веке до нашей эры. С помощью скитала,первого известного криптографического устройства, спартанские эфоры (эфоры- члены коллегиального правительства Спарты.) шифровали послания, используяметод простой перестановки. Ленивые и оттого юбретательные римляне в IVвеке до нашей эры, чтобы упростить процедуру шифрования, стали применятьшифрующие диски. Каждый из 2 дисков, помещенных на общую ось, содержал наободе алфавит в случайной последовательности. Найдя на одном диске буквутекста, с другого диска считывали соответствующую ей букву шифра. Такиеприборы, порождающие шифр простой замены. Использовались вплоть до эпохиВозрождения. Для связи греки и римляне использовали код на основеполибианского квадрата с естественным заполнением алфавитом. Буквакодировалась номером строки и столбца, соответствующим ей в квадрате.Сигнал подавался ночью факелами, а днем флагами. На основе такого кода легко сделать шифр, обозначив каждый ряд истолбец своим числом флагов. Очень вероятно, что подобные шифрыприменялись, но исторических свидетельств об этом нет. Окончим рассмотрениешифров древности, поскольку в небольшом числе приведенных примеровзаключено все многообразие классических подходов к шифрованию, подобнотому, будто в мельчайшей капле воды отражается весь мир. Становление науки криптологии В ручных шифрах того времени часто используются таблицы,которые дают простые шифрующие процедуры перестановки букв в сообщении.Ключом в них служат размер таблицы, фраза, задающая перестановку илиспециальная особенность таблиц. Простая перестановка без ключа - один изсамых простых методов шифрования, родственный шифру скитала. Например,сообщение НЕЯСНОЕ СТАНОВИТСЯ ЕЩЕ БОЛЕЕ НЕПОНЯТНЫМ записывается в таблицу постолбцам. Для таблицы из 5 строк и 7 столбцов это выглядит так: Н О Н С Б Н Я Е Е О Я О Е Т Я С В Е Л П Н С Т И Щ Е О Ы Н А Т Е Е Н М После того, как открытый текст записан колонками, для образованияшифровки он считывается по строкам. Если его записывать группами по 5 букв,то получится: НОНСБ НЯЕЕО ЯОЕТЯ СВЕЛП НСТИЩ ЕОЫНА ТЕЕНМ. Для использованияэтого шифра отправителю и получателю нужно договориться об общем ключе ввиде размера таблицы. Объединение букв в группы не входит в ключ шифра ииспользуется лишь для удобства записи несмыслового текста. Более практический метод шифрования, называемый одиночнойперестановкой по ключу очень похож на предыдущий. Он отличается лишь тем,что колонки таблицы переставляются по ключевому слову, фразе или наборучисел длиной в строку таблицы. Использовав в виде ключа слово ЛУНАТИК,получим такую таблицу. Л У Н А Т И К 4 7 5 1 6 2 3 Н О Н С Б Н Я Е Е О Я О Е Т Я С В Е Л П Н С Т И Щ Е О Ы Н А Т Е Е Н М до перестановки А И К Л Н Т У 1 2 3 4 5 6 7 С Н Я Н Н Б О Я Е Т Е О О Е Е П Н Я В Л С Щ О Ы С И Е Т Е Н М Н Т Е А после перестановки В верхней строке ее записан ключ, а номера под ключом определены поестественному порядку соответствующих букв ключа в алфавите. Если в ключевстретились бы одинаковые буквы, они бы нумеровались слева направо.Получается шифровка: СНЯНН БОЯЕТ ЕООЕЕ ПНЯВЛ СЩОЫС ИЕТЕН МНТЕА. Длядополнительной скрытности можно повторно шифровать сообщение, которое ужебыло зашифровано. Этот способ известен под названием двойная перестановка.Для этого размер второй таблицы подбирают так, чтобы длины ее строк истолбцов были другие, чем в первой таблице. Лучше всего, если они будутвзаимно простыми. Кроме того, в первой таблице можно переставлять столбцы,а во второй строки. Наконец, можно заполнять таблицу зигзагом, змейкой, поспирали или каким-то другим способом. Такие способы заполнения таблицы еслии не усиливают стойкость шифра, то делают процесс шифрования гораздо болеезанимательным. Кроме одиночных перестановок использовались еще двойныеперестановки столбцов и строк таблицы с сообщением. При этом перестановкиопределялись отдельно для столбцов и отдельно для строк. В таблицувписывался текст, и переставлялись столбцы, а потом строки. При расшифровкепорядок перестановок был обратный. Насколько просто выполнялось этошифрование, показывает следующий пример: 2 4 1 3 4 П P И Е 1 3 Ж а Ю 2 Ш Е С 3 Т О Г О исходная таблица 1 2 3 4 4 И П Е Р 1 а 3 Ю Ж 2 Е С Ш 3 Г Т О О перестановка столбцов 1 2 3 4 1 а 3 Ю Ж 2 Е С Ш 3 Г Т О О 4 И П Е Р перестановка строк Получается шифровка АЗЮЖЕ СШГТООИПЕР. Ключом к этому шифру служатномера столбцов 2413 и номера строк 4123 исходной таблицы. Число вариантовдвойной перестановки тоже велико: для таблицы 3х3 их 36, для 4х 4 их 576, адля 5 х 5 их уже 14400. Однако двойная перестановка очень слабый вид шифра,легко читаемый при любом размере таблицы шифрования. Выдающимся английским философом и изобретателем Роджером Бэконом,предвосхитившим многие позднейшие открытия (наиболее значительное из егоизобретений - очки, которые он предложил в 1268 году), был найден составчерного пороха. Так почему же традиционно считают его изобретателемБертольда Шварца, по преданиям казненного императором Венцеславом напороховой бочке? Карамзин по этому поводу писал: "Нет сомнения, что и монахРогер Бакон за 100 лет до Бертольда Шварца умел составлять порох: ибо ясноговорит в своем творении de nulitate Magiae о свойстве и силе оного". Делов том, что средневековые ученые, сделав открытие, отнюдь не всегда спешилиего опубликовать в письмах коллегам, как это было тогда принято приотсутствии периодических научных изданий. Нередко ту часть открытия,которую теперь называют know how, они шифровали анаграммой, переставляябуквы сообщения по известному только им ключу. Например, названия древней исовременной столиц Японии в русском написании тоже представляют собойанаграмму: КИОТО - ТОКИО. В упомянутом труде Бэкона состав пороха был приведен в видезашифрованной анаграммы, которую до появления сверхбыстродействующих ЭВМ неудавалось вскрыть, и слава открытия поэтому приписывалась Шварцу. Гораздоболее сложная проблема возникает с приписываемым Галилео Галилею открытиемспутников Юпитера. Долгое время приведенная им анаграмма читалась так:"Высочайшую планету двойною наблюдал", но в 1960-х годах с применениемкомпьютеров при расшифровке был получен иной вариант прочтения: "Приветвам, близнецы, Марса порождение!" Конечно, открытие Фобоса и Деймоса наслабеньком телескопе за два с половиной столетия до американца Асафа Холла- событие мало реальное, но кто знает? Описал же Свифт в "ПутешествияхГулливера" спутники Марса за полтораста лет до астрономов с поразительнойточностью! Может быть Свифт знал результаты Галилея, которые сейчаснеизвестны? Шифры перестановки чрезвычайно коварны в том смысле, что могутдать несколько вариантов осмысленного прочтения, если не знать точногозначения ключа. Какие же шифры применялись еще средневековыми учеными? На известнойгравюре Дюрера "Меланхолия" позади грустящего ангела изображен магическийквадрат, заполненный цифрами. Магическими квадратами называются квадратныетаблицы со вписанными в их клетки последовательными натуральными числами от1, которые дают в сумме по каждому столбцу, каждой строке и каждойдиагонали одно и то же число. Подобные квадраты широко применялись длявписывания шифруемого текста по приведенной в них нумерации. Если потомвыписать содержимое таблицы по строкам, то получалась шифровкаперестановкой букв. Считалось, что созданные с их помощью шифровки охраняетне только ключ, но и магическая сила. Вот пример магического квадрата и егошифровки: 16 3 2 13 5 10 11 8 9 6 7 12 4 15 14 1 О И Р Т З Ш Е Ю Ж А С Е Г О П Полученная из ПРИЕЗЖАЮ ШЕСТОГО, шифровка ОИРТЗШЕЮ ЖАСЕГОПпредставляется довольно основательной. На первый взгляд кажется, будтомагических квадратов очень мало. Тем не менее их число очень быстровозрастает с увеличением размера квадрата. Так, существует лишь одинмагический квадрат размером 3 х 3, если не принимать во внимание егоповороты. Магических квадратов 4 х 4 насчитывается уже 880, а числомагических квадратов размером 5 х 5 около 250000. Поэтому магическиеквадраты больших размеров могли быть хорошей основой для надежной системышифрования того времени, потому что ручной перебор всех вариантов ключа дляэтого шифра был немыслим. Широкое развитие торговли в средние века потребовало специфическихшифров, предельно простых и удобных, которыми могли бы пользоваться купцыдля передачи, например, даты приезда или цены товара. Это были простыешифры замены цифр на буквы, основанные на ключевом слове. Собственно, этокоды, а не шифры - вспомните обозначение месяцев на банках консервов, нокод, примененный единожды с неизвестной таблицей кодирования, схож посвойствам с шифром. Торговцы заранее договаривались использовать общееключевое слово, буквы которого соответствовали бы цифрам. Например, дляключа РЕСПУБЛИКА цифра 0 означает букву Р, цифра 1 означает Е, 2 - С, 3-Н итак далее. Поэтому, получив от корреспондента сообщение, ПРИБЫВАЮ ЕЛРПАС,они его читали, как ПРИБЫВАЮ 16/03/92. Простота и удобство этой системышифрования позволили ей дожить до начала этого века без всяких изменений. Другой шифр, обычно называемый шифром Гронсфельда, состоит вмодификации шифра Цезаря числовым ключом. Для этого под сообщением пишутключ. Если ключ короче сообщения, то его повторяют циклически. Шифровкуполучают будто в шифре Цезаря, но отсчитывая необязательно только третьюбукву по алфавиту, а ту, которая сдвинута на соответствующую цифру ключа.Так, применяя в качестве ключа группу из трех начальных цифр числа "пи", аименно 314, получаем шифровку: сообщение СОВЕРШЕННО СЕКРЕТНО ключ 3143143143143143143 шифровка ФПЖИСЬИОССАХИЛФИУСС Чтобы зашифровать первую букву сообщения С используя первую цифру ключа3, отсчитывается третья по порядку от С в алфавите буква С-Т-У-Ф иполучается буква шифровки Ф. Разновидность этого шифра была применена врезидентном англо-русском словаре, составленном студентами МВТУ, и взломкаего доставила слушателям лекций по программированию не меньше удовольствия,чем разгадывание кроссворда. Шифр Гронсфелвда имеет массу модификаций,претендующих на его улучшение, от курьезных, вроде записи текста шифровкибуквами другого алфавита, до нешуточных, как двойное шифрование разнымиключами. Кроме этих шифров, зачастую использовался шифр простой замены,заключающийся в замене каждой буквы сообщения на соответствующую ей буквушифра. Такой шифр, популярный среди школьников, является простым кодом ивскрытие его возможно при длине шифровки всего в 20-30 букв, а при длинахтекста свыше 100 символов представляет собой очень простую, но весьмаувлекательную задачу приведенную ниже. А сейчас рассмотрим рождение шифрасложной замены, шифры сложной замены называют многоалфавитными, так как дляшифрования каждого символа исходного сообщения применяется свой шифрпростой замены. Шифр Гронсфельда тоже многоалфавитный шифр (в нем 10вариантов замены), который используется по сей день. Архитекторы и исследователи Италии эпохи Возрождения считают, что одиниз самых важных этапов ренессансной архитектуры связан с именем ЛеонаБатиста Альберти, написавшем десять книг о зодчестве, построившим палаццоРучеллаи, церковь Иль Джезу и ряд других замечательных произведенийзодчества средневековой Италии. Будучи теоретиком искусства, он обобщилопыт гуманистической науки в изучении античного наследия, написав рядтрактатов: "О статуе", "О живописи", "О зодчестве". С другой стороны,криптологи всего мира почитают его отцом своей науки. Главным достижениемАльберти в криптологии было изобретение многоалфавитной замены, сделавшихшифровку очень устойчивой к вскрытию. Кроме самого шифра он еще подробноописал устройства из вращающихся колес для его реализации. Этот шифр можноописать таблицей шифрования, иногда называемой таблицей Виженера, по имениБлеза Виженера, дипломата XVI века, который развивал и совершенствовалкриптографические системы: АБВГДЕЖЗИКЛМНОПРСТУФХЦЧШЩЬЫЪЭЮЯ А АБВГДЕЖЗИКЛМНОПРСТУФХЦЧШЩЬЫЪЭЮЯ Б _АБВГДЕЖЗИКЛМНОПРСТУФХЦЧШЩЬЫЪЭЮЯ В Я_АБВГДЕЖЗИКЛМНОПРСТУФХЦЧШЩЬЫЪЭЮ Г ЮЯ_АБВГДЕЖЗИКЛМНОПРСТУФХЦЧШЩЬЫЪЭ ....... Я ВГДЕЖЗИКЛМНОПРСТУФХЦЧШЩЬЫЪЭЮЯ_АБ _ БВГДЕЖЗИКЛМНОПРСТУФХЦЧШЩЬЫЪЭЮЯ_А Каждая строка в этой таблице соответствует одному шифру замены вродешифра Юлия Цезаря для алфавита, дополненного пробелом. При шифрованиисообщения его выписывают в строку, а под ним ключ. Если ключ оказалсякороче сообщения, то его циклически повторяют. Шифровку получают, находясимвол в колонке таблицы по букве текста и строке, соответствующей буквеключа. Этот очень распространенный вид шифра сохранился до наших дней.Например, используя ключ АГАВА, из сообщения ПРИЕЗЖАЮ ШЕСТОГО получаемследующую шифровку: сообщение: ПРИЕЗЖАЮ ШЕСТОГО ключ: АГАВААГАВААГАВАА шифровка: ПНИГЗЖЮЮЮАЕОТМГО В компьютере такая операция соответствует сложению кодов ASCII символовсообщения и ключа по некоторому модулю. Кажется, что если таблица будетболее сложной, чем циклическое смещение строк, то шифр станет надежнее. Этодействительно так, если ее менять почаще, например, от слова к слову. Носоставление таких таблиц, представляющих собой латинские квадраты, гделюбая буква встречается в строке или столбце один раз, трудоемко и егостоит делать лишь на ЭВМ. Для ручного же многоалфавитного шифра полагаютсялишь на длину и сложность ключа, используя приведенную таблицу, которуюможно не держать в тайне, а это упрощает шифрование и расшифровывание.Итак, помимо ряда строений в античной манере, являющихся шедеврамиархитектуры итальянского Возрождения, Альберти еще ввел в практикукриптографии многоалфавитные шифры замены. Его книга "Трактат о шифре",написанная в 1466 году, представляла собой первый в мире научный труд покриптологии, если не считать арабских рукописей, с которыми Европа в этовремя вряд ли была хорошо знакома. Многие историки считают Иоганна Трисемуса, аббата из Германии, вторымотцом современной криптологии. В 1508 году Трисемус написал "Полиграфию",первую печатную работу по криптологии. В ней он первым систематическиописал применение шифрующих таблиц, заполненных алфавитом в случайномпорядке. Для получения такого шифра обычно использовались ключевое словоили фраза и таблица, которая для русского языка может иметь размер 5 х 6.Ключевое слово вписывалось в таблицу по строкам, а повторяющиеся буквыотбрасывались. Таблица дозаполнялась не вошедшими в нее буквами алфавита попорядку. Поскольку ключевое слово легко хранить в памяти, то такой подходупрощал процессы шифрования и дешифрования. Для ключа РЕСПУБЛИКА таблицабудет иметь следующий вид: Р Е С П У Б Л И К А В Г Д Ж 3 М Н О Т Ф Х Ц Ч Ш Щ Ь Ы Э Ю Я Для описанного выше шифра Полибия с данной таблицей сообщение ОТПЛЫВАЕМдавало шифровку ШЩАДСНМИЦ. Такие табличные шифры называются монограммными,так как шифрование ведется по одной букве. Трисемус первым заметил, чтоможно шифровать по две буквы за раз. Такие шифры были названы биграммными.Наиболее известный шифр биграммами называется Playfair. Он применялсяВеликобританией в Первую мировую войну. Опишем его на примере той же самойтаблицы. Открытый текст разбивался на пары букв (биграммы) и текст шифровкистроился из него по следующим двум очень простым правилам. 1. Если обе буквы биграммы исходного текста принадлежали одной колонке таблицы, то буквами шифра считались буквы, которые лежали под ними. Так биграмма УН давала текст шифровки ВЧ. Если буква открытого текста находилась в нижнем ряду, то для шифра бралась соответствующая буква из верхнего ряда и биграмма ОЯ давала шифр ШБ. (Биграмма из одной буквы или пары одинаковых букв тоже подчинялась этому правилу и текст ЕЕ давал шифр ИИ). 2. Если обе буквы биграммы исходного текста принадлежали одной строке таблицы, то буквами шифра считались буквы, которые лежали справа от них. Так биграмма ИВ давала текст шифровки КГ. Если буква открытого текста находилась в правой колонке, то для шифра бралась соответствующая буква из левой колонки и биграмма ОМ давала шифр ДН. Если обе буквы биграммы открытого текста лежали в разных рядах иколонках, то вместо них брались такие две буквы, чтобы вся четверка ихпредставляла прямоугольник. При этом последовательность букв в шифре былазеркальной исходной паре. Например, СТ шифровалось как РХ, а ТБ шифровалоськак ШР. При шифровании фразы ПУСТЬ КОНСУЛЫ БУДУТ БДИТЕЛЬНЫ по биграммамполучается такая шифровка: ПУ СТ ЬК ОН СУ ЛЫ БУ ДУ ТБ ДИ ТЕ ЛЬ НЫ УБ РХ ЫИ ДО ПБ КЩ РБ HP ШР ЖЛ ФР ИЩ ЗЮ Шифрование биграммами резко усилило стойкость шифров к вскрытию. Привсем при том, что "Полиграфия" была довольно доступной печатной книгой,описанные в ней идеи получили признание лишь тремя веками позже. Скореевсего, это вызвано плохой известностью среди криптографов Трисемуса,который слыл богословом, библиофилом и основателем архивного дела. Средишифров средневековья встречается много курьезов. Леонардо да Винчи шифровалбольшинство своих личных записей. Самый простой вид шифра, которым онпользовался, это обратное написание текста так, что прочесть его можно лишьв отражении зеркала. Однако Леонардо иногда использовал шифры ипосерьезнее, поэтому далеко не все его заметки и записи расшифрованы иизучены. Люди, умеющие писать левой рукой справа налево зеркальный текст,нередки. Изумительно, но встречаются люди, которые умеют даже произноситьфразы "наоборот" и понимать их на слух. Поистине, человеческим способностямнет и не будет предела. В средние века появляются профессиональные и дажепотомственные криптографы, вроде семейства Ардженти, служившего у папыРимского. Тем не менее папы Римские сами не чуждались услуг криптографов ивыдающийся итальянский математик Джироламо Кардано, имя которого дошло донас благодаря изобретенному им шарнирному механизму и первой публикации ометоде решения уравнений третьей степени, состоял у них на службе. Его перупринадлежит несколько книг по криптографии и описание метода трафаретов,который будет рассмотрен ниже. Если учесть род занятий Кардано, становитсяпонятным, почему, выведя гороскоп Христа, он остался недоступныминквизиции, сжегшей Бруно и судившей Галилея за куда меньшую ересь: эка,невидаль, что Земля вертится! Жизнь и смерть Джироламо полны легенд. Большевсего современников в Кардано поражал дар предвидения, благодаря которомуон безмятежно перенес казнь своего сына и потерю крупного состояния.Вероятно, хотя бы отчасти его мистический талант знать будущее объясняетсяпринадлежностью к криптографической службе, знающей все, что можно узнать.Но вот, предсказав продолжительность своей жизни в 75 лет, он в назначенныйгод покончил самоубийством, оставив записку: "Если и неверно, то неплохопридумано". Увлечение теорией магических квадратов привело Кардано коткрытию нового класса шифров перестановок, названных решетками илитрафаретами. Они представляют собой квадратные таблицы, где четверть ячеекпрорезана так, что при четырех поворотах они покрывают весь квадрат.Вписывание в прорезанные ячейки текста и повороты решетки продолжаются дотех пор, пока весь квадрат не будет заполнен. Например, на рисунке нижепоказан процесс шифровки решеткой 4 х 4. Черными квадратами обозначенынепрорезанные ячейки, а повороты осуществляются по часовой стрелке науказанный ниже угол: В результате получается шифровка ЗТП ОЖШРЕИГАЕСЮО. Число подобныхрешеток быстро растет с их размером. Так, решетка 2 х 2 единственна,решеток 4 х 4 уже 256, а решеток размером 6 х 6 свыше ста тысяч. Несмотряна кажущуюся сложность, шифры типа решеток довольно просто вскрываются и немогут использоваться в виде самостоятельного шифра. Однако они очень удобныи еще долго использовались в практике для усиления шифров замены. Один мойзнакомый, остановившись при чтении рукописи книги на этом месте, попыталсявысказать сомнение в том, что шифры подобного рода легко вскрываются.Поскольку это глубоко ошибочное и обидное для криптологов мнение широкораспространилось из популярных математических книг или иных источниковдезинформации, то в следующей главе специально приведен пример вскрытияшифровки, сделанной этой решеткой. В Англии XVII века возглавлял криптографическую службу математик ДжонВаллис, основавший исчисление бесконечно малых, но получивший научноепризнание и профессуру в Оксфорде не за химерические бесконечно малые, а заредкостные успехи в расшифровке. В Германии же лучшим криптографом тогдабыл Лейбниц, основатель Берлинской академии наук, языковед и математик,один из создателей дифференциального исчисления, к имени которого мы ещевернемся позже в связи с развитием криптографии в России. Одно время еговысокий покровитель, ганноверский курфюрст Георг1, став королем Англии,хотел пригласить Лейбница на британскую криптографическую службу, но Валлисбыл там незаменим и утечка континентальных "мозгов" на запад не состоялась.Лейбницу не подфартило стать главным криптографом Англии может быть ипотому, что Ньютон, оспаривающий его авторство в дифференциальномисчислении, единолично заправлял в Королевском научном обществе и изо всехсил преследовал менее именитого иностранного конкурента. Другой разЛейбницу не повезло с приглашением в Петербург для организации русскойкриптографической службы. Неожиданная его болезнь и смерть расстроили планыПетра 1, активно вербовавшего нужных России ученых. Человеком, сумевшимзавершить развитие криптографии в отдельную научную дисциплину, стал, по-видимому, однофамилец Роджера Бэкона - Френсис Бэкон. Будучи лорд-канцлером, при короле Якове 1, он хорошо знал потребности государства внадежных шифрах, и его первая талантливая работа, относящаяся к 1580 году,в дальнейшем получила блестящее практическое развитие. В частности, именноон впервые предложил двоичное кодирование букв латинского алфавита - то жесамое, которое используется сейчас в компьютерах. Такой заботливый уход за пустившей первые ростки криптографией привел ктому, что она скоро стала давать плоды. Разгром Великой Армады в 1588 годув значительной степени был обусловлен мощью английской криптографическойшколы, легко ломавшей испанские шифры и сообщавшей о всех передвиженияхнеприятельских судов. Криптография была известна и применялась во многихслоях общества Британии. Лондонец Самуэль Пепис (1633-1703) всемирноизвестен своим дневником, по которому историки пишут труды о переходе отПуританства к Реставрации. Искусствоведы включили это произведение вмировую сокровищницу литературы. Пепис окончил Кембридж благодаря кузенуотца - адмиралу Монтегю и имел много друзей: ученого Исаака Ньютона,архитектора Кристофера Рена, поэта и драматурга Джона Драйдена. Пепис быллично свидетелем таких незабываемых для Англии событий, как возвращениекороля Чарльза II в Англию, большая чума 1664 года, пожар Лондона 1666года, революция 1688 года. Интересно, что его мемуары были зашифрованы посистеме криптолога Томаса Шелтона и дополнительно собственным шифромПеписа, поскольку содержали много скандальных фактов о великихсовременниках. Вместе с его личными книгами и бумагами дневник после смертиписателя попал в Кембридж, где сразу же привлек внимание исследователей.Первый успех в его расшифровке был получен лишь в 1822 году, а полностьюона завершена в 1899 году. Таким образом, к XVIII веку криптографияокончательно сложилась в виде самостоятельной науки. Однако, несмотря наналичие профессиональных криптологов, находящихся на государственнойслужбе, и постоянного использования шифров в дипломатии и военном деле,криптология еще не вышла из младенческого возраста и ею могли заниматьсялишь избранные, одаренные одиночки. Криптология в Новое время Новое время привнесло новые достижения в криптографию. Постояннорасширяющееся применение шифров выдвинуло новое требование к ним - легкостьмассового использования, а старое требование - устойчивость к взлому нетолько осталось, но и было усилено. Поэтому 1854 год, когда англичанинЧарльз Уитстон разработал новую шифровку биграммами, которую называютдвойной квадрат, открыл новый этап в криптографии. Название шифр получил поаналогии с полибианским квадратом. В отличие от полибиаиского, двойнойквадрат использует сразу две таблицы, расположенные по горизонтали, ашифрование идет биграммами, как в шифре Playfair. Эти, казалось бы и нестоль уж значительные изменения привели к появлению на свет новойкриптографической системы ручного шифрования. Она оказалась так надежна иудобна, что применялась немцами даже в годы Второй мировой войны. По отзывуее создателя, шифрование двойным квадратом предельно просто и его "можнодоверить даже дипломатам". Приведем пример использования шифра двойнойквадрат для русских текстов. Имеются две таблицы со случайно расположеннымив них алфавитами:Ч В Ы ПО К : Д УГ Ш 3 Э ФЛ Ъ Х А ,Ю Р Ж Щ НЦ Б И Т Ь. С Я М ЕЕ Л Ц : П. Х Ъ А НШ Д Э К СЫ Б Ф УЯ Т И Ч ГМ О , Ж ЬВ Щ 3 Ю Р Для шифрования сообщение разбивают на биграммы. Первая буква биграммынаходится в левой таблице, а вторая в правой. Затем, мысленно в таблицестроится прямоугольник так, чтобы буквы биграммы лежали в егопротивоположных вершинах. Другие две вершины этого прямоугольника даютбуквы шифровки. Предположим, что шифруется биграмма текста ОЖ. Буква Онаходится в колонке 1 строки 2 левой таблицы. Буква Ж находится в колонке 4строки 6 правой таблицы. Значит, прямоугольник образован строками 2 и 6, атакже колонками 1 левой и 4 правой таблиц. Следовательно, шифровкесоответствуют буквы, лежащие в колонке 1 строки 6 левой таблицы Ц и вколонке 4 строки 2 правой таблицы А - биграмма АЦ. Так парами буквшифруется все сообщение: Сообщение: ПР ИЕ ЗЖ АЮ Ш ЕС ТО ГО Шифровка : ПЕ МБ КИ ФМ ЕШ РФ ЖБ ДЦ ЩП Если обе буквы биграммы сообщения лежат в одной строке, то и буквышифровки берутся из этой же строки. Первая буква биграммы шифровки беретсяиз левой таблицы в столбце, соответствующем второй букве биграммысообщения. Вторая же буква биграммы шифровки берется из правой таблицы встолбце, соответствующем первой букве биграммы сообщения. Так, поприведенным выше таблицам биграмма сообщения ТО превращается в биграммушифровки ЖБ. Несомненно, что шифрование биграммами дает весьма устойчивый квскрытию и простой шифр, а это было в то время крупным успехом. Взломшифровки двойного квадрата требует больших усилий и длины сообщения болеетридцати строк. Во второй половине XIX века появляется множество работ по вскрытиюсложных шифров замены для конкретных условий, при использованииповторяющегося короткого ключа, при шифровке нескольких сообщений однимключом. Тогда же в Англии и США стали выходить периодические издания,посвященные вопросам криптоанализа, где профессионалы и любители,обмениваясь опытом, предлагали новые типы шифров и анализировали ихстойкость к взлому. Возможно, одного из самых больших успехов XX векакриптоаналитика добилась, когда Британская морская разведка в начале 1917года передала правительству США текст секретной расшифрованной телеграммы(телеграмма была перехвачена с трансатлантического кабеля.) , известной какпослание Циммермана, бывшего министром иностранных дел Германии. В нейнемецкому послу в Мексике предлагалось заключить союз, чтобы Мексиказахватила американские штаты Техас, Нью-Мехико и Аризону. Эта телеграмма,произвела эффект взрыва и, считают сейчас историки, стала главным поводомдля вступления США в Первую мировую войну против Германии, обеспечив ееразгром. Так криптография впервые серьезно заявила о своей исключительнобольшой значимости в современном мире. XIX век с расширением связных коммуникаций занялся автоматизациейпроцесса шифрования. Появился телеграф, нужно шифровать и его. Любопытно,что цифровое шифрующее колесо было изобретено госсекретарем ТомасомДжефферсоном в 1790 году, ставшим потом третьим президентом США. Похожиешифрующие устройства применялись армией США и после Второй мировой войны.Принцип работы таких машин, очень похожих на арифмометры, заключается вмногоалфавитной замене текста сообщения по длинному ключу. Длина периодаключа определялась наименьшим общим кратным периодов оборотов шифрующихколес. При 4 колесах и периодах их оборотов 13, 15, 17 и 19 получаласьбольшая длина периода ключа 62985, очень затрудняющая расшифровку короткихсообщений. Гораздо более примитивный прибор, цилиндр Базери, был предложенЭтьеном Базери в 1891 году. Он состоял из 20 дисков со случайно нанесеннымпо ободу алфавитом. Перед началом шифрования диски помешались на общую осьв порядке, определяемым ключом. Набрав первые 20 букв текста в ряд нацилиндрах их поворачивали вместе и считывали в другом ряду шифрованноесообщение. Процесс повторялся, пока все сообщение не было зашифровано.Однако первая практически используемая криптографическая машина былапредложена Жильбером Вернамом лишь в 1917 году. Применение машин вкриптографии расширялось, что привело к созданию частных фирм, занимающихсяих серийным выпуском. Шифровальная аппаратура создавалась в Германии,Японии, США и ряде других развитых стран. Предшественницей современныхкриптографических машин была роторная машина, изобретенная ЭдвардомХеберном в 1917 году и названная впоследствии Энигмой (Слово enigmaпереводится как загадка, Промышленные образцы этой машины изготовляла фирмаSiemens.). Независимая промышленная ее версия создана чуть позже берлинскиминженером Артуром Кирхом (некоторые источники называют его АртуромШербиусом). Она сначала Представляла собой 4 вращающихся на одной осибарабана, обеспечивающих более миллиона вариантов шифра простой замены,определяемого текущим положением барабанов. На каждой стороне барабана поокружности располагалось 25 электрических контактов, столько же, сколькобукв в алфавите. Контакты с обеих сторон барабана соединялись попарнослучайным образом 25 проводами, формировавшими замену символов. Колесаскладывались вместе и их контакты, касаясь друг друга, обеспечивалипрохождение электрических импульсов сквозь весь пакет колес. Перед началомработы барабаны поворачивались так, чтобы устанавливалось заданное кодовоеслово - ключ, а при нажатии клавиши и кодировании очередного символа правыйбарабан поворачивался на один шаг. После того, как он делал оборот, на одиншаг поворачивался следующий барабан - будто бы в счетчике электроэнергии.Таким образом, получался ключ заведомо гораздо более длинный, чем текстсообщения. Например, в первом правом барабане провод от контакта, соответствующегобукве U, присоединен к контакту буквы F на другой его стороне. Если жебарабан поворачивался на один шаг, то этот же провод соответствовал заменеследующей за U буквы V на следующую за F букву G. Так как барабанысоприкасались контактами, то электрический импульс от нажатой клавиши сбуквой исходного текста, прежде чем достигал выхода претерпевал 4 замены:по одной в каждом барабане. Для затруднения расшифрования барабаны день отодня переставлялись местами или менялись. Дальнейшее усовершенствование этоймашины сделало движение барабанов хаотичным, а число их увеличилось сначаладо 5, а потом до 6. Все устройство могло поместиться в портфеле и было такпросто, что обслуживалось обычными связистами. Казалось бы, сделано все для невозможности вскрытия шифровок Энигмы. Ивсе же английские криптографические службы в Блетчли Парке (уединенноепоместье в 80 километрах севернее Лондона, отведенное британскимкриптологам.) почти всю войну читали немецкие шифры. Это стало возможнымлишь благодаря польской разведке, которая к злополучному 1939 году смоглаполучить чертежи Энигмы и разобраться в ее устройстве. После нападениягитлеровцев на Польшу чертежи немецкой шифровальной машины были переданыАнглии. Довольно быстро британские криптоаналитики установили, что длявзлома шифра, нужно знать распайку проводов в шифрующих колесах. Началасьохота британских спецслужб за образцами Энигмы. Первый удалось выкрастьпрямо с завода на юго-востоке Германии, второй сняли со сбитого в небеНорвегии немецкого бомбардировщика, третий был найден во время боев заФранцию у немецких военных связистов, взятых в плен. Остальные Энигмы снятыводолазами с немецких подводных лодок, за которыми специально сталиохотиться и топить на малых глубинах. Взлом шифров Энигмы шел тяжело до техпор, пока в 1942 году не вступили в строй несколько ЭВМ, специальносозданных для этого Аланом Тьюрингом. Это была первая в мире довольнобыстродействующая ЭВМ под названием "Колосс", специализированная для взломашифров. После этого английские криптоаналитики могли меньше чем за деньмогли расколоть любую шифровку Энигмы, полученную добытыми ранее колесами,методично перебирая все возможные ключи. Немцы рассчитывали на сложностьсвоего шифра, исходя из его ручной дешифровки, в то время как англичанестали его ломать, используя ЭВМ. Отметим, что сами немцы допускаливозможность взлома шифра Энигмы. Еще в 1930 году ведущий немецкийкриптоаналитик Георг Шредер продемонстрировал такую возможность, едкозаметив при этом: "Энигма - дерьмо!" Однако она постоянно усложнялась ибыли периоды, когда в Блетчли Парке с ней не могли справиться. Передшифровками Энигмы, которые исходили не от войск, а из немецкихкриптографических центров, "Колосс" тоже был бессилен. Высокое развитие криптографической техники стран западных союзников взначительной степени предопределило ход многих боевых операций во времяВторой мировой войны. Англия, хоть и несла на море большие потери, нопрактически подавляла любые организованные действия немецкого флота,перехватывая и читая приказы гроссадмиралов Редера и Деница. В книгахвоспоминаний английских криптографов страницы сплошь усеяны фразами "...мызнали...", за которыми стоит колоссальный труд тысяч человек. Шифр Цезаря Гай Юлий Цезарь, римский император, в то же время, известен какизобретатель (не могу сказать "разработчик") своего шифра, поручавшегоМарку Туллию Цицерону и своим близким шифровать послания и использовать 50-буквенный алфавит. Цитирую Гая Светония: "Существуют и его письма к Цицерону и письма кблизким о домашних делах: в них, если нужно было сообщить что-нибудьнегласно, он пользовался тайнописью, то есть менял буквы так, чтобы из нихне складывалось ни одного слова. Чтобы разобрать и прочитать их, нужночитать всякий раз четвертую букву вместо первой, например, D вместо А и такдалее". Выражаясь современной терминологией, номер каждого символа пришифровании увеличивался на 3: А на D, B на E и т.д. Знаменитая фраза ЦезаряVENI VIDI VICI (пришел, увидел, победил), посланная сенату послеоднодневной войны с Фарнаком, царем Понта, после зашифровки превратилось быв SBKF SFAF SFZF. Для уточнения стоит отметить, что Гай Светоний ошибался,давая этому методу название тайнописи. Тайнопись - это сокрытие самогофакта передачи сообщения, изложенное Светонием называется, в современнойтерминологии, шифром однозначной замены. Криптоалгоритм будет реализован на ASCII-таблице. Для корректнойреализации шифра еще потребуется нормализация, проводимая для того, чтобымножества совпадали и, естественно, размеры множеств открытого ишифротекста были равны (т.н. гомоморфизм). Для этого делается следующее:если сумма текущего номера и тройки выходит за пределы алфавита (размерамножества разрешенных символов), то отсчет букв начинается сначала. Программный код для шифрования текстовых сообщений по принципу«шифра Цезаря» на языке программирования Visual Basic Пусть kk = 3 и кодируемой фразой будет «i remember that September».Будем использовать латинские буквы со стандартным следованием букв валфавите. Результаты шифрования указанной выше фразы показаны ниже втаблице: Private Sub Command2_Click()EndEnd Sub Запустим программу на выполнение. Наберем число 3 в текстовом окне«Введите сдвиг», а в окне «Введите фразу»: i remember that September. Наборпроводим строчными буквами, поскольку работа с прописными буквами впрограмме не предусмотрена. Проверив состояние контрольного индикатора(Кодирование), закодируем набранную фразу, щелкнув по кнопке «Обработатьфразу». Результатом кодирования будет lcuhphpehucwkdwcvhswhpehu, рис. 2.Можно убедиться, что он совпадает с «найденным теоретически». Декодируем полученную шифровку. Для этого перенесем зашифрованнуюфразу lcuhphpehucwkdwcvhswhpehu из окна «Результат» в окно «Введите фразу»и изменим состояние контрольного индикатора (уберем флажок). Снова щелкнемпо кнопке «Обработать фразу» и в окне «Результат» появится исходная фраза iremember that September, рис. 3. Теперь можно зашифровать ту же фразу для другого значения сдвига,пусть например kk = 5. Результат кодирования представлен на рис. 4. [pic] Рис. 3. [pic] Рис. 4. Несмотря на простоту шифра Цезаря, шифровки Цезаря при его жизни ниразу не были декодированы его многочисленными врагами. Это объясняется,скорее всего, тем, что Цезарь применял не современную стандартнуюпоследовательность букв в латинском алфавите, а свою собственную, которуюон хранил в глубокой тайне. В дальнейшем можно увеличить сложность этой программы путемзамены ключа выбираемого пользователем, ключом, определяемым программой(генератором псевдослучайных чисел), что усложнит работу аналитика .Список использованной литературы: 1. Ж . Брассар «Современная криптология», изд. «Полимед», 1999г. 2. Библия , изд. «Московская патриархия», 1998 г. 3. Учебник по программированию «Visual basic 6.0», изд. «Эком», 2002г. 4. Н. Г. Волчёнков программирование на «Visual basic 6.0», изд. Инфра- м, 2002 г.-----------------------**П* З*** *** *Т** ЗТП***Р *Ж** **Ш* О*** ОЖШР *И** ***А Е*****Г* ЕИГАЕ*** **Ю* *C** ***О ЕСЮО 0' 90' 180' 270' шифp