The Task

I’m an engineer tasked with building a system to launch nuclear missiles, and I want to make sure that the missiles aren’t launched by mistake. But I also want to make sure that they will be launched when properly authorized, so that they can serve as a credible deterrent. To do this, I want to give out launch codes to a number of trusted individuals (for redundancy) but require the cooperation of a few of them in order to launch (so one or two of them can’t go rogue).

The Problem

I have a b-bit secret s that I want to break into n shares so that any k of those shares can be combined to reconstruct the secret, but no k−1 of them can give any information about the secret.

• s, a b-bit secret
• n b-bit shares of s
• k shares required to retrieve secret s

Easy Cases

k = 1:  Each share is the secret itself:

s_i = s

k = n:  n−1 shares are random b-bit numbers, and the remaining share is the xor of those numbers and the secret s:

s_i = r_i  for 0 < i < k

s₀ = s ⊕ r₁ ⊕ ⋯ ⊕ r_k−1

General Case

Observation: A line is determined by 2 points. More generally a polynomial curve of degree k−1 is determined by k points on that curve.

So, if we give a point on a k−1 degree curve to each of our n sharers, any k of them can together determine the curve. If we make y at x = 0 be our secret s, and choose the other k−1 coefficients randomly, we’ve mostly solved our problem.

Share computation

What’s Wrong With This Scheme?

So far, I’ve described the scheme using “real” numbers, but those are problematic on a computer. We could use rational numbers, but those get expensive to compute. Also, the notion of a random number gets a bit dicey. Integers don’t work, because they’re mostly hard to invert. The numbers we really want to use are those from a finite field.

The Right Kind of Numbers

In order for numbers to be usable for our secret sharing scheme, they have to satisfy certain properties:

+ − × / 0 1  ∞ 

• They can be added (a+b) and multiplied (ab)
• Addition and multiplication must be associative and commutative: (a+b)+c = a+(b+c), (ab)c = a(bc), a+b = b+a, ab = ba
• Multiplication must distribute over addition: a(b+c) = ab + ac
• They have to include an additive identity, 0, and a multiplicative identity, 1: 0+a = a and 1a = a
• Each number must have a negative (−a+a = 0), and each nonzero number must have an inverse (a⁻¹a = 1)
• There must only be a finite number of numbers, so we can choose one at random.

Numbers with these properties are called finite fields, and lucky for us, there are lots of them. For each prime p and each positive integer n, there is exactly one finite field, written GF(pⁿ); it has pⁿ numbers in it.

Computing with Finite Fields

ffield.py

I’ve written a finite field module, ffield.py, for computing with finite fields. It has a single class, called ffield, which takes three arguments: a prime p, a positive integer n, and an irreducible polynomial encoded as a number or tuple, and returns a class implementing the specified finite field. The reason for the third argument is that, while there is only a single finite field for a given p and n, its numbers can be represented by nonegative integers less than pⁿ in many different ways, depending on that third argument. But 0 and 1 are always represented as themselves.

ffield(2,4,15)

Computing with Matrices

matrix.py

I’ve written a matrix module, matrix.py, for computing with matrices whose elements may be regular Python numbers or Python number-like class instances. In particular, it works with ffield.py and rational.py (an implementation of the field of rational numbers). It has a single class, called matrix, which takes arguments specifying the dimensions of the matrix and its contents, and returns the corresponding vector or matrix, or higher-dimensional array (but we can ignore that). It provides the usual matrix operations, such as addition, subtraction, multiplication, division, negation, inverse, transpose, trace, determinant.

Secret Sharing with Finite Fields

(Demonstration)

I’ve written a little module, share.py, for demonstrating the use of finite fields for secret sharing. If we have a b-bit secret, GF(2^b) is a natural choice. By default, share.py uses b = 256, and in particular F=ffield(2,256,1061).

• shares(s,n,k) returns n shares of secret s, such that any k shares can reconstruct s, but fewer than k shares convey no information.
  s should be a member of a finite field, for example F(0xaddedbaddeadbeef), and each share will be a pair of numbers in that same field.
  s may instead be a string of up to 56 ASCII characters—it is converted to a member of GF(2³⁶⁸) using G = ffield(2,368,141).
• printshares(ss) prints the shares ss as pairs of share number and share value.
• selectshares(ss,*args) returns the list of shares in ss selected by the numeric args.
• secret(ss) takes a list of shares and returns the secret. If ss has fewer than k shares, the result is random. ss can have as many as n shares, and will still return the secret.
• mungeshare(xs,j,t) takes a list of k shares and returns a copy with only the jth element changed so that secret(mungeshare(xs,j,t)) will return t.

Questions?

All of the python modules mentioned, as well as this presentation, are available on https://github.com/ms0/. The python modules can be imported from the msmath package (pip install msmath).