înregistrare Logare
Puncte:1
Iwan5050 avatar Crypto

Este $H:\mathbb{Z} \rightarrow \mathbb{Z}_{p}^{*}$ și $a \mapsto g^a\bmod p$ cu $p$ prim (puternic) fără coliziuni?

drapel us
Iwan5050

Lăsa $H:\mathbb{Z} \rightarrow \mathbb{Z}_{p}^{*}$ și $a \mapsto g^a\bmod p$ pentru $g \in \mathbb{Z}_{p}^{*}$ Unde $p$ este prim. Este această funcție (puternic) fără coliziuni, ceea ce înseamnă că nu putem găsi practic $x_1$,$x_2$ astfel încât $H(x_1)=H(x_2)$?

Susțin nu cu următorul raționament: Să $A$ fi un algoritm care generează $x_1 \neq x_2$ astfel încât $H(x_1)=H(x_2)$ și definiți $A: \mathbb{N} \rightarrow (X_1,X_2)$ $A: n \mapsto (n,n+(p-1))=(x_1,x_2)$ găsim într-adevăr cu mica teoremă a lui Fermat că $g^{x_2}=g^{n+(p-1)}=g^{n}g^{p-1}=g^{n}=g^{x_1}$

Marea mea frică este aici că am confundat (slab) fără coliziuni cu puternice fără coliziuni. Dacă ceva greșit, vreun indiciu ce să faci mai bine.

88
0 + 0
fgrieu avatar
drapel ng
fgrieu
Sugestie: priviți din nou setul de intrare pentru $H$. Dacă $p$ este prim (sau mai general de factorizare cunoscută), face asta posibilă afișarea unei a doua preimagine? Se potrivește asta cu definiția „(puternic) fără coliziune” pe care o utilizați (și ar trebui să facă parte din întrebarea BTW)?
0
Răspunde
Iwan5050 avatar
drapel us
Iwan5050
Văd o greșeală lol. Nu, după definiția noastră, că îl folosim nu este într-adevăr (puternic) lipsit de coliziuni. Deoarece putem găsi astfel de $x_1,x_2$ practic (chiar și în câteva secunde) cu $H(x_1)=H(x_2)$, deci nu (puternic) fără coliziuni.
0
Răspunde
SSA avatar
drapel ng
SSA
Maparea dvs. este un homomorfism surjectiv, unde x și x+p se vor mapa la același element de codomeniu. ${x \equiv x+p}$, de asemenea, nucleul mapării dvs. este ${
0
Răspunde
fgrieu avatar
drapel ng
fgrieu
@SSA: dacă prim $p$ este public, atunci $p$ mare nu este suficient de bun pentru a face $H$ rezistent la coliziuni. În cripto, luăm în considerare adversarii inteligenți (modelizați prin algoritmi, în teorie orice algoritm, în practică algoritm proiectat de oameni sau AI) și se așteaptă ca aceștia (adversari, algoritmi) să folosească orice informație publică, inclusiv parametri. Nu sunt obligați să genereze coliziuni aleatoriu (care ar eșua pentru $p$ mari).
0
Răspunde
SSA avatar
drapel ng
SSA
@fgrieu, Funcția Hash Chaum-van Heijst-Pfitzmann, este similară cu aceasta. satisface toate cele 3 proprietăți pentru care este necesară o funcție hash, dar nu este văzută ca fiind utilizată, deoarece este lent în practică.
0
Răspunde
Puncte:1
Iwan5050 avatar Crypto
drapel us
Iwan5050

Nu, după definiția noastră, că îl folosim nu este într-adevăr (puternic) lipsit de coliziuni. Pentru că cu algoritmul $A$ am construit deja o modalitate foarte rapidă de a calcula astfel $x_1,x_2$ cu $H(x_1)=H(x_2)$ și, practic, prin definiție, aceasta contrazice condiția fără coliziune.

0 + 0
fgrieu avatar
drapel ng
fgrieu
Ar trebui să puteți accepta acest răspuns în câteva zile. Voi încerca apoi să elimin acel comentariu.
0
Răspunde
fgrieu avatar
drapel ng
fgrieu
Aș prefera demonstrarea prin exemplu: „Intrarile $a=1$ și $a=p$ din $H$ aparțin domeniului de definiție $\mathbb Z$, iar prin FLT ieșirile se ciocnesc deoarece $p$ este prim” ( și poate „O astfel de pereche de ciocnire poate fi prezentată de un adversar deoarece $p$ este un parametru public”), urmată de „Astfel, $H$ nu este rezistent la coliziuni”.
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.