Ouvrir le menu principal

Partage de clé secrète de Shamir

protocole cryptographique
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.

Sommaire

Définition mathématiqueModifier

Formellement, notre objectif est de diviser certaines données   (par exemple, la combinaison du coffre) en   pièces   de telle sorte que:

  1. la connaissance de   ou plus   pièces rend   facilement calculable.
  2. la connaissance de   ou moins   pièces rend   complètement indéterminée (en ce sens que toutes ses valeurs possibles sont également probables).

Ce régime est appelé schéma seuil  . Si   alors tous les participants sont nécessaires pour reconstituer le secret.

Système de partage de secret de ShamirModifier

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   points pour définir un polynôme de degré  .

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

Choisir au hasard   coefficients   dans  , et poser  .

Construire le polynôme  . Soient n'importe quels   points calculés à partir de lui, par exemple   qui donnent  . 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   de ces couples, nous pouvons trouver les coefficients du polynôme à l'aide de l'interpolation polynomiale, le secret étant le terme constant  .

UtilisationModifier

ExempleModifier

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éparationModifier

Supposons que notre secret est 1234  .

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

 

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

 

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

 

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

La reconstructionModifier

Afin de reconstituer le secret, 3 points seront suffisants.

Par exemple  .

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

 

où les j sont les polynômes de base de Lagrange :

 

 

 

Par conséquent :

 

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

PropriétésModifier

Certaines des propriétés utiles du schéma seuil   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   est fixe,   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éeModifier

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 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 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

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

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 secretModifier

/* 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é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 secretModifier

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 externesModifier