Diviser un secret

L'idée géniale : un polynôme

Comment obtenir la propriété magique du seuil ? L'idée de Shamir est d'une élégance rare : elle repose sur une simple observation de géométrie.

Combien de points pour fixer une courbe ?

Repartons de l'école :

Par 1 point, passe une infinité de droites.
Par 2 points distincts, passe une seule droite.
Par 2 points, passe une infinité de paraboles ; mais par 3 points, une seule.

La règle générale est nette :

Un polynôme de degré (k - 1) est déterminé
de façon unique par k points distincts.

degré 1 (droite)    <- 2 points
degré 2 (parabole)  <- 3 points
degré 3 (cubique)   <- 4 points
...
degré k-1           <- k points

Moins de k points ne suffisent jamais : il reste une infinité de courbes candidates. C'est exactement la frontière qu'il nous faut.

L'idée géniale de Shamir

On cache le secret dans un polynôme, puis on distribue des points de ce polynôme comme parts.

Concrètement, pour un schéma (k, n) :

Le secret S devient le terme constant du polynôme : S = P(0).
On choisit au hasard les autres coefficients a_1, ..., a_{k-1}.

P(x) = S + a_1·x + a_2·x^2 + ... + a_{k-1}·x^{k-1}
       ^
       terme constant = le secret = P(0)

Le polynôme est de degré k - 1.

On calcule n points : P(1), P(2), ..., P(n). Chaque part est un couple (i, P(i)).
On n'utilise jamais le point x = 0, car il révélerait S directement.

Reconstruire, c'est retrouver le polynôme

Puisque le polynôme est de degré k - 1, il faut et il suffit de k points pour le reconstituer entièrement. Une fois le polynôme connu, on l'évalue en 0 :

k parts  -->  polynôme P retrouvé  -->  S = P(0)

L'exemple le plus simple : k = 2 (une droite)

Cachons S = 7 avec un seuil k = 2. On tire un coefficient au hasard, disons a_1 = 3, d'où la droite :

P(x) = 7 + 3x

Parts distribuées :
  P(1) = 10   -> part (1, 10)
  P(2) = 13   -> part (2, 13)
  P(3) = 16   -> part (3, 16)

  y
16 |              * (3,16)
13 |        * (2,13)
10 |  * (1,10)
 7 |* <- P(0) = S = 7  (secret, jamais distribué)
   +------------------- x
   0   1   2   3

Deux parts quelconques, par exemple (1, 10) et (3, 16), redonnent l'unique droite qui les relie, donc P(0) = 7. Une seule part ne dit rien : une infinité de droites passent par un point unique.

En résumé