Puncte:1

Atacul preimagine asupra sumei a două funcții Hash modulo 2

drapel cn

Dacă o funcție hash $H$ este definit ca $H(x_1,x_2) = H_1(x_1) \oplus H_2(x_2)$ pentru două funcții hash bune de n biți $H_1$ și $H_2$ atunci cum putem construi un atac preimagine asupra $H$ adică de $O(2^\frac{n}{2})$ dat ceva y?

Aici, avem voie să interogăm $H_1$ și $H_2$ ?

Chiar aș aprecia câteva indicii.

Patriot avatar
drapel cn
Poate doriți să votați răspunsul pe care l-ați acceptat.
drapel cn
@Patriot Da, am încercat. Am nevoie de cel puțin 15 reputație ca să se arate.
Patriot avatar
drapel cn
OK, aproape ai ajuns.
Puncte:2
drapel in

Aceasta pare a fi o muncă la domiciliu, așa că mă voi opri la o soluție completă. Da, aveți voie să interogați funcțiile $H_1$ și $H_2$ este aproape singurul lucru pe care îl poți face. Deci, puteți colecta un grup de perechi de intrare și ieșire pentru fiecare. Și atunci ce poți face cu două astfel de colecții de perechi de intrare și ieșire? Poate doriți să indexați unul dintre ele pentru o căutare eficientă.

drapel cn
Pot alege un set de interogări de dimensiunea 2^(n/2) și pot interoga H_1(x) și H_2(x) pe acel set. Apoi va trebui să compar valorile y+H_1(x) și H_2(x) folosind cele interogate pentru a găsi o coliziune. Este corect?
Meir Maor avatar
drapel in
da, este o metodă rezonabilă.
drapel cn
Mulțumesc mult

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.