Клод Шеннон - Теория связи в секретных системах (1085222), страница 9
Текст из файла (страница 9)
В секретной системе, где полное число возможных криптограмм равно числувозможных сообщений длины N, имеет место неравенство H(E) £ logG. Следовательно,HE (K) = H(K) + H(M) – H(E) ³ H(K) – (logG – H(M)).ПоэтомуH(K) – HE (K) £ DN.Из этого видно, что, например, в замкнутой системе уменьшение ненадежностиключа после перехвата N букв не превзойдет избыточности N языка.
В таких системах (кним относится большинство шифров) только наличие избыточности в исходном сообщениии дает возможность нахождения решения.Предположим теперь, что имеется чистая секретная система. Обозначим различныеостаточные классы сообщений через C1,C2,…,Cr и соответствующие остаточные классыкриптограмм через C1',C2',…,Cr' . Вероятности всех E из Ci одинаковыP(E) =P (C i ), E – элемент Ci ,jiгде ji – число различных сообщений в Ci .
Таким образом, имеемH ( E ) = - åj iiP (C i )P (C i )P (C i ).log= - å P (Ci ) logjijijii30Подставив это значение H(E) в выражение, полученное выше для HE (K), получимследующую теорему.Теорема 11. Для чистого шифраH E ( K ) = H ( K ) + H ( M ) + å P (C i ) logiP (C i ).jiЭто выражение может быть использовано для вычисления HE (K) в некоторых случаях,представляющих интерес.13.Ненадежность простой подстановки для языка с двухбуквеннымалфавитом.Подсчитаем теперь ненадежность ключа и сообщения для простой подстановки8,примененной к языку с двухбуквенным алфавитом, причем вероятности для 0 и 1 равны pи q, а последовательные буквы выбираются независимо.В этом случаеH E ( M ) = H E ( K ) = -å P ( E ) PE ( K ) log PE ( K )Вероятность того, что E содержит точно s нулей в фиксированных местах, равна1 s N -s( p q + q s p N -s ) ,2и апостериорные вероятности тождественной и обратной подстановок (здесь есть только этидве подстановки) равны соответственноp sq N -sq s p N -s,(1)=.PE (0) = s N - sPE( p q + q s p N -s )( p sq N -s + q s p N -s )Имеется C Ns слагаемых для каждого s и, следовательноH E ( K , N ) = -å C Ns p s q N - s log121sp sq N - s.p sq N - s + q s p N - s7Для р = /3; q = /3 и р = /8; q = /8 величины HE(K,N) приведены на рис.
6.8В которой оба ключа (обе подстановки) равновероятны. — Прим. ред.31HE(K,N) = HE(M,N) - д е с я т и ч н ы х е д и н и ц0.30.2p = 1/3, q = 2/30.1p = 1/8, q = 7/80.002468101214161820Число буквРис. 6. Ненадежность для простой подстановки в двухбуквенном языке.14.Характеристика ненадежности для «случайного» шифра.В предыдущем разделе была вычислена характеристика ненадежности для простойподстановки, примененной к языку с двухбуквенным алфавитом. Но даже для этого почтисамого простого шифра и языка полученные формулы уже настолько сложны, что почтибесполезны.
Что же делать в практически интересных случаях, скажем в тех случаях, когдадробная транспозиция применена к английскому тексту с его крайне сложной статистической структурой. Эта сложность сама выдвигает метод подхода. Достаточно сложныепроблемы часто могут быть разрешены статистически. Чтобы облегчить дело, введемпонятие «случайного» шифра.Сделаем следующие допущения.1. Число возможных сообщений длины N равно T = 2 R0 N таким образомR0 = log2G, где G – число букв алфавита. Предполагается, что число возможныхкриптограмм длины N также равно T.2. Все возможные сообщения длины N можно разделить на две группы: группу свысокими и достаточно равномерными априорными вероятностями и группу с пренебрежимо малой полной вероятностью.
Высоко вероятная группа будет содержать S = 2RNсообщений, где R = H(M)/N, т.е. R – энтропия источника сообщений на одну букву9.9Подробнее исследование этого допущения можно найти, например, в работах А. Я. Хинчина и А. Файнстейна,указанных в библиографии в конце книги. — Прим. ред.323. Операцию расшифрования можно представлять графически в виде ряда линий(как на рис.
2 и рис. 4), идущих от каждого Е к различным M. Предположим, что имеетсяk равновероятных ключей, и что от каждого E будет отходить k линий. Предположим,что для случайного шифра линии от каждого E отходят к случайному набору возможныхсообщений. Тогда случайный шифр будет представлять собой фактически целый ансамбльшифров и его ненадежность будет равна средней ненадежности этого ансамбля10.Ненадежность ключа определяется с помощью равенстваH E ( K ) = å P ( E ) PE ( K ) log PE ( K ) .Вероятность того, что от частного E к высоковероятной группе сообщений отходит ровноm линий, равнаCkmmSöæSö æç ÷ ç1 - ÷tøètø èk -m.Если перехвачена криптограмма, которой соответствует m таких линий, то ненадежностьравна log m.
Вероятность такой криптограммы равна mT/Sk, так как она может бытьсоздана из высоковероятных сообщений, каждое из которых имеет вероятность T/S спомощью одного из m ключей. Отсюда ненадежность равнаmT k mæSö æ SöHE (K ) =å Ck çè t ÷ø çè1 - t ÷øSk m =1k -mm log m .Требуется найти простое приближенное выражение для HE(K), когда k велико. Если длявеличины m ее среднее значение m = Sk / T много больше 1, то изменение log m вобласти тех m, для которых биномиальные слагаемые велики, будет малым и мы можемзаменить log m на log m . Этот множитель можно вынести за знак суммы, которая дастзначение m .
Таким образом, при этом условииSk= log S - log T + log k ,THE(K) » H(K) – DN ,H E ( K ) » logгде D – избыточность на букву первоначального языка (D = DN/N).Если m мало по сравнению с k, то биномиальное распределение может бытьприближенно пуассоновским:Ckm p m q k - m »e -ll m,m!где l = Sk/T. Отсюда1 -l ¥ l mHE (K ) » e åm log m .l2 m!Заменив m на m+1, получим¥H E ( K ) » e -l å110lmlog( m + 1) .m!Это третье допущение, а также дальнейшие рассуждения этого раздела, хотя и достаточно наглядны, все же,конечно, далеки от математической строгости. Вероятно, они могут быть уточнены так же, как это ужесделано, с аналогичными построениями Шеннона в других его статьях.
При этом свое место в теории могли бызанять и оговорки, которым посвящен следующий параграф. Однако эта работа, по-видимому, еще никем непроведена. — Прим. ред.33Это выражение можно использовать, когда l близко к 1. Если же l << 1, то существеннымявляется лишь первый член ряда. Отбрасывая другие, получимH E ( K ) » e -ll log 2 » l log 2 » 2 - ND k log 2 .Итак, подводя итог вышесказанному, получаем, что HE(K), рассматриваемая какфункция от N – числа перехваченных букв – при N = 0 равна H(K). Далее она убываетлинейно с наклоном –D до окрестности точки N = H(K)/D. После небольшой переходнойобласти HE(K) начинает убывать экспоненциально со временем «полураспада» 1/D, еслиD измеряется в битах на букву.
Поведение HE(K) показано на рис. 7 вместе с аппроксимирующими кривыми.С помощью аналогичных рассуждений можно подсчитать ненадежность сообщения.Она равнаHE(M) = R0Nдля R0N << HE(K),HE(M) = HE(K)для R0N >> HE(K),для R0N ~ HE(K),HE(M) = HE(K) – j(N)H(K)1.0HE(K)HE(K) ( з н а к о в )где j(N) – функция, показанная на рис. 7, причем шкала N сжата в D/R0 раз.
Такимобразом, HE(M) возрастает линейно с наклоном R0 до тех пор, пока она не пересечетлинию HE(K). После закругленного перехода она идет ниже кривой HE(K).10H(K) - ND lg 2H(K) - ND0H(K)H(K)+1H(K)+2ND ( з н а к о в )Рис. 7. Ненадежность для случайного шифра.На рис. 7 видно, что кривые ненадежности стремятся к нулю довольно резко.Поэтому можно с достаточной определенностью говорить о точке, в которой решениестановится единственным. Найденное при этом число букв мы будем называть расстояниемединственности. Для случайного шифра оно приблизительно равно H(K)/D.15.
Применение к стандартным шифрам.Большинство стандартных шифров требует выполнения достаточно сложныхопераций шифрования и расшифрования. Кроме того, естественные языки обладают крайнесложной статистической структурой. Поэтому можно предположить, что для случаястандартного шифра применимы формулы, выведенные для случайного шифра.
Однако в34некоторых случаях необходимо вносить определенные поправки. Наиболее важно отметитьследующее.1. Мы предполагали, что для случайных шифров возможные расшифровки некоторой криптограммы являются случайной выборкой из возможных сообщений. В то времякак в обычных системах это, строго говоря, неверно, некоторое приближение к такойситуации достигается при возрастании сложности операций шифрования и при усложнениистатистической структуры языка. Ясно, что для шифра транспозиции частоты букв сохраняются при операциях шифрования.
Это означает, что возможные расшифровки выбираютсяне из всего пространства сообщений, а из более ограниченной группы, и, следовательно,наша формула должна быть изменена. Вместо R0 нужно использовать R1 – энтропийнуюскорость для языка с независимыми буквами, но с регулярными частотами букв. В некоторых других случаях можно заметить определенную тенденцию возвращения расшифровок квысоковероятным сообщениям.
Если не заметно явно выраженной тенденции такого рода исистема достаточно сложна, то разумно воспользоваться результатами анализа случайногошифра.2. Во многих случаях полный ключ не используется при зашифровке короткихсообщений. Например, в простой подстановке все буквы алфавита будут содержаться лишьв достаточно длинных сообщениях, и таким образом, только для таких сообщений нуженполный ключ.
В таком случае, очевидно, наше предположение о случайности не верно длямалых N, так как все ключи, отличающиеся только в тех буквах, которые еще не появилисьв криптограмме, приводят к тому же самому сообщению, следовательно, эти ключи неявляются случайно распределенными. Эту ошибку легко исправить, применяя «характеристику появления ключа». Для частного значения N используется эффективный объем ключа,который можно ожидать для данной длины криптограммы. Для большинства шифров этотобъем легко оценить.3. В связи с тем, что сообщение начинается с определенного знака, имеют место такназываемые концевые эффекты, приводящие к отклонению от случайных характеристик.Если в английском тексте взять случайную начальную точку, то первая буква (если предыдущие буквы неизвестны) может быть любой буквой с обычным набором вероятностей.Следующая буква характеризуется полнее, так как теперь имеются частоты диграмм.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
