Главная  >  Политика   >  Российская власть   >  Спецслужбы   >  Техника спецслужб


Криптографические идеи XIX века

11 октября 2007, 320

В 1817 году полковник американской армии, начальник артиллерийско-технической службы армии США Д. Уодсворт предложил оригинальное устройство – механический шифратор. В предложении Уодсворта просматриваются идеи Энея (замена букв на расстояние).

Шифратор Уодсворта. В 1817 году полковник американской армии, начальник артиллерийско-технической службы армии США Д. Уодсворт предложил оригинальное устройство – механический шифратор. Схема шифратора приведено на рисунке.

Основные элементы устройства – два шифровальных диска. На торце первого из них (2), реализующего алфавит открытого текста, в алфавитном порядке расположены 26 букв английского алфавита. На втором диске с алфавитом шифрованного текста в произвольном порядке располагались эти же буквы и цифры от 2 до 8. Таким образом, он содержал 33 знака. Литеры на диске – съемные, что позволяло менять алфавит шифрованного текста. Диски соединены между собой шестеренчатой передачей с числом зубьев 26?33. При перемещении первого диска (с помощью кнопки) на один шаг второй диск перемещается также на один шаг в другую сторону. Поскольку числа 26 и 33 взаимно просты, то при пошаговом вращении первого диска оба диска приходят в исходное состояние через 26?33 = 858 шагов. Диск открытого текста вращался только в одну сторону. Диски помещались в футляр, в котором были прорезаны окна (5). С помощью специальной кнопки (6) шестерни разъединялись, что позволяло независимо друг от друга перемещать диски в начальное для шифрования положение (с помощью кнопок 7 и 8). Долговременным ключом является алфавит шифрованного текста (их количество 33!); разовый ключ состоял из двух букв (верхнего и нижнего диска) и устанавливался в окнах при независимом повороте дисков. Количество разовых ключей: 26?33 = 858.

На рисунке изображен разовый ключ LB. Шифрование производилось следующим образом. Перед началом шифрования диски ставились в начальные условные положения (LB). Затем шестерни соединялись, и с помощью кнопки 2 диск поворачивался до тех пор, пока в верхнем окне не появлялась первая буква открытого текста. С окна под ним списывалась первая буква шифрованного текста. Остальные буквы шифровались аналогичным образом. Если буквы повторялись (например, АА), то диск совершал полный оборот, поэтому в шифртексте этой паре соответствовала пара из различных знаков (например, 8В).

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

Отметим следующие особенности данного шифра:

- количество знаков в алфавите шифрованного текста (33) больше количества букв в алфавите открытого текста (26);

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

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

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

Диски вращаются в противоположных направлениях, которые отмечены стрелками. Зашифруем слово THE APPLE при начальном угловом положении дисков (разовом ключе) LB. Буква Т открытого текста отстоит от буквы L на 8 шагов. На восьмом шаге от буквы В (в алфавите шифрованного текста) находится соответствующий знак шифрованного текста 6 (циклическое отсчитывание). Вторая буква открытого текста Н отстоит от буквы Т на 14 шагов. На 14 месте после знака 6 (по стрелке движения) в алфавите шифрованного текста находится буква Q, которая и является буквой шифрованного текста. Продолжая этот процесс дальше, получим шифрованный текст: 6QOWS3PR.

Расшифрование производится в обратном порядке. Первый знак шифрованного текста (6) отстоит от буквы разового ключа В (в алфавите шифрованного текста) на 8 шагов. В алфавите открытого текста 8-й буквой после L является буква Т, и т. д.

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

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

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

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

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

Итак, на той же оси, что и диски (алфавиты) устройства, соединенные шестернями размером 27х26 соответственно, расположены две стрелки, как в современных часах. В начале шифрования большая (длинная) стрелка указывает на знак «+» (пробел). Малая стрелка, связанная с большой резьбовой шестеренкой, ставилась в то же положение: «часы» показывали «12.00». Набор букв открытого текста производился поворотом большой стрелки по направлению движения часовой. После такого поворота малая стрелка указывает знак шифрованного текста. Таким образом, при полном повороте большого диска малый диск смещался на единицу по отношению к исходному взаимному состоянию двух дисков, что приводило к сдвиговому изменению алфавита шифрованного текста по отношению к алфавиту открытого текста. По окончании каждого слова большая стрелка становилась на знак «+», буква, на которую при этом указывала короткая стрелка, записывалась как знак шифрованного текста. Во избежание неоднозначности расшифрования, удвоение букв в открытом тексте не допускается. Повторную букву следует либо пропустить, либо ставить вместо нее какую-нибудь редкую букву, например Q. Таким образом, слово THEAPPLE при шифровании записывается так: +THE+APLE+или +THE+APQLE+.

