Comment partager un secret ?

Piste rouge Le 5 mars 2017  - Ecrit par  Romain Dujardin Voir les commentaires (1)

On rencontre de nombreuses situations pratiques
où il peut être utile de séparer un secret en plusieurs morceaux :

  • Une entreprise est la propriété de 10 actionnaires un peu craintifs. Ils tiennent absolument à ce que 7 d’entre eux soient d’accord
    pour chaque dépense. Comment mettre en place un protocole assurant qu’une coalition de 6 actionnaires ou moins ne pourra pas siphonner les comptes ?
  • Le président Trump n’arrête pas d’oublier le code nucléaire, il faut donc le noter quelque part. Pour une sécurité optimale, l’état major décide de le séparer en plusieurs morceaux, stockés dans 12 bunkers disséminés à travers l’Union, de sorte que si l’ennemi prend 5 quelconques de ces bunkers, le code pourra toujours être reconstitué sans pour autant tomber aux mains de l’ennemi.
  • La société Cumulus Inc., spécialisée dans le stockage en ligne, dispose d’une vingtaine de data-centers disséminés sur la planète. Elle assure à ses clients que le système fonctionne même si la moitié de ses serveurs se retrouve hors ligne, et que néanmoins les données restent confidentielles même si plusieurs d’entre eux sont piratés.
JPEG - 106.4 ko
cadenas collectif

Une solution rudimentaire à ce problème est la suivante
(raisonnons dans le cadre de la société par actions, les autres situations sont similaires) : on met le numéro de compte dans une boîte fermée par
plusieurs serrures, et on distribue à chaque actionnaire un certain nombre de clefs, de sorte que 6 actionnaires n’ont jamais simultanément toutes les clefs.
Un petit raisonnement montre que la solution nécessite
au moins 210 serrures sur la boîte, et 84 clefs par actionnaire... Bref, ça fait beaucoup !
Et il reste encore à trouver un algorithme pour attribuer individuellement les clefs...

Détails du raisonnement.

Il y a $\binom{10}{6} = 210$ groupes distincts de 6 personnes, numérotons les de $G_1$ à $G_{210}$. Il manque au premier groupe
$G_1$ une clef $s_1$ pour ouvrir le coffre. J’affirme qu’il manque à $G_2$ une autre clef $s_2$ : en effet si la seule clef manquante à $G_2$ était $s_1$, on pourrait
trouver un sous-ensemble de 7 personnes dans l’union de $G_1$ et $ G_2$ ne pouvant ouvrir la boîte. On continue ainsi de suite le raisonnement en montrant que
pour le groupe $G_i$ il y a une nouvelle clef $s_i$ qui manque, différente des précédentes. Sinon avec le même raisonnement, on trouverait un ensemble de 7
personnes parmi $G_i$ et $G_j$ pour un
certain
$j < i$
et ne pouvant ouvrir la boîte. On conclut de ce raisonnement qu’il faut au moins 210 serrures sur la boîte.
En outre, chaque actionnaire doit avoir sur lui au moins $\binom{9}{6} = 84$ clefs, puisque pour chaque groupe de 6 actionnaires parmi les 9 restants, il doit posséder
la clef manquant à ce groupe.

JPEG - 1.9 Mo
Adi Shamir

Voici une méthode élémentaire et très efficace
proposée par Adi Shamir [1] dans un article fameux [2].

Pour comprendre l’algorithme, commençons par une situation très simple. Le couple le plus célèbre de l’informatique, Alice et Bob, voudrait partager le
code à 4 chiffres de leur carte bancaire, un nombre secret noté $S$ compris entre 0000 et 9999. Pour cela, il suffit de choisir deux nombres entiers $a$ et $b$ tels que $a+b=S$ et de fournir $a$ à Alice et $b$ à Bob. S’ils veulent faire un achat commun, il leur suffit d’ajouter leurs codes respectifs. [Il faut pour cela imaginer un dispositif technique qui permette à chacun d’entrer secrètement son code de son côté, mais ce n’est pas le point ici.] Tout ceci est très simple, mais il y a une faille potentielle : supposons qu’Alice se voie attribuer le code $a = 9958$. Elle dispose alors d’une information capitale sur $S$ : il est compris entre 9958 et 9999, elle peut donc le trouver en au plus 42 tentatives. Pas très robuste... surtout s’il s’agit du code nucléaire !

