Курс теории чисел и криптографии - Коблиц Н.
Скачать (прямая ссылка):
Преобразования биграмм. Предположим теперь, что элементами открытого и шифрованного текстов являются двухбуквенные блоки, называемые биграммами. Это значит, что открытый текст
§ 1. НЕКОТОРЫЕ ПРОСТЫЕ КРИПТОСИСТЕМЫ
67
разбивается на двухбуквенные сегменты. Если открытый текст состоит из нечетного числа букв, то, чтобы получить целое число би-грамм, добавим к концу текста еще одну букву, выбрав ее так, чтобы не исказить смысл, например, добавим пробел, если он содержится в нашем алфавите, и «X» или «Q», если имеем дело с 26-буквенным алфавитом.
Каждой биграмме приписывается далее ее числовой эквивалент. Простейший способ — взять его в виде xN + у где X — числовой эквивалент первой буквы биграммы, у — числовой эквивалент второй буквы биграммы, a TV — число букв в алфавите, т.е. рассматривать биграмму как запись двузначного целого числа в системе счисления с основанием N. Это дает взаимно однозначное соответствие между множеством всех биграмм в TV-буквенном алфавите и множеством всех неотрицательных целых, меньших TV . Выше мы рассмотрели частный случай этой процедуры при TV = 27.
Следующий шаг — выбор шифрующего преобразования, т.е. перестановки целых чисел {0,1,2,...,X — 1}. Примером простейших шифрующих преобразований служат аффинные преобразования: указанное множество целых чисел отождествляется с ZfN2Z и при ши-фровании P переходит в неотрицательное целое число, меньшее N и удовлетворяющее сравнению С = aP + b (mod TV2). Здесь, как и раньше, число а должно не иметь общих множителей с N (что означает отсутствие общих множителей и с N ) для того, чтобы существовало обратное преобразование, указывающее способ дешифрования: P = а С + Ъ' (mod TV2), где a' = a"1 (mod TV2), b' = -a~Xb (mod TV2). Мы преобразуем С в двухбуквенный блок шифртекста, записывая его
в виде С = X N + у и затем выписывая буквы с числовыми эквива-/ і
лентами хну.
Пример 5. Пусть мы имеем дело с 26-буквенным алфавитом и используем биграммное шифрующее преобразование С = 159Р + 580 (mod 676). Тогда биграмма «NO» имеет числовой эквивалент 13-26 + 14 = 352, и ей соответствует биграмма шифртекста 159 • 352 + 580 = 440 (mod 676), что есть «QY». Биграмма «ON» имеет числовой эквивалент 377 и переходит в 359=«NV». Заметим, что биграмма преобразуется как единое целое, и между зашифрованными биграммами, имеющими общую букву или даже составленными из одних и тех же букв, но в разном порядке, нет явной связи.
Для того чтобы вскрыть биграммную систему, использующую аффинное преобразование С = aP+b (mod TV ), надо знать шифртекст, соответствующий двум разным элементам открытого текста. Так как элементами текста являются биграммы, то частотный анализ означа-
68
ГЛ. III. КРИПТОГРАФИЯ
ет выделение в длинном отрезке шифртекста двухбуквенных блоков, встречающихся чаще других (разумеется, надо считать только элементы текста и игнорировать пары, образованные буквами соседних элементов), и сравнение с известными частотами биграмм в английских текстах (записанных в том же алфавите). Например, если используется 26-буквенный алфавит, то статистический анализ, скорее всего, покажет, что наиболее частыми биграммами являются «ТН» и «НЕ» (в указанном порядке). Информации о двух парах отвечающих друг другу биграмм открытого и шифрованного текстов зачастую (но не всегда) бывает достаточно для определения а и Ь.
Пример 6. Вы знаете, что ваш противник использует криптосистему с 27-буквенным алфавитом, в которой буквы A-Z имеют числовые эквиваленты 0-25 и пробел=26. Каждой биграмме отве-
2
чает числовой эквивалент — целое число между 0 и 728 = 27 — 1, определяемое по правилу 27х + у, где х и у — числовые эквиваленты букв биграммы. Пусть анализ длинного шифртекста показал, что чаще всего в нем встречаются биграммы «ZA», «IA» и «IW» (в указанном порядке). Предположим, что самыми частыми биграммами в английском языке (в текстах в нашем 27-буквенном алфавите) являются биграммы «Е » (т.е. E и пробел), «S » и « Т». Мы знаем, что криптосистема использует аффинное шифрующее преобразование по модулю 729. Найти ключ дешифрования и прочитать сообщение «NDXBHO». Найти также ключ шифрования.
Решение. Мы знаем, что открытый текст шифруется по правилу С = aP + b (mod 729) и что шифртекст может быть расшифрован по правилу P = а С + У (mod 729), где a, b образуют ключ шифрования, а а ,У — ключ дешифрования. Сначала мы хотим найти а и У. Нам известно, как расшифровываются три биграммы. Заменив эти биграммы их числовыми эквивалентами, получим три сравнения
675а' + У = 134 (mod 729), 216а' + У = 512 (mod 729), 238а' + У = 721 (mod 729).
Если исключить У, взяв разность первых двух сравнений, то получим 459а =351 (mod 729), что не дает единственного решения a (mod 729) (имеется 27 решений). Будет лучше, если вычесть из первого сравнения третье, что даст 437а' = 142 (mod 729). Для решения последнего сравнения надо найти число, обратное к 437 по модулю 729. Воспользуемся алгоритмом Евклида:
§ 1. НЕКОТОРЫЕ ПРОСТЫЕ КРИПТОСИСТЕМЫ
69
