Бабаш А.В., Шанкин Г.П. Криптография (распознано не всё)

111

Кулачковая и ступенчатая матрицы образуют ключ для шифровки с помощью С-36. Машина может быть рассмотрена как физическая реализация криптосистемы, описанной выше: она оперирует с переопределенным ключом после того, как активизируются подходящие штифты и позиционируются подходящие зубцы. Уравнение у=Ь-а-1 может быть записано также в виде а=Ь-у-1 . Это означает, что процесс шифрования ирасшифрования иденти­

чен.

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

Очевидно, что ступенчатая матрица генерирует векторы периодиче­ ски. Следовательно, шифровка с помощью С-36 может быть рассмотрена как использование квадрата Бофора с ключевым словом. Но какова длина ключе­ вого слова? Обычно она намного длиннее любого допустимого сообщения. Следовательно, периодичность в криптотексте может и не появиться.

Действительно, длины строк в ступенчатой матрице попарно взаимно просты. Это означает, что только после

17-19 • 21-23 • 25-26 = 101.405.850 шагов мы можем быть уверены, что опять вернемся в исходное состояние. В

общем случае период не меньше данного числа, которое в действительности превышает число символов в достаточно объемной энциклопедии. Однако в конкретных случаях период может быть короче. К примеру, если ступенчатая матрица не содержит нулей, то генерируется только вектор (1 ,1 ,1,1 ,1 ,1), и,

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

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

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

112

криптоаналйтических подходов читатель может обратиться к (Векег Н. & Р1рег Р. С1рЬег зу81етз. МойЬшооё Воокз, Ьопёоп, 1982).

Некоторые известные криптографические машины, такие как немец­ кая ЕМОМА (описание приведено ранее), американская 5ЮАВА и японские КЕО и ШКРЬЕ времен второй мировой войны, являются электромеханиче­ скими. Основным блоком в них является диск в виде кодового колеса с про­ волочными перемычками внутри, называемый также ротором, по внешней и внутренней поверхностям которого равномерно распределены электрические контакты. Эти контакты позволяют объединять роторы. Как и для С-36, ре­ зультирующая подстановка может меняться от буквы к букве.

Ниже мы кратко обсудим роторные машины. Результирующие крип­ тографические отображения для них являются несколько более общими, чем в случае С-36, по крайней мире с нашей точки зрения. Для более подробного изучения читатель может обратиться к (Векег Н. & Р1рег Р. СМрЬег зуз1етз.

МойЬтюё Воокз, Ьопёоп, 1982).

Роторные машины.

В 20-х годах XX века были изобретены электромеханические устрой­ ства шифрования, автоматизирующие процесс шифрования для некоторых поточных шифров. Принцип действия таких машин основан на многоалфа­ витной замене символов исходного текста по длинному ключу согласно вер­ сии Виженера (см. /РОМ/). Другими словами, эти устройства реализовывали последовательность подстановок алфавита, с помощью которой шифровалась последовательность букв открытого текста. Наверно первым примером ро­ торной машины служит шифратор Джефферсона, о котором уже говорилось в параграфе 1.1. Кроме того, примерами таких устройств являются: описанный выше шифратор Хагелин, немецкая машина «Энигма-ЕЫЮМА», американ­ ская машина ЗЮАВА (М-134), английская ТУРЕХ, японская РЦКРЬЕ и др. Главной деталью таких машин являлся ротор. Ряд таких машин (а именно дисковые шифраторы) в роторах - дисках имели проволочные перемычки внутри и контакты, расположенные по окружности двух сторон дисков. Каж­ дый контакт с одной стороны диска был соединен с одним контактом другой стороны диска. Контакты отождествляются с буквами алфавита. В соответст­ вии с внутренним еоединением контактов электрический сигнал, представ­ ляющий букву алфавита - номер контакта переставляется в соответствии с тем, как он проходит через диск. Если П - подстановка букв, осуществляемая диском в некотором фиксированном положении, то при повороте диска на) шагов осуществляется новая подстановка Т’П'Г’ , где Т - подстановка цикли­ ческого вида к—»к+1 (тоё |1|), I - алфавит текста.

и з

Последовательное прохождение тока через контакты от первого диска доп-го моделируется подстановкой - произведением подстановок П1П2...Пп,

соответствующих дискам 1,2,. ..,п. Если же первый диск провернется на Ц, позиций, второй на]2 позиций, п-й напозиций, то реализуемая дисками подстановка (схема токопрохождения) математически записывается в виде подстановки Т '^ 'Г ’1 Т’2П2'Г’2 ... Т'ПП„'Г’П. Роторные машины-шифраторы от­

