# Necessity for finite field arithmetic and the prime number p in Shamir's Secret Sharing Scheme

Shamir's original paper (PDF, 197kb) describing a threshold secret sharing scheme states:

To make this claim more precise, we use modular arithmetic instead of real arithmetic. The set of integers modulo a prime number $p$ forms a field in which interpolation is possible. Given an integer valued data $D$, we pick a prime $p$ which is bigger than both $D$ and $n$. The coefficients $a_1,...,a_{k-1}~$ in $q(x)$ are randomly chosen from a uniform distribution over the integers in [0, $p$), and the values $D_1,...,D_n$ are computed modulo $p$.

Where:

• $D$ is the secret to be shared
• $n$ is the number of shares
• $k$ is the threshold number of shares needed to reconstruct $D$
• $q(x)$ is a $k-1$ order polynomial with $q(0)=D$ and the coefficients $a_1,...,a_{k-1}~$
• $D_1,...,D_n$ are individual shares (points on the polynomial $q(x)$)

Can someone please explain (in the simplest possible manner) the reason that Shamir's Secret Sharing Scheme uses finite field arithmetic? Also, why must the size of the Galois field be a prime number with the requirements that Shamir put forth?

The reason for asking these questions is: I would like to implement Shamir Sharing in Javascript using a field of size $2^8 = 256$, which:

1. will obviate the need for a big integer library for Javascript, such as jsbn
2. will simplify the math.

Whatever the size of the secret to be shared, it could be broken down into byte-length segments and the math performed on those segments. The resulting share would be a concatenation of the results of the necessary operations on each segment.

To find the secret, the shares can again be broken down into byte-length segments. The polynomial interpolation can be done with the corresponding byte-length segments from the shares to get individual segments of the secret. The segments can then be concatenated to form the complete secret.

Would this work and be cryptographically secure?

If there is indeed an absolute necessity for a prime number $p$, could I use any small prime number with the concatenations described to perform the necessary operations in Javascript and still remain cryptographically secure?

• Your idea has two parts: using a field $\mathbb F_{2^8}$ rather than $\mathbb F_p$; and splitting the secret to share into multiple bytes each treated in that field. That works; and the second part is present in the original article: "If the number D is long, it is advisable to break it into shorter blocks of bits (which are handled separately) in order to avoid multiprecision arithmetic operations".
– fgrieu
Nov 28, 2012 at 15:25
• @fgrieu thanks for that quote. I overlooked it. Had I read that statement I would not have asked this unnecessary Q. Nov 28, 2012 at 15:48
• You may be interested in this analysis I came across recently. Mar 12, 2015 at 13:28
• @mikeazo thanks. Seems interesting, but I cannot get the full article. Do you have a direct link? Mar 20, 2015 at 15:38
• @ampersand is there something missing in the PDF that is downloaded on the left hand side? It appears to be the whole thing to me. Mar 20, 2015 at 15:43

There is no reason in Shamir's scheme for the finite field $\mathbb F$ to have a prime number $p$ of elements; the field can have $p^m$ elements for suitable prime $p$ and integer $m \geq 1$. So, using $F_{2^8}$, the field with $2^8$ elements is perfectly all right. However, choosing $m = 1$ has the advantage that calculations in $\mathbb F_p$ can be done using the standard arithmetic unit included in microprocessors and the like (followed by integer divisions for doing the mod $p$ operations) whereas using $\mathbb F_{p^m}$ requires having a library already available (or developing one) or building a processor for arithmetic in the field.
Given that you have the capability of doing arithmetic in $\mathbb F_{2^8}$, you can use this field if you like. But, (as you say) in Shamir's scheme, the secret is just one element of the field (one $8$-bit byte), and so, if the Secret to be shared is several bytes long, you will need to process each byte separately into its (one-byte) shares, and concatenate the $i$-th share bytes into the $i$-th Share of the Secret. Keep in mind that each byte can be divided into at most $255$ shares (the point $q(0)$ on $q(x)$ cannot be used for obvious reasons), and so if you need to have more than $255$ shares to distribute, you will have to use a different field. Finally, to maintain cryptographic security, as the shares corresponding to each byte of the Secret are being computed, you should do exactly what you say you are doing in your comment: use a different set of "randomly chosen coefficients" for $q(x)$, rather than re-use the same set over and over again for finding the shares of all the bytes.
• "building a processor" is a little far-fetched for arithmetic in $\mathbb F_{p^m}$; a library will do.
• I think this wouldn't work for exactly 256 shares either. $\:$
• @RickyDemer You are correct. One of the $256$ shares would be the secret itself. I have corrected my answer. Nov 28, 2012 at 11:38
• @fgrieu Yes, a library of routines can be used for arithmetic in $\mathbb F_{p^m}$. But lots of people do build processors (application-specific integrated circuits or ASICs) for doing arithmetic in $\mathbb F_{p^m}$, especially $\mathbb F_{2^8}$ since error-correcting (Reed-Solomon) codes over this field are used in CD and DVD players, the DVB video broadcasting standard, various other communication systems and the like, which is where I am coming from. Nov 28, 2012 at 11:43