Метод Полига — Хеллмана

Метод Полига — Хеллмана (также известный как алгоритм Полига — Хеллмана или алгоритм Силвера — Полига — Хеллмана) — это алгоритм дискретного логарифмирования в конечной циклической группе, эффективность которого зависит от факторизации порядка группы. Метод позволяет вычислить дискретный логарифм за время, пропорциональное квадратному корню из наибольшего простого делителя порядка группы, что делает его особенно эффективным, когда порядок группы является гладким числом (то есть состоит из малых простых множителей). Алгоритм был независимо разработан Стивеном Полигом и Мартином Хеллманом в 1978 году, а также ранее предложен Роландом Силвером.

История

Метод был впервые опубликован в 1978 году в статье Стивена Полига и Мартина Хеллмана «An improved algorithm for computing logarithms over GF(p) and its cryptographic significance» (IEEE Transactions on Information Theory). Однако, как отмечается в литературе, аналогичная идея была предложена Роландом Силвером ещё в 1970-х годах, но не была опубликована в открытой печати. Алгоритм стал важным вкладом в криптографию, так как он показал, что безопасность криптосистем, основанных на задаче дискретного логарифмирования (например, протокол Диффи — Хеллмана), напрямую зависит от выбора группы с большим простым делителем порядка. Если порядок группы имеет малые простые множители, то дискретный логарифм может быть вычислен относительно быстро, что делает такие группы уязвимыми.

Математическая основа

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

Пусть дана конечная циклическая группа \(G\) порядка \(n\) с образующим элементом \(g\). Для заданного элемента \(h \in G\) требуется найти целое число \(x\) (дискретный логарифм) такое, что:

\[ g^x = h \]

Решение \(x\) определено по модулю \(n\).

Идея метода

Метод Полига — Хеллмана основан на разложении порядка группы \(n\) на простые множители:

\[ n = \prod_{i=1}^{k} p_i^{e_i} \]

где \(p_i\) — различные простые числа, а \(e_i\) — их показатели. Вместо того чтобы искать \(x\) непосредственно, алгоритм находит \(x\) по модулю каждого \(p_i^{e_i}\) с помощью китайской теоремы об остатках, а затем восстанавливает полное значение \(x\).

Алгоритм

1. Факторизация порядка \(n\). Находятся все простые делители \(p_i\) и их степени \(e_i\).

1. Для каждого простого делителя \(p_i\):

• Вычисляется \(x \mod p_i^{e_i}\).
• Для этого используется представление \(x\) в \(p_i\)-ичной системе счисления:

\[ x = x_0 + x_1 p_i + x_2 p_i^2 + \dots + x_{e_i-1} p_i^{e_i-1} \mod p_i^{e_i} \] где \(0 \le x_j < p_i\).

• Последовательно находятся коэффициенты \(x_0, x_1, \dots, x_{e_i-1}\).
• Для нахождения \(x_0\) вычисляется:

\[ h^{n/p_i} = g^{x \cdot n/p_i} = (g^{n/p_i})^{x_0} \] так как \(g^{n/p_i}\) имеет порядок \(p_i\). Затем \(x_0\) находится перебором или с помощью алгоритма «шаг младенца — шаг великана» (алгоритм Шенкса) за время \(O(\sqrt{p_i})\).

• После нахождения \(x_0\) вычисляется:

\[ h_1 = h \cdot g^{-x_0} \] и процесс повторяется для нахождения \(x_1\) с использованием \(h_1^{n/p_i^2}\) и т.д.

1. Сбор результата. После нахождения всех \(x_i\) по модулям \(p_i^{e_i}\) применяется китайская теорема об остатках для восстановления \(x\) по модулю \(n\).

Вычислительная сложность

Временная сложность алгоритма Полига — Хеллмана составляет:

\[ O\left( \sum_{i=1}^{k} e_i \cdot \sqrt{p_i} \right) \]

где \(p_i\) — простые делители порядка \(n\), а \(e_i\) — их показатели. Таким образом, сложность определяется наибольшим простым делителем \(p_{\max}\) порядка группы. Если \(p_{\max}\) велико (например, порядка \(10^{30}\) и более), то алгоритм становится неэффективным. Однако если все \(p_i\) малы, то алгоритм работает очень быстро — за полиномиальное время относительно размера входа.

Пространственная сложность алгоритма незначительна — требуется хранить лишь несколько промежуточных значений.

Применение

Криптографический анализ

Метод Полига — Хеллмана используется в криптоанализе для оценки стойкости криптосистем, основанных на задаче дискретного логарифмирования. Он показывает, что для обеспечения безопасности необходимо выбирать группы, порядок которых имеет хотя бы один большой простой делитель (обычно порядка 256 бит и более). В противном случае злоумышленник может вычислить дискретный логарифм за приемлемое время.

