Курс теории чисел и криптографии - Коблиц Н.
Скачать (прямая ссылка):
Параметр b (более сложные криптосистемы обычно используют несколько параметров) называется ключом или, более точно, ключом шифрования.
Пример 2. Так, предположим, что перехвачено сообщение «FQOCUDEM», которое, как нам известно, зашифровано с использованием преобразования сдвига на буквах 26-буквенного алфавита, как в примере выше. Нам остается найти Ь. Сделать это можно при помощи частотного анализа. Он работает следующим образом. Предположим, что нами перехвачен длинный отрезок шифртекста, скажем, несколько сотен букв. Мы знаем, что «Е» — наиболее часто встречающаяся буква английского языка. Поэтому разумно предположить, что наиболее часто встречающаяся в шифртексте буква является результатом шифрования буквы «Е». Пусть чаще других в шифртексте встречается буква «U». Это значит, что сдвиг преобразует «Е»= 4 в «U»= 20, т.е. 20 = 4 + b (mod 26), так что b = 16. Чтобы дешифровать сообщение, остается вычесть 16 (по модулю 26) из числовых эквивалентов «FQOCUDEM»:
«FQOCUDEM» = 5 1614 2 20 3 412
к* 15 0 2412413 1422 = «PAYMENOW».
Если шифрование сдвигом применяется к буквам 26-буквенного алфавита, то нет необходимости иметь длинный отрезок шифртекста, позволяющий найти наиболее часто встречаемую букву. В конце концов, для b имеется всего 26 возможностей, и можно просто попробовать их все. Скорее всего, лишь одному из значений Ь будет соответствовать осмысленное сообщение, такое b и есть ключ шифрования.
Значит, этот тип криптосистем слишком прост, чтобы быть хорошим. Вскрыть его очень легко. Его можно усовершенствовать, используя более широкий класс преобразований Z/NZ, называемых аффинными отображениями: С = aP+b (mod N), где а и 6 — фиксированные целые числа (вместе они образуют ключ шифрования). Если,
§ 1. НЕКОТОРЫЕ ПРОСТЫЕ КРИПТОСИСТЕМЫ
65
например, опять имея дело с 26-буквенным алфавитом, мы хотим зашифровать сообщение «PAYMENOW», используя аффинное отображение с ключом шифрования а = 7 и Ь = 12, то получим
15 0 24 12 4 13 14 22 h-> 13 12 24 18 14 25 6 10 = «NMYSOZGK».
Чтобы расшифровать сообщение, зашифрованное применением аффинного отображения С = аР + b (mod TV), нужно просто выразить P через С: P = а!С + b' (mod N), где а' = а 1 есть обратное к а по модулю TV число, a b' равно -а lb. Заметим, что это возможно лишь при НОД (a, N)=I. В противном случае нельзя выразить P через С: если НОД (a, N) > 1, то, как нетрудно убедиться, одной букве шифртекста отвечает несколько букв открытого текста, и поэтому нельзя однозначно восстановить открытый текст по шифрованному. По определению такое преобразование не является шифрующим, так как последнее обязано быть взаимно однозначным, т.е. открытый текст должен определяться шифртекстом однозначно. Итак, аффинная криптосистема над TV-буквенным алфавитом с параметрами а Є (Z/TVZ)* и Ь Є Z/TVZ задается правилами
С = аР + b (mod TV), P = а С + Ь1 (mod N),
где a = a 1B (Z/7VZ)*, b' = —а ХЬ.
Как частный случай аффинной криптосистемы при а = 1 получаем преобразования сдвига. В другом частном случае при 6 = 0 получаем P = аС (mod N), С = a P (mod TV). Такое преобразование называется линейным. Оно отображает сумму в сумму, т.е. если Р\ при шифровании переходит в С\, a P2 — в C2, то P1 + P2 переходит в C1 + C2 (сложение, конечно, производится по модулю TV).
Пусть теперь нам известно, что перехваченное сообщение зашифровано применением аффинного отображения букв TV-буквенного алфавита. Мы хотим определить ключ а,Ь, чтобы прочитать это сообщение. Для этого нужно знать, как зашифровываются какие-нибудь две буквы.
Пример 3. По-прежнему используем 26-буквенный алфавит. Допустим, что в шифртексте чаще всего встречается буква «К», а вторая по встречаемости буква — «D». Разумно предположить, что ими зашифрованы две наиболее часто встречающиеся буквы английского языка «Е» и «Т». Заменяя буквы их числовыми эквивалентами и подставляя последние в формулу дешифрования, получаем:
10а' + b' = 4 (mod 26), За' + Ъ' = 19 (mod 26).
66
ГЛ. III. КРИПТОГРАФИЯ
Мы имеем два сравнения с двумя неизвестными а и b'. Кратчайший способ решения — вычесть одно сравнение из другого, чтобы исключить Ь'. Получаем Ia = 11 (mod 26) и а = 7—111 = 9 (mod 26). Наконец, находим b , подставив это значение а в одно из сравнений: b' = 4 —10а' = 18 (mod 26). Итак, сообщение может быть дешифровано применением формулы P = 9С + 18 (mod 26).
Из линейной алгебры известно, что п уравнений позволяют определить п неизвестных только тогда, когда эти уравнения независимы (т.е. когда определитель системы отличен от нуля). Например, в случае двух уравнений с двумя неизвестными это означает, что прямолинейные графики уравнений пересекаются в одной точке (не параллельны). В нашем случае при попытке провести криптоанализ аффинной системы на базе информации о двух наиболее часто встречаемых буквах шифртекста может оказаться, что два сравнения не могут быть однозначно разрешены относительно а и b .
Пример 4. Пусть имеется отрезок шифртекста, полученного применением аффинного преобразования 28-буквенного алфавита, содержащего буквы A-Z, пробел и знак ?, причем буквы имеют численные эквиваленты 0-25, пробел=26, ?=27. Пусть частотный анализ показал, что чаще всего в шифртексте встречаются «В» и «?» (в указанном порядке). Поскольку самыми частыми буквами в английском письменном тексте в таком 28-буквенном алфавите являются пробел и «Е» (в указанном порядке), мы предполагаем, что пробел при шифровании переходит в «В», а «Е» — в «?». Это приводит к двум сравнениям a -\-b' = 26 (mod 28), 27а' + b' = 4 (mod 28). Вычитая одно из другого, получаем 2а' = 22 (mod 28), что эквивалентно сравнению а = 11 (mod 14). Это означает, что а = 11 или 25 (mod 28), а тогда b' ~ 15 или 1 (mod 28) соответственно. Оба допустимых аффинных преобразования HC + 15 и 25С -f- 1 дают пробел и «Е» как буквы открытого текста, отвечающие «В»и «?» соответственно. Теперь можно испытать обе возможности и определить, какой вариант дает осмысленное сообщение. А можно продолжить частотный анализ. Пусть «I» — третья по частоте встречаемости буква шифртекста. Используя тот факт, что «Т» — третья по частоте встречаемости буква английского языка (из наших 28 букв), получаем третье сравнение 8а' + b' = 19 (mod 28). Эта дополнительная информация достаточна для того, чтобы выбрать из двух аффинных отображений правильное: ПС + 15.
