Полная версия

Главная arrow Информатика arrow Защита информации

  • Увеличить шрифт
  • Уменьшить шрифт


<<   СОДЕРЖАНИЕ   >>

ПРОГРАММНО-АППАРАТНЫЕ МЕТОДЫ ЗАЩИТЫ ИНФОРМАЦИИ

КРИПТОГРАФИЧЕСКАЯ ЗАЩИТА ИНФОРМАЦИИ

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

Как и любая наука, криптография опирается на базовые понятия и определения [1, 5]. Рассмотрим основные из них.

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

Изначально криптография изучала методы шифрования информации — обратимого преобразования открытого (исходного) текста на основе секретного алгоритма и/или ключа в шифрованный текст (шифротекст). Традиционная криптография образует раздел симметричных криптосистем, в которых зашифрование и расшифрование проводится с использованием одного и того же секретного ключа. Помимо этого раздела современная криптография включает в себя асимметричные криптосистемы, системы электронной цифровой подписи (ЭЦП), хеш-функции, управление ключами, получение скрытой информации, квантовую криптографию 11,251.

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

Шифр (от арабского зт/г «ноль», откуда французское сИ$ге «цифра»; родственно слову «цифра») — это совокупность условных знаков (условная азбука из цифр или букв) для секретной переписки дипломатических представителей со своими правительствами, а также в вооруженных силах для передачи текста секретных документов по техническим средствам связи.

Открытый (исходный) текст — данные (текстовые или иного вида), передаваемые без использования криптографии.

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

Код — это совокупность алгоритмов криптографических преобразований (шифрования), отображающих множество возможных открытых данных на множество возможных зашифрованных данных, и обратных им преобразований. Важным параметром любого шифра является ключ [5, 25, 281.

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

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

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

Асимметричный шифр — это шифр, который для шифрования и дешифрования использует два различных ключа. К асимметричным шифрам относятся следующие известные шифры: RSA, Эль-Гамаля (Elgamcil), Elliptic сите cryptography (ЕСС) — криптосистема на основе эллиптических кривых [28, 29].

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

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

В блочных шифрах результат зашифрования очередного блока зависит только от него самого и не зависит от других блоков шифруемого массива данных [25, 28, 291:

Из этого следует, что в результате зашифрования двух одинаковых блоков открытого текста всегда получаются идентичные блоки шиф-ротекста:

Ti=TJ->E(Tl) = E(Tj).

К блочным шифрам относятся следующие известные шифры: ГОСТ 28147—89, Advanced Encryption Standard (AES), также известный как Rijndael, DES, DESX, Triple DES, CAST-128, CAST-256, Blowfish, Twofish, IDEA, MARS, RC2, RC5, RC6, Serpent, Safer+, TEA, 3-WAY, WAKE, FROG, Skipjack.

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

К поточным шифрам относятся следующие известные шифры: ЯС4, А5.

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

Г/=?(Г„Г2,..., Т;).

Сюда же относится важный частный случай, когда результат зашифрования очередного блока зависит от этого блока и от его номера:

Т; = Е{1,Т,).

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

Шифрование — процесс нормального применения криптографического преобразования открытого текста на основе алгоритма и ключа, в результате которого возникает шифрованный текст [29].

Расшифровывание — процесс нормального применения криптографического преобразования шифрованного текста в открытый.

Если принять во внимание требование к реализуемости шифрования устройством с конечным числом возможных состояний, то наиболее общей моделью шифров является конечный автомат, описываемый множеством состояний^, входным и выходным алфавитами 1 и Е, и правилами перехода и выхода 0 и Е соответственно:

%i+ ©(А/, 7)),

Г/= 5^., 7}),

где для всех / Xt g X, 7} g /, T- g Е.

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

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

Эта информация называется синхропосылкой и передается до начала передачи зашифрованных данных всякий раз при установлении или восстановлении соединения после сбоя в канале связи. По вполне понятной причине синхропосылка может передаваться только в открытом виде — на момент ее получения автомат расшифрования на принимающей стороне не готов к работе [25, 28, 29].

Криптоанализ — наука, изучающая математические методы нарушения конфиденциальности и целостности информации.

Криптоаналитик — человек, создающий и применяющий методы криптоанализа.

Криптография и криптоанализ составляют криптологию как единую науку о создании и взломе шифров (такое деление привнесено с Запада, до этого в СССР и России не применялось специального деления).

Криптографическая атака — попытка криптоаналитика вызвать отклонения в атакуемой защищенной системе обмена информацией. Успешную криптографическую атаку называют взлом, или вскрытие.

Дешифрование (дешифровка) — процесс извлечения открытого текста без знания криптографического ключа на основе известного шифрованного. Термин «дешифрование» обычно применяют по отношению к процессу криптоанализа шифротекста (криптоанализ сам по себе, вообще говоря, может заключаться и в анализе шифросистемы,анетолько зашифрованного ею открытого сообщения) |5, 25, 29].

Криптографическая стойкость — способность криптографического алгоритма противостоять криптоанализу.

Имитозащита — защита от навязывания ложной информации. Имитозащита достигается обычно за счет включения в пакет передаваемых данных имитовставки.

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

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

Первый период (приблизительно с 3-го тысячелетия до н.э. до IX в. на Ближнем Востоке и до XV в. в Европе) характеризуется господством моноалфавитных шифров (основной принцип — замена алфавита исходного текста другим алфавитом через замену букв другими буквами или символами). Второй период (хронологические рамки — с IX в. на Ближнем Востоке и с XV в. в Европе — до начала XX в.) ознаменовался введением в обиход полиалфавитных шифров. Третий период (с начала XX в. и до конца 70-х гг. XX в.) характеризуется внедрением электромеханических устройств в работу шифровальщиков. При этом продолжалось использование полиалфавитных шифров. Четвертый период (с конца 70-х гг. XX в. по настоящее время) характеризуется переходом к математической криптографии. В работе К.Э. Шеннона появляются строгие математические определения количества информации, передачи данных, энтропии, функций шифрования. Обязательным этапом создания шифра считается изучение его уязвимости к различным известным атакам — линейному и дифференциальному криптоанализу. Однако до 1975 г. криптография оставалась «классической», или же, более корректно, криптографией с секретным ключом.

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

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

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

Примером древнего применения криптографии является случай, когда автор таблички с рецептом для изготовления глазури для гончарных изделий из Месопотамии использовал редкие обозначения, пропускал буквы, а имена заменял на цифры, чтобы скрыть написанное [4, 13, 18, 29].

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

Примеры использования криптографии можно встретить в священных иудейских книгах, в том числе в книге пророка Иеремии (VI в. до н.э.), где использовался простой метод шифрования под названием атбаш. Для реализации данного метода шифрования использовались сциталы [4, 13].

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

Принцип ее действия изложили Аполлоний Родосский (середина III в. до н.э.) и Плутарх (около 45—125 н.э.).

Сцитала представляла собой длинный стержень, на который наматывалась лента из пергамента. На ленту вдоль оси сциталы Рис. 5.1. Внешний вид сциталы наносился текст так, что после

разматывания он становился нечитаемым. Для его восстановления требовалась сцитала такого же диаметра.

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

С именем полководца Энея Тактика (IV в. до н.э.) связывают несколько техник шифрования и тайнописи. Диск Энея представлял собой диск диаметром 10—15 см с отверстиями по числу букв алфавита. Для записи сообщения нитка протягивалась через отверстия в диске, соответствующие буквам сообщения. При чтении получатель вытягивал нитку и получал буквы, правда, в обратном порядке. Хотя недоброжелатель мог прочитать сообщение, если перехватит диск, Эней предусмотрел способ быстрого уничтожения сообщения — для этого было достаточно выдернуть нить, закрепленную на катушке в центре диска.

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

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

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

Согласно свидетельству Светония, Цезарь использовал в переписке моноалфавитный шифр, вошедший в историю как Шифр Цезаря. Книгу о шифре написал грамматик Проб. В шифре Цезаря каждая буква алфавита циклически сдвигается на определенное число позиций (рис. 5.2). Величину сдвига можно рассматривать как ключ шифрования. Сам Цезарь использовал сдвиг на три позиции |4, 5, 13].

X

У

г

А

В

с

о

Е

Б

• • •

V

X

• • •

А

В

С

о

Е

Б

С

н

I

Рис. 5.2. Принцип использования шифра Цезаря

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

М ножество вариантов тайнописи использовалось и на Руси. Среди них и простые моноалфавитные шифры (простая литорея, письмо в квадратах), замена алфавита — тайнопись глаголицей, тайнопись греческой азбукой, а также особые приемы письма, например, мо-нокондил. Наиболее ранние тексты с использованием тайнописи относятся к XII в.

Существует мнение, что в более поздний период тайнопись использовалась для иконографии, например, при написании иконы XIV в. «Донская Богоматерь». Согласно другой точке зрения, буквенный ряд является лишь шрифтовым декором, который был широко распространен как в древнерусской, так и, например, в византийской иконописи.

