Об использовании свойства коммутирования символа степенного вычета в схемах открытого распределения ключа тема диссертации и автореферата по ВАК РФ 01.01.06, кандидат физико-математических наук Назаров, Вадим Владиславович

• Назаров, Вадим Владиславович
• кандидат физико-математических наук
• 2006

Оглавление диссертации кандидат физико-математических наук Назаров, Вадим Владиславович

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 Структура группы {Z[Q/(\v))*.

4.1.3 Переход к векторному пространству.

4.1.4 Оценка размерности максимальных тривиальных подпространств формы ф.

4.2 Оценка стойкости схемы.

4.3 Алгоритм вычисления символа норменного вычета.

4.3.1 Логарифмические функции из Z[(p] в Z/pZ.

4.3.2 Вычисление логарифмических функций из Z[£p] в Z/pZ.

4.3.3 Алгоритм вычисления символа норменного вычета

5 Схема на основе символа норменного вычета.

Случай 77() =

5.1 Быстрое вычисление символов (а + ЬХа , с + d\a)x.

5.2 Применение быстрых вычислений в схеме С2.

Введение диссертации (часть автореферата) на тему «Об использовании свойства коммутирования символа степенного вычета в схемах открытого распределения ключа»

1.1 Описание основных результатов диссертации

В.М. Сидельников в работе [13] предложил схему открытого распределения ключа на основе некоммутативной группы. Пусть G - некоммутативная группа с ассоциативной эффективно вычислимой операцией *; Gi,G2 коммутативные подгруппы G; с - элемент G, не лежащий в Gi,G2. Схема С

А В

Шаг 1. Шаг 1.

Выбирает сч G Gj, г = 1,2; вычис- Выбирает bi £ Gi, г = 1,2; вычисляет с1д = а\ * с * а,2", отправляет dа ляет ds = h * с * 62; отправляет de абоненту В абоненту А

Шаг 2. Шаг 2.

Получает и вычисляет Получает ^ и вычисляет

К = Ка = а,\ * ds * а2 К = Кв = Ъ\ * * 62

Помимо общей схемы рассматривались два её частных случая: С1, в которой Gi = G2, и С2, в которой с = 1. М.А. Черепнёв в работе [16] предложил использовать для аналогичной схемы некоммутативную ассоциативную операцию в кольце целых чисел простого кругового поля. Пусть г)(),»0 - мультипликативные функции, такие что rj((p) = fi((p) = 1, ft J - символ степенного вычета тогда р

Ф)\ . х*у=хуШР {г)

В настоящей диссертации проведены исследования схемы при использовании такой операции. Показано, что схема С1 является нестойкой, кроме того доказана теорема, устанавливающая критерий вскрытия схемы С.

Рассмотрен класс некоммутативных ассоциативных операций на основе коммутативной полугруппы (G, •) и двуместной мультипликативной функции F(, ) такой, что F(F(x, y),z) — F(x, F(y, z)) = 1: x * у = x ■ у ■ F(x,y) (ii)

Операция (г) имеет такой вид. При использовании в схеме С произвольной операции вида (гг), получен критерий вскрытия схемы, такой же, как и при использовании операции (г).

В случае совпадения функций г)() и ji() в операции (г) дано описание максимальных коммутирующих подмножеств и на его основе реализован алгоритм атаки на схему. Вычислительная сложность алгоритма атаки эквивалента сложности протокола схемы при использовании известных алгоритмов вычисления символов степенного и норменного вычета для элементов общего вида.

По аналогии с операцией (г) рассмотрена операция вида (гг), использующая символ норменного вычета: х*у = ху(ф),?](у))А (Иг)

Для схемы С на основе операции (Иг) также проведено построение коммутирующих множеств и указан алгоритм атаки. При использовании операции вида (Hi) получены условия на функцию rj() и подгруппы Gj, выполнение которых приводит к экспоненциальному росту количества арифметических операций, необходимых для реализации упомянутого алгоритма атаки, при полиномиальном росте количества операций, необходимых для реализации протокола схемы С.

Построен алгоритм вычисления символа норменного вычета в простых круговых полях, использующий свойства некоторого семейства логарифмических функций из кольца целых чисел простого кругового поля в кольцо вычетов по модулю р.

Список литературы диссертационного исследования кандидат физико-математических наук Назаров, Вадим Владиславович, 2006 год

1. Айерлэнд К., Роузен М. Классическое введение в современную теорию чисел, Москва, Мир, 1987

2. Боревич З.И., Шафаревич И.Р. Теория Чисел, Москва, Наука, Главная редакция физ-мат литературы, 1985.

