Sécurité et reconstruction

Reconstruction par interpolation de Lagrange

Nous savons que k points suffisent, en principe. Reste la question pratique : comment reconstruit-on concrètement le secret à partir de k parts ? La réponse est l'interpolation de Lagrange.

Le principe de l'interpolation de Lagrange

Étant donné k points, l'interpolation de Lagrange fournit directement l'unique polynôme de degré k - 1 qui passe par tous ces points. Comme on ne veut que S = P(0), on peut évaluer la formule en 0 sans même écrire le polynôme entier :

Parts : (x_1, y_1), (x_2, y_2), ..., (x_k, y_k)

            k                    x_j
S = P(0) =  Σ   y_i ·  ∏   ---------------
           i=1        j≠i     x_j - x_i

Chaque part y_i est pondérée par un coefficient qui ne dépend que des abscisses x_i. On combine le tout, et on obtient S.

Un exemple complet avec k = 2

Reprenons la droite de la leçon précédente. On nous donne deux parts, (1, 10) et (3, 16), et on cherche S = P(0) :

          x_2                x_1
S = y_1·-------  +  y_2·-------
        x_2-x_1          x_1-x_2

         3               1
= 10·-------  +  16·-------
       3-1             1-3

= 10·(3/2)  +  16·(-1/2)
= 15 - 8
= 7                      <- secret retrouvé !

On retrouve bien S = 7, sans avoir eu besoin de la troisième part. N'importe quelles deux parts auraient donné le même résultat.

Pourquoi un corps fini est indispensable

Dans les exemples, on a travaillé avec des entiers ordinaires. En vrai, Shamir impose de faire toute l'arithmétique modulo un grand nombre premier p : on travaille dans le corps fini noté GF(p). Trois raisons majeures :

Précision. Les réels et les fractions engendrent des erreurs d'arrondi. Dans un corps fini, tout est entier et exact — la division devient une multiplication par un inverse modulaire, toujours définie.
Sécurité parfaite. Sur les entiers ordinaires, l'ampleur des valeurs P(i) fuit une information sur les coefficients, donc sur S. Un corps fini borne toutes les valeurs dans [0, p-1] de façon uniforme : la sécurité parfaite de la leçon précédente n'est rigoureusement vraie que dans un corps fini.
Uniformité. Le tirage au hasard des coefficients dans [0, p-1] rend chaque secret équiprobable, ce qui est la clé de la preuve.

Chaîne complète de reconstruction :

  k parts (x_i, y_i)
        |
        |  interpolation de Lagrange (mod p)
        v
   polynôme P (implicite)
        |
        |  évaluation en x = 0
        v
   S = P(0)  = le secret

Ce qu'il faut retenir de l'ensemble

Le schéma de Shamir est remarquable : simple à énoncer, prouvé sûr, et souple (on peut ajouter des parts sans changer le secret, ajuster le seuil, etc.). C'est pourquoi on le retrouve dans la gestion des clés maîtresses, les portefeuilles de cryptomonnaie et les cérémonies de sécurité.

En résumé