Об использовании свойства коммутирования символа степенного вычета в схемах открытого распределения ключа

• Автор: Назаров, Вадим Владиславович
• Шифр специальности: 01.01.06
• Научная степень: Кандидатская
• Год защиты: 2006
• Место защиты: Москва
• Количество страниц: 91 с.

1 Введение
1.1 Описание основных результатов диссертации
1.2 Схемы открытого распределения ключа
1.3 Схема на основе символа степенного вычета
1.4 Основные результаты диссертации
2 Общие свойства схемы
2.1 Общие свойства схемы
2.2 Построение некоммутативной операции
2.2.1 Построение операции на основе коммутативной полугруппы и мультипликативной функции
2.2.2 Свойства схемы при использовании операции на основе мультипликативных функций
3 Схема на основе логарифмических функций
3.1 Построение и свойства некоммутативной операции
3.2 Описание коммутирующих множеств
3.3 Криптоанализ схемы
4 Схема на основе символа степенного вычета.
Случай ц() = д()
4.1 Описание коммутирующих множеств
4.1.1 Аддитивный период символа норменного вычета
4.1.2 Структура группы (Й[(р]/(ЛР))*
4.1.3 Переход к векторному пространству
4.1.4 Оценка размерности максимальных тривиальных подпространств формы ф
4.2 Оценка стойкости схемы
4.3 Алгоритм вычисления символа норменного вычета
4.3.1 Логарифмические функции из Щ(р} в Z/pZ
4.3.2 Вычисление логарифмических функций из Щ(р в 2/рй
4.3.3 Алгоритм вычисления символа норменного вычета
5 Схема на основе символа норменного вычета.
Случай г]{) = ц{)
5.1 Быстрое вычисление символов (а + Ьа, с + с1а)х
5.2 Применение быстрых вычислений в схеме С2
Литература

1 Введение

Глявя
1.1 Описание основных результатов диссертации
В.М. Сидельников в работе [13] предложил схему открытого распределения ключа на основе некоммутативной группы. Пусть С - некоммутативная группа с ассоциативной эффективно вычислимой операцией *; Сх,Сг коммутативные подгруппы С; с - элемент С, не лежащий в Сх, Сг.
Схема С
А В
Шаг 1. Шаг 1.
Выбирает щ € Сщ г = 1,2; вычис- Выбирает Д € С*, г = 1,2; вычисляет <1д = сц*с* а2] отправляет <1д ляет с1в = Ьх * с* Ь2] отправляет йв абоненту В абоненту А
Шаг 2. Шаг 2.
Получает с1в и вычисляет Получает (1д и вычисляет
К = Ка = а * (1в * а2 К = Кв — Ьх * с1д * Ь2
Помимо общей схемы рассматривались два её частных случая: С1, в которой Сх = Сг, и С2, в которой с = 1. М.А. Черепнёв в работе [16] предложил использовать для аналогичной схемы некоммутативную ассоциативную операцию в кольце целых чисел простого кругового поля. Пусть
4.1 Описание коммутирующих множеств

1. Действительно, если (3j > 2 для некоторого j, ТО В (Z[£p]/(AP))* есть элемент порядка р^. Поэтому для (Z[(p]/(AP))* верно разложение:
(Z[CP]/(AP))* = S0 0 Z/pZ ... 0 Z/pZ = §о 0 Sp, (4.4)
где §o группа порядка р — 1, число слагаемых вида Z/pZ равно р — 1, а через §р обозначена подгруппа, состоящая из 1 и элементов порядка р.
Предложение 4.1.9. §о — %/{р- 1)^-
Доказательство. Пусть до £ Z первообразный корень по модулю р2 и пусть wo = рор (mod р2), wo € Z. Найдем порядок wo в (Z[(p]/(AP))*.
wT1 = Ро(Р-1) = ^о(р2) = 1 (mod Р2)
и следовательно Wq-1 = 1 (mod (Ар)). Поэтому порядок Wo делит р — 1.
Предположим, что порядок wo в (Z[(p]/(AP))* меньше р - 1 и равен s. Тогда Wq — 1 = 0 (mod (Ар)).
Но так как Wq - 1 £ Z, следовательно Wq — 1 = 0 (mod р2). Но это сравнение противоречит тому, что до первообразный корень по модулю р2. Следовательно, порядок wq в (Z[(p]/(AP))* равен в точности р — 1. Предложение доказано.
Таким образом, получили, что
(Z[CP]/(AP))* “ ZКр - 1)Z 0 Z/pZ 0 ... 0 Z/pZ (4.5)
В силу предложения 4.1.7 элементы w* для i = 1,... ,р — 1 имеют порядок р в (Z[(P]/(AP))*, поэтому для доказательства теоремы 4.4 осталось показать, что они образуют мультипликативный базис подгруппы §р. Рассмотрим подгруппу S С (Z[(p]/(AP))*, мультипликативно порождённую wi,... ,Wp_i- Так как порядки W; равны р, то S С §р.
Предложение 4.1
Wiai •... • Wp_i°p“1 = w^1 •... • Wp-i^"1 (mod (Ap)) (4.6)
и 0 < ai, fa < p — 1, то щ — для 1 < i < p — 1.