Satunnaislukugeneraattorin uusi käsittely

Kirjoitin aiemmin postissa http://moijari.com/?p=62 genbyte ja genbytes rutiineihin perustuvasta satunnaisbittigeneraattorista, joka tekee satunnaislukuja kellon perusteella. Satunnaislukugeneraattori perustuu vaihteluihin, joita tapahtuu luettaessa kelloa toistuvasti. (rutiinipari on oma keksintöni)

HUOM: Tätä ei tällä tiedolla kannata käyttää ainoana satunnaislukugeneraattoreina, vaan kannattaa aina summata useampia generaattoreita xor:aamalla tai tiivistefunktiolla. Tietysti on mukavaa, jos joku summattavista generaattoreista on omassa ohjelmassa…

HUOM2: Ilmeisesti b:n arvo 20 on liian pieni 64 merkin puskurille, se tuottaa duplikaattipuskureita. Kokeiluissani b:n arvolla 100 ei duplikaattipuskureita ole tullut 64 merkkisellä puskurilla (muutamilla miljoonilla ajokerroilla). Tavoite on saada b:n arvo määriteltyä siten, että satunnaisbittien määrä riittää koko puskuriin, ja että kuitenkin ajoaika on kohtuulinen (tuplien laskuohjelma lopussa). Edit: Onko niin, että jos satunnaislukugeneraattori alkaa tuottamaan tuplia ~1048576 suorituskerran jälkeen, inputista (tässä kellodatasta) saadaan ~20 (2^20=1048576) bittiä satunnaisuutta. ja jos satunnaisuutta halutaan 40 bittiä, lisätään kierroksia kaksinkertaiseksi (alkuperäinen b on esim 30, uusi b on 60). Pondering..

summary: this random bit generator is based on fluctuations on bit stream reading clock repeatedly. post tries to show what these fluctuations are, and how they are used to create random bit stream. post gives code that i created in these couple of days i have been studying generator. generator itself was invented by me in ~november 2013. code for the generator is in next two functions, and the rest of the post tries to show how it works. i am not totally confident that the generator is good enough, but confident enough to write this summary in english. language of the post is finnish, of course.

Rutiinit ovat seuraavassa, ensimmäisen rutiinin nimi on muutettu ja “turhat” bitit on otettu pois (millisekunnit, minuutit, tunnit, päivät, kuukaudet… oli aiemmassa versiossa ympätty yhteen merkkiin). Tämä on helpompi selittää ja ymmärtää, siinä on vain millisekuntien alimmat 8 bittiä:

/*
 * (c)2013-2016 Jari Kuivaniemi, Kaikki oikeudet pidätetään!
 */
unsigned char clockbyte()
{
  unsigned char byte;
  unsigned long usec,sec;

  struct timeval tv;

  gettimeofday(&tv,NULL);

  usec=tv.tv_usec;
  sec=tv.tv_sec;

  byte=(usec&0xff);

  return(byte);
}

genbytes(int size, unsigned char *buffer, int b)
{
  int c,d,e,f;
  unsigned char byte;

  f=0;
  for(c=0;c<8*b;c++) {
    for(d=0;d<size;d++) {
      byte=clockbyte();
      e=buffer[d];
      e=((e&0x80)>>7) | ((e&0x7f)<<1);
      e=e^byte;
      buffer[d]=e;
    }
    for(d=0;d<size;d++) { /* see rc4 */
      f=(f+buffer[d])%size;
      e=buffer[d];
      buffer[d]=buffer[f];
      buffer[f]=e;
    }
  }
}

Seuraavilla testirutiineilla voidaan mielestäni havainnollistaa näitä vaihteluita:

test_timer1()
{
  int c,size;
  unsigned char *buffer;

  size=buffer_size*8*bytes_per_bit;

  if((buffer=malloc(size))==NULL) {
    fprintf(stderr,"jarik2: cannot allocate testing buffer");
  }

  for(c=0;c<size;c++) {
    buffer[c]=clockbyte();
  }

  for(c=0;c<size;c++) {
    if(c>0 && c%64==0)
      fprintf(stdout,"\n");
    fprintf(stdout," %3d",buffer[c]);
  }

  free(buffer);
}

Edellisen rutiinin size lauseke sisältää kaikki puskurin laskemiseen tarvittavat merkit, eli siis näemme kaikki merkit, jotka vaikuttavat puskuriin. (buffer size on näissä testeissä 64 ja b eli bytes per bit on esimerkiksi 20)

Seuraavana edellisen rutiinin osittainen tuloste merkki merkiltä. tämä lähinnä kertoo, millaista suoraan kellolta tulevat merkit näyttävät: (huomaa että esimerkiksi 1,3,5,6,8 jne puuttuvat, tuplia tässä ei ole hmm…)

 246 248 251 253 255   2   4   7   9  10  11  12  13  14  15  16  17
  18  19  20  21  22  23  24  25  26  27  28  29  30  31  32  33  34
  35  36  38  39  40  41  42  43  44  45  46  47  48  49  50  51  52
  53  54  55  56  57  58  59  60  61  62  63  64  65  66  67  68  69
  70  71  72  73  74  75  76  77  78  79  80  81  82  84  85  86  87
  88  89  90  91  92  93  94  95  96  97  98  99 100 101 102 103 104
 105  97  98  99 100 101 102 103 104 105 106 107 108 109 110 111 112
 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129
 130 131 132 133 134 135 136 137 139 140 141 142 143 144 145 146 147
 148 149 150 151 152 153 154 155 156 157 158 159 160 161 162 163 164
 165 166 167 168 169 170 171 172 173 174 175 176 177 178 179 180 181
 182 183 184 185 186 187 188 189 190 192 193 194 195 196 197 198 199
 200 201 202 203 204 205 206 207 208 209 210 211 212 213 214 215 216
 217 218 219 220 221 222 223 224 225 226 227 228 229 230 231 232 233
 234 235 236 237 239 240 241 242 243 244 245 246 247 248 249 250 251
 252 253 254 255   0   1   2   3   4   5                                                                                                                
