Partage de clé secrète de Shamir

Partage de clé secrète de Shamir

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 forcement 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ématique

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

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

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

Système de partage de secret de Shamir

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

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

Choisir au hasard (k − 1) coefficients a1,...,ak − 1 dans F, et soit a0 = S.

Construire le polynôme f(x) = a0 + a1x + a2x2 + a3x3 + ... + ak − 1xk − 1. Soit n'importe quels n points calculés à partir de lui, par exemple i = 1,...,n qui donnent (i,f(i)). Chaque participant se voit attribuer un point (un couple d'antécédent et de l'image correspondante par la fonction polynôme). Étant donné un sous-ensemble de k de ces couples, nous pouvons trouver les coefficients du polynôme à l'aide de l'interpolation polynomiale, le secret étant le terme constant a0.

Utilisation

Exemple

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

Supposons que notre secret est 1234 (S = 1234).

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

(a1 = 166;a2 = 94)

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

f(x) = 1234 + 166x + 94x2

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

(1,1494);(2,1942);(3,2578);(4,3402);(5,4414);(6,5614)

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

La reconstruction

Afin de reconstituer le secret, 3 points seront suffisants.

Par exemple (x0,y0) = (2,1942);(x1,y1) = (4,3402);(x2,y2) = (5,4414).

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

f(x)=\sum_{j = 0}^{2}y_j\ell_j(x)~,

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

\ell_0 =\frac{x-x_1}{x_0-x_1}\frac{x-x_2}{x_0-x_2}=\frac{x-4}{2-4}\frac{x-5}{2-5} = \frac{1}{6}x^2 - \frac{3}{2}x + \frac{10}{3}

\ell_1 =\frac{x-x_0}{x_1-x_0}\frac{x-x_2}{x_1-x_2}=\frac{x-2}{4-2}\frac{x-5}{4-5} = -\frac{1}{2}x^2 + \frac{7}{2}x -5

\ell_2 =\frac{x-x_0}{x_2-x_0}\frac{x-x_1}{x_2-x_1}=\frac{x-2}{5-2}\frac{x-4}{5-4} = \frac{1}{3}x^2 -2 x + \frac{8}{3}

Par conséquent :

\begin{align}f(x)&= 1942(\frac{1}{6}x^2 - \frac{3}{2}x + \frac{10}{3})+ 3402(-\frac{1}{2}x^2 + \frac{7}{2}x -5)+ 4414(\frac{1}{3}x^2 -2x + \frac{8}{3})\\&= 1234 + 166x + 94x^2\end{align}

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

Propriétés

Certaines des propriétés utiles du schéma seuil (k,n) 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 k est fixe, Di 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.

Liens externes


Wikimedia Foundation. 2010.

Contenu soumis à la licence CC-BY-SA. Source : Article Partage de clé secrète de Shamir de Wikipédia en français (auteurs)

Игры ⚽ Поможем решить контрольную работу

Regardez d'autres dictionnaires:

  • Clé privée — Cryptographie asymétrique La cryptographie asymétrique, ou cryptographie à clé publique, est une méthode de chiffrement qui s oppose à la cryptographie symétrique. Elle utilise une clé publique (qui est diffusée) qui permet de coder le message et …   Wikipédia en Français

  • Clé publique — Cryptographie asymétrique La cryptographie asymétrique, ou cryptographie à clé publique, est une méthode de chiffrement qui s oppose à la cryptographie symétrique. Elle utilise une clé publique (qui est diffusée) qui permet de coder le message et …   Wikipédia en Français

  • Partage de secret — Secret réparti Blakley: Chaque partage de secret est un plan et le secret est le point d intersection entre les trois partages. Deux partages se croisent seulement en une ligne d intersection …   Wikipédia en Français

  • Chiffrement à clé publique — Cryptographie asymétrique La cryptographie asymétrique, ou cryptographie à clé publique, est une méthode de chiffrement qui s oppose à la cryptographie symétrique. Elle utilise une clé publique (qui est diffusée) qui permet de coder le message et …   Wikipédia en Français

  • Cryptographie à clé publique — Cryptographie asymétrique La cryptographie asymétrique, ou cryptographie à clé publique, est une méthode de chiffrement qui s oppose à la cryptographie symétrique. Elle utilise une clé publique (qui est diffusée) qui permet de coder le message et …   Wikipédia en Français

  • Sécurité matérielle des cartes à puce — La sécurité matérielle des cartes à puce et des autres microcontrôleurs est l un des éléments clefs de la sécurité des informations sensibles qu ils manipulent. La littérature scientifique a produit un grand nombre de publications visant à… …   Wikipédia en Français

  • Cryptographie asymétrique — La cryptographie asymétrique, ou cryptographie à clé publique, est une méthode de chiffrement qui s oppose à la cryptographie symétrique. Elle repose sur l utilisation d une clé publique (qui est diffusée) et d une clé privée (gardée secrète), l… …   Wikipédia en Français

  • Chiffrement asymétrique — Cryptographie asymétrique La cryptographie asymétrique, ou cryptographie à clé publique, est une méthode de chiffrement qui s oppose à la cryptographie symétrique. Elle utilise une clé publique (qui est diffusée) qui permet de coder le message et …   Wikipédia en Français

  • Clef privée — Cryptographie asymétrique La cryptographie asymétrique, ou cryptographie à clé publique, est une méthode de chiffrement qui s oppose à la cryptographie symétrique. Elle utilise une clé publique (qui est diffusée) qui permet de coder le message et …   Wikipédia en Français

  • Clef publique — Cryptographie asymétrique La cryptographie asymétrique, ou cryptographie à clé publique, est une méthode de chiffrement qui s oppose à la cryptographie symétrique. Elle utilise une clé publique (qui est diffusée) qui permet de coder le message et …   Wikipédia en Français

Share the article and excerpts

Direct link
… Do a right-click on the link above
and select “Copy Link”