Васюков В_Н_ Теория электрической связи_

13. ОСНОВЫ КРИПТОЗАЩИТЫ СООБЩЕНИЙ

ВСИСТЕМАХ СВЯЗИ

омере развития и все более широкого рас- Ппространения средств связи возрастает роль

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

дачи информации, защищенных от незаконного вмешательства. Несанкционированный сбор информации конфиденциального

характера – реальность, и было бы проявлением неоправданного оптимизма не придавать ему значения. Методы сбора информации весьма разнообразны [25]; перечислим лишь некоторые из них:

акустический контроль помещений, автомобилей, людей;

прослушивание телефонных каналов, перехват факсовой и модемной передачи сообщений;

перехват компьютерной информации (при передаче по сетям, путем анализа радиоизлучений компьютера, путем внедрения в локальные сети, серверы, базы данных);

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

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

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

354 13. ОСНОВЫ КРИПТОЗАЩИТЫ СООБЩЕНИЙ В СИСТЕМАХ СВЯЗИ

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

13.1. ОСНОВНЫЕ ПОНЯТИЯ КРИПТОГРАФИИ

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

своих целях, а значит – во вред законным пользователям. Для краткости эти незаконные пользователи называются противника-

ми. Действия противника представляют угрозу для законного поль-

зователя (угрозу разглашения, подмены, имитации, уничтожения информации и т.п.).

Возможны три подхода к защите информации [28]:

создать абсолютно надежный канал связи, совершенно недоступный для незаконных пользователей;

передавать информацию по общедоступному каналу, сохраняя в тайне сам факт передачи;

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

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

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

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

Третий способ – криптографическая защита информации путем шифрования – в настоящее время является одним из самых

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

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

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

Зашифрованием называется процесс преобразования открытого

сообщения в зашифрованное (криптограмму) с помощью шифра, а расшифрованием – обратный процесс преобразования зашифро-

ванных (закрытых) данных в открытые с помощью шифра (шифро-

вание – общее наименование для зашифрования и расшифрования).

Дешифрованием (вскрытием, взломом) называют процесс преобра-

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

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

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

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

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

деляющая его способность противостоять дешифрованию. Обычно

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

356 13. ОСНОВЫ КРИПТОЗАЩИТЫ СООБЩЕНИЙ В СИСТЕМАХ СВЯЗИ

количественной мерой криптостойкости считается время, необходимое для дешифрования [25].

Проблема криптозащиты существует многие сотни лет, что естественно, если вспомнить, что у любого человека есть свои секреты. Математические основы криптографии были разработаны К. Шенноном [26]. В общем случае секретная система связи может быть представлена структурной схемой, показанной на рис. 13.1.

Рис. 13.1. Структура секретной системы

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

E f (M , K) .

Удобнее понимать это выражение не как функцию двух переменных, а как отображение

E TK{M},

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

M TK1{E} TK1 TK M ,

TK1TK I ,

где I – тождественное отображение.

Предполагается, что множество всех сообщений конечно и сообщения M1 ,… Mn вырабатываются источником с вероятностями

q1 ,…, qn . Аналогично источник ключей вырабатывает ключи K1 ,…, Km с вероятностями p1 ,…, pm . В современной криптографии принято считать, что противнику известно множество отображений TKi , i 1,m и набор априорных вероятностей p1 ,…, pm .

Это предположение является пессимистическим, но, в конечном счете, реалистическим, так как рано или поздно всякая секретная система может быть раскрыта [26]. Если противник не сможет взломать алгоритм шифрования, даже зная, как он устроен, то тем более это окажется ему не по силам без такого знания.

В настоящее время используются следующие криптографические методы защиты [25]:

−методы замены (подстановки);

−методы на основе датчика псевдослучайных чисел;

−методы перемешивания (алгоритмические);

−системы с открытым ключом.

13.2. МЕТОДЫ ЗАМЕНЫ

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

358 13. ОСНОВЫ КРИПТОЗАЩИТЫ СООБЩЕНИЙ В СИСТЕМАХ СВЯЗИ

13.2.1.ШИФР ПРОСТОЙ ПОДСТАНОВКИ

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

Подстановкой называется взаимно однозначное отображение конечного множества M на себя. Это означает, что каждому элементу множества (например, символу алфавита) ставится в соответствие один и только один элемент этого же множества. Очевидно, для задания конкретной подстановки природа элементов не имеет значения, важно лишь их количество N (называемое степенью подстановки). Можно поэтому в качестве множества рассматривать множество целых чисел M {1, 2, 3, ..., N}.

Любая подстановка может быть описана матрицей 2× N , в которой первая строка содержит числа 1, 2, …, N , а вторая строка состоит из тех же чисел, расположенных в порядке, определяемом подстановкой, например, если число i после подстановки получает

