Разрешимость задачи дискретного логарифмирования в кольцах тема диссертации и автореферата по ВАК РФ 01.01.06, кандидат физико-математических наук Маркелова, Александра Викторовна

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

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

Обозначения

1 Введение

1.1 Разрешимость задачи дискретного логарифмирования

1.2 Результаты диссертации.

1.2.1 Разрешимость в кольце вычетов по составному модулю

1.2.2 Разрешимость в факторкольце многочленов над конечным полем.

1.2.3 О вычислении символов степенного вычета.

1.3 Благодарности.

2 Разрешимость показательного сравнения в кольце вычетов по составному модулю

2.1 Постановка задачи, определения, вспомогательные теоремы

2.2 Полиномиальное сведение к случаю М - pq.

2.3 Разрешимость сравнения ах = b (mod pq).

2.4 Общий критерий разрешимости

3 Подъём решений показательного сравнения в факторкольце многочленов. Подъём решений показательного сравнения в цепных кольцах

3.1 Постановка задачи.

3.2 Подъём решений по степени неприводимого многочлена.

3.3 Подъём решений в цепных кольцах

3.4 Оптимизация алгоритма подъёма решений и проверки разрешимости

4 Разрешимость показательного сравнения по модулю произвольного многочлена над полем

4.1 Полиномиальное сведение к случаю F(x) = fi(x)f2(x).

4.2 Использование обобщённого символа Якоби (квадратичного характера в кольце многочленов) для проверки разрешимости в частных случаях.

4.3 Связь задачи дискретного логарифмирования в поле с вычислением символов степенного вычета.

4.4 Разрешимость сравнения an(x) = b(x) (mod р, fi(x)f2(x))

4.5 Общий критерий разрешимости

5 О вычислении символов степенного вычета специального вида

5.1 Общие теоремы.

5.2 Способ выбора идеалов в частных случаях.

Введение диссертации (часть автореферата) на тему «Разрешимость задачи дискретного логарифмирования в кольцах»

1.1 Разрешимость задачи дискретного логарифмирования

Задача дискретного логарифмирования является одной из ключевых задач современной теории чисел. В [1] (п.3.6) приводится следующая классификация видов этой задачи.

Задача дискретного логарифмирования (DLP): имея простое число р, первообразный корень а е (Z/pZ)* и некоторый элемент /9 G (Z/pZ)*, найти целое число х, 0 < х < р — 2, для которого ах = /3 (mod р).

