Lagrange Interpolation for finite field GF(2^8), for Secret Reconstruction

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.

My Questions

1. 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?
2. Is there anything wrong with my approach to finding the Secret $D$?

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;
}

-
1. It's the other way around, 0-x is really -x, and y-x is really y+(-x). Addition can be represented as xor in binary fields, but that doesn't work in fields whose characteristic is not two. – Ricky Demer Aug 26 '13 at 6:49
So in the case of GF(2^8), addition and subtraction are both XOR yes? – jatcwang Aug 26 '13 at 7:58
I see what you mean now, sorry it was misleading. Edited to clarify. – jatcwang Aug 26 '13 at 8:10
If you're using operator overloading to implement Galois field arithmetic, remember that you need to overload addition and subtraction too. And don't forget to overload the non-assignment versions of the operators, either. – Ilmari Karonen Aug 26 '13 at 13:25
This question appears to be off-topic because it is about code review. Code review is out of scope for this site; see meta.crypto.stackexchange.com/q/303/351. – D.W. Aug 26 '13 at 18:50

I now see your problem; it's more fundamental than what my previous answer assumed. You state:

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

where you interpret "should work" as "coming up with the exact same answer".

Actually, that's not the case. Your original example appears to be designed in the infinite field $Q$ (or some superfield); you then use the exact same shares, reinterpret them as $GF(2^8)$ points (in some unspecified representation), and then are confused that answers you get aren't precisely the same.

$Q$ and $GF(2^8)$ are both fields, but they are about as unlike as fields can get. For example:

$2+2=4$ (in the field $Q$)

$2+2=0$ (in the field $GF(2^8)$)

$3 \times 3 = 9$ (in the field $Q$)

$3 \times 3 = 5$ (in the field $GF(2^8)$, in the most common representation)

Your original shares $(1, 17)$, $(2, 34)$, $(3, 61)$ were computed in $Q$; if they were computed in $GF(2^8)$, they would have lhad different values. Therefore, it is not suprising that if you reconstruct them in a field other than what they were computed in, you'll come up with a different answer. I recomputed your shares using the original polynomial (assuming a polynomial representation of $GF(2^8)$), and came up with the values $(1, 13)$, $(2, 26)$, $(3, 29)$

To test your code, you'll need to come up with your own shares, computing in the field you're using to reconstruct.

(You'll also need to fix up your multiplication logic, in case one of the shares happen to be the value 0)

-
Correcto! Substituted it in and magic number 10 appears! Thanks for the answer. – jatcwang Aug 27 '13 at 0:03

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?

In any finite field, $-x$ is defined to be $0-x$, and in a field of characteristic two (which you are working with), yes, $-x = x$

Is there anything wrong with my approach to finding the Secret D?

Nothing immediately wrong springs to mind.

However, there is an obvious problem with your multiplication routine.

Multiplication in $GF(2^8)$ (actually, any field) has $0 \otimes x = x \otimes 0 = 0$; that is, if either multiplicand is 0, the result is 0. This doesn't fit into the log-table logic you're using, and so needs to be handled as a special case:

GF256elm& GF256elm::operator*=(const GF256elm& other) {
if (val == 0 || other.val == 0)
val = 0;
else {
int t = _logTable[val] - _logTable[other.val];
...


The same issue arises in your division routine if val is 0; that needs to be handled separately (and if the value you're dividing by is 0, well, that's obviously an error; $x/0$ is no more defined in a finite field than it is in any other field).

I'm not sure this is the only problem you have (e.g. have you defined an operator- and an operator/ ?); however until you fixed the above problem, it's pointless to speculate.

-
Oh yes that! I'm aware of it, but since I have guards elsewhere in the code it's not in the code yet. I have implemented all binary operators like /,*,+,-, they are directly based on their corresponding /=, *= etc. (As suggested by operator override guidelines) – jatcwang Aug 26 '13 at 13:47
@poncho : $\;\;\;$ I can cite Wikipedia and Wolfram Mathworld for the position that, at least in general fields, subtraction is defined in terms of the additive inverse operation. $\:$ I do not see any indication on either of those site's finite field pages that it's the other way around for finite fields. $\:$ Do you have a reference for the additive inverse operation being defined in terms of subtraction, at least for finite fields? $\hspace{.8 in}$ – Ricky Demer Aug 27 '13 at 8:15

In addition to the other bugs in your code that others have pointed out, you forgot to provide an overloaded implementation for the subtraction operator -- you use subtraction in your code, but you haven't provided an appropriate implementation of it for $GF(2^8)$ arithmetic. This will mess you up.

Kudos to Ilmari Karonen and poncho for both spotting this.

In general, this site is not the place for code review.

-
I tried to keep the question concise, and at no point I asked for a code review. I came to check my theory/approach and it is indeed where the my problem is. – jatcwang Aug 27 '13 at 0:06