I have been reading about Shamir\'s secret sharing, and maybe i completely misun

Question

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.

Explanation / Answer

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.

Related Questions

Navigate

• Browse (All)
• Browse I
• Subjects

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.