Обобщённая задача дискретного логарифмирования (GDLP'): имея конечную мультипликативную циклическую группу G порядка п, порождающий элемент этой группы а и некоторый элемент этой группы /3, найти целое число х, 0 < х < п — 1, для которого ах = ¡3.

Обобщение GDLP: в произвольной конечной мультипликативной группе G для некоторых элементов а,/3 е G найти целое число х, для которого ах = ¡3, если такой х существует.

В последнем случае не требуется, чтобы группа G была циклической, а элемент а был образующим. Такая постановка задачи в общем случае может оказаться сложнее, чем GDLP. При этом если группа G является циклической и известен порядок п элемента а, то легко проверить, существует ли требуемое решение х: в этом случае решение сравнения ах = /3 существует тогда и только тогда, когда ¡Зп = 1 ([1], 3.54).

Хочется отметить, что многие авторы не следуют подобной классификации и обобщение СБЬР называют просто задачей дискретного логарифмирования ([2], [3], [4] и пр.). Поскольку в дальнейшем мы будем рассматривать именно обобщение СБЬР, то для простоты формулировок, мы тоже будем пользоваться термином "дискретное логарифмирование" именно в таком, наиболее общем, смысле.

В общем случае не известно полиномиального алгоритма решения задачи дискретного логарифмирования. На сложности этой задачи в простом поле базируется множество криптоалгоритмов, таких как алгоритм выработки общего ключа Диффи-Хеллмана ([5]), алгоритм выработки электронной цифровой подписи Эль-Гамаля ([6]), алгоритм выработки цифровой подписи ББА ([7]), предыдущий российский стандарт электронной цифровой подписи ГОСТ Р 34.10-94. На данный момент эти алгоритмы считаются устаревшими, им на смену пришли аналоги, вычисляемые в группе точек эллиптической кривой: ЕСБН, ЕСББА ([8]), ГОСТ Р 34.10-2001 ([9]).

Данный переход стал следствием успешного применения субэкспоненциальных алгоритмов для дискретного логарифмирования по модулю р ([Ю], [11] и т.д.) при том, что для эллиптической кривой общего вида не существует хоть сколько-то эффективных алгоритмов дискретного логарифмирования.

Тем не менее, несмотря на значительные достижения и новые разработки, для дискретного логарифмирования в конечных полях по-прежнему не существует полиномиального алгоритма, и данный вопрос продолжает волновать ведущих математиков всего мира.

В нашей работе мы будем рассматривать задачу дискретного логарифмирования в конечных кольцах, которые являются не менее важным криптографическим объектом, чем конечные поля. Вопрос дискретного логарифмирования в конечных кольцах зачастую полиномиально сводится к дискретному логарифмированию в конечных полях. Но в случае, если мультипликативная группа кольца не является циклической, возникает дополнительный вопрос: вопрос о существовании решения показательного сравнения.

Хочется подчеркнуть, что в данном случае вопрос не сводится к дискретному логарифмированию (или к проверке разрешимости) в поле. Нашей задаче будет научиться проверять разрешимость заданного сравнения, не решая его. Мы хотим получить критерии разрешимости, проверка которых была бы существенно проще решения задачи дискретного логарифмирования.

В [4] приведён алгоритм для проверки разрешимости в произвольной абе-левой группе. Данный алгоритм для конечной мультипликативной абелевой группы 6? и элементов а,/3 € С за 0(л/|(о;)|) умножений проверяет, принадлежит ли элемент /3 циклической группе (а), порождённой элементом а, и в случае положительного ответа находит /3. Для проверки используется таблица, состоящая из 0{л/\[а)\) пар элементов.

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

Этой темой ранее занимался О.Н.Василенко. Он рассматривал вопрос о разрешимости показательного сравнения в кольце вычетов по составному модулю ([12]) и в факторкольце многочленов над конечным полем ([13]). Им были получены некоторые критерии разрешимости для частных случаев. В нашей работе мы продолжим исследования О.Н.Василенко и обобщим критерии, полученные им, на случай произвольных параметров задачи.

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

Теорема В1 ([12]; [2], т.5.28). Пусть М = р\ • . • Рк, где все рг

Уг различные нечётные простые ир{ — 1 = 2 [] р^3, гдерц - нечётные простые, 1 различные для всех г,у. Предположим, что ог6.Рга = р^ — 1 для г = 1,., t и огс1рга = для г — £ + 1,., к. Сравнение

Данная теорема позволяет проверять разрешимость показательного сравнения по нечётному составному модулю, не содержащему квадратов в ах == Ъ (mod М) разрешимо тогда и только тогда, когда разложении, при условии, что все простые делители модуля имею специальный вид, а порядок а по модулям делителей строго равен одному из двух значений.

Далее, интерес представляет вопрос о разрешимости показательного сравнения в факторкольце многочленов над полем. Cohen Н., Dyaz у Dyaz F., Olyver М. в 1998 году ([14]), затем Hess F., Pauli S., Pohst M.E. в 2003 году ([15]) и позднее Поповян И.А. в 2006 году ([16]) рассматривали задачу подъёма решений показательного сравнения в кольце целых алгебраических чисел. Было доказано, что решение сравнения ax = ß (mod 7TU) для некоторых а, ß 6 Zjk и простого идеала 7г полиномиально сводится к нахождению решения сравнения ах = ß (mod 7г).

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

Частным случаем рассматриваемой задачи является сравнение вида an{x) = b{x) (mod р'у, f{x)), где многочлен f(x) со старшим коэффициентом 1 неприводим по модулю простого р.

При этом решение задачи сводится к нахождению решения сравнения ап(х) = Ъ{х) (mod р, f{x)).

Однако, решение последнего сравнения можно "поднимать" не только по степеням р, но и по степеням f(x). Этот вопрос рассматривался О.Н. Василенко, и им были получены следующие результаты.

Теорема В2 ([13]; [2], т.5.37). Пусть р/2 <v <р, orda(x) = ordb(:c) = р и а(х) ~ 1 + aP{x)f(x) + . + а^~1\х)Г-\х) (mod р, Г(х)),

Ь(х) = 1 + b^\x)f(x) + . + Ь^-1\х)Г-\х) (mod р, f(x)), где deg а®(х) < deg f{x), deg b®(x) < deg f(x). Если a^(x) ^0« сравнение an{x) = b(x) (mod p, f{x)) разрешимо относительно переменной n E N, mo n={bw(x)a^){x)-1)p (mod p, f(x)).

Теорема B3 ([13]; [2], т.5.39). Пусть p/2 < v < p, d = deg/{x), orda(a;) = p8\, ordb(x) = p^, \pd — l и a{xfd-1 = 1 + aP\x)f{x) + . + f^"1 (x) (mod p, fu(x)), bixf-1 = 1 + b^{x)f(x) + . + Ь^~1\х)Г~1(х) (mod p, fv(x)), где dega^(x) < d, degb^\x) < d. Пусть ail\x) 0.

