On rencontre de nombreuses situations pratiques
où il peut être utile de séparer un secret en plusieurs morceaux :

• Une entreprise est la propriété de 10 actionnaires un peu craintifs. Ils tiennent absolument à ce que 7 d’entre eux soient d’accord
  pour chaque dépense. Comment mettre en place un protocole assurant qu’une coalition de 6 actionnaires ou moins ne pourra pas siphonner les comptes ?
• Le président Trump n’arrête pas d’oublier le code nucléaire, il faut donc le noter quelque part. Pour une sécurité optimale, l’état major décide de le séparer en plusieurs morceaux, stockés dans 12 bunkers disséminés à travers l’Union, de sorte que si l’ennemi prend 5 quelconques de ces bunkers, le code pourra toujours être reconstitué sans pour autant tomber aux mains de l’ennemi.
• La société Cumulus Inc., spécialisée dans le stockage en ligne, dispose d’une vingtaine de data-centers disséminés sur la planète. Elle assure à ses clients que le système fonctionne même si la moitié de ses serveurs se retrouve hors ligne, et que néanmoins les données restent confidentielles même si plusieurs d’entre eux sont piratés.

cadenas collectif

Une solution rudimentaire à ce problème est la suivante
(raisonnons dans le cadre de la société par actions, les autres situations sont similaires) : on met le numéro de compte dans une boîte fermée par
plusieurs serrures, et on distribue à chaque actionnaire un certain nombre de clefs, de sorte que 6 actionnaires n’ont jamais simultanément toutes les clefs.
Un petit raisonnement montre que la solution nécessite
au moins 210 serrures sur la boîte, et 84 clefs par actionnaire... Bref, ça fait beaucoup !
Et il reste encore à trouver un algorithme pour attribuer individuellement les clefs...

Adi Shamir

Voici une méthode élémentaire et très efficace
proposée par Adi Shamir [1] dans un article fameux [2].

Pour comprendre l’algorithme, commençons par une situation très simple. Le couple le plus célèbre de l’informatique, Alice et Bob, voudrait partager le
code à 4 chiffres de leur carte bancaire, un nombre secret noté $S$ compris entre 0000 et 9999. Pour cela, il suffit de choisir deux nombres entiers $a$ et $b$ tels que $a+b=S$ et de fournir $a$ à Alice et $b$ à Bob. S’ils veulent faire un achat commun, il leur suffit d’ajouter leurs codes respectifs. [Il faut pour cela imaginer un dispositif technique qui permette à chacun d’entrer secrètement son code de son côté, mais ce n’est pas le point ici.] Tout ceci est très simple, mais il y a une faille potentielle : supposons qu’Alice se voie attribuer le code $a = 9958$. Elle dispose alors d’une information capitale sur $S$ : il est compris entre 9958 et 9999, elle peut donc le trouver en au plus 42 tentatives. Pas très robuste... surtout s’il s’agit du code nucléaire !

Pour y remédier, une astuce classique est de travailler modulo 10000, c’est à dire de calculer en ajoutant ou retirant
autant de multiples de 10000 que nécessaire pour revenir entre 0000 et 9999, par exemple $8545+2651 = 11196 =1196$. On peut alors choisir $a$ au hasard entre 0000 et 9999 et poser $b = S- a$ mod. 10000. On voit que maintenant la connaissance de $a$ n’apporte plus
aucune information sur $S$.

Comment faire maintenant pour partager un secret à $n\geq 3$ personnes de sorte que 2 personnes au moins soient nécessaires pour le révéler ?
L’idée de Shamir est de tout simplement considérer....une droite. En effet, une droite est complètement déterminée par deux de ses points,
et à l’inverse la connaissance d’un point sur cette droite ne révèle que peu d’information sur celle-ci.
En formules, supposons que notre secret est un entier naturel $S$, et choisissons une droite dans le plan passant par le point $(0,S)$, son équation est donc de la forme $y = m x+ S$ (avec $m$ entier). L’information donnée
au participant $A_i$ est le point d’abscisse $i$ sur la droite, soit le point de coordonnées $(i,a_i)$. Si deux participants entrent leurs codes $(i,a_i)$ et $(j,a_j)$, l’ordinateur calcule la pente $ m= \frac{a_j - a_i}{j-i}$ et en déduit $S$ par la formule $S = a_i - m i$. Joli, non ?

Une droite est déterminée par deux de ses points.

En pratique, il y a la même faille que précédemment, et plutôt qu’avec des entiers naturels, il vaut mieux travailler modulo $N$, où $N$ est un entier
assez grand. Mieux, il est préférable de choisir pour $N$ un nombre premier : déplier le paragraphe suivant pour quelques détails.

Continuons ! S’il faut 3 personnes pour révéler le secret, on utilise maintenant une parabole. Son équation sera de la forme $y = m_2x^2 + m_1 x + S$, où $S$ est le secret.
On distribue donc aux participants des points distincts $(i,a_i)$ sur la parabole, et peu importe le nombre de participants, il
faut 3 points pour la déterminer, et donc déterminer le secret $S$.

Une parabole est déterminée par trois de ses points.

Pour revenir au problème de départ, notre société par actions n’a qu’à choisir au hasard un polynôme $P$ de degré 6 (sur un corps fini assez grand pour contenir les informations du secret)
\[P(x) = m_6x^6+m_5x^5+m_4x^4+m_3x^3+m_2x^2+m_1x + S\]
dont le terme constant est le numéro du compte en banque, et distribuer à ses actionnaires les valeurs $P(1), P(2), \ldots, P(10)$.

Pour extraire le secret au moment voulu,
comparativement à la solution consistant à ouvrir 210 serrures sur une boîte, le procédé pour inverser la méthode de Shamir est très simple. On détermine par un petit calcul l’unique polynôme de degré 6 qui interpole 7 (ou plus) valeurs connues.
Il y a pour cela une formule explicite, redoutée des étudiants de Licence, et connue sous le nom de formule d’interpolation de Lagrange. [4]