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

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

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


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 вариантов выбора параметра &, по одному варианту на каждую неделю следующего года.
Предыдущая << 1 .. 26 27 28 29 30 31 < 32 > 33 34 35 36 37 38 .. 125 >> Следующая

Реклама

c1c0fc952cf0704ad12d6af2ad3bf47e03017fed

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

c1c0fc952cf0704ad12d6af2ad3bf47e03017fed