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

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

Коблиц Н. Курс теории чисел и криптографии — Москва: Научное изд-во ТВП, 2001. — 254 c.
Скачать (прямая ссылка): theory-chisel-kriptographii.djvu
Предыдущая << 1 .. 43 44 45 46 47 48 < 49 > 50 51 52 53 54 55 .. 125 >> Следующая


к

вида, например, простых Мерсенна или делителей чисел вида b ± 1 при малых Ь и сравнительно малых А:). Что понимается под «случайно выработанным» простым числом? Это следующее. Сначала вырабатывается большое случайное целое число та. Если та четное, то оно заменяется на т+ 1. Потом, чтобы проверить, является ли это нечетное число простым, используется тест на простоту числа (тесты на простоту подробно изучаются в следующей главе). Если число т не является простым, то проверяются т + 2, потом т + 4 и т. д., пока не будет получено первое простое число, превосходящее т, которое и берется в качестве «случайного» простого. Поскольку по теореме

102

ГЛ. IV. ОТКРЫТЫЙ ключ

о простых числах (формулировку см. в упражнении 13 раздела 1.1) доля простых среди целых вблизи тп составляет примерно 1/log 771, можно ожидать, что для нахождения первого простого, большего или равного тп, потребуется проверить O(logm) чисел.

Подобным образом вырабатывается «случайное» число е, взаимно простое с <р(п). Сначала вырабатывается случайное (нечетное) целое число подходящего размера, которое последовательно увеличивается, пока не будет найдено е с НОД (е, ср(гг)) = 1. (Можно поступать по-другому: проводить проверку на простоту, пока не найдется простое е, скажем, между max(p, q) и <р(п); такое простое обязательно удовлетворяет условию НОД (е,(р(п)) = 1.)

Итак, каждый пользователь А выбирает два простых числа рд, qA, а вслед за этим — случайное число еА, которое не имеет общих множителей с (рд - 1)(<7д - 1). Далее, А вычисляет пА = Рд?д, уз(пд) = гід + 1 — рд — qA и число, обратное относительно умножения к ед по модулю у?(пд): dAd=еА (mod (р(пА)). Ключ шифрования Ке,а = (па,єа) делается открытым, а ключ дешифрования Kd1 а = {nA->dA) — секретным. Шифрующее преобразование — это отображение Ъ/пАЪ в себя по формуле J(P) = РвА (mod пА). Дешифрующее преобразование — это отображение Ъ/пАЪ в себя по формуле / 1(С) = CdA (mod пА). Нетрудно заметить, что согласно нашему выбору dA эти два отображения взаимно обратны. А именно, последовательное применение в любом порядке / и / приводит к возведению в степень dAeA. Поскольку dAeA дает при делении на (f(nA) остаток 1, это эквивалентно возведению в первую степень (см. следствие из предложения 1.3.5, которое гарантирует это, когда P не имеет общих множителей с пА; случай НОД (Р,пА) > 1 рассматривается ниже в упражнении 6).

В приведенном описании множества V и С элементов открытого и шифрованного текстов удовлетворяли условию V = С и были различными для разных пользователей. На практике может возникнуть необходимость выбирать VnC единообразно для всей системы. Пусть, например, используется Л^-буквенный алфавит и к < / — та-

к I

кие натуральные числа, что N и N имеют приблизительно по 200 десятичных разрядов каждое. В качестве элементов открытого текста рассмотрим все блоки по к букв, которые интерпретируются как ^-разрядные /V-ичные числа, т. е. им присваиваются числовые экви-

к

валенты из диапазона между 0 и TV - 1. Аналогично, элементами шифртекста будут блоки из I букв того же алфавита. Каждый пользователь А должен выбрать большие простые числа рд и qA так, чтобы пА — PaQa удовлетворяло неравенствам TV < пА < N . Тогда любой

§ 2. КРИПТОСИСТЕМА RSA

103

элемент открытого текста, т. е. целое число, меньшее TV , соответствует вычету из Z/nAZ (для пользователя А) и, так как пА < N1, то образ J(P) Є Z/nAZ может быть записан в виде /-буквенного блока единственным образом. (При этом возникают не все /-буквенные блоки, а только те, которые отвечают целым, меньшим значения пА, выбранного данным пользователем.)

Пример 1. Ради читателей, не имеющих под рукой компьютера и программного обеспечения, позволяющего производить вычисления с большим числом знаков, мы отойдем от реальности и будем использовать в большинстве наших примеров сравнительно небольшие целые числа. Выберем N = 26, /: = 3,/ = 4. Таким образом, открытый текст составлен из триграмм, а шифртекст — из четырехграмм 26-буквенного алфавита. Чтобы послать сообщение «YES» пользователю А с ключом шифрования (пА,еА) = (46927,39423), мы определяем чи-еловой эквивалент для «YES»: 24-26 + 4 • 26 + 18 = 16346, и затем вычисляем 16 3 4 639423 (mod 46927), что есть 21166 = 1 • 263 + 5 • 262 + 8 • 26 + 2=«BFIC». Адресат А знает ключ дешифрования (nA,dA) = (46927,26767) и вычисляет 2116626767 (mod 46927) = 16346 =«YES». Как же пользователь А построил свои ключи? Сначала он перемножил простые числа рА = 281 и qA = 167 и получил пА, затем случайно (но при условии, что НОД (еА, 280) = НОД (еА, 166) = 1) было выбрано еА. В итоге было найдено dA = еА (mod 280 • 166). Числа рА, qA, dA остались секретными.

Сколь громоздки вычисления в примере 1? Самым трудоемким по времени является возведение в степень по модулю, т. е. вычисление

394 23

16346 (mod 46927). Но оно может быть выполнено методом повтор-ного возведения в квадрат (см. §1.3) за 0{к ) двоичных операций, где к — число бит в наших целых числах. Если бы использовались очень большие целые числа, то для пользователя А самым трудоемким этапом мог бы оказаться поиск пары больших простых чисел рА и qA. Чтобы ускорить поиск очень больших простых чисел, нужно использовать эффективные тесты на простоту. Такие тесты описываются в следующей главе.
Предыдущая << 1 .. 43 44 45 46 47 48 < 49 > 50 51 52 53 54 55 .. 125 >> Следующая

Реклама

c1c0fc952cf0704ad12d6af2ad3bf47e03017fed

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

c1c0fc952cf0704ad12d6af2ad3bf47e03017fed