4
$\begingroup$

I have been reading about Shamir's secret sharing, and maybe i completely misunderstand something, but the field is meant to be a prime. However, when i look at the implementations of this algorithm, they all use GF(256).

I do understand the beauty of such field, since that's the best compromise between the size of the chunk of the data and the number of keys that one can generate, but i was unable to find how they got around the requirement of a prime.

Alternatively, of course, i have misread something.

Improve this question
$\endgroup$
4
  • 2
    $\begingroup$ You can use any field. Prime order fields are nice because you can use standard modular arithmetic, whereas other fields are a bit tricky to understand. But fields exist for all prime powers p^n. The most common choices p=2 (binary fields like the 2^8 you're talking about) or n=1 (prime fields). $\endgroup$ – CodesInChaos Nov 26 '13 at 17:14
  • $\begingroup$ Ah, ok. You should have answered as an answer rather than a comment. I could accept that then. $\endgroup$ – Volodya Nov 26 '13 at 17:30
  • $\begingroup$ And if i understood you correctly GF(6) would not be allowed. $\endgroup$ – Volodya Nov 26 '13 at 17:34
  • 4
    $\begingroup$ Yes, there is no GF(6) since you can't write it as p^n. $\endgroup$ – CodesInChaos Nov 26 '13 at 17:37
7
$\begingroup$

Shamir's secret sharing works in any finite field. A field is a mathematical structure that follows the usual laws of addition and multiplication. A finite field is a field with a finite number of elements, unlike for example the real numbers, which have an infinite number of elements.

Fields exist for all prime powers pk where p is a prime and k a positive integer.

Prime order fields (k=1) are nice because you can use standard modular arithmetic. You add/multiply as usual, and apply the modulo operation in the end.

For other fields operations are slightly harder to understand. If you use simple modular reduction they won't work (e.g. you can't just compute the operations mod 256). Mathematically you use a reduction polynomial. In practice an implementation will use lookup tables.

The most common choices are binary fields with p=2 (including 256 = 28) and prime fields with k=1.

Improve this answer
$\endgroup$
2
  • $\begingroup$ The formulas would work in infinite fields (like the reals or the rationals), too, but it is difficult to do a (pseudo-)random distribution on them, therefore the secret would stay less secret. $\endgroup$ – Paŭlo Ebermann Nov 26 '13 at 20:05
  • 2
    $\begingroup$ @PaŭloEbermann: Shamir's secret sharing requires that the secret polynomial be selected from a uniform distribution; it turns out that's impossible for the rationals (or any other set of size $\aleph_0$). As for the reals, well, that can be defined, but the fact that you cannot express (almost all) elements in a finite number of bits is a bit of a drawback. Hence, in both cases, you could say that Shamir's secret sharing "doesn't work" $\endgroup$ – poncho Nov 26 '13 at 20:29

Your Answer

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