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.

Définition mathématique

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

1. la connaissance de k ou plus D_i pièces rend D facilement calculable.
2. la connaissance de k − 1 ou moins D_i 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 a₁,...,a_{k − 1} dans F, et soit a₀ = S.

Construire le polynôme f(x) = a₀ + a₁x + a₂x² + a₃x³ + ... + a_{k − 1}x^{k − 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 a₀.

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.

(a₁ = 166;a₂ = 94)

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

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

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 (x₀,y₀) = (2,1942);(x₁,y₁) = (4,3402);(x₂,y₂) = (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, D_i 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

• (en) ssss: Une implémtentation libre (GPL) du schéma de Shamir avec une démonstration en ligne
• (en) Une implémentation en Perl du partage de clé secrète de Shamir
• (en) Secret Sharp : une implémentation libre (GPL) du schéma de Shamir pour Windows
• (en) Implémentation web de Christophe David 'Comment partager un secret'