Bjarke Walling Petersen wrote:
> Er hashfunktioners (som MD5, SHA-1, etc.) output uniformt fordelt
Det vil jeg tro, ellers er det en uhyre dårlig tilfældighedsgenerator.
> og overholder den i øvrigt de statistiske tests som en
> tilfældighedsgenerator også skal?
Jeg ved ikke hvilke statistiske tests du referere til.
En pseudo tilfældig generator vil generere en sekvens af tal der
næsten har de samme egenskaber som en sand tilfældig sekvens,
men da koden til sådan en generator har en endelig størrelse,
kan den aldrig være sand tilfældig.
I praksis kan du sample korrelationsfunktioner, før eller siden
vil du se en korrelation der er forskellige fra en sand tilfældigheds
generator der ikke har nogen korrelationer overhovedet.
Mht. enkryption er et mere relevant spørgsmål om koden kan brydes
inden for f.eks. 10^9 år. Om sekvensen så er sand eller pseudo-
tilfældig er irrelevant.
> Selvom det ikke har så meget med kryptologi at gøre kunne et sjovt forsøg
> jo være at lave en tilfældighedsgenerator utrolig simpelt - noget i
> retningen af h(s) / h_max, hvor h betegner funktionen der giver
> hashværdien af input (tilfældighedsgeneratorens frø) s (kaldes det ikke
> frø på dansk?) og h_max er den maksimale outputværdi. Man kunne så enten
> udregne det iterativt, så output blev input ved næste generering - eller
> man kunne lade s være et index, der blot hver gang bliver forhøjet med én.
> Ville det være en god tilfældighedsgenerator?
Prøv at udregne C(n)=<h(s[i])*h(s[i-n])> hvor du tager gennemsnit over i,
og hvor du sampler den for en række ofsets n.
Plotter du denne er C(0)=<h²> hvorimod C(n)=0 for n>1.
Det er den mest basale test, ud over at fordelingen af h(s) er flad.
Du kan så prøve C2(n,m)=<h(s[i])*h(s[i-n])*h(s[i-m])> osv.
--
Mvh. Carsten Svaneborg
http://www.softwarepatenter.dk