Puncte:0

Construcție Merkle-DamgÃ¥rd

drapel bw

Lăsa $H^f$ fie o funcție hash proiectată folosind construcția Merkle-DamgÃ¥rd pe $f:\{0,1\}^{2n}\la\{0,1\}^n$. Scrieți un algoritm care face aproximativ 2,2 $^{n/2}$ multe interogări la $f$ și găsiți patru mesaje sub care toate hash la aceeași valoare $H^f$.

Am o idee să folosesc extensia de lungime și atacul de 2 ani pentru a obține patru coliziuni. Dar nu sunt în stare să scriu soluția potrivită. Ma poate ajuta cineva sa-mi dau seama.

fgrieu avatar
drapel ng
Vă sugerez (A) să scrieți definiția pe care o obțineți a funcției hash pentru cea mai mare intrare care necesită două evaluări de $f$; (B) explicați cum găsiți o coliziune internă variind intrarea mesajului primului $f$; (C) explicați cum găsiți o coliziune variind intrarea mesajului celui de-al doilea $f$; (D) concluzionează. Nu înțeleg cum obținem 2,2$^{n/2}$, cred că numărul așteptat de evaluări pentru $f$ este ca $2^{n/2+1,326}$ (care este mai puțin pentru $n$ mari) .
drapel bw
da, aceasta este o valoare aproximativă @fgrieu
poncho avatar
drapel my
Poate că în loc de $2,2^{n/2}$, ceea ce s-a înțeles a fost $2 \cdot 2^{n/2} = 2 \times 2^{n/2}$
kelalaka avatar
drapel in
[încrucișat la CS](https://cs.stackexchange.com/q/141917/94479)

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.