Развитие криптографии в эпоху второго периода. В 855 г. выходит Книга о большом стремлении человека разгадать загадки древней письменности арабского ученого Абу Бакр Ахмед бен-Али бен-Вах-шия ан-Набати. Это одна из первых книг о криптографии с описаниями нескольких шифров, в том числе с применением нескольких алфавитов. Также к IX в. относится первое известное упоминание о частотном криптоанализе — в книге Ал-Кинди «Манускрипт о дешифровке криптографических сообщений» [5, 10, 131.

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

Рогериса Бакониса о тайных действиях искусства и природы и ничтожестве магии» (лат. Epistola Fratris Rog. Baconis, de secretis operibus artis et naturae et nullitate magiae), описывающий, в числе прочего, применение семи методов скрытия текста.

Симеоне де Крема (Simeone de Сгета) был первым (1401), кто использовал таблицы омофонов для сокрытия каждого гласного в тексте при помощи более чем одного эквивалента. Спустя более ста лет эти таблицы использовал Эрнан Кортес для успешной защиты от криптоаналитических атак.

Первая организация, посвятившая себя целиком криптографии, была создана в Венеции (Италия) в 1452 г. Три секретаря этой организации занимались взломом и созданием шифров по заданиям правительства. В 1469 г. появляется шифр пропорциональной замены «Миланский ключ».

Отцом западной криптографии называют ученого эпохи Возрождения Леона Баттиста Альберти. Изучив методы вскрытия использовавшихся в Европе моноалфавитных шифров, он попытался создать шифр, который был бы устойчив к частотному криптоанализу. Трактат о новом шифре был представлен им в папскую канцелярию в 1466 г. Альберти предложил вместо единственного секретного алфавита, как в моноалфавитных шифрах, использовать два или более, переключаясь между ними по какому-либо правилу. Однако флорентийский ученый так и не смог оформить свое открытие в полную работающую систему, что было сделано уже его последователями [13, 18].

Очередной известный результат принадлежит перу германского аббата Иоганна Тритемия (по некоторым источникам Иоганн Три-семус), которого многие историки считают вторым отцом современной криптологии. В пятой книге серии Polygraphia, изданной в 1518г., он описал шифр, в котором каждая следующая буква шифруется своим собственным шифром сдвига.

Его подход был улучшен Джованом Баттистой Белласо (итал. Giovan Battista Bel/aso), который предложил выбирать некоторое ключевое слово и записывать его над каждым словом открытого текста. Каждая буква ключевого слова используется для выбора конкретного шифра сдвига из полного набора шифров для шифрования конкретной буквы, тогда как в работе Тритемия шифры выбираются просто по циклу. Для следующего слова открытого текста ключ начинал использоваться снова, так, что одинаковые слова оказывались зашифрованы одинаково. Данный способ в настоящий момент известен как шифр Виженера. Кроме этого, Тритемий первым заметил, что шифровать можно и по две буквы за раз — биграммами (хотя первый биграммный шифр — Playfair — был предложен лишь в XIX в.). Позже, в XVII в., член ордена иезуитов Атанасиус Кирхер провел исследования лингвистических аспектов работ Тритемия, результаты которых опубликовал в своей Polygraphia nova в 1663 г. Одним из результатов стало создание «полиглотического кода на пяти языках», который мог использоваться для шифрования и передачи сообщений на латинском, итальянском, французском, испанском и немецком языках, при этом декодирование могло производиться на любом из указанных языков.

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

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

Фрэнсис Бэкон в своей первой работе 1580 г. предложил двоичный способ кодирования латинского алфавита по принципу, аналогичному тому, что сейчас используется в компьютерах. Используя этот принцип, а также имея два разных способа начертания для каждой из букв, отправитель мог «спрятать» в тексте одного длинного сообщения короткое секретное. Данный способ получил название «шифр Бэкона», хотя относится больше к стеганографии |4, 5, 13].

Самым известным криптографом XVI в. можно назвать Блеза де Виженера (фр. Blaise de Vigenere). В своем трактате 1585 г. он описал шифр, подобный шифру Тритемия, однако изменил систему выбора конкретного шифра замены для каждой буквы. Одной из предложенных техник было использование букв другого открытого текста для выбора ключа каждой буквы исходного текста.

Описанный шифр известен как шифр Виженера и при длине случайного ключа, равной длине открытого текста, является абсолютно стойким шифром, что было математически доказано много позже (в XX в. в работах К.Э. Шеннона). Другая техника использовала результат шифрования для выбора следующего ключа — то, что впоследствии использует Фейстель и компания IBM при разработке шифра DES в 1970-х гг.

В 1626 г. при осаде города Реальмон, а позже и в 1628 г. при осаде Ла-Рошели, французский подданный Антуан Россиньоль (фр. Antoine Rossignol, 1600—1682) расшифровал перехваченные сообщения и тем самым помог победить армию гугенотов. После победы правительство Франции несколько раз привлекало его к расшифровке шифров. После его смерти его сын (фр. Bonaventure Rossignol), а позже и внук (фр. Antoine-Bonaventure Rossignol) продолжили начатое дело. В то время правительство Франции привлекало к работе множество криптографов, которые вместе образовывали так называемый Черный кабинет (фр. Cabinet Noir).

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

В России датой учреждения первой государственной шифровальной службы можно считать 1549 г. — образование «посольского приказа» с «циферным отделением». А как минимум с 1702 г. Петра I сопровождала походная посольская канцелярия под руководством первого министра Ф.А. Головина, которая с 1710 г. приобрела статус постоянного учреждения. В нем сосредоточилась криптографическая работа с перепиской между Петром, его приближенными и различными получателями, а также по созданию новых шифров [13, 181.

Впоследствии над дешифрованием сообщений в России трудились в том числе такие математики, как Кристиан Гольдбах, Леонард Эйлер и Франц Эпинус. При этом во время Семилетней войны ( 1756— 1763) Эйлер, находясь в Пруссии, хотя и продолжал переписываться с высшими лицами Российской империи, также занимался дешифровкой перехваченных писем русских офицеров.

К началу XVIII в. подобные кабинеты были по всей Европе, в том числе Die Geheime Kabinettskanzlei в Вене, первое дешифровальное отделение в Германии под начальством графа Гронсфельда, группа Джона Валлиса в Англии. До, во время и после войны за независимость США они оказались способны вскрыть большую часть колониальных шифров. Большинство из них было закрыто к середине

XIX в., в том числе, по одной из версий, из-за отсутствия вооруженного противостояния с США.

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

В 1790-х гг. будущий президент США Томас Джефферсон построил одну из первых механических роторных машин, упрощавшую использование полиалфавитных шифров. Среди других авторов-изо-бретателей стоит отметить полковника Десиуса Вадсворта, изобретателя машины с вращательными шифровальными дисками с различным количеством букв. Хотя он изобрел ее в 1817 г., вся слава досталась Чарлзу Уитстону за аналогичную машину, представленную на Всемирной выставке 1867 г. в Париже. Однако распространение роторные машины получили лишь в начале XX в.

Значительный толчок криптографии дало изобретение телеграфа. Сама передача данных перестала быть секретной, и сообщение, в теории, мог перехватить кто угодно. Интерес к криптографии возрос и среди простого населения, в результате чего многие попытались создать индивидуальные системы шифрования. Преимущество телеграфа было явным и на поле боя, где командующий должен был отдавать немедленные приказания по всей линии фронта или хотя бы на всем поле сражения, а также получать информацию с мест событий. Это послужило толчком к развитию полевых шифров. Сначала армия США использовала шифр Виженера с коротким ключевым словом, однако после открытия метода Касиски в 1863 г., он был заменен [18|.

Дальнейший прогресс был связан как с индивидуальными, так и с государственными исследованиями. В 1854 г. Чарлз Уитстон описал, а Лион Плейфер добился применения британскими вооруженными силами нового шифра, как его позже назовут — шифра Плейфера.

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

В 1863 г. Фридрих Касиски опубликовал метод, впоследствии названный его именем, позволявший быстро и эффективно вскрывать практически любые шифры того времени. Метод состоял из двух частей — определение периода шифра и дешифровка текста с использованием частотного криптоанализа.

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

  • 1. Шифр должен быть физически, если не математически, не-вскрываемым.
  • 2. Система не должна требовать секретности, на случай, если она попадет в руки врага.
  • 3. Ключ должен быть простым, храниться в памяти без записи на бумаге, а также легко изменяемым по желанию корреспондентов.
  • 4. Зашифрованный текст должен иметь возможность передаваться по телеграфу.
  • 5. Аппарат для шифрования должен быть легко переносимым, работа с ним не должна требовать помощи нескольких лиц.
  • 6. Аппарат для шифрования должен быть относительно прост в использовании, не требовать значительных умственных усилий или соблюдения большого количества правил.

В настоящее время второе из этих правил известно как принцип Керкгоффса.

Развитие криптографии в эпоху третьего периода. В конце XIX — начале XX в. правительства стран вновь бросили значительные силы на шифрование и криптоанализ. В 1914 г. Британия открыла «Комнату 40», в 1917 г. США — MI-8, ставшую предшественницей современного АН Б.

В 1918г. вышла монография американского криптографа российского происхождения Уильяма Ф. Фридмана «Индекс совпадения и его применение в криптографии» (англ. Index of Coincidence and Its Applications in Cryptography). Работа вышла в открытой печати, несмотря на то что была выполнена в рамках военного заказа. Двумя годами позже Фридман ввел в научный обиход термины «криптология» и «криптоанализ».

В начале 1920-х гг. практически одновременно в разных странах появляются патенты и электромеханические машины, использующие принципы криптографического диска (ротора) и автоматизирующие процесс шифрования. В США это был Эдвард Реберн, после него — Хьюго Кох из Нидерландов и его «Энигма» (позже патентбыл куплен Артуром Шербиусом), Арвид Герхард Дамм из Швеции и его машина «В-1» — разработки последнего были продолжены Борисом Хаге-линым [5, 10, 13].

В 1928—1929 гг. польское Biuro Szyfrow организовало курсы для 20 математиков со знанием немецкого языка — будущих криптоаналитиков, трое из которых известны работой по взлому «Энигмы». До этого на работу принимали в основном лингвистов.

В 1929 г. Лестер Хилл опубликовал в журнале The American Mathematical Monthly статью Cryptography in an Algebraic Alphabet. В ней он описал подход к конструированию криптографических систем, для которых математически была доказана их неуязвимость к частотным атакам, в том числе к методу Касиски. Для представления текста он перевел его в цифровой вид, а для описания шифрования использовал полиномиальные уравнения. В целях упрощения вычисления были представлены в виде операций над матрицами, отдельные элементы которых складывались и умножались по модулю 26 (по числу букв в латинском алфавите). Так как система оказалась слишком сложна в использовании, он собрал механическую шифровальную машину, которая упрощала эти операции. К сожалению, машина могла использовать лишь ограниченное множество ключей, и даже с машиной шифр использовался очень редко — лишь для шифрования некоторых государственных радиопередач. Тем не менее, его основной вклад — математический подход к конструированию надежных криптосистем.

До Первой мировой войны Россия наряду с Францией являлась лидером в области криптоанализа на государственном уровне. Англия, США, Германия и менее влиятельные государства — вообще не имели государственной дешифровальной службы, а Австро-Венгрия читала, в основном, переписку соседних государств. При этом если во Франции и Австро-Венгрии дешифровальная служба была военной, то в России — гражданской.

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

Перед началом Второй мировой войны ведущие мировые державы имели электромеханические шифрующие устройства, результат работы которых считался невскрываемым. Эти устройства делились на два типа — роторные машины и машины на дисках. К первому типу относят «Энигму», использовавшуюся сухопутными войсками Германии и ее союзников. Ко второму типу относят американскую машину М-209. В СССР производились оба типа машин.

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

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

Однако группа из трех польских математиков так не считала, и вплоть до 1939 г. вела работы по «борьбе» с «Энигмой», и даже умела читать многие сообщения, зашифрованными «Энигмой» (в варианте до внесения изменений в протокол шифрования от декабря 1938 г.). У одного из них, Мариана Реевского, зародилась идея бороться с криптографической машиной с помощью другой машины. Идея озарила Реевского в кафе, и он дал машине имя «Бомба» по названию круглого пирожного. Среди результатов, переданных британским разведчикам перед захватом Польши Германией, были и «живые» экземпляры «Энигмы», и электромеханическая машина Bomba, состоявшая из шести спаренных «Энигм» и помогавшая в расшифровке (прототип для более поздней Bombe Алана Тыоринга), а также уникальные методики криптоанализа [5, 18].

С современной точки зрения шифр «Энигмы» был не очень надежным, но только сочетание этого фактора с наличием множества

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

Внешний вид шифровальной машины «Энигма»

Рис. 5.3. Внешний вид шифровальной машины «Энигма»

Однако с 1940 г. высшее германское командование начало использовать новый метод шифрования, названный британцами Fish. Для шифрования использовалось новое устройство Lorenz SZ 40, разработанное по заказу военных.

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

Внешний вид шифровальной машины Lorenz SZ 40

Рис. 5.4. Внешний вид шифровальной машины Lorenz SZ 40

К сожалению, для Германии генератор, используемый в машинах Lorenz SZ40, оказался «слабым». Однако его взлом все равно нельзя было осуществить вручную — криптоаналитикам из Блетчли-парка потребовалось создать устройство, которое бы перебирало все возможные варианты и избавляло бы криптоаналитиков от ручного перебора. Таким устройством стала одна из первых программируемых вычислительных машин Colossus, созданная Максом Ньюменом и Томми Флауэрсом при участии Алана Тьюринга в 1943 г. (хотя некоторые источники указывают, что она была сделана для взлома «Энигмы»).

Также США во время Второй мировой войны набирали связистов из индейского племени Навахо, языка которого за пределами США никто не знал. При этом была учтена проблема, возникшая еще во время Первой мировой войны с использованием языка племени Чокто для похожих целей, — в обоих языках просто не было достаточного количества военных терминов. Поэтому был составлен словарь из 274 военных терминов, а также 26 слов алфавитного кода. Последний был впоследствии расширен для предотвращения частотных атак. Как указывает Сингх, именно отсутствие знания языка племени Навахо стало причиной того, что данный код так и остался не расшифрован японцами. Информация об использовании столь экзотического средства шифрования радиопереговоров была рассекречена лишь в 1968 г. 110, 13].

Крупным успехом американских криптоаналитиков явился проект «Венона» (англ. Venona project) по расшифровке переговоров советской разведки со своими агентами в ядерном «проекте Манхэттен». В передачах радиосвязи со своими агентами Центр в Москве использовал теоретически неуязвимую криптографическую систему с одноразовым ключом. Тем не менее, в ходе реализации глубоко засекреченного проекта «Венона» контрразведке США удавалось расшифровать передачи. Это происходило оттого, что в военные годы из-за недостатка ресурсов некоторые ключи использовались повторно, особенно в 1943—1944 гг. Кроме того, ключи не были по-настоящему случайными, поскольку производились машинистками вручную.

Развитие криптографии в эпоху четвертого периода. После Первой мировой войны правительства стран засекретили все работы в области криптографии. К началу 1930-х гг. окончательно сформировались разделы математики, являющиеся основой для будущей науки, — общая алгебра, теория чисел, теория вероятностей и математическая статистика. К концу 1940-х гг. построены первые программируемые счетные машины, заложены основы теории алгоритмов, кибернетики. Тем не менее, в период после Первой мировой войны идо конца 1940-х гг. в открытой печати было опубликовано совсем немного работ и монографий, но и те отражали далеко не самое актуальное состояние дел. Наибольший прогресс в криптографии достигается в военных ведомствах |13, 18].

