Dotaz: Měření entropie /dev/random

[mazlik]

Pěkné víkendové odpoledne,

měl bych dotaz ohledně měření entropie /dev/random, tedy když to nějak zkusím formulat česky lze změřit jak moc velký "chaos" vrací /dev/random? Respektive jak se vlastně taková entropie měří?

( napadá mě, měřit samozdřejmě četnost výskytu hodnot za nějaké časové obdoví a z toho dělat nějakou statistiku )

Odpovědi

[Martin Tůma]

Kromě testů, zda dává čísla s předpokládaným (rovnoměrným) rozdělením, což se testuje obyčejným chí² testem, se používají ještě různé další testy. Například americká vláda požaduje pro kryptografické moduly toto:

• test četnosti jedniček
• poker test
• test úseku stejných znaků
• test nejdelšího runu

Více viz příslušná norma.

[karel]

Pro kryptografické účely se náhodná data proženou nějakou "testovací baterií" (která používá výše zmíněné statistické testy) a třeba zrovna Maurer & Coronův univerzální test spočítá entropii na 1 bit.

Výhoda/nevýhoda? /dev/random je v tom, že pokud je entropie příliš malá, generátor nic negeneruje, což se dá vyřešit třeba připojením externího zdroje šumu, třeba ze zvukovky...

[Michal Kubeček]

Kdysi jsem viděl článek o metodě, která umožňuje skutečně změřit entropii, ale bylo to dost komplikované a těch dat bylo potřeba dost značné množství. Takže v praxi se testují spíš jen určité základní vlastnosti, které by měl dobrý generátor mít, viz předchozí odpovědi.

[pht]

Nestačilo by vzít nějaký vzorek (třeba 100B) a spočítat na něm entropie všech řádů až do N/2 a porovnat je s max. entropií?

[Michal Kubeček]

Co si pamatuji, bylo to o dost komplikovanější, ale už je to tak deset let, takže detaily si nepamatuji. Jen vím, že to tam tenkrát prezentovali jako dost revoluční objev (i když s trochu problematickým praktickým využitím), takže bych se divil, kdyby to šlo nějak výrazně snáze.

[graviton]

Pěkná utilita je například ent. Mám dojem, že u /dev/random dat to ukazovalo poněkud nenulovou sériovou korelaci. Jako ideální náhodná data vycházely soubory šifrované gnupg nebo komprimované lzma...

[jehovista]

Tak ja v tom vidim predevsim jeden problem a to je fakt, ze nikdy neziskas cely soubor dat. Pokud ale z randomu cucnes treba mega dat, tak uz v tom snad zadny problem neni. Pak si jen urcis, co pokladas za atomarni jev(bit/byte) a entropii spocitas podle definice. http://en.wikipedia.org/wiki/Entropy_(information_theory)#Definition Tohle je zakladni definice informacni entropie, ale je dost dobre mozne, ze te vlastne zajima uplne neco jineho. Je to jen takovy nahodny napad, nebo ma ten dotaz aplikacni smysl?

[mazlik]

Diky vsem za nasmerovani, prostudoval jsem nejake materialy a pustim se do prace. Diky.

[karel]

Pro představu přikládám analýzu dvou 10MB souborů dat z výstupu /dev/random (pomocí testovací baterie VANAD 2.3, dílo to RNDr. Tesaře)

První soubor:

Testovany soubor : 1.rand
Delka v bytech   =    10000000
Delka v bitech   =    80000000
Byty zpracovavany ZDOLA

  TEST FREKVENCE
Relativni cetnost 1 = 0.50001021
Testovane epsilon   = 0.0005590170
Statistika =      0.1827  Dist. = 0.572478
HODNOCENI TESTU = VYHOVUJE    (Trestne body =   0)

  TEST N-TIC
 2-tice  Stat =      1.5764  Dist. = 0.335249
 3-tice  Stat =      5.8954  Dist. = 0.447990
 4-tice  Stat =      7.8685  Dist. = 0.071054
 5-tice  Stat =     21.5010  Dist. = 0.101938
 6-tice  Stat =     54.1474  Dist. = 0.221008
 7-tice  Stat =    116.4393  Dist. = 0.261149
 8-tice  Stat =    211.4754  Dist. = 0.021723
 9-tice  Stat =    563.7871  Dist. = 0.947194
