# Shamir Secret Sharing GF(p) or GF(2^8)

I'm implementing Shamir's Secret Sharing Scheme, but I've hit a conceptual roadblock. In Shamir's paper "How To Share A Secret" he creates his shares an a finite field of order p, where p is some prime larger than both the secret and the number of shares. I understand why this needs to be done to ensure an even distribution of the shares. However, in nearly every implementation I've seen, GF(256) is used. I know that this is technically okay, since it is still GF(p^k), but why is this preferable to just using a prime field? In the prime field, only modular arithmetic is needed, but with GF(256), you end up writing a ton more code and it is much less intuitive.

• GF(256) is perfect when operating on bytes. Addition is just XOR in that field. Multiplication shouldn't be too hard to implement. Sep 11, 2016 at 1:00

I know that this is technically okay, since it is still GF(p^k), but why is this preferable to just using a prime field?

They have equivalent security; however the nice thing about $GF(2^8)$ is that everything ends up to be an integral number of byte. We could use (say) $GF(257)$, however when the shares will end up being slightly larger than 1 byte, and so if we encode a secret that's an random set of bytes, the shares end up using a bit more space.

If we used a trinary computer, we'd probably end using something like $GF(3^6)$, because that would be an even number of trits.

with GF(256), you end up writing a ton more code

Not that much; most computer languages support $GF(256)$ addition as a standard operator, and multiplication/division can be done with two tables, and a few lines of code.

Compare this to the logic required to do modular division.

As for "far less intuitive", well, that depends on your experience with finite fields; I find it perfectly intuitive.

• I think that last paragraph pretty much sums up the whole issue. :) Sep 11, 2016 at 9:12
• am curious how often the shares would end up slightly higher than 1 byte incase GF(257) is used ? Sep 12, 2016 at 2:34
• @sashank: if you used a fixed length encoding, they'd always be larger than 1 byte. If you used a variable length encoding, well, that'd depend on the encoding. Sep 12, 2016 at 3:21