В.Н. Васюков - Теория электрической связи (1266498), страница 58

Просмтор этого файла доступен только зарегистрированным пользователям. Но у нас супер быстрая регистрация: достаточно только электронной почты!

Текст из файла (страница 58)

МЕТОДЫ ЗАМЕНЫРассмотрим несколько примеров шифров замены. В примерах используются буквы русского алфавита (без буквы «ѐ») плюспробел, обозначаемый символом ‗. Для удобства приведем русский алфавит в виде таблицы, содержащей также номера букв.БукваАБВГДЕЖЗИЙКЛ№010203040506070809101112БукваМНОПРСТУФХЦЧ№131415161718192021222324БукваШЩЪЫЬЭЮЯ‗№25262728293031323335813. ОСНОВЫ КРИПТОЗАЩИТЫ СООБЩЕНИЙ В СИСТЕМАХ СВЯЗИ13.2.1. ШИФР ПРОСТОЙ ПОДСТАНОВКИВ основе шифрования этим методом лежит алгебраическаяоперация над алфавитом сообщения, называемая подстановкой.Подстановкой называется взаимно однозначное отображениеконечного множества M на себя. Это означает, что каждому элементу множества (например, символу алфавита) ставится в соответствие один и только один элемент этого же множества.

Очевидно, для задания конкретной подстановки природа элементов неимеет значения, важно лишь их количество N (называемое степенью подстановки). Можно поэтому в качестве множества рассматривать множество целых чисел M  {1, 2, 3, ..., N } .Любая подстановка может быть описана матрицей 2× N , в которой первая строка содержит числа 1, 2, …, N , а вторая строкасостоит из тех же чисел, расположенных в порядке, определяемомподстановкой, например, если число i после подстановки получаетзначение ki , то можно записать1 2 .

. . N ,S k1 k2 . . . k N где ki M i .Очевидно, если последовательно применить две подстановкиS1 и S2 , то их результат снова будет подстановкой, равной композиции (произведению) исходных подстановок S  S1  S2 . Множество подстановок одинаковой степени образует группу 9 относительно «умножения», определенного таким образом.

Отсюдаследует, что для каждой подстановки существует обратная. Нейтральным элементом группы подстановок служит тривиальнаяподстановка, оставляющая на месте все элементы множества.Пусть открытый текст представляет собой фразу «открытыйтекст», а подстановка задана таблицей 1 2 3 . . 32 33 .S 33 32 31 . . 2 1 Шифртекст имеет вид «тоцреоечаоыцпо». Очевидно, что ключом к этому шифру является сама подстановка S . Количество всевозможных подстановок для алфавита из N символов равно N ! ,9Определение группы см. в разд. 2.35913.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]mod M ,где gi , i  1, 2, 3,... – последовательность псевдослучайных чисел,g0 – стартовое значение, A и C – некоторые константы. Обычнопринимается M  2b , где b – разрядность машины.Если гамма имеет период больший, чем длина зашифрованного сообщения, и если не известна никакая часть исходного текста,то этот шифр можно раскрыть только прямым перебором возможных ключей, поэтому криптостойкость определяется размером ключа [25].Шифрование на основе датчиков псевдослучайных чисел наиболее часто применяется в программной реализации криптозащитыданных, так как, с одной стороны, он достаточно прост для про-13.4.

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

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

МЕТОДЫ ПЕРЕМЕШИВАНИЯМетоды перемешивания основаны на работе К. Шеннона[26], в которой задачи криптологии рассматривались с информационной точки зрения. Прежде чем перейти к конкретным системамшифрования на основе перемешивания, приведем основные положения работы Шеннона.Основные вопросы, которые представляют интерес с теоретической точки зрения, состоят в следующем. Насколько устойчивасистема, если шифровальщик противника располагает всеми необходимыми средствами для криптоанализа и неограниченным временем? Имеет ли криптограмма единственное решение (даже еслионо может быть найдено за практически неприемлемое время), аесли нет, то сколько решений она имеет? Какой объем шифрованного текста нужно перехватить, чтобы решение стало единственным? Существуют ли секретные системы, для которых нельзя найти единственное решение независимо от объема перехваченнойкриптограммы? Существуют ли системы, в которых противник вообще не получает никакой информации независимо от объема перехваченного шифртекста? Рассмотрение этих вопросов основывается на понятиях теории информации.Пусть имеется конечное множество сообщений M1 ,… M n саприорными вероятностями P(M1 ) , P(M 2 ) ,…, P(M n ) и эти со-36213.

ОСНОВЫ КРИПТОЗАЩИТЫ СООБЩЕНИЙ В СИСТЕМАХ СВЯЗИобщения преобразуются в криптограммы E1 , E2 , …, En , так чтоE  Ti {M } .После перехвата криптограммы E шифровальщик противникаможет вычислить условные (апостериорные) вероятности различных сообщений PE (M )  P(M | E) . Тогда совершенная секретнаясистема удовлетворяет следующему условию: для всех E все апостериорные вероятности равны априорнымPE (Mi )  P(Mi ) i E .В этом и только в этом случае перехват шифртекста не дает противнику никакой информации.По теореме БайесаP( M ) PM ( E ),(13.1)PE ( M ) P( 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 .

Характеристики

Список файлов книги