10-tice  Stat =   1056.6584  Dist. = 0.773616
11-tice  Stat =   1991.2987  Dist. = 0.192662
12-tice  Stat =   4143.9046  Dist. = 0.707334
13-tice  Stat =   8024.9904  Dist. = 0.096684
14-tice  Stat =  16592.2630  Dist. = 0.875925
15-tice  Stat =  32840.3084  Dist. = 0.613616
HODNOCENI TESTU = VYHOVUJE    (Trestne body =   0)

  AUTOKORELACNI TEST
Maximalni posun =  1024
Velikost posunu =   1 bit 
Kriticka hodnota pro Kolmogorova 0.05  = 0.04227
Kriticka hodnota pro Kolmogorova 0.01  = 0.05069
Kriticka hodnota pro Kolmogorova 0.001 = 0.06074
Smirnov Minus  = 0.01246  Dist. = 0.278157
Smirnov Plus   = 0.01681  Dist. = 0.445511
Kolmogorov     = 0.01681
Maximum: Posun =    820 Cetnost shod = 0.500167  Dist. = 0.99863
HODNOCENI TESTU = VYHOVUJE    (Trestne body =   0)

  TEST ROZDELENI SERII
Celkovy pocet serii   =     39997512
Pocet stupnu volnosti = 20
Hodnota Statistiky    =    17.77628    Dist. = 0.397857
L =  1 Celkem =     19996075 Teorie =   19998756.00
L =  2 Celkem =      9996953 Teorie =    9999378.00
L =  3 Celkem =      5005097 Teorie =    4999689.00
L =  4 Celkem =      2500293 Teorie =    2499844.50
L =  5 Celkem =      1249603 Teorie =    1249922.25
L =  6 Celkem =       624682 Teorie =     624961.13
L =  7 Celkem =       312416 Teorie =     312480.56
L =  8 Celkem =       156653 Teorie =     156240.28
L =  9 Celkem =        77958 Teorie =      78120.14
L = 10 Celkem =        38910 Teorie =      39060.07
L = 11 Celkem =        19403 Teorie =      19530.04
L = 12 Celkem =         9790 Teorie =       9765.02
L = 13 Celkem =         4808 Teorie =       4882.51
L = 14 Celkem =         2423 Teorie =       2441.25
L = 15 Celkem =         1174 Teorie =       1220.63
L = 16 Celkem =          653 Teorie =        610.31
L = 17 Celkem =          298 Teorie =        305.16
L = 18 Celkem =          166 Teorie =        152.58
L = 19 Celkem =           77 Teorie =         76.29
L = 20 Celkem =           42 Teorie =         38.14
L > 20 Celkem =           38 Teorie =         38.14
HODNOCENI TESTU = VYHOVUJE    (Trestne body =   0)

  UNIVERZALNI TEST - Maurer & Coron

Velikost bloku L  =         12
Velikost useku Q  =      65536
Velikost useku K  =    6601130

Statistika Tu     =     11.9998314
Tu-normalizovana  =     -0.3743706
Dist.             =       0.354064
ENTROPIE na 1 bit =      0.9999859

HODNOCENI TESTU   = VYHOVUJE    (Trestne body =   0)


Celkovy pocet provedenych testu  = 18
Redukovany pocet trestnych bodu  = 0
CELKOVE HODNOCENI = 1 : VYHOVUJE bez vyhrad

***************************************************

Druhý soubor:

Testovany soubor : 2.rand
Delka v bytech   =    10000000
Delka v bitech   =    80000000
Byty zpracovavany ZDOLA

  TEST FREKVENCE
Relativni cetnost 1 = 0.49999610
Testovane epsilon   = 0.0005590170
Statistika =     -0.0698  Dist. = 0.472190
HODNOCENI TESTU = VYHOVUJE    (Trestne body =   0)

  TEST N-TIC
 2-tice  Stat =      0.4210  Dist. = 0.064122
 3-tice  Stat =      4.6035  Dist. = 0.291773
 4-tice  Stat =     12.1206  Dist. = 0.330122
 5-tice  Stat =     40.9609  Dist. = 0.891233
 6-tice  Stat =     51.8824  Dist. = 0.159823
 7-tice  Stat =    183.1973  Dist. = 0.999184
 8-tice  Stat =    240.4279  Dist. = 0.264899
 9-tice  Stat =    482.5633  Dist. = 0.187911
