Hollie Little Pink Laptop.jpg
Garçon devant un ordinateur.jpg

Le Livre d'or  • avoir tout Vikidia hors-connexion

Participez à améliorer Vikidia : Pilpay, L'Île au trésor, Sorgho, Chasseur-cueilleur, et 300 autres articles importants et trop courts à compléter. Vos contributions sont les bienvenues !

Partage de secret

Une page de Vikidia, l’encyclopédie junior
Aller à la navigation Aller à la recherche

Le partage de secret est une technique qui permet de répartir entre plusieurs personnes une information secrète, typiquement une clef. Grâce à cette technique, une personne seule ne pourra pas accéder à cette information secrète ; seul un groupe de personnes possédant chacune une partie de l’information pourra récupérer l’information complète.

Par exemple, pour le vote électronique, les votes sont comptabilisés par un ordinateur. Pour empêcher que quelqu'un ne découvre avant les autres le résultat du vote, cet ordinateur est protégé par une clef qui est « répartie » entre différentes personnes. Si toutes ces personnes sont réunies, elles peuvent reconstituer la clef ; mais s’il manque une personne, les autres ne peuvent pas retrouver la clef ni, donc, découvrir le résultat du vote.

Méthode naïve[modifier | modifier le wikicode]

Comment faire ?[modifier | modifier le wikicode]

Imaginons que la clef soit : « abcdefghijklmnopqr ».

La méthode la plus simple peut être de découper cette clef en autant de morceaux que de personnes doivent la partager. Ainsi, si trois personnes doivent se réunir pour récupérer la clef, on donnera à chaque personne un morceau de la clef et la position de ce morceau :

  1. La personne n°1 obtiendra « abcdef************ ».
  2. La personne n°2 obtiendra « ******ghijkl****** ».
  3. La personne n°3 obtiendra « ************mnopqr ».

Inconvénients[modifier | modifier le wikicode]

Cependant, cette méthode n’est pas sûre. En effet, ceux qui possèdent un morceau de la clef ont beaucoup plus de chances que les autres de retrouver la clef : sur une clef de 18 caractères, eux n’ont que 12 caractères à trouver (puisqu’ils connaissent déjà leurs six propres caractères), alors que ceux qui n’ont pas de morceau de la clef doivent trouver les 18 caractères. Si la clef ne contient que des lettres minuscules, pour essayer toutes les possibilités, trouver 18 caractères demande 2618 = 29 479 510 200 013 920 000 000 000 essais ; trouver 12 caractères ne demande « que » 2612 = 95 428 956 661 682 180 essais, c’est-à-dire quand même 308 915 776 fois moins !

Pire : si la personne n°3 persuade ou force la personne n°2 de lui dire sa partie de clef, elle connaîtra alors 12 caractères sur 18 et n’aura donc que 266 = 308 915 776 essais à faire, au maximum, pour découvrir la clef complète. Un ordinateur le fait très rapidement.

Qu’améliorer ?[modifier | modifier le wikicode]

Dans les vrais systèmes de partage de secret, quel que soit le nombre de clefs que l’on connaisse, on a toujours les mêmes chances que n’importe qui d’autre de découvrir la clef complète. De plus, si l’on dit que la clef a été « découpée » en morceaux, ces systèmes permettent généralement à un groupe de personnes, où , de récupérer la clef complète. Cela peut-être très utile : par exemple, dans le cas où l’une des personnes détenant un morceau de clef perdait celui-ci ou même mourait, on pourrait quand même encore retrouver la clef et le secret ne serait pas perdu pour toujours.

Méthode de Shamir[modifier | modifier le wikicode]

