înregistrare Logare
Puncte:1
avatar Crypto

Modificarea problemei logaritmului discret în Zp prin selectarea unui subset de elemente de grup

drapel do
Panos

Lăsa $g$ generator de grup ciclic $Z_p$ de ordine $p-1$, Unde $g$ poate genera toate elementele grupului $\alpha \in Z_p$ la fel de $\alpha = g^x$mod$p$, $x \in (0..p-1)$, unde problema logaritmului discret este grea, adică calculul $x= $Buturuga$_ga$.

Să presupunem că instanțiăm un sistem criptografic cu parametrii de mai sus (de exemplu, o schemă de criptare sau o schemă de semnătură digitală), dar cu modificarea luării în considerare doar a valorilor $x$ valabil astfel încât $\alpha < t$, Unde $t \in (0..p-1)$ o valoare „țintă”. Intuitiv, securitatea acestui sistem este echivalentă cu cea fără modificarea respectivă (adică introducerea cerinței ca acesta să poată utiliza numai acele $x$ astfel încât rezultatul $a$ sunt sub țintă), deoarece un atacator ar trebui totuși să forțeze toate $x$ care nu satisfac asta.

Întrebarea mea este totuși, deschide acest lucru vreun atac potențial teoretic numerelor? De exemplu, munca unui atacator ar putea fi accelerată folosind o formulă matematică pentru a exclude „invalidul” $x$ și astfel reduc direct securitatea sistemului cripto?

88
0 + 0
kelalaka avatar
drapel in
kelalaka
În primul rând, asigurați-vă că $p-1$ nu provoacă un atac al lui Pohlig-Hellman. În al doilea rând, căutați cangurii lui Pollard, care funcționează foarte bine în intervale.
0
Răspunde
drapel do
Panos
Deci, pentru ca Pohlig-Hellman să funcționeze, $p-1$ trebuie să fie o putere a unui prim, care se aplică și parametrilor originali (adică se pare că modificarea mea nu este afectată de acest lucru). Algoritmul cangur pare aplicabil modificării mele, dar încă nu sunt sigur cum ar putea reduce securitatea problemei inițiale. Luând în considerare algoritmul din https://en.wikipedia.org/wiki/Pollard%27s_kangaroo_algorithm , chiar dacă intervalul meu valid (0,...t) este foarte mic (de exemplu, dacă t=1 ca caz extrem), atunci cangurul ar mai trebui să calculeze seria de numere întregi $d_0,... ,d_p$ care este scumpă, nu?
0
Răspunde
fgrieu avatar
drapel ng
fgrieu
Este dificil din punct de vedere computațional să instanțiați un sistem criptografic care se limitează la $x$ cu $g^x\bmod p=\alpha
1
Răspunde
drapel do
Panos
Sunt de acord că atingerea $t$ necesită efort de calcul. Să presupunem că $t$ este suficient de mare astfel încât acest efort să fie în limite rezonabile. Deci intuitiv, securitatea sistemului modificat (adică forța brută necesară a atacatorului) ar fi $p-t$, deoarece atacatorul știe $t$. Încerc doar să înțeleg dacă există vreun atac teoretic numeric care reduce securitatea sub $p-t$. Cangurul menționat mai sus nu mi se pare o problemă.
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.