Accueil > Maths difficiles, Vulgarisation > Partage de secret

Partage de secret

07/07/2010 Tukikun Commenter Allez aux commentaires

Supposons que le PDG d’une grande compagnie de soda veuille garder secrète la recette qui a fait la fortune de l’entreprise. Il l’enferme donc dans un coffre fort blindé, qui s’ouvre à l’aide d’une certaine clé (qu’il garde secrète). Cette solution est très sécuritaire dans le sens où seul le PDG peut accéder au secret. Mais elle revêt un gros défaut : si le PDG perd cette clé, ou vient à décéder dans un accident, la clé est perdue et personne ne peut jamais accéder à la recette, entraînant inévitablement la déroute de la multinationale.

Une des solutions est de donner des copies de cette clé secrète à des collaborateurs au travail. Mais répliquer la clé augmente les chances des espions de l’obtenir et de rapporter la recette à l’entreprise concurrente. Le PDG est bien conscient qu’il ne peut pas faire entièrement confiance à un de ses 5 subordonnés. Il veut donc mettre en place un schéma où tout groupe contenant au moins 3 de ses subordonnés puisse ouvrir le coffre alors que tout groupe contenant strictement moins de 3 subordonnés ne puisse rien savoir sur la clé.
Une solution qui consisterait à donner des bouts du secret aux subordonnés de manière à ce qu’ensemble ils puissent le reconstruire ne convient pas parce qu’ils connaîtraient alors partiellement la clé secrète.

Ce problème peut-être résolu par la mise en place d’un schéma de partage de secret.

Le partage de secret avec seuil

Notons 2\leq t<n des entiers. Notre but est de partager une clé secrète K entre un ensemble de n personnes \mathcal P = \{P_1, \ldots, P_n\} de telle manière que toute coalition de t ou plus de ces personnes puisse calculer K facilement, et que toute coalition de t-1 ou moins de ces personnes ne puisse rien déterminer sur la valeur de K, autrement dit que toutes les valeurs de K possibles soient équiprobables. Un tel schéma est appelé un schéma au seuil (t,n). Dans l’exemple introductif, le PDG cherche un schéma au seuil (3,5).

La valeur du secret est choisie par un participant spécial D (le dealer) (que l’on suppose bien évidemment ne pas faire partie de \mathcal P). Le dealer va donner à chaque participant une clé de partage. Cette distribution sera secrète bien entendu, pour qu’aucun des participants ne connaissent les clés de partage des autres participants.

Le problème de construire un tel schéma a été résolu indépendamment par Sharmir [1] et Blakley [2] en 1979.

Schéma de Shamir

Commençons par présenter le schéma de Shamir, qui repose sur l’interpolation polynômiale.

Le dealer veut partager la clé secrète K\in \mathbf F_q où q\geq n+1 est la puissance d’un nombre premier (on peut prendre q=p premier et raisonner dans \mathbf F_p bien évidemment). Il choisit de manière aléatoire n éléments distincts de \mathbf F_q que l’on note x_1, \ldots, x_n. Ces éléemnts ne sont pas les clés de partages secrètes, ce sont des clés publiques : chaque P_i reçoit la clé x_i. Dans l’exemple du PDG, on pourrait dire par exemple que x_i représente l’ordre d’arrivée de l’employé dans l’entreprise. Ensuite, il réalise les étapes suivantes :

  1. Il choisit secrètement et aléatoirement t-1 éléments de \mathbf F_q notés a_1, \ldots, a_{t-1}.
  2. Pour tout 1\leq i\leq n, le dealer calcule y_i=a(x_i) où

    a(X) = K+\sum_{i=1}^{t-1}a_jX^j.

  3. Pour tout 1\leq i\leq n, le dealer donne secrètement la clé de partage y_i à P_i

Regardons comment un groupe B=\left\{P_{i_1}, \ldots, P_{i_t}\right\} de t personnes (avec leur clé publique x_i) peut retrouver les coefficients secrets du polynôme a(X) par interpolation, et ainsi retrouver K=a(0). Comme y_{i_k} = a(x_{i_k}) pour tout 0\leq k\leq t, le groupe B obtient t équations linéaires en les t inconnues K, a_1, \ldots, a_{t-1}. Ainsi, le système obtenu par B peut-être écrit sous la forme

\begin{pmatrix}1& x_{i_1}& x_{i_1}^2& \cdots& x_{i_1}^{t-1}\\1& x_{i_2}& x_{i_2}^2& \cdots& x_{i_2}^{t-1}\\\vdots& \vdots & \vdots & & \vdots\\1& x_{i_t}& x_{i_t}^2& \cdots& x_{i_t}^{t-1}\\\end{pmatrix}\begin{pmatrix}K\\a_1\\\vdots\\a_{t-1}\end{pmatrix} = \begin{pmatrix}y_{i_1}\\y_{i_2}\\\vdots\\y_{i_t}\end{pmatrix}.

Or, la matrice A des coefficients x_i est appelée matrice de Vandermonde et son déterminant vaut \det(A) = \prod_{1\leq k<j\leq t}\left(x_{i_j}-x_{i_k}\right)\neq 0. Comme il est non nul (par choix des x_i), le système admet une unique solution sur \mathbf F_q, et K peut-être retrouvé.