...

Ohjelma kaksi jakaa tulosteen riveihin, siten että rivin pienin numero aloittaa aina rivin.

test_timer2()
{
  int c,size,start;
  unsigned char *buffer;

  size=buffer_size*8*bytes_per_bit;

  if((buffer=malloc(size))==NULL) {
    fprintf(stderr,"jarik2: cannot allocate testing buffer");
  }
  for(c=0;c<size;c++) {
    buffer[c]=clockbyte();
  }

  start=0;
  /* same as test1 routine except cr in between largest and smallest number.                                                                    
   */
  for(c=0;c<size;c++) {
    if(start==1 && buffer[c]<buffer[c-1])
      fprintf(stdout,"\n");
    fprintf(stdout," %3d",buffer[c]);
    start=1;
  }
  free(buffer);
}

Tämä versio on hiukan muokattu edellisestä(osa tulosteesta). Nolla on aina samalla kohdalla, tässä voi jo vertailla eri jonoja hakemalla puuttuvia ja tuplia. (Puuttuvat ja tuplat antavat generaattorin satunnaisuuden)

   0   1   2   3   4   5   6   7   8   9  10  11  12  13  14  15  16  17  18  19  20  21  22  23  24  25  26  27                                
  28  29  30  31  32  33  34  35  36  37  38  39  40  41  43  44  45  46  47  48  49  50  51  52  53  54  55  56                                
  57  58  59  60  61  62  63  64  65  66  67  68  69  70  71  72  73  74  75  76  77  78  79  80  81  82  83  84                                
  85  86  87  88  90  90  92  93  94  95  96  97  98  99 100 101 102 103 104 105 106 107 108 109 110 111 112 113                                
 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 130 131 132 133 134 135 136 138 139 140 141 142                                
 143 144 145 146 147 148 149 150 151 152 153 154 155 156 157 158 159 160 161 162 163 164 165 166 167 168 169 170                                
 171 172 173 174 175 176 177 178 179 180 181 182 183 184 185 186 187 188 190 191 192 193 194 195 196 197 198 199                                
 200 201 202 203 204 205 206 207 208 209 210 211 212 213 214 215 216 217 218 219 220 221 222 223 224 225 226 227                                
 228 229 230 231 232 233 234 235 236 237 238 239 240 241 242 243 244 245 246 248 249 250 251 252 253 254 255                                    
   0   1   2   3   4   5   6   7   8   9  10  11  12  13  14  15  16  17  18  19  20  21  22  23  24  25  26  27                                
  28  29  30  31  32  33  34  35  36  37  38  39  40  41  42  44  44  46  47  48  49  50  51  52  53  54  55  56                                
  57  58  59  60  61  62  63  64  65  66  67  68  69  70  71  72  73  74  75  76  77  78  79  80  81  82  83  84                                
  85  86  87  88  89  90  91  92  93  94  95  96  97  98  99 100 101 102 104 104 106 107 108 109 110 111 112 113                                
 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 130 131 132 133 134 135 136 137 138 139 140 141                                
 142 143 144 145 146 147 148 149 150 151 154 156 158 161 164 166 168 171 173 176 178 180 183 185 188 190 193 195                                
 197 199 200 201 202 203 204 205 206 207 208 209 210 211 212 214 214 216 217 218 219 220 221 222 223 224 225 226                                
 227 228 229 230 231 232 233 234 235 236 237 238 239 240 241 242 243 244 245 246 247 248 249 250 251 252 253 254                                
 255
...                                                                                                                                            

Kolmannessa versiossa tulostetaan(osa listasta) merkeistä vain 4 alinta bittiä:

test_timer3()
{
  int c,size;
  unsigned char *buffer;

  size=buffer_size*8*bytes_per_bit;

  if((buffer=malloc(size))==NULL) {
    fprintf(stderr,"jarik2: cannot allocate testing buffer");
  }

  /* Same as previous routine except only low 4 bits printed. */
  for(c=0;c<size;c++) {
    buffer[c]=clockbyte()&0x0f;
  }

  for(c=0;c<size;c++) {
    if(c>0 && c%64==0)
      fprintf(stdout,"\n");
    fprintf(stdout," %2d",buffer[c]);
  }

  free(buffer);
}

 10 13 15  1  4  6  9 11 14  0  2  5  7  9 10 11 12 13 14 15  0  1  2  3  4  5  7  7  9 10 11 12 13 14 15  0  1                                 
  2  3  4  5  6  7  8  9 10 11 12 13 14 15  0  1  2  3  5  6  7  8  9 10 11 12 13 14 15  0  1  2  3  4  5  6  7                                 
  8  9 10 11 12 13 14 15  0  1  2  3  4  5  6  7  8  9 10 11 13 14 15  0  1  2  3  4  5  6  7  8  9 10 11 12 13                                 
 14 15  0  1  2  3  4  5  6  7  8  9 10 11 12 13 14  0  0  2  3  4  5  6  7  8  9 10 11 12 13 14 15  0  1  2  3                                 
  4  5  6  7  8  9 10 11 12 13 14 15  0  1  2  3  4  5  7  8  9 10 11 12 13 14 15  0  1  2  3  4  5  6  7  8  9                                 
 10 11 12 13 14 15  0  1  2  3  4  5  6  7  8  9 10 11 12 13 14 15  0  1  2  4  5  6  7  8  9 10 11 12 13 14 15                                 
  0  1  2  3  4  5  6  7  8  9 10 11 12 13 14 15  0  1  2  3  4  5  6  7  8  9 10 11 12 13 14 15  0  2  2  4  5                                 
  6  7  8  9 10 11 12 13 14 15  0  1  2  3  4  5  6  7  8  9 10 11 12 13 14 15  0  1  2  3  4  5  6  7  8  9 10                                 
 11 12 13 14 15  0  2  3  4  5  6  7  8  9 10 11 12 13 14 15  0  1  2  3  4  5  6  7  8  9 10 11 12 13 14 15  0                                 
  1  2  3  4  5  6  7  8  9 10 11 12 13 14  0  1  2  3  4  5  6  7  8  9 10 11 12 13 14 15  0  1  2  3  4  5  6                                 
  7  9 10 12 13 14 15  0  1  2  3  4  5  6
