Скляр Б. Цифровая связь (2003) (1151859), страница 213
Текст из файла (страница 213)
М ьмм ми о М О Р ога Рав авз язт зто точ к у г хуг У2А гда АВС ВСО СОЕ ОЕГ Ега гаН а н н з к зкь кьм ьмн мно М О Р О Р а Рав аяз взт зто точ оча чах вху Здесь первая буква ключа (Т) указывает, что в качестве'строки для шифрования первой буквы открытого текста выбирается строка„начинающаяся с Т (сдвиг 19). Следующей выбирается строка, начинающаяся с г' (сдвиг 24), и т. д, Разновидностью этого метода является так называемый метод автоматического (явнаю) ключа Вигнгра (Ущепег ашо (р1ап) 1геу шег)кх)), когда в качестве образующего ключа используется единственная буква или слово.
Этот ключ дает начальную строку нли строки для шифрования первого или нескольких первых символов открытогс текста аналогично предыдущему примеру. Затем в качестве юпоча для выбора шифрующей строки используются символы исходною текста. В приведенном ниже примере в качестве образующего ключа использована буква "Р'. Ключ: Г Х О % 1 Т Н Е Т 1 М Исходный текст: Х О % 1 Б Н Е Т 1 М Е Шифрованный Б В К Е А А 1, Х В () О текст: Б Т С К С 1 Б Т К С У Хотя каждый символ ключа может быть найден из предшествующего ему символа шифрованного текста„функционально он зависит от всех предшествующих символов в сообщении и плюс основного ключа.
Таким образом, имеется эффект рассеивания статистических свойств исходного текста вдоль шифрованного текста, что делает статистический анализ очень сложным для крнптоаналитика. Слабым звеном описанного здесь примера шифрования с использованием ключа является то, что шифрованный текст содержит знаки ключа, которые будут публично выставлены через общедоступный канал "иа всеобщее обозрение". Для того чтобы предотвратить такое пубяичное разоблачение, можно использовать вариации этого метода (3). По нынешним стандартам схема шифрования Вигнера не является очень защищенной; основным вкладом Вигнера было открытие того, что неповторяюшиеся ключевые последоватеяьности можно создавать с использованием самих сообщений или функций от сообщений.
14.2. Секретность системы шифрования 14.2.1. Совершенная секретность Рассмотрим систему шифрования с конечной областью сообщений (М) = Мв, Мь.", М», и конечной областью шифрованных текстов (С) = Сь Сь .", Св-1 для любого М, 14.2. Секретность системы шифооваиия Метод автоматического ключа показывает, что в процесс шифрования может быть введена обратная связь. При использовании обратной связи выбор шифрованного текста опредеяяется содержанием сообщения. Последняя разновидность метода Вигнера — это метод автоматического (шифраваннага) ключа Вигнгра (маепеге ацго (с!рьег) )геу шег)згх)), подобный простому методу ключа; в нем также используются образующий ключ и обратная связь.
Отличие состоит в том, что после шифрования с помощью образующего ключа, каждый последующий симвоя ключа в последовательности берется не из символа исходного текста, а из символа шифрованного текста. Ниже приведен пример, который должен помочь понять принцип работы данного метода; как и ранее, в качестве начального ключа используется буква "Г". Ключ: Р Б О У С О г. Н Т Исходный текст: Х О % Н Е Т 1 М Е Шифрованный Б О С С О л. Н Т Х текст: априорная вероятность передачи сообщения М, равна Р(М,).
Апостериорная аероят- ность принятия сообшения С) при переданном сообшении М; равна Р(ЩСт). Говорят, что система шифрования имеет совершенную секретность, если для любого сообшения М, и любого шифрованного текста С, апостериорная вероятность равна априорной. (14.2) Таким образом, для системы с совершенной секретностью характерно следующее: ес- ли криптоаналитик перехватил сообшение Ст то дальнейшей информации, которая бы облегчила ему дешифровку сообшения, он не получит.
Необходимое и достаточное условие совершенной секретности: для любого М, и С, Р(Ст')М,) = Р(С)) (14.3) Р(Ме) ! Р(м!) а м! 1 о 1 2 2 Р(Мг) 41 Мг О \ Сг Р(Мг) = 1 Сг Открытые сообщения Шифрованные сообщения Рис. 14.4. Совершенная секретность Здесь Тх определяет преобразование с помощью ключа Ц, а "к по модулю у" — зто остаток от деления х на у. Таким образом, к = О, 1, 2, 3. Криптоаналнтик, перехвативший одно из шифрованных сообщений С, = С„Сн Сг или С„не сможет определить, какой из четырех ключей использовался и, следовательно, какое из сообщений М„Мь Мг или М, является верным.
Если и системе шифрования число сообшений, число ключей и число шиф- Глава 14. Шифрование и дешифооаание На рис. 14.4 изображен пример схемы соаершенной секретности. В атом примере (М) = М, М, М, М; (С) = С, Сн С, С; (К) = К„Кн Кг, )Гт; ! ) = () = 4, Р(М ) = Р(С ) = -„, Преобразование сообшения а шифрованный текст выполняется следующим образом: С,=тк (М;), (14.4) в = (! + )) по модулю )т'. рованных сообщений равны между собой, то система имеет совершенную секретность то- гда и только тогда, когда выполняются следующие два условия. !.
Существует только один ключ, преобразующий каждое сообщение в каждый шифрованный текст. 2. Все ключи равновероятны. Если эти условия не выполняются, то будет существовать некоторое сообщение М„ при котором для данного С, не существует ключа, который мог бы дешифровать С, в Мн Отсюда следует, что для некоторых ! и у Р(ЬЦСг) = О. В этом случае криптоаналитик может исключить из рассмотрения определенные нешифрованные сообщения, упростив, таким образом, задачу.
Вообще, совершенная секретность является очень желательным свойством, поскольку зто означает, что система шифрования безусловно защищена. Должно быть очевидно, что в системах, передающих большое количество сообщений, для достижения совершенной секретности требуется распредеяить большое количество ключей, а это, в свою очередь, может привести к значительным практическим затруднениям„что делает такие системы нереализуемыми. В системе с совершенной секретностью чисяо возможных ключей так же велико, как и число возможных сообщений, поэтому„если мы разрешим передавать сообщения неограниченной длины, совершенная секретность потребует бесконечного количества ключей. Пример 14.1. Взлом системы шифрования, если область ключей меньше области сообщений Рассмотрим шифрованный текст, состоящий из 29 символов.
О К О В О К В О 1) К О К О В У О С У Р 1 О С 1) О В 1 О К В Данный текст был получен с помощью шифра Пезаря (см. раздел !4рь4); каждая буква получена сдвигом на К символов, где 1 < К < 25. Покахсите, как криптоаналитик может взломать этот кол. Решение Поскольку количество возможных ключей (их 25) меньше количества возможных осмысленных сообщений из 29 символов (их огромное множество), совершенная секретность не может быть достигнута.
В исходном полиаяфавитном шифре, показанном на рис. 14.3, символ открытого текста заменяется буквой некоторой строки, причем номер проки постоянно возрастает. Следовательно, в процессе анализа шифрованного текста мы обращаем процесс: теперь буквы шифрованного текста заменяются буквами строк, причем номер строки постоянно уменьшается. Путем перебора всех ключей от ! до 25 (рис. 14.5) можно легко рассмотреть все возможности. В результате, этот процесс приводит к единственному ключу (К= 10), дающему осмысленное сообщение (пробелы были добавлены вручную): 1ЧНЕКЕ АКЕ ТНЕ НЕКОЕЬ ОГ УЕБТЕКУЕАК. Пример 142. Совершенная секретность Для создания шифра, имеющего совершенную секретность, можно несколько модифицировать область ключей, описанную в примере 14.!.
В этой новой системе шифрования кюкдый символ сообщения щифруется с использованием случайно выбранною ключевого значения. Теперь ключ К задается последовательностью йо lгь ..., Iгн, где каждое й; — это случайно выбранное целое число из интервала (1, 25), определяющее сдвиг, используемый для (-го символа. Таким образом, всего существует (25)" различных ключевых последовательностей. Значит, шифрованный текст из 29 символов, приведенный в примере 14. 1, может соответствовать любому осмысленному сообщению из 29 символов. Например, шифрованный текст мог соответствовать следующему открытому тексту (пробелы были добавлены вручную). ЕХИ.13Н АМЭ РКЕХСН АКЕ ЕРОКЕН НЕВЕ Данный текст получен с помощью ключа 2, 4, 8, 16, 6, 18, 20, ....
Стоит отметить, что большинство возможных наборов из 29 символов можно исключить, поскольку они не являются осмысленными сообщениями. Совершенная секретя!кть данного кода — результат того, что перехват шифрованного текста не дает никакой дополнительной информации об открьпом сообщении. Текат ОВЯОВОКВООНОЯОВУОСУР1ОС0081ОКВ Н й В С й А Н К 3 А ОМАВМ26М12 Е С 2 А 1 У Е Ь Н У ЕКУ2КХЕКОХ О 4ХУЗВО ЗЕВ С1ВХ1ЧС 1ЕЧ ВНЧВНОВН00 АООЧОТАОСТ 2ЕТОЕ82ЕВБ У Е 8 Т Е Я У Е А й 1 РОК АК 2ЕРМ2М 300вт 4СККХК 5ВМЗВ б А в ! Ч 1 ?2КНОН 8УЗОТВ 9 Х 1 Е 8 Е 10ВНЕЯЕ А й С О К О К А Х й В Х О 12МВРМРМ2ВМАВК Н У к А О в О в У Ч С 2 Ч и ОХ К 2 ККККХОКУ0 ЕВЗУМЗМЗВТЗХТК Е Ч ! Х 1.
1 'в 1 Ч 5 1 В 5 0 0 Н В К Н К Н 0 й Н Ч Я с тачзцзатаацан В 8 Е 0 1 Е 1 Е 8 Р Е Т Р 6 А Я Е Т Н Е Н Е Я О Е 5 О Е паата СРСУР ВОВХО АНАВК 2М2ЧМ УЬУ0 ХКХТК ВЗВБ Ч ! Ч й 0НООН ТОТРВ БЕБОЕ Я Е Н й Е ОООМО РСРвС НЕХО МОВС С Ч В КВОА А Т 2 28У НУЙХ ОХОВ ЕВР Ч ЕЧО0 00КТ СТМ8 В 3 Ь й А Н К О 2 О 3 Р Рис. 14.5.
Пример взлома системы шифрования, если облоств ключеи меньше об- ласти сообщений 14.2.2. Энтропия и неопределенность Как обсуждалось в главе 9, объем информации в сообщении связан с вероятностью появления сообщения. Сообщения вероятности 0 либо 1 не содержат информации, поскольку можно с известной далей определенности предсказать их появление. Чем больше неопределенности существует в предсказании появления сообщения, тем больше оно содержит информации. Следовательно, если все сообщения множества равновероятны, мы нв можем быть уверенными в возможности предсказания появления конкретного сообщения, и неопределенность информационного содержания сообщения является максимальной.
Энтропия Н(К) определяется как средний объем информации на сообщение. Она может рассматриваться как мера того„насколько в выбор сообщения Х вовлечен случай. Она записывается как следующее суммирование по всем возможным сообщениям. И(Х) = -~~) Р(Х) 1082 Р(Х) = ~~) Р(Х)!082— 1 Р(Х) (14.5) 916 11 Ч 6 12 0 Е 13 Т Е 14 8 0 15 й С 18 О В 17 РА 18 0 2 19 К У 20 МХ 21 вВ 22 КУ 23 3 0 24 1 Т 25 Н 8 03606 С й Е С Е В О Е В Е АРОАО 2 О С 2 С У К В У В ХМАХА и'в2В2 ЧКУЧУ 0 3 Х 0 Х Т1ВТВ БНЧБЧ Н60Й0 О Г Т О Т Р Е 8 Р 8 СОК ОН СРМСО В 0 в В Р АККАО 2 М 3 2 К У 1. 1 У М Х К Н Х ВЗОВК Ч 1 Е Ч 3 0 Н Е 0 1 ТООТН 8ЕС86 НЕВЯЕ ООАОЕ РС2РО Я 8 0 ОйС Р О В 0 Р А и О 2 М й У М Х К1В 3 К Ч 1 3 0 Н 1 Т ОН 5 ГОН Е Е О 0 Е Р ахо2а РВСУР ОЧВХО КОАВК МТ2ЧМ БУ0 КНХТК ОВБ 1РЧН1 НОООН ОКТРО ЕМБОЕ ЕкййЕ ОКОМО СЗРЬС Если, как выше, логарифм берется по основанию 2, Н(Х) представляет собой математическое азкидапие числа битов в оптимально закодированном сообщении Х. Это все еше не та мера, которую хотел бы иметь криптоаналнтик.
Им будут перехвачены некоторые шифрованные тексты, и он захочет узнать, насколько достоверно он может предсказать сообщение (или ключ) при условии, что был отправлен именно этот конкретный шифрованный текст. Неопределенность, определенная как условная энтропия Х при данном У, является для криптоаналитика более полезной мерой при попытке взлома шифра.
Она задается с помощью следующей формулы: Н(Х ) У) =- ~~Р(Х,У)1ойз Р(Х,У) = хд (14.6) Р(У)~~) Р(Х ( У) 1ойз 1 Р(Х ) У) Неопределенность может рассматриваться как неуверенность в том, что отправлено было сообщение Х, при условии получения У. Желательным для криптоаналнтика яшгяется при- ближение Н(л()) к нулю при увеличении объема перехваченного шифрованного текста У..
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
