Take the 2-minute tour ×
Cryptography Stack Exchange is a question and answer site for software developers, mathematicians and others interested in cryptography. It's 100% free, no registration required.

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?

share|improve this question
    
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 '12 at 15:25
    
@fgrieu thanks for that quote. I overlooked it. Had I read that statement I would not have asked this unnecessary Q. –  ampersand Nov 28 '12 at 15:48

1 Answer 1

up vote 7 down vote accepted

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.

share|improve this answer
    
"building a processor" is a little far-fetched for arithmetic in $\mathbb F_{p^m}$; a library will do. –  fgrieu Nov 28 '12 at 7:20
2  
I think this wouldn't work for exactly 256 shares either. $\:$ –  Ricky Demer Nov 28 '12 at 7:26
    
@RickyDemer You are correct. One of the $256$ shares would be the secret itself. I have corrected my answer. –  Dilip Sarwate Nov 28 '12 at 11:38
1  
@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. –  Dilip Sarwate Nov 28 '12 at 11:43

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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