...

Ja neljännessä versiossa vaihdetaan taas riviä numerosasrjojen välissä:

test_timer4()
{
  int c,size,start;
  unsigned char *buffer;

  size=buffer_size*8*bytes_per_bit;

  if((buffer=malloc(size))==NULL) {
    fprintf(stderr,"jarik2: cannot allocate testing buffer");
  }

  for(c=0;c<size;c++) {
    buffer[c]=clockbyte()&0x0f;
  }

  start=0;
  for(c=0;c<size;c++) {
    if(start==1 && buffer[c]<buffer[c-1])
      fprintf(stdout,"\n");
    fprintf(stdout," %2d",buffer[c]);
    start=1;
  }

  free(buffer);
}

Tässä on testin 4 osatuloste. Tässä voidaan selvästi havaita puuttuvat ja kaksois merkit.

  0  1  2  3  4  5  6  7  8  9 10 11 12 13 14 15                                                                                                
  1  1  3  4  5  6  7  8  9 10 11 12 13 14 15                                                                                                   
  0  1  2  3  4  5  6  7  8  9 10 11 12 13 14 15                                                                                                
  0  1  2  3  4  5  6  7  8  9 10 11 12 13 14                                                                                                   
  0  1  2  3  4  5  6  7  8  9 10 11 12 13 14 15                                                                                                
  0  1  2  3  4  5  6  7  8  9 10 11 12 13 14 15                                                                                                
  0  1  2  3  4  5  6  7  8  9 11 11 13 14 15                                                                                                   
  0  1  2  3  4  5  6  7  8  9 10 11 12 13 14 15                                                                                                
  0  1  2  3  4  5  6  7  8  9 10 11 12 13 14 15                                                                                                
  0  1  2  3  4  6  7  8  9 10 11 12 13 14 15                                                                                                   
  0  1  2  3  4  5  6  7  8  9 10 11 12 13 14 15                                                                                                
  0  1  2  3  4  5  6  9 12 14                                                                                                                  
  1  3  6  8 10 13 15                                                                                                                           
  2  4  7  9 12 14                                                                                                                              
  1  3  5  6  7  8  9 10 11 12 13 14 15                                                                                                         
  0  1  2  3  4  5  6  7  8  9 10 11 12 13 14 15                                                                                                
  0  1  2  3  4  6  6  8  9 10 11 12 13 14 15                                                                                                   
  0  1  2  3  4  5  6  7  8  9 10 11 12 13 14 15                                                                                                
  0  1  2  3  4  5  8 10 13 15                                                                                                                  
  2  4  6  9 11 14                                                                                                                              
  0  3  5  7  8  9 10 11 12 13 14 15                                                                                                            
  0  1  2  3  5  7 10 12 15                                                                                                                     
  1  4  6  8 11 13                                                                                                                              
  0  2  4  7  9 12 14
...

Seuraavassa on osatuloste rutiinin pääohjelmasta (genbytes), joka lukee näitä lukuja ja muodostaa puskuriin satunnaisbittijonon:

Tässä ensimmäisessä tietueessa generaattori on aloitustilassa, sillä on tyhjä puskuri, joka on täynnä nollamerkkejä. Todellisuudessa generaattorin alkuarvo voidaan täyttää kutsuvassa ohjelmassa.

genbytes input                                                                                                                                  
00000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000

Tässä toisessa tietueessa (genbytes():in ensimmäisen luupin jälkeen) näemme selvästi kellon luvun tuoman rakenteen, merkit alkavat 0xb0 merkistä ja loppuvat 0xdf merkkiin (huomaa puuttuvat b1,b2 ja tuplat b4, b7, bb, be jne). Tässä vielä ensimmäinen luuppi:

for(d=0;d<size;d++) { /* Käydään läpi koko puskuri */
  byte=clockbyte();   /* Luetaan kello */
  e=buffer[d];        /* Luetaan vuorossa oleva merkki */
                      /* Siirretään ylin bitti alas ja 7 alabittiä askel ylös */
  e=((e&0x80)>>7) | ((e&0x7f)<<1);  
  e=e^byte;           /* xorataan kellomerkillä */
  buffer[d]=e;        /* laitetaan takaisin samaan paikkaan puskuriin */
}
genbytes after adding clock bits                                                                                                                
b0b3b4b4b5b6b7b7b8b9b9babbbbbcbdbebebfc0c0c1c2c3c3c4c5c5c6c7c8c8c9cacacbcccdcdcecfcfd0d1d2d2d3d4d5d5d6d7d7d8d9d9dadbdcdcdddededff

Kolmannessa rivissä genbytes rutiinin jälkimmäinen kappale sekoittaa merkkien järjestyksen merkkien perusteella: (merkit ovat vielä väliltä 0xb0-0xdf). Tässä vielä toinen luuppi:

