Re: Generování náhodných čísel

[Pavel Kankovsky]

On Mon, 2 Feb 2004, Jan Kokoska wrote:

> > Pak jeste zalezi na tom, co ma byt vysledkem. Vetsina nahodnych i
> > pseudonahodnych generatoru produkuje proud bitu resp. bajtu s uniformnim
> > rozdelenim. Vami navrzeny postup generuje pseudonahodnou sekvenci znaku
> > z mnoziny { '0'..'9', 'A'..'F' } 
> 
> To uz pravdu nemate, sekvence je z mnoziny {'0'..'9'}, ani dale uplne
> nesouhlasim.

Ojoj...ja prehledl -d u hexdump. No jo, clovek by si mel vzdy poradne
precist, k cemu se to vlastne vyjadruje. :P

> Vinou meho trivialniho postupu bude kazde pate cislo z rozsahu 0..5
> (nahodny vstup konvertovan po dvou bajtech na hodnoty 0..65535),

Spis kazde pate (rozumej kazde 5n+1.) cislo mezi 0 a 6. Ale nerovnomerne
bude rozdeleni pravdepodobnosti na vsech mistech a dokonce ani modulo na
tom nic nemeni.

> jinak se nedomnivam ze bude vysledek pseudonahodny.. pokud to chcete
> vysvetlovat laikovi, proc by tomu tak melo byt?

Ano, mate pravdu, takhle by vysledek nebyl pseudonahodny, protoze kazdy
trouba dokaze generovanou posloupnost odlisit od nahodne resp. ucinit
odhat hodnoty nasledujiciho clena posloupnosti se znatelne nadprumernou
pravdepodobnosti uspechu (napr. trivialni hypoteza, ze nasledujici cislice
bude 0 ma pokazde pravdepodobnost uspechu vetsi nez ocekavanou 1/10). :)

Pokud bychom diskutovali primo vystup samotneho /dev/random (nebo
nejakou jeho transformaci, ktera nekazi jeho vlastnosti), pak by to bylo
komplikovanejsi. Toto zarizeni je navrzeno tak, aby nejak realisticky
odhadovalo, kolik "skutecne nahody" do nej ruznymi cestami vstupuje, a
vzdy generovalo jen takove mnozstvi vystupu, na ktere si mezitim
nasetrilo dost one "skutecne nahody". Klicova otazka je, nakolik je ten
odhad presny: pokud by totiz byl vetsi nez je skutecnost (coz samozrejme 
zalezi na mnoha obtizne kvantifikovatelnych faktorech), pak se ve vysledne
posloupnosti objevi nejaka skryta zavislost, ktera ji odlisi od zcela
nahodne posloupnosti, a takovy generator muze aspirovat pouze na to, aby
byl pseudonahodny, tj. ze ho nebude mozno rozlisit od zcela nahodneho
pouze za jistych omezujicich predpokladu na vypocetni silu nepritele.

> Autor vlakna na rozdil od vas nevypada, ze studoval kryptografii na
> matfyzu (no offense), takze tak hluboko to mozna neni treba resit ;) 

Ubezpecuji vsechny, ze kryptografie tvorila jen pomerne malou cast meho
studia na matfyzu. :)  Nicmene bych rekl, ze to, co puvodni tazatel
potrebuje, nesouvisi az tolik s tim, zda a jak prislusne problematice
rozumi.

> Realna bezpecnost je nehlede na entropii zdroje relativni (postranni
> kanaly), vyplati se uvazovat o tom, co ma pro zabezpeceni danych dat
> smysl. A vyplati se uvazovat dostatecne kratce, ma-li se vyvojaruv cas
> zaplatit. Uz mlcim a jdu zhodnocovat svuj vyvojarsky cas...

Vyuziti (pseudo)nahodnych cisel nemusi byt nutne jen pro kryptograficke
ucely. Velkou spotrebu ma i jakakoli simulace metodou Monte Carlo. Tam je
samozrejme pripadna moznost utoku pres nejaky postranni kanal irelevantni,
zalezi jen na kvalite samotneho vystupu (a nekdy na ni zalezi velice).


On Mon, 2 Feb 2004, Jan Kokoska wrote:

> Hmm, nedomyslel jsem to modulo, cisla z intervalu 0..5535 maji trochu
> vetsi pravdepodobnost vyskytu, nez jejich doplnek do 9999. Takze s
> nevhodne pouzitym uniformnim rozdelenim mate pravdu. Pokud je baze tech
> rozdeleni (pocet prvku) nesoudelna, je zrejme i ten prevod netrivialni,
> pokud se s _zadnou_ chybou nehodlam smirit (v uvedenem pripade a mudulo
> 10, pokud mi vadi, ze pravdepodobnost vyskytu 0..5 je 6553/6554/10, asi
> 0.099984742142203237, zatimco 5..9 se vyskytuje s P 6554/6553/10, tedy
> asi 0.10001526018617428.

To mate evidentne spatne, protoze cislic <= 5 se vyskytuje vice, nez
cislic > 5. Ale je pravda, ze pri pohledu na vsechna cisla najednou ten
rozdil neni az tak velky.

Jenze na kazdem ctvrtem (presneji 4n+1.) miste (druhem v puvodnim
petimistnem cisle) bude rozdil mnohem vetsi a patrnejsi: napr. cislo 0
se objevi s pravdepodobnosti 7000/65536 = 0.10681, zatimco treba 9
jen s pravdepodobnosti 6000/65536 = 0.09155. To uz chyba v jednotkach
procent.


On Mon, 2 Feb 2004, oldfrog.linux na volny.cz wrote:

> Nekde jsem zahledl navod na generator nahodnych cisel,
> ktery jako zdroj nahodnosti bere sum diody v zavernem
> smeru. Staci pry zvukovka, vhodna dioda a mozna par
> pasivnich soucastek. V nahodnosti je pry bezkonkurencni...

Bezkonkurencni...no...asi dost zalezi na provedeni.


--Pavel Kankovsky aka Peak  [ Boycott Microsoft--http://www.vcnet.com/bms ]
"Resistance is futile. Open your source code and prepare for assimilation."