значение ki , то можно записать

Очевидно, если последовательно применить две подстановки

S1 и S2 , то их результат снова будет подстановкой, равной компо-

зиции (произведению) исходных подстановок S S1 S2 . Множе-

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

Пусть открытый текст представляет собой фразу «открытый текст», а подстановка задана таблицей

Шифртекст имеет вид «тоцреоечаоыцпо». Очевидно, что ключом к этому шифру является сама подстановка S . Количество всевозможных подстановок для алфавита из N символов равно N ! ,

9 Определение группы см. в разд. 2.

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

Частным случаем шифра замены является известный шифр Цезаря, состоящий в замене каждой буквы сообщения на букву, отстоящую от нее в алфавите на фиксированное число шагов. Например, буква «а» заменяется на «д», «б» на «е», «в» на «ж» и так далее; буквы «ю» и «я» заменяются на «в» и «г» соответственно (пробел не учитывается).

13.2.2.ШИФР ВИЖЕНЕРА

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

yi xi ki (mod N),

где xi – номер буквы открытого текста в алфавите; yi – номер бу-

квы шифртекста; ki – номер i -й буквы ключа (ключом является

слово или любая последовательность букв длины d , повторяемая столько раз, сколько требуется для зашифрования всего сообщения). Число d называется периодом шифра Виженера. Очевидно, упомянутый выше шифр Цезаря является шифром Виженера при d 1 .

Вариант шифра Виженера был реализован в механической шифровальной роторной машине [29], изобретенной в 20-х годах XX в.

13.2.3.ШИФРЫ БОФОРА

Эти шифры определяются формулами

yi ki xi (mod N)

и

yi xi ki (mod N),

где смысл обозначений такой же, как в шифре Виженера.

36013. ОСНОВЫ КРИПТОЗАЩИТЫ СООБЩЕНИЙ В СИСТЕМАХ СВЯЗИ

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

13.3. МЕТОДЫ ШИФРОВАНИЯ НА ОСНОВЕ ДАТЧИКА ПСЕВДОСЛУЧАЙНЫХ ЧИСЕЛ

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

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

gi 1 [Agi C]modM ,

где gi , i 1, 2, 3,... – последовательность псевдослучайных чисел, g0 – стартовое значение, A и C – некоторые константы. Обычно

принимается M 2b , где b – разрядность машины.

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

Шифрование на основе датчиков псевдослучайных чисел наиболее часто применяется в программной реализации криптозащиты данных, так как, с одной стороны, он достаточно прост для про-

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

Одной из форм реализации описанного метода является метод «одноразового блокнота». Суть этого метода состоит в том, что у

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

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

13.4. МЕТОДЫ ПЕРЕМЕШИВАНИЯ

Методы перемешивания основаны на работе К. Шеннона [26], в которой задачи криптологии рассматривались с информационной точки зрения. Прежде чем перейти к конкретным системам шифрования на основе перемешивания, приведем основные положения работы Шеннона.

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

ходимыми средствами для криптоанализа и неограниченным временем? Имеет ли криптограмма единственное решение (даже если

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

Пусть имеется конечное множество сообщений M1 ,… Mn с априорными вероятностями P(M1) , P(M2) ,…, P(Mn ) и эти со-

362 13. ОСНОВЫ КРИПТОЗАЩИТЫ СООБЩЕНИЙ В СИСТЕМАХ СВЯЗИ

общения преобразуются в криптограммы E1 , E2 , …, En , так что

E Ti{M}.

После перехвата криптограммы E шифровальщик противника может вычислить условные (апостериорные) вероятности различ-

ных сообщений PE (M) P(M | E) . Тогда совершенная секретная

система удовлетворяет следующему условию: для всех E все апостериорные вероятности равны априорным

PE (Mi ) P(Mi ) i E .

В этом и только в этом случае перехват шифртекста не дает противнику никакой информации.

По теореме Байеса

где P(M ) – априорная вероятность сообщения M ; PM (E) – ус-

ловная вероятность криптограммы E при условии, что выбрано сообщение M ; P(E) – вероятность получения криптограммы E ;

PE (M) – апостериорная вероятность сообщения M при условии,

что перехвачена криптограмма E .

Из выражения (13.1) следует, что для совершенной секретности необходимо и достаточно, чтобы выполнялось равенство

PM (E) P(E)

для любых сообщения M и криптограммы E .

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

Mдолжна однозначно соответствовать криптограмма E , которой,

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

Втерминах теории информации секретная система содержит два источника неопределенности: источник сообщений10 с энтропией

n

H M P Mi log P Mi

i 1

10 Здесь, очевидно, имеется в виду конечное число сообщений.