La méthode dite « de Shamir » (en anglais : Shamir's Secret Sharing Scheme) est une méthode de partage de secret inventée en 1979 par le cryptologue Adi Shamir, l’un des inventeurs de RSA. Elle repose sur les mathématiques (comme la plupart du temps en cryptologie) et corrige les défauts de la méthode naïve :

  • sa sécurité est théorique, ce qui signifie qu’elle ne dépend pas de la puissance de calcul dont l’attaquant dispose. Cela veut dire qu’un gouvernement (qui dispose de supercalculateurs et d’équipes de « casseurs de codes ») a les mêmes chances que n’importe qui d’autre de découvrir le secret sans en avoir le droit ;
  • s’il faut un nombre de « morceaux de secret » pour retrouver le secret, alors quelqu'un qui connaît morceaux n’a pas plus de chances de retrouver le secret entier que quelqu'un qui ne connaît qu’un morceau, ou même aucun morceau ;
  • on peut découper le secret en morceaux et permettre que n’importe quel groupe de morceaux, avec , reconstitue le secret.

Exemple d’utilisation[modifier | modifier le wikicode]

Interrogation.svg Dans quel cas peut-on avoir besoin d’employer une méthode aussi sophistiquée ?

Mettons-nous à la place d’un directeur de banque. C’est nous seuls qui devons ouvrir le coffre chaque soir pour les transferts d’argent, donc nous seuls devrions connaître la combinaisons secrète du coffre. Cependant, si nous mourrions soudainement, plus personne ne pourrait ouvrir le coffre !

Pour éviter cette situation, nous avons décidé de partager la combinaison du coffre (notre secret principal) avec nos employés. Cependant, il ne faut pas que l’un d’entre eux décide de vider le coffre… En utilisant la méthode de partage de clef de Shamir, nous pouvons créer des « morceaux de secret ». Nous avons par exemple 36 employés dans notre banque, et nous voulons :

  • que n’importe quel groupe de dix employés puisse ouvrir le coffre tous ensemble ;
  • pouvoir ouvrir nous-mêmes le coffre directement, sans l’aide de personne.

Nous créons donc 46 morceaux de secret avec la méthode de Shamir : un pour chaque employé et dix pour nous (pour pouvoir ouvrir d’un coup le coffre, on simule dix employés). De la sorte, nous pouvons toujours ouvrir le coffre comme avant mais, en plus, les employés eux-mêmes peuvent, au cas où, l’ouvrir aussi ; cependant, pour éviter qu’un voleur qui se serait fait embaucher puisse ouvrir le coffre, il faut qu’ils s’y mettent à dix à la fois.

Deux avantages supplémentaires de la méthode de Shamir :

  • si nous embauchons de nouveaux employés, il est très facile de créer de nouveaux « morceaux de secret » sans modifier ceux des autres (ce qui est impossible avec la méthode naïve : il faut changer le secret principal, ici la combinaison du coffre, et redistribuer tous les morceaux) ;
  • si Arsène Lupin vole les morceaux de secret de plusieurs employés, nous pouvons même annuler la valeur de tous les morceaux déjà distribués et en créer de nouveaux pour les employés, toujours sans modifier la combinaison du coffre. Ainsi, les morceaux volés ne permettent plus de reconstituer la combinaison.

Fonctionnement[modifier | modifier le wikicode]

Morceler le secret[modifier | modifier le wikicode]

Par deux points1 (en bleu), on peut faire passer n’importe quels polynômes de degré 2 (ici, le rouge, le vert et le jaune). Si l’on ajoute un point, en revanche, il n’y a plus qu’un polynôme de degré 2 qui passe par les trois en même temps.

Le partage de secret de Shamir utilise des notions de mathématiques qui s’expliquent facilement, même si elles sont un peu avancées.

Article à lire : polynôme.

Un polynôme est la somme de termes dits variables (des coefficients multipliés par une puissance de l’inconnue) et d’un terme dit constant (qui n’est pas multiplié par l’inconnue). On va créer un polynôme dont le terme constant sera notre secret. Pour cela, il faut donc que notre secret ait la forme d’un nombre. Dans le cas du directeur de banque, c’est la combinaison du coffre, disons 235711.

Toujours dans l’exemple de la banque, nous voulons créer 46 morceaux de secret et que des groupes de 10 détenteurs d’un morceau de secret puissent retrouver le secret en se réunissant. Il existe justement un résultat très intéressant sur les polynômes :

Par points1 passe une infinité de polynômes de degré . Par contre, par points1 ne passe qu’un unique polynôme de degré .

Par conséquent, notre polynôme peut être entièrement déterminé si l’on connaît suffisamment de points par lesquels il passe. Les morceaux de secret que nous allons distribuer seront donc des points de notre polynôme : si assez de points sont réunis, on pourra reconstituer le polynôme et donc son terme constant, qui est le secret principal !

Nous voulons d’abord créer 46 morceaux de secret : il faut donc créer 46 points, n’importe lesquels. Cela sera très facile dès que nous aurons notre polynôme. Ensuite, nous voulons que 10 points suffisent à reconstituer le polynôme : il faut donc que celui-ci soit de degré . Nous savons que son terme constant doit être la combinaison du coffre, notre secret : 235711. Pour les autres coefficients, nous n’avons qu’à les prendre au hasard, par exemple : 5, 9, 1, 17, -4, 2, -13, 0, 1, ce qui nous donne le polynôme :

Pour créer les 46 points (un par employé et dix pour nous), il ne reste plus qu’à calculer le résultat par de 46 nombres distincts, par exemple l’ordre d’embauche de chaque employé par la banque et dix autres nombres aléatoires pour nous. Pour le troisième plus ancien employé, on fera ainsi :

donc le morceau de secret de cet employé sera le point (3 ; 406597).

Reconstituer le secret[modifier | modifier le wikicode]

Nous avons parce que, pour pouvoir déterminer sans le connaître, il faut connaître au moins dix points par lesquels il passe. Lorsque dix employés ont mis en commun leur dix points, il devient donc possible d’utiliser ce que l’on appelle en mathématiques une interpolation : une méthode qui, à partir des points, donne la fonction qui passe par ces points. L’interpolation utilisée par le partage de secret de Shamir s’appelle interpolation de Lagrange et est assez technique. (Pour son application, on se reportera aux liens externes en fin d’article.)

Sources[modifier | modifier le wikicode]

Notes[modifier | modifier le wikicode]

  1. 1,0 1,1 et 1,2 D’abscisse distincte.
Portail de l'information —  Tout sur les écritures, les codes secrets, les médias...