Yesterday, I discussed Shamir's secret sharing and how it works. The TL;DR was a method to give people a secret number so that any of the recipients can reveal the secret. The method works by defining a -degree polynomial with the secret number as the constant term and then distributing points on the polynomial. Once we have 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 . We use it to generate the coefficients for the polynomial and the -coordinates of the 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 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 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 , “division” is a bit more complicated. The `modinv`

function uses the Euclidean algorithm to compute the (mod ) inverse of a number. When we need to divide by some number, , 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 points by choosing random, non-zero 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 -values of the points. Then it uses `horner`

to generate the points.

The `xvals`

list is initialized to (0) so that 0 will not be chosen as an -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 points , we retrieve the secret by evaluating the polynomial resulting from the Lagrangian interpolation of the points at 0. We can do this all at once by computing

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.