Den perfekta slumpgeneratorn

[JustNeed]

En "slumptalskälla" som inte nämnts är tiden. Om en apparat har en klocka, och användaren inte kan veta vad den klockan kan vara, så kan tiden - eller åtminstone de minst signifikanta siffrorna i den - vara tillräckligt godtyckliga för att agera slumptal eller frö till slumptalsgenerering.

En klassisk programmeringslab är att dra random med tiden som källa. Insikten den laborationen syftar till är att systemtiden ändrar sig på ett förutsägbart sätt under programmets gång. Dvs, om man vet tiden vid ett tillfälle i koden kan man räkna ut vad tiden är i ett annat tillfälle.
Långt ifrån perfekt alltså, men oftast helt tillräckligt.

[Nerre]

Egentligen är det väl så att när man använder tiden som en slumpkälla så är det inte tiden som är slumpmässig utan användaren?

Om en användare systematiskt trycker på en knapp med en bestämd takt så kommer en tidsbaserat slumpgenerering att generera ett förutsägbart mönster.

[/mr]

Stämmer bra, det är användaren och inte tiden som är slumpkällan!

En klassisk programmeringslab är att dra random med tiden som källa. Insikten den laborationen syftar till är att systemtiden ändrar sig på ett förutsägbart sätt under programmets gång. Dvs, om man vet tiden vid ett tillfälle i koden kan man räkna ut vad tiden är i ett annat tillfälle.

Jajavisst, man får tidmäta vid externa "okända" händelser såsom användarinput eller externa enheters händelser, inte råka mäta programmets egen exekvering.

[Nerre]

Jag har ju haft det högteknologiska brädspelet Data Finans. Det kom med en "elektronisk" tärning, som jag som elektroniknörd dissekerade:)

Den var byggd med 74xx-kretsar vill jag minnas (drevs av ett 4,5 V ficklampsbatteri, jag byggde om den med ett laddningsbart 9 V-batteri från en slaktad Texas miniräknare och en 5 V regulator).

En oscillator på några Hz, själva "tärningen" var tre bitar från en räknare. Sen om aktiekursen gick upp eller ner indikerades av en lysdiod som man "kollade" med en separat knapp. Den växlade med klockfrekvensen (det såg man om man höll den knappen nedtryckt samtidigt som man "slog" tärningen).

Man lärde sig rätt snabbt att om man tryckte så kort man kunde på "slå"-knappen så kunde man få räknaren att bara stega ett steg.

Hade nog gått att "förbättra" genom att göra en debounce på knappen med RC-nät, med flera resistorer som "matas" från ett par av räknarens bitar så skulle man ju få en mer oförutsägbar debounce-tid.

[RoPa]

Ta bara två väl avskärmade bruskällor (det är där som radioaktivt sönderfall är så bra) som har hög bandbredd, kvantifiera dem med en komparator som är lika snabb åt båda hållen (hög/låg), 1-bit sampla dem båda och om A är hög, spar bit B annars kasta den, repetera.
Skifta in bitarna i en byte. Skapa 64K byte och gör en frekvens fördelnings kurva från 0 till 255, den bör "se rak ut" om än "knagglig".
Räkna antalet ettor och nollor som sparas, kontrollera hur nära 50% du hamnar vilket visar hur bra tröskelvärdet ligger i mitten av amplitud spannet på bruset.

Vill man ha bra slumptal får man vänta lite, det är som med god mat, tar tid att laga.
En Randomize funktion är snabbare men inte lika god... eller bra menar jag

[überfuzz]

Latency, minnes access, mellan olika kärnor i en fler kärnig processor tycks ofta vara slumpmässig.

[stoffe]

Jag har funderat på hur man på ett billigt och relativt enkelt sätt kan bygga en hårdvarubaserad slumptalsgenerator. Vilken princip skall man använda och vilken metod är bäst för utvärdering av resultaten? hur detekterar man avvikelser? Hur ofta behöver man få ut ett slumptal av hög kvalitet från enheten?

Detta hörde jag om på vetenskapsradion i P1 för några år sedan, en mycket bra slumpgenerator var tydligen 6 stycken uppställda lavalampor där en kamera kontinuerligt fotograferade händelseförloppet och själva bildfilen som blev blev ett mycket bra slumptal. Jag vet inte hur de skalade ner slumptalet till den storlek som önskades men något i den stilen var det.

[/mr]

Lavalampor må vara mer slumpartade än de flesta andra prylar i vår omgivning, men eftersom lavalampornas tillstånd är väldigt beroende av tillståndet en stund före, så skulle jag verkligen inte vilja kalla det "en mycket bra slumpgenerator". Inte bland de potentiella slumpgeneratorer man skulle leta bland i jakten på en mycket bra slumpgenerator. Om man inte bara är ute efter ett enda slumptal, eller har väääldigt mycket tid på sig mellan stunderna av slumptalsbehov.

[RoPa]

One technique is to run a hash function against a frame of a video stream from an unpredictable source. Lavarand used this technique with images of a number of lava lamps.

från http://en.wikipedia.org/wiki/Random_number_generation
Bilden på lavalamporna används alltså som en typ av seed om hash funktionen ses som en Randomize.

[superx]

Det här är ju spännande! Jag har byggt en usb-geiger-mätare för andra syften. Kanske borde skriva en slumpgeneratormjukvara till den också. Förslag på algoritmer?

[blueint]

Varje gång ett sönderfall sker så samplar du en räknare kopplad till en kristalloscillator. Sedan kan man använda energinivåer. Eller låta ett visst antal sönderfall vara kod för hur oscillatorn skall samplas och hashas osv..

[superx]

Och då tar man enbart en eller ett par av de minst signifikanta bitarna antar jag. Borde funka så länge som räknaren är snabb i förhållande till sönderfallstakten (förhoppningsvis inte ett svårt krav).

[blueint]

Eller så tar man en hash rakt av..

Se detta exempel:
> perl -e 'print "\x00\x00\x00\x00"; '| md5sum
f1d3ff8443297732862df21dc4e57262 -
> perl -e 'print "\x00\x00\x00\x01"; '| md5sum
f1450306517624a57eafbbf8ed995985 -

Man kan förstås använda tidigare värden som initialiseringsvektor för att förbättra resultatet ännu mer.

[superx]

Ja, men då måste man vara säker på att md5 är lämplig för detta. Det kanske den är, men det har ju dykt upp bakdörrar i liknande sammanhang tidigare. Det är ju lite för att slippa krångliga och svåröverskådliga algoritmer som man använder hårdvarugeneratorer.

[blueint]

md5 ska du nog inte använda. Den vart mest för att visa på principen.