1
$\begingroup$

I am implementing Shamir's secret sharing scheme on arbitrary binary files. I don't intend to use this; this is a project to help me explore cryptography. In setting up the finite field arithmetic, I chose my field to be GF(257).

My understanding is that a prime GF is needed to ensure that a single modular inverse exists for each value in the field (this conflicts with the answer to How can Shamir's method for secret sharing work in the GF(256)?).

Can someone explain this discrepancy?

|improve this question
$\endgroup$
  • 1
    $\begingroup$ You may be misinterpreting the notation: $\mathrm{GF}(256)$ is not the ring of integers modulo $256$; it is the unique (up to isomorphism) degree-$8$ extension of $\mathrm{GF}(2)$. In particular, it is a field, while $\mathbb Z/256$ contains lots of zero divisors. $\endgroup$ – yyyyyyy Aug 12 '17 at 18:22
2
$\begingroup$

You appear to be confused by the sentence in the answer:

If you use simple modular reduction they won't work (e.g. you can't just compute the operations mod 256).

This sentence is true, but doesn't mean what you think it does.

It doesn't mean that you can't compute inverses in $GF(256)$; instead, what it means is that you can't compute the addition and multiplication as $A + B \bmod 256$ and $A \times B \bmod 256$; other algorithms need to be used.

It happens that addition is easy; you can do it by doing a bitwise exclusive or; in C, that's A ^ B

Multiplication and inverses are a bit trickier; however, I can point you to the answer here that addresses how to do with with a few table lookups

|improve this answer
$\endgroup$
  • $\begingroup$ Further question - as the input is within [0, 255], I was wondering if I could do a workaround. Instead of implementing this in GF(256), could you generate a polynomial, test to see if the shares/shadows are in [0, 255], and regenerate the polynomial if that's not the case? Would that have any impact on the security of the algorithm? $\endgroup$ – brennonbrimhall Aug 13 '17 at 0:17
  • 1
    $\begingroup$ @brennonbrimhall: that absolutely would compromise the security of the algorithm. For example, if we had a scheme with threshold=2, and the attacker held the share at $x=1$, and he also know that there were participants with $x=2, 3, 4, 5$, even if he didn't know the values of the shares, he could exclude any secret value that would imply a value of 256 at any of those 4 $x$ coordinates. As he doesn't hold threshold shares, he is not supposed to deduce anything about the secret. $\endgroup$ – poncho Aug 13 '17 at 1:53

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.