Implementing Secret Sharing In Python

One of Python's less frequently used features is its support for "long integers", numbers that can be any length. The ordinary integer type is stored in a C long data type, and can only hold values within a certain range. On 32-bit Linux machines, that range is from -2,147,483,648 to 2,147,483,647, while under Linux/AXP, the range is from --9,223,372,036,854,775,808 to 9,223,372,036,854,775,807.

Unlike ordinary integers, long integers can be as large as the system's memory and your patience allow. They're also more complex data structures than simple integers, and thus operations involving them are somewhat slower. On the other hand,

To use a value as a long integer instead of an ordinary one, simply add an 'L' after a number; for example, "50L". A lowercase letter 'l' will also work, but is rarely used because it's easily mistaken for a '1'. Or, an integer or floating point number can be converted to a long integer by the long() function.

Long integers support all the same operations that integers do:

>> 12L/5L
2L
>> 17L+33L
50L
>> 13L * 454L
5902L
>> pow(3L,75)
608266787713357709119683992618861307L

Sometimes long integers are considered an example of "creeping featurism". However, I think they're a useful feature to have, simply for portability's sake. If a function might need to operate on values larger than those that will fit in a 32-bit integer, then you can simply use long integers and know that it'll work without causing an OverflowError exception to be raised.

They're also useful for mathematical work. As an example, let's implement a secret sharing scheme in Python.

First, an explanation of secret sharing is needed.

There are various ways to share a secret; the simplest method doesn't require much more than high-school algebra. S is the secret we want to split up into N pieces, such that having M of them will allow reconstructing the secret.

Generate a prime number P that is larger than S.
Generate a polynomial F(x) = (kM-1*x^(M-1) + kM-2*x^(M-2) ... + k1*x + S) mod P ; k1...kM-1 are random numbers between 0 and P-1.
A share of the secret is then just a pair containing a random x and the result of F(x). Compute N such pairs to generate N shares. The polynomial's coefficients are discarded.

To reconstruct the secret, you'll need at least M shares. Write down M equations, with k1 through kM-1 and S as the unknowns. Since there are M equations and M unknowns, you can add and subtract equations to solve for them; one of those unknowns is S, so you've recovered the message.

An example will make this clearer. Let's divide a number (say, 77) into 3 shares, such that two of them can be used to reconstruct the secret. This means that m=2 and n=3. M=77, so let's choose p=97.

[The finished secret sharing module, secret-share.py, is available; I just have to finish describing it.]