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
*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)
(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))))))
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.
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
(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
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))
(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))
(- (car (aref v j))
(car (aref v i)))
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.