Шифры гаммирования. Табличное гаммирование.
Латинским квадратом, называется квадратная таблица в каждой строке и в каждом столбце которой ровно 1 раз встречается каждый элемент некоторого множества.
Шифр
табличного гаммирования в алфавите
определяется произвольным латинским
квадратом L
на A
и способом получения последовательности
букв из А, называемой гаммой шифра. Буква
открытого текста под действием знака
гаммы
переходит в букву
шифрованного текста, содержащуюся в
j-й
строке и i-том
столбце квадрата L
(подразумевается, что строки с столбцы
L
занумерованы в соответствии с порядком
следования букв в алфавите A).
См. шифр Виженера в самом начале.
Чт, сен 29 2005 09:54:02
В общем виде формула для
шифров гаммирования имеет вид:
(это
выражение обозначает остаток от деления
на n
от суммы в скобках).
Как шифр замены, шифр гаммирования имеет следующую интерпретацию.
исходя из этого любую i-тую
строчку таблицы можно представить в
следующем виде:
Если j=i, то…
В
i-тый
момент в зависимости от значения
мы осуществляем подстановку:
Пример:
- выработано каким-то устройством (шифратором), которое накладывается на открытый текст.
Посл.
значение
О возможности восстановления вероятности знаков .
Предположим:
В качестве алфавита А:
-
занумеруем буквы алфавита от 0 до n-1.
- открытый текст, шифртекст, и гамма берутся из одного и того же алфавита.
Пусть:
-
нельзя оценить (не зная ключа и
идентификатора (?));
- вероятность появления знака i в открытом тексте, гамме и шифртексте соответственно.
Тогда задание вероятностных распределений на знак открытого текста и гаммы (которые естественно считать независимыми) индуцирует распределение вероятностей знаков шифртекста по формуле:
в которой разность
берётся по модулю n.
y=j в случаях:
Это означает, что при зашифровании открытого текста равновероятной гаммой получается шифртекст, вероятные свойства которого не отличаются от самой равновероятной гаммы. Это обстоятельство не оставляет шансов криптоаналитику использовать диаграмму повторяемости букв открытого текста, поскольку при наложении гаммы эта информация как бы стирается. Поэтому на практике стремятся к тому, чтобы по своим вероятностным свойствам гамма была близка к случайной равновероятной последовательности.
Определитель этой системы
Такая матрица называется циркулянтом, в ней каждая строка получается циклическим сдвигом предыдущей строки.
Линейная система имеет решение, если определитель не равен 0.
Восстановление текстов при зашифровке не равновероятной гаммы.
Предположим, что в качестве знаков гаммы встречаются только такие знаки:
Которые встречаются с
вероятностями
,
соответственно.
В качестве знаков шифр текста (предположим, что шифрованию подлежала одна из следующих букв открытого текста):
(*)
Поэтому знаки открытого текста следует искать в колонках таблицы, следующим образом:
Зигзагообразное чтение – перебор.
Отбирая по одному знаку из каждой колонки так, чтобы получался «читаемый» текст, мы получим возможность восстановить открытый текст.
Описанный метод относится к классу так называемых методов безключевого чтения (когда открытый текст восстанавливается без предварительного определения ключа) и называется методом чтения в колонках.
Адаптация по вероятности знаков. Метод чтения в колонках можно усовершенствовать за счёт упорядочения букв в колонках. В самом деле, в каждом такте возможные знаки открытого текста
имеют
априорные вероятности
,
которые считаются известными. В нашем
случае имеется также дополнительная
информация, а именно известно, что
произошло событие «
»
-
вероятность того, в этот момент появится
значение k.
Отсюда по формуле Байеса получаем:
Теперь можно упорядочить вероятности (*) знаков открытого текста в каждой колонке таблицы в соответствии с убыванием вычисленных априорных вероятностей. Поместим наиболее вероятные знаки открытого текста в начало таблицы, чем облегчим чтение в колонках. С ростом m чтение в колонках становится затруднительными, я при m=n и при условии, что при шифровании использовалась случайная равновероятная гамма, каждая колонка содержит все знаки алфавита, ни одному из которых нельзя отдать предпочтения. Поэтому в последовательности колонок можно прочитать любой текст, то есть нет возможности получить информацию об открытом сообщении.
06.10.05