Регистрация Войти
Рейтинг:1
Turbo avatar Crypto

Деление на $2$ или главный корень с оракулом DH

флаг ru
Turbo

Предполагать $г$ является генератором мультипликативной группы по простому модулю $p=2q+1$ куда $q$ является простым.

Предположим, мы знаем $g^{2t}\bmod p$ и $g^{2}\bmod p$ и предположим, что у нас есть доступ к оракулу Диффи-Хеллмана.

Можем ли мы найти $g^t\bmod p$ за полиномиальное время?

Обратите внимание, что если мы сможем сделать это, мы сможем сломать дискретный журнал с доступом к оракулу DH, когда порядок генератора четный.

46
0 + 0
Рейтинг:2
poncho avatar Crypto
флаг my
poncho

Можем ли мы найти $g^t \bmod p$ за полиномиальное время?

Мы можем найти либо $г^т$ или же $-g^{t} = g^{t + (p-1)/2}$; очевидно, мы не можем сказать, какой из них был правильным с информацией, которую нам дали.

Так как $p \экв 3 \pmod 4$ (так как $(p-1)/2$ предполагается простым, и принимая $р=5$ вне таблицы — это можно рассматривать как частный случай), то [1] мы можем вычислить модульные квадратные корни с помощью простого вычисления $\sqrt{x} = \pm x^{(p+1)/4}$.

Итак, у нас есть $g^t \in\{ -(g^{2t})^{(p+1)/4},+(g^{2t})^{(p+1)/4}\}$, легко выполнимый в политайме.

[1]: Если $p \экв 1 \bmod 4$, тогда по-прежнему практично вычислять модульные квадратные корни, это немного сложнее.

0 + 0
Turbo avatar
флаг ru
Turbo
Верно.. но может ли оракул разрешить двусмысленность в знаке?
0
Ответить
poncho avatar
флаг my
poncho
@Turbo: нет, не может, потому что оба значения являются возможными решениями для $g^t$
0
Ответить
флаг Moldova
Admin
Этот вопрос на других языках:

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

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