for(d=0;d<size;d++) {   /* Käydään koko puskuri läpi merkki merkiltä */
  f=(f+buffer[d])%size; /* f:ään lisätään puskurin tämänhetkinen merkki mod size */
  e=buffer[d];          /* vaihdetaan d:s(tämänhetkinen) ja f:s merkki */
  buffer[d]=buffer[f];
  buffer[f]=e;
}
genbytes after mixing bytes                                                                                                                     
ddcbb4bac9d9d2c8c6c1bcc3b4dad7d3c4d0b8bfc0c5b7c3dec7becab3bdcadbb7b0d4dcbbd8c2b6c8b9c5d1cfd6d2b9cecdded9d5d7dcbecfdfccbbb5cdd5c0

Huomaa että toisessa tietueessa alin bitti on jonoina nollia ja ykkösiä, mutta kun puskurin “sekoitus” tehdään (kolmannella rivillä) nollien ja ykkösten järjestys muuttuu satunnaiseksi. Puskurin pituuden pitää olle riittävän pitkä (jos aloituspuskuri on tyhjä), ettei puskurin riville tule pelkästään nollia tai ykkösiä. (nollien lukumäärä rivillä tilastollisesti ~ykkösten lukumäärä).

Neljännessä rivissä lisäämme toisen kellorivin tulosteeseen. Huomaa, että kun nyt lisäämme puskuriin uuden rivin sitä ei kirjoiteta samassa järjestyksessä kun edellisellä kierroksella, edellisen kierroksen merkit on sekoitettu satunnaisesti. Sekoituksessa käytetään kellon tuottamia tämän hetkisiä merkkejä (siis puskurin sisältöä).

Huomaa lisäksi että yhden merkin bitit on rollattu ylöspäin, joten kellon tarkin bittit tapaa itseasiassa ensimmäisen rivin ylimmän bitin, ja ensimmäisessä kierroksessa lisätty kellobitti on nyt toisessa bitissä.

genbytes after adding clock bits                                                                                                                
cae51a01e7c6d3e7fafb00fe13ced4dbf4df0f00010bee053e0cf910e2fd123fe7e82333fc3d08e01ffc04330e3f37e0090f28253c3821e4062502ebf706351f

Viidennessä rivissä sekoitamme bitit taas uuteen järjestykseen, ja jatkamme kierroksia, kunnes kellon alin bitti on koskenut kaikkiin puskurin bitteihin.

genbytes after mixing bytes                                                                                                                     
3fe8fc0801fbfee7f7101f06e7122823df3df937023313383c0625ee051ae53e09d3cee035ebc61ff425e4fcd40c0421fd00ca0edbe00b0fe23fe70ffa013300                
genbytes after adding clock bits                                                                                                                
4ae4cf2735cfc4f6d51b0230f21a6e79ff3bb22c472562353e4a0d95427d813759ebd08c2498dd6eb8189baafd4d5d14ac57cd45ed9b4d4299239140aa620761                
genbytes after mixing bytes                                                                                                                     
623723599881ddcf27354a02991ac4d0f2f6b279ac0d5d6e07cf479bfd18aaeb4a61d52c457d30b84d254257ed6e3e421b14ff3b408caacd24e43591954d629b                
genbytes after adding clock bits                                                                                                                
369db247c4f54c68b6936efec8c8755c1b129af2581bb8df0a9b8b31fd375dde9dc8a05386f76d7f955a94bfc9ce6f90233de96197014c8152d2763f3684db28                
genbytes after mixing bytes                                                                                                                     
c49a90ce1bb63f536ec9c80a1b7ffd61f2df3d315a1236819397d29d9df79b76688bbf474cb84cfe3784865c01f56fc82895e952b2db6da0de3675c8235d9458                
genbytes after adding clock bits                                                                                                                
2685902f84deca13692526a38e4741785e03c6df0a9bd3c3e6ee67f8ff2bf22a16d0b74651bb5336a2c4c076cd3b0e4082f90070b0620c966ab4334b9c61f56c                
genbytes after mixing bytes                                                                                                                     
f52ae67640cac3c0d06a7061693b0e90a22b4678d3f84bb02fde008485c4b7a35e26475113bb25b4c6ff8e0c6cee9bf91696035333419c26f2df826267cd360a                
genbytes after adding clock bits                                                                                                                
853bbd9df1e7f4f2d5a196b4a50e64583f2cf78cda8ce81e213d818b890aebc339ca0925aefec3e3067391955653b863bdbc9435f516acda73289d5c5701f78f                
genbytes after mixing bytes                                                                                                                     
910e3f815721e82c732528caf794da89a553da7309955caeebd5f13df71ebd3556f2b4e38fa10a1606acc3859d9d3bbdf596398bf4fe6358bce7c3b864018c8c                
genbytes after adding clock bits                                                                                                                
0e32502c9e73e06ad57964a0da1f822b739f8fdc29178560e994dc3aae7e3929e8a12c8158045c654513cc4077763835a47d2246bbae95e42c9ad126905a4043                
genbytes after mixing bytes                                                                                                                     
7d136a76bb50dc5a26a0354595642b732c04ae1740393a2c909eae82dc0e5c9a77e4e9811f40a4d53879a129d17e43cc6094222c32584665e029858f9fdae873                
genbytes after adding clock bits                                                                                                                
10cc3f009a4d575ba3b19b78d93ba212adfeabd9788b8da2dac6a1f847e24735eec8d1003d844cae76f54b5aaaf68c92cc2449566bbf9cdbd340180b2ba0c7f1                
genbytes after mixing bytes                                                                                                        
c700b13f00785b5a12fe3badf8189a928ba384cca1cce2aa0b5678a24deea2aec82bdb353d768d576b4747f68cbf4cd94b9c9bd9a040f5da24d3d1c610f1ab49                

