Partage de secret avec la méthode de Shamir

Le partage de secret est une méthode permettant de répartir entre plusieurs personnes un secret tel qu'un message en le chiffrant et en donnant à chaque individu un fragment de clef. Il faut réunir ces fragments pour pouvoir déchiffrer le message d'origine.

Une des variantes de partage de secret est appelée la méthode de Shamir et a été inventée par Adi Shamir (notamment connu pour être un des créateurs du chiffrement RSA) en 1979. Elle présente de nombreux avantages par rapport à d'autres approches :

elle présente une sécurité inconditionelle
elle permet de choisir un nombre requis de fragments de clef pour pouvoir déchiffrer le secret d'origine qui peut être inférieur au nombre total de fragment. En cas de décès, disparition ou conflit avec l'un des membres, les autres peuvent toujours déchiffrer le texte d'origine
les fragments de clefs sont de tailles inférieures à la taille du message
on peut générer des fragments de clefs supplémentaires pour de nouvelles personnes si nécessaire
on peut révoquer des fragments de clefs

Approche naïve du partage de secret et limitations

Afin de mieux comprendre l'intérêt de la méthode de Shamir il est utile d'essayer d'identifier les problématiques entourant le partage de secret.

Sécurité inconditionelle

Une approche extrêmement basique du partage de secret serait de se dire qu'il n'y a pas besoin de chiffrement et qu'il suffit de donner à chaque personne un fragment du texte secret. Imaginons par exemple que l'on veuille partager le mot de passe suivant équitablement entre 4 personnes :

t7udautfvu3z

Si l'on répartie entre chaque personnes le mot de passe cela va nous donner les fragments suivants : t7u, dau, tfv et u3z.

On pourrait à priori penser que cette solution fonctionne car chaque personne ne possède qu'un fragment du secret d'origine. Cependant cette solution ne respecte pas le principe de sécurité inconditionelle : une personne connaissant un des fragments du mot de passe aura plus de facilité à retrouver le mot de passe d'origine. Pire, plus le nombre de fragments connus est important, plus il est facile de trouver le mot de passe :

Fragments connus	Combinaisons possibles
0	4.73e18
1	1.02e14
2	2176782336
3	46656
4	1

Pour un ordinateur de bureautique moderne il deviendrait possible de trouver le mot de passe en quelques minutes à partir de 2 fragments connus. Cela souligne l'importance de la sécurité inconditionnelle ; posséder un ou plusieurs fragment de clef ne doit pas permettre de deviner le message d'origine.

Gestion du seuil

Le partage de fragments du mot de passe ne permettant pas une sécurité suffisante, on peut imaginer utiliser un ensemble de masques jetables que l'on distribuerait entre chaque candidat pour assurer une sécurité inconditionnelle.

Si l'on utilise une simple fonction XOR pour chiffrer le mot de passe, on peut établir la relation suivante :

{\textstyle secret \oplus F_1 \oplus F_2 \oplus F_3 = F_4}

Les fragments ${\textstyle F_1}$ , ${\textstyle F_2}$ et ${\textstyle F_3}$ sont de même taille que le mot de passe et sont générés aléatoirement. Le fragment ${\textstyle F_4}$ est la valeur résultant des opérations XOR. Si l'on XOR les différents fragments on retrouve le mot de passe :

{\textstyle F_1 \oplus F_2 \oplus F_3 \oplus F_4 = secret}

En théorie cette méthode de partage du mot de passe est un chiffrement parfait et équitable : il est impossible de retrouver avec certitude le mot de passe d'origine sans posséder l'ensemble des fragments de clef. Mieux, disposer de tous les fragments sauf un ne facilite en rien la recherche du mot de passe. Enfin, chaque fragment fait exactement la taille du mot de passe d'origine, ni plus, ni moins.

En pratique, cette méthode a un défaut majeur : si l'une des personnes possédant un fragment de clef décède ou perd son fragment, il devient alors impossible de déchiffrer le message d'origine.

Le concept de seuil vient corriger ce défaut : on peut déterminer le nombre minimum de fragments nécessaires pour déchiffrer le message d'origine.

Taille de fragment et flexibilité

Si l'on reprend la logique du chiffrement par XOR ci-dessus, on peut palier la problématique de seuil en générant des fragments plus longs et segmentés qui permettent le déchiffrement avec un seuil plus bas.

Par exemple, si l'on a 3 personnes entre qui l'on veut partager un secret, on peut utiliser la méthode suivante :

{secret \oplus F_{1A} = F_{2A}}

{secret \oplus F_{1B} = F_{3A}}

{secret \oplus F_{2B} = F_{3B}}

