home *** CD-ROM | disk | FTP | other *** search
/ The Unsorted BBS Collection / thegreatunsorted.tar / thegreatunsorted / old_apps / security / gost.c < prev    next >
C/C++ Source or Header  |  2001-02-10  |  11KB  |  416 lines
  1. /*
  2.  * The GOST 28147-89 cipher
  3.  *
  4.  * This is based on the 25 Movember 1993 draft translation
  5.  * by Aleksandr Malchik, with Whitfield Diffie, of the Government
  6.  * Standard of the U.S.S.R. GOST 28149-89, "Cryptographic Transformation
  7.  * Algorithm", effective 1 July 1990.  (Whitfield.Diffie@eng.sun.com)
  8.  *
  9.  * That is a draft, and may contain errors, which will be faithfully
  10.  * reflected here, along with possible exciting new bugs.
  11.  *
  12.  * Some details have been cleared up by the paper "Soviet Encryption
  13.  * Algorithm" by Josef Pieprzyk and Leonid Tombak of the University
  14.  * of Wollongong, New South Wales.  (josef/leo@cs.adfa.oz.au)
  15.  *
  16.  * The standard is written by A. Zabotin (project leader), G.P. Glazkov,
  17.  * and V.B. Isaeva.  It was accepted and introduced into use by the
  18.  * action of the State Standards Committee of the USSR on 2 June 89 as
  19.  * No. 1409.  It was to be reviewed in 1993, but whether anyone wishes
  20.  * to take on this obligation from the USSR is questionable.
  21.  *
  22.  * This code is placed in the public domain.
  23.  */
  24.  
  25. /*
  26.  * If you read the standard, it belabors the point of copying corresponding
  27.  * bits from point A to point B quite a bit.  It helps to understand that
  28.  * the standard is uniformly little-endian, although it numbers bits from
  29.  * 1 rather than 0, so bit n has value 2^(n-1).  The least significant bit
  30.  * of the 32-bit words that are manipulated in the algorithm is the first,
  31.  * lowest-numbered, in the bit string.
  32.  */
  33.  
  34.  
  35. /* A 32-bit data type */
  36. #ifdef __alpha  /* Any other 64-bit machines? */
  37. typedef unsigned int word32;
  38. #else
  39. typedef unsigned long word32;
  40. #endif
  41.  
  42. /*
  43.  * The standard does not specify the contents of the 8 4 bit->4 bit
  44.  * substitution boxes, saying they're a parameter of the network
  45.  * being set up.  For illustration purposes here, I have used
  46.  * the first rows of the 8 S-boxes from the DES.  (Note that the
  47.  * DES S-boxes are numbered starting from 1 at the msb.  In keeping
  48.  * with the rest of the GOST, I have used little-endian numbering.
  49.  * Thus, k8 is S-box 1.
  50.  *
  51.  * Obviously, a careful look at the cryptographic properties of the cipher
  52.  * must be undertaken before "production" substitution boxes are defined.
  53.  *
  54.  * The standard also does not specify a standard bit-string representation
  55.  * for the contents of these blocks.
  56.  */
  57. static unsigned char const k8[16] = {
  58.     14,  4, 13,  1,  2, 15, 11,  8,  3, 10,  6, 12,  5,  9,  0,  7 }; 
  59. static unsigned char const k7[16] = {
  60.     15,  1,  8, 14,  6, 11,  3,  4,  9,  7,  2, 13, 12,  0,  5, 10 };
  61. static unsigned char const k6[16] = {
  62.     10,  0,  9, 14,  6,  3, 15,  5,  1, 13, 12,  7, 11,  4,  2,  8 };
  63. static unsigned char const k5[16] = {
  64.      7, 13, 14,  3,  0,  6,  9, 10,  1,  2,  8,  5, 11, 12,  4, 15 };
  65. static unsigned char const k4[16] = {
  66.      2, 12,  4,  1,  7, 10, 11,  6,  8,  5,  3, 15, 13,  0, 14,  9 };
  67. static unsigned char const k3[16] = {
  68.     12,  1, 10, 15,  9,  2,  6,  8,  0, 13,  3,  4, 14,  7,  5, 11 };
  69. static unsigned char const k2[16] = {
  70.      4, 11,  2, 14, 15,  0,  8, 13,  3, 12,  9,  7,  5, 10,  6,  1 };
  71. static unsigned char const k1[16] = {
  72.     13,  2,  8,  4,  6, 15, 11,  1, 10,  9,  3, 14,  5,  0, 12,  7 };
  73.  
  74. /* Byte-at-a-time substitution boxes */
  75. static unsigned char k87[256];
  76. static unsigned char k65[256];
  77. static unsigned char k43[256];
  78. static unsigned char k21[256];
  79.  
  80. /*
  81.  * Build byte-at-a-time subtitution tables.
  82.  * This must be called once for global setup.
  83.  */
  84. void
  85. kboxinit(void)
  86. {
  87.     int i;
  88.     for (i = 0; i < 256; i++) {
  89.         k87[i] = k8[i >> 4] << 4 | k7[i & 15];
  90.         k65[i] = k6[i >> 4] << 4 | k5[i & 15];
  91.         k43[i] = k4[i >> 4] << 4 | k3[i & 15];
  92.         k21[i] = k2[i >> 4] << 4 | k1[i & 15];
  93.     }
  94. }
  95.  
  96. /*
  97.  * Do the substitution and rotation that are the core of the operation,
  98.  * like the expansion, substitution and permutation of the DES.
  99.  * It would be possible to perform DES-like optimisations and store
  100.  * the table entries as 32-bit words, already rotated, but the
  101.  * efficiency gain is questionable.
  102.  *
  103.  * This should be inlined for maximum speed
  104.  */
  105. #if __GNUC__
  106. __inline__
  107. #endif
  108. static word32
  109. f(word32 x)
  110. {
  111.     /* Do substitutions */
  112. #if 0
  113.     /* This is annoyingly slow */
  114.     x = k8[x>>28 & 15] << 28 | k7[x>>24 & 15] << 24 |
  115.         k6[x>>20 & 15] << 20 | k5[x>>16 & 15] << 16 |
  116.         k4[x>>12 & 15] << 12 | k3[x>> 8 & 15] <<  8 |
  117.         k2[x>> 4 & 15] <<  4 | k1[x     & 15];
  118. #else
  119.     /* This is faster */
  120.     x = k87[x>>24 & 255] << 24 | k65[x>>16 & 255] << 16 |
  121.         k43[x>> 8 & 255] <<  8 | k21[x & 255];
  122. #endif
  123.  
  124.     /* Rotate left 11 bits */
  125.     return x<<11 | x>>(32-11);
  126. }
  127.  
  128. /*
  129.  * The GOST standard defines the input in terms of bits 1..64, with
  130.  * bit 1 being the lsb of in[0] and bit 64 being the msb of in[1].
  131.  *
  132.  * The keys are defined similarly, with bit 256 being the msb of key[7].
  133.  */
  134. void
  135. gostcrypt(word32 const in[2], word32 out[2], word32 const key[8])
  136. {
  137.     register word32 n1, n2; /* As named in the GOST */
  138.  
  139.     n1 = in[0];
  140.     n2 = in[1];
  141.  
  142.     /* Instead of swapping halves, swap names each round */
  143.     n2 ^= f(n1+key[0]);
  144.     n1 ^= f(n2+key[1]);
  145.     n2 ^= f(n1+key[2]);
  146.     n1 ^= f(n2+key[3]);
  147.     n2 ^= f(n1+key[4]);
  148.     n1 ^= f(n2+key[5]);
  149.     n2 ^= f(n1+key[6]);
  150.     n1 ^= f(n2+key[7]);
  151.  
  152.     n2 ^= f(n1+key[0]);
  153.     n1 ^= f(n2+key[1]);
  154.     n2 ^= f(n1+key[2]);
  155.     n1 ^= f(n2+key[3]);
  156.     n2 ^= f(n1+key[4]);
  157.     n1 ^= f(n2+key[5]);
  158.     n2 ^= f(n1+key[6]);
  159.     n1 ^= f(n2+key[7]);
  160.  
  161.     n2 ^= f(n1+key[0]);
  162.     n1 ^= f(n2+key[1]);
  163.     n2 ^= f(n1+key[2]);
  164.     n1 ^= f(n2+key[3]);
  165.     n2 ^= f(n1+key[4]);
  166.     n1 ^= f(n2+key[5]);
  167.     n2 ^= f(n1+key[6]);
  168.     n1 ^= f(n2+key[7]);
  169.  
  170.     n2 ^= f(n1+key[7]);
  171.     n1 ^= f(n2+key[6]);
  172.     n2 ^= f(n1+key[5]);
  173.     n1 ^= f(n2+key[4]);
  174.     n2 ^= f(n1+key[3]);
  175.     n1 ^= f(n2+key[2]);
  176.     n2 ^= f(n1+key[1]);
  177.     n1 ^= f(n2+key[0]);
  178.  
  179.     /* There is no swap after the last round */
  180.     out[0] = n2;
  181.     out[1] = n1;
  182. }
  183.     
  184.  
  185. /*
  186.  * The key schedule is somewhat different for decryption.
  187.  * (The key table is used once forward and three times backward.)
  188.  * You could define an expanded key, or just write the code twice,
  189.  * as done here.
  190.  */
  191. void
  192. gostdecrypt(word32 const in[2], word32 out[2], word32 const key[8])
  193. {
  194.     register word32 n1, n2; /* As named in the GOST */
  195.  
  196.     n1 = in[0];
  197.     n2 = in[1];
  198.  
  199.     n2 ^= f(n1+key[0]);
  200.     n1 ^= f(n2+key[1]);
  201.     n2 ^= f(n1+key[2]);
  202.     n1 ^= f(n2+key[3]);
  203.     n2 ^= f(n1+key[4]);
  204.     n1 ^= f(n2+key[5]);
  205.     n2 ^= f(n1+key[6]);
  206.     n1 ^= f(n2+key[7]);
  207.  
  208.     n2 ^= f(n1+key[7]);
  209.     n1 ^= f(n2+key[6]);
  210.     n2 ^= f(n1+key[5]);
  211.     n1 ^= f(n2+key[4]);
  212.     n2 ^= f(n1+key[3]);
  213.     n1 ^= f(n2+key[2]);
  214.     n2 ^= f(n1+key[1]);
  215.     n1 ^= f(n2+key[0]);
  216.  
  217.     n2 ^= f(n1+key[7]);
  218.     n1 ^= f(n2+key[6]);
  219.     n2 ^= f(n1+key[5]);
  220.     n1 ^= f(n2+key[4]);
  221.     n2 ^= f(n1+key[3]);
  222.     n1 ^= f(n2+key[2]);
  223.     n2 ^= f(n1+key[1]);
  224.     n1 ^= f(n2+key[0]);
  225.  
  226.     n2 ^= f(n1+key[7]);
  227.     n1 ^= f(n2+key[6]);
  228.     n2 ^= f(n1+key[5]);
  229.     n1 ^= f(n2+key[4]);
  230.     n2 ^= f(n1+key[3]);
  231.     n1 ^= f(n2+key[2]);
  232.     n2 ^= f(n1+key[1]);
  233.     n1 ^= f(n2+key[0]);
  234.  
  235.     out[0] = n2;
  236.     out[1] = n1;
  237. }
  238.  
  239. /*
  240.  * The GOST "Output feedback" standard.  It seems closer morally
  241.  * to the counter feedback mode some people have proposed for DES.
  242.  * The avoidance of the short cycles that are possible in OFB seems
  243.  * like a Good Thing.
  244.  *
  245.  * Calling it the stream mode makes more sense.
  246.  *
  247.  * The IV is encrypted with the key to produce the initial counter value.
  248.  * Then, for each output block, a constant is added, modulo 2^32-1
  249.  * (0 is represented as all-ones, not all-zeros), to each half of
  250.  * the counter, and the counter is encrypted to produce the value
  251.  * to XOR with the output.
  252.  *
  253.  * Len is the number of blocks.  Sub-block encryption is
  254.  * left as an exercise for the user.  Remember that the
  255.  * standard defines everything in a little-endian manner,
  256.  * so you want to use the low bit of gamma[0] first.
  257.  *
  258.  * OFB is, of course, self-inverse, so there is only one function.
  259.  */
  260.  
  261. /* The constants for addition */
  262. #define C1 0x01010104
  263. #define C2 0x01010101
  264.  
  265. void
  266. gostofb(word32 const *in, word32 *out, int len,
  267.     word32 const iv[2], word32 const key[8])
  268. {
  269.     word32 temp[2];         /* Counter */
  270.     word32 gamma[2];        /* Output XOR value */
  271.  
  272.     /* Compute starting value for counter */
  273.     gostcrypt(iv, temp, key);
  274.  
  275.     while (len--) {
  276.         temp[0] += C2;
  277.         if (temp[0] < C2)       /* Wrap modulo 2^32? */
  278.             temp[0]++;      /* Make it modulo 2^32-1 */
  279.         temp[1] += C1;
  280.         if (temp[1] < C1)       /* Wrap modulo 2^32? */
  281.             temp[1]++;      /* Make it modulo 2^32-1 */
  282.  
  283.         gostcrypt(temp, gamma, key);
  284.  
  285.         *out++ = *in++ ^ gamma[0];
  286.         *out++ = *in++ ^ gamma[1];
  287.     }
  288. }
  289.  
  290. /*
  291.  * The CFB mode is just what you'd expect.  Each block of ciphertext y[] is
  292.  * derived from the input x[] by the following pseudocode:
  293.  * y[i] = x[i] ^ gostcrypt(y[i-1])
  294.  * x[i] = y[i] ^ gostcrypt(y[i-1])
  295.  * Where y[-1] is the IV.
  296.  *
  297.  * The IV is modified in place.  Again, len is in *blocks*.
  298.  */
  299.  
  300. void
  301. gostcfbencrypt(word32 const *in, word32 *out, int len,
  302.            word32 iv[2], word32 const key[8])
  303. {
  304.     while (len--) {
  305.         gostcrypt(iv, iv, key);
  306.         iv[0] = *out++ ^= iv[0];
  307.         iv[1] = *out++ ^= iv[1];
  308.     }
  309. }
  310.  
  311. void
  312. gostcfbdecrypt(word32 const *in, word32 *out, int len,
  313.            word32 iv[2], word32 const key[8])
  314. {
  315.     word32 t;
  316.     while (len--) {
  317.         gostcrypt(iv, iv, key);
  318.         t = *out;
  319.         *out++ ^= iv[0];
  320.         iv[0] = t;
  321.         t = *out;
  322.         *out++ ^= iv[1];
  323.         iv[1] = t;
  324.     }
  325. }
  326.  
  327.  
  328. /*
  329.  * The message suthetication code uses only 16 of the 32 rounds.
  330.  * There *is* a swap after the 16th round.
  331.  * The last block should be padded to 64 bits with zeros.
  332.  * len is the number of *blocks* in the input.
  333.  */
  334. void
  335. gostmac(word32 const *in, int len, word32 out[2], word32 const key[8])
  336. {
  337.     register word32 n1, n2; /* As named in the GOST */
  338.  
  339.     n1 = 0;
  340.     n2 = 0;
  341.  
  342.     while (len--) {
  343.         n1 ^= *in++;
  344.         n2 = *in++;
  345.  
  346.         /* Instead of swapping halves, swap names each round */
  347.         n2 ^= f(n1+key[0]);
  348.         n1 ^= f(n2+key[1]);
  349.         n2 ^= f(n1+key[2]);
  350.         n1 ^= f(n2+key[3]);
  351.         n2 ^= f(n1+key[4]);
  352.         n1 ^= f(n2+key[5]);
  353.         n2 ^= f(n1+key[6]);
  354.         n1 ^= f(n2+key[7]);
  355.  
  356.         n2 ^= f(n1+key[0]);
  357.         n1 ^= f(n2+key[1]);
  358.         n2 ^= f(n1+key[2]);
  359.         n1 ^= f(n2+key[3]);
  360.         n2 ^= f(n1+key[4]);
  361.         n1 ^= f(n2+key[5]);
  362.         n2 ^= f(n1+key[6]);
  363.         n1 ^= f(n2+key[7]);
  364.     }
  365.  
  366.     out[0] = n1;
  367.     out[1] = n2;
  368. }
  369.  
  370. #ifdef TEST
  371.  
  372. #include <stdio.h>
  373. #include <stdlib.h>
  374.  
  375. /* Designed to cope with 15-bit rand() implementations */
  376. #define RAND32 ((word32)rand() << 17 ^ (word32)rand() << 9 ^ rand())
  377.  
  378. int
  379. main(void)
  380. {
  381.     word32 key[8];
  382.     word32 plain[2];
  383.     word32 cipher[2];
  384.     int i, j;
  385.  
  386.     kboxinit();
  387.  
  388.     printf("GOST 21847-89 test driver.\n");
  389.  
  390.     for (i = 0; i < 1000; i++) {
  391.         for (j = 0; j < 8; j++)
  392.             key[j] = RAND32;
  393.         plain[0] = RAND32;
  394.         plain[1] = RAND32;
  395.  
  396.         printf("%3d\r", i);
  397.         fflush(stdout);
  398.  
  399.         gostcrypt(plain, cipher, key);
  400.         for (j = 0; j < 99; j++)
  401.             gostcrypt(cipher, cipher, key);
  402.         for (j = 0; j < 100; j++)
  403.             gostdecrypt(cipher, cipher, key);
  404.  
  405.         if (plain[0] != cipher[0] || plain[1] != cipher[1]) {
  406.             fprintf(stderr, "\nError! i = %d\n", i);
  407.             return 1;
  408.         }
  409.     }
  410.     printf("All tests passed.\n");
  411.     return 0;
  412. }
  413.  
  414. #endif /* TEST */
  415.  
  416.