SHA256 tiivisteen laskentaohjelman vakiot

SHA256 laskentaohjelmaa kuvaavassa postissani mainitsin vakionumerot, joilla täytetään tiivisteen alustuksessa tiivisteen tila (state[]) ja transformissa käytettävä k256 taulu. Postissa sanoin, että ne tulevat alkulukujen neliöjuuren (state[]) ja kuutiojuuren (k256[]) desimaaleista. Tässä postissa käydään läpi ohjelma, joilla ne voidaan tarkistaa tai laskea. Postin mittaan käydään ohjelma ja sen tuloste läpi kappaleittain ja lopussa on ohjelma kokonaisuudessaan.

Ohjelman laskemiseen tarvitaan alkulukuja, joten ensimmäisissä kappaleissa tehdään lista niistä: ohjelmassa Eratostheneen seulan toteutus. Toteutuksessa haetaan alkuluvut 400 ensimmäisen luvun joukosta, tilataululle tarvitaan alkuluvut 2-19 ja k256[]-taululle alkuluvut 2-311. Alussa taulu alustetaan ykkösillä (for(c=0…) ja merkataan 0 ja 1 ei alkuluvuiksi. Sitten käydään taulu läpi taulun pituuden neliöjuureen asti (for(c=2…). Taulusta etsitään ykköset (alkulukuja) ja käydään läpi niiden kerrannaiset (for(d=c*2…) ja merkataan ne nolliksi, ne eivät kerrannaisina ole alkulukuja.

  int c, d, count, id;
  char primes[400];

  for(c=0; c<sizeof(primes); c++)
    primes[c] = 1;

  primes[0] = 0;
  primes[1] = 0;

  for(c=2; c<=sqrt(sizeof(primes)-1); c++) {
  // Little bug 30.6 JariK
  //for(c=2; c<=sqrt(sizeof(primes)); c++) {
    if(primes[c] == 1) {
      fprintf(stdout,"*%d", c);
      count = 0;
      for(d = c*2; d < sizeof(primes); d+=c) {
        primes[d] = 0;
        if(count++ < 20)
          fprintf(stdout," %d", d);
      }
      if(count > 20)
        fprintf(stdout,"...");
      fprintf(stdout,"\n");
    }
  }

Näiden ensimmäisten kappaleiden tuloste on seuraavanlainen: tähdellä merkitty on alkuluku, jota käsitellään ja samalla rivillä sen kanssa ovat kerrannaiset, jotka poistetaan listalta. Riville tulostetaan count muuttujan avulla vain 20 ensimmäistä kerrannaista. Ohjelman on käytävä läpi vain 19 ensimmäistä alkulukua, luku 20 ei ole alkuluku ja sen kerrannaiset menisivät taulun yli (20*20=400). Siis neliöjuuren jälkeen taulussa ei voi olla yhdistettyjä lukuja, joita ei ole vielä merkitty. Neliöjuurta pienempien tekijöiden luvut on jo merkitty, ja neliöjuurta suurempien tekijöiden luvut (joissa ei ole pientä tekijää) sijoittuvat taulun ulkopuolelle.

*2 4 6 8 10 12 14 16 18 20 22 24 26 28 30 32 34 36 38 40 42...
*3 6 9 12 15 18 21 24 27 30 33 36 39 42 45 48 51 54 57 60 63...
*5 10 15 20 25 30 35 40 45 50 55 60 65 70 75 80 85 90 95 100 105...
*7 14 21 28 35 42 49 56 63 70 77 84 91 98 105 112 119 126 133 140 147...
*11 22 33 44 55 66 77 88 99 110 121 132 143 154 165 176 187 198 209 220 231...
*13 26 39 52 65 78 91 104 117 130 143 156 169 182 195 208 221 234 247 260 273...
*17 34 51 68 85 102 119 136 153 170 187 204 221 238 255 272 289 306 323 340 357...
*19 38 57 76 95 114 133 152 171 190 209 228 247 266 285 304 323 342 361 380 399

Seuraavassa kappaleessa tulostetaan lista alkuluvuista 2-19 ja niiden perusteella lasketaan neliojuuri (sqrt()), neliöjuuren kokonaisosa (isqrt), näiden erotuksena neliöjuuren desimaalit (decimalpart), kerrotaan desimaalit kokonaisluvuksi ja sen perusteella tulostetaan neliöjuuren desimaalit desimaalina (decimal) ja heksana (hex). Näistä heksaluvuilla on täytetty state[] taulu.

  id=0;
  for(c=2; c<=19; c++) {
    if(primes[c] == 1) {
      int isqrt;
      fprintf(stdout,"id:%d", id);
      fprintf(stdout,", c:%2d", c);
      fprintf(stdout,", sqrt:%f", sqrt(c));
      isqrt = (int)sqrt(c);
      fprintf(stdout,", isqrt:%2d", isqrt);
      double decimalpart = sqrt(c)-isqrt;
      fprintf(stdout,", decimalpart:%f",
          decimalpart);
      fprintf(stdout,", decimalpart*16^8:%017f",
          decimalpart*pow(16,8));
      fprintf(stdout,", decimal:%010lu",
          (long)(decimalpart*pow(16,8)));
      fprintf(stdout,", hex:%08lx",
          (long)(decimalpart*pow(16,8)));
      fprintf(stdout,"\n");
      id++;
    }
  }

Edellinen kappale tulostaa seuraavan taulun: rivillä on alkuluku (c), sen neliöjuuri (sqrt), neliöjuuren kokonaisosa (isqrt), neliöjuuren desimaaliosa (decimalpart), edellinen kerrottuna kokonaisluvuksi, tulos desimaaleina ja heksana.

id:0, c: 2, sqrt:1.414214, isqrt: 1, decimalpart:0.414214, decimalpart*16^8:1779033703.952100, decimal:1779033703, hex:6a09e667
id:1, c: 3, sqrt:1.732051, isqrt: 1, decimalpart:0.732051, decimalpart*16^8:3144134277.518717, decimal:3144134277, hex:bb67ae85
id:2, c: 5, sqrt:2.236068, isqrt: 2, decimalpart:0.236068, decimalpart*16^8:1013904242.994461, decimal:1013904242, hex:3c6ef372
id:3, c: 7, sqrt:2.645751, isqrt: 2, decimalpart:0.645751, decimalpart*16^8:2773480762.371540, decimal:2773480762, hex:a54ff53a
id:4, c:11, sqrt:3.316625, isqrt: 3, decimalpart:0.316625, decimalpart*16^8:1359893119.679298, decimal:1359893119, hex:510e527f
id:5, c:13, sqrt:3.605551, isqrt: 3, decimalpart:0.605551, decimalpart*16^8:2600822924.168921, decimal:2600822924, hex:9b05688c
id:6, c:17, sqrt:4.123106, isqrt: 4, decimalpart:0.123106, decimalpart*16^8:0528734635.981472, decimal:0528734635, hex:1f83d9ab
id:7, c:19, sqrt:4.358899, isqrt: 4, decimalpart:0.358899, decimalpart*16^8:1541459225.076145, decimal:1541459225, hex:5be0cd19

Sitten alkuluvut 2-311 k256[] taulua varten: käsittely on oikeastaan kopio edellisestä paitsi että käytetään kuutiojuurta: lasketaan kuutiojuuri, sen kokonaisosa, niistä desimaaliosa, kerrotaan desimaaliosa kokonaisiksi, ja tulostetaan desimaaliosa desimaalina ja heksana.

  id=0;
  for(c=2; c<=311; c++) {
    if(primes[c] == 1) {
      int icbrt;
      fprintf(stdout,"id:%d", id);
      fprintf(stdout,", c:%3d", c);
      fprintf(stdout,", cbrt:%f", cbrt(c));
      icbrt = (int)cbrt((double)c);
      fprintf(stdout,", icbrt:%2d", icbrt);
      double decimalpart = cbrt(c)-icbrt;
      fprintf(stdout,", decimalpart:%f",
          decimalpart);
      fprintf(stdout,", decimalpart*16^8:%017f",
          decimalpart*pow(16,8));
      fprintf(stdout,", decimal:%010lu",
          (long)(decimalpart*pow(16,8)));
      fprintf(stdout,", hex:%08lx",
          (long)(decimalpart*pow(16,8)));
      //if((long)(decimalpart*pow(16,8))
      //    == k256[id])
	//fprintf(stdout,"ok");
      fprintf(stdout,"\n");
      id++;
    }
  }

Edellisen tuloste:

id:0, c:  2, cbrt:1.259921, icbrt: 1, decimalpart:0.259921, decimalpart*16^8:1116352408.840466, decimal:1116352408, hex:428a2f98
id:1, c:  3, cbrt:1.442250, icbrt: 1, decimalpart:0.442250, decimalpart*16^8:1899447441.140371, decimal:1899447441, hex:71374491
id:2, c:  5, cbrt:1.709976, icbrt: 1, decimalpart:0.709976, decimalpart*16^8:3049323471.923053, decimal:3049323471, hex:b5c0fbcf
id:3, c:  7, cbrt:1.912931, icbrt: 1, decimalpart:0.912931, decimalpart*16^8:3921009573.506011, decimal:3921009573, hex:e9b5dba5
id:4, c: 11, cbrt:2.223980, icbrt: 2, decimalpart:0.223980, decimalpart*16^8:0961987163.950329, decimal:0961987163, hex:3956c25b
id:5, c: 13, cbrt:2.351335, icbrt: 2, decimalpart:0.351335, decimalpart*16^8:1508970993.711027, decimal:1508970993, hex:59f111f1
id:6, c: 17, cbrt:2.571282, icbrt: 2, decimalpart:0.571282, decimalpart*16^8:2453635748.683981, decimal:2453635748, hex:923f82a4
id:7, c: 19, cbrt:2.668402, icbrt: 2, decimalpart:0.668402, decimalpart*16^8:2870763221.853235, decimal:2870763221, hex:ab1c5ed5
id:8, c: 23, cbrt:2.843867, icbrt: 2, decimalpart:0.843867, decimalpart*16^8:3624381080.636766, decimal:3624381080, hex:d807aa98
id:9, c: 29, cbrt:3.072317, icbrt: 3, decimalpart:0.072317, decimalpart*16^8:0310598401.271248, decimal:0310598401, hex:12835b01
id:10, c: 31, cbrt:3.141381, icbrt: 3, decimalpart:0.141381, decimalpart*16^8:0607225278.308178, decimal:0607225278, hex:243185be
id:11, c: 37, cbrt:3.332222, icbrt: 3, decimalpart:0.332222, decimalpart*16^8:1426881987.835932, decimal:1426881987, hex:550c7dc3
id:12, c: 41, cbrt:3.448217, icbrt: 3, decimalpart:0.448217, decimalpart*16^8:1925078388.947197, decimal:1925078388, hex:72be5d74
id:13, c: 43, cbrt:3.503398, icbrt: 3, decimalpart:0.503398, decimalpart*16^8:2162078206.230814, decimal:2162078206, hex:80deb1fe
id:14, c: 47, cbrt:3.608826, icbrt: 3, decimalpart:0.608826, decimalpart*16^8:2614888103.147570, decimal:2614888103, hex:9bdc06a7
id:15, c: 53, cbrt:3.756286, icbrt: 3, decimalpart:0.756286, decimalpart*16^8:3248222580.810200, decimal:3248222580, hex:c19bf174
id:16, c: 59, cbrt:3.892996, icbrt: 3, decimalpart:0.892996, decimalpart*16^8:3835390401.620871, decimal:3835390401, hex:e49b69c1
id:17, c: 61, cbrt:3.936497, icbrt: 3, decimalpart:0.936497, decimalpart*16^8:4022224774.219959, decimal:4022224774, hex:efbe4786
id:18, c: 67, cbrt:4.061548, icbrt: 4, decimalpart:0.061548, decimalpart*16^8:0264347078.545116, decimal:0264347078, hex:0fc19dc6
id:19, c: 71, cbrt:4.140818, icbrt: 4, decimalpart:0.140818, decimalpart*16^8:0604807628.467480, decimal:0604807628, hex:240ca1cc
id:20, c: 73, cbrt:4.179339, icbrt: 4, decimalpart:0.179339, decimalpart*16^8:0770255983.348312, decimal:0770255983, hex:2de92c6f
id:21, c: 79, cbrt:4.290840, icbrt: 4, decimalpart:0.290840, decimalpart*16^8:1249150122.432236, decimal:1249150122, hex:4a7484aa
id:22, c: 83, cbrt:4.362071, icbrt: 4, decimalpart:0.362071, decimalpart*16^8:1555081692.739288, decimal:1555081692, hex:5cb0a9dc
id:23, c: 89, cbrt:4.464745, icbrt: 4, decimalpart:0.464745, decimalpart*16^8:1996064986.511982, decimal:1996064986, hex:76f988da
id:24, c: 97, cbrt:4.594701, icbrt: 4, decimalpart:0.594701, decimalpart*16^8:2554220882.931259, decimal:2554220882, hex:983e5152
id:25, c:101, cbrt:4.657010, icbrt: 4, decimalpart:0.657010, decimalpart*16^8:2821834349.178532, decimal:2821834349, hex:a831c66d
id:26, c:103, cbrt:4.687548, icbrt: 4, decimalpart:0.687548, decimalpart*16^8:2952996808.597584, decimal:2952996808, hex:b00327c8
id:27, c:107, cbrt:4.747459, icbrt: 4, decimalpart:0.747459, decimalpart*16^8:3210313671.745834, decimal:3210313671, hex:bf597fc7
id:28, c:109, cbrt:4.776856, icbrt: 4, decimalpart:0.776856, decimalpart*16^8:3336571891.240852, decimal:3336571891, hex:c6e00bf3
id:29, c:113, cbrt:4.834588, icbrt: 4, decimalpart:0.834588, decimalpart*16^8:3584528711.574383, decimal:3584528711, hex:d5a79147
id:30, c:127, cbrt:5.026526, icbrt: 5, decimalpart:0.026526, decimalpart*16^8:0113926993.875053, decimal:0113926993, hex:06ca6351
id:31, c:131, cbrt:5.078753, icbrt: 5, decimalpart:0.078753, decimalpart*16^8:0338241895.039284, decimal:0338241895, hex:14292967
id:32, c:137, cbrt:5.155137, icbrt: 5, decimalpart:0.155137, decimalpart*16^8:0666307205.276646, decimal:0666307205, hex:27b70a85
id:33, c:139, cbrt:5.180101, icbrt: 5, decimalpart:0.180101, decimalpart*16^8:0773529912.359966, decimal:0773529912, hex:2e1b2138
id:34, c:149, cbrt:5.301459, icbrt: 5, decimalpart:0.301459, decimalpart*16^8:1294757372.354557, decimal:1294757372, hex:4d2c6dfc
id:35, c:151, cbrt:5.325074, icbrt: 5, decimalpart:0.325074, decimalpart*16^8:1396182291.615566, decimal:1396182291, hex:53380d13
id:36, c:157, cbrt:5.394691, icbrt: 5, decimalpart:0.394691, decimalpart*16^8:1695183700.545647, decimal:1695183700, hex:650a7354
id:37, c:163, cbrt:5.462556, icbrt: 5, decimalpart:0.462556, decimalpart*16^8:1986661051.236202, decimal:1986661051, hex:766a0abb
id:38, c:167, cbrt:5.506878, icbrt: 5, decimalpart:0.506878, decimalpart*16^8:2177026350.280975, decimal:2177026350, hex:81c2c92e
id:39, c:173, cbrt:5.572055, icbrt: 5, decimalpart:0.572055, decimalpart*16^8:2456956037.080109, decimal:2456956037, hex:92722c85
id:40, c:179, cbrt:5.635741, icbrt: 5, decimalpart:0.635741, decimalpart*16^8:2730485921.300552, decimal:2730485921, hex:a2bfe8a1
id:41, c:181, cbrt:5.656653, icbrt: 5, decimalpart:0.656653, decimalpart*16^8:2820302411.735386, decimal:2820302411, hex:a81a664b
id:42, c:191, cbrt:5.758965, icbrt: 5, decimalpart:0.758965, decimalpart*16^8:3259730800.816296, decimal:3259730800, hex:c24b8b70
id:43, c:193, cbrt:5.778997, icbrt: 5, decimalpart:0.778997, decimalpart*16^8:3345764771.024734, decimal:3345764771, hex:c76c51a3
id:44, c:197, cbrt:5.818648, icbrt: 5, decimalpart:0.818648, decimalpart*16^8:3516065817.839592, decimal:3516065817, hex:d192e819
id:45, c:199, cbrt:5.838272, icbrt: 5, decimalpart:0.838272, decimalpart*16^8:3600352804.333588, decimal:3600352804, hex:d6990624
id:46, c:211, cbrt:5.953342, icbrt: 5, decimalpart:0.953342, decimalpart*16^8:4094571909.341568, decimal:4094571909, hex:f40e3585
id:47, c:223, cbrt:6.064127, icbrt: 6, decimalpart:0.064127, decimalpart*16^8:0275423344.198177, decimal:0275423344, hex:106aa070
id:48, c:227, cbrt:6.100170, icbrt: 6, decimalpart:0.100170, decimalpart*16^8:0430227734.721970, decimal:0430227734, hex:19a4c116
id:49, c:229, cbrt:6.118033, icbrt: 6, decimalpart:0.118033, decimalpart*16^8:0506948616.317406, decimal:0506948616, hex:1e376c08
id:50, c:233, cbrt:6.153449, icbrt: 6, decimalpart:0.153449, decimalpart*16^8:0659060556.873276, decimal:0659060556, hex:2748774c
id:51, c:239, cbrt:6.205822, icbrt: 6, decimalpart:0.205822, decimalpart*16^8:0883997877.881279, decimal:0883997877, hex:34b0bcb5
id:52, c:241, cbrt:6.223084, icbrt: 6, decimalpart:0.223084, decimalpart*16^8:0958139571.772606, decimal:0958139571, hex:391c0cb3
id:53, c:251, cbrt:6.307994, icbrt: 6, decimalpart:0.307994, decimalpart*16^8:1322822218.887722, decimal:1322822218, hex:4ed8aa4a
id:54, c:257, cbrt:6.357861, icbrt: 6, decimalpart:0.357861, decimalpart*16^8:1537002063.466370, decimal:1537002063, hex:5b9cca4f
id:55, c:263, cbrt:6.406959, icbrt: 6, decimalpart:0.406959, decimalpart*16^8:1747873779.838661, decimal:1747873779, hex:682e6ff3
id:56, c:269, cbrt:6.455315, icbrt: 6, decimalpart:0.455315, decimalpart*16^8:1955562222.366940, decimal:1955562222, hex:748f82ee
id:57, c:271, cbrt:6.471274, icbrt: 6, decimalpart:0.471274, decimalpart*16^8:2024104815.262074, decimal:2024104815, hex:78a5636f
id:58, c:277, cbrt:6.518684, icbrt: 6, decimalpart:0.518684, decimalpart*16^8:2227730452.632576, decimal:2227730452, hex:84c87814
id:59, c:281, cbrt:6.549912, icbrt: 6, decimalpart:0.549912, decimalpart*16^8:2361852424.103092, decimal:2361852424, hex:8cc70208
id:60, c:283, cbrt:6.565414, icbrt: 6, decimalpart:0.565414, decimalpart*16^8:2428436474.138229, decimal:2428436474, hex:90befffa
id:61, c:293, cbrt:6.641852, icbrt: 6, decimalpart:0.641852, decimalpart*16^8:2756734187.869183, decimal:2756734187, hex:a4506ceb
id:62, c:307, cbrt:6.745997, icbrt: 6, decimalpart:0.745997, decimalpart*16^8:3204031479.698341, decimal:3204031479, hex:bef9a3f7
id:63, c:311, cbrt:6.775169, icbrt: 6, decimalpart:0.775169, decimalpart*16^8:3329325298.888462, decimal:3329325298, hex:c67178f2

Tulosteessa on alkuluku (c), kuutiojuuri (cbrt), kuutiojuuren kokonaisosa (icbrt), desimaaliosa, desimaaliosa kerrottuna kokonaisosaksi, edellinen desimaalina ja heksana. Heksaarvoilla on täytetty taulu k256[].

Vielä ohjelma kokonaisuudessaan:

void main(int argc,char *argv[])
{
  int c, d, count, id;
  char primes[400];

  for(c=0; c<sizeof(primes); c++)
    primes[c] = 1;

  primes[0] = 0;
  primes[1] = 0;

  for(c=2; c<=sqrt(sizeof(primes)-1); c++) {
    if(primes[c] == 1) {
      fprintf(stdout,"*%d", c);
      count = 0;
      for(d=c*2; d<sizeof(primes); d+=c) {
        primes[d] = 0;
        if(count++ < 20)
          fprintf(stdout," %d", d);
      }
      if(count > 20)
        fprintf(stdout,"...");
      fprintf(stdout,"\n");
    }
  }

  fprintf(stdout,"\n");

  id = 0;
  for(c=2; c<=19; c++) {
    if(primes[c] == 1) {
      int isqrt;
      fprintf(stdout,"id:%d", id);
      fprintf(stdout,", c:%2d", c);
      fprintf(stdout,", sqrt:%f", sqrt(c));
      isqrt = (int)sqrt(c);
      fprintf(stdout,", isqrt:%2d", isqrt);
      double decimalpart = sqrt(c)-isqrt;
      fprintf(stdout,", decimalpart:%f",
          decimalpart);
      fprintf(stdout,", decimalpart*16^8:%017f",
          decimalpart*pow(16,8));
      fprintf(stdout,", decimal:%010lu",
          (long)(decimalpart*pow(16,8)));
      fprintf(stdout,", hex:%08lx",
          (long)(decimalpart*pow(16,8)));
      fprintf(stdout,"\n");
      id++;
    }
  }

  fprintf(stdout,"\n");

  id = 0;
  for(c=2; c<=311; c++) {
    if(primes[c] == 1) {
      int icbrt;
      fprintf(stdout,"id:%d", id);
      fprintf(stdout,", c:%3d", c);
      fprintf(stdout,", cbrt:%f", cbrt(c));
      icbrt = (int)cbrt((double)c);
      fprintf(stdout,", icbrt:%2d", icbrt);
      double decimalpart = cbrt(c)-icbrt;
      fprintf(stdout,", decimalpart:%f",
          decimalpart);
      fprintf(stdout,", decimalpart*16^8:%017f",
          decimalpart*pow(16,8));
      fprintf(stdout,", decimal:%010lu",
          (long)(decimalpart*pow(16,8)));
      fprintf(stdout,", hex:%08lx",
          (long)(decimalpart*pow(16,8)));
      fprintf(stdout,"\n");
      id++;
    }
  }
}