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. <\/p>\n
We begin with a couple of constants and a function. The Because we’re working in \\(\\mathbb{Z}_{p}\\), \u201cdivision\u201d is a bit more complicated. The 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<\/a>. <\/p>\n The The 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 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. <\/p>\n","protected":false},"excerpt":{"rendered":" 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 … Continue reading randp<\/code> function uses strong-random<\/code> 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*<\/code> parameter holds the state for randp<\/code>. <\/p>\n*P*<\/code> 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*<\/code> gives us a field with \\(2^{256}\\) members rendering a brute force attack infeasible. <\/p>\n(defparameter<\/span> *prng*<\/span> (ironclad:make-prng :fortuna<\/span>) \"Holds the RNG state.\"<\/span>)\n(defparameter<\/span> *P*<\/span> 108838049659940303356103757286832107246140775791152305372594007835539736018383 \"256 bit prime\"<\/span>)\n\n(defun<\/span> randp<\/span> (p)\n \"Generate a random number for the polynomial coefficents and sample points.\"<\/span>\n (ironclad:strong-random p *prng*))\n<\/pre>\n<\/p><\/div>\nmodinv<\/code> 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<\/code> to compute its inverse and then multiply by that inverse to \u201cdivide.\u201d <\/p>\n(defun<\/span> modinv<\/span> (a p)\n \"Find the inverse of a mod p, p a prime. Uses the Euclidian algorithm.<\/span>\nThis is Algorithm X of Section 4.5.2 of TAOCP.\"<\/span>\n (labels<\/span> ((euclid (u v)\n (if<\/span> (= (caddr v) 0)\n (let<\/span> ((u0 (car u)))\n (if<\/span> (minusp u0)\n (+ u0 p)\n u0))\n (let<\/span> ((q (floor (\/ (caddr u) (caddr v)))))\n (euclid v (mapcar (lambda<\/span> (x y) (- x (* q y))) u v))))))\n (euclid (list 1 0 a) (list 0 1 p))))\n<\/pre>\n<\/p><\/div>\n(defun<\/span> horner<\/span> (a x)\n \"Evaluate the polynomial with coefficients in the array a at x.\"<\/span>\n (if<\/span> (= (length a) 1)\n (aref a 0)\n (do*<\/span> ((k (1- (length a)) (1- k))\n (val (* (aref a k) x) (* (+ val (aref a k)) x)))\n ((<= k 1) (+ val (aref a 0))))))\n<\/pre>\n<\/p><\/div>\nmake-keys<\/code> function uses randp<\/code> to choose the polynomial’s coefficients (and thus the secret) and the \\(x\\)-values of the \\(n\\) points. Then it uses horner<\/code> to generate the \\(n\\) points. <\/p>\nxvals<\/code> list is initialized to (0) so that 0 will not be chosen as an \\(x\\)-value. It’s discarded before xvals<\/code> is input to the mapcar<\/code> by the butlast<\/code>. <\/p>\n(defun<\/span> make-keys<\/span> (n k &optional<\/span> (p *P*))\n \"Returns a random secret and n distinct keys.<\/span>\nK keys are sufficient to recover the secret. Each key is a pair, a point<\/span>\non a random polynomial over the field Z\/p.\"<\/span>\n (let<\/span> ((a (make-array k))\n (xvals '(0))) ;<\/span>ensure x=0 not chosen as a point<\/span>\n (dotimes<\/span> (i k)\n (setf (aref a i) (randp p)))\n (while<\/span> (< (length xvals) (1+ n))\n (setq xvals (adjoin (randp p) xvals)))\n (cons (aref a 0)\n (mapcar (lambda<\/span> (x) (list x (mod (horner a x) p))) (butlast xvals)))))\n<\/pre>\n<\/p><\/div>\nretrieve-secret<\/code> is an almost literal translation of the above. <\/p>\n(defun<\/span> retrieve-secret<\/span> (v &optional<\/span> (p *P*))\n \"Recover the secret given k points and the prime.\"<\/span>\n (let<\/span> ((k (length v))\n (secret 0)\n prod)\n (dotimes<\/span> (i k (mod secret p))\n (setq prod (cadr (aref v i)))\n (setq secret (+ secret \n (dotimes<\/span> (j k prod)\n (unless<\/span> (= j i)\n (setq prod (* prod\n (car (aref v j))\n (modinv\n (- (car (aref v j))\n (car (aref v i)))\n p))))))))))\n<\/pre>\n<\/p><\/div>\n