Клод Шеннон - Теория связи в секретных системах (1085222), страница 5
Текст из файла (страница 5)
невсегда RS = SR), хотя в частных случаях (таких, как подстановка и перестановка)коммутативность имеет место. Так как наше умножение представляет собой некоторуюоперацию, оно по определению ассоциативно, т.е. R(ST) = (RS)T = RST. Кроме того, вернызаконыp(p'T + q'R) + qS = pp'T + pq'R + qS(взвешенный ассоциативный закон для сложения);T(pR + qS) = pTR + qTS(pR + qS)T = pRT + qST(право- и левосторонние дистрибутивные законы), а также справедливо равенствоp1T + p2T + p3R = (p1 + p2)T + p3R.Следует подчеркнуть, что эти операции комбинирования сложения и умноженияприменяются к секретным системам в целом.
Произведение двух систем TR не следуетсмешивать с произведением отображений в системах TiRj, которое также часто используетсяв настоящей работе. Первое является секретной системой, т.е. множеством отображений ссоответствующими вероятностями; второе является фиксированным отображением. Далее, вто время как сумма двух систем pR + qT является системой, сумма двух отображений неопределена. Системы T и R могут коммутировать, в то время как конкретные Rj и Ti некоммутируют. Например, если R – система Бофора данного периода, все ключи которойравновероятны, то, вообще говоря,RiRj ¹ RjRi,но, конечно, произведение RR не зависит от порядка сомножителей; действительноRR = Vявляется системой Виженера того же самого периода со случайным ключом.
С другойстороны, если отдельные отображения Ti и Rj двух систем T и R коммутируют, то исистемы коммутируют.Системы, у которых пространства M и E можно отождествить (этот случайявляется очень частым, если последовательности букв преобразуются в последовательности15букв), могут быть названы эндоморфными. Эндоморфная система T может быть возведенав степень Tn.Секретная система T, произведение которой на саму себя равно T, т.е. такая, чтоTT = T,будет называться идемпотентной. Например, простая подстановка, транспозиция спериодом p, система Виженера с периодом p (все с равновероятными ключами) являютсяидемпотентными.Множество всех эндоморфных секретных систем, определенных в фиксированномпространстве сообщений, образует «алгебраическую систему», т.
е. некоторый вид алгебры,использующей операции сложения и умножения. Действительно, рассмотренные свойствасложения и умножения можно резюмировать следующим образом:Множество эндоморфных шифров с одним и тем же пространством сообщений идвумя операциями комбинирования — операцией взвешенного сложения и операциейумножения — образуют линейную ассоциативную алгебру с единицей, с той лишьособенностью, что коэффициенты во взвешенном сложении должны бытьнеотрицательными, а их сумма должна равняться единице.Эти операции комбинирования дают способы конструирования многих новых типовсекретных систем из определенных данных систем, как это было показано в приведенныхпримерах. Их можно также использовать для описания ситуации, с которой сталкиваетсяшифровальщик противника, когда он пытается расшифровать криптограмму неизвестноготипа.
Фактически он расшифровывает секретную систему типаT = p1A + p2B + ... + prS + p'X,S p = 1,iгде A,B,...,S в данном случае – известные типы шифров с их априорными вероятностями pi,а p'X соответствует возможности использования совершенно нового неизвестного шифра.7. Чистые и смешанные шифры.Некоторые типы шифров, такие как простая подстановка, транспозиция с даннымпериодом, система Виженера с данным периодом, система Виженера со смешаннымалфавитом и т.д.
(все с равновероятными ключами), обладают некоторой однородностью поотношению к ключу. Каков бы ни был ключ, процессы зашифрования, расшифрованияадресатом и дешифрования противником являются по существу теми же самыми. Этисистемы можно противопоставить системе с шифромpS + qT,где S – простая подстановка, а T – транспозиция с данным периодом.
В таком случаепроцессы зашифрования и расшифрования адресатом или противником полностью меняютсяв зависимости от того, используется подстановка или транспозиция.Причина однородности таких систем лежит в групповом свойстве: заметим, что вприведенных выше примерах однородных шифров произведение TiTj любых двухотображений из множества равно третьему отображению Tk из этого же множества. Сдругой стороны, TiSj не равно какому-нибудь отображению для шифраpS + qT,который содержит только подстановки и транспозиции, но не их произведения.Было бы можно, таким образом, определить «чистый» шифр как шифр, в котором Tjобразуют группу. Однако это было бы слишком сильным ограничением, так как тогдапотребовалось бы, чтобы пространство E совпадало с пространством M, т.е. чтобы система16была эндоморфной.
Дробная транспозиция так же однородна, как и обычная транспозиция,но она не эндоморфна. Подходящим является следующее определение: шифр T являетсячистым, если для каждых Ti, Tj, Tk имеется такое Ts, чтоTiTj–1Tk = Ts,и все ключи равновероятны. В противном случае шифр является смешанным.
Шифры нарис. 2 являются смешанными, а на рис. 4 – чистыми, если только все ключи равновероятны.ОстаточныеклассысообщенийОстаточныеклассыкриптограммM1 1M2C1M3M4M5C2C3M6M74433312E24E3122E1234E41123443211C'1234E5E6E7C'2C'3Чистая системаРис 4. Чистая система.Теорема 1.
В чистом шифре операции Ti–1Tj, отображающие пространство сообщений всебя, образуют группу, порядок которой равен m – числу различных ключей.Так какTj–1TkTk–1Tj = I,17то каждый элемент имеет обратный. Ассоциативный закон верен, так как это операции, агрупповое свойство следует из того, чтоTi–1TjTk–1Tl = Ts–1TkTk–1Tl = Ts–1Tl,где предполагалось, что Ti–1Tj = Ts–1Tk для некоторого s.Операция Ti–1Tj означает шифрование сообщения с помощью ключа j споследующим расшифрованием с помощью ключа i, что приводит нас назад к пространствусообщений. Если система T эндоморфна, т.е.
Ti отображают пространство WM в самосебя (что имеет место для большинства шифров, в которых и пространство сообщений, ипространство криптограмм состоит из последовательностей букв), и если Ti образуютгруппу и равновероятны, то T – чистый шифр, так какTiTj–1Tk = TiTr = Ts.Теорема 2.
Произведение двух чистых коммутирующих шифров является чистым шифром.Если T и R коммутируют, то TiRj = RlTm для любых i,j при соответствующихl,m. ТогдаTiRj(TkRl)–1TmRn = TiRjRl–1Tk–1TmRn = RuRv–1RwTrTs–1Tt = RhTg.Условие коммутативности не является, однако, необходимым для того, чтобыпроизведение было чистым шифром.Система, состоящая из одного ключа, т.е. из единственной определенной операцииT1, является чистым шифром, т.е. при единственном возможном выборе индексов имеемT1T1–1T1 = T1.Таким образом, разложение шифра в сумму таких простых отображенийпредставляет собой разложение в его сумму чистых шифров.Исследование примера, приведенного на рис. 4, вскрывает некоторые свойствачистого шифра.
Сообщения распадаются на определенные подмножества, которые мыбудем называть остаточными классами, и возможные криптограммы также распадаются насоответствующие им остаточные классы. От каждого сообщения в любом классе к каждойкриптограмме в соответствующем классе ведет не менее одной линии и нет линий междунесоответствующими классами. Число сообщений в классе является делителем полногочисла ключей. Число «параллельных» линий от сообщения M к криптограмме всоответствующем классе равно числу ключей, деленному на число сообщений в классе,содержащем это сообщение (или криптограмму).В приложении показывается, что это верно для чистых шифров и в общем случае.Резюмируя сказанное, мы имеемТеорема 3.
В чистой системе сообщения можно разделить на множество «остаточныхклассов» С1,...,Сs, а криптограммы – на соответствующее множество остаточных классовС1',...,Сs'. Эти классы будут иметь следующие свойства:1. Остаточные классы сообщений взаимно исключают друг друга и содержат всевозможные сообщения. Аналогичное утверждение верно и для остаточных классовкриптограмм.2.
Если зашифровать любое сообщение из класса Сi с помощью любого ключа, тополучится криптограмма из класса Сi'. Расшифрование любой криптограммы из класса Сi'с помощью любого ключа приводит к сообщению из класса Сi.3. Число сообщений в классе Сi, скажем ji, равно числу криптограмм в классе Сi' иявляется делителем k – числа ключей.184. Каждое сообщение из класса Сi, может быть зашифровано в каждую криптограмму изкласса Сi' при помощи точно k/ji различных ключей. То же самое верно и длярасшифрования.Смысл понятия чистый шифр (и причина для выбора такого термина) лежит в том,что в чистом шифре все ключи являются по существу одинаковыми.
Какой бы ключ нииспользовался для заданного сообщения, апостериорные вероятности всех сообщений будуттеми же самыми. Чтобы показать это, заметим, что два различных ключа, примененных кодному сообщению, дадут в результате две криптограммы из одного остаточного класса,скажем Сi'. Поэтому эти две криптограммы могут быть расшифрованы с помощью k/jiключей в каждое из сообщений в классе Сi, и больше ни в какие возможные сообщения. Таккак все ключи равновероятны, то апостериорные вероятности различных сообщений равныPE ( M ) =P ( M ) × PM ( E )P ( M ) × PM ( E )P(M )==,P(E)å P ( M ) × PM ( E ) P (Ci )Mгде M – сообщение из класса Сi, E – криптограмма из класса С'i и сумма берется по всемM из класса Сi. Если E и M не принадлежат соответствующим остаточным классам, тоPE(M) = 0.Аналогично можно показать, что набор апостериорных вероятностей различныхключей всегда одинаков, но эти вероятности ставятся в соответствие ключам лишь послетого, как уже использован некоторый ключ.
При изменении частного ключа это множествочисел PE(M) подвергается перестановке. Иными словами, имеем:Теорема 4. В чистой системе апостериорные вероятности различных сообщений PE(M)не зависят от выбора ключа. Апостериорные вероятности ключей PE(K) образуют один итот же набор величин, но подвергаются перестановке в результате различных выборовключа.Грубо говоря, можно считать, что любой выбор ключа в чистом шифре приводит кодинаковым трудностям при дешифровании. Поскольку все различные ключи приводят кформированию криптограмм из одного и того же остаточного класса, то все криптограммыиз одного остаточного класса эквивалентны с точки зрения сложности дешифрования – ониприводят к тем же самым апостериорным вероятностям сообщений и, если учитыватьперестановки, к тем же самым вероятностям ключей.В качестве примера чистого шифра может служить простая подстановка сравновероятными ключами.
Остаточный класс, соответствующий данной криптограмме E,является множеством всех криптограмм, которые могут быть получены из E с помощьюопераций TjTk–1E. В рассматриваемом случае операция TjTk–1 сама является подстановкой ипоэтому любая подстановка переводит криптограмму E в другой член того же самогоостаточного класса; таким образом, если криптограмма представляет собойЕ = XCPPGCFQ,тоЕ1 = RDHHGDSN,Е2 = ABCCDBEFи т.д.,принадлежат к тому же остаточному классу. В этом случае очевидно, что криптограммы посуществу эквивалентны.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