Les fragments ${F_{1A}}$ , ${F_{1B}}$ et ${F_{2B}}$ sont générés aléatoirement et ${F_{2A}}$ , ${F_{3A}}$ et ${F_{3B}}$ sont déduit de la taille du XOR des premiers fragments avec le mot de passe. Chaque personne obtient un couple de fragments : la première ( ${F_{1A}}$ , ${F_{1B}}$ ), la seconde ( ${F_{2A}}$ , ${F_{2B}}$ ) et la dernière ( ${F_{3A}}$ , ${F_{3B}}$ ).

Les opérations XOR étant commutative, pour retrouver le mot de passe d'origine, la première personne et la seconde doivent mettre en commun ${F_{1A}}$ et ${F_{2A}}$ car :

{F_{1A} \oplus F_{2A} = secret}

À l'inverse la seconde et la troisième personne devront mettre en commun ${F_{2B}}$ et ${F_{3B}}$ pour retrouver le mot de passe et la première personne et la troisième devront réunir ${F_{1B}}$ et ${F_{3A}}$ .

La problématique majeure de cette méthode est que si le code reste impossible à briser avec un seul fragment, chaque fragment a une longueur plusieurs fois supérieure à la longueur du texte chiffré. Ce nombre varie avec :

le nombre de personnes pour qui une clef est générée
le seuil de personnes nécessaires pour déchiffrer le message

Par ailleurs, si l'on souhaite partager un fragment de secret avec de nouvelles personnes, la taille de chaque fragment individuel augmentera de manière conséquente. La révocation de clef n'est également possible qu'en récréant de nouveaux fragments pour l'ensemble des personnes.

Méthode de Shamir

Comme on a pu le voir il est relativement compliqué d'établir une méthode naïve permettant d'assurer à la fois une sécurité inconditionelle, une valeur seuil variable et des tailles de fragment réduites. La méthode de Shamir permet pourtant de remplir ces trois conditions avec une mise en oeuvre relativement faible.

Présentation de la théorie

La méthode de Shamir utilise les propriétés des fonctions polynomiale et de l'interpolation lagrangienne grâce à laquelle on peut déterminer la valeur d'une fonction de degré ${\textstyle k}$ dès que l'on dispose d'au moins ${\textstyle k+1}$ points.

De manière très schématique, imaginons que l'on veuille partager un secret entre 3 personnes et qu'il faille qu'au moins 2 fragments soient réunis pour reconstituer le secret. La méthode de Shamir va générer une fonction polynomiale de degré 1 et générer 3 points pour celle-ci qui seront partagés entre chaque personnes. La valeur de cette fonction lorsqu'elle vaut 0 représente le secret.

On a les points suivant :

A(1,14)

B(2,16)

C(3,18)

Chacun des points représente un des fragments du secret partagé. On peut noter que si l'on dispose seulement que d'un seul des points, alors il y a une infinité de fonctions polynomiales de degré 1 potentielles passant par celui-ci :

Par contre dès lors que l'on dispose d'au moins 2 points, qui représentent ici le nombre nécessaires pour atteindre la valeur seuil, on peut retrouver facilement la fonction d'origine :

Génération des fragments

La méthode de génération des fragments avec la méthode Shamir est triviale ; il suffit d'écrire une fonction polynomiale avec les propriétés suivantes :

le terme constant représente notre secret sous forme d'un nombre entier positif m
le nombre de degrés k représente la valeur seuil (le nombre de personnes nécessaires pour déchiffrer le secret) moins un
les coefficients de chaque degrés du polynôme sont choisis au hasard parmi les entiers positifs (à noter que cela n'est possible qu'en considérant un modulo p)
afin de garantir la sécurité de la méthode de Shamir il est impératif d'appliquer un modulo p à notre fonction polynomiale de manière à rendre les coefficients de degrés "réellement" aléatoire en utilisant l'arithmétique modulaire. Ce modulo doit être un nombre premier supérieur au nombre représenté par notre secret.

Illustrons par l'exemple : on a comme chiffre secret m = 123456 et l'on a 5 personnes à qui l'on souhaite confier un fragment de secret, avec un minimum de k = 4 fragments nécessaire pour le déchiffrement et un modulo premier valant p = 129763. Notre équation sera comme comme suit :

S(X)=(m + \sum _{i=1}^{k-1}{a_{i}X^i}) \mod p

En reprenant les paramètres d'exemple on peut donc écrire :

S(X) = (123456 + 423X^{3} + 121X^{2} + 103X) \mod 129763

Comme expliqué au-dessus, les coefficients de chaque degrés du polynôme (423, 121 et 103) sont choisis au hasard sur $\mathbb{R}$ , l'utilisation d'un modulo derrière impliquant un passage sur $\mathbb{Z}_{p}$ .

Si l'on trace le graphique correspondant au polynôme de la fonction ${\textstyle S(X)}$ (sans appliquer le modulo p) on obtient :

On peut noter que pour ${\textstyle X=0}$ on obtient la valeur du secret : ${\textstyle S(X) = 123456}$ .

