Научная литература
booksshare.net -> Добавить материал -> Математика -> Коблиц Н. -> "Курс теории чисел и криптографии" -> 37

Курс теории чисел и криптографии - Коблиц Н.

Коблиц Н. Курс теории чисел и криптографии — Москва: Научное изд-во ТВП, 2001. — 254 c.
Скачать (прямая ссылка): theory-chisel-kriptographii.djvu
Предыдущая << 1 .. 31 32 33 34 35 36 < 37 > 38 39 40 41 42 43 .. 125 >> Следующая


§ 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 = В, где А обозначает матрицу
Предыдущая << 1 .. 31 32 33 34 35 36 < 37 > 38 39 40 41 42 43 .. 125 >> Следующая

Реклама

c1c0fc952cf0704ad12d6af2ad3bf47e03017fed

Есть, чем поделиться? Отправьте
материал
нам
Авторские права © 2009 BooksShare.
Все права защищены.
Rambler's Top100

c1c0fc952cf0704ad12d6af2ad3bf47e03017fed