Рейтинг:0

Почему существуют разные версии атаки Полига-Хеллмана?

флаг fr

Я думаю, что понимаю атаку Полига-Хеллмана на эллиптических кривых. Со страницы 31 Пейринги для начинающих:

  • Найдите групповой заказ $\#E(\mathbb{F}_q)$, назови это $n$, и факторизовать его. Пример: $966 = 2 \cdot 3 \cdot 7 \cdot 23$
  • Для каждого простого множителя $p_i$, вверху: умножить генератор $P$ и целевая точка (не знаю, что это за термин), $Q$, к $n/p_i$ (кофактор)
    • В этом конкретном примере нет простых множителей, возведенных в степень (например, факторизация не $2^3 \cdot 5^2$, но вы умножаете на $n$ делится на простое число, а не на простое число, возведенное в степень)
  • Теперь у нас есть $[\frac{n}{p_i}]P$ и $[\frac{n}{p_i}]Q$.
  • Мы знаем порядок $[\frac{n}{p_i}]P$ является $p_i$
  • Таким образом, $[\frac{n}{p_i}]Q = [k \text{ mod } p_i]P$ куда $кП = Q$
  • Мы решаем для $k\text{ мод } p_i$ и повторить для каждого $p_i$
  • Тогда, используя китайскую теорему об остатках, мы можем найти $к\текст{ мод } п$

Это все примерно имеет смысл. Это также совпадает с другими объяснениями Полига-Хеллмана на этом сайте: Алгоритм Полига-Хеллмана.

Тем не менее, я сбит с толку, потому что кажется, что "полная" атака Полига-Хеллмана включает в себя представление $k_i$ как $z_0 + z_1p_i + z_2p_i^2 + ...$

Почему существует несколько вариантов алгоритма Полига-Хеллмана?

Рейтинг:2
флаг gb

На самом деле метод, использующий китайскую теорему об остатках, является более общей версией. тот, который представляет $k_i$ как $z_0 + z_1p_i + z_2p_i^2 + ...$ полезен только в ситуации, когда групповой порядок представляет собой первичную мощность (силу $p_i$), поэтому вы сначала решаете каждую из меньших степеней и накапливаете. Вы используете CRT (или их смесь), когда группы не являются всеми степенями одного и того же простого числа. В обоих случаях идея одна и та же — решить DLP в меньшей подгруппе и использовать эту информацию для восстановления решения в полной группе.

Foobar avatar
флаг fr
Чтобы уточнить, когда вы говорите «групповой порядок», вы имеете в виду порядок подгруппы $p_i^{n_i}$, верно?
meshcollider avatar
флаг gb
Полный порядок группы, в которой вы вычисляете дискретный вход. В примере в вашем вопросе порядок был составным (966), поэтому мы используем CRT. Если бы порядок был, скажем, 3 ^ 5, мы бы сначала использовали подгруппу порядка 3, затем 3 ^ 2, затем 3 ^ 3 и т. д.

Ответить или комментировать

Большинство людей не понимают, что склонность к познанию нового открывает путь к обучению и улучшает межличностные связи. В исследованиях Элисон, например, хотя люди могли точно вспомнить, сколько вопросов было задано в их разговорах, они не чувствовали интуитивно связи между вопросами и симпатиями. В четырех исследованиях, в которых участники сами участвовали в разговорах или читали стенограммы чужих разговоров, люди, как правило, не осознавали, что задаваемый вопрос повлияет — или повлиял — на уровень дружбы между собеседниками.