Ключевой вехой в развитии криптографии является фундаментальный труд Клода Шеннона «Теория связи в секретных системах» (англ. Communication Theory of Secrecy Systems) — секретный доклад, представленный автором в 1945 г. и опубликованный им в Bell System Technical Journal в 1949 г. В этой работе, по мнению многих современных криптографов, был впервые показан подход к криптографии в целом как к математической науке. Были сформулированы ее теоретические основы и введены понятия, с объяснения которых сегодня начинается изучение криптографии студентами.

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

В 1967 гг. выходит книга Дэвида Кана «Взломщики кодов». Хотя книга не содержала сколько-нибудь новых открытий, она подробно описывала имеющиеся на тот момент результаты в области криптографии, большой исторический материал, включая успешные случаи использования криптоанализа, а также некоторые сведения, которые правительство США полагало все еще секретными. Но главное — книга имела заметный коммерческий успех и познакомила с криптографией десятки тысяч людей. С этого момента начали понемногу появляться работы и в открытой печати.

В 1976 г. публикуется работа Уитфилда Диффи и Мартина Хел-лмана «Новые направления в криптографии» (англ. New Directions in Cryptography). Данная работа открыла новую область в криптографии, теперь известную как криптография с открытым ключом. Также в работе содержалось описание алгоритма Диффи-Хеллмана, позволявшего сторонам сгенерировать общий секретный ключ, используя только открытый канал. Кроме этого, одним из результатов публикации стал значительный рост числа людей, занимающихся криптографией.

Хотя работа Диффи—Хеллмана создала большой теоретический задел для открытой криптографии, первой реальной криптосистемой с открытым ключом считают алгоритм RSA (названный по имени авторов — Rivest, ShamirwAdleman). Опубликованная в августе 1977 г. работа позволила сторонам обмениваться секретной информацией, не имея заранее выбранного секретного ключа. Опасаясь распространения системы в негосударственных структурах, АН Б безуспешно требовало прекращения распространения данной системы. RSA используется во всем мире. Черновики стандарта ISO для цифровой подписи и банковского стандарта ANSI основаны на RSA, также он служит информационным дополнением для ISO 9796, принят в качестве стандарта во Французском банковском сообществе и в Австралии.

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

С конца 1990-х гг. начинается процесс открытого формирования государственных стандартов на криптографические протоколы. Пожалуй, самым известным является начатый в 1997 г. конкурс A ES, в результате которого в 2000 г. государственным стандартом США для криптографии с секретным ключом был принят шифр Rijndael, сейчас уже более известный как A ES. Аналогичные инициативы носят названия N ESSIE (англ. New European Schemes for Signatures, Integrity, and Encryptions) в Европе и CR YPTREC (англ. Cryptography Research and Evaluation Committees) в Японии.

В самих алгоритмах в качестве операций, призванных затруднить линейный и дифференциальный криптоанализ, кроме случайных функций (вроде 5-блоков, используемых в шифрах DES и ГОСТ), стали использовать более сложные математические конструкции, такие как вычисления в поле Галуа в шифре AES. Принципы выбора алгоритмов (криптографических примитивов) постепенно усложняются. Предъявляются новые требования, часто не имеющие прямого отношения к математике, такие как устойчивость к атакам по сторонним каналам. Для решения задачи защиты информации предлагаются все новые механизмы, в том числе организационные и законодательные.

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

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

Классификация криптографических алгоритмов шифрования. Криптографические алгоритмы шифрования информации подразделяются на следующие группы: симметричные, несимметричные и гибридные. Кроме того, алгоритмы подразделяются по типу преобразования и по способу обработки информации (рис. 5.5).

Классификация криптографических алгоритмов

Рис. 5.5. Классификация криптографических алгоритмов

шифрования

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

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

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

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

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

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

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

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

  • — шифры замены;
  • — шифры перестановок;
  • — шифры гаммирования;
  • — шифры, основанные на аналитических преобразованиях шифруемых данных;
  • — композиционные шифры.

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

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

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

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

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

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

Идея, лежащая в основе составных или композиционных шифров, состоит в построении криптостойкой системы путем многократного применения относительно простых криптографических преобразований, в качестве которых К. Шеннон предложил использовать преобразования подстановки (substitution) и транспозиции (permutation). Многократное использование этих преобразований позволяет обеспечить два свойства, которые должны быть присущи стойким шифрам: рассеивание (diffusion) и перемешивание (confusion).

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

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

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

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

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

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

X

є

и

ш

У

р

$

6

о

О

р

п

3

у

ц

I

?

п

е

а

X

ъ

V

ф

1

Рис. 5.6. Полибианский квадрат, заполненный случайным образом

24 буквами греческого алфавита и пробелом

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

Например, для слова: тсшроо получается шифртекст: %ср6рт?.

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

Шифр Цезаря является частным случаем шифра простой замены (одноалфавитной подстановки). Свое название этот шифр получил по имени римского императора Гая Юлия Цезаря, который использовал этот шифр при переписке с Цицероном (около 50 г. до н.э.).

При шифровании исходного текста каждая буква заменялась на другую букву того же алфавита по следующему правилу. Заменяющая буква определялась путем смешения по алфавиту от исходной буквы на А'букв. При достижении конца алфавита выполнялся циклический переход к его началу. Цезарь использовал шифр замены при смещении К= 3. Такой шифр замены можно задать таблицей подстановок, содержащей соответствующие пары букв открытого текста и шифр-текста. Совокупность возможных подстановок для К= 3 показана в табл. 5.1.

Таблица 5.1

Одноалфавитные подстановки = 3,т = 26)

>

О

J -> М

СП

<

00 гп

К— N

Т—> W

0

Ч

Ч

О

с

1

X

0

О

М Р

Т

>

X

т

ш

N —? Q

N

Т

?

F —> I

т

о

X

1

>

7

о

Р —? S

Y—? В

Т

X

  • 0
  • 1 ч

и

Т

N

I — L

R —> U

Например, послание Цезаря « VENI VIDI VICI» в переводе на русский означающее «Пришел. Увидел. Победил», направленное его другу Аминтию после победы над понтийским царем Фарнаком, сыном Митридата, выглядело бы в зашифрованном виде так: YHQL YLGL YLFL.

