Подъем решений показательных уравнений в конечных кольцах

В современной криптографии важную роль играет понятие односторонней функции, то есть такой функции, которая вычислима за полиномиальное от длины входа время, но задача её обращения неполиномиальна. Согласно У. Диффи ([1]) в середине 70-х годов Дж. Гилл предложил использовать в качестве одностороннего отображения возведение в степень по модулю простого числа. Позже оно было обобщено до возведения в степень в произвольной конечной циклической группе, т. е. если (G, х) -циклическая группа, G =<д>, то.

Задача обращения этого отображения называется (обобщенной) задачей дискретного логарифмирования (GDLP), а при G = (Z/(p))*, где рпростое рациональное число, эта задача называется просто задачей дискретного логарифмирования (DLP). На ее предположительной неполино-миальноети основана стойкость множества асимметричных криптосхем, таких как, например, схема распределения ключей Диффи-Хэллмэна [1] или схема электронной подписи Эль-Гамаля [2] и ее варианты, DS, А [3] или ГОСТ-34.10−94.

История алгоритмов для решения DLP началась, конечно, с алгоритмов, имеющих в общем случае экспоненциальную сложность, таких как «Baby-Step, Giant-Step» Шенкса [4], ри А-методы Полларда [5], алгоритм Полига-Хэллмэна [6] и др. Одним из первых субэкспоненциальный алгоритм для БЬР предложил Адлеман в [7], а в [8] было предложено уже три таких алгоритма. Позже для решения БЬР был адаптирован ([9]) и улучшен ([10]) алгоритм решета числового поля, используемый в то время для решения задачи разложения составного числа на множители. Упомянутые алгоритмы имели субэкспоненциальную оценку сложности, полученную лишь эвристически, пока в работе [11] она не была строго доказана. На сегодняшний день, все соврменные алгоритмы для решения задачи БЬР являются субэкспоненциальными.

Параллельно развивались алгоритмы для решения задачи СБЬР. Так в работе [12] был предложен субэкспоненциальный алгоритм для решения СБЬР в С = ¥-рп. Этот алгоритм имел несколько улучшений, пока в частном случае С = F2m не был улучшен так сильно ([13],[14]), что стал на сегодняшний день алгоритмом, имеющим наилучшую оценку сложности из всех известных алгоритмов дискретного логарифмирования. В качестве С также рассматривалась группа точек на эллиптической кривой (на сегодня одно из перспективнейших направлений), группа классов идеалов конечного расширения и др.

Естественным обобщением БЬР является СЭЬР для С = (Ъ/{т))*, где т е Ъ — составное. Задача полиномиального сведения ОБЬР в (Z/mZ)+ к БЬР в группах (Ъ/р^Ъ)*, соответствующих всем простым делителям Рг числа ш, решена. Решение состоит в применении китайской теоремы об остатках для сведения задачи в (Ъ/тЪ)* к задаче в {Ъ/ркЪ)*, рк\т, и так называемого подъёма решения.

1.1 Подъём решения.

1. W. Diffie and M. E. Hellman New Directions in Cryptography, 1. EE Transactions on Information Theory, Vol. IT-22, № 6, November 1976, pp. 644−654.

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

3. 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.

4. D. Shanks Class number, a theory of factorization, and genera, Proc. Symp. Pure Math. 20 (1971), pp. 415−440.

5. J.M. Pollard Monte Carlo methods for index computation (mod p), Math. Comp. 32(1978), № 143, pp. 918−924.

6. S.C. Pohlig, M.E. Hellman An improved algorithm for computing logarithms over GF (p) and its cryptographic significance, IEEE Transactions on Information Theory, 24 (1978), pp. 106−110.

7. L.M. Adleman, A subexponential algorithm for the discrete logarithm problem with applications to cryptography, Proceedings of the IEEE 20th Annual Symposium on Foundations of Computer Science (1979), pp. 55−60.

8. D. Coppersmith, A.M. Odlyzko, R. Schroeppel, Discrete logarithms in GF (p), Algorithmica, 1 (1986), pp. 1−15/.

9. C. Pomerance Fast, rigorous factorization and discrete logarithm algorithms, Discrete Algorithms and Complexity, Academic Press (1987), pp. 119−143.

10. M.E. Hellman, J.M. Reyneri Fast computation of discrete logarithms in GF (q), Advances in CryptologyProceedings of Crypto 82 (1983), pp. 3−13.

11. D. Coppersmith Fast evaluation of logarithms in fields of characteristic two, IEEE Transactions on Information Theory, 30 (1984), pp. 587−594.

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

13. H. Riesel Some soluble cases of the discrete logarithm problem. BIT, 28 (1988), № 4.

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

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

16. Боревич 3. И., Шафаревич И. Р. Теория чисел. М. «Наука», 1964.

17. Nakagoshi N. The structure of the multiplicative group of residue classes modulo Nagoya Math. J., Vol. 73 (1979), pp. 41−60.

18. Cohen H., Diaz у Diaz F., Oliver M. Computing ray class groups, conductors and discriminants. Math. Сотр., Vol. 67 (1998), № 222, pp. 773−795.

19. Cohen Н., Advanced Topics in Computational Number Theory. GTM 193, Springer-NY, 1999.

20. Hess F., Pauli S., Pohst M. E. Computing the multiplicative group of residue class rings. Math. Сотр., Vol. 72 (2003), № 243, pp. 1531−1548.

21. Поповян И. А. Подъём решения показательного сравнения. Матем. заметки, т. 80 (2006), № 1, сс. 76−86.

22. Поповян И. А. Оптимальные логарифмические функции для подъёма решения показательного сравнения. Диск, матем., т. 19 (2007), № 2, сс. 53−66.

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

24. Sauerberg J., Cohen L. S. D. Fermat Quotients over Function Fields. Finite Fiealds and Theier Applications, Vol. 3 (1997), № 4, pp. 275−286.

25. Satoh K., Araki K. Fermat quotients and the polynomial time discrete log alogorithm for anomalous elliptic curve. Commentarii Math, Univ, Sancti Pauli, Vol.47 (1998), № 1, pp. 81−92.

26. Kunihiro N., Koyama K. Two discrete log algorithms for super-anomalous elliptic curves and their applications. IEICE Trans. Fundamentals, Vol. E83-A (2000), № 1.

27. Cepp Ж. П. Курс арифметики. M. «Мир», 1972.

28. Hasse Н. Zahlentheorie. Akademie-Verlag, Berlin, 2 Aufl., 1963.

29. Cohen HA Course In Computational Algebraic Number Theory. GTM, Springer-NY, 1993.

30. Виноградов И. M. Основы теории чисел. М. «Гос. Изд. Тех.-Теор. Литературы», 1953.

31. Artin Е., Tate J. Class Field Theory. NY, Amsterdam, Benjamin, 1967.

32. Pohst М. Е. Computational Algebraic Number Theory. Birkhauser, 1993.

33. Hafner J. L., McCurley K. S. Asymptotically fast triangularization of matrices over rings., SIAM J. Comput. 20 (1991), pp. 1068−1083.

34. Ахо А., Хопкрофт Дж., Ульман Дж. Построение и анализ вычислительных алгоритмов. М., &bdquo-Мир", 1979.