Titta på slumptal med view_rnd

I Cryptech-projektet arbetar vi mycket just nu med att utveckla och testa olika entropikällor som kan användas för att driva slumptalsgeneratorn. En viktig del i arbetet är att kunna bedöma hur väl entropikällan fungerar – under normala förhållanden och när den är utsatt för försök till manipulation.

Det finns flera olika verktyg och standarder för att undersöka kvalitet på slumptal. Ett av det mest omfattande verktygen är Dieharder. Dieharder inkluderar en stor uppsättning av tester och tar lång tid att köra. Ett enklare och snabbare verktyg är Ent. Ent gör en skattning på mängd entropi per bit, försöker komprimera indatat, beräknar median-, och medelvärden m.m. Att använda Ent går mycket snsnabbt och ger en bra första skattning. Testar jag på en av mina entropikällor jag byggt inne i en FPGA får jag exempelvis:

pluttis:data js$ ent filtered_fpga_entropy_2014-06-10.bin
Entropy = 7.961751 bits per byte.

Optimum compression would reduce the size
of this 374387184 byte file by 0 percent.

Chi square distribution for 374387184 samples is 20168698.69, and randomly
would exceed this value less than 0.01 percent of the times.

Arithmetic mean value of data bytes is 127.5067 (127.5 = random).
Monte Carlo value for Pi is 3.079589263 (error 1.97 percent).
Serial correlation coefficient is -0.004758 (totally uncorrelated = 0.0).

Utifrån Ent verkar det ganska bra… Men ett ännu snabbare test är att faktiskt titta på de genererade värdena. Människan är ganska bra på att se mönstrer i bilder. För att snabbt ta en fil och omvandla den till en bild satte jah ihop verktyget view_rnd.

Programmet view_rnd är byggt i Python och använder PIL/Pillow för att skapa biblioteket. Genom att använda bytevärdena i källfilen som gråskalenivåer skapas bilder som ger en visuell representation av innehållet. Så här ser exempelvis bilden för datafilen som testades med Ent ovan ut:

Exempel på bild med entropi från FPGA.
Bild skapad med entropikälla inne i en FPGA.

Det syns inga tydliga regelbundna mönster. Däremot finns det lite bågar och punkter i bilden. Samtidigt kan mönster uppkomma bara igenom att indata organiserad i en 2D-struktur. Dimensionerna man väljer ger viss påverkan. I programmet gör jag det enkelt för mig och skapar kvadratiska bilder utifrån storleken på indatafilen. En sak man inte ser enkelt är generella nivåer, dvs om indatat spänner bara innehåller värden inom en del av värderymden [0..255]. Det ser man exempelvis på följande lilla bild där indata är programmet skälv som alltså är en textfil:

Figur skapad med view_rnd med view_rnd som indata.
Bild för källkoden till view_rnd.

För att ha något att testa mot inkluderar view_rnd även ett par testlägen där den antingen använder slumptalsgeneratorn i Python eller slumptalsgeneratorn (PRNG) beskriven i boken Numerical Recipies in C. Den senare generatorn genererar värden som innehåller en hel del mönster:

Bild skapad med data från slumptalsgeneratorn i Numerical Recipies in C.
Bild skapad med värden genererade med generatorn från Numerical Recipies in C.

Kasper Ingelvide har testat olika slumptalsgeneratorer i C++11:s standardbibliotek (pseudoslumptalsgeneratorer – PRNG). Kasper skrev ett program som genererade data med de olika generatorerna och skapade bilder med view_rnd. I flera av dessa synns klara mönster:

Bild för data skapad med mt19937
Data skapad med generatorn Mersenne Twister 19937.

Generatorn baserad på Mersenne Twister ger en fin figur utan uppenbarliga mönster.

Bild skapad med data från ranlux24.
Data skapad med generatorn ranlux24.

I bilden för ranlux24 finns tydliga ränder där värdena generellt har lägre nivå – en bias.

Tack till Kasper för att bygga programmet och testa view_rnd.

3 reaktioner på ”Titta på slumptal med view_rnd

  1. Gammal post men kan inte låta bli:
    Det kan vara bra att variera ”linjelängden” dvs bredden i bilden för att upptäcka mönster.

Kommentera

E-postadressen publiceras inte. Obligatoriska fält är märkta *