Курс теории чисел и криптографии - Коблиц Н.
Скачать (прямая ссылка):
§ 2. ШИФРУЮЩИЕ МАТРИЦЫ
73
«Е » и «S » при шифровании переходят в биграммы «FQ» и «LE» соответственно. Найти ключ дешифрования и прочитать сообщение «YAVAOCH'D!».
16. Продолжая упражнение 15, покажем, как можно без особого труда построить криптоситему, вскрыть которую существенно труднее. Пусть /і — криптосистема описанного в упражнении 15 типа, т.е. заданная правилом /i (P) = а\Р + Ь\ (mod Li), и пусть /2 — другая криптосистема того же типа. Параметры .V и M у этих систем одни и те же, но параметры а, Ъ и L у каждой системы свои. Пусть L2 > Ь\. Построим композицию (произведение) этих двух криптоситем (см. упражнение 14), т.е. будем зашифровывать элемент P открытого текста по правилам
I = а\Р + Ь\ (mod Li), С = ail + 62 (mod L2)-
(В первом случае I — неотрицательное целое число, меньшее Li и удовлетворяющее первому сравнению, во втором правиле С меньше L2.) Поскольку модули L\ и L2 различны, утверждения из упражнения 14 в) здесь неприменимы, и эта композиция криптосистем, вообще говоря, не является аффинной системой. Здесь мы предполагаем, что алфавиты из N и M букв заданы, но можно произвольным образом выбирать параметры ai, 61, Li, аг, Ьг> L2, подчиненные, разумеется, условиям N2 < Lx < L2 < M2, НОД (auLi) = 1, НОД (a2,L2) = 1- Таким образом, ключ состоит из шестерки параметров {щ , bi, Li, а2, 62, L2 }. Пусть, как и в упражнении 15, алфавиты открытого и шифрованного текстов содержат по 27 и 30 букв, соответственно. Пусть ключ шифрования имеет вид {247,109,757,675,402,881}. Объяснить, как проводить дешифрование, и дешифровать сообщение «DIRAJ'KCTN».
§ 2. Шифрующие матрицы
Пусть имеется /V-буквенный алфавит и нам надо передавать биграммы (двухбуквенные блоки) как элементы сообщения. В §1 было показано, что каждой биграмме можно сопоставить целое число по
2 2
модулю Л' , т.е. элемент из Z/N Z. Другая возможность состоит в сопоставлении биграмме некоторого вектора, т.е. пары целых чисел (^) с X и у, рассматриваемыми по модулю N. Например, если имеется 26-буквенный алфавит A-Z с числовыми эквивалентами 0-25 соответственно, то биграмме NO отвечает вектор (\3), как показано на диаграмме.
Мы изображаем каждую биграмму как узел в квадратной решетке размера NxN. Наше изображение аналогично обычной координатной плоскости с той разницей, что каждая из осей соответствует не множеству вещественных чисел, а множеству Z/NZ. Аналогично обо-значению R для обычной плоскости будем использовать обозначение (ZINZ) для этой решетки размера NxN.
Изобразив биграммы векторами (точками на плоскости), мы можем интерпретировать «шифрующее преобразование» как перестановку узлов нашей N х ^-решетки. Точнее, шифрующее отображе-
74
ГЛ. III. КРИПТОГРАФИЯ
ниє — это взаимно однозначное отображение (Z/7VZ)2 в себя.
DO N
NO
ZWZ
ND
ZAVZ
Замечание. В течение нескольких веков одним из самых распространенных способов шифрования был так называемый «шифр Ви-женера». Его можно описать следующим образом. При некотором заданном к рассмотрим блоки из к букв как векторы в (Z/NZ)k. Зафиксируем некоторый вектор Ь Є (Z/NZ)k (обычно выбирается вектор, соответствующий какому-нибудь легко запоминаемому «ключевому слову»). Шифрование проводится посредством векторного сдвига С = P + Ь. где элемент шифртекста С и элемент открытого текста P представляют собой векторы с целочисленными координатами по модулю N. К сожалению, эта криптосистема вскрывается почти так же просто, как сдвиг отдельных букв (см. пример 1 в предыдущем разделе). А именно, при известных или угаданных N и к нужно просто разбить текст на блоки по к букв и провести частотный анализ первых букв в каждом блоке, чтобы определить первую компоненту вектора Ь. Затем исследуются вторые буквы блоков, и т. д.
Сведения из линейной алгебры. Напомним, как проводятся операции с векторами в вещественной двумерной плоскости и с 2 X 2-матрицами из вещественных чисел. Напомним, что, имея 2x2-матрицу (" ^) и вектор (*) (мы будем записывать векторы как столбцы), можно получить новый вектор, применив матрицу к вектору по правилу
При фиксированной матрице эта функция, переводящая вектор в вектор, называется линейным преобразованием, так как она перестановочна с операциями сложения векторов и умножения векторов на кон-
§ 2. ШИФРУЮЩИЕ МАТРИЦЫ 75
D \-с a J \-D 1C D 1O
Сущетвует три возможных вида множества решений системы уравнений AX = В. Во-первых, если определитель D отличен от нуля, то система имеет единственное решение X= (р. Если же D = 0, то либо решений нет, либо их бесконечно много. Эти три варианта имеют простую геометрическую интерпретацию. Два уравнения соответствуют двум прямым на координатной плоскости. Если D ф 0, то прямые пересекаются в единственной точке (х,у). В противном случае они либо параллельны и не пересекаются вовсе (уравнения системы не имеют общих решений), либо совпадают (уравнения системы имеют бесконечно много общих решений).
станты. В этих обозначениях любая система уравнений вида ах + by = е, сх + dy = f эквивалентна матричному уравнению AX = В, где А обозначает матрицу