1) Предположим, что найдётся € Ъ, для которого выполнено сравнение щ = (b^(х)а^(ж)1)р (mod р, f{x)). Если a{x)pd~l)no ~ b(x)pd-1 (mod р, fd(x)), то ап(х) = b{x) (mod р, fv{x)) разрешимо.

2) Если класс вычетов (ftW(ж)а(1)(ж)1)р (mod f(x)) не содержит элемента щ е Z или содержит, но (a{x)pd~l)n° ф b{x)pd~~l (mod р, fv{x)), то ап{х) = Ъ{х) (mod р, fv{x)) неразрешимо. •

Данные теоремы накладывают существенные ограничения на значение у и на порядки элементов а{х) и Ъ{х), что не позволяет их использовать в общем случае.

Заключение диссертации по теме «Математическая логика, алгебра и теория чисел», Маркелова, Александра Викторовна

Заключение

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

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

Отдельно мы рассмотрели случай факторкольца по степени неприводимого многочлена. Была решена задача о подъёме решений и приведён конструктивный полиномиальный алгоритм для такого подъёма. Т.е. вопрос о дискретном логарифмировании в факторкольце многочленов был полиномиально сведён к дискретному логарифмированию в поле. Данный результат обобщает известные результаты О.Н.Василенко, верные для частных случаев.

В том числе были рассмотрены цепные кольца, заданные в канонической форме. Для них также получен критерий разрешимости и решена задача подъёма решений. Было показано, что в некоторых случаях конструктивный изоморфизм в цепные кольца помогает оптимизировать проверку разрешимости показательного сравнения.

Как оказалось, в общем случае вопрос о существовании решения показательного сравнения без его непосредственного решения является достаточно сложным и не всегда возможно построить полиномиальный алгоритм для такой проверки.

Достаточно легко выполняется редукция задачи. А именно, доказано, что в случае кольца вычетов нам необходимо и достаточно научиться проверять разрешимость сравнения по модулю произведения двух нечётных простых чисел, а в случае факторкольца многочленов - разрешимость сравнения по модулю произведения двух различных неприводимых над рассматриваемым полем многочленов.

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

Нашей гипотезой является, что вопрос проверки разрешимости эквивалентен вычислению символов степенного вычета для заданных делителей. Т.е. мы предполагаем, что нет принципиально более простых алгоритмов проверки существования решения, чем вычисление упомянутых символов. Однако на данный момент вопрос обратного сведения (т.е. сведения вычисления символов к проверке разрешимости) остаётся открытым.

Вопрос о проверке разрешимости полиномиально свёлся к вопросу о вычислении символов степенного вычета. В связи с этим последняя глава данной работы была посвящена вопросам вычисления символов степенного вычета. Задача вычисления символов степенного вычета в общем случае является достаточно сложной. Однако в некоторых частных случаях её можно существенно упростить. А именно, для символов г^-степенного вычета, где гк\\р — 1, был приведён алгоритм полиномиального сведения к вычислению символов степенного вычета г-ой степени.

Существующие алгоритмы вычисления символов г-степенного вычета (например, для г — 2,3, 5, 7) в совокупности с доказанной теоремой о "подъёме" символов позволяют применять сформулированные критерии разрешимости для достаточно широкого класса задач. Но по-прежнему остаётся широкий набор параметров задачи, при которых сформулированные критерии проверки разрешимости не являются конструктивными.

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

• вычисление символов г-степенного вычета для некоторых простых г;

• получение явного вида простых делителей идеала (р), для которых можно явно выписать значение ( ) в случае т\р — 1; я / ш

• исследование вопроса эквивалентности вычисления символов степенного вычета и проверки разрешимости задачи дискретного логарифмирования.

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

1. Menezes A., Van Oorschot P.C., Vanstone S.A. Handbook of applied cryptography. CRC Press, 1997

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