Криптосистемы, подверженные атаке

• Протокол Диффи — Хеллмана (обмен ключами). Если группа \(G\) имеет гладкий порядок, то злоумышленник, перехвативший открытые ключи, может вычислить общий секретный ключ.
• Криптосистема Эль-Гамаля. Аналогично, если порядок группы гладкий, то закрытый ключ может быть восстановлен.
• Цифровая подпись на основе эллиптических кривых (ECDSA). В случае эллиптических кривых метод применяется, если порядок кривой (количество точек) имеет малые простые делители.

Ограничения

Метод неэффективен для групп с большим простым делителем порядка. Например, в стандартных криптографических протоколах (например, в группе \(Z_p^*\) для 2048-битного \(p\)) порядок \(p-1\) обычно содержит большой простой множитель, что делает атаку Полига — Хеллмана непрактичной.

Пример работы

Рассмотрим группу \(G = Z_{101}^*\) (мультипликативная группа по модулю 101). Порядок группы \(n = 100 = 2^2 \cdot 5^2\). Пусть \(g = 2\) — образующий элемент, и требуется найти \(x\) такой, что \(2^x = 3 \mod 101\).

1. Факторизация: \(n = 2^2 \cdot 5^2\).
2. Для \(p=2, e=2\):

• Находим \(x \mod 4\). Представляем \(x = x_0 + 2x_1\).
• Вычисляем \(h^{n/2} = 3^{50} \mod 101\). Получаем \(3^{50} = 100 \mod 101\). Так как \(g^{n/2} = 2^{50} = 100 \mod 101\), то \(x_0 = 1\).
• Затем \(h_1 = 3 \cdot 2^{-1} = 3 \cdot 51 = 52 \mod 101\). Вычисляем \(h_1^{n/4} = 52^{25} \mod 101\). Получаем \(52^{25} = 1 \mod 101\). Так как \(g^{n/4} = 2^{25} = 32 \mod 101\), то \(x_1 = 0\). Итого \(x \equiv 1 \mod 4\).

1. Для \(p=5, e=2\):

• Находим \(x \mod 25\). Представляем \(x = x_0 + 5x_1\).
• Вычисляем \(h^{n/5} = 3^{20} \mod 101\). Получаем \(3^{20} = 84 \mod 101\). \(g^{n/5} = 2^{20} = 95 \mod 101\). Перебором находим \(x_0 = 3\) (так как \(95^3 = 84 \mod 101\)).
• Затем \(h_1 = 3 \cdot 2^{-3} = 3 \cdot 2^{-3} \mod 101\). \(2^{-3} = 2^{97} \mod 101 = 38\). \(h_1 = 3 \cdot 38 = 114 \equiv 13 \mod 101\). Вычисляем \(h_1^{n/25} = 13^{4} \mod 101\). Получаем \(13^4 = 1 \mod 101\). \(g^{n/25} = 2^{4} = 16 \mod 101\). Так как \(16^0 = 1\), то \(x_1 = 0\). Итого \(x \equiv 3 \mod 25\).

1. Решаем систему сравнений:

\[ x \equiv 1 \pmod{4}, \quad x \equiv 3 \pmod{25} \] По китайской теореме об остатках получаем \(x = 53 \mod 100\). Проверка: \(2^{53} = 3 \mod 101\) — верно.

Вариации и родственные алгоритмы

• Алгоритм Силвера — Полига — Хеллмана — то же самое, с упоминанием приоритета Силвера.
• Алгоритм «шаг младенца — шаг великана» (алгоритм Шенкса) — используется как подпрограмма в методе Полига — Хеллмана для нахождения \(x_0\).
• Алгоритм Полига — Хеллмана для эллиптических кривых — адаптация метода для групп точек эллиптических кривых, где порядок кривой (количество точек) может быть гладким.

Критика и ограничения

Основной недостаток метода — его экспоненциальная зависимость от размера наибольшего простого делителя порядка группы. В современных криптографических системах порядок группы выбирается так, чтобы содержать большой простой делитель (например, 256-битное простое число), что делает атаку Полига — Хеллмана непрактичной. Кроме того, метод требует факторизации порядка группы, что само по себе может быть сложной задачей для больших чисел. Однако если порядок известен и гладок, то алгоритм работает очень эффективно.

Источники

• Pohlig, S., Hellman, M. (1978). «An improved algorithm for computing logarithms over GF(p) and its cryptographic significance». IEEE Transactions on Information Theory, 24(1), 106–110.
• Menezes, A. J., van Oorschot, P. C., Vanstone, S. A. (1996). Handbook of Applied Cryptography. CRC Press. Глава 3.6.
• Шнайер, Б. (2002). Прикладная криптография. Глава 11.6.
• Silver, R. (1970-е). Неопубликованная работа, упоминаемая в литературе.