10-tice  Stat =    937.3734  Dist. = 0.026573
11-tice  Stat =   2052.6498  Dist. = 0.539286
12-tice  Stat =   4014.1322  Dist. = 0.186155
13-tice  Stat =   8198.5469  Dist. = 0.525576
14-tice  Stat =  16145.2034  Dist. = 0.094017
15-tice  Stat =  32617.0846  Dist. = 0.279641
HODNOCENI TESTU = NEVYHOVUJE  (Trestne body =   6)

  AUTOKORELACNI TEST
Maximalni posun =  1024
Velikost posunu =   1 bit 
Kriticka hodnota pro Kolmogorova 0.05  = 0.04227
Kriticka hodnota pro Kolmogorova 0.01  = 0.05069
Kriticka hodnota pro Kolmogorova 0.001 = 0.06074
Smirnov Minus  = 0.00445  Dist. = 0.042532
Smirnov Plus   = 0.02763  Dist. = 0.794420
Kolmogorov     = 0.02763
Maximum: Posun =    612 Cetnost shod = 0.499794  Dist. = 0.00012
HODNOCENI TESTU = VYHOVUJE    (Trestne body =   0)

  TEST ROZDELENI SERII
Celkovy pocet serii   =     39995726
Pocet stupnu volnosti = 20
Hodnota Statistiky    =    21.50049    Dist. = 0.631781
L =  1 Celkem =     19992602 Teorie =   19997863.00
L =  2 Celkem =     10001192 Teorie =    9998931.50
L =  3 Celkem =      5000370 Teorie =    4999465.75
L =  4 Celkem =      2501797 Teorie =    2499732.88
L =  5 Celkem =      1250973 Teorie =    1249866.44
L =  6 Celkem =       624184 Teorie =     624933.22
L =  7 Celkem =       312755 Teorie =     312466.61
L =  8 Celkem =       156234 Teorie =     156233.30
L =  9 Celkem =        77600 Teorie =      78116.65
L = 10 Celkem =        38841 Teorie =      39058.33
L = 11 Celkem =        19444 Teorie =      19529.16
L = 12 Celkem =         9747 Teorie =       9764.58
L = 13 Celkem =         4996 Teorie =       4882.29
L = 14 Celkem =         2505 Teorie =       2441.15
L = 15 Celkem =         1201 Teorie =       1220.57
L = 16 Celkem =          623 Teorie =        610.29
L = 17 Celkem =          332 Teorie =        305.14
L = 18 Celkem =          157 Teorie =        152.57
L = 19 Celkem =           90 Teorie =         76.29
L = 20 Celkem =           43 Teorie =         38.14
L > 20 Celkem =           40 Teorie =         38.14
HODNOCENI TESTU = VYHOVUJE    (Trestne body =   0)

  UNIVERZALNI TEST - Maurer & Coron

Velikost bloku L  =         12
Velikost useku Q  =      65536
Velikost useku K  =    6601130

Statistika Tu     =     11.9995188
Tu-normalizovana  =     -1.0683305
Dist.             =       0.142686
ENTROPIE na 1 bit =      0.9999599

HODNOCENI TESTU   = VYHOVUJE    (Trestne body =   0)


Celkovy pocet provedenych testu  = 18
Redukovany pocet trestnych bodu  = 6
CELKOVE HODNOCENI = 4 : NEVYHOVUJE zavazne

***************************************************

[graviton]

20 MB z /dev/random? To mohlo trvat tak měsíc než se to přečetlo, ne? (pokud vím tak /dev/random na linuxu dá zhruba megabajt za den)

[pht]

asi hodně jezdil myší...

[Ash]

Při souběžném generování na dvou mašinách to máš ze 10 dní :)

[Karel]

/dev/random/ dává skutečně pár B/s a když jsem to kdysi měřil, tak jsem rozhodně neměl čas čekat...

Pomocí randomsound a vlastního šumu zvkukovky se to o poznání urychlí

(tu aplikaci randomsound jsem ale nijak podrobně nepitval, měla by jen přidávat data do zdrojového poolu, ze kterého bere /dev/random, takže by snad neměla zhoršovat náhodnost generovaných dat