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

Большинство криптоаналитических методов могут быть модифицированы благодаря параллельным алгоритмам. Одним из них является метод Шенкса решения проблемы дискретного логарифма. Цель работы – построить алгоритм, позволяющий параллельно находить все значения из таблиц малого шага и большого шага, а также сделать этот поиск более направленным и упорядочить все значения элементов таблиц. Это позволит применить метод блочного поиска, разбиение на упорядоченные подблоки, ускорит применение метода индексации значений (или хэш от значений). Методом решения поставленной задачи является параллельная оптимизация и блочная параллельная поразрядная сортировка, которые стали возможными благодаря быстрым пересылкам в дуплексном режиме и математи¬ческим моделям алгоритма. В работе предложен метод параллельного вычисления векторов, координатами ко¬то¬рых являются значения таблички 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 с.

Полнотекстовый документSize
2013-5-7.pdf264.81 KB