Курс теории чисел и криптографии - Коблиц Н.
Скачать (прямая ссылка):
62
ГЛ. III. КРИПТОГРАФИЯ
станавливающая открытый текст по шифртексту. Всю эту ситуацию можно схематически изобразить диаграммой
f f-1
Любая такая конструкция называется криптосистемой.
Первый шаг в создании криптосистемы состоит в обозначении всех возможных элементов открытого и шифрованного текстов математическими объектами, на которых легко строить функции. Часто такими объектами являются числа из некоторого диапазона. Например, если элементами открытого и шифрованного текстов являются отдельные буквы латинского 26-буквенного алфавита от А до Z, то можно обозначать буквы числами 0,1,...,25, которые будем называть их «числовыми эквивалентами». Так, вместо А мы пишем 0, вместо S — 18, а вместо X — 23. Если же, например, элементарными сообщениями являются биграммы букв 27-буквенного алфавита, состоящего из букв A-Z и пробела, то можно сопоставить пробелу числовой эквивалент 26 (следующий за эквивалентом для Z), а в качестве обозначения для биграммы, состоящей из двух букв с эквивалентами X. у Є {0,1,..., 26}, взять целое число
21 х + у Є {0,1,...,728}.
Таким образом, мы рассматриваем отдельные буквы как разряды 27-ричного числа, а саму биграмму — как двузначное число по основанию 27. Например, биграмме «NO» соответствует целое число 27 • 13 + 14 = 365. Аналогично, если в качестве элементов текста используются триграммы, их можно обозначать числами 129x + 21y-\-z Є {0,1,...,19682}. В общем случае ^-буквенные блоки iV-буквенного
к
алфавита можно обозначать целыми числами между OnN — 1, рассматривая каждый такой блок как /с-разрядное целое число в системе, счисления с основанием N.
, Иногда удобнее обозначать элементарные сообщения иными математическими объектами, нежели целые числа, например, векторами или точками некоторой кривой. Hq в данной главе в качестве обозначений используются только целые числа.
Примеры. Начнем со случая, когда элементами сообщений (как открытого, так и шифрованного) являются буквы Л7-буквенного алфавита, обозначенные числами 0,1,2,... ,N — 1. Тогда по определению преобразование шифрования является перестановкой этих N чисел.
Для ускорения шифрования и дешифрования удобно иметь относительно простое правило реализации такой перестановки. Один из
§ 1. НЕКОТОРЫЕ ПРОСТЫЕ КРИПТОСИСТЕМЫ
63
способов — рассматривать множество целых {0,1,2,...,X — 1} как Z/7VZ и использовать на нем операции сложения и умножения по модулю N.
Пример 1. Предположим, что используется 26-буквенный алфавит A-Z с числовыми эквивалентами 0-25. Пусть буква P Є {0,1,...,25} представляет собой элемент открытого текста. Определим функцию / из множества {0,1,..., 25} на себя правилом
Другими словами, / просто прибавляет 3 по модулю 26: f(P) = P + 3 (mod 26). Последнее определение, использующее модульную арифметику, удобнее для записи и для работы с ним. Так, в данной системе для зашифрования слова «YES» сначала мы преобразуем буквы в цифры: 24 4 18, затем прибавляем 3 по модулю 26: 1 7 21 и переходим обратно к буквам: «BHV». Для дешифровки сообщения надо вычесть 3 по модулю 26. Например, шифртекст «ZKB» переходит в открытый текст «WHY». Эта криптосистема, по-видимому, использовалась в Древнем Риме Юлием Цезарем, который, как предполагается, изобрел ее сам.
Пример 1 можно обобщить следующим образом. Предположим, что используется TV-буквенный алфавит с числовыми эквивалентами 0,1,...,7V — 1. Пусть Ь — фиксированное целое. Под преобразованием сдвига мы понимаем функцию /, определенную по правилу С = f{P) = P + b (mod N). Шифрсистема Юлия Цезаря отвечает случаю N = 26, b = 3. Для дешифрования элемента шифртекста С Є {0,1,..., N — 1} надо просто вычислить P = /1 (С) = С — b (mod N).
Теперь предположим, что вы не обладаете информацией о правилах зашифрования и дешифрования, но, тем не менее, хотите прочитать кодированное сообщение. Такое действие называется вскрытием кода, а наука о вскрытии кодов называется криптоанализом.
Для вскрытия криптосистемы нужна, информация двух видов. Первый вид — это информация о природе (структуре) криптосистемы. Например, может быть известно, что криптосистема использует преобразование сдвига отдельных букв 26-буквенного алфавита A-Z с числовыми эквивалентами 0-25 соответственно. Второй вид информации — это информация о конкретном выборе некоторых параметров рассматриваемой криптосистемы. В нашем примере второй тип информации — это значение параметра сдвига Ь. Имея эту информацию, можно по формулам С = P + b (mod N) и P = С - b (mod N) производить шифрование и дешифрование.
№ = {
P + 3, если P < 23, P - 23, если X ^ 23.
64
ГЛ. III. КРИПТОГРАФИЯ
Будем всегда предполагать, что общая структура системы известна. На практике пользователи часто имеют оборудование для шифрования и дешифрования, предназначенное для реализации только одной криптосистемы. Со временем возможна утечка, информации о типе используемой системы. Поэтому для повышения надежности производят частую смену выбираемых параметров системы. Например, два пользователя криптосистемы с преобразованием сдвига могут встречаться раз в год. При каждой встрече они согласовывают список из 52 вариантов выбора параметра &, по одному варианту на каждую неделю следующего года.