Ключом шифра является порядок расположения букв на внутреннем диске (26!»4?1026). Приведем формализованный пример шифрования на устройстве Уитстона. Выпишем алфавиты в две строки:

Слово THEAPPLE шифруется следующим образом. Под буквой Т стоит соответствующая шифрованная буква J; буква Н отстоит от Т на 15 шагов; на этом расстоянии от буквы J находится вторая буква шифрованного текста Р, и т. д. Окончательно получим шифрованный текст JPUASZYVB. Расшифрование производится в обратном порядке. Над буквой J шифрованного текста открытая буква Т. От J до Р 15 шагов. За буквой Т на этом расстоянии располагается буква Н и т. д.

Заметим, что если допустить удвоение букв (например АА), то шифртекст имел бы вид QD. Однако такой же шифртекст соответствует и биграмме АВ, следовательно, в этом случае расшифрованный текст будет неоднозначен.

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

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

Это изобретение повторяет предложение Дж. Порта о шифровании не отдельных букв, а двухбуквенных сочетаний (биграмм), однако уже на новом уровне. Шифр Порта не мог быть использован при телеграфной передаче сообщений, поскольку экзотические обозначения биграмм в шифрованном тексте недоступны этому виду связи. Смысл предложения Уитстона заключается в следующем. В квадрат размером 5х5 выписывались в произвольном порядке буквы английского алфавита (буквы I и J не различались). Для облегчения запоминания такой выписки Уитстон предложил использовать идею создания «хаотического» набора букв из ключевого слова (лозунга). Пусть этим словом является слово MAGNETIC.Составим табличку по этому слову, дополняя ее буквами алфавита, не вошедшими в указанное слово, в их естественном порядке расположения в алфавите. Получаем следующий результат:

M A G N E T I C

B D F H K L O P

Q R S U V W X Y

Z

Выпишем буквы по столбцам:

MBQZADRGFSNHUEKVTLWIOXCPY

Эта последовательность располагается в квадрат 5х5:

M B Q Z A

D R G F S

N H U E K

V T L W I

O X C P Y

Аалгоритм шифрования поясним на примере. Пусть требуется зашифровать слово THEAPPLE. Удвоенные буквы разделяются буквой Х: получим THEAPXPLE. Поскольку получилось нечетное число букв, добавим произвольно выбранную букву (Z): THEAPXPLEZ. Этот текст разбивается на пары:

TH.EA.PX.PL.EZ.

Буквы TH стоят в одном столбце. Они заменяются буквами, стоящими под ними в том же столбце (при циклическом сдвиге). Таким образом, ТН заменяется на ХТ. Биграмма ЕА соответствует буквам, стоящим в разных строках и столбцах. Она заменяется на биграмму ZK, стоящую в противоположных углах соответствующего прямоугольника.

Биграмма РХ, расположенная в одной строке, шифруется циклическим сдвигом нижней строки: получаем YC.

Биграмма PLзаменяется по правилу прямоугольника на WC.

Наконец, биграмма EZ по правилу шифрования столбцов заменяется на WF.

Окончательно получаем шифрованный текст:

XTZKYCWCWF

Расшифрование определяется очевидным образом.

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

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

Уильям Фридман. В начале ХХ века начал свою карьеру известный американский криптограф У. Фридман, ставший одним из основоположников современной научной криптографии. У. Фридман родился в 1891 году в Кишиневе. Его отец был переводчиком, работавшимв русском почтовом ведомстве. В 1892 году его семья эмигрировала в США, где отец стал заниматься производством швейных машинок. В 1914 году У. Фридман окончил университет по специальности генетика, а годом позже поступил на работу к бизнесмену Д. Фабиану. Наниматель в это время увлекался криптографией, и, в частности, пытался доказать (используя методы «дешифрования» пьес Шекспира), что автором пьес последнего являлся Ф. Бэкон. Через некоторое время У. Фридман возглавил два отдела: «Генетика» и «Шифры» в специализированной лаборатории.

Во время I мировой войны Фридман служил в криптографической службе, в том числе и дешифровальщиком. Помимо криптоаналитической работы Фридман занимался преподаванием курса криптографии для армейских офицеров. К 1918 году им был подготовлен цикл из восьми лекций для слушателей, которые легли в основу труда «Ривербэнские публикации», ставшего серьезным вкладом в теоретическую криптографию. Отметим, что в этих лекциях был предложен метод определения периода гаммы (длины лозунга) в шифре Виженера, а также бесключевой метод дешифрования при использовании неравновероятной гаммы. В целом Фридман продемонстрировал эффективность теоретико-вероятностных методов при решении криптографических задач.