Edellinen rivi on viimeinen rivi, kuten se olisi tulostettu genbytes ohjelman b arvolla 1. Lisäämällä b:n arvoa voidaan tehdä useampia kahdeksan bitin kierroksia. Itse olen ajatellut, että kellodatassa olisi bitin verran tietoa kahtakymmentä byteä kohti, eli rutiinia ajettaisiin b:n arvolla 20 (Edit: HUOM2). Generaattorissa kaikki luetut kellomerkit vaikuttavat lopullisen puskurilliseen eli jos haluat saada puskurin sisällön ilman sitä (sisältöä) joudut arvaamaan kaikki tuplat ja puuttuvat merkit ajoajankohdan lisäksi.

Edellinen esimerkki on laadittu melko hitaalla laitteella (raspberry pi). Nopeammalla laitteella tulee enemmän tuplia ja vähemmän puuttuvia. Itseasiassa tässä on vielä lopuksi testi nopeampaa laitetta varten:

test_timer5()
{
  int c,size,lastbits,countbits;
  unsigned char *buffer;

  size=buffer_size*8*bytes_per_bit;

  if((buffer=malloc(size))==NULL) {
    fprintf(stderr,"jarik2: cannot allocate testing buffer");
  }

  for(c=0;c<size;c++) {
    buffer[c]=clockbyte()&0xf;
  }

  lastbits=-1;
  for(c=0;c<size;c++) {
    if(lastbits==-1) {
      lastbits=buffer[c];
      countbits=1;
    } else if(lastbits!=buffer[c]) {
      fprintf(stdout," %d(%d)",countbits,lastbits);
      if(lastbits>buffer[c]) {
        fprintf(stdout,"\n");
      }
      lastbits=buffer[c];
      countbits=1;
    } else if(lastbits==buffer[c]) {
      countbits++;
    }
  }
  if(c>0)
    fprintf(stdout," %d(%d)",countbits,lastbits);
  fprintf(stdout,"\n");

  free(buffer);
}

Seuraavassa testiohjelman 5 osatuloste: se tulostaa jokaisesta lukemasta määrän ja numeron, esimerkiksi 2(3) tarkoittaa kaksi kappaletta arvoa 3. Erillisten arvojoukkojen välissä on cr.

 1(0) 1(1) 1(2) 1(3) 1(4) 1(5) 1(6) 1(7) 1(8) 1(9) 1(10) 1(11) 1(12) 1(13) 1(14) 1(15)                                                          
 1(0) 1(1) 1(2) 1(3) 1(4) 1(5) 1(6) 1(7) 1(8) 1(9) 1(10) 1(11) 1(12) 1(13) 1(14) 1(15)                                                          
 1(0) 1(1) 1(2) 1(4) 1(5) 1(6) 1(7) 1(8) 1(9) 1(10) 1(11) 1(12) 1(13) 1(14) 1(15)                                                               
 1(0) 1(1) 1(2) 1(3) 1(4) 1(5) 1(6) 1(8) 1(9) 1(10) 1(11) 1(12) 1(13) 1(14) 1(15)                                                               
 1(0) 1(1) 1(2) 1(3) 1(4) 1(5) 1(6) 1(7) 1(8) 1(9) 1(10) 1(11) 1(12) 1(13) 1(14) 1(15)                                                          
 1(0) 1(1) 1(2) 1(3) 1(4) 1(5) 1(7) 1(8) 1(9) 1(10) 1(11) 1(12) 1(13) 1(14) 1(15)                                                               
 1(0) 1(2) 1(5) 1(7) 1(10) 1(12) 1(15)                                                                                                          
 1(1) 1(4) 1(6) 1(8) 1(11) 1(13)                                                                                                                
 1(0) 1(2) 1(5) 1(7) 1(10) 1(12) 1(14) 1(15)                                                                                                    
 1(1) 1(2) 1(3) 1(6) 1(8) 1(11) 1(13)                                                                                                           
 1(0) 1(2) 1(4) 1(7) 1(9) 1(12) 1(14)                                                                                                           
 1(1) 1(3) 1(6) 1(8) 1(11) 1(13)                                                                                                                
 1(0) 1(1) 1(2) 1(3) 1(4) 1(5) 1(8) 1(10) 1(13) 1(15)                                                                                           
 1(2) 1(4) 1(6) 1(9) 1(11) 1(14)                                                                                                                
 1(0) 1(3) 1(5) 1(7) 1(10) 1(12) 1(15)                                                                                                          
 1(1) 1(2) 1(3) 1(4) 1(5) 1(6) 1(7) 1(8) 1(9) 1(10) 1(11) 1(12) 1(13) 1(14) 1(15)                                                               
 1(1) 1(3) 1(6) 1(8) 1(11) 1(13)                                                                                                                
 1(0) 1(2) 1(4) 1(7) 1(9) 1(11) 1(14)                                                                                                           
 1(1) 1(3) 1(6) 1(8) 1(10) 1(13) 1(14) 1(15)                                                                                                    
 1(0) 1(1) 1(2) 1(3) 1(4) 1(5) 1(6) 1(7) 1(8) 1(9) 1(10) 1(11) 1(12) 1(15)                                                                      
 1(1) 1(3) 1(6) 1(8) 1(10) 1(13)                                                                                                                
 1(0) 1(2) 1(5) 1(7) 1(9) 1(12) 1(14)
...