Supposons maintenant que t-1 des n clés de partages secrètes sont révélées à un ennemi. Pour chaque candidat K'\in \mathbf F_q pour le secret, l'ennemi peut construire un et un unique polynôme a'(X) de degré t-1 tel que a'(0)=K' et a'(x_i)=y_i pour les t-1 clés connues. Par construction, ces q possibles polynômes sont équiprobables, en conséquence de quoi l'espion ne peut rien déduire sur la valeur de la clé secrète K.

Bien entendu, il y a une méthode alternative basée sur la formule de l'interpolation de Lagrange. La formule est la suivante :

a(X) = \sum_{j=1}^t y_{i_j} \prod_{\substack{1\leq k\leq t\\k\neq j}}\frac{X-x_{i_k}}{x_{i_j}-x_{i_k}}.

Étant donné qu’un groupe recherche la valeur du secret K=a(0), ils peuvent calculer

K = \sum_{j=1}^{t}y_{i_j}b_j, \qquad \text{avec} \quad b_j = \prod_{\substack{1\leq k\leq t\\k\neq j}}\frac{x_{i_k}}{x_{i_k}-x_{i_j}}.

Remarquons que les valeurs b_j ne dépendent que des x_i et peuvent-être pré-calculées.

Un exemple concret

Donnons un petit exemple concret pour soulager notre PDG qui a vraiment peur de faire un infarctus qui perdrait à tout jamais la recette ! Supposons que q=17 et que les coordonnées publiques sont x_i = i pour tout 1\leq i\leq 5. Supposons maintenant que les collaborateurs P_1, P_3 et P_5 veuillent retrouver le secret. Ils mettent en commun leurs clés de partages secrètes qui sont respectivement 8, 10 et 11. Comme a(X) = K+a_1X+a_2X^2, ils obtiennent le système d’équation suivant :

\left\{\begin{array}{lll}K+a_1+a_2 &=&8\\K+3a_1+9a_2&=&10\\K+5a_1+8a_2&=&11\end{array}\right.

Ce système admet une unique solution dans \mathbf F_{17}=\mathbf Z/17\mathbf Z : K=13, a_1=10 et a_2=2. Le secret est donc K=13 !

Schéma de Blakley

Donnons un autre exemple : le schéma de Blakley basé sur la géométrie des hyperplans sur les corps finis. Le secret est un point d’un espace t-dimensionnel, et les n clés de partages secrètes sont des hyperplans affines passant par ce point. Un hyperplan dans un espace t-dimensionnel à coordonnées dans un corps \mathbf F peut être décrit par une équation de la forme suivante :

a_1x_1 + a_2x_2 + \cdots + a_tx_t = y.

Le point d’intersection est obtenu en trouvant l’intersection d’un ensemble quelconque de t de ces hyperplans. Par exemple, le secret peut être la première coordonnée du point d’intersection.

Disons que \mathbf F = \mathbf F_q est le corps sur lequel on travaille. Le dealer génère un point x dans \mathbf F_q^t, où la première coordonnée x_1 est la clé secrète et les autres coordonnées sont choisies aléatoirement dans \mathbf F_q. Le ième participant recevra comme clé de partage secrète l’hyperplan sur \mathbf F_q d’équation

a_{i,1}x_1+a_{i,2}x_2+\cdots+a_{i,t}x_t=y_i.

Pour obtenir un schéma au seuil (t, n), il y aura n équations d’hyperplan, et on obtient alors un système linéaire n\times t: Ax=y.

Le dealer donne en pratique la clé de partage secrète y_i ainsi que les coordonnées (qui peuvent être publiques) a_{i,1}, \ldots, a_{i,t} au participant P_i. un choix judicieux pour la matrice A est de faire en sorte que ses lignes soient les lignes d’une matrice de Vandermonde pour se ramener à une situation similaire à celle du schéma de Shamir.

Pour aller plus loin…

Bien entendu, ceci n’est qu’une introduction sommaire à un domaine toujours en pleine expansion en cryptologie. On pourra trouver d’autres schémas basés sur la géométrie, sur les graphes, sur le théorème des restes chinois… Une excellente introduction au sujet est l’article [3].

Pour les plus intrépides d’entre vous, remarquez que jusquà présent nous avons travaillé sur des corps, s’autorisant allégrement la possibilité d’inverser pour retrouver le secret si nécessaire. Un sujet intéressant est de vouloir construire des schémas valables sur n’importe quel groupe abélien (sans connaître le groupe, c’est-à-dire un schéma en boîte noire), qui ont fait l’objet de deux articles récents [4] et [5].

Références
  • [1] A. Shamir – « How to share a secret », Communications of the ACM 22 (1979), no. 11, p. 612 – 613.
  • [2] G. R. Blakley – « Safeguarding cryptographic keys », AFIPS Conference Proceedings 48 (1979), p. 313 – 317.
  • [3] D. R. Stinson – « An explication of secret sharing schemes », Designs, Codes and Cryptography 2 (1992), no. 4, p. 357 – 390.
  • [4] R. Cramer & S. Fehr – « Optimal black-box secret sharing over arbitrary Abelian groups », Advances in Cryptology – CRYPTO’02 (2002), p. 272 – 287.
  • [5] R. Cramer, S. Fehr & M. Stam – « Black-box secret sharing from primitive sets in algebraic number fields », Advances in Cryptology – CRYPTO 2005, Springer, 2005, p. 344-360.
Categories: Maths difficiles, Vulgarisation Tags: , , , , , , , , ,
  1. Pas encore de commentaire
  1. Pas encore de trackbacks

Vous pouvez insérer des formules mathématiques en latex dans vos commentaire, on les mettant entre $latex et $.