_ Git - shamirs/blob - shamirssecret.c

   1 #include <stdint.h>
   2 #include <assert.h>
   3
   4 #include "shamirssecret.h"
   5
   6 /*
   7  * Calculations across the finite field GF(2^8)
   8  */
   9
  10 #ifndef TEST
  11 static uint8_t field_add(uint8_t a, uint8_t b) {
  12         return a ^ b;
  13 }
  14
  15 static uint8_t field_sub(uint8_t a, uint8_t b) {
  16         return a ^ b;
  17 }
  18
  19 static uint8_t field_neg(uint8_t a) {
  20         return field_sub(0, a);
  21 }
  22 #endif
  23
  24 static const uint8_t exp[P] = {
  25         0x01, 0x03, 0x05, 0x0f, 0x11, 0x33, 0x55, 0xff, 0x1a, 0x2e, 0x72, 0x96, 0xa1, 0xf8, 0x13, 0x35,
  26         0x5f, 0xe1, 0x38, 0x48, 0xd8, 0x73, 0x95, 0xa4, 0xf7, 0x02, 0x06, 0x0a, 0x1e, 0x22, 0x66, 0xaa,
  27         0xe5, 0x34, 0x5c, 0xe4, 0x37, 0x59, 0xeb, 0x26, 0x6a, 0xbe, 0xd9, 0x70, 0x90, 0xab, 0xe6, 0x31,
  28         0x53, 0xf5, 0x04, 0x0c, 0x14, 0x3c, 0x44, 0xcc, 0x4f, 0xd1, 0x68, 0xb8, 0xd3, 0x6e, 0xb2, 0xcd,
  29         0x4c, 0xd4, 0x67, 0xa9, 0xe0, 0x3b, 0x4d, 0xd7, 0x62, 0xa6, 0xf1, 0x08, 0x18, 0x28, 0x78, 0x88,
  30         0x83, 0x9e, 0xb9, 0xd0, 0x6b, 0xbd, 0xdc, 0x7f, 0x81, 0x98, 0xb3, 0xce, 0x49, 0xdb, 0x76, 0x9a,
  31         0xb5, 0xc4, 0x57, 0xf9, 0x10, 0x30, 0x50, 0xf0, 0x0b, 0x1d, 0x27, 0x69, 0xbb, 0xd6, 0x61, 0xa3,
  32         0xfe, 0x19, 0x2b, 0x7d, 0x87, 0x92, 0xad, 0xec, 0x2f, 0x71, 0x93, 0xae, 0xe9, 0x20, 0x60, 0xa0,
  33         0xfb, 0x16, 0x3a, 0x4e, 0xd2, 0x6d, 0xb7, 0xc2, 0x5d, 0xe7, 0x32, 0x56, 0xfa, 0x15, 0x3f, 0x41,
  34         0xc3, 0x5e, 0xe2, 0x3d, 0x47, 0xc9, 0x40, 0xc0, 0x5b, 0xed, 0x2c, 0x74, 0x9c, 0xbf, 0xda, 0x75,
  35         0x9f, 0xba, 0xd5, 0x64, 0xac, 0xef, 0x2a, 0x7e, 0x82, 0x9d, 0xbc, 0xdf, 0x7a, 0x8e, 0x89, 0x80,
  36         0x9b, 0xb6, 0xc1, 0x58, 0xe8, 0x23, 0x65, 0xaf, 0xea, 0x25, 0x6f, 0xb1, 0xc8, 0x43, 0xc5, 0x54,
  37         0xfc, 0x1f, 0x21, 0x63, 0xa5, 0xf4, 0x07, 0x09, 0x1b, 0x2d, 0x77, 0x99, 0xb0, 0xcb, 0x46, 0xca,
  38         0x45, 0xcf, 0x4a, 0xde, 0x79, 0x8b, 0x86, 0x91, 0xa8, 0xe3, 0x3e, 0x42, 0xc6, 0x51, 0xf3, 0x0e,
  39         0x12, 0x36, 0x5a, 0xee, 0x29, 0x7b, 0x8d, 0x8c, 0x8f, 0x8a, 0x85, 0x94, 0xa7, 0xf2, 0x0d, 0x17,
  40         0x39, 0x4b, 0xdd, 0x7c, 0x84, 0x97, 0xa2, 0xfd, 0x1c, 0x24, 0x6c, 0xb4, 0xc7, 0x52, 0xf6, 0x01};
  41 static const uint8_t log[P] = {
  42         0x00, // log(0) is not defined
  43         0xff, 0x19, 0x01, 0x32, 0x02, 0x1a, 0xc6, 0x4b, 0xc7, 0x1b, 0x68, 0x33, 0xee, 0xdf, 0x03, 0x64,
  44         0x04, 0xe0, 0x0e, 0x34, 0x8d, 0x81, 0xef, 0x4c, 0x71, 0x08, 0xc8, 0xf8, 0x69, 0x1c, 0xc1, 0x7d,
  45         0xc2, 0x1d, 0xb5, 0xf9, 0xb9, 0x27, 0x6a, 0x4d, 0xe4, 0xa6, 0x72, 0x9a, 0xc9, 0x09, 0x78, 0x65,
  46         0x2f, 0x8a, 0x05, 0x21, 0x0f, 0xe1, 0x24, 0x12, 0xf0, 0x82, 0x45, 0x35, 0x93, 0xda, 0x8e, 0x96,
  47         0x8f, 0xdb, 0xbd, 0x36, 0xd0, 0xce, 0x94, 0x13, 0x5c, 0xd2, 0xf1, 0x40, 0x46, 0x83, 0x38, 0x66,
  48         0xdd, 0xfd, 0x30, 0xbf, 0x06, 0x8b, 0x62, 0xb3, 0x25, 0xe2, 0x98, 0x22, 0x88, 0x91, 0x10, 0x7e,
  49         0x6e, 0x48, 0xc3, 0xa3, 0xb6, 0x1e, 0x42, 0x3a, 0x6b, 0x28, 0x54, 0xfa, 0x85, 0x3d, 0xba, 0x2b,
  50         0x79, 0x0a, 0x15, 0x9b, 0x9f, 0x5e, 0xca, 0x4e, 0xd4, 0xac, 0xe5, 0xf3, 0x73, 0xa7, 0x57, 0xaf,
  51         0x58, 0xa8, 0x50, 0xf4, 0xea, 0xd6, 0x74, 0x4f, 0xae, 0xe9, 0xd5, 0xe7, 0xe6, 0xad, 0xe8, 0x2c,
  52         0xd7, 0x75, 0x7a, 0xeb, 0x16, 0x0b, 0xf5, 0x59, 0xcb, 0x5f, 0xb0, 0x9c, 0xa9, 0x51, 0xa0, 0x7f,
  53         0x0c, 0xf6, 0x6f, 0x17, 0xc4, 0x49, 0xec, 0xd8, 0x43, 0x1f, 0x2d, 0xa4, 0x76, 0x7b, 0xb7, 0xcc,
  54         0xbb, 0x3e, 0x5a, 0xfb, 0x60, 0xb1, 0x86, 0x3b, 0x52, 0xa1, 0x6c, 0xaa, 0x55, 0x29, 0x9d, 0x97,
  55         0xb2, 0x87, 0x90, 0x61, 0xbe, 0xdc, 0xfc, 0xbc, 0x95, 0xcf, 0xcd, 0x37, 0x3f, 0x5b, 0xd1, 0x53,
  56         0x39, 0x84, 0x3c, 0x41, 0xa2, 0x6d, 0x47, 0x14, 0x2a, 0x9e, 0x5d, 0x56, 0xf2, 0xd3, 0xab, 0x44,
  57         0x11, 0x92, 0xd9, 0x23, 0x20, 0x2e, 0x89, 0xb4, 0x7c, 0xb8, 0x26, 0x77, 0x99, 0xe3, 0xa5, 0x67,
  58         0x4a, 0xed, 0xde, 0xc5, 0x31, 0xfe, 0x18, 0x0d, 0x63, 0x8c, 0x80, 0xc0, 0xf7, 0x70, 0x07};
  59
  60 // We disable lots of optimizations that result in non-constant runtime (+/- branch delays)
  61 static uint8_t field_mul_ret(uint8_t calc, uint8_t a, uint8_t b) __attribute__((optimize("-O0"))) __attribute__((noinline));
  62 static uint8_t field_mul_ret(uint8_t calc, uint8_t a, uint8_t b) {
  63         uint8_t ret, ret2;
  64         if (a == 0)
  65                 ret2 = 0;
  66         else
  67                 ret2 = calc;
  68         if (b == 0)
  69                 ret = 0;
  70         else
  71                 ret = ret2;
  72         return ret;
  73 }
  74 static uint8_t field_mul(uint8_t a, uint8_t b)  {
  75         return field_mul_ret(exp[(log[a] + log[b]) % 255], a, b);
  76 }
  77
  78 static uint8_t field_invert(uint8_t a) {
  79         assert(a != 0);
  80         return exp[0xff - log[a]]; // log[1] == 0xff
  81 }
  82
  83 // We disable lots of optimizations that result in non-constant runtime (+/- branch delays)
  84 static uint8_t field_pow_ret(uint8_t calc, uint8_t a, uint8_t e) __attribute__((optimize("-O0"))) __attribute__((noinline));
  85 static uint8_t field_pow_ret(uint8_t calc, uint8_t a, uint8_t e) {
  86         uint8_t ret, ret2;
  87         if (a == 0)
  88                 ret2 = 0;
  89         else
  90                 ret2 = calc;
  91         if (e == 0)
  92                 ret = 1;
  93         else
  94                 ret = ret2;
  95         return ret;
  96 }
  97 static uint8_t field_pow(uint8_t a, uint8_t e) {
  98 #ifndef TEST
  99         // Although this function works for a==0, its not trivially obvious why,
 100         // and since we never call with a==0, we just assert a != 0 (except when testing)
 101         assert(a != 0);
 102 #endif
 103         return field_pow_ret(exp[(log[a] * e) % 255], a, e);
 104 }
 105
 106 #ifdef TEST
 107 static uint8_t field_mul_calc(uint8_t a, uint8_t b) {
 108         // side-channel attacks here
 109         uint8_t ret = 0;
 110         uint8_t counter;
 111         uint8_t carry;
 112         for (counter = 0; counter < 8; counter++) {
 113                 if (b & 1)
 114                         ret ^= a;
 115                 carry = (a & 0x80);
 116                 a <<= 1;
 117                 if (carry)
 118                         a ^= 0x1b; // what x^8 is modulo x^8 + x^4 + x^3 + x + 1
 119                 b >>= 1;
 120         }
 121         return ret;
 122 }
 123 static uint8_t field_pow_calc(uint8_t a, uint8_t e) {
 124         uint8_t ret = 1;
 125         for (uint8_t i = 0; i < e; i++)
 126                 ret = field_mul_calc(ret, a);
 127         return ret;
 128 }
 129 int main() {
 130         // Test inversion with the logarithm tables
 131         for (uint16_t i = 1; i < P; i++)
 132                 assert(field_mul_calc(i, field_invert(i)) == 1);
 133
 134         // Test multiplication with the logarithm tables
 135         for (uint16_t i = 0; i < P; i++) {
 136                 for (uint16_t j = 0; j < P; j++)
 137                         assert(field_mul(i, j) == field_mul_calc(i, j));
 138         }
 139
 140         // Test exponentiation with the logarithm tables
 141         for (uint16_t i = 0; i < P; i++) {
 142                 for (uint16_t j = 0; j < P; j++)
 143                         assert(field_pow(i, j) == field_pow_calc(i, j));
 144         }
 145 }
 146 #endif // defined(TEST)
 147
 148
 149
 150 /*
 151  * Calculations across the polynomial q
 152  */
 153 #ifndef TEST
 154 /**
 155  * Calculates the Y coordinate that the point with the given X
 156  * coefficients[0] == secret, the rest are random values
 157  */
 158 uint8_t calculateQ(uint8_t coefficients[], uint8_t shares_required, uint8_t x) {
 159         assert(x != 0); // q(0) == secret, though so does a[0]
 160         uint8_t ret = coefficients[0];
 161         for (uint8_t i = 1; i < shares_required; i++) {
 162                 ret = field_add(ret, field_mul(coefficients[i], field_pow(x, i)));
 163         }
 164         return ret;
 165 }
 166
 167 /**
 168  * Derives the secret given a set of shares_required points (x and q coordinates)
 169  */
 170 uint8_t calculateSecret(uint8_t x[], uint8_t q[], uint8_t shares_required) {
 171         // Calculate the x^0 term using a derivation of the forumula at
 172         // http://en.wikipedia.org/wiki/Lagrange_polynomial#Example_2
 173         uint8_t ret = 0;
 174         for (uint8_t i = 0; i < shares_required; i++) {
 175                 uint8_t temp = q[i];
 176                 for (uint8_t j = 0; j < shares_required; j++) {
 177                         if (i == j)
 178                                 continue;
 179                         temp = field_mul(temp, field_neg(x[j]));
 180                         temp = field_mul(temp, field_invert(field_sub(x[i], x[j])));
 181                 }
 182                 ret = field_add(ret, temp);
 183         }
 184         return ret;
 185 }
 186 #endif // !defined(TEST)