Г. Вернам. Значительный вклад в развитие криптографии сделал американец Г. Вернам. В 1917 году он, будучи сотрудником телеграфной компании, предложил идею автоматического шифрования телеграфных сообщений, суть которой заключается в следующем. Открытый текст представляется в коде Бодо (в виде пятизначных «импульсных комбинаций»). В этом коде, например, буква «А» имела вид (+ + — — —). На бумажной ленте эта буква получала следующий вид:

Знак «+» означал отверстие, а знак «–» – его отсутствие. При считывании с ленты пятерка металлических щупов «опознавала» отверстия (при наличии отверстия щуп замыкал электрическую цепь). В линию связи посылались импульсы тока:

Вернам предложил электромеханически покоординатно складировать импульсы знаков секретного текста с импульсами гаммы. Гамма – это секретный ключ, представляющий из себя хаотический набор букв того же самого алфавита. Сложение, по современной терминологии, осуществлялось «по модулю 2»: 0 + 0 = 0, 0 + 1 = 1, 1 + 0 = 1, 1 + 1 = 0 (здесь «0» означает знак «–» «кода Бодо», а 1 – «+»). Пусть, например, знак гаммы имеет вид: + — + — — (10100). Тогда буква «А» при шифровании переходит в двоичную комбинацию: 01100 (— + + — —). При расшифровании ту же операцию необходимо повторить (покоординатно):

(01100)?(10100) = (11000) = (А)

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

Отметим одну важную особенность шифра Вернама, которая послужила в последующем обоснованию теории совершенного шифра, предложенной американским классиком криптографии К. Шенноном. Дело в том, что при применении шифра Вернама за перехваченным шифрованным текстом вида b1, b2, …, bn может скрываться любой открытый текст a1,a2, …, an. Любому открытому тексту можно подобрать гамму, которая порождает данный шифрованный текст. Поскольку гаммаявляется ключом, то по перехвату шифрованного сообщения невозможно отвергнуть ни одного открытого текста той же длины. Усилия дешифровальщиков сводятся на «нет».

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

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

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

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

Литература

 Kahn D. The codebreakers. N.-Y., 1967.

 Kahn D. Kahn on codes. N.-Y., 1983.

 Keith Melton H. The ultimate spy book. N.-Y., 1992.

 Анин Б. А., Петрович А. И. Радиошпионаж. М., 1996.

 Анин Б. А. Радиоэлектронный шпионаж. М., 2000.

 Бабаш А. В., Шанкин Г. П. История криптографии. Часть 1. М., «Гелиос», 2002.

 Даллес А. Искусство разведки. М., 1992.

 Дамасскин И. А. Сто великих разведчиков. М., 2002.

 Жельников В. Криптография от папируса до компьютера. М., 1996.

 Кукридж Е. Х. Тайны английской секретной службы. М., 1959.

 Мазер И. Дипломаты и дипломатия // «За рубежом» № 17, 1993.

 Найтли Ф. Шпионаж ХХ века. М., 1994.

 Очерки истории внешней разведки т. 1 ред. Е. М. Примакова , М., 1997.

 Очерки истории внешней разведки т. 2 ред. Е. М. Примакова , М., 1999.

 Полмар Н., Аллен Т. Б. Энциклопедия шпионажа. М., 1999.

 Ронге М. Разведка и контрразведка. Киев, 1993.

 Роуан Р. Очерки секретной службы. СПБ., 1992.

 Саломаа А. Криптография с открытым ключом. М., 1997.

 Соболева Т. А. Тайнопись в истории России. М., 1994.

 Соболева Т. А. История шифровального дела в России. М.: ОЛМА-ПРЕСС-Образование, 2002.

 Тайные операции российских спецслужб. М., 2000, с. 231.

 Тайные страницы истории. М., 2000, с. 391.

 Фролов Г. Тайны тайнописи. М., 1992.

 Черняк Е. Секретная дипломатия Великобритании. М., 1975.

 Черняк Е. Пять столетий тайной войны. М., 1991

А. В. Бабаш, д. ф.-м. н., профессор, Ю. И. Гольев, Д. А. Ларин, к. т. н., Г. П. Шанкин, д. т. н., профессор / журнал «Конфидент» /

Источник: http://www.agentura.ru/press/about/jointprojects/confident/crypto19end/

Русская Цивилизация
Читайте также:



©  Фонд "Русская Цивилизация", 2004 | Контакты