Irreal

Yesterday, I discussed Shamir’s secret sharing and how it works. The TL;DR was a method to give \(n\) people a secret number so that any \(k\) of the recipients \((k\lt n)\) can reveal the secret. The method works by defining a \((k-1)\)-degree polynomial with the secret number as the constant term and then distributing \(n\) points on the polynomial. Once we have \(k\) points, we can recover the polynomial—and therefore the secret constant term—by interpolation.

We begin with a couple of constants and a function. The randp function uses strong-random from the ironclad library to generate cryptographically secure random integers between 0 and \(p-1\). We use it to generate the coefficients for the polynomial and the \(x\)-coordinates of the \(n\) points. The *prng* parameter holds the state for randp.

*P* is a 256 bit prime number. It’s the default size for the number of elements in our finite field. Because \(\mathbb{Z}_{p}\) is a finite field, you might think that we could simply try each element of the field to recover an encryption key based on the constant term of the polynomial. That would work for a low order field but using *P* gives us a field with \(2^{256}\) members rendering a brute force attack infeasible.

(defparameter *prng* (ironclad:make-prng :fortuna) "Holds the RNG state.")
(defparameter *P* 108838049659940303356103757286832107246140775791152305372594007835539736018383 "256 bit prime")

(defun randp (p)
  "Generate a random number for the polynomial coefficents and sample points."
  (ironclad:strong-random p *prng*))

Because we’re working in \(\mathbb{Z}_{p}\), “division” is a bit more complicated. The modinv function uses the Euclidean algorithm to compute the (mod \(m\)) inverse of a number. When we need to divide by some number, \(x\), we use modinv to compute its inverse and then multiply by that inverse to “divide.”

(defun modinv (a p)
  "Find the inverse of a mod p, p a prime. Uses the Euclidian algorithm.
This is Algorithm X of Section 4.5.2 of TAOCP."
  (labels ((euclid (u v)
             (if (= (caddr v) 0)
                 (let ((u0 (car u)))
                   (if (minusp u0)
                       (+ u0 p)
                       u0))
                 (let ((q (floor (/ (caddr u) (caddr v)))))
                   (euclid v (mapcar (lambda (x y) (- x (* q y))) u v))))))
    (euclid (list 1 0 a) (list 0 1 p))))

We’ll generate the \(n\) points by choosing \(n\) random, non-zero \(x\) values and evaluating the polynomial at those points. The efficient way to evaluate polynomials is with Horner’s methods. I wrote about Horner’s method previously.

(defun horner (a x)
  "Evaluate the polynomial with coefficients in the array a at x."
  (if (= (length a) 1)
      (aref a 0)
      (do* ((k (1- (length a)) (1- k))
            (val (* (aref a k) x) (* (+ val (aref a k)) x)))
           ((<= k 1) (+ val (aref a 0))))))

The make-keys function uses randp to choose the polynomial’s coefficients (and thus the secret) and the \(x\)-values of the \(n\) points. Then it uses horner to generate the \(n\) points.

The xvals list is initialized to (0) so that 0 will not be chosen as an \(x\)-value. It’s discarded before xvals is input to the mapcar by the butlast.

(defun make-keys (n k &optional (p *P*))
  "Returns a random secret and n distinct keys.
K keys are sufficient to recover the secret. Each key is a pair, a point
on a random polynomial over the field Z/p."
  (let ((a (make-array k))
        (xvals '(0)))                   ;ensure x=0 not chosen as a point
    (dotimes (i k)
      (setf (aref a i) (randp p)))
    (while (< (length xvals) (1+ n))
      (setq xvals (adjoin (randp p) xvals)))
    (cons (aref a 0)
          (mapcar (lambda (x) (list x (mod (horner a x) p))) (butlast xvals)))))

Given the \(k\) points \((x_{0}, y_{0}) \ldots (x_{k-1}, y_{k-1})\), we retrieve the secret by evaluating the polynomial resulting from the Lagrangian interpolation of the \(k\) points at 0. We can do this all at once by computing \[\sum_{i=0}^{k-1} y_{i} \prod_{\substack{0\leq{}j\leq{}k-1 \\ j\neq{}i}} \frac{-x_{j}}{x_{i}-x_{j}}\] as explained in yesterday’s post. Notice that retrieve-secret is an almost literal translation of the above.

(defun retrieve-secret (v &optional (p *P*))
  "Recover the secret given k points and the prime."
  (let ((k (length v))
        (secret 0)
        prod)
    (dotimes (i k (mod secret p))
      (setq prod (cadr (aref v i)))
      (setq secret (+ secret 
                      (dotimes (j k prod)
                        (unless (= j i)
                          (setq prod (* prod
                                        (car (aref v j))
                                        (modinv
                                         (- (car (aref v j))
                                            (car (aref v i)))
                                         p))))))))))

As you can see, Shamir’s method is easy to understand and implement. None-the-less, it’s a powerful way of having a distributed secret.

References to Jeremy Kun’s The Mathematics of Secret Sharing keep popping up in my feed so it appears there’s some interest in it. The problem is to entrust shares in a secret to \(n\) people in such a way that the secret can be recovered if \(k\) shareholders \((k < n)\) agree to reveal the secret. If less than \(k\) of the shareholders agree, the secret remains hidden. For each shared secret, the number \(k\) is fixed but any number of shares can be distributed. The secret must be a number so in practice the secret will usually be an encryption key.

It might seem like this would be a difficult problem requiring some esoteric mathematics but it turns out to be simple and requires no more than high school mathematics. The method uses the fact that it takes \(m + 1\) points to recover an \(m^{\textrm{th}}\) degree polynomial (because, after all, there are \(m + 1\) coefficients to determine). For example two points determine a line (1^st degree polynomial), three points determine a parabola (2^nd degree polynomial) and so on.

As an example, suppose our secret is 7, that we want 6 shareholders, and that we require at least 4 shares to reveal it. We define a third degree polynomial with a constant term of 7, say \(x^{3} + 3x^{2} – x + 7\), and then pick 6 points on the polynomial (avoiding the \(x=0\) point) and give each of the shareholders a point. This is illustrated in Figure 1 where the green points are given to the shareholders and the blue point corresponds to the secret.

Now if four of the shareholders agree to reveal their points, it is a simple matter to recover the polynomial with Lagrangian interpolation¹, and retrieve the secret as the constant term.

This method has the advantage of being theoretically unbreakable. If an attacker has \(j < k\) points, a polynomial having any desired constant term can easily be constructed that passes through the \(j\) points. That means that the \(j\) points could represent any secret. Only by having \(k\) points can an attacker recover the secret.

For various technical reasons the calculations should be carried out over a finite field. That doesn’t really change anything except that “division” calculations are a bit more difficult. Tomorrow, I’ll present Lisp code that implements Shamir’s Secret Sharing over the finite field \(\mathbb{Z}_{p}\) where \(p\) is a 256 bit prime.