Подстановка, определяемая ключом К, является криптографическим преобразованием Ек, которое шифрует л-грамму (х0, xh х2, x„_j) открытого текста в л-грамму (у0, У,у2, Уп-) шифртекста,

где уj — лДх,), 0 < / < я, для каждого я, я = 1,2,3,...

Криптографическое преобразование ^-называется одноалфавитной подстановкой, если значение л, одинаково для каждого /, / = 0, 1, 2, ...; в противном случае преобразование Ек называется многоалфавитной подстановкой.

На рис. 5.7 представлена схема реализации подстановки Ек.

Отметим характерные особенности подстановки Ек:

  • — открытый текст шифруется побуквенно (буква за буквой);
  • — /'-я буква у, шифртекста является функцией только /-й компоненты р, ключа К и /-й буквы х;- открытого текста;
  • — шифрование «-граммы (х0, х,, х2, ..., хи_1> производится в соответствии с формулой 0, уьу2,..., уп_|) = Ек0, X,, х2, ..., хи_!).

Система Цезаря представляет собой одноалфавитную подстановку, которая шифрует «-грамму (х0, х1? х2,..., х„_,) открытого текста в «-грамму (у0, У,у2,..., уп_[) шифртекста согласно следующему правилу:

у, = Ек (х,), 0 < /' < «,

Ек :у —? (/ + А)(тос1«), 0 < К < «?,

где у — числовой код буквы открытого текста;у + К — числовой код соответствующей буквы шифртекста.

Схема подстановки Е

Рис. 5.7. Схема подстановки Ек

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

Достоинством системы шифрования Цезаря является простота шифрования и расшифрования. К недостаткам системы Цезаря следует отнести:

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

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

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

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

Система Цезаря с ключевым словом является одноалфавитной системой подстановки. Особенностью этой системы является использование ключевого слова для смещения и изменения порядка символов в алфавите подстановки.

Выберем некоторое число 0 < К< 25 и слово или короткую фразу в качестве ключевого слова. Желательно, чтобы все буквы ключевого слова были различными. Пусть выбрано слово DIPLOMATв качестве ключевого слова и число к — 5.

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

Таблица 5.2

Исходный алфавит и ключевое слово

0

5

10

15

20

25

А

В

С

D

Е

F

Q

Н

I

J

К

L

М

N

О

Р

Q

R

S

т

и

V

W

X

Y

Z

D

I

Р

L

О

м

А

Т

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

Таблица 5.3

Измененный алфавит для осуществления подстановки

0

5

10

15

20

25

А

В

с

D

Е

F

Q

Н

I

J

К

L

М

N

О

Р

Q

R

S

T

U

V

W

X

Y

Z

V

W

X

Y

Z

D

I

Р

L

О

м

А

т

В

с

Е

F

G

H

J

K

N

Q

R

S

U

Теперь имеем подстановку для каждой буквы произвольного сообщения. Возьмем исходным следующее сообщение: SEND MORE MONEY. Тогда в соответствии с табл. 5.3 исходное сообщение зашиф-руется и будет выглядеть как HZBY TCGZ TCBZS.

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

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

Данные о распределениях вероятностей букв в русском и английском текстах приведены в табл. 5.4 и 5.5.

Таблица 5.4

Распределение вероятностей букв в русских текстах

Буква

Вероят

ность

Буква

Вероят

ность

Буква

Вероят

ность

Буква

Вероят

ность

Пробел

0,175

P

0,040

Я

0,018

X

0,009

О

0,090

B

0,038

БІ

0.016

ж

0,007

E

0,072

Л

0,035

3

0,016

ю

0,006

A

0,062

K

0,028

ъ

0,014

ш

0,006

И

0,062

M

0,026

Б

0,014

ц

0,004

H

0,053

Д

0,025

Г

0,013

щ

0,003

T

0,053

П

0,023

Ч

0,012

э

0,003

C

0,045

y

0,021

О

и

0,010

ф

0,002

Буквы в таблицах 5.4 и 5.5 указаны в порядке убывания вероятности их появления в тексте. Например, русская буква Е встречается в 36 раз чаще, чем буква Ф, а английская буква Е встречается в 123 раза чаще, чем буква Z

Шифруя букву исходного сообщения, выбирают случайным образом одну из ее замен. Замены (часто называемые омофонами) могут быть представлены трехразрядными числами от 000 до 999. Например, в английском алфавите букве Еприсваиваются 123 случайных номера, буквам В и С — по 16 номеров, а буквам J и Z— по 1 номеру. Если омофоны (замены) присваиваются случайным образом различным появлениям одной и той же буквы, тогда каждый омофон появляется в шифргексте равновероятно.

Таблица 5.5

Распределение вероятностей букв в английских текстах

Буква

Вероятность

Буква

Вероятность

Буква

Вероятность

Е

0,123

L

0,040

В

0,016

Т

0,096

D

0,036

G

0,016

А

0,081

С

0,032

V

0,009

О

0,079

и

0,031

К

0.005

N

0,072

Р

0,023

Q

0.002

I

0,071

F

0,023

X

0.002

S

0,066

М

0,022

J

0,001

R

0,060

W

0,020

Z

0,001

Н

0,051

Y

0,019

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

Шифр гаммирования. Гаммирование {gammaxoring) — метод шифрования, основанный на «наложении» гамма-последовательности на открытый текст. Обычно это суммирование в каком-либо конечном поле (например, в поле GF{2) такое суммирование принимает вид обычного «исключающего ИЛИ»). При расшифровании операция проводится повторно, в результате получается открытый текст.

Алгоритм шифрования в режиме гаммирования по ГОСТ 28147— 89 является реализацией режима обратной связи по выходу блочного шифра и позволяет обеспечить помехоустойчивую шифрованную связь при передаче данных по каналам связи с ошибками, так как размножения ошибок при расшифровании не происходит. Для исключения снижения криптостойкости при повторном использовании одного и того же оперативного ключа необходимо в каждом сеансе связи использовать неповторяющуюся синхропосылку. Алгоритм шифрования в режиме гаммирования при возможности ими-товоздействия со стороны нарушителя необходимо использовать совместно с алгоритмом выработки имитоставки.

Процедура гаммирования на передаче и приеме представлена на рис. 5.8.

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

  • — для каждого сообщения необходимо использовать новую гамму шифрующую (повторное использование гаммы недопустимо);
  • — для формирования гаммы необходимо использовать аппаратные генераторы случайных чисел на основе физических процессов;
  • — длина шифрующей гаммы должна быть не менее длины защищаемого сообщения.

Передатчик

Приемник

Процедура шифрования, основанная на «наложении» гамма-последовательности на открытый текст

Рис. 5.8. Процедура шифрования, основанная на «наложении» гамма-последовательности на открытый текст

Шифр блочной замены. При блочной замене шифрование открытого текста производится блоками. Например, блоку «АБА» может соответствовать «РТК», а блоку «АББ» — «СЛЛ».

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

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

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

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

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

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

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

Блочные же шифры не обладают таким устройством запоминания своего предыдущего состояния. Криптографическое преобразование данных они осуществляют в зависимости от итерационных подключей, которые вырабатываются из главного ключа. И шифрование строится только на основе ключевой последовательности и криптог-рафичеких примитивов. То есть блочный шифр может сгенерировать все необходимые ему для работы подключи сразу, и зависеть они будут только от исходной ключевой последовательности. Хотя здесь опять возникает некоторая неопределенность, если рассматривать существующие блочные шифры, для которых описаны алгоритмы работы в режиме поточного гаммирования, — это, например, ГОСТ 28147—89 и DES. В таком случае, будучи, например, использованным в режиме гаммирования с обратной связью, блочный шифр работает как поточный.

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

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

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

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

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

Примером шифра простой замены может служить программа ЛО Л 3, которую обычно можно найти в операционной системе UNIX. С ее помощью буква Л открытого текста на английском языке заменяется на букву /V, В — на О и так далее. Таким образом, ЛОЛ 3 циклически сдвигает каждую букву английского алфавита на 13 позиций вправо. Чтобы получить исходный открытый текст надо применить функцию шифрования ЛОЛ 3 дважды:

Р= ЛОЛЗ(ЛОЛЗ(Л)). (5.3)

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

Разновидностью шифра замены можно считать код, который вместо букв осуществляет замену слов, фраз и даже целых предложений. Например, кодовый текст «ЛЕДЕНЕЦ» может соответствовать фразе открытого текста «ПОВЕРНУТЬ ВПРАВО НА 90°». Однако коды применимы только при определенных условиях: если, например, в коде отсутствует соответствующее значение для слова «МУРАВЬЕД», то вы не можете использовать это слово в открытом тексте своего сообщения, предназначенном для кодирования.

Рассмотрим, как обычно практически выполняется шифрование заменой с помощью ЭВМ. Самый простой и эффективный способ сделать текст нечитаемым — спрятать его, смешав с последовательностью случайных чисел, заданной ключом, с помощью операции ХОЯ. Операция ХОВ выполняет следующие действия: (ОАОЛО) = О, (ОЛОЛ1) = 1, (1АОЛО) = 1, (1 Х(Ж) = 0. При этом информация сообщения прячется в шуме — самом информативном, по определению

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

Более того, если биты в используемой для шифрования случайной последовательности статистически независимы друг от друга, то и в шифровке они становятся такими же. Текст превращается во что угодно, т.е. в шум. Из-за специфики операции ХОЯ процедура шифрования совпадает с процедурой расшифрования. Например, обозначив через ґ вектор бит сообщения, через у вектор случайной последовательности и через ^ вектор шифровки, получаем:

ї = зХОЯу и 5 = їХОЯу. (5.4)

У машинного многоалфавитного шифра замены с помощью операции ХОЯ есть ряд очень слабых мест, которые нужно знать и учитывать при использовании этого шифра. Серьезную неприятность может доставить обратимость этого шифра, так как для расшифровки применяется то же самое преобразование, что и для зашифровки. В том случае, если одно и то же сообщение должно быть послано нескольким адресатам и шифруется одним и тем же шифром, может произойти так, что длина сообщения изменится из-за сбоя или ошибки. В этом случае будет получено 2 сообщения разной длины. Так, если имеем две шифровки $'и 5", которые отличаются тем, что исходный текст сообщения оказался сдвинутым на один символ:

ЯО = ДО + ПО; 5"(/ + 1) = Д/ + 1) + Ці), (5.5)

где / — текст, а у — ключ, то, находя их сумму, получим сумму текста со сдвигом:

5(0 = Я0 + 5"(/ + 1) = ДО + Ш + 1). (5.6)

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

Дл) = 5() + 5| + 52 + ... + 5/;. (5.7)

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

и передать искаженную шифровку по каналу связи.

Получатель, расшифровав ее

5’ + у = $ + Г + у = 7 + у+ у =/, (5.9)

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

Аналоговое скремблирование. Среди современных устройств закрытия речевых сигналов наибольшее распространение имеют устройства, использующие метод аналогового скремблирования [32—34]. Применение метода аналогового скремблирования позволяет реализовать устройства защиты информации с низкой стоимостью в стандартных телефонных каналах с полосой частот 0,3—3,4 кГц, при этом обеспечивается коммерческое качество дешифрованной речи и гарантируется достаточно высокая степень закрытия речи.

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

  • 1. Скремблирование в частотной области: частотная инверсия (преобразование спектра сигнала с помощью гетеродина и фильтра), частотная инверсия и смещение (частотная инверсия с меняющимся скачкообразно смещением несущей частоты), разделение полосы частот речевого сигнала на ряд поддиапазонов с последующей их перестановкой и инверсией.
  • 2. Скремблирование во временной области — разбиение фрагментов на сегменты с перемешиванием их по времени с последующим прямым и (или) инверсным считыванием.
  • 3. Комбинация временного и частотного скремблирования.

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

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

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

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

По режиму работы аналоговые скремблеры можно разбить на два класса:

  • — статические системы, схема кодирования которых остается неизменной в течение всей передачи речевого сообщения;
  • — динамические системы, постоянно генерирующие кодовые подстановки в ходе передачи (код может быть изменен в процессе передачи в течение каждой секунды).

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

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

Считается, что использовать амплитуду нецелесообразно, так как изменяющиеся во времени соотношения сигнал/шум делают чрезвычайно сложной задачу точного восстановления амплитуды сигнала. Поэтому практическое применение получили только частотное и временное скремблирование, а также их комбинации. В качестве вторичных ступеней скремблирования в таких системах могут использоваться некоторые виды амплитудного скремблирования [32— 34].

Существует два основных вида частотных скремблеров — инверсные и полосовые. Оба основаны на преобразованиях спектра исходного речевого сигнала для сокрытия передаваемой информации и восстановления полученного сообщения путем обратных преобразований.

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

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

Амплитуда

  • - -
  • 0,3 3,0 Г, кГц 0,3 3,0 Г, кГц

Рис. 5.9. Принцип работы инверсного скремблера

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

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

А, амплитуда

Принцип работы четырехполосного скремблера

Рис. 5.10. Принцип работы четырехполосного скремблера

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

Существенное повышение степени закрытия речи может быть достигнуто путем реализации в полосовом скремблере быстрого преобразования Фурье (БПФ). При этом количество допустимых перемешиваний частотных полос значительно увеличивается, что обеспечивает высокую степень закрытия без ухудшения качества речи [32—341. Можно дополнительно повысить степень закрытия путем осуществления задержек различных частотных компонент сигнала на разную величину. Схема такой системы показана на рис. 5.11.

Главным недостатком использования БПФ является возникновение в системе большой задержки сигнала (до 300 м/с), обусловленной необходимостью использования весовых функций. Это приводит к затруднениям в работе дуплексных систем связи.

Временные скремблеры основаны на двух основных способах закрытия: инверсии по времени сегментов речи и их временной перестановке. По сравнению с частотными скремблерами задержка у временных скремблеров намного больше, но существуют различные методы ее уменьшения [32—34].

Схема полосового скремблера быстрого преобразования

Рис. 5.11. Схема полосового скремблера быстрого преобразования

Фурье

В скремблерах с временной инверсией речевой сигнал делится на последовательность временных сегментов, каждый из которых передается инверсно во времени — с конца. Такие скремблеры обеспечивают ограниченный уровень закрытия, зависящий от длительности сегментов. Для достижения неразборчивости медленной речи необходимо, чтобы длина сегментов составляла около 250 мс. Задержка системы в таком случае составляет около 500 мс, что может оказаться неприемлемым в некоторых приложениях.

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

1

2

3

4

5

6

0

/

4

1

5

3

6

2

0

/

Рис. 5.12. Схема работы временного скремблера с перестановками

в фиксированном кадре

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

Главный недостаток скремблера с фиксированным кадром — большая величина времени задержки (приблизительно 2 кадра). Этот недостаток устраняется в скремблере с перестановкой временных отрезков речевого сигнала со скользящим окном. В нем количество перестановок ограничено таким образом, чтобы задержка не превышала установленного максимального значения. Каждый отрезок исходного речевого сигнала как бы имеет временное окно, внутри которого он может занимать произвольное место при скремблировании. Это окно скользит во времени по мере поступления в него каждого нового отрезка сигнала. Задержка при этом снижается до длительности окна.

Используя комбинацию временного и частотного скремблирования, можно значительно повысить степень закрытия речи. Комбинированный скремблер намного сложнее обычного и требует компромиссного решения по выбору уровня закрытия, остаточной разборчивости, времени задержки, сложности системы и степени искажений в восстановленном сигнале [32—341. Количество же всевозможных систем, работающих по такому принципу, ограничено лишь воображением разработчиков.

В качестве примера такой системы рассмотрим скремблер, схема которого представлена на рис. 5.13.

Исходная Восстанов-

Блок-схема комбинированного скремблера

Рис, 5.13. Блок-схема комбинированного скремблера

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

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

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

Амплитуда

1

2

3

4

5

5

13

18

16

15

6

7

8

9

10

3

8

2

12

6

11

12

13

14

15

10

7

1

14

19

16

17

18

19

20

9

20

4

11

17

0,3 3,0 Г, кГц 0,3 3,0 Г кГц

Рис. 5.14. Принцип работы комбинированного скремблера

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

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

Цифровое шифрование. Альтернативным аналоговому скремблированию речи является шифрование речевых сигналов, преобразованных в цифровую форму, перед их передачей. Этот метод обеспечивает более высокий уровень закрытия по сравнению с описанными выше аналоговыми методами [32—34]. В основе устройств, работающих по такому принципу, лежит представленный речевой сигнал в виде цифровой последовательности, закрываемой по одному из криптографических алгоритмов. Передача данных, представляющих дискретизированные отсчеты речевого сигнала или его параметров, по телефонным сетям, как и в случае устройств шифрования алфавитно-цифровой и графической информации, осуществляется через устройства, называемые модемами.

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

Ширину спектра речевого сигнала можно считать приблизительно равной 3,3 кГц, а для достижения хорошего качества восприятия необходимо соотношение сигнал/шум примерно 30 дБ. Тогда согласно теории Шеннона требуемая скорость передачи дискретизированной речи будет соответствовать величине 33 кбит/с.

С другой стороны, речевой сигнал представляет собой последовательность фонем, передающих информацию. В английском языке, например, около 40 фонем, в немецком — около 70 и т.д. Таким образом, для представления фонетического алфавита требуется примерно 6—7 бит. Максимальная скорость произношения не превышает 10 фонем в секунду. Следовательно, минимальная скорость передачи основной технической информации речи — не ниже 60—70 бит/с.

Сохранение формы сигнала требует высокой скорости передачи и, соответственно, использования широкополосных каналов связи [35, 361. Так, при импульсно-кодовой модуляции (ИКМ), используемой в большинстве телефонных сетей, необходима скорость передачи, равная 64 кбит/с. В случае применения адаптивной дифференциальной ИКМ скорость понижается до 32 кбит/с и ниже. Для узкополосных каналов, не обеспечивающих такие скорости передачи, требуются устройства, снижающие избыточность речи до ее передачи. Снижение информационной избыточности речи достигается параметризацией речевого сигнала, при которой сохраняются существенные для восприятия характеристики речи.

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

Чем короче интервал анализа, тем точнее можно представить динамику речи, но при этом должна быть выше скорость передачи данных. В большинстве случаев на практике используются 20-миллисекунд-ные интервалы, а скорость передачи достигает 2400 бит/с.

Наиболее распространенными типами вокодеров являются полосные и с линейным предсказанием. Целью любого вокодера является передача параметров, характеризующих речь и имеющих низкую информационную скорость. Полосный вокодер достигает эту цель путем передачи амплитуды нескольких частотных полосных речевого спектра. Каждый полосовой фильтр такого вокодера возбуждается при попадании энергии речевого сигнала в его полосу пропускания. Так как спектр речевого сигнала изменяется относительно медленно, набор амплитуд выходных сигналов фильтров образует пригодную для вокодера основу. В синтезаторе параметры амплитуды каждого канала управляют коэффициентами усиления фильтра, характеристики которого подобны характеристикам фильтра анализатора. Таким образом, структура полосового вокодера базируется на двух блоках фильтров — для анализа и для синтеза. Увеличение количества каналов улучшает разборчивость, но при этом требуется большая скорость передачи. Компромиссным решением обычно становится выбор 16—20 каналов при скорости передачи данных около 2400 бит/с.

Полосовые фильтры в цифровом исполнении строятся на базе аналоговых фильтров Баттерворта, Чебышева, эллиптических и др. [30, 32—34,40]. Каждый 20-миллисекундный отрезок времени кодируется 48 битами, из них 6 бит отводится на информацию об основном тоне, один бит — на информацию «тон—шум», характеризующую наличие или отсутствие вокализованного участка речевого сигнала, остальные 41 бит описывают значения амплитуд сигналов на выходе полосовых фильтров.

Существуют различные модификации полосного вокодера, приспособленные для каналов с ограниченной полосой пропускания. При отсутствии жестких требований на качество синтезированной речи удается снизить количество бит передаваемой информации с 48 до 36 на каждые 20 мс, что обеспечивает снижение скорости до 1200 бит/с. Это возможно в случае передачи каждого второго кадра речевого сигнала и дополнительной информации о синтезе пропущенного кадра. Потери в качестве синтезированной речи от таких процедур не слишком велики, достоинством же является снижение скорости передачи сигналов.

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

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

В вокодере с линейным предсказанием речевая информация передается тремя параметрами: амплитудой, решением «тон/шум» и периодом основного тока для вокализованных звуков [30, 32—34,40]. Так, согласно федеральному стандарту США период анализируемого отрезка речевого сигнала составляет 22,5 мс, что соответствует 180 отсчетам при частоте дискретизации 8 кГц. Кодирование в этом случае осуществляется 54 битами, что соответствует скорости передачи 2400 бит/с. При этом 41 бит отводится на кодирование десяти коэффициентов предсказания, 5 — на кодирование величины амплитуды, 7 — на передачу периода основного тона и 1 бит определяет решение «тон/шум». При осуществлении подобного кодирования предполагается, что все параметры независимы, однако в естественной речи параметры коррелированы, и возможно значительное снижение минимально допустимой скорости передачи данных без потери качества, если правило кодирования оптимизировать с учетом зависимости всех параметров. Такой подход известен под названием векторного кодирования. Его применение к вокодеру с линейным предсказанием позволяет снизить скорость передачи данных до 800 бит/с и менее с небольшой потерей качества.

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

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

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

Упрощенная структурная схема аппаратуры цифрового шифрования речи представлена на рис. 5.15.

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

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

Структурная схема аппаратуры цифрового шифрования речи

Рис. 5.15. Структурная схема аппаратуры цифрового шифрования речи

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

Физическое распределение. С помощью доверенных курьеров или вооруженной охраны ключи могут рассылаться традиционным физическим путем. До 70-х гг. XX в. это действительно был единственный безопасный путь распределения ключей при установке системы. Ему сопутствовал ряд трудностей, в особенности при расширении, масштабировании (модульном наращивании системы в рамках унифицированной архитектуры) криптосистемы, но основной недостаток, связанный с таким способом распределения, состоит в том, что криптостойкость системы зависит не столько от ключа, сколько от курьера. Если подкупить, похитить или просто убить курьера, то система будет скомпрометирована.

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

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

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

друг с другом, необходимо -— -разных секретных ключей. С рос

том и возникает проблема управления огромным числом ключей. Например, для небольшого университета с 10 тыс. студентов нужно около 50 млн отдельных секретных ключей. С большим количеством уже существующих ключей связано много проблем. Например, к чему приведет компрометация ключа конкретного пользователя? Другими словами, кто-то посторонний нашел ключ конкретного пользователя. Что следует предпринять в связи с этим? Поэтому большое число ключей порождает сложную проблему управления ими [40. 44—47J.

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

Протокол распределения ключей Диффи—Хеллмана. Данный протокол позволяет пользователям обмениваться ключами по открытым (незащищенным) каналам связи. Сформированный таким образом общий секретный ключ используется для симметричного шифрования. Генерация общего ключа шифрования проводится только для пары абонентов сети. Схема данного способа проиллюстрирована на рис. 5.16.

Безопасность протокола обусловлена трудностью вычисления дискретных логарифмов в конечном поле, в отличие от легкости решения прямой задачи дискретного возведения в степень в том же конечном поле. Схема открытого распределения ключей Диффи— Хеллмана заключается в следующем (рис. 5.17). Каждой паре пользователей в открытом виде рассылаются большие простые числа Р и X: Р — модуль расчетов, X — любое простое число от 2 до р— 1. Числа Р и X могут не храниться в секрете. Как правило, эти значения являются общими для всех пользователей сети.

Пользователи А и В генерируют независимо друг от друга свои секретные ключи ха и хь (случайные большие целые числа).

Затем пользователь А вычисляет на основании своего секретного ключа ха открытый ключ каку„ = Xх“ mod Р.

Пользователь В производит аналогичные вычисления уь = = Xxb mod Р.

м

ключами

Рис. 5.16. Схема симметричного шифрования секретным ключом, сформированным по протоколу Диффи-Хеллмана (М — открытое

сообщение, Е — криптограмма)

Схема открытого распределения ключей Диффи-Хеллмана

Рис. 5.17. Схема открытого распределения ключей Диффи-Хеллмана

Затем пользователи/! и В обмениваются своими открытыми ключами уа и уь по незащищенному каналу и используют их для вычисления общего ключа. Пользователь Л вычисляет: КаЬ = ybXa mod Р = (kXh)Xa mod Р.

Пользователь В вычисляет: КЬа = yXb mod Р = (XXa)Xb mod Р.

Как видим, КаЬ = КЬа, общий секретный ключ получен.

Злоумышленник, перехвативший значения открытых ключейуа и уь, не может вычислить общий ключ КаЬ, потому что он не имеет соответствующих значений секретных ключей Ха и Хь. Благодаря ис- пользованию однонаправленной функции операция вычисления открытого ключа необратима, т.е. невозможно по значению открытого ключа абонента вычислить его секретный ключ.

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

Протокол Диффи—Хеллмана дает возможность шифровать данные при каждом сеансе связи на новых ключах. Это позволяет не хранить секреты на дискетах или других носителях. Не следует забывать, что любое хранение секретов повышает вероятность попадания их в руки конкурентов или противника.

Пример.

Пусть р = 31Д = 7.

Пользователь А выбрал ха = II.

Пользователь В выбрал xh= 13.

Затем пользователь А вычисляет свой открытый ключ как уа = = Xх“ mod p = lu mod 31 =20.

Пользователь В вычисляет свой открытый ключ как уь = = Xxb mod р = 713 mod 31 = 19.

Затем оба пользователя вычисляют общий секретный ключ.

Пользователь A: Kab = {yb)Xa mod р = 19й mod 31 = 10.

Пользователь В: Kba = (ya)Xb mod р = 2013 mod 31 = 10.

Общий ключ сформирован и равен 10.

Шифр RSA. В 1978 г. появилась работа, в которой Рон Райвест {Ron Rivest), Ади Шамир {Adi Shamir) и Лен Адлеман {Len Adleman) предложили алгоритм с открытым ключом. Схема Райвеста—Шами-ра—Адлемана (/?5Л) получила широкое распространение.

Опишем процесс шифрования. Исходный текст должен быть переведен в числовую форму, этот метод считается известным. В результате этого текст представляется в виде одного большого числа. Затем полученное число разбивается на части (блоки) так, чтобы каждая из них была числом в промежутке [0, N— 1] (о выборе N см. ниже). Процесс шифрования одинаков для каждого блока. Поэтому мы можем считать, что блок исходного текста представлен числом х, 0 1. Каждый абонент вырабатывает свою пару ключей. Для этого он генерирует два больших простых числа/? и q, вычисляет произведение

N = p ? q. Затем он вырабатывает случайное число в, взаимно простое со значением функции Эйлера от числа N, ф(N) = (р — 1) ? (q — 1) и находит число d из условия в • d = 1 (mod ф(N)). Так как (е, ф(Л0) — 1, то такое число d существует, и оно единственно. Пару (N, е) он объявляет открытым ключом и помещает в открытый доступ. Пара (N, d) является секретным ключом. Для расшифрования достаточно знать секретный ключ. Числа p, q, ф(Л0 в дальнейшем не нужны, поэтому их можно уничтожить.

Пользователь А, отправляющий сообщение х абоненту В, выбирает из открытого каталога пару (N, е) абонента В и вычисляет шифрованное сообщение у = хе(mod N). Чтобы получить исходный текст, абонент В вычисляет/^mod N). Так как е ? d = 1 (mod ф(/V)), т.е. е • d = — ф(Л0 • к + , где к — целое, то, применяя теорему Эйлера, получается следующее соотношение: /= (jf)d = jfd = jflW-к+ i = (^(^.x=x(mod N). (5.10)

Пример.

Пусть p = 7, q = 17. Тогда N =7 • 17 = 119, ф(Л0 = 96. Выбираем значение е:е 96, (е, 96) = 1. Пусть в нашем случае е = 5. Находим d d= l/c(mod 96). Получаем d= 77, так как 77 • 5 = 4 • 96 + 1. Открытый ключ(119,5), личный ключ(119,77). Пустьх= 19. Для зашифрования число 19 возводим в 5-ю степень по модулю 119, тогда имеем 195 = = 2 476 099 и остаток от деления 2 476 099 на 119 равен 66. Итак, у = = 191 mod 119 = 66, а расшифрование х = 667 mod 119= 19. Как шифрование, так и расшифрование в RSA предполагают использование операции возведения целого числа в целую степень по модулю N. Если возведение в степень выполнять непосредственно с целыми числами и только потом проводить сравнение по модулю N, то промежуточные значения окажутся огромными. Здесь можно воспользоваться свойствами арифметики в классах вычетов (a mod N) • • (b mod N) mod N = (ab) mod N. Таким образом, можно рассмотреть промежуточные результаты по модулю N. Это делает вычисления практически выполнимыми.

Безопасность алгоритма /??/1 основана на трудоемкости разложения на множители больших чисел. Современное состояние технических средств разложения на множители таково, что число, содержащее 193 десятичных знака, факторизовано в 2005 г. Следовательно, выбираемое N должно быть больше. Большинство общепринятых алгоритмов вычисления простых чисел р и q носят вероятностный характер.

Для работы алгоритма RSA нужны простые числа. Наиболее приемлемым является генерация случайных чисел и последующая проверка их на простоту. Существуют вероятностные тесты, определяющие с заданной степенью достоверности факт простоты числа. Возникает вопрос, что произойдет, если числа окажутся составными? Можно свести вероятность такого события до приемлемого минимума, используя тесты на простоту. Кроме того, если такое событие произойдет, это будет быстро обнаружено — шифрование и расшифрование не будут работать.

Кроме разрядности р и q, к ним предъявляются следующие дополнительные требования:

  • — числа не должны содержаться в списках известных больших простых чисел;
  • — они не должны быть близкими, так как иначе можно воспользоваться для факторизации N методом Ферма и решить уравнение

Ч

Р + Я

-N =

{ 2

р-я

V

/

/

— в алгоритме RSA всегда есть эквивалентные по расшифрованию показатели степеней, например с1 и с1' = с! + я ~ 1]. При этом эквивалентных решений тем больше, чем больше {р— , я — 1)• В лучшем случае — 1 ,я~ 1) = 2,р = 21 + 1, д = 2.? + 1, где/ — нечетные числа с условием (5, 0 = 1.

Чтобы исключить возможность применения методов факторизации, накладывают следующее ограничение: числа р— 1 ,р + 1 ,я~ 1, + 1 не должны разлагаться в произведение маленьких простых множителей, должны содержать в качестве сомножителя хотя бы одно большое простое число. В 1978 г. Райвест сформулировал наиболее

р-1 р+1 q-

сильные требования. Числа р{ --, р~, --, ср --, д2 =- должны быть простыми, причем числа т?! — 1 и <7j — 1 не должны разлагаться в произведение маленьких простых.

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

Однако выбор малых параметров е или с! представляется небезопасным по ряду соображений. Если малым является секретный параметр с1, то можно применить метод перебора малых значений до получения искомого числа с1. А если малым является параметр е, то достаточно большое число открытых сообщений, удовлетворяющих неравенству х < /а , будет зашифровываться простым возведением в степень у = хДтос1 А), и поэтому их можно найти путем извлечения корня степени е.

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

Сначала нужно каким-либо способом представить текст сообще-ния в виде упорядоченного набора чисел по модулю N. Это еще не процесс шифрования, а только подготовка к нему.

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

Таблица 5.6

Номера букв при осуществлении замены

А

Б

В

Г

д

Е

ж

3

И

&#

и

К

Л

М

Н

О

П

Р

С

10

11

12

13

14

15

16

17

18

19

20

21

22

23

24

25

26

27

т

У

Ф

X

ц

Ч

ш

Щ

Ъ

Ы

Ь

Э

Ю

Я

28

29

30

31

32

33

34

35

36

37

38

39

40

41

Пробел между словами будем заменять числом 99.

Например, пусть открытый текст — это девиз «П 03Н АЙ СЕ БЯ ». Тогда его цифровое представление имеет вид: 2524172310199927151141.

Пусть в нашем примере/? = 149,

2524- 1723 - 10199- 9271 - 511 -41.

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

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

Обратим внимание на то, что в этом примере каждая буква кодируется двузначным числом. Это сделано для предотвращения неоднозначности. Если пронумеровать буквы не по порядку, начиная с 1, т.е. А соответствует 1, Б соответствует 2 и т.д., то будет непонятно, что обозначает блок 12: пару букв АБ или букву Л, двенадцатую букву алфавита. Конечно, для кодирования можно использовать любые однозначные соответствия между буквами и числами, например ASCII-кодировку, что чаще всего и делается.

Продолжим пример. Выбираемр — 149,q = 157, вычисляем ф(N) = = 23088. Теперь нужно выбрать число е, взаимно простое с ф(А). Наименьшее простое, не делящее ф(А9, равно 5. Положим е = 5. Зашифруем первый блок сообщения: вычисляем 2524^ mod 23393 = 22752; далее 17235 mod 23393 = 6198,

  • 101995 mod 23393 = 14204,
  • 92715 mod 23393 = 23191,
  • 5 ll5 mod 23393 = 10723,
  • 415 mod 23393 = 14065.

Теперь шифрованный текст имеет вид 22752619814204231911072314065.

В нашем примере N = 23393, е = 5. Применив алгоритм Эвклида к числам ф(А) = 23 088 ие = 5, найдем d = е~х mod 23088 = 13853. Значит, для расшифровки блоков шифртекста необходимо возвести этот блок в степень 13583 по модулю 23393. В примере первый блок шифртекста — число 22752, тогда получим 2275213853 mod 23393 = = 2524.

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

Криптографический стандарт шифрования данных DES (DES — Data Encryption Standard) принят в США в 1977 г. в качестве федерального. В стандарт входит описание блочного шифра типа шифра Фай-стеля, а также различных режимов его работы как составной части нескольких процедур криптографического преобразования данных. Обычно под аббревиатурой /ЖУпонимается именно блочный шифр, который в стандарте соответствует процедуре шифрования в режиме электронной кодовой книги (ЕСВ — Electronic Codebook Mode). Название вызвано тем, что любой блочный шифр является простым подстановочным шифром и в этом отношении подобен кодовой книге [50-54J.

Рассмотрим принцип работы блочного шифра. Входом яблочный шифр и результатом его работы является блок длины п — последовательность, состоящая из п бит. Число п постоянно. При необходимости шифрования сообщения длиной, большей л, оно разбивается на блоки, каждый из которых шифруется отдельно. Различные режимы работы связаны с дополнительными усложнениями блочного шифра при переходах от блока к блоку. В стандарте DES длина блока п = 64.

В режиме ЕС В шифрование блока открытого текста В производится за 16 однотипных итераций, именуемых циклами. Схема преобразования приведена на рис. 5.17. Блок рассматривается как конкатенация (сцепление) двух подблоков равной длины: В = (L, R). На каждом цикле применяется свой ключ (2Q, обычно вырабатываемый из некоторого основного ключа (X). Ключи, используемые в циклах, называются подключами.

Основным элементом шифра является несекретная цикловая функция вида Y=flR, X). Входом в цикл является выход из предыдущего цикла. Если упомянутый вход имеет вид (L, R), то выход имеет вид (/?, L Ф f(/?, X)), где © — поразрядное сложение по модулю 2. Например, для выхода цикла с номером / это означает: /?, = Li_l 0

ss, Rj-1 ? Xj), Lj — Rj_ j, (/— 1,..., 16).

В режиме ECB алгоритм DES зашифровывает 64-битовый блок за 16 циклов. Биты входного блока перед первым циклом переставляются в соответствии с табл. 5.7 в ходе так называемой начальной перестановки {IP — initial permutation). После выхода из последнего цикла LuR переставляются местами, после чего соединяются в блок. Биты полученного блока снова переставляются в соответствии с перестановкой 1Р~ обратной начальной. Результат принимается в качестве блока шифртекста.

Таблица 5.7

Начальная перестановка IP

58

50

42

34

26

18

10

2

60

52

44

36

28

20

12

4

62

54

46

38

30

22

14

6

64

56

48

40

32

24

16

8

57

49

41

33

25

17

9

1

59

51

43

35

27

19

11

3

61

53

45

37

29

21

13

5

63

55

47

39

31

23

15

7

На каждом цикле, как проиллюстрировано на рис. 5.18, из ключа Л'длиной 56 бит формируется ключ Х-, размером 48 бит. Сам ключ

II

о

R Lq®J{Rq, X)

г ,

" ^15 ^14 ^15 L]4 ©У(/?14, А) * 1

?

Л16

5-- Лл|5;л)

Рис. 5.18. Блок-схема работы алгоритма DES

X размещается в восьмибайтовом слове, причем восьмые разряды каждого байта являются контрольными и в ключ не входят. Перед шифрованием в соответствии с процедурой выбора PC 1, представленной в табл. 5.8, из Xвыбираются 56 бит, которыми заполняются

г

1

^16 - ЛІ5

R

^16

3

р

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

Преобразование PC 1

Таблица 5.8

Заполнение С

Заполнение D

57

49

41

33

25

17

9

63

55

47

39

31

23

15

1

58

50

42

34

26

18

7

62

54

46

38

30

22

10

2

59

51

43

35

27

14

6

61

53

45

37

29

19

11

3

60

52

44

36

21

13

5

28

20

12

4

После сдвига оба подблока объединяются в порядке (С, О). Затем, в соответствии с функцией выбора РС2, представленной в табл. 5.9, из них выбираются 48 бит подключа Х{. Шифрование и расшифровывание отличаются направлением сдвигов, представленных в табл. 5.10.

Преобразование PC2

Таблица 5.9

14

17

11

24

1

5

3

28

15

6

21

10

23

19

12

4

26

8

16

7

27

20

13

2

41

52

31

37

47

55

30

40

51

45

33

48

44

49

39

56

34

53

46

42

50

36

29

32

Таблица 5.10

Соответствие сдвигов номерам циклов DES

Номер цикла

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

Сдвиг влево (шифрование)

1

1

2

2

2

2

2

2

1

2

2

2

2

2

2

1

Сдвиг вправо (расшифровывание)

1

1

2

2

2

2

2

2

1

2

2

2

2

2

2

1

В обобщенном виде алгоритм формирования подключей для криптоалгоритма DES представлен на рис. 5.19.

Алгоритм формирования подключей

Рис. 5.19. Алгоритм формирования подключей

Выбор битов по табл. 5.8 и 5.9 из соответствующих блоков производится следующим образом. Таблица рассматривается как последовательность ее строк, записанных друг за другом, начиная с первой строки. Биты блока данных соответствующей длины нумеруются слева направо, начиная с единицы. Каждый элемент 5 таблицы рассматривается как номер бита 6У в блоке данных. Преобразование заключается в замене всех элементов я на биты Ьу

Цикловая функция производит следующие действия:

  • 1. Расширение блока до 48 бит за счет повторения битов блока с помощью функции расширения ЕР, представленной в табл. 5.11.
  • 2. Поразрядное сложение результата с ключом
  • 3. Преобразование полученной суммы с помощью замены (используя так называемые .5-блоки), в результате которого получается блок длиной 32 бит.
  • 4. Применение перестановки Р, представленной в табл. 5.12, дает значение функции У=/(Я, X).

Преобразование, с помощью которого 48-разрядный блок преобразуется в 32-разрядный, сводится к выборке восьми тетрад из 8 таблиц (А-блоков) размером 4x16 (табл. 5.13). Из каждого А-блока выбирается одна тетрада. Для этого 48-разрядный блок делится последовательно на 8 комбинаций по 6 бит каждая. Первая комби-

Преобразование EP

Таблица 5.11

32

1

2

3

4

5

4

5

6

7

8

9

8

9

10

11

12

13

12

13

14

15

16

17

16

17

18

19

20

21

20

21

22

23

24

25

24

25

26

27

28

29

28

29

30

31

32

1

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

Таблица 5.12

16

7

20

21

29

12

28

17

1

15

23

26

5

18

31

10

2

8

24

14

32

27

3

9

19

13

30

6

22

11

4

25

нация (слева) является входом в первый 5-блок, вторая — во второй и т.д. При этом первый и последний биты комбинации задают номер строки, а остальные 4 бита — номер столбца 5-блока, на пересечении которого расположена соответствующая тетрада. Конкретные значения 5, (/' = 1,8) представлены в табл. 5.13.

Помимо режима ЕС В, алгоритм DES может использоваться в режиме сцепления блоков шифртекста (СВС — Cipher Block Chaining). Суть этого режима состоит в том, что сообщение разбивается на блоки по 64 бита, и их последовательность зашифровывается.

Таблицы S-блоков для алгоритма DES

Таблица 5.13

SI

0

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

0

14

4

13

1

2

15

11

8

3

10

6

12

5

9

0

7

1

0

15

7

4

14

2

13

1

10

6

12

11

9

5

3

8

2

4

1

14

8

13

6

2

11

15

12

9

7

3

10

5

0

3

15

12

8

2

4

9

1

7

5

11

3

14

10

0

6

13

S2

0

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

0

15

1

8

14

6

11

3

4

9

7

2

13

12

0

5

10

1

3

13

4

7

15

2

8

14

12

0

1

10

6

9

11

5

Окончание табл. 5.13

Перед шифрованием (в режиме ЕС В) блок открытого текста поразрядно складывается с предыдущим блоком шифртекста. Для шифрования первого блока шифртекста требуется так называемый вектор инициализации (IV — initialization vector). Последний не является секретным. Данный режим не позволяет накапливаться ошибкам при передаче, поскольку ошибка при передаче приведет к потере только двух блоков исходного текста. Кроме ЕСВ и СВС, существуют также режимы шифрования с обратной связью (СЕВCipher Feedbaac) и шифрования с внешней обратной связью (OFB — Output FeedhacK).

Стандарт криптографического преобразования данных ГОСТ 28147—89 рекомендован к использованию для защиты любых данных, представленных в виде двоичного кода. Данный стандарт формировался с учетом мирового опыта, и, в частности, при его разработке были приняты во внимание недостатки алгоритма DES. Стандарт довольно сложен, поэтому приведем лишь его концептуальное описание [47, 51—55].

В криптографическом стандарте ГОСТ 28147—89 используется симметричный алгоритм шифрования, т.е. ключ зашифровки совпадает с ключом расшифровки. Длина ключа — 256 бит, что обеспечивает очень большую криптостойкость алгоритма. По скорости алгоритм примерно равен скорости подобных алгоритмов (по крайней мере, имеет тот же порядок) или немного быстрее их. ГОСТ 28147—89 относится к блочным шифрам.

Ключом в данном алгоритме служит массив из восьми 32-битных чисел. Таким образом, длина ключа составляет 256 бит. Ключ можно представить как таблицу, в которой 8 строк и 32 столбца. Такая конфигурация ключа необходима для работы алгоритма.

Таблица замен — это долговременный ключевой элемент, который не изменяется в системе шифрования. Таблица замен состоит из 8 строк и 16 столбцов, в каждой ячейке таблицы хранится 4-битное число. Строки таблицы замен называют узлами замен, и на них накладывается ограничение, несоблюдение которого не влечет за собой неработоспособность алгоритма, но значительно снижает криптостойкость. Ограничение заключается в следующем: все числа в пределах одной строки (одного узла) таблицы замен должны быть различными, т.е. в каждой строке таблицы замен не должно быть повторяющихся чисел. С учетом этого каждая строка таблицы замен содержит произвольную перестановку чисел от 0 до 15.

Криптографический алгоритм, используемый в стандарте ГОСТ 28147—89, условно состоит из трех уровней. Основной шаг криптопреобразования — самый нижний уровень, на его основе строятся все более высокие части алгоритма. Отталкиваясь от основных шагов, строятся базовые циклы: цикл зашифрования (32-3), цикл расшифрования (32-Р) и цикл выработки имитовставки (16-3). На самой верхней ступени стоят собственно реальные алгоритмы или циклы (на самом деле стандарт ГОСТ 28147—89 содержит нс один, а несколько алгоритмов шифрования), которые строятся на основе базовых циклов.

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

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

Рассмотрим основные этапы и базовые циклы, используемые в криптографическом стандарте ГОСТ 28147—89.

Основной шаг криптопреобразования. На входе основного шага определяется 64-битный блок данных УУ= (УУ,, УУ2), где УУ, — младшая 32-битовая часть, а УУ2 — старшая 32-битовая часть. Обе части рассматриваются как отдельные 32-битовые числа. На вход основного шага также поступает один из восьми элементов ключа. 32-битовый элемент ключа обозначается за X. Далее производятся следующие действия:

  • 1.5=ЛУ1,(тоб 232).
  • 2. Число ,5разбивается на 8 частей: Зф 5], 52, ?3, ЗУ*, З^, 3'6, 57 по 4 бита каждая, где 3’0 — младшая, а 3'7 — старшая части числа ЗУ
  • 3. Для всех /' от 0 до 7: 3) = 717, 3)), где Т{А, Ь) означает ячейку таблицы замен с номером строки А и номером столбца Ь (счет с нуля).
  • 4. Новое число ЗУ полученное на предыдущем шаге циклически сдвигается в сторону старших разрядов на 11 бит.
  • 5. 3* = З1 хог УУ,, где хог — операция, исключающая ИЛИ.
  • 6. УУ2 = ТУ1.
  • 7. уу; = ЗУ

Как результат основного шага криптопреобразования возвращается блок данных N = (УУ,, УУ2), где УУ2 равно исходному ТУ,, а — результат преобразований основного шага.

Базовые циклы ГОСТ 28147—89 строятся из основных шагов криптопреобразования путем многократного их повторения с различными элементами ключа. Блок данных, с которым работает базовый цикл, поступает на его вход один раз в начале работы, а результатом базового цикла является преобразованный блок данных. Как и в основном шаге, 64-битный блок данных обозначим через УУ = (УУ,, УУ2), а элементы ключа через — Хс индексом, означающим номер элемента в ключевом массиве.

Берется блок данных УУ и начинается последовательная процедура основного шага криптопреобразования со следующими ключами:

1. Для цикла зашифрования (32-3): Х0, Х{, Х2, Х3, Х4, Х5, Х6, Х7, Xо, *2, Х3, Х4, Х5, *6, Хь Х0, ХЬХ2, Х3, Х4, Х5, Х6, Х7, Х7, Х6, Л”5, *4, ЗГ3, Хъ

ад-

  • 2. Для цикла расшифрования (32-Р): Х$, Хх, Х2, Х3, Х4, Х5, Хь, Х7, х7, Хв, 2Г5, Х4, Х3, Х2, ХЬХ0, Х7, Х6, Х5, Х4, 2Г3, Х2,2Г„ 2Г0, Х7,6, Х5, Х4, Х3, Х210.
  • 3. Для цикла выработки имиговставки (1б-3):2Г0, Х{, Х2, Х3, Х45,

Хв, Х7, ЛЬ, Ху,Х2, х3, х4, х5, х6, х7.

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

ГОСТ 28147—89 определяет три основных режима шифрования: простая замена, гаммирование и гаммирование с обратной связью и один дополнительный режим выработки имитовставки. Данные обрабатываются блоками по 64 бита, на которые разбивается массив, последний блок может быть неполным. В двух последних режимах имеется возможность обрабатывать неполный блок данных, в первом длина данных должна быть кратна 64-м битам.

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

ся блоками по 64 бита, и исходный текст постепенно заменяется шифрованным текстом, начиная от начала массива данных к концу массива данных.

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

Для выработки случайных 64-битных чисел в ГОСТ 28147—89 определен специальный математический генератор. Таким образом, шифрование и расшифровка данных в режиме гаммирования производится путем наложения зашифрованных псевдослучайных чисел.

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

ГОСТ 28147—89 определяет в качестве синхропосылки, или начального заполнителя, не само число, полученное из какого-либо источника (например, текущее время), а результат зашифровки этого числа по алгоритму зашифрования. Таким образом, используя текущее время или что-то иное в качестве начального заполнителя, необходимо это число предварительно зашифровать, а затем уже инициализировать им генератор.

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

Рекуррентный генератор последовательности чисел (РГПЧ) представляет собой генератор чисел, который используется при шифровании гаммированием. На каждом шаге он выдает 64-битное число, которое состоит из двух 32-битных чисел, которые генерируются отдельно. Фактически существуют два РГПЧ — для старшей и младшей частей.

Числа, которые выдает РГПЧ, обозначим через Q = (А, В), где А — младшая, а В — старшая части числа. Индекс числа Q обозначает номер шага, на котором числа получены, так, индекс і — 1 означает предыдущий шаг. 0О — синхропосылка или начальный заполнитель. Выработка происходит следующим образом:

Aj — Aj_x + Cj (mod 232), где Cl= 1010101,6.

В, = B,_x + C2 (mod 232 - 1), где C2 = 1010104l6.

Если Bj — 0, to Bj — 232 — I.

Число В не может получиться нулевым. Константы С, и С2 даны в шестнадцатеричной системе счисления.

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

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

Режим шифрования «выработка имитовставки». Имитовставка — это контрольная комбинация, зависящая от открытых данных и секретной ключевой информации. Целью использования имитовставки является обнаружение всех случайных или преднамеренных изменений в массиве данных. Для потенциального злоумышленника две следующие задачи практически неразрешимы, если он не владеет ключевой информацией: вычисление имитовставки для заданного открытого массива данных; подбор открытых данных под заданную имитовставку. Алгоритм выработки имитовставки выглядит следующим образом: l.S=0.

  • 2. Для каждого 64-битного блока данных из массива данных: S = F(S xor Tj), где Tj — блок данных, F — базовый цикл выработки имитовставки (16-3), хог —операция исключающего ИЛИ.
  • 3.5— полученная имитовставка.

В качестве имитовставки можно использовать лишь часть полученного числа 5, но следует помнить, что вероятность успешного навязывания ложных данных равна величине 2~L, где L — длина используемой части числа в битах. Обычно используются младшие 32 бита числа 5.

В шифре ГОСТ 28147—89 используется 256-битовый ключ, и объем ключевого пространства составляет 2256. Ни на одном из существующих в настоящее время или предполагаемых к реализации в недалеком будущем компьютере общего применения нельзя подобрать ключ за время, меньшее многих сотен лет. Российский стандарт ГОСТ 28147—89 проектировался с большим запасом и по стойкости на много порядков превосходит американский стандарт DES с его реальным размером ключа в 56 бит и объемом ключевого пространства всего 2>6.

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

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

 
<<   СОДЕРЖАНИЕ   >>