3. Василенко О.Н., Теоретико-числовые алгоритмы в криптографии, Москва, МЦМНО, 2003.

4. Вейль Г., Алгебраическая Теория Чисел, Москва, УРСС, 2003.

5. Винберг Э.Б. Курс Алгебры, Москва, Факториал-Пресс, 2001.

6. Виноградов И.М. Основы теории чисел, Москва, Ленинград, Государственное издательство технико-теоретической литературы, 1952.

7. Алгебраическая теория чисел, под ред. Касселс Дж., Фрёлих А. Москва, Мир, 1969

8. Черепнёв М.А. Криптографические протоколы, Москва, Центр прикладных исследований при механико-математическом факультете МГУ, 2006

9. Artin Е., Tate J. Class field theory Notes of a Seminar at Princeton, 1951/52. Harvard University, Mathematics Department, 1961.

10. Cohen H. A Course in Computational Algebraic Number Theory, 3 corr. print, Springer, Berlin-Heidelberg-New York, 1996И. LemmermeyerF. Reciprocity Laws From Euler to Eisenstein. Berlin, Springer, 2000

11. Washington L.C. Introduction to Cyclotomic Fields, Springer, New York-Heidelberg-Berlin, 1982

12. Сидельников B.M., Черепнёв M.A., Ященко В.В., Системы открытого распределения ключа на основе некоммутативных полугрупп. Доклады РАН, 332 (1993), Вып. 5, стр. 566-567.

13. Сидельников В.М. Системы распределения ключей на основе экспоненциального представления линейной группы GLn(Fp).

14. Черепнёв М.А. Схемы открытого распределения ключа на основе некоммутативной операции. Тезисы докладов XIII Международной конференции "Проблемы теоретической кибернетики". Казань 27-31 мая 2002 г. стр. 190

15. Черепнёв М.А. Схемы открытого распределения ключа на основе некоммутативной группы. Дискретная математика Т. 15 (2003), Вып. 2, стр. 47-51

16. Назаров В.В. Об использовании символа степенного вычета в схемах открытого распределения ключа. Вестник Московского Университета, сер.1, Математика, Механика. №3 (2005), стр. 9-13.

17. Назаров В.В. Схемы открытого распределения ключа на основе некоммутативной операции. Дискретная математика Т. 18 (2006), Вып. 4, стр. 149-156

18. Назаров В.В. О некоторых вычислительных свойствах символа норменного вычета в простых круговых полях. Депонировано в ВИНИТИ 31.10.2006, № 1289-В2006, 24 стр

19. AdelmanL.M., PomeranceC.,RumelyR.S. On distinguishing prime numbers from composite numbers. Annals of Mathematics, 117 (1983), pp. 173-206

20. Buchmann J.A., Williams H.C. A key-exchange system based on imaginary quadratic fields. Journ. Cryptology, 1 (1988), pp. 107-118

21. Daberkow M. On computations in Kummer extensions Journ. Symbolic Computations 31 (2001), pp. 113-131

22. Diffie W., Hellman M.E., New directions in criptography, IEEE Transactions on Information Theory, 22 (1976), pp. 644-654

23. Helou C. Power Reciprocity for Binomial Cyclotomic Integers. Journal of Number Theory, 71 (1998), pp. 245-256

24. Horowits J. Applications of Cayley graphs, bilinearity and higher-order residues to cryptology Staford Univercity, PhD. Thesis, 2004

25. Jacobson M.J., Jr., Scheidler R., Williams H.C. The efficiency and security of a Real Quadratic Field Based Key Exchange Protocol. In Public-Key Cryptography and Computational Number Theory (Warsaw, Poland), de Gruyter, 2001, pp. 89-112

26. Koblits N., Elliptic curve cryptosystems, Math. Comp, 48 (1987), pp. 203209

27. McCurley K.S., A key distribution scheme based on factoring, Journ. Cryptology, 1 (1988), pp. 95-105

28. Miller V., Use of elliptic curves in cryptography. In Advances in Cryptology -ProceedingsofCRYPTO'85, LNCS, 218 (1986), Springer (New York), pp. 417-426

29. Odoni R.W.K., Varadharajan V., Saunders P.W., Public-key distribution in matrix rings, Electr. Letters, 20 (1984), pp. 386-387

30. Scheidler R., Buchmann J.A., Williams H.C. A key-exchange protocol using real quadratic fields. Journ. Cryptology, 7 (1994), pp. 171-199

31. Squirell D. Computing power residue symbol. Reed College, Undergraduate Thesis, 1997