Puncte:3

Pot trata hashurile SHA-256 ca 64 de aruncări de zaruri corecte cu numere între 1 și 16?

drapel in

Am înțeles că SHA-256 este destul de aleatoriu sau destul de „aleatoriu”.

Am presupus că asta ar însemna că fiecare personaj se va comporta ca o aruncare de 1 până la 16 zaruri.

Cu această ipoteză, m-aș aștepta să puteți modela probabilitatea de a repeta caractere ca 16$^x$. Deci un lanț de $\texttt{FFF}$ sau $\texttt{333}$ ar avea o șansă de 1 la $16^3 (4096)$ și un lanț de $\texttt{FFFF}$ o șansă de 1 la $16^4 (65536)$.

Dar, în timp ce generăm o mulțime de hashe-uri (cu UUID-uri aleatorii ca semințe) pentru a confirma presupunerea mea, numerele nu se adună. De exemplu, într-un set de 100k hashuri am deja mai mult de 1k lanțuri de 4 caractere sau mai multe (în timp ce mă așteptam la 1 și 2 lanțuri).

Deci aici încerc să înțeleg de ce presupunerea mea a fost greșită în primul rând.

Am înțeles greșit în mod fundamental caracterul aleatoriu al hashe-urilor SHA-256 sau este altceva?

kelalaka avatar
drapel in
Nu este o întrebare clară, deoarece experimentul dvs. nu este clar. Vedeți [experimentul meu SHA-1 cu privire la zerourile de început](https://crypto.stackexchange.com/a/83227/18298). Cum ai lanțul 1K? Rețineți că modelăm SHA-256 ca o funcție pseudo-aleatorie, nu știm că este una nu.
kelalaka avatar
drapel in
Modelul dvs. lipsește un punct în care, în ieșirea de 64 de hex a lui SHA-256, trebuie să găsiți probabilitatea unei secvențe de 4 caractere oriunde. Nu puteți modela cu adevărat ca fiecare hex de ieșire ca o singură rolă, deoarece nu sunt independente de intrare...
drapel in
@kelalaka mulțumesc pentru intrare!
Puncte:4
drapel my

Deci un lanț de $\texttt{FFF}$ sau $\texttt{333}$ ar avea o șansă de 1 la $16^3 (4096)$

De fapt, o șansă de trei ciuguri repetate (fie el $\texttt{FFF}$ sau $\texttt{333}$ sau $\texttt{000}$) ar fi de 1 in $16^2 (256)$ - asta se întâmplă pentru că există $16^3$ valori la fel de probabile ale acelor 3 nybbles și 16 dintre aceste modele sunt repetări - prin urmare probabilitatea unei repetări este ${16 \over 16^3} = {1 \over 16^2}$. Dacă specificați că trebuie să fie $\texttt{FFF}$ (Așadar $\texttt{333}$ nu ar conta), atunci ai primi $16^3$; totuși nu asta faci.

De exemplu, într-un set de 100.000 hashuri, am deja peste 1.000 lanțuri de 4 caractere sau mai multe

Așa este corect - în 100.000 de hasheuri, există aproximativ 6.000.000 de locuri în care ar putea apărea un șir de 4 nibble-uri repetate; orice loc are o probabilitate de $16^{-3} = {1 \over 4096}$ de a fi o repetare - un calcul simplist oferă aproximativ 1.400 de șiruri de repetări.

Spun simplist, deoarece acest calcul simplu ignoră șirurile care se suprapun - de exemplu, un șir de 5 nybble-uri repetate ar conta ca o rundă, nu 2 runde de 4. În plus, probabilitățile implicate cu șirurile suprapuse nu sunt independente. În timp ce aceste efecte reduc oarecum totalul așteptat, cred că calculul simplist este suficient de bun pentru o estimare din spate.

drapel in
mulțumesc foarte mult! Subliniind eroarea din presupunerea mea, am reușit să înțeleg unde este problema și cu acest videoclip https://www.youtube.com/watch?v=O4Qnsubo2tg am putut să înțeleg cum trebuie să îmi ajustez funcția
drapel in
tbh sunt încă puțin confuz de ce o șansă de 1/4096 nu înseamnă un rezultat mediu de 100k / 4096, pentru că ar fi ~24.
knaccc avatar
drapel es
@braunbaer Deoarece într-un șir hexadecimal de 64 de caractere, există 61 de poziții posibile în care poate exista o secvență de șiruri de 4 hexadecimale. Pentru fiecare dintre aceste poziții, șansele ca primul caracter să fie aceleași cu următoarele trei caractere este (1/16)^3 = (1/4096). Prin urmare, secvențele quad-repeating-hex per hash vor fi (1/4096 * 61) = 0,01489257812. Pe 100k hashe-uri, adică 0,01489257812 * 100k = 1489.
drapel in
@knaccc da! asta are atât de mult sens. Deci, pentru a fi clar, dacă am lucra cu un șir hexadecimal de 4 caractere, am avea o șansă „plată” de 1/4096, deoarece există o singură poziție posibilă pentru o secvență de șiruri de 4 hex sau (1/4096 *1) a fi clar
knaccc avatar
drapel es
@braunbaer da, exact. 1/4096 șansă ca toate caracterele hexagonale să fie aceleași, ceea ce este un alt mod de a spune că al 2-lea, al 3-lea și al 4-lea caracter sunt toți la fel ca primul.
Maarten Bodewes avatar
drapel in
Acest Q/A a făcut HNQ, așa că am editat întrebarea pentru a fi reprezentativă - ceea ce înseamnă și actualizarea răspunsului desigur - sper să nu vă superi.

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.