Edit: Vielä yksi juttu: seuraava ohjelma laskee samaa merkkiä sisältävien merkkien määrän jonojen pituuksittain:

#define RUNSMAX 50

int runs8[RUNSMAX];

reset_runs8()
{
  int c;

  for(c=0;c<RUNSMAX;c++) {
    runs8[c]=0;
  }
}

test_runs8(int size, unsigned char *buffer)
{
  int c,d,firstbyte,count,total;

  firstbyte=-1;
  count=0;
  for(c=0;c<size;c++) {
    if(firstbyte==-1) {
      firstbyte=buffer[c];
      count=1;
    } else {
      if(buffer[c]==firstbyte) {
        count++;
      } else {
        if(count>=RUNSMAX)
          count=RUNSMAX-1;
        if(count<RUNSMAX) {
          runs8[count]++;
        }
        firstbyte=buffer[c];
        count=1;
      }
    }
  }
  if(count>=RUNSMAX)
    count=RUNSMAX-1;
  if(count<RUNSMAX) {
    runs8[count]++;
  }
}

results_runs8()
{
  int c,d,total;
  char tmp[32],buffer[4096];

  total=0;

  *buffer='\0';
  for(d=RUNSMAX-1;d>0 && runs8[d]==0;d--);
  for(c=1;c<=d;c++) {
    sprintf(tmp," %d:%d",c,runs8[c]);
    strcat(buffer,tmp);
    total+=c*runs8[c];
  }
  message("runs8: any: %s",buffer);
  message("runs8: total:  %d",total);
}

Se tulostaa (hiukan nopeammalla koneella) seuraavan listan. Listan perusteella kellodatassa on eniten neljän ja viiden merkin pituisia samaa merkkiä sisältäviä sarjoja eli ne ovat ilmeisesti perusjono ja 1, 2, 3 ja 6 merkin sarjoja voidaan pitää satunnaisuutena.

runs8: any:  1:139 2:145 3:128 4:1292 5:2841 6:49
runs8: total:  20480

Näyte datasta (test_timer1())

 237 237 237 237 238 238 238 238 238 239 239 239 239 240 240 240 240 240
 241 241 241 241 242 242 242 242 242 243 243 243 243 244 244 244 244 244
 245 245 245 245 246 246 246 246 246 247 247 247 247 248 248 248 248 248
 249 249 249 249 250 250 250 250 250 251 251 251 251 252 252 252 252 252
 253 253 253 253 254 254 254 254 254 255 255 255 255   0   0   0   0   0
   1   1   1   1   2   2   2   2   2   3   3   3   3   4   4   4   4   4
   5   5   5   5   5   6   6   6   6   7   7   7   7   7   8   8   8   8
   8   9   9   9   9  10  10  10  10  10  11  11  11  11  11  12  12  12
  12  13  13  13  13  13  14  14  14  14  15  15  15  15  15  16  16  16
  16  17  17  17  17  17  18  18  18  18  19  19  19  19  19  20  20  20
  20  21  21  21  21  21  22  22  22  22  23  23  23  23  23  24  24  24
  24  25  25  25  25  25  26  26  26  26  27  27  27  27  27  28  28  28
  28  29  29  29  29  29  30  30  30  30  31  31  31  31  31  32  32  32
  32  33  33  33  33  33  34  34  34  34  35  35  35  35  35  36  36  36
  36  37  37  37  37  37  38  38  38  38  39  39  39  39  39  40  40  40
  40  40  41  41  41  41  42  42  42  42  42  43  43  43
...

Tuloste raportilla test_timer5(): En kyllä nelosen ja viitosen vaihteluitakaan lähtisi arvaamaan..

 5(0) 5(1) 4(2) 5(3) 5(4) 4(5) 5(6) 5(7) 4(8) 5(9) 5(10) 4(11) 5(12) 5(13) 4(14) 5(15)
 5(0) 4(1) 5(2) 5(3) 5(4) 4(5) 5(6) 5(7) 4(8) 5(9) 5(10) 5(11) 4(12) 5(13) 5(14) 4(15)
 5(0) 5(1) 5(2) 4(3) 5(4) 5(5) 4(6) 5(7) 4(8) 5(9) 5(10) 4(11) 5(12) 5(13) 4(14) 5(15)
 5(0) 5(1) 4(2) 5(3) 5(4) 4(5) 5(6) 5(7) 4(8) 5(9) 4(10) 5(11) 5(12) 5(13) 4(14) 5(15)
 5(0) 4(1) 5(2) 5(3) 5(4) 4(5) 5(6) 5(7) 5(8) 4(9) 5(10) 5(11) 4(12) 5(13) 5(14) 4(15)
 5(0) 5(1) 4(2) 5(3) 5(4) 5(5) 4(6) 5(7) 5(8) 4(9) 5(10) 5(11) 4(12) 5(13) 5(14) 5(15)
 4(0) 5(1) 5(2) 5(3) 4(4) 5(5) 4(6) 5(7) 5(8) 4(9) 5(10) 5(11) 5(12) 4(13) 5(14) 5(15)
 5(0) 4(1) 5(2) 5(3) 4(4) 5(5) 5(6) 4(7) 5(8) 5(9) 4(10) 5(11) 5(12) 4(13) 5(14) 5(15)
 4(0) 5(1) 5(2) 5(3) 4(4) 5(5) 5(6) 4(7) 5(8) 5(9) 5(10) 5(11) 5(12) 5(13) 5(14) 5(15)
 5(0) 6(1) 5(2) 5(3) 5(4) 5(5) 5(6) 4(7) 6(8) 5(9) 5(10) 5(11) 5(12) 5(13) 5(14) 5(15)
 6(0) 4(1) 5(2) 5(3) 6(4) 5(5) 4(6) 5(7) 5(8) 4(9) 5(10) 5(11) 4(12) 5(13) 5(14) 5(15)
 4(0) 5(1) 5(2) 4(3) 5(4) 5(5) 4(6) 5(7) 5(8) 4(9) 5(10) 5(11) 4(12) 5(13) 5(14) 4(15)
 5(0) 4(1) 5(2) 5(3) 4(4) 5(5) 5(6) 4(7) 5(8) 5(9) 4(10) 5(11) 5(12) 4(13) 5(14) 5(15)
 4(0) 5(1) 5(2) 4(3) 5(4) 5(5) 5(6) 4(7) 5(8) 5(9) 4(10) 5(11) 4(12) 5(13) 5(14) 5(15)
 4(0) 5(1) 5(2) 4(3) 5(4) 5(5) 4(6) 5(7) 5(8) 5(9) 4(10) 5(11) 5(12) 4(13) 5(14) 5(15)
 4(0) 5(1) 4(2) 5(3) 5(4) 4(5) 5(6) 5(7) 5(8) 4(9) 5(10) 5(11) 4(12) 5(13) 5(14) 4(15)
 5(0) 5(1) 4(2) 5(3) 5(4) 4(5) 5(6) 5(7) 5(8) 5(9) 4(10) 5(11) 5(12) 4(13) 5(14) 4(15)
