I'm using Lagrange's Interpolation technique to reconstruct the secret from a set of point pairs (x,y).
Since I only need the secret, not the whole polynomial, I have simplified the reconstruction process as follows:
Let Secret $D = 10$, and we use a 3 out of 3 secret sharing scheme which generates 3 key pairs
and all of them are needed to reconstruct the secret. We pick two random numbers as the coefficients. This gives us the polynomial $5x^2 + 2x + 10$. 3 Points are generated from the polynomial: $(1, 17)$, $(2, 34)$, $(3, 61)$ To get secret $D$, we only need to take care of the constant part of Lagrange's Polynomial. $$ \it{l}_{0} = \dfrac{(x-2)(x-3)}{(1-2)(1-3)} = \dfrac{(x-2)(x-3)}{2} $$ $$ \it{l}_{1} = \dfrac{(x-1)(x-3)}{(2-1)(2-3)} = \dfrac{(x-1)(x-3)}{-1} $$ $$ \it{l}_{2} = \dfrac{(x-1)(x-2)}{(3-1)(3-2)} = \dfrac{(x-1)(x-2)}{2} $$By only considering the constant part of Lagrange's Polynomial (ignore $x$es), we can calculate secret $D$:
$$ D = 17 \dfrac{(-2)(-3)}{2} + 34 \dfrac{(-1)(-3)}{-1} + 61 \dfrac{(-1)(-2)}{2} = 10 $$
which is our secret.
Now the same method should work for finite field GF(2^8) as long as the arithmetic are replaced with finite field arithmetic. However this is not the case:
unsigned int decodeByte(vector<pair<unsigned int, unsigned int>> keys) {
int numKeys = keys.size();
//extract the x's and y's from the vector
vector<int> x;
vector<int> y;
for (int i = 0; i < numKeys; i++) {
x.push_back(keys[i].first); //extract x
y.push_back(keys[i].second); //extract y
}
GF256elm result(0);
for (int i = 0; i < numKeys; ++i) {
//calculate the constant term of lagrange interpolation polynomial
GF256elm l(1);
for (int j = 0; j < numKeys; ++j) {
if (i == j)
continue;
GF256elm nxj = GF256elm(x[j]);
GF256elm xi = GF256elm(x[i]); //xj
GF256elm xj = GF256elm(x[j]); //xj
GF256elm ximxj = xi - xj; //xi - xj
GF256elm prod = nxj / ximxj; // (-xj)/(xi-xj)
l *= prod;
}
GF256elm product = GF256elm(y[i]) * l;
result += product;
}
return result.getVal();
}
Basically what I'm doing here is I'm calculating $\dfrac{-2}{1-2}$, then multiply it with $\dfrac{-3}{1-3}$, then multiplying everything by 17, (which is the y value from the first point $(1, 17)$). This is the first term in D's equation above. I then go on and calculate the other two terms.
Problem is, instead of 10, I get 14 as my answer.
My Questions
- In finite field arithmetic, negating x ($-x$) is really $0 - x$, which is actually $0 \oplus x$ (XOR), and it ends up being $x$ itself, am I right?
- Is there anything wrong with my approach to finding the Secret $D$?
Additional info:
My division and multiplication is implemented using table look up. This part of the code has been tested and its results are the same as other sources.
GF256elm& GF256elm::operator*=(const GF256elm& other) {
int temp = (_logTable[val] + _logTable[other.val]) % 255;
val = _expTable[temp];
return *this;
}
GF256elm& GF256elm::operator/=(const GF256elm& other) {
int t = _logTable[val] - _logTable[other.val];
int temp = ((t % 255) + 255) % 255;
val = _expTable[temp];
return *this;
}