shannon (Клод Шеннон - Теория связи в секретных системах), страница 6

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

Здесь остаточный класс сообщений состоит из всехпоследовательностей с теми же первыми разностями, что и у криптограммы для букв,отстоящих на расстояние d. Для d = 3 остаточный класс определяется с помощью равенствm1m4=e1e4––m2m3m4–––m5=m6=m7=e2e3e4–––e5e6e7… … …где E = e1e2… – криптограмма, а m1m2… является любым сообщением M всоответствующем остаточном классе.В транспозиции с периодом d со случайным ключом остаточный класс состоит извсех способов расстановок символов криптограммы, в которых никакое ei не выдвигается изсвоего блока длины d и любые два ei с расстоянием d остаются на таком же расстоянии.Это используется для раскрытия шифра следующим образом: криптограмма записывается ввиде последовательных блоков длины d один под другим, как показано ниже (для d = 5)e1e2e3e4e5e6e7e8e9e10e11 e12 … … …… … … … …Затем столбцы переставляются до тех пор, пока не получится осмысленный текст.После того, как криптограмма разбита на столбцы, оставшейся существенной информациейявляется только остаточный класс криптограммы.Теорема 5.

Если шифр T – чистый, то TiTj–1T = T, где Ti ,Tj – любые два отображения изT. Обратно, если это выполняется для любых принадлежащих шифру Ti ,Tj, то шифр Tявляется чистым.20Первая часть этой теоремы следует, очевидно, из определения чистого шифра.Чтобы доказать вторую часть, заметим сначала, что если TiTj–1T = T то TiTj–1Ts являетсяотображением из T. Остается показать, что все ключи равновероятны.

Имеем T = å psTsSиå p TTs iST = å psTs .-1jsSСлагаемое в стоящей слева сумме с s = j дает pjTi. Единственным слагаемым с Ti, в правойчасти является piTi. Так как все коэффициенты неотрицательны, то отсюда следует, чтоpj £ pi.То же самое рассуждение остается справедливым, если i и j поменять местами.Следовательно,pj = piи T – чистый шифр. Таким образом, условие TiTj–1T = T можно было бы использовать вкачестве другого определения чистого шифра.8. Подобные системы.Две секретные системы R и S будем называть подобными, если существуетотображение A, имеющее обратное A–1, такое, чтоR = AS.Это означает, что шифрование с помощью R даст то же, что шифрование с помощью S споследующим применением отображения А.

Если использовать запись R » S дляобозначения того, что R подобно S, то, очевидно, из R » S следует S » R. Кроме того, изR » S и S » T следует, что R » T и, наконец, R » R. Резюмируя вышеизложенное, можносказать, что подобие систем является соотношением эквивалентности.Криптографический смысл подобия состоит в том, что если R » S, то R и Sэквивалентны с точки зрения дешифрования. Действительно, если шифровальщикпротивника перехватывает криптограмму из системы S, он может перевести ее вкриптограмму из системы R простым применением к ней отображения A. Обратно,криптограмма из системы R переводится в криптограмму из системы S с помощью A–1.Если R и S применяются к одному и тому же пространству сообщений или языку, тоимеется взаимно однозначное соответствие между получающимися криптограммами.Соответствующие друг другу криптограммы дают одинаковое апостериорное распределениевероятностей для всех сообщений.Если имеется некоторый способ раскрытия системы R, то любая система S,подобная R, может быть раскрыта после приведения ее к R с помощью операции A.

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

е. сообщением, используемым в качестве «ключа») с используемымивначале ключами K1K2…Kd подобен шифру Виженера с ключом, поочередно складываемыми вычитаемым по модулю 26. Отображение A в этом случае представляет собой21«дешифровку» автоключа с помощью последовательности из d таких отображений длякаждого из начальных ключей.Часть II.ТЕОРЕТИЧЕСКАЯ СЕКРЕТНОСТЬ.9.

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

Совершенная секретность.Предположим, что имеется конечное число возможных сообщений M1,…,Mn саприорными вероятностями P(M1),…,P(Mn) и что эти сообщения преобразуются ввозможные криптограммы E1,…,Em, так чтоE = TiM.После того как шифровальщик противника перехватил некоторую криптограмму E,он может вычислить, по крайней мере в принципе, апостериорные вероятности различныхсообщений PE(M). Естественно определить совершенную секретность с помощью следующего условия: для всех E апостериорные вероятности равны априорным вероятностямнезависимо от величины этих последних.

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

А это в свою очередь может повлиять на выборпротивником своих действий и, таким образом, совершенной секретности не получится.Следовательно, приведенное определение неизбежным образом следует из нашегоинтуитивного представления о совершенной секретности.4К. Шеннон «Работы по теории информации и кибернетике», М., ИЛ, 1963, с. 243-332.Пурист мог бы возразить, что противник получил некоторую информацию, а именно он знает, что посланокакое-то сообщение. На это можно ответить следующим образом. Пусть среди сообщений имеется «чистыйбланк», соответствующий «отсутствию сообщения». Если не создается никакого сообщения, то чистый бланкзашифровывается и посылается в качестве криптограммы.

Тогда устраняется даже эта крупинка информации.522Необходимое и достаточное условие для того, чтобы система была совершенносекретной, можно записать в следующем виде. По теореме БайесаPE ( M ) =P ( M ) × PM ( E ),P(E)гдеP(M) – априорная вероятность сообщения M;PM(E) – условная вероятность криптограммы E при условии, что выбрано сообщение M,т.е. сумма вероятностей всех тех ключей, которые переводят сообщение M вкриптограмму E;P(E) – вероятность получения криптограммы E;PE(M) – апостериорная вероятность сообщения M при условии, что перехваченакриптограмма E.Для совершенной секретности системы величины PE(M) и P(M) должны бытьравны для всех E и M. Следовательно, должно быть выполнено одно из равенств: илиP(M) = 0 [это решение должно быть отброшено, так как требуется, чтобы равенствоосуществлялось при любых значениях P(M)], или жеPM(E) = P(E)для любых M и E.

Наоборот, если PM(E) = P(E), тоPE(M) = P(M),и система совершенно секретна. Таким образом, можно сформулировать следующее:Теорема 6. Необходимое и достаточное условие для совершенной секретности состоит втом, чтоPM(E) = P(E)для всех M и E, т.е. PM(E) не должно зависеть от M.Другими словами, полная вероятность всех ключей, переводящих сообщение Mi вданную криптограмму E, равна полной вероятности всех ключей, переводящих сообщениеMj в ту же самую криптограмму E для всех Mi, Mj и E.Далее, должно существовать по крайней мере столько же криптограмм E, сколько исообщений M, так как для фиксированного i отображение Ti дает взаимно-однозначноесоответствие между всеми M и некоторыми из E.