Cryptographie!

Le partage de secret

Partager des secrets, une nécessité
  Il existe de nombreux cas où il faut partager un secret, c'est-à-dire où pour reconstituer un secret, il faut les informations détenues par plusieurs personnes. Par exemple, si vous avez enterré un trésor avec trois autres personnes et que vous avez mis l'emplacement du trésor sur une carte découpée en trois parties, il vous faut faire en sorte qu'il faut les trois parties de la carte pour retrouver l'emplacement du trésor.

  La situation peut aussi être légèrement différente. Dans une banque ayant trois responsables, pour éviter la corruption, on peut estimer qu'aucun responsable ne peut ouvrir à lui seul le coffre. Cependant, il est raisonnable que deux des trois responsables puissent ensemble ouvrir le coffre, notamment si le troisième est indisponible. On parle alors de partage de secret à seuil. C'est par exemple un tel système qui était en oeuvre en Russie au début des années 1990 pour utiliser l'arme nucléaire. Il fallait la participation de deux personnes parmi le président, le ministre de la défense et le chef des armées.

  Plus formellement, on parle de partage de secret à n participants avec seuil k si on partage un secret entre n personnes de sorte que :
  • k personnes prises parmi ces n participants peuvent toujours reconstituer l'information secrète;
  • (k-1) personnes prises parmi ces n participants ne peuvent jamais reconstituer l'information secrète.
Des méthodes simples
  Il existe des méthodes très simples pour partager des secrets. Imaginons que vous vouliez partager un nombre à 4 chiffres parmi n personnes. Aux (n-1) premières personnes, on donne un nombre à 4 chiffres complètement quelconque. A la dernière personne, on donne le premier nombre à 4 chiffres, et à la dernière personne on donne le premier nombre, moins la somme des autres nombres, mais considéré "modulo 10000" (ie en oubliant les retenues après le 4ème chiffre). En faisant la somme des n nombres (toujours modulo 10000), on retrouve le nombre initial, mais en ne connaissant que n-1 nombres, impossible de retrouver le nombre initial.

  Imaginions par exemple que nous voulions partager le nombre 7339 entre 3 participants. Au premier, on donne 3534, au second 8910, et au troisième, on donne $$7339-3534-8910=4895\ \mod 10000.$$ On peut vérifier que $$4895+3534+8910=7339\ \mod 10000,$$ mais on ne peut pas reconstituer ce nombre en connaissant uniquement 4985 et 3534, ou tout autre couple de nombres parmi 3534, 8910 et 4895. On a ainsi fabriqué un partage de secret à n participants, avec un seuil égal à n.

  Voyons maintenant constituer un système de secret à n participants, avec un seul égal à 2 (deux participants quelconques suffisent pour reconstituer le secret). Ce système utilise de très jolie façon de la géométrie élémentaire. Le secret à partager est constitué par les coordonnées d'un point du plan. Ce point est défini comme intersection de deux droites. On commence par donner à tous les participants l'équation d'une de ces deux droites. Sur la deuxième droite, on fixe des points distincts, autant que de participants au partage de secret. À chaque participant on donne les coordonnées d'un de ces points.

  Un participant seul connait donc une droite et un point de l'autre droite. Il ne peut pas reconstituer le point d'intersection. En revanche, si deux participants se mettent ensemble, ils connaissent deux points de la deuxième droite, et donc totalement la deuxième droite. Ils peuvent ainsi reconstituer le point d'intersection.

  Ce protocole tout simple peut être généralisé pour partager un secret avec un seuil de plus que deux personnes. Par exemple, pour avoir un seuil de trois personnes, on remplace la droite secrète par une parabole d'axe parallèle à la droite publique. Il faut trois points sur cette parabole pour la reconstituer.
La protocole de Shamir pour partager un secret
  Le protocole de partage de secret de Shamir, publié en 1979, est une simple évolution des méthodes précédemment décrites. Soit $S$ un secret à partager, que l'on suppose être un nombre réel. Il y a $n$ participants, et le seuil pour reconstituer le secret est $t$ participants. On se donne des réels choisis au hasard et de façon uniforme $a_1,\dots,a_{t-1}$, et on considère le polynôme $$P(X)=S+\sum_{j=1}^{t-1}a_j X^j.$$ $P$ est de degré $t-1$. Chaque participant reçoit un nombre $x_i$, et son image $y_i=P(x_i)$.

  Si $t$ participants mettent leurs informations en commun, ils connaissent $t$ points et leurs images par un polynôme de degré $t-1$. Par la théorie des polynômes interpolateurs de Lagrange, on sait reconstituer $P$, et donc retrouver $S$. On peut démontrer que si on dispose de seulement $t-1$ points et leurs images, on ne peut pas retrouver d'information sur $S$.
Partagez vos secrets
  Grâce au formulaire suivant, vous pouvez partager un secret (nombre à 4 chiffres) en n parts, de sorte qu'il faut les n parts pour reconstituer le secret. Si vous voulez reconstituer le secret en connaissant les parts, séparez les nombres par un espace.

Secret
Nombre de participants
     
Message codé :

Sources : S. Vaudenay, la fracture cryptographique - J. Buchmann, Introduction à la cryptographie