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