...

Edit: vielä tilastotietoa genbytes():in tulostamasta merkkijonosta ja tilastot luovat ohjelmat: (puskurin koko on 2500 merkkiä, kuten FIPS-120 suosittelee (osa testeistä on laadittu näiden satunnaisuus testien mukaan))

monobit ones: 9994 zeroes 10006, total: 20000
poker2:  data:  0:2505 1:2485 2:2499 3:2511
poker2: total: 10000, lowest: 2485, highest: 2511
poker4:  data:  0:327 1:315 2:280 3:309 4:283 5:287 6:345 7:319 8:339 9:311 10:305 11:287 12:325 13:338 14:327 15:303
poker4: total: 5000, lowest: 280, highest: 345
runs: stat:    1:2500 2:1250 3:625 4:312 5:156 6:78 7:39 8:19 9:9 10:4 11:2 12:1 13:0 14:0 15:0
runs: zeroes:  1:2448 2:1227 3:611 4:336 5:158 6:75 7:47 8:22 9:5 10:10 11:0 12:1 13:1
runs: ones:    1:2410 2:1280 3:615 4:319 5:164 6:76 7:33 8:23 9:13 10:2 11:2 12:2 13:2 14:0 15:1
runs: total:  20000
runs8: any:  1:2482 2:9
runs8: total:  2500

Nämä tilastoluvut kertovat tässä tapauksessa lähinnä satunnaisbittien keräilyn ja sekoittamisen laadusta. Kokeile tulostaa tilastot siten että genbytes():in kellona käytetään vuorotellen lukuja 1-255, kun numerosarja loppuu se aloitetaan taas alusta. Sekin saa varsin hyvät tilastoluvut (ilmeisesti, en kokeillut…). Jos kellon alimmassa bitissä on riittävästi nollia ja ykkösiä, se saa hyvän arvosanan. Edellisessä joka toinen alin bitti on nolla, ja joka toinen 1. Jos teit itsellesi viritetyn kellon, voit jatkaa kokeiluja toistamalla numerot kahteen kertaan ja kolmeen kertaan, ja siitä pääset mukavasti kehittämään kellon arvaamista. Onkohan se niin, että jokaisessa kellon arvon vaihdoksessa on 1 bitti satunnaisuutta? (Jos kello ei ole säännöllinen sarja)

Monobit alkuinen rivi laskee puskurin nollat ja ykköset. Nollia ja ykkösiä pitäisi olla tilastollisesti yhtä paljon.

int monobit_zeroes = 0, monobit_ones = 0;

reset_monobit()
{
  monobit_zeroes = 0;
  monobit_ones = 0;
}

test_monobit(int size, unsigned char *buffer)
{
  int c,d,zeroes,ones;

  for(c=0;c<size;c++) {
    for(d=0;d<8;d++) {
      if((buffer[c]>>d)&1)
        monobit_ones++;
      else
        monobit_zeroes++;
    }
  }
}

results_monobit()
{
  message("monobit ones: %d zeroes %d, total: %d",monobit_zeroes,monobit_ones,monobit_zeroes+monobit_ones);
}

Poker2 testi jakaa puskurin 2 bitin lukuihin, ja tulostaa näiden lukumäärät. (neljä lukua)

int poker2_i[4];

reset_poker2()
{
  int c;

  for(c=0;c<4;c++) {
    poker2_i[c]=0;
  }
}

test_poker2(int size, unsigned char *buffer)
{
  int c;

  for(c=0;c<size;c++) {
    poker2_i[(buffer[c]>>6)&0x03]++;
    poker2_i[(buffer[c]>>4)&0x03]++;
    poker2_i[(buffer[c]>>2)&0x03]++;
    poker2_i[buffer[c]&0x03]++;
  }
}

results_poker2()
{
  int c,total,lowest,highest;
  char tmp[32],buffer[1024];

  total=0;
  lowest=999999999;
  highest=0;
  *buffer='\0';
  for(c=0;c<4;c++) {
    sprintf(tmp," %d:%d",c,poker2_i[c]);
    strcat(buffer,tmp);

    total+=poker2_i[c];
    if(lowest>poker2_i[c])
      lowest=poker2_i[c];
    if(highest<poker2_i[c])
       highest=poker2_i[c];
  }
  message("poker2:  data: %s",buffer);
  message("poker2: total: %d, lowest: %d, highest: %d",total,lowest,highest);
}

