Пред.
След.
Макеты страниц
Распознанный текст, спецсимволы и формулы могут содержать ошибки, поэтому с корректным вариантом рекомендуем ознакомиться на отсканированных изображениях учебника выше Также, советуем воспользоваться поиском по сайту, мы уверены, что вы сможете найти больше информации по нужной Вам тематике ДЛЯ СТУДЕНТОВ И ШКОЛЬНИКОВ ЕСТЬ
ZADANIA.TO
7. Чистые и смешанные шифрыНекоторые типы шифров, такие как простая подстановка, транспозиция с данным периодом, система Виженера с данным периодом, система Виженера со смешанным алфавитом и т. д. (все с равновероятными ключами), обладают некоторой однородностью по отношению к ключу. Каков бы ни был ключ, процессы шифрования, дешифрирования адресатом и дешифрирования противником являются по существу теми же самыми. Эти системы можно противопоставить системе с шифром
где Рис. 4. (см. скан) Причина однородности таких систем лежит в групповом свойстве: заметим, что в приведенных выше примерах однородных шифров произведение
который содержит только подстановки и транспозиции, но не их произведения. Было бы можно, таким образом, определить «чистый» шифр как шифр, в котором
и все ключи равновероятны. В противном случае шифр является смешанным. Шифры на рис. 2 являются смешанными, а на рис. 4 — чистыми, если только все ключи равновероятны. Теорема 1. В чистом шифре операции отображающие пространство сообщений в себя, образуют группу, порядок которой равен Так как
то каждый элемент имеет обратный. Ассоциативный закон верен, так как это операции, а групповое свойство следует из того, что
где предполагалось, что Операция
Теорема 2. Произведение двух чистых коммутирующих шифров является чистым шифром. Если
Условие коммутирования не является, однако, необходимым для того, чтобы произведение было чистым шифром. Система, состоящая из одного ключа, т. е. из единственной определенной операции
Таким образом, разложение шифра в сумму таких простых отображений представляет собой разложение в его сумму чистых шифров. Исследование примера, приведенного на рис. 4, вскрывает некоторые свойства чистого шифра. Сообщения распадаются на определенные подмножества, которые мы будем называть остаточными классами, и возможные криптограммы также распадаются на соответствующие им остаточные классы. От каждого сообщения в любом классе к каждой криптограмме в соответствующем классе имеется не менее одной линии и нет линий между несоответствующими классами. Число сообщений в классе является делителем полного числа ключей. Число «параллельных» линий от сообщения В приложении показывается, что это верно для чистых шифров и в общем случае. Резюмируя сказанное, мы имеем Теорема 3. В чистой системе сообщения можно разделить на множество «остаточных классов» 1. Остаточные классы сообщений взаимно исключают друг друга и содержат все возможные сообщения. Аналогичное утверждение верно и для остаточных классов криптограмм. 2. Если зашифровать любое сообщение из класса 3. Число сообщений в классе 4. Каждое сообщение из класса Смысл понятия чистый шифр (и причина для выбора такого термина) лежит в том, что в чистом шифре все ключи являются по существу одинаковыми. Какой бы ключ ни использовался для заданного сообщения, апостериорные вероятности всех сообщений будут теми же самыми. Чтобы показать это, заметим, что два различных ключа, примененных к одному сообщению, дадут в результате две криптограммы из одного остаточного класса, скажем
где Аналогично можно показать, что набор апостериорных вероятностей различных ключей всегда одинаков, но эти вероятности ставятся в соответствие ключам лишь после того, как уже использован некоторый ключ. При изменении частного ключа это множество чисел Теорема 4. В чистой системе апостериорные вероятности различных сообщений Грубо говоря, можно считать, что любой выбор ключа в чистом шифре приводит к одинаковым трудностям при дешифрировании. Поскольку различные ключи все приводят к формированию криптограмм из одного и того же остаточного класса, то все криптограммы из одного остаточного класса эквивалентны с точки зрения сложности дешифрирования — они приводят к тем же самым апостериорным вероятностям сообщений и, если учитывать перестановки, к тем же самым вероятностям ключей. В качестве примера чистого шифра может служить простая подстановка с равновероятными ключами. Остаточный класс, соответствующий данной криптограмме
то
принадлежат к тому же остаточному классу. В этом случае очевидно, что криптограммы по существу эквивалентны. Все существенное в простой подстановке со случайным ключом заключено в характере повторения букв, в то время как сами буквы являются несущественной маскировкой. В действительности можно бы полностью обойтись без них, указав характер повторений букв в
Это обозначение описывает остаточный класс, но устраняет всю информацию относительно конкретных членов этого класса; таким образом, оно представляет как раз ту информацию, которая имеет значение для шифровальщика противника. Это связано с одним из методов подхода к раскрытию шифров типа простой подстановки методом характерных слов. В шифре типа Цезаря имеют значение только первые разности криптограммы по модулю 26. Две криптограммы с теми же самыми разностями Шифр Виженера с периодом
где В транспозиции с периодом
Затем столбцы переставляются до тех пор, пока не получится осмысленный текст. После того как криптограмма разбита на столбцы, оставшейся существенной информацией является только остаточный класс криптограммы. Теорема 5. Если шифр Первая часть этой теоремы следует, очевидно, из определения чистого шифра. Чтобы доказать вторую часть, заметим сначала, что если
Слагаемое в стоящей слева сумме с
То же самое рассуждение остается справедливым, если
и
|
1 |
Оглавление
|