2 * Shamir's secret sharing sharing implementation
4 * Copyright (C) 2013 Matt Corallo <git@bluematt.me>
6 * This program is free software; you can redistribute it and/or modify it
7 * under the terms and conditions of the GNU General Public License,
8 * version 2, as published by the Free Software Foundation.
10 * This program is distributed in the hope it will be useful, but WITHOUT
11 * ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or
12 * FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License for
15 * You should have received a copy of the GNU General Public License along with
16 * this program; if not, write to the Free Software Foundation, Inc., 59 Temple
17 * Place - Suite 330, Boston, MA 02111-1307 USA.
24 #define CHECKSTATE(x) assert(x)
26 #include <linux/bug.h>
27 #define CHECKSTATE(x) BUG_ON(x)
30 #include "shamirssecret.h"
33 * Calculations across the finite field GF(2^8)
37 static uint8_t field_add(uint8_t a, uint8_t b) {
41 static uint8_t field_sub(uint8_t a, uint8_t b) {
45 static uint8_t field_neg(uint8_t a) {
46 return field_sub(0, a);
50 //TODO: Using static tables will very likely create side-channel attacks when measuring cache hits
51 // Because these are fairly small tables, we can probably get them loaded mostly/fully into
52 // cache before use to break such attacks.
53 static const uint8_t exp[P] = {
54 0x01, 0x03, 0x05, 0x0f, 0x11, 0x33, 0x55, 0xff, 0x1a, 0x2e, 0x72, 0x96, 0xa1, 0xf8, 0x13, 0x35,
55 0x5f, 0xe1, 0x38, 0x48, 0xd8, 0x73, 0x95, 0xa4, 0xf7, 0x02, 0x06, 0x0a, 0x1e, 0x22, 0x66, 0xaa,
56 0xe5, 0x34, 0x5c, 0xe4, 0x37, 0x59, 0xeb, 0x26, 0x6a, 0xbe, 0xd9, 0x70, 0x90, 0xab, 0xe6, 0x31,
57 0x53, 0xf5, 0x04, 0x0c, 0x14, 0x3c, 0x44, 0xcc, 0x4f, 0xd1, 0x68, 0xb8, 0xd3, 0x6e, 0xb2, 0xcd,
58 0x4c, 0xd4, 0x67, 0xa9, 0xe0, 0x3b, 0x4d, 0xd7, 0x62, 0xa6, 0xf1, 0x08, 0x18, 0x28, 0x78, 0x88,
59 0x83, 0x9e, 0xb9, 0xd0, 0x6b, 0xbd, 0xdc, 0x7f, 0x81, 0x98, 0xb3, 0xce, 0x49, 0xdb, 0x76, 0x9a,
60 0xb5, 0xc4, 0x57, 0xf9, 0x10, 0x30, 0x50, 0xf0, 0x0b, 0x1d, 0x27, 0x69, 0xbb, 0xd6, 0x61, 0xa3,
61 0xfe, 0x19, 0x2b, 0x7d, 0x87, 0x92, 0xad, 0xec, 0x2f, 0x71, 0x93, 0xae, 0xe9, 0x20, 0x60, 0xa0,
62 0xfb, 0x16, 0x3a, 0x4e, 0xd2, 0x6d, 0xb7, 0xc2, 0x5d, 0xe7, 0x32, 0x56, 0xfa, 0x15, 0x3f, 0x41,
63 0xc3, 0x5e, 0xe2, 0x3d, 0x47, 0xc9, 0x40, 0xc0, 0x5b, 0xed, 0x2c, 0x74, 0x9c, 0xbf, 0xda, 0x75,
64 0x9f, 0xba, 0xd5, 0x64, 0xac, 0xef, 0x2a, 0x7e, 0x82, 0x9d, 0xbc, 0xdf, 0x7a, 0x8e, 0x89, 0x80,
65 0x9b, 0xb6, 0xc1, 0x58, 0xe8, 0x23, 0x65, 0xaf, 0xea, 0x25, 0x6f, 0xb1, 0xc8, 0x43, 0xc5, 0x54,
66 0xfc, 0x1f, 0x21, 0x63, 0xa5, 0xf4, 0x07, 0x09, 0x1b, 0x2d, 0x77, 0x99, 0xb0, 0xcb, 0x46, 0xca,
67 0x45, 0xcf, 0x4a, 0xde, 0x79, 0x8b, 0x86, 0x91, 0xa8, 0xe3, 0x3e, 0x42, 0xc6, 0x51, 0xf3, 0x0e,
68 0x12, 0x36, 0x5a, 0xee, 0x29, 0x7b, 0x8d, 0x8c, 0x8f, 0x8a, 0x85, 0x94, 0xa7, 0xf2, 0x0d, 0x17,
69 0x39, 0x4b, 0xdd, 0x7c, 0x84, 0x97, 0xa2, 0xfd, 0x1c, 0x24, 0x6c, 0xb4, 0xc7, 0x52, 0xf6, 0x01};
70 static const uint8_t log[P] = {
71 0x00, // log(0) is not defined
72 0xff, 0x19, 0x01, 0x32, 0x02, 0x1a, 0xc6, 0x4b, 0xc7, 0x1b, 0x68, 0x33, 0xee, 0xdf, 0x03, 0x64,
73 0x04, 0xe0, 0x0e, 0x34, 0x8d, 0x81, 0xef, 0x4c, 0x71, 0x08, 0xc8, 0xf8, 0x69, 0x1c, 0xc1, 0x7d,
74 0xc2, 0x1d, 0xb5, 0xf9, 0xb9, 0x27, 0x6a, 0x4d, 0xe4, 0xa6, 0x72, 0x9a, 0xc9, 0x09, 0x78, 0x65,
75 0x2f, 0x8a, 0x05, 0x21, 0x0f, 0xe1, 0x24, 0x12, 0xf0, 0x82, 0x45, 0x35, 0x93, 0xda, 0x8e, 0x96,
76 0x8f, 0xdb, 0xbd, 0x36, 0xd0, 0xce, 0x94, 0x13, 0x5c, 0xd2, 0xf1, 0x40, 0x46, 0x83, 0x38, 0x66,
77 0xdd, 0xfd, 0x30, 0xbf, 0x06, 0x8b, 0x62, 0xb3, 0x25, 0xe2, 0x98, 0x22, 0x88, 0x91, 0x10, 0x7e,
78 0x6e, 0x48, 0xc3, 0xa3, 0xb6, 0x1e, 0x42, 0x3a, 0x6b, 0x28, 0x54, 0xfa, 0x85, 0x3d, 0xba, 0x2b,
79 0x79, 0x0a, 0x15, 0x9b, 0x9f, 0x5e, 0xca, 0x4e, 0xd4, 0xac, 0xe5, 0xf3, 0x73, 0xa7, 0x57, 0xaf,
80 0x58, 0xa8, 0x50, 0xf4, 0xea, 0xd6, 0x74, 0x4f, 0xae, 0xe9, 0xd5, 0xe7, 0xe6, 0xad, 0xe8, 0x2c,
81 0xd7, 0x75, 0x7a, 0xeb, 0x16, 0x0b, 0xf5, 0x59, 0xcb, 0x5f, 0xb0, 0x9c, 0xa9, 0x51, 0xa0, 0x7f,
82 0x0c, 0xf6, 0x6f, 0x17, 0xc4, 0x49, 0xec, 0xd8, 0x43, 0x1f, 0x2d, 0xa4, 0x76, 0x7b, 0xb7, 0xcc,
83 0xbb, 0x3e, 0x5a, 0xfb, 0x60, 0xb1, 0x86, 0x3b, 0x52, 0xa1, 0x6c, 0xaa, 0x55, 0x29, 0x9d, 0x97,
84 0xb2, 0x87, 0x90, 0x61, 0xbe, 0xdc, 0xfc, 0xbc, 0x95, 0xcf, 0xcd, 0x37, 0x3f, 0x5b, 0xd1, 0x53,
85 0x39, 0x84, 0x3c, 0x41, 0xa2, 0x6d, 0x47, 0x14, 0x2a, 0x9e, 0x5d, 0x56, 0xf2, 0xd3, 0xab, 0x44,
86 0x11, 0x92, 0xd9, 0x23, 0x20, 0x2e, 0x89, 0xb4, 0x7c, 0xb8, 0x26, 0x77, 0x99, 0xe3, 0xa5, 0x67,
87 0x4a, 0xed, 0xde, 0xc5, 0x31, 0xfe, 0x18, 0x0d, 0x63, 0x8c, 0x80, 0xc0, 0xf7, 0x70, 0x07};
89 // We disable lots of optimizations that result in non-constant runtime (+/- branch delays)
90 static uint8_t field_mul_ret(uint8_t calc, uint8_t a, uint8_t b) __attribute__((optimize("-O0"))) __attribute__((noinline));
91 static uint8_t field_mul_ret(uint8_t calc, uint8_t a, uint8_t b) {
103 static uint8_t field_mul(uint8_t a, uint8_t b) {
104 return field_mul_ret(exp[(log[a] + log[b]) % 255], a, b);
107 static uint8_t field_invert(uint8_t a) {
109 return exp[0xff - log[a]]; // log[1] == 0xff
112 // We disable lots of optimizations that result in non-constant runtime (+/- branch delays)
113 static uint8_t field_pow_ret(uint8_t calc, uint8_t a, uint8_t e) __attribute__((optimize("-O0"))) __attribute__((noinline));
114 static uint8_t field_pow_ret(uint8_t calc, uint8_t a, uint8_t e) {
126 static uint8_t field_pow(uint8_t a, uint8_t e) {
128 // Although this function works for a==0, its not trivially obvious why,
129 // and since we never call with a==0, we just assert a != 0 (except when testing)
132 return field_pow_ret(exp[(log[a] * e) % 255], a, e);
136 static uint8_t field_mul_calc(uint8_t a, uint8_t b) {
137 // side-channel attacks here
141 for (counter = 0; counter < 8; counter++) {
147 a ^= 0x1b; // what x^8 is modulo x^8 + x^4 + x^3 + x + 1
152 static uint8_t field_pow_calc(uint8_t a, uint8_t e) {
154 for (uint8_t i = 0; i < e; i++)
155 ret = field_mul_calc(ret, a);
159 // Test inversion with the logarithm tables
160 for (uint16_t i = 1; i < P; i++)
161 CHECKSTATE(field_mul_calc(i, field_invert(i)) == 1);
163 // Test multiplication with the logarithm tables
164 for (uint16_t i = 0; i < P; i++) {
165 for (uint16_t j = 0; j < P; j++)
166 CHECKSTATE(field_mul(i, j) == field_mul_calc(i, j));
169 // Test exponentiation with the logarithm tables
170 for (uint16_t i = 0; i < P; i++) {
171 for (uint16_t j = 0; j < P; j++)
172 CHECKSTATE(field_pow(i, j) == field_pow_calc(i, j));
175 #endif // defined(TEST)
180 * Calculations across the polynomial q
184 * Calculates the Y coordinate that the point with the given X
185 * coefficients[0] == secret, the rest are random values
187 uint8_t calculateQ(uint8_t coefficients[], uint8_t shares_required, uint8_t x) {
188 CHECKSTATE(x != 0); // q(0) == secret, though so does a[0]
189 uint8_t ret = coefficients[0];
190 for (uint8_t i = 1; i < shares_required; i++) {
191 ret = field_add(ret, field_mul(coefficients[i], field_pow(x, i)));
197 * Derives the secret given a set of shares_required points (x and q coordinates)
199 uint8_t calculateSecret(uint8_t x[], uint8_t q[], uint8_t shares_required) {
200 // Calculate the x^0 term using a derivation of the forumula at
201 // http://en.wikipedia.org/wiki/Lagrange_polynomial#Example_2
203 for (uint8_t i = 0; i < shares_required; i++) {
205 for (uint8_t j = 0; j < shares_required; j++) {
208 temp = field_mul(temp, field_neg(x[j]));
209 temp = field_mul(temp, field_invert(field_sub(x[i], x[j])));
211 ret = field_add(ret, temp);
215 #endif // !defined(TEST)