Poker 4 jakaa puskurin 4 bitin lukuihin ja laskee niiden lukumäärän. Poker4 ei mielestäniei ollut FIPS:issä.

int poker4_i[16];

reset_poker4()
{
  int c;

  for(c=0;c<16;c++) {
    poker4_i[c]=0;
  }
}


test_poker4(int size, unsigned char *buffer)
{
  int c;

  for(c=0;c<size;c++) {
    poker4_i[(buffer[c]>>4)&0x0f]++;
    poker4_i[buffer[c]&0x0f]++;
  }
}

results_poker4()
{
  int c, total, lowest, highest;
  char tmp[32],buffer[1024];

  total=0;
  lowest=999999999;
  highest=0;
  *buffer='\0';
  for(c=0;c<16;c++) {
    sprintf(tmp," %d:%d",c,poker4_i[c]);
    strcat(buffer,tmp);
    total+=poker4_i[c];
    if(lowest>poker4_i[c])
      lowest=poker4_i[c];
    if(highest<poker4_i[c])
      highest=poker4_i[c];
  }
  message("poker4:  data: %s",buffer);
  message("poker4: total: %d, lowest: %d, highest: %d",total,lowest,highest);
}

Seuraava testi on runs, ja se laskee peräkkäisten 0 ja 1 jonojen määrän puskurissa.

#define RUNSMAX 50

int runs_zero[RUNSMAX];
int runs_ones[RUNSMAX];

reset_runs()
{
  int c;

  for(c=0;c<RUNSMAX;c++) {
    runs_zero[c]=0;
    runs_ones[c]=0;
  }
}

test_runs(int size, unsigned char *buffer)
{
  int c,d,firstbit,count,total;

  firstbit=-1;
  count=0;
  for(c=0;c<size;c++) {
    for(d=0;d<8;d++) {
      if(firstbit==-1) {
        firstbit=buffer[c]&1;
        count=1;
      } else {
        if(((buffer[c]>>d)&1)==firstbit) {
          count++;
        } else {
          if(count>=RUNSMAX)
            count=RUNSMAX-1;
          if(count<RUNSMAX) {
            if(firstbit==0)
              runs_zero[count]++;
            else
              runs_ones[count]++;
          }
          firstbit=(buffer[c]>>d)&1;
          count=1;
        }
      }
    }
  }
  if(count>=RUNSMAX)
    count=RUNSMAX-1;
  if(count<RUNSMAX) {
    if(firstbit==0)
      runs_zero[count]++;
    else
      runs_ones[count]++;
  }
}

results_runs(int size)
{
  int c,d,total;
  char tmp[32],buffer[4096];

  total=0;

  *buffer='\0';
  for(d=RUNSMAX-1;d>0 && runs_zero[d]==0 && runs_ones[d]==0 ;d--);
  for(c=1;c<=d;c++) {
    sprintf(tmp," %d:%d",c,(int)(pow((double)0.5,c+2)*(size*8)));
    strcat(buffer,tmp);
  }
  message("runs: stat:   %s",buffer);

  *buffer='\0';
  for(d=RUNSMAX-1;d>0 && runs_zero[d]==0;d--);
  for(c=1;c<=d;c++) {
    sprintf(tmp," %d:%d",c,runs_zero[c]);
    strcat(buffer,tmp);
    total+=c*runs_zero[c];
  }
  message("runs: zeroes: %s",buffer);

  *buffer='\0';
  for(d=RUNSMAX-1;d>0 && runs_ones[d]==0;d--);
  for(c=1;c<=d;c++) {
    sprintf(tmp," %d:%d",c,runs_ones[c]);
    strcat(buffer,tmp);
    total+=c*runs_ones[c];
  }
  message("runs: ones:   %s",buffer);

  message("runs: total:  %d",total);
}

Seuraava testi on runs8, ja se laskee samaa lukua sisältävien merkkijonojen määrän puskurissa. (tämä ei ollut muistaakseni FIPS testeissä). Runs8 testi on listattu aiemmin tässä postissa.

FIPS:issä näissä testeissä oli hylkäämisehto, mutta en vielä ole lisännyt sitä näihin rutiineihin.

Edit 20160120: Vielä duplikaattien laskemiseen liittyvä rutiini:

Duplikaattien lasku:

$ sort test8_64_45_30.txt | uniq -cd

tai

$ sort test8_64_45_30.txt | uniq -d | wc -l
test_timer8()
{
  int c,e,f;
  unsigned char buffer[1024],filename[128];
  FILE *fp1;
  int alku,loppu,b;
  int testcount=16384;
  int testsize=64,dumpsize=30;

  for(;;) {
    for(b=45;b<70;b+=5) {
      for(testsize=64;testsize<=128;testsize+=64) {
        sprintf(filename,"test8_%d_%d_%d.txt",testsize,b,dumpsize);

        fp1=fopen(filename,"a");
        alku=(int)time(NULL);
        for(c=0;c<testcount;c++) {
          memset(buffer,0,testsize);
          genbytes(testsize,buffer,b);
          for(e=0;e<dumpsize;e++)
            fprintf(fp1,"%02x",buffer[e]);
          fprintf(fp1,"\n");
          fflush(fp1);
        }
        fclose(fp1);
        loppu=(int)time(NULL);
        fprintf(stdout,"%d bytes per bit, %d testsize, %d total seconds, %f seconds per crypt\n",
          b,testsize,loppu-alku,((double)((double)loppu-alku)/testcount));
        fflush(stdout);
      }
    }
  }
}
;