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.

This question already has an answer here:

I'm not quite sure the benefits of working over a prime modulus in Shamir's secret share- but doesn't limiting the numbers you pull from make the secret easier to guess? Instead of being over the real numbers, with infinite elements, limiting yourself to some prime limits the possibilities-albeit that number can get very large. Isn't this bad? What benefits are there to working over a prime that justify this choice?

share|improve this question

marked as duplicate by Ilmari Karonen, e-sushi, Gilles, Henrick Hellström, B-Con Oct 1 '13 at 20:49

This question has been asked before and already has an answer. If those answers do not fully address your question, please ask a new question.

A computer can't represent real numbers –  CodesInChaos Sep 27 '13 at 9:06

2 Answers 2

Computers are unable to handle real numbers, especially irrational numbers.

Computers can handle a fraction of the rational numbers (for being limited in size in a binary representation), and without some special tricks it can't handle the entire field $\mathbb{Q}$.

So you're down to integer arithmetic anyway (if you consider floats: rounding and cancellation can really mess things up). However, addition and multiplication over integers are just a ring structure and not a field (multiplicative inverse elements do not exist). So if you need to invert multiplication you need to use the finite structure.

share|improve this answer

As long as computers have a finite amount of RAM, then they cannot handle infinite amounts of data.

Shamir's secret sharing is "perfect" in the following sense: it does not leak any extra information. When a threshold $t$ is used, an attacker obtaining $t-1$ shares learns nothing that he did not already know. But we assume that "what the attacker already knew" includes the set of possible values for the secret. For instance, the attacker may know that the secret is "a 128-bit key", which means that they key is any one of the $2^{128}$ possible sequences of 128 bits.

Since we use practical computers which exist in the real world, the attacker necessarily knows that whatever secret value we are handling must fit in a computer, thus be part of a finite (but huuuuuge) set of possible values. This knowledge is intrinsic; no amount of cryptography can change anything to that. If I tell you that "I know of a secret value" then I reveal that I know of that secret value, which implies that the secret value fits in the set of "things that can be known" -- in particular, it cannot be so large that I would not be able to store it or remember it, otherwise I would not "know" it.

While most of the above is rather empty, this still highlights the importance of taking care of your encodings. When using Shamir's secret sharing on a per-byte basis (by working in $GF(2^8)$), the size of each share (in bytes) is equal to the size of the secret value. So the size may leak information; thus, people who indulge in Shamir's secret sharing shall first agree upon an encoding of the shared secret which has a fixed length for all possible secret values. This is easy if the secret is, say, a symmetric key (a 128-bit key for AES). This can be a bit more tricky if the secret is a RSA key with ASN.1/DER encoding.

share|improve this answer
How does it not leak extra information? Doesn't knowledge of the other keys reveal some sort of divisibility criteria? If some attacker finds out that $(1,2)$ and $(2,1)$ are keys, won't he know that the polynomial must be of the form $(x-1)(x-2)$ and some other stuff? Does that not help at all? –  user8632 Sep 27 '13 at 15:33