Pour y remédier, une astuce classique est de travailler modulo 10000, c’est à dire de calculer en ajoutant ou retirant
autant de multiples de 10000 que nécessaire pour revenir entre 0000 et 9999, par exemple $8545+2651 = 11196 =1196$. On peut alors choisir $a$ au hasard entre 0000 et 9999 et poser $b = S- a$ mod. 10000. On voit que maintenant la connaissance de $a$ n’apporte plus
aucune information sur $S$.

Comment faire maintenant pour partager un secret à $n\geq 3$ personnes de sorte que 2 personnes au moins soient nécessaires pour le révéler ?
L’idée de Shamir est de tout simplement considérer....une droite. En effet, une droite est complètement déterminée par deux de ses points,
et à l’inverse la connaissance d’un point sur cette droite ne révèle que peu d’information sur celle-ci.
En formules, supposons que notre secret est un entier naturel $S$, et choisissons une droite dans le plan passant par le point $(0,S)$, son équation est donc de la forme $y = m x+ S$ (avec $m$ entier). L’information donnée
au participant $A_i$ est le point d’abscisse $i$ sur la droite, soit le point de coordonnées $(i,a_i)$. Si deux participants entrent leurs codes $(i,a_i)$ et $(j,a_j)$, l’ordinateur calcule la pente $ m= \frac{a_j - a_i}{j-i}$ et en déduit $S$ par la formule $S = a_i - m i$. Joli, non ?

JPEG - 19.1 ko
Une droite est déterminée par deux de ses points.

En pratique, il y a la même faille que précédemment, et plutôt qu’avec des entiers naturels, il vaut mieux travailler modulo $N$, où $N$ est un entier
assez grand. Mieux, il est préférable de choisir pour $N$ un nombre premier : déplier le paragraphe suivant pour quelques détails.

Explication

Supposons que le code d’Alice soit $(1,37)$. De deux choses l’une : soit le code est compris entre 0 et 37,
soit la pente est négative, mais comme par hypothèse tous les $a_i$ sont des entiers positifs, on aura par exemple
$a_2 = 2m+ S$. Mais $37 = m+S$ donc $0\leq a_2 = m+37$ et donc $m\geq -37$. Dans tous les cas, on conclut que $0\leq S\leq 74$, ce qui ne fait pas beaucoup de possibilités...

Qu’à cela ne tienne, travaillons modulo 10000 ! Le souci, c’est que le calcul de la pente fait intervenir une division, et que les divisions modulo 10000
sont mal définies : $5226/2 = 2613 "=" 15226/2 =7613$, lequel choisir ? Le problème vient de ce que 10000 est divisible par 2 et
la solution est de travailler modulo $p$, où $p$ est un nombre premier, par exemple 10007 qui est proche de 10000. L’objet dans lequel on calcule s’appelle un corps fini, et les règles ordinaires de l’algèbre s’y appliquent. [3]

Continuons ! S’il faut 3 personnes pour révéler le secret, on utilise maintenant une parabole. Son équation sera de la forme $y = m_2x^2 + m_1 x + S$, où $S$ est le secret.
On distribue donc aux participants des points distincts $(i,a_i)$ sur la parabole, et peu importe le nombre de participants, il
faut 3 points pour la déterminer, et donc déterminer le secret $S$.

JPEG - 17.7 ko
Une parabole est déterminée par trois de ses points.

Pour revenir au problème de départ, notre société par actions n’a qu’à choisir au hasard un polynôme $P$ de degré 6 (sur un corps fini assez grand pour contenir les informations du secret)
\[P(x) = m_6x^6+m_5x^5+m_4x^4+m_3x^3+m_2x^2+m_1x + S\]
dont le terme constant est le numéro du compte en banque, et distribuer à ses actionnaires les valeurs $P(1), P(2), \ldots, P(10)$.

Pour extraire le secret au moment voulu,
comparativement à la solution consistant à ouvrir 210 serrures sur une boîte, le procédé pour inverser la méthode de Shamir est très simple. On détermine par un petit calcul l’unique polynôme de degré 6 qui interpole 7 (ou plus) valeurs connues.
Il y a pour cela une formule explicite, redoutée des étudiants de Licence, et connue sous le nom de formule d’interpolation de Lagrange. [4]

Formule d’interpolation de Lagrange

On se donne $n+1$ scalaires distincts $(x_i)_{1\leq i\leq n+1}$ et des valeurs correspondantes $y_i$, et on cherche
un polynôme $P$ de degré $n$ (qui sera en fait unique)
tel que pour tout $i$, $P(x_i) = y_i$.

