Модифікований алгоритм Шенкса з упорядкованими блоками

Більшість методів криптоаналізу можуть бути модифіковані завдяки застосуванню паралельних алгоритмів. Одним із них є метод Шенкса розв’язання проблеми дискретного логарифму. Мета роботи – побудувати алгоритм, що паралельно знахо-дить всі значення з таблиць малого кроку і великого кроку, а також зробити цей пошук більш спрямованим і впорядкованим для всіх значень елементів таблиць. Це дасть можливість застосування методу блокового пошуку, розбиття на впорядковані підблоки, пришвидшить застосування методу індексації значень (чи хеш від значень). Методом розв’язку поставленої задачі є паралельна оптимізація і блочне паралельне порозрядне сортування, які стали можливими завдяки швидким пересилкам в дуплексному режимі й математичним моделям алгоритму. В роботі запропоновано метод паралельного обчислення векторів, координатами яких є значення таблички BS. Також знайдено оптимальну довжину малого кроку і, як наслідок, великого кроку для методу, що не використовує повного порядку на множині значень елементів такого малого кроку. Запропоновано метод покращення алгоритму Шенкса.

Рік видання: 
2013
Номер: 
5
УДК: 
688.321
С. 46–52., укр., Бібліогр.: 12 назв.
Література: 

1. Василенко О.Н. Теоретико-числовые алгоритмы в криптографии. — М.: МЦНМО, 2003. — 328 с.
2. L. Adleman, “A subexponential algorithm for the discrete logarithm problem with applications to cryptography”, in Proc. 20th Ann. IEEE Symp. Found. Comput. Sci., 1979, pp. 55—60.
3. А. Stein and Teske E., “Optimized baby step-giant step methods”, J. Ramanujan Math. Soc., vol. 20, no. 1, 2005, pp. 1—32.
4. J.S. Coron et al., “A new baby — step gigant — step algorithm and some applications to cryptanalysis”, in Proc. 7th Int. Conf. Cryptographic hardware and embedded system. Springer-Verlag, 2005, pp. 47—60.
5. Основи дискретної математики / Ю.В. Капітонова, С.Л. Кривий, А.А. Летичевський та ін. — К.: Наук. думка, 2002. — 578 с.
6. Костюкова Н.И. Графы и их применение. Комбинаторные алгоритмы для программистов. — М.: Изд-во ИНТУИТ.ру, 2007. — С. 231.
7. Handbook of Graph theory (Discrete Mathematics and its application), J.L. Gross and J. Yellen, Eds. Florida: CRS Press, 2004, 1192 p.
8. Цегелик Г.Г. Методы автоматической обработки информации. — Львов: Вища школа, 1981. — С. 132.
9. Задирака В.К. Олексюк О.А. Компьютерная арифметика многоразрядных чисел. — Тернополь: Підручники і посібники, 2003. — С. 247.
10. D.R. Stinson, “Some baby-step giant-step algorithm for low hamming weight discrete logarithm problem”, Math. Comp., vol. 71, pp. 379—391, 2002.
11. M.J. Wiener, “The Full Cost of Cryptanalytic Attacks”, J. Crypt., vol. 17, no. 2, pp. 105—124, 2004.
12. Бессалов А.В., Телиженко А.Б. Криптосистемы на эллиптических кривых. — К.: Політехніка, 2004. — 224 с.

Текст статтіРозмір
2013-5-7.pdf264.81 КБ