3. Odlyzko A.M. Discrete logarithms in finite fields and their cryptographic significance. Advances in Cryptology-Proceedings of EUROCRYPT 84 (LNCS 209% 224-314, 1985.

4. Buchmann J., Jacobson M.J., Teske E. On some computational problems in finite abelian groups. Mathematics of Computation, 1997, V. 66 (220), p. 1663-1687.

5. Diffie W., Hellman M. E. New Directions in Cryptography. IEEE Transactions on Information Theory, Vol. IT-22, No. 6, November 1976, pp. 644-654.

6. ElGamal T. A public key cryptosystem and a signature scheme based on discrete logarithms. IEEE Transactions on Information Theory, Vol. IT-31, No. 4, July 1985, pp. 469-472.

7. FIPS 186 Digital signature standard, Federal Information Processing Standards Publication 186, U.S. Department of Commerce/ N.I.S.T., National Technical Information Service, Springfield, Virginia, 1994.

8. Jonson D., Menezes A. The elliptic curve digital signature alghoritm. Technical report CORR 99-31, Dept. of C&O, University of Waterloo, Canada, 1999.

9. ГОСТ Р 34.10-2001. Государственный стандарт Российской Федерации. Информационная технология. Криптографическая защита информации. Процессы формирования и проверки электронной цифровой подписи.

10. Gordon D.M. Discrete logarithms in GF(p) using the number field sieve. SI AM Journal on Discrete Mathematics, 6 (1993), 124-138.

11. Schirokauer O. Discrete logarithms and local units. Philosophical Transactions of the Royal Society of London A, 345 (1993), 409- 423.

12. Василенко O.H. О разрешимости задачи дискретного логарифмирования в кольцах вычетов. Фунд. и прикл. матем, 2002. 8, № 3. 647-653.

13. Василенко О.Н. О дискретном логарифмировании в некоторых группах. Вестник МГУ, сер.1. Матем. Механ., 2000, №5, с. 53-55.

14. Cohen Н., Diaz у Diaz F., Oliver М. Computing ray class groups, conductors and discriminants. Math. Сотр., Vol. 67:222, 1998, pp. 773-795.

15. Hess F., Pauli S. , Pohst M.E. Computing the multiplicative group of residue class rings. Math. Сотр., Vol. 72:243, 2003, pp. 1531-1548.

16. Поповян И.А. Подъём решений показательного сравнения. Математические заметки, 2006, 80:1, с.76-86

17. Riesel Н. Some soluble cases of the discrete logarithm problem. BIT, v28, no4, 1988.

18. Dickson L.E. History of the theory of numbers. V I. Divisibility and primality. New York, 1952.

19. Нестеренко Ю.В., Частные Ферма и р-адические логарифмы. Труды по дискретной математике, т. 5, М. "Физматлит", 2002, с. 173-188.

20. Сидельников В.М. Частные Ферма и логарифмирование в мультипликативной группе кольца вычетов по примарному модулю. Математические вопросы кибернетики, 1999. 8. 55-62.

21. Черепнёв М.А. О некотором свойстве дискретного логарифма. Тез.докл. XII межд. конф. "Проблемы теоретической кибернетики", Н. Новгород, 1999.

22. Artin Е., Tate J. Class Field Theory. 1968, W.A.Benjamin, Inc.

23. Ван дер Варден Б.JI. Алгебра. Наука, Москва, 1976.

24. Bach Е., Shallit J. Algorithmic number theory. V. 1. MIT Press, Massachusetts, 1996.

25. Scheidler R. Applications of Algebraic Number Theory to Cryptography. PhD Dissertation, University of Manitoba (Canada), 1993. (http://math.ucalgary.ca/ rscheidl/Papers/my-thesis.pdf)

26. Caranay P.C., Scheidler R. An efficient seventh power residue symbol algorithm. International Journal of Number Theory, 2009 (http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.158.2501)

27. Adleman L.M., Pomerance C., Rumely R.S. On Distinguishing Prime Numbers from Composite Number. Ann. Math., 117, 173-206, 1983.

28. Виноградов И.М. Основы теории чисел. М.: Наука, 1972.

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

30. Pohst М. Computational algebraic number theory. Basel, Boston, Berlin: Birkhauser, 1993.

31. Алгебраическая теория чисел. Под редакцией Касселс Дж., Фрёлих А. М.: Мир, 1969

32. Cohen Н. A course in computational algebraic number theory. SpringerVerlag, Berlin, 1993.

33. Елизаров В.П. Конечные кольца. Гелиос АРВ, Москва, 2006.

34. Галочкин А.И., Нестеренко Ю.В., Шидловский А.Б. Введение в теорию чисел. М.: Изд-во Моск. Ун-та, 1984

35. Публикации автора по теме диссертации

36. Маркелова A.B. 0 разрешимости задачи дискретного логарифмирования. Вестник МГУ, сер.1. Матем. Механ., 2008, №6, с. 6-9.

37. Маркелова A.B. Дискретное логарифмирование в произвольных фактор-кольцах многочленов от одной переменной над конечным полем. Дискретная математика, 2010г., том 22, выпуск 2, стр. 120-132.

38. Маркелова A.B. О разрешимости задачи дискретного логарифмирования в кольце вычетов по составному модулю. Математика и безопасность информационных технологий. Материалы конференции в МГУ 28-29 октября 2004 г. С.185-191. М.: МЦМНО, 2005