Partage de clé secrète de Shamir

Le partage de clé secrète de Shamir (Shamir's Secret Sharing) est un algorithme de cryptographie créé par Adi Shamir^[1]. C'est une forme de secret réparti, où un secret est divisé en parties, donnant à chaque participant sa propre clé partagée, où certaines des parties ou l'ensemble d'entre elles sont nécessaires afin de reconstruire une phrase de passe qui donne accès au secret.

Parfois, il n'y a pas forcément besoin de tous les participants pour reconstituer le minimum nécessaire qui forme la phrase de passe d'accès au secret, c'est pourquoi est utilisé parfois le schéma seuil où un nombre k des parties est suffisant pour reconstruire le secret d'origine.

Explication avancée[modifier | modifier le code]

Le partage de clés secrètes de Shamir est utilisé pour sécuriser l'accès à un secret (un fichier, un texte...) de manière distribuée, le plus souvent pour sécuriser d'autres clés de chiffrement. Le secret est divisé en plusieurs morceaux, appelées parties. Ces morceaux, en éclats de verre, sont utilisés pour reconstituer le secret original : la phrase de passe. Ce qui s'apparente à une technique de hachage d'une phrase de passe, qui donne accès au secret, en plusieurs morceaux de clés.

Pour déverrouiller l'accès au secret via le partage de clès secrètes de Shamir, vous avez besoin d'un nombre minimum de parties réunies. C'est ce qu'on appelle le seuil, qui est utilisé pour indiquer le nombre minimum de parties nécessaires pour réconstituer la phrase de passe et déverrouiller l'accès au secret. Prenons un exemple :

« Problème : La société XYZ doit sécuriser le mot de passe de son coffre-fort. Elle pourrait utiliser un moyen standard, comme l'AES, mais que faire si la détentrice ou le détenteur de la clé n'est pas disponible ou meurt ? Que se passe-t-il si la clé est compromise par un pirate malveillant ou si le détenteur de la clé décide de trahir la société, et utilise son pouvoir sur le coffre à son avantage ? »

C'est là qu'intervient le partage de clé secrète de Shamir. Il peut être utilisé pour chiffrer le mot de passe du coffre-fort et générer un certain nombre de parties, une configuration dans laquelle un certain nombre de parties peut être attribué à chaque dirigeant de la société XYZ. Ce n'est que s'ils mettent leurs parties en commun qu'ils peuvent reconstituer la phrase de passe secrète pour déverrouiller le coffre-fort. Le seuil peut être fixé de façon appropriée en fonction du nombre de personnes impliquées, de sorte que le coffre-fort soit toujours accessible par les personnes autorisées. Si une partie ou deux tombaient entre de mauvaises mains, cela ne permettrait pas de déverrouiller par mot de passe à moins que les autres dirigeants ne coopèrent avec leurs parties distribuées auparavant.

Définition mathématique[modifier | modifier le code]

Formellement, notre objectif est de diviser certaines données $D$ (par exemple, la combinaison du coffre) en $n$ pièces $D_{1},...,D_{n}$ de telle sorte que:

la connaissance de $k$ ou plus $D_{i}$ pièces rend $D$ facilement calculable ;
la connaissance de $k-1$ ou moins $D_{i}$ pièces rend $D$ complètement indéterminée (en ce sens que toutes ses valeurs possibles sont également probables).

Ce régime est appelé schéma seuil $(k;n)$ . Si $k=n$ alors tous les participants sont nécessaires pour reconstituer le secret.

Système de partage de secret de Shamir[modifier | modifier le code]

L'idée essentielle d'Adi Shamir est que 2 points sont suffisants pour définir une ligne, 3 points suffisent à définir une parabole, 4 points pour définir une courbe cubique, etc. Autrement dit, il faut $k$ points pour définir un polynôme de degré $k-1$ .

Supposons que nous voulons utiliser un schéma de seuil $(k,n)$ pour partager notre secret $S$ , que l'on suppose, sans perte de généralité, être un élément dans un corps fini $F$ .

Choisir au hasard $(k-1)$ coefficients $a_{1},...,a_{k-1}$ dans $F$ , et poser $a_{0}=S$ .

Construire le polynôme $f(x)=a_{0}+a_{1}x+a_{2}x^{2}+a_{3}x^{3}+...+a_{k-1}x^{k-1}$ . Soient n'importe quels $n$ points calculés à partir de lui, par exemple $i=1,...,n$ qui donnent $(i,f(i))$ . Chaque participant se voit attribuer un point (un couple d'antécédent et de l'image correspondante par la fonction polynomiale). Étant donné un sous-ensemble de $k$ de ces couples, nous pouvons trouver les coefficients du polynôme à l'aide de l'interpolation polynomiale, le secret étant le terme constant $a_{0}$ .

Utilisation[modifier | modifier le code]

Exemple[modifier | modifier le code]

L'exemple suivant illustre l'idée de base. Notez, cependant, que les calculs sont effectués sur des entiers plutôt que dans un corps fini. Par conséquent, l'exemple ci-dessous ne fournit pas le secret parfait, et n'est pas un véritable exemple du régime de Shamir.

Préparation[modifier | modifier le code]

Supposons que notre secret est 1234 $(S=1234)$ .

Nous tenons à partager le secret en 6 parties $(n=6)$ , où une réunion quelconque de 3 parties $(k=3)$ suffit pour reconstruire le secret. Au hasard, on obtient 2 numéros: 166, 94.

$(a_{1}=166;a_{2}=94)$

Le polynôme pour produire les clés est donc:

$f(x)=1234+166x+94x^{2}$

Nous avons construit 6 points à l'aide du polynôme :

$(1,1494);(2,1942);(3,2578);(4,3402);(5,4414);(6,5614)$

Nous donnons à chaque participant un point différent (à la fois $x$ et $f(x)$ ).

Reconstruction[modifier | modifier le code]

Afin de reconstituer le secret, 3 points seront suffisants.

Par exemple : $(x_{0},y_{0})=(2,1942);(x_{1},y_{1})=(4,3402);(x_{2},y_{2})=(5,4414)$ .

Le polynôme de Lagrange associé s'écrit :

f(x)=\sum _{j=0}^{2}y_{j}\ell _{j}(x)~,

où les ℓ_j sont les polynômes de base de Lagrange :

$\ell _{0}={\frac {x-x_{1}}{x_{0}-x_{1}}}{\frac {x-x_{2}}{x_{0}-x_{2}}}={\frac {x-4}{2-4}}{\frac {x-5}{2-5}}={\frac {1}{6}}x^{2}-{\frac {3}{2}}x+{\frac {10}{3}}$

$\ell _{1}={\frac {x-x_{0}}{x_{1}-x_{0}}}{\frac {x-x_{2}}{x_{1}-x_{2}}}={\frac {x-2}{4-2}}{\frac {x-5}{4-5}}=-{\frac {1}{2}}x^{2}+{\frac {7}{2}}x-5$

$\ell _{2}={\frac {x-x_{0}}{x_{2}-x_{0}}}{\frac {x-x_{1}}{x_{2}-x_{1}}}={\frac {x-2}{5-2}}{\frac {x-4}{5-4}}={\frac {1}{3}}x^{2}-2x+{\frac {8}{3}}$

Par conséquent :

${\begin{aligned}f(x)&=1942({\frac {1}{6}}x^{2}-{\frac {3}{2}}x+{\frac {10}{3}})+3402(-{\frac {1}{2}}x^{2}+{\frac {7}{2}}x-5)+4414({\frac {1}{3}}x^{2}-2x+{\frac {8}{3}})\\&=1234+166x+94x^{2}\end{aligned}}$

Rappelons que le secret est le premier coefficient, ce qui signifie que $S=1234$ , et on a fini.

Propriétés[modifier | modifier le code]

Certaines des propriétés utiles du schéma seuil $(k,n)$ de Shamir sont les suivantes :

Sécurisé : la sécurité de l'information est théorique (c'est-à-dire qu'elle ne repose pas sur des calculs numériques compliqués et longs à inverser ou sur un algorithme secret).
Minimal : La taille de chaque pièce ne dépasse pas la taille des données d'origine.
Extensible : Quand $k$ est fixe, $D_{i}$ morceaux peuvent être ajoutés ou supprimés de manière dynamique (par exemple, quand des participants sont congédiés ou meurent subitement) sans affecter les autres morceaux.
Dynamique : La sécurité peut être facilement améliorée sans changer le secret, mais en changeant le polynôme de temps en temps (en gardant le même premier terme du polynôme) et en construisant alors les nouvelles parties pour les participants.
Flexible : Dans les organisations où la hiérarchie est importante, nous pouvons fournir à chaque participant un nombre différent de pièces en fonction de son importance dans l'organisation. Par exemple, le président peut déverrouiller le coffre-fort seul, tandis que 3 secrétaires sont nécessaires pour cette même tâche.

Porte dérobée[modifier | modifier le code]

Il est possible de créer très facilement une porte dérobée dans l'implémentation d'un logiciel du partage de clé secrète de Shamir. Vous pouvez présenter un code source qui ne présente aucun souci puis compiler avec un "Œuf de Pâques" (Easter egg) qui contiendra une porte dérobée. En l'absence des coefficients du polynôme, les participants ne peuvent vérifier si l'autorité les trompe ou non. Tout a l'"air aléatoire".

Les deux exemples suivants veulent attirer l'attention sur la possibilité qu'un seul participant bien choisi peut obtenir le secret dans le cas (3,5) ou que deux participants bien choisis peuvent également s'associer pour obtenir le secret dans le cas du seuil (3,5). On peut bien sûr généraliser au cas (k,n).

Il ne s'agit pas d'une attaque du schéma, seulement de la possibilité, au niveau logiciel, que l'autorité puisse tromper la plupart des participants. Il est possible qu'une configuration logicielle, par défaut, permette cette possibilité.

Exemples[modifier | modifier le code]

Cette section n’est pas rédigée dans un style encyclopédique. Améliorez sa rédaction !

Utilisation de Pari/GP - version 2.5.0 : sont adoptées ici les notations du livre « Cryptographie : Théorie et Pratique », Douglas Stinson, 1996, Chapitre 11 « Systèmes de partage de secret »^{[réf. nécessaire]}

Schéma de seuil (3,5) : un participant connait le secret[modifier | modifier le code]

Le choix du nombre premier $P$ , du secret $K$ , de $x$ et de $AA$ est arbitraire :

{\begin{aligned}P&=prime(1010)\\K&=Mod(4131,P)\\x&=Mod([1,2,30,4,5],P)\\AA&=Mod(prime(999),P)\end{aligned}}

$a_{1}$ est aléatoire ( $=AA$ ), le choix de l'autre coefficient secret $a_{2}$ ici n'est pas aléatoire du tout :

$a=Mod([AA,-AA\times x[1]/(x[1]\times x[1])],P)$

Calcul classique des clés :

$y=[K+a[1]*x[1]+a[2]*x[1]*x[1],K+a[1]*x[2]+a[2]*x[2]*x[2],K+a[1]*x[3]+a[2]*x[3]*x[3],K+a[1]*x[4]+a[2]*x[4]*x[4],K+a[1]*x[5]+a[2]*x[5]*x[5]$

Vérification avec la coalition : 1 3 5

$b=[x[3]*x[5]/((x[3]-x[1])*(x[5]-x[1])),x[1]*x[5]/((x[1]-x[3])*(x[5]-x[3])),x[1]*x[3]/((x[1]-x[5])*(x[3]-x[5]))]$

secret=b[1]*y[1]+b[2]*y[3]+b[3]*y[5] /* ok */ /* Vérification avec la coalition: 2 3 5*/ b=[x[3]*x[5]/((x[3]-x[2])*(x[5]-x[2])),x[2]*x[5]/((x[2]-x[3])*(x[5]-x[3])),x[2]*x[3]/((x[2]-x[5])*(x[3]-x[5]))] secret=b[1]*y[2]+b[2]*y[3]+b[3]*y[5] /* ok */

/* Mais x_1 détenait déjà l'information (sans le savoir ?) */print("On a une information y[1]:") y[1]

Résultats :

%58 = 8017

%59 = Mod(4131, 8017)

%60 = [Mod(1, 8017), Mod(2, 8017), Mod(30, 8017), Mod(4, 8017), Mod(5, 8017)]

%61 = Mod(7907, 8017)

%62 = [Mod(7907, 8017), Mod(110, 8017)]

%63 = [Mod(4131, 8017), Mod(4351, 8017), Mod(3627, 8017), Mod(5451, 8017), Mod(6331, 8017)]

%64 = [Mod(2904, 8017), Mod(5916, 8017), Mod(7215, 8017)]

%65 = Mod(4131, 8017)

%66 = [Mod(2865, 8017), Mod(1947, 8017), Mod(3206, 8017)]

%67 = Mod(4131, 8017)

On a une information y[1]:

%68 = Mod(4131, 8017)

/ schéma de seuil (3,5) : deux participants ensemble connaissent le secret[modifier | modifier le code]

La somme de la clé du 1^er participant et de la clé du 2^e participant fournit le secret

/* le choix du nombre premier P, du secret K, de x et de AA est arbitraire */

P=prime(1010) K=Mod(4131,P) AA=Mod(124,P)

/* a_1 est aléatoire (=AA), le choix de l'autre coefficient secret a_2 ici n'est pas aléatoire du tout: !*/

a=Mod([AA,(-K-AA*(x[1]+x[2]))/(x[1]*x[1]+x[2]*x[2])],P)

/* Calcul classique des clés:*/

y=[K+a[1]*x[1]+a[2]*x[1]*x[1],K+a[1]*x[2]+a[2]*x[2]*x[2],K+a[1]*x[3]+a[2]*x[3]*x[3],K+a[1]*x[4]+a[2]*x[4]*x[4],K+a[1]*x[5]+a[2]*x[5]*x[5]]

/* Vérification avec la coalition: 1 3 5 */

b=[x[3]*x[5]/((x[3]-x[1])*(x[5]-x[1])),x[1]*x[5]/((x[1]-x[3])*(x[5]-x[3])),x[1]*x[3]/((x[1]-x[5])*(x[3]-x[5]))]

secret=b[1]*y[1]+b[2]*y[3]+b[3]*y[5]

print("On a une information y[1]+y[2]:")

y[1]+y[2]

Résultats :

%69 = 8017

%70 = Mod(4131, 8017)

%71 = Mod(124, 8017)

%72 = [Mod(124, 8017), Mod(5513, 8017)]

%73 = [Mod(1751, 8017), Mod(2380, 8017), Mod(7028, 8017), Mod(4648, 8017), Mod(6287, 8017)]

%74 = [Mod(2904, 8017), Mod(5916, 8017), Mod(7215, 8017)]

%75 = Mod(4131, 8017)

On a une information y[1]+y[2] :

%76 = Mod(4131, 8017)

Liens externes[modifier | modifier le code]

Notes et références[modifier | modifier le code]

↑ (en) Adi Shamir, « How to share a secret », Communications of the ACM, vol. 22, n^o 11,‎ novembre 1979, p. 612–613 (ISSN 0001-0782 et 1557-7317, DOI 10.1145/359168.359176, lire en ligne, consulté le 27 janvier 2023)

[1] (en) Adi Shamir, « How to share a secret », Communications of the ACM, vol. 22, n^o 11,‎ novembre 1979, p. 612–613 (ISSN 0001-0782 et 1557-7317, DOI 10.1145/359168.359176, lire en ligne, consulté le 27 janvier 2023)

[1]