личались количеством дисков, их коммутацией, схемой совместного движе­ ния дисков.

Шифры гаммирования (/Про/).

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

1011 12 1з 15 1б.:.

У0У1 У2У0УЫУ0У1-.

Если длина ключа меньше длины открытого текста, то ключ периодически повторяется. Каждому знаку открытого текста и ключа ставится в соответст­ вие некоторый вычет по модулю п, например, А=1, Б=2,.... Способ сопостав­ ления не является секретным. Шифрованный текст получается по правилу

, уОН.+У! (тобп)

Таким образом, мы имеем перед собой шифр Цезаря с меняющимся сдвигом нередко его называют и шифром ВИЖЕНЕРА.

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

Гаммирование чаще всего осуществляется:

-по модулю 2, если открытый текст представляется в виде бинарной по­

следовательности;

-по модулю 256, если открытый текст представляется в виде последова­ тельности байтов;

-с помощью покоординатного суммирования двоичных векторов (опе­ рация Л в обозначениях языка программирования С или хог в обозначе­ ниях ассемблера);

-по модулю 10, если открытый текст представлен в виде последователь­

ности цифр, что иногда делается в ручных системах шифрования.

114

Блочные шифры как узлы усложнения поточных шифров (/Про/).

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

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

Поточный шифр гаммирования КС4.

Выбор схемы шифратора как правило ориентирован на элементную ба­ зу, на которой предполагается осуществить ее реализацию. В качестве примера современного шифра гаммирования, ориентированного на программную реа­ лизацию, приведем Алгоритм К.С-4 (разработка К.8А Зесигйу 1псогрога1еб).

Данный шифр применен, в частности, для защиты в распределенной базе дан­ ных Ьо1из 1ЧоШз и в некоторых других программных продуктах.

