Курс теории чисел и криптографии - Коблиц Н.
Скачать (прямая ссылка):
Поэтому еще рано судить о том, какие из криптосистем: типа RSA (основанные на сложности разложения целых чисел) или системы дискретного логарифмирования, окажутся более надежными.
УПРАЖНЕНИЯ
Замечание. Упражнения 4, 6, 7 в) и 8 предназначены для читателей, располагающих компьютерами с программами умножения многократной точности. (Необходимы лишь программы для вычисления аь (mod т) для очень больших целых чисел а,Ь,т, Напомним, что a-1 (mod р) может быть вычислено как
1. Если приходится проводить много вычислений в некотором не очень большом конечном поле Fg1 то можно сэкономить время, составив полную «таблицу логарифмов». Для этого выбирается порождающий элемент д в F, и строится таблица пар п,дп для всех п от 1 до q — 1. К двум столбцам этой таблицы присоединяются третий и четвертый столбцы, содержащие все пары a,\ogg а. Для этого располагаем элементы а из в третьем столбце в некотором удобном для нас порядке, а затем просматриваем первые два столбца, и ставим в четвертый столбец рядом с а то значение п, при котором д" = а. Например, для Fg (см. пример 2 в
§ 3. ДИСКРЕТНОЕ ЛОГАРИФМИРОВАНИЕ
119
§11.1) выбираем д как корень а многочлена X2 — X — 1 и строим таблицу
п
9п
а
1
а
1
8
2
а + 1
-1
4
3
-а + 1
а
1
4
-1
а + 1
2
5
—а
а - 1
7
6
-а - 1
—а
5
7
а - 1
-а + 1
3
8
1
-а - 1
6
После этого умножение и деление сводятся к сложению или вычитанию по модулю q — 1 и использованию таблицы. Например, для умножения а — 1 на —а — 1 надо найти эти два числа в третьем столбце, сложить отвечающие им логарифмы:
7 + 6 = 5 (mod 8), и, наконец, найти ответ —а во втором столбце рядом с числом 5 из первого столбца.
а) Построить таблицу логарифмов для Fj1 и воспользоваться ею для вычисления 16 ¦ 17, 19 • 13, 1/17, 20/23.
б) Построить таблицу логарифмов для Fg и воспользоваться ею для вычисления следующих элементов (здесь а — корень X3 + X + 1): (а -4- 1)(а2 -4- а), (а2 + а + 1)(а2 + 1), 1/(о2 + 1), а/(а2 + а + 1). Ответы должны быть записаны в виде многочленов от а не выше второй степени.
2. На первый взгляд кажется, что при постановке задачи дискретного логарифмирования вместо F* можно использовать циклическую группу (Z/paZ)* (см. упражнение 2 а) к § II.1). Однако задача дискретного логарифмирования для Z/paZ при а > 1 даже при больших а лишь немногим сложнее задачи логарифмирования при а = 1 (т.е. для Fp). Точнее, используя приемы, описанные в этом упражнении, можно доказать, что если мы можем решать задачу дискретного логарифмирования «по модулю р», то для логарифмирования «по модулю р°» остается произвести лишь небольшую дополнительную работу за полиномиальное по logpa = a log р время. (Напомним, что пока нет алгоритма дискретного логарифмирования «по модулю р» при больших р за полиномиальное относительно logр время, и специалисты сомневаются в том, что такой алгоритм существует.)
8 этом упражнении мы увидим, что при р = 3 существует несложный алгоритм дискретного логарифмирования «по модулю 3Q» за полиномиальное по а время.
Итак, возьмем д = 2 (легко показать, что 2 — порождающий элемент (Z/3aZ)* при любом а). Пусть а — некоторое целое не делящееся на 3 число, и нужно решить сравнение 2х = a (mod 3a). Показать, что приводимый ниже алгоритм всегда позволяет найти х за полиномиальное относительно а время, и оценить (в терминах О-большое) необходимое для этого число двоичных операций.
1) Показать, что эта задача дискретного логарифмирования эквивалентна решению сравнения 2ха = 1. Далее показать, что без потери общности можно считать, что a = 1 (mod 3), и — четное число. Поэтому исходное сравнение можно заменить сравнением 4ха = 1 (mod 3Q).
2) Запишем X = хо + Зхі +• • • + 3°-2ха-2, где Xj — разряды числа х в троичной системе счисления. Возьмем X-I =0. Тогда сравнение
4«0+3S1+-+з' Ч_2а = ! (mod 3j)
(*);
1 ?KJ
гл. iv. открытый ключ
выполнено при j = 1. Положим <7i = 4. В процессе работы в качестве промежуточных результатов наш алгоритм будет вычислять 0jd=43J_1 (mod 3Q).
Положим ai = а. При j > I определим a j как наименьший положительный вычет по модулю За числа 4*о+Зіі + ---+з-' 2іу_2а гт0 ходу алгоритма мы будем последовательно вычислять a.j.
3) Пусть j > 1 и уже найдены такие го, ¦ • ¦, Zj-Зі что выполнено сравнение (*)j _i. Предположим также, что мы уже вычислили gj _i =43"1 2 (mod 3а) и Oj _i. Сначала полагаем Zj_2 равным (1 — а;-_і)/3J-1 по модулю 3. (Заметим, что в силу
имеем aj_i = 1 (mod З-*-1).) Далее вычисляем dj = З;іі2а;'-1 (mod 3а). Наконец, если j < а, вычисляем gj, возводя <7j-i в третью степень в кольце вычетов по модулю За.
4) Если j = а, то алгоритм свою работу заканчивает.
3. Вы с вашим другом договорились поддерживать связь, используя аффинное преобразование шифрования С = AP + В (mod N) (см. примеры 3 и 4 в § III. 1; в этих примерах коэффициенты преобразования обозначались строчными буквами а и Ь). Элементами сообщений являются отдельные буквы 31-буквенного алфавита, в котором A-Z имеют числовые эквиваленты 0-25, пробел = 26, . = 27, ?=28, ! = 29, ' = 30. Вы рассматриваете ключ Ke = {Л, В) как элемент А + Bi поля из 312 элементов (г обозначает корень из —1 в этом поле). Вы также договорились обменяться ключами с помощью системы Диффи-Хеллмана и взять д = 4 + і. Затем вы выбираете случайно секретное целое число а = 209. Ваш друг прислал вам свое значение gb = 1 + 19г.