On observe d’abord que pour tout $j$
le polynôme $P_j$ défini par la formule
\[P_j(X) = \frac{(X-x_1)(X-x_2)\cdots (X-x_{j-1}) (X-x_{j+1}) \cdots (X-x_{n+1})} {(x_j-x_1)(x_j-x_2)\cdots (x_j-x_{j-1}) (x_j-x_{j+1}) \cdots (x_j-x_{n+1})} \] (noter que le j-ème facteur est omis)
vérifie $P_j(x_j) = 1$ et $P_j(x_i) = 0$ pour $i\neq j$. Il suffit alors de poser
\[P(X) = \sum_{j=1}^{n+1} y_j P_j(X).\]

Post-scriptum :

Merci à Clément Caubel, Nicolas Bédaride et Xavier Goaoc pour leurs commentaires avisés.

Article édité par Romain Dujardin

Notes

[1Adi Shamir, mathématicien et cryptographe israélien, célèbre pour être le « S » de RSA.

[2« How to share a secret », Communications of the ACM, 22 (11) : 612–613. Deux pages et plus de 11000 citations à ce jour, ça laisse rêveur le scientifique ordinaire....

[3Un ordinateur préfèrera sûrement travailler dans un corps à $2^{14} =16384$ voire $2^{15} = 32768$
éléments.

[4Courez voir ce documentaire passionnant sur ce scientifique hors norme.

Partager cet article

Pour citer cet article :

Romain Dujardin — «Comment partager un secret ?» — Images des Mathématiques, CNRS, 2017

Crédits image :

Image à la une - Google Images
Adi Shamir - By Erik Tews (Own work) [CC BY-SA 3.0 (http://creativecommons.org/licenses/by-sa/3.0)], via Wikimedia Commons
cadenas collectif - Tayhope lock borrowed from http://tywkiwdbi.blogspot.fr/2013/07/an-unusual-lock.html

Commentaire sur l'article

  • Comment partager un secret ?

    le 26 mars à 01:03, par projetmbc

    Bonjour.

    N’étant pas satisfait par la 1ère preuve. Je vous propose la version légèrement modifiée suivante. En espérant améliorer un peu les choses.


    Notons que si 6 personnes n’ont pas assez de clés ensemble pour ouvrir le coffre, il en sera de même pour 5 personnes ou moins. Il suffit donc de s’intéresser aux groupes de 6 personnes.

    Le nombre de groupes distincts de 6 personnes parmi 10 est (10 6) = 210 (nombre de combinaisons). Numérotons les groupes de G1 à G210 .

    Par hypothèse, il manque au premier groupe G1 une clef s1 pour ouvrir le coffre. J’affirme qu’il manque ensuite à G2 une autre clef s2.

    En effet, dans le cas contraire si la seule clef manquante à G2 était s1, il suffirait de prendre les personnes du groupe G1 plus une quelconque du groupe G2 pour avoir un sous-ensemble de 7 personnes à qui il manquerait la clé s1 pour ouvrir la boîte. Ceci contredirait les hypothèses.

    On continue ainsi de suite le raisonnement en montrant que pour le groupe Gi il y a une nouvelle clef si qui manque, différente des précédentes. Sinon avec le même raisonnement, on trouverait un ensemble de 7 personnes parmi Gi et Gj pour un certain j < i et ne pouvant ouvrir la boîte.

    On conclut de ce raisonnement qu’il faut au moins 210 serrures sur la boîte.

    En outre, pour chaque groupe Gi de 6 actionnaires, un 7ème actionnaire n’appartenant pas à ce groupe doit posséder la clef manquant à ce groupe Gi. Or pour un actionnaire donné, le nombre de groupes de 6 actionnaires auxquels il n’appartient pas est égal au nombre de groupes de 6 personnes parmi 9, c’est à dire (9 6) = 84. Donc chaque actionnaire doit avoir sur lui au moins (9 6) = 84 clefs.

    Répondre à ce message

Laisser un commentaire

Forum sur abonnement

Pour participer à ce forum, vous devez vous enregistrer au préalable. Merci d’indiquer ci-dessous l’identifiant personnel qui vous a été fourni. Si vous n’êtes pas enregistré, vous devez vous inscrire.

Connexions’inscriremot de passe oublié ?

Suivre IDM