shannon (1014203), страница 9
Текст из файла (страница 9)
Пусть M, E1, E2 – сообщение ипервая и вторая криптограммы соответственно. ТогдаPE1E2 ( M ) = PE1 ( M )Следовательно,H E1 , E2 ( M ) = H E1 ( M )так как для любых случайных величин х, у, z справедливо Hxy(z) £ Hy(z) то получаемжелаемый результат: H E2 ( M ) ³ H E1 ( M ) .Теорема 8. Ненадежность сообщения для произведения секретных систем S = TR неменьше ненадежности для одной системы R.Предположим, что имеется система T, которая может быть записана как взвешенная сумманескольких систем R,S,…,UT = p1R + p2S + … + pmU,åpi= 1,и системы R,S,…,U имеют ненадежности H1,H2,…,Hm.Теорема 9. Ненадежность для взвешенной суммы систем ограничена неравенствами29åpHii£ H £ å pi H i - å pi log piЭти границы нельзя улучшить. Здесь Hi могут означать ненадежность ключа илисообщения.Верхняя граница достигается, например, в строго идеальных системах (которыебудут описаны ниже), где разложение производится на простые преобразования системы.Нижняя граница достигается, если все системы R,S,…,U приводят к полностью различнымпространствам криптограмм.
Эта теорема также доказывается с помощью общихнеравенств, которым подчиняется ненадежность:HA (B) £ H(B) £ H(A) + HA (B),где A может обозначать данную используемую систему, а B – ключ или сообщение.Имеется аналогичная теорема для взвешенных сумм языков.
Для ее доказательстваобозначим данный язык буквой A.Теорема 10. Предположим, что система может быть применена к языкам L1,L2,…,Lm ипри этом получаются ненадежности H1,H2,…,Hm. Если система применяется к взвешенной сумме å pi Li то ненадежность H ограничена неравенствамиåpHii£ H £ å pi H i - å pi log pi .Эти границы нельзя улучшить. Рассматриваемая ненадежность может относиться как кключу, так и к сообщению.Полная избыточность DN для N букв сообщения определяется с помощьюсоотношенияDN = logG – H(M),где G – полное число сообщений длины N, а H(M) – неопределенность выбора одного изних.
В секретной системе, где полное число возможных криптограмм равно числувозможных сообщений длины 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 измеряется в битах на букву.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