Pour générer les 6 fragments de clefs nécessaires il suffit de générer 6 valeurs avec la fonction ${\textstyle S(X)}$ :

{\begin{aligned} S(1) &= 124103 \\ S(2) &= 127530 \\ S(3) &= 6512 \\ S(4) &= 23113 \\ S(5) &= 50108 \\ S(6) &= 90035 \end{aligned}}

Chaque personne se voit alors communiquer un fragment de clef, la valeur de ${\textstyle X}$ ayant permis de généré ce fragment, ainsi que la valeur du modulo p.

L'utilisation d'un modulo dans la fonction ${S}$ est impérative pour garantir la sécurité inconditionelle. En effet sans ce modulo la fonction ${S}$ est une courbe ; plus l'on connait un nombre important de fragments, plus il est facile d'avoir une idée approximative de l'orientation de cette courbe et de sa valeur en ${S(0)}$ là où avec le modulo on a un nuage de point.

Reconstitution du secret

Pour reconstituer le secret d'origine, il faut être en mesure de retrouver la fonction ${\textstyle S}$ de manière à pouvoir calculer la valeur de ${\textstyle S(0)}$ qui a pour résultat le secret sous forme numérique. Pour retrouver notre fonction ${\textstyle S}$ il suffit d'utiliser une méthode d'interpolation des différents fragments de clefs via un polynôme de Lagrange :

S(X)=\sum _{j=0}^{k-1}y_{j}\ell _{j}(X)~ \mod p

Ce qui, en reprenant les paramètres de notre exemple, donne :

S(X)=\sum _{j=0}^{3}y_{j}\ell _{j}(X)~ \mod 129763

En parallèle on réunit au moins 4 points nécessaires au déchiffrement :

{\begin{aligned}(x_{1},y_{1})&=(1,124103) \\ (x_{2},y_{2})&=(2,127530) \\ (x_{3},y_{3})&=(3,6512)\\(x_4,y_4) &= (4, 23113)\end{aligned}}

On a les polynômes de Lagrange $\ell _{j}$ de base suivants :

{\begin{aligned} \ell _{0}&={\frac {x-x_{1}}{x_{0}-x_{1}}}\cdot{\frac {x-x_{2}}{x_{0}-x_{2}}}\cdot{\frac{x-x_3}{x_0-x_3}}={\frac {x-2}{1-2}}\cdot{\frac {x-3}{1-3}}\cdot{\frac{x-4}{1-4}}=-{\frac{x^3-9x^2+26x-24}{6}} \\ \ell _{1}&={\frac {x-x_{0}}{x_{1}-x_{0}}}\cdot{\frac {x-x_{2}}{x_{1}-x_{2}}}\cdot{\frac{x-x_3}{x_1-x_3}}={\frac {x-1}{2-1}}\cdot{\frac {x-3}{2-3}}\cdot{\frac{x-4}{2-4}}={\frac{x^3-8x^2+19x-12}{2}} \\ \ell _{2}&={\frac {x-x_{0}}{x_{2}-x_{0}}}\cdot{\frac {x-x_{1}}{x_{2}-x_{1}}}\cdot{\frac{x-x_3}{x_2-x_3}}={\frac {x-1}{3-1}}\cdot{\frac {x-2}{3-2}}\cdot{\frac{x-4}{3-4}}=-{\frac{x^3-7x^2+14x-8}{2}} \\ \ell _{3}&={\frac{x-x_0}{x_3-x_0}}\cdot{\frac{x-x_1}{x_3-x_1}}\cdot{\frac{x-x_2}{x_3-x_2}} = {\frac{x-1}{4-1}} \cdot {\frac{x-2}{4-2}} \cdot {\frac{x-3}{4-3}} = {\frac{x^3-6x^2+11x-6}{6}} \end{aligned}}

On obtient donc :

{S(x)=(124103\cdot\ell_0 + 127530\cdot\ell_1 + 6512\cdot\ell_2 + 23113\cdot\ell_0)\mod 129763}

Il nous reste alors plus qu'à calculer la valeur de ${S(0)}$ pour retrouver la valeur du secret :

{\begin{aligned}S(0)&=(124103\cdot\ell_0 + 127530\cdot\ell_1 + 6512\cdot\ell_2 + 23113\cdot\ell_0)\mod 129763\\&=(124103\cdot4)+(127530\cdot-6)+(6512\cdot4)+(23113\cdot-1)\mod 129763\\&=123456\end{aligned}}

Conclusion

La méthode de Shamir reste encore aujourd'hui un moyen sûr de partager un secret entre plusieurs individus en contrôlant le nombre de personnes nécessaires au déchiffrement. De nombreuses implémentations existent et la méthode de Shamir est notamment utilisée dans l'outil de partage de secrets Hashicorp Vault.