4 #include "shamirssecret.h"
7 * Calculations across the finite field GF(2^8)
11 static uint8_t field_add(uint8_t a, uint8_t b) {
15 static uint8_t field_sub(uint8_t a, uint8_t b) {
19 static uint8_t field_neg(uint8_t a) {
20 return field_sub(0, a);
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};
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) {
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);
78 static uint8_t field_invert(uint8_t a) {
80 return exp[0xff - log[a]]; // log[1] == 0xff
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) {
97 static uint8_t field_pow(uint8_t a, uint8_t e) {
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)
103 return field_pow_ret(exp[(log[a] * e) % 255], a, e);
107 static uint8_t field_mul_calc(uint8_t a, uint8_t b) {
108 // side-channel attacks here
112 for (counter = 0; counter < 8; counter++) {
118 a ^= 0x1b; // what x^8 is modulo x^8 + x^4 + x^3 + x + 1
123 static uint8_t field_pow_calc(uint8_t a, uint8_t e) {
125 for (uint8_t i = 0; i < e; i++)
126 ret = field_mul_calc(ret, a);
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);
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));
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));
146 #endif // defined(TEST)
151 * Calculations across the polynomial q
155 * Calculates the Y coordinate that the point with the given X
156 * coefficients[0] == secret, the rest are random values
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)));
168 * Derives the secret given a set of shares_required points (x and q coordinates)
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
174 for (uint8_t i = 0; i < shares_required; i++) {
176 for (uint8_t j = 0; j < shares_required; j++) {
179 temp = field_mul(temp, field_neg(x[j]));
180 temp = field_mul(temp, field_invert(field_sub(x[i], x[j])));
182 ret = field_add(ret, temp);
186 #endif // !defined(TEST)