5 #define CHECKSTATE(x) assert(x)
8 #define CHECKSTATE(x) BUG_ON(x)
11 #include "shamirssecret.h"
14 * Calculations across the finite field GF(2^8)
18 static uint8_t field_add(uint8_t a, uint8_t b) {
22 static uint8_t field_sub(uint8_t a, uint8_t b) {
26 static uint8_t field_neg(uint8_t a) {
27 return field_sub(0, a);
31 //TODO: Using static tables will very likely create side-channel attacks when measuring cache hits
32 // Because these are fairly small tables, we can probably get them loaded mostly/fully into
33 // cache before use to break such attacks.
34 static const uint8_t exp[P] = {
35 0x01, 0x03, 0x05, 0x0f, 0x11, 0x33, 0x55, 0xff, 0x1a, 0x2e, 0x72, 0x96, 0xa1, 0xf8, 0x13, 0x35,
36 0x5f, 0xe1, 0x38, 0x48, 0xd8, 0x73, 0x95, 0xa4, 0xf7, 0x02, 0x06, 0x0a, 0x1e, 0x22, 0x66, 0xaa,
37 0xe5, 0x34, 0x5c, 0xe4, 0x37, 0x59, 0xeb, 0x26, 0x6a, 0xbe, 0xd9, 0x70, 0x90, 0xab, 0xe6, 0x31,
38 0x53, 0xf5, 0x04, 0x0c, 0x14, 0x3c, 0x44, 0xcc, 0x4f, 0xd1, 0x68, 0xb8, 0xd3, 0x6e, 0xb2, 0xcd,
39 0x4c, 0xd4, 0x67, 0xa9, 0xe0, 0x3b, 0x4d, 0xd7, 0x62, 0xa6, 0xf1, 0x08, 0x18, 0x28, 0x78, 0x88,
40 0x83, 0x9e, 0xb9, 0xd0, 0x6b, 0xbd, 0xdc, 0x7f, 0x81, 0x98, 0xb3, 0xce, 0x49, 0xdb, 0x76, 0x9a,
41 0xb5, 0xc4, 0x57, 0xf9, 0x10, 0x30, 0x50, 0xf0, 0x0b, 0x1d, 0x27, 0x69, 0xbb, 0xd6, 0x61, 0xa3,
42 0xfe, 0x19, 0x2b, 0x7d, 0x87, 0x92, 0xad, 0xec, 0x2f, 0x71, 0x93, 0xae, 0xe9, 0x20, 0x60, 0xa0,
43 0xfb, 0x16, 0x3a, 0x4e, 0xd2, 0x6d, 0xb7, 0xc2, 0x5d, 0xe7, 0x32, 0x56, 0xfa, 0x15, 0x3f, 0x41,
44 0xc3, 0x5e, 0xe2, 0x3d, 0x47, 0xc9, 0x40, 0xc0, 0x5b, 0xed, 0x2c, 0x74, 0x9c, 0xbf, 0xda, 0x75,
45 0x9f, 0xba, 0xd5, 0x64, 0xac, 0xef, 0x2a, 0x7e, 0x82, 0x9d, 0xbc, 0xdf, 0x7a, 0x8e, 0x89, 0x80,
46 0x9b, 0xb6, 0xc1, 0x58, 0xe8, 0x23, 0x65, 0xaf, 0xea, 0x25, 0x6f, 0xb1, 0xc8, 0x43, 0xc5, 0x54,
47 0xfc, 0x1f, 0x21, 0x63, 0xa5, 0xf4, 0x07, 0x09, 0x1b, 0x2d, 0x77, 0x99, 0xb0, 0xcb, 0x46, 0xca,
48 0x45, 0xcf, 0x4a, 0xde, 0x79, 0x8b, 0x86, 0x91, 0xa8, 0xe3, 0x3e, 0x42, 0xc6, 0x51, 0xf3, 0x0e,
49 0x12, 0x36, 0x5a, 0xee, 0x29, 0x7b, 0x8d, 0x8c, 0x8f, 0x8a, 0x85, 0x94, 0xa7, 0xf2, 0x0d, 0x17,
50 0x39, 0x4b, 0xdd, 0x7c, 0x84, 0x97, 0xa2, 0xfd, 0x1c, 0x24, 0x6c, 0xb4, 0xc7, 0x52, 0xf6, 0x01};
51 static const uint8_t log[P] = {
52 0x00, // log(0) is not defined
53 0xff, 0x19, 0x01, 0x32, 0x02, 0x1a, 0xc6, 0x4b, 0xc7, 0x1b, 0x68, 0x33, 0xee, 0xdf, 0x03, 0x64,
54 0x04, 0xe0, 0x0e, 0x34, 0x8d, 0x81, 0xef, 0x4c, 0x71, 0x08, 0xc8, 0xf8, 0x69, 0x1c, 0xc1, 0x7d,
55 0xc2, 0x1d, 0xb5, 0xf9, 0xb9, 0x27, 0x6a, 0x4d, 0xe4, 0xa6, 0x72, 0x9a, 0xc9, 0x09, 0x78, 0x65,
56 0x2f, 0x8a, 0x05, 0x21, 0x0f, 0xe1, 0x24, 0x12, 0xf0, 0x82, 0x45, 0x35, 0x93, 0xda, 0x8e, 0x96,
57 0x8f, 0xdb, 0xbd, 0x36, 0xd0, 0xce, 0x94, 0x13, 0x5c, 0xd2, 0xf1, 0x40, 0x46, 0x83, 0x38, 0x66,
58 0xdd, 0xfd, 0x30, 0xbf, 0x06, 0x8b, 0x62, 0xb3, 0x25, 0xe2, 0x98, 0x22, 0x88, 0x91, 0x10, 0x7e,
59 0x6e, 0x48, 0xc3, 0xa3, 0xb6, 0x1e, 0x42, 0x3a, 0x6b, 0x28, 0x54, 0xfa, 0x85, 0x3d, 0xba, 0x2b,
60 0x79, 0x0a, 0x15, 0x9b, 0x9f, 0x5e, 0xca, 0x4e, 0xd4, 0xac, 0xe5, 0xf3, 0x73, 0xa7, 0x57, 0xaf,
61 0x58, 0xa8, 0x50, 0xf4, 0xea, 0xd6, 0x74, 0x4f, 0xae, 0xe9, 0xd5, 0xe7, 0xe6, 0xad, 0xe8, 0x2c,
62 0xd7, 0x75, 0x7a, 0xeb, 0x16, 0x0b, 0xf5, 0x59, 0xcb, 0x5f, 0xb0, 0x9c, 0xa9, 0x51, 0xa0, 0x7f,
63 0x0c, 0xf6, 0x6f, 0x17, 0xc4, 0x49, 0xec, 0xd8, 0x43, 0x1f, 0x2d, 0xa4, 0x76, 0x7b, 0xb7, 0xcc,
64 0xbb, 0x3e, 0x5a, 0xfb, 0x60, 0xb1, 0x86, 0x3b, 0x52, 0xa1, 0x6c, 0xaa, 0x55, 0x29, 0x9d, 0x97,
65 0xb2, 0x87, 0x90, 0x61, 0xbe, 0xdc, 0xfc, 0xbc, 0x95, 0xcf, 0xcd, 0x37, 0x3f, 0x5b, 0xd1, 0x53,
66 0x39, 0x84, 0x3c, 0x41, 0xa2, 0x6d, 0x47, 0x14, 0x2a, 0x9e, 0x5d, 0x56, 0xf2, 0xd3, 0xab, 0x44,
67 0x11, 0x92, 0xd9, 0x23, 0x20, 0x2e, 0x89, 0xb4, 0x7c, 0xb8, 0x26, 0x77, 0x99, 0xe3, 0xa5, 0x67,
68 0x4a, 0xed, 0xde, 0xc5, 0x31, 0xfe, 0x18, 0x0d, 0x63, 0x8c, 0x80, 0xc0, 0xf7, 0x70, 0x07};
70 // We disable lots of optimizations that result in non-constant runtime (+/- branch delays)
71 static uint8_t field_mul_ret(uint8_t calc, uint8_t a, uint8_t b) __attribute__((optimize("-O0"))) __attribute__((noinline));
72 static uint8_t field_mul_ret(uint8_t calc, uint8_t a, uint8_t b) {
84 static uint8_t field_mul(uint8_t a, uint8_t b) {
85 return field_mul_ret(exp[(log[a] + log[b]) % 255], a, b);
88 static uint8_t field_invert(uint8_t a) {
90 return exp[0xff - log[a]]; // log[1] == 0xff
93 // We disable lots of optimizations that result in non-constant runtime (+/- branch delays)
94 static uint8_t field_pow_ret(uint8_t calc, uint8_t a, uint8_t e) __attribute__((optimize("-O0"))) __attribute__((noinline));
95 static uint8_t field_pow_ret(uint8_t calc, uint8_t a, uint8_t e) {
107 static uint8_t field_pow(uint8_t a, uint8_t e) {
109 // Although this function works for a==0, its not trivially obvious why,
110 // and since we never call with a==0, we just assert a != 0 (except when testing)
113 return field_pow_ret(exp[(log[a] * e) % 255], a, e);
117 static uint8_t field_mul_calc(uint8_t a, uint8_t b) {
118 // side-channel attacks here
122 for (counter = 0; counter < 8; counter++) {
128 a ^= 0x1b; // what x^8 is modulo x^8 + x^4 + x^3 + x + 1
133 static uint8_t field_pow_calc(uint8_t a, uint8_t e) {
135 for (uint8_t i = 0; i < e; i++)
136 ret = field_mul_calc(ret, a);
140 // Test inversion with the logarithm tables
141 for (uint16_t i = 1; i < P; i++)
142 CHECKSTATE(field_mul_calc(i, field_invert(i)) == 1);
144 // Test multiplication with the logarithm tables
145 for (uint16_t i = 0; i < P; i++) {
146 for (uint16_t j = 0; j < P; j++)
147 CHECKSTATE(field_mul(i, j) == field_mul_calc(i, j));
150 // Test exponentiation with the logarithm tables
151 for (uint16_t i = 0; i < P; i++) {
152 for (uint16_t j = 0; j < P; j++)
153 CHECKSTATE(field_pow(i, j) == field_pow_calc(i, j));
156 #endif // defined(TEST)
161 * Calculations across the polynomial q
165 * Calculates the Y coordinate that the point with the given X
166 * coefficients[0] == secret, the rest are random values
168 uint8_t calculateQ(uint8_t coefficients[], uint8_t shares_required, uint8_t x) {
169 CHECKSTATE(x != 0); // q(0) == secret, though so does a[0]
170 uint8_t ret = coefficients[0];
171 for (uint8_t i = 1; i < shares_required; i++) {
172 ret = field_add(ret, field_mul(coefficients[i], field_pow(x, i)));
178 * Derives the secret given a set of shares_required points (x and q coordinates)
180 uint8_t calculateSecret(uint8_t x[], uint8_t q[], uint8_t shares_required) {
181 // Calculate the x^0 term using a derivation of the forumula at
182 // http://en.wikipedia.org/wiki/Lagrange_polynomial#Example_2
184 for (uint8_t i = 0; i < shares_required; i++) {
186 for (uint8_t j = 0; j < shares_required; j++) {
189 temp = field_mul(temp, field_neg(x[j]));
190 temp = field_mul(temp, field_invert(field_sub(x[i], x[j])));
192 ret = field_add(ret, temp);
196 #endif // !defined(TEST)