Partage de clé secrète de Shamir

Un article de Wikipédia, l'encyclopédie libre.
Aller à : navigation, rechercher
Page d'aide sur l'homonymie Pour les articles homonymes, voir Partage.

Le partage de clé secrète de Shamir (Shamir's Secret Sharing) est un algorithme de cryptographie. C'est une forme de partage de secret, 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 le secret.

Parfois, il n'y a pas forcément besoin de tous les participants pour reconstituer le secret, c'est pourquoi nous utilisons parfois le schéma seuil où un nombre k des parties est suffisant pour reconstruire le secret d'origine.

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:

  1. la connaissance de k ou plus D_i pièces rend D facilement calculable.
  2. 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_1x + a_2x^2 + a_3x^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 polynôme). É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 + 94 x^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 )).

La 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 -2 x + \frac{8}{3}

Par conséquent :

\begin{align}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{align}

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 :

  1. 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).
  2. Minimal : La taille de chaque pièce ne dépasse pas la taille des données d'origine.
  3. 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.
  4. 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.
  5. 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 (backdoor) 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 Paques" (Easter egg) qui contiendra une porte dérobée. En l'absence des coefficients du polynome, les participants ne peuvent vérifier si l'autorité les trompe ou non. Tout à l'"air aléatoire".

Les deux exemples suivant veulent attirer l'attention sur la possibilité qu'un seul participant bien choisi peut obtenir le secret dans le cas (3,5) ou que l'association de deux participants bien choisis peuvent également 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, permettrait cette possibilité.

Exemples (Utilisation de Pari/GP - version 2.5.0)[modifier | modifier le code]

Nous adoptons les notations du livre "Cryptographie: Théorie et Pratique", Douglas Stinson, 1996, Chapitre 11 "Systèmes de partage de secret"

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 sont arbitraires */

P=prime(1010)
K=Mod(4131,P)
x=Mod([1,2,30,4,5],P)
AA=Mod(prime(999),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,-AA*x[1]/(x[1]*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éja 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 1er participant et de la clé du 2e participant fournit le secret

/* le choix du nombre premier P, du secret K, de x et de AA sont arbitraires */

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)

Goodbye!

Liens externes[modifier | modifier le code]