29.5 (7.2.5) Порівняння складності дискретного логарифмування

У роботах [4, 5, 11–13, 422–424, 426–428] запропоновано значне число моделей оцінки складності дискретного логарифмування. Основним етапом криптоаналізу є дискретне логарифмування. У табл. 9.7 наведені аналітичні вирази, що можуть бути застосовані для оцінки складності відповідних методів дискретного логарифмування. Їх аналіз підтверджує висновок про те, що методи ρ-Полларда, Поліга-Геллмана мають експоненційну складність дискретного логарифмування. Методи Адлемана, Купершмідта й решета числового поля мають субекспоненційну складність дискретного логарифмування. Причому в [426] та [427] наведено аналітичні вирази, що відрізняються. Скоріше за все вони враховують особливості дискретного логарифмування і є певними оцінками. Детальний розгляд цього факту виходить за межі можливостей цієї монографії. Для більш детального освоєння методу дискретного логарифмування в скінченному полі Галуа можна скористатися роботою [426] і роботами, на які є посилання в ній. Загальним же висновком є те, що найбільш простим (швидким) методом дискретного логарифмування є решето числового поля.

Таблиця 9.7

Складність дискретного логарифмування

Назва методу	Складність методу
ρ-Полларда метод	О(P1/2)
Метод Поліга-Геллмана при P-1 =	О( )
Метод Адлемана ( , v – константи), 0≤v<1	О(exp ( Ln(ln (P)))v))
Метод Купершмідта ( =1,56, v=1/2)	О(exp ( Ln(ln (P)))v))
Метод решета числового поля [426]	О(exp ( ln )
Метод решета числового поля [427]	exp ((64/9)1/3 (ln q)1/3(ln ln q)2/3).

Серед суб експоненційних за складністю методів необхідно відмітити таке.

Метод Адлемана з’явився ще в 1979 році. Це був перший метод, що мав субекспоненційну складність дискретного логарифмування. Для нього v =1/2, а с 2.

Метод Купершмідта (Don Coppersmith), або COS метод, був запропонований декількома математиками [426]. Для цього методу v =1/2, а с=1. З його застосуванням у 1997 році було практично розв’язано задачу дискретного логарифмування з розміром модуля Р ⁸⁵. Також вважається, що метод Купершмідта є більш швидким за решето числового поля при Р ⁹⁰.

Решето числового поля вперше було запропоноване Д. Гордоном у 1993 році. Для нього було обгрунтувано оцінку вигляду

О(exp ( ln ), (9.58)

але воно було не практичним, тому в подальшому було декілька разів удосконалено. Також було показано, що при Р ¹⁰⁰ решето числового поля є більш швидким (менш складним), ніж решето Гордона.

Згідно даних [426], на сьогодні максимальним дискретним логарифмом, що розв’язаний практично, є дискретний логарифм розміром Р ⁹⁰⁷ (273 десяткових цифр). Відповідні доступні відомості щодо сучасних досягнень дискретного логарифмування в скінченному полі Галуа наведені в табл. 9.7.

Таблиця 9.8

Досягнення криптоаналізу (дискретного логарифмування) DSA

Рік	Довжина ключа, бітів	Час, MIPS-років	Пам’ять ОЗУ/HDD, Гб
DSA
2001	607	20000	0,256 /5
2011	907	2,775*108	1/35