Описание функционирования поточного шифра К.С4 дается по работе Йована Голича (ГОЛ. I. О. Оойс, «1лйеаг 81аП$Нса1 Шеакпезз оГА11е§её К.С4 КеузГгеат §епега!ог», т ЬесШге Ыо1еа т СотрШег 8с1епсе 1233; Абуапсе» т

СгурЮ1ору:: Ргос. Еигосгур1 '97, XV. Риту, ЕсЦ Мау 1997, рр. 226-238, ВегНп: 8рпп§ег-Уег1а§, 1997 ). Фактически, К.С4 представляет собой семейство алго­ ритмов, задаваемых параметром «, который является положительным целым с рекомендованным типичным значением п = 8. Внутреннее состояние генера­

тора ВС4 в момент времени ( состоит из таблицы 8 , = (8, (/))^о', содержа­

щей 2я «-битных слов и из двух «-битных слов-указателей /, и Т а к и м обра­

I

115

зом, размер внутренней памяти составляет М = и2" + 2п бит. Пусть выходное п-битное слово генератора в момент I обозначается как 2,. Пусть начальные значения /0=у0= 0. Тогда функция следующего состояния и функция выхода

ЯС4 для каждого I > 1 задается следующими соотношениями:

/, = ;,.! + 1 ,

У/ =У» - 1 "*■8/ -1О/Х

8/ (О = 8/. 1(7'/), 8 1 (/,) —8 1 -1(|/),

2 , = 5,(5,(/,) + $,(/,)),

где все сложения выполняются по модулю 2". Подразумевается, что все слова, кроме подвергаемых изменению по формулам, остаются теми же самыми.

Выходная последовательность и-битных слов обозначается как 2 = (2 ,) ” ,.

Начальная таблица />0задается в терминах ключевой последовательнос­

ти К =

с использованием той же самой функции следующего состоя­

ния, начиная от таблицы единичной подстановки (0/=о' • Более строго, пусть

}а - 0 и для каждого 1< I < Т вычисляетсяу, = (/,. \ + 8,.\(1- 1) + К ,.\) шоё 2", а затем переставляются местами 8,.\(( - 1) и 8 ,.^ ,). На последнем шаге порож­ дается таблица, представляющая $о. Ключевая последовательность К состав­ ляется из секретного ключа, возможно повторяющегося, и рандомизирующего ключа, передаваемого в открытом виде в целях ресинхронизации. Шифрован­ ный текст получается сложением по модулю 2 двоичных векторов О, длины п (байтов при п=8) открытого текста с двоичными векторами 2 , длины п.

Скремблеры (/Про/).

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

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

-уверенность корреспондента в том, что сообщение дошло до адресата, чего не бывает, скажем, в случае отсылки письма или телеграммы;

116

-узнавание корреспондентами друг друга по тембру голоса, что бывает очень важно при передаче конфиденциальной информации;

-меньшие затраты времени для передачи информации по сравнению с други­ ми видами связи;

-простота вхождения в связь и относительная дешевизна этого вида связи;

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

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

Известно несколько типовых преобразований аналогового сигнала, которые могут быть легко реализованы инженерными методами. Укажем главные из них.

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

\у

Перестановка частот

Простейший скремблер ограничивает защиту введением подобных простейших частотных преобразований. Серийный скремблер переставляет диапазон 250-675 Гц 675-1100 Гц 1100-1525 Гц 1950-2375 Гц. В данной схеме на вход узла наложения шифра подается одно и то же управление, ор­ ганизующее перестановку.

ИНВЕРТИРОВАНИЕ СПЕКТРА. Более сложные скремблеры допол­ нительно проводят инвертирование спектра (см. рисунок).

г

117

Инвертирование спектра

ЧАСТОТНО-ВРЕМЕННЫЕ ПЕРЕСТАНОВКИ. Еще более сложные системы разбивают сигнал на временном интервале 60-500 миллисекунд и на каждом интервале используются в комбинации свои аналоговые преобразо­ вания. Сменой преобразований в разные временные интервалы управляет по­ следовательность, поступающая на узел наложения шифра из блока усложне­ ния. Тот, кто просто послушает дешифрованную аналоговым сигналом речь услышит какое-то булькание, шум. О сложности задачи зашифрования и расшифрования аналоговых сообщений писал Солженицын в своем «В круге первом». Цитируем: «...Клиппирование, демпфирование, амплитудное сжа­ тие, электронное дифференцирование и интегрирование привольной челове­ ческой речи были таким же инженерным издевательством над ней, как если бы кто-нибудь взялся расчленить Новый Афон или Гурзуф на кубики вещест­ ва, втиснуть в миллиард спичечных коробок, перевести самолетом в Нер­ чинск, на новом месте распутать, неотличимо собрать и воссоздать субтропи­ ки, шум прибоя, южный воздух и лунный свет. То же, в некоторых импуль­ сах надо было сделать и с речью, даже воссоздать ее так, чтобы не только все было понятно, но Хозяин мог бы по голосу узнать, с кем говорит...» Конец цитаты. «Хозяин» - это речь идет о Сталине. Также красочно и немного пре­ небрежительно Солженицын отзывался о самой работе по разработке отече­ ственных средств защиты телефонной информации. Однако здесь он был не прав. По мнению высококвалифицированных специалистов из так называе­ мой шарашки в Марфино (настоящее название у нее другое, сейчас - это НИИ в престижном районе Москвы) в то время работа шла очень целена­ правленно и аппаратуру на самом деле делали в срок. Это - аппаратура вре­ менной стойкости. При наличии спецтехники типа видимой речи содержание переговоров удается восстановить. Если забыть про инверсии, то мы имеем шифр перестановки. Аппаратура видимой речи сводит задачу дешифрования к восстановлению некого рисунка, зашифрованного шифром перестановки.

Для гарантированного засекречивания телефонной речи ее сначала оцифровывают - переводят в двоичную последовательность, а потом обраба­

118

тывают также как и любое текстовое сообщение. В практике используются как аппаратура аналогового, так и цифрового засекречивания. Цифровая ап­ паратура обеспечивает гарантированную надежность защиты, но она более дорогая, более привередливая к каналам связи. Аналоговая аппаратура менее стойкая, но более дешевая, более портативная, менее требовательная к кана­ лам связи. Более подробно о шифровании в телефонии см. (Алферов А.П., Зубов А.Ю., Кузьмин А.С., Черемушкин А.В. «Основы криптографии» М., Гелиус АРВ, 2001- 4&0 с.), а также (ЗреесЬ апё РасетПе зсгатЫт§ апб Оесобт^. А сгур!о§гарЫс зепез, у.31,1981. Ае§еап Рагк Ргезз).

Параграф 1.5 Стеганографические средства защиты информации

в переходный период от древности к современности

(/Про/)

Напомним, что под стеганографическими методами защиты инфор­ мации понимаются методы сокрытия самого факта наличия или передачи ин­ формации.

В первом параграфе этой главы отмечалось, что первые следы стега­ нографических методов теряются в глубокой древности. Например, мы ука­ зывали и такой способ сокрытия письменного сообщения. Голову раба брили,' на коже головы писали сообщение и после отрастания волос отправляли раба к адресату. Отзвук этой истории можно встретить в «Гиперболоиде инженера Гарина» Алексея Толстого, где текст нанесли на спину мальчика.

Тайнопись.

Сообщения симпатические, латентные или скрытые, могут быть сде­ ланы специальными техническими средствами, например, бесцветными чер­ нилами, проявляющимися лишь после специального физического или хими­ ческого воздействия. Популярные исторические книжки сообщали, что рос­ сийские революционеры в тюрьмах использовали в качестве симпатических чернил даже обычное молоко. При нагревании огнем или горячим утюгом та­ кие записки становились отчетливо видны. Литератор Куканов в своей повес­ ти о Ленине «У истоков грядущего» рассуждал так: «Молоко в роли чернил - не самый хитрый способ тайнописи, но порой, чем проще уловка, тем она на­ дежнее». Однако если заглянуть в архивы российской охранки, то станет ясно, что там было прекрасно известно о подобных уловках. Выявить и прочесть эту тайнопись Департаменту полиции не составляло труда. Именно в России были разработаны и развиты способы чтения скрытых и стертых текстов с

119

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

Микроточки. Сокрытие текста достигло своих вершин после второй

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

вкниге среднего формата было много сложнее, чем пресловутую иголку в стоге сена.

Адвокат Рудольфа Абеля, известного разведчика в США, обмененного

в1962 г. после 5 лет заключения из 30, на пилота-шпиона Пауэрса, хотел продать его конфискованные картины с аукциона, чтобы поддержать своего подзащитного, хотя бы материально. Однако этого не удалось сделать, т. к. картины были написаны маслом с применением непрозрачных для рентгенов­ ских лучей красок. При поиске микроточек картины были бы разрушены, а сампоиск занял бы годы кропотливой работы ЦРУ. Поэтому в тюрьме Абелю пришлось подрабатывать, рисуя лишь прозрачные акварели. Сейчас нет тех­ нических проблем записать текст так мелко, что его вообще нельзя будет про­ честь оптическими средствами без применения электронного микроскопа. Похожая технология используется при создании компьютерных микросхем большой интеграции.

Маскировка среди другой информации. Акростих. Метод Грибое­

дова А.С. Другой подход - маскировка сообщения среди посторонней ин­

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

пользовал А.С. Грибоедов в бытность послом России в Персии. Уже в Совет­ ское время некоторых его биографов смутил тот факт, что в отдельных пись­ мах из Персии жене нарушался характерный стиль и замечательный писатель был не похож сам на себя. При исследовании оказалось, что эти письма со­ держали дипломатические послания Александра Сергеевича. Они были сде­ ланы через накладываемый на лист бумаги трафарет, в котором были выреза­ ны отдельные окошки под буквы. Написав донесение через трафарет, Грибое­ дов дописывал разбросанные по листу-буквы в связный текст так, чтобы он содержал письмо жене, и отправлял его с обычной почтой. Российские сек­ ретные службы перехватывали это письмо или, как говорят, перлюстрирова­ ли, расшифровывали, а затем доставляли адресату. По-видимому, жена его не догадывалась о двойном назначении этих посланий. Отметим большое остро­

120

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

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

предложены различные способы реализации идеи сокрытия содержания среди «шумовой» последовательности. При написании текста от руки человек ис­ пользует различные начертания для букв, например, «д» или «т». Если отпра­ витель и получатель договорятся, что только одно из возможных начертаний принимается во внимание, то Вы получите способ маскировки сообщения. Стеганографические способы маркировки очень любят фокусники и шарлата­ ны. Проскурин Г.В. сообщил авторам один карточный фокус с математиче­ ским и стеганографическим оттенком. Фокусник берет колоду карт, вынимает часть из них, на остальные внимательно смотрит, как-то перекладывает, по­ том предлагает Вам вынуть одну карту из колоды, посмотреть на нее, и поло­ жить в колоду, можно положить на то же место. Далее он тасует Колоду, предлагает потасовать Вам. Затем берет карты, просматривает их и угадывает ту, что Вы выбрали. Секрет фокуса достаточно прост. У каждой карты можно определить верх и низ по виду рисунка. Самый простой способ: сердечко чер­ вей должно быть ориентировано острым концом вниз, крест треф в правиль­ ном положении стоит на палочке - подставке, острый конец пики должен быть направлен вверх. Симметричные карты фокусник откладывает. Остав­ шиеся карты он укладывает в установленном им нормальном положении вер­ хом вверх. Когда Вы вытаскиваете карту, его задача подставить колоду так, чтобы Вы вложили карту кверху ногами. Стасовав колоду, не меняя при этом ориентации карт, и просматривая картинки, он сразу видит карту, ориентиро­ ванную не так как остальные. Именно ее Вы и выбрали.

Использование особенностей поведения. Имея определенный навык

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