înregistrare Logare
Puncte:1
Turbo avatar Crypto

Împărțire cu $2$ sau rădăcină principală cu oracolul DH

drapel ru
Turbo

Să presupunem $g$ este generator de grupă multiplicativă modulo prime $p=2q+1$ Unde $q$ este prim.

Să presupunem că știm $g^{2t}\bmod p$ și $g^{2}\bmod p$ și presupunem că putem avea acces la un oracol Diffie-Hellman.

Putem găsi $g^t\bmod p$ în timp polinomial?

Rețineți, dacă putem face asta, putem rupe jurnalul discret cu acces la un oracol DH atunci când comanda generatorului este egală.

46
0 + 0
Puncte:2
poncho avatar Crypto
drapel my
poncho

Putem găsi $g^t \bmod p$ în timp polinomial?

Putem găsi oricare $g^t$ sau $-g^{t} = g^{t + (p-1)/2}$; evident, nu putem spune care a fost cea corectă cu informațiile care ni s-au oferit.

pentru că $p \equiv 3 \pmod 4$ (deoarece $(p-1)/2$ se presupune a fi prim, și luând $p=5$ off the table - care poate fi tratat ca un caz special), apoi [1] putem calcula rădăcini pătrate modulare cu calculul simplu $\sqrt{x} = \pm x^{(p+1)/4}$.

Deci avem $g^t \in\{ -(g^{2t})^{(p+1)/4},+(g^{2t})^{(p+1)/4}\}$, ușor de realizat în polytime.

[1]: Dacă $p \equiv 1 \bmod 4$, atunci este încă practic să calculezi rădăcini pătrate modulare, este puțin mai implicat.

0 + 0
Turbo avatar
drapel ru
Turbo
Adevărat.. dar poate oracolul să rezolve ambiguitatea din semn?
0
Răspunde
poncho avatar
drapel my
poncho
@Turbo: nu, nu se poate, deoarece ambele valori sunt soluții posibile pentru $g^t$
0
Răspunde
drapel romania
SEF 777
întrebarea această in alte limbi:

Postează un răspuns

Majoritatea oamenilor nu înțeleg că a pune multe întrebări deblochează învățarea și îmbunătățește legătura interpersonală. În studiile lui Alison, de exemplu, deși oamenii își puteau aminti cu exactitate câte întrebări au fost puse în conversațiile lor, ei nu au intuit legătura dintre întrebări și apreciere. În patru studii, în care participanții au fost implicați în conversații ei înșiși sau au citit transcrieri ale conversațiilor altora, oamenii au avut tendința să nu realizeze că întrebarea ar influența – sau ar fi influențat – nivelul de prietenie dintre conversatori.