Une introduction à l'algorithme cryptographique de partage secret de Shamir

Le partage secret d'Adi Shamir est un algorithme cryptographique qui permet à des parties distinctes de partager conjointement la propriété d'un seul secret en détenant des actions . Le secret d'origine ne peut être reconstitué qu'en utilisant un nombre minimum de partages, ce qui permet aux différentes parties de coopérer sans avoir besoin de se faire entièrement confiance.

Exemple de problème

Pour illustrer, imaginons qu'une famille de quatre personnes partage un seul portefeuille Bitcoin. Ce portefeuille Bitcoin contient une seule clé privée que tous les membres de la famille sont copropriétaires. Parce qu'il n'y a qu'une seule clé, n'importe quel membre de la famille peut utiliser cette clé pour dépenser tous les Bitcoins.

La famille a un problème : s'ils gardent chacun une copie, alors une seule de leurs copies doit être compromise pour que toutes les pièces soient volées. Si un seul d'entre eux garde la clé, alors cette personne peut la perdre ou décider de doubler les autres membres de la famille.

Heureusement, l'un des membres de la famille est également cryptographe. Au lieu de partager naïvement la clé d'origine, ils utilisent SSS (Shamir's secret sharing). La famille crée quatre actions et fixe un seuil de trois, avec la clé Bitcoin comme secret d'origine. Maintenant, leur plan a les propriétés suivantes :

• Ils n'ont pas stocké la clé bitcoin à un seul endroit, ce qui la rend plus difficile à voler
• Les membres de la famille doivent coopérer pour dépenser le Bitcoin, un membre de la famille ne peut pas trahir les autres
• Si un membre de la famille décède ou perd sa part, les trois autres membres peuvent encore reconstituer la clé

Comprendre le seuil

Chaque système de partage Shamir a un nombre total d'actions et un seuil. Le seuil est le nombre de partages requis pour reconstituer le secret d'origine. Par exemple, avec cinq partages et un seuil de trois, vous n'avez besoin que de trois des cinq partages pour calculer le secret d'origine.

Les maths - Lignes

L'une des propriétés mathématiques fondamentales utilisées dans le partage secret de Shamir est le fait qu'il faut k points pour définir un polynôme de degré k - 1. Par exemple :

• Une seule ligne peut être tracée entre deux points
• Une seule parabole possible passe par les trois mêmes points
• Une seule courbe cubique passe par les quatre mêmes points
• Un nombre infini de lignes peut être tracé à travers le même point
• Un nombre infini de paraboles peut être tracé à travers les deux mêmes points

Les maths - procédure pas à pas

Construisons un schéma pour partager notre secret 1954 ( S) avec 4 ( n) partages et un seuil de 3 ( k) .

Tout d'abord, nous choisissons au hasard k - 1 entiers positifs, donc dans notre cas, 2 entiers positifs. Nous choisissons au hasard 43 et 12.

Ensuite, on construit un polynôme de la forme

 y = a0 + a1*x + a2*x^2

Où a0 est le secret, et a1 et a2 sont nos entiers choisis au hasard. Il nous reste :

 y = 1954 + 43x + 12x^2

Ensuite, nous utilisons cette formule pour créer 4 points (actions) que nous donnons à chaque participant.

Partager 1

(x, y) où x = 1

y = 1954 + 43*1 + 12*1^2 = 2009

(1, 2009)

Partager 2

(x, y) où x = 2

y = 1954 + 43*2 + 12*2^2 = 2088

(2, 2088)

Partager 3

(x, y) où x = 3

y = 1954 + 43*3 + 12*3^2 = 2191

(3, 2191)

Partager 4

(x, y) où x = 4

y = 1954 + 43*4 + 12*4^2 = 2318

(4, 2318)

Reconstruction

Chaque participant à notre système possède désormais un (x,y) , qui est une action unique. Rappelons que nous fixons notre seuil à 3 et que 3 points définissent parfaitement une parabole (polynôme de degré 2). Cela signifie que si nous utilisons trois points, nous pouvons tracer une parabole et calculer a0 (le secret). Supposons que nous ayons le contrôle des actions 1, 2 et 4.

Étape 1 - Tracez les points (parts) que nous contrôlons

Étape 2 - Dessinez la parabole correspondante

Étape 3 - Trouvez le point où x=0 . Sa valeur y est le secret

Dans notre cas, le secret est 1954 .

Ce n'est pas si simple en fait. Nous avons besoin de champs finis.

Bien que l'exemple que nous avons travaillé ci-dessus soit idéal à des fins de démonstration, il n'est en fait pas très sécurisé. Pour chaque partage obtenu par un attaquant, il obtient en fait de plus en plus d'informations sur le secret. Bien que deux points ne décrivent pas parfaitement une parabole, ils laissent encore échapper des informations critiques sur la parabole.

La solution réside dans l'arithmétique des corps finis . En traçant la fonction sur un champ fini de taille suffisante, le graphique du polynôme devient disjoint et dispersé, ce qui signifie que l'attaquant est incapable de faire des suppositions éclairées sur le cheminement de la fonction sous-jacente.

Adi Shamir

Adi Shamir est un cryptographe israélien célèbre pour le partage secret de Shamir, mais il est également co-inventeur de l'algorithme RSA largement utilisé sur lequel repose la grande majorité d'Internet. Shamir est né à Tel-Aviv et a obtenu un diplôme de premier cycle en mathématiques à l'université de Tel-Aviv. Plus tard, il a obtenu sa maîtrise et son doctorat. diplômes en informatique de l'Institut Weizmann en 1975 et 1977 respectivement.