Considérez le scénario lorsqu'il est nécessaire d'assurer la sécurité du coffre de banque. Il est considéré comme absolument imprenable sans clé, qui vous est remis le premier jour de travail. Votre objectif est de sauvegarder la clé en toute sécurité.

Supposons que vous décidiez de garder la clé avec vous tout le temps, donnant accès au magasin au besoin. Mais vous vous rendrez rapidement compte qu'une telle solution dans la pratique ne s'adapte pas normalement, car chaque fois que vous avez besoin de votre présence physique pour ouvrir le référentiel. Qu'en est-il des vacances qui vous ont été promises? De plus, la question est encore plus effrayante: et si vous perdiez une seule clé?

En pensant aux vacances, vous avez décidé de faire une copie de la clé et de la confier à un autre employé. Cependant, vous comprenez que ce n'est pas idéal non plus. En doublant le nombre de clés, vous avez également doublé les possibilités de vol de clés.

Désespéré, vous détruisez le double et décidez de diviser la clé d'origine en deux. Maintenant, vous pensez que deux personnes de confiance avec des fragments de clé doivent être physiquement présentes pour récupérer la clé et ouvrir le magasin. Cela signifie que le voleur doit voler deux fragments, ce qui est deux fois plus difficile que de voler une clé. Cependant, vous vous rendrez vite compte que ce schéma n'est pas beaucoup mieux qu'une seule clé, car si quelqu'un perd la moitié de la clé, la clé complète ne peut pas être restaurée.

Le problème peut être résolu avec une série de clés et de verrous supplémentaires, mais avec cette approche, vous aurez rapidement besoin de beaucoup de clés et de verrous. Vous décidez que dans un schéma idéal, vous devez diviser la clé afin que la sécurité ne repose pas entièrement sur une seule personne. Vous concluez également qu'il doit y avoir un certain seuil pour le nombre de fragments, de sorte que si un fragment est perdu (ou si une personne part en vacances), la clé entière reste fonctionnelle.

Comment partager un secret

Ce type de système de gestion des clés a été pensé par Adi Shamir en 1979 lorsqu'il a publié son ouvrage How to Share a Secret . L'article explique brièvement la soi-disant $$$(k, n)$ schéma de seuil pour diviser efficacement une valeur secrète (par exemple, une clé cryptographique) en $$$n$ pièces. Ensuite, quand et seulement quand au moins $$$k$ de $$$n$ pièces assemblées, vous pouvez facilement restaurer le secret $$$S$ .

Du point de vue de la sécurité, une propriété importante de ce schéma est que l'attaquant ne doit absolument rien savoir s'il n'a pas au moins $$$k$ pièces. Même disponibilité $$$k - 1$ les pièces ne doivent donner aucune information. Nous appelons cette propriété la sécurité sémantique .

Interpolation polynomiale

Schéma de seuil de Shamir $$$(k, n)$ construit autour du concept d' interpolation polynomiale . Si vous n'êtes pas familier avec ce concept, il est en fait assez simple. En général, si vous avez déjà dessiné des points sur un graphique, puis les avez connectés avec des lignes ou des courbes, vous l'avez déjà utilisé!


Un nombre illimité de polynômes de degré 2 peut être tracé à travers deux points. Pour choisir le seul, vous avez besoin d'un troisième point. Illustration: Wikipedia

Considérons un polynôme de degré un, $$$f (x) = x + 2$ . Si vous souhaitez tracer cette fonction sur un graphique, de combien de points avez-vous besoin? Eh bien, nous savons que c'est une fonction linéaire qui forme une ligne et donc au moins deux points sont nécessaires. Ensuite, considérons une fonction polynomiale de degré deux, $$$f (x) = x ^ 2 + 2x + 1$ . Il s'agit d'une fonction quadratique, donc au moins trois points sont nécessaires pour construire un graphique. Et un polynôme de degré trois? Au moins quatre points. Et ainsi de suite et ainsi de suite.

La chose vraiment cool à propos de cette propriété est que, compte tenu du degré de la fonction polynomiale, et au moins $$$degré + 1$ points, nous pouvons dériver des points supplémentaires pour cette fonction polynomiale. L'extrapolation de ces points supplémentaires est appelée interpolation polynomiale .

Faire un secret

Vous avez peut-être déjà réalisé que le schéma intelligent de Shamir entre en jeu ici. Supposons que notre secret $$$S$ Est-ce $$ . Nous pouvons tourner $$$S$ à un point sur le graphique $$$(0.42)$ et trouver une fonction polynomiale avec degré $$$k-1$ qui satisfait ce point. Rappelez-vous que $$$k$ sera notre seuil pour les fragments requis, donc si nous fixons le seuil à trois fragments, nous devons choisir une fonction polynomiale de degré deux.

Notre polynôme prendra la forme $$$f (x) = a_0 + a_1x + a_2x ^ 2 + a_3x ^ 3 + ... + a_ {k-1} x ^ {k-1}$ où $$$a_0 = S$ et $$$a_1, ..., a_ {k-1}$ - entiers positifs sélectionnés au hasard. Nous construisons juste un polynôme avec un diplôme $$$k-1$ où est le coefficient libre $$$a_0$ Est notre secret $$$S$ et chacun des éléments suivants $$$k-1$ Les membres ont un coefficient positif choisi au hasard. Si vous revenez à l'exemple original et supposez que $$$S = 42, k = 3, a_1, ..., a_ {k-1} = [3,5]$ alors nous obtenons la fonction $$$f (x) = 42 + 3x + 5x ^ 2$ .

À ce stade, nous pouvons générer des fragments en connectant $$$n$ entiers uniques dans $$$f (x) = 42 + 3x + 5x ^ 2$ où $$$x \ neq 0$ (parce que c'est notre secret). Dans cet exemple, nous voulons distribuer quatre fragments avec un seuil de trois, donc nous générons aléatoirement des points $$$(18, 1716), (27, 3768), (31, 4940), (35, 6272)$ et envoyer un point à chacune des quatre personnes de confiance, gardiens clés. Nous disons aussi aux gens que $$$k = 3$ , car il est considéré comme une information publique et est nécessaire pour la récupération $$$S$ .

Récupération secrète

Nous avons déjà discuté du concept d'interpolation polynomiale et du fait qu'il sous-tend le schéma de seuil de Shamir $$$(k, n)$ . Lorsque trois des quatre mandataires veulent récupérer $$$S$ il suffit d'interpoler $$$f (0)$ avec ses propres points uniques. Pour ce faire, ils peuvent déterminer leurs points $$$(x_1, y_1), ..., (x_k, y_k) = (18, 1716), (27, 3768), (31, 4940)$ et calculer le polynôme d'interpolation de Lagrange en utilisant la formule suivante. Si la programmation vous est plus compréhensible que les mathématiques, alors pi est essentiellement une instruction for qui multiplie tous les résultats, et sigma est une instruction for qui additionne tout.

$$

$$P (x) = \ sum_ {j = 1} ^ {k} p_j (x)$$

$$

$$P_j (x) = y_j \ prod _ {\ scriptstyle m = 1 \ atop \ scriptstyle m \ neq j} ^ {k} \ frac {x-x_m} {x_j-x_m}$$

À $$$k = 3$ nous pouvons résoudre ce problème comme suit et retourner notre fonction polynomiale d'origine:

$$

$$\ begin {aligné} P (x) & = {y_1} \ left ({x-x_2 \ over x_1-x_2} \ cdot {x-x_3 \ over x_1-x_3} \ right) + {y_2} \ left ( {x-x_1 \ over x_2-x_1} \ cdot {x - \ _ 3 \ over x_2-x_3} \ right) + {y_3} \ left ({x-x_1 \ over x_3-x_1} \ cdot {x-x_2 \ sur x_3-x_2} \ droite) \\ P (x) & = {1716} \ gauche ({x-27 \ sur 18-27} \ cdot {x-31 \ sur 18-31} \ droite) + {3768 } \ left ({x-18 \ over 27-18} \ cdot {x-31 \ over 27-31} \ right) + {4940} \ left ({x-18 \ over 31-18} \ cdot {x -27 \ sur 31-27} \ droite) \\ P (x) & = 42 + 3x + 5x ^ 2 \ end {aligné}$$

Parce que nous savons que $$$S = P (0)$ récupération $$$S$ effectué simplement:

$$

$$\ begin {aligné} P (0) & = 42 + 3 (0) + 5 (0) ^ 2 \\ P (0) & = 42 \ end {aligné}$$

Utilisation d'une arithmétique entière non sûre

Bien que nous ayons appliqué avec succès l'idée de base de Shamir $$$(k, n)$ , nous avons encore un problème que nous avons ignoré jusqu'à présent. Notre fonction polynomiale utilise une arithmétique entière non sûre. Notez que pour chaque point supplémentaire que l'attaquant reçoit sur le graphique de notre fonction, il y a moins d'options pour d'autres points. Vous pouvez le voir de vos propres yeux lors de la construction d'un graphique avec une augmentation du nombre de points pour une fonction polynomiale en utilisant l'arithmétique entière. Ceci est contre-productif pour notre objectif de sécurité déclaré, car l'attaquant n'a rien à apprendre avant d'avoir au moins $$$k$ fragments.

Pour démontrer la faiblesse du schéma avec l'arithmétique entière, considérons un scénario dans lequel un attaquant a obtenu deux points $$$(18, 1716), (27,3768)$ et connaît les informations publiques $$$k = 3$ . De ces informations, il peut déduire $$$f (x)$ égal à deux et connectez les valeurs connues dans la formule $$$x$ et $$$f (x)$ .

$$

$$\ begin {aligné} f (x) & = a_0 + a_1x + a_2x ^ 2 + a_3x ^ 3 + ... + a_ {k-1} x ^ {k-1} \\ f (x) & = S + a_1x + a_2x ^ 2 \\ f (18) \ equiv 1716 & = S + a_118 + a_218 ^ 2 \\ f (27) \ equiv 3768 & = S + a_127 + a_227 ^ 2 \ end {aligné}$$

Ensuite, l'attaquant peut trouver $$$a_1$ compter $$$f (27) - f (18)$ :

$$

$$\ begin {aligné} 3768 - 1716 & = (S - S) + (27a_1 - 18a_1) + (729a_2 - 324a_2) \\ 2052 & = 9a_1 + 405a_2 \\ 9a_1 & = 2052 - 405a_2 \\ a_1 & = \ frac {2052 - 405a_2} {9} \\ a_1 & = 228 - 45a_2 \ end {aligné}$$

Depuis que nous avons identifié $$$a_1, ..., a_ {k-1}$ comme des nombres entiers positifs choisis au hasard, il y a un nombre limité de $$$a_2$ . En utilisant ces informations, un attaquant peut inférer $$$a_2 \ in [1,2,3,4,5]$ , puisque tout ce qui est supérieur à 5 fera l'affaire $$$a_1$ négatif. Cela s'avère être vrai, comme nous l'avons déterminé $$$a_2 = 5$

Ensuite, l'attaquant peut calculer les valeurs possibles $$$S$ remplacer $$$a_1$ dans $$$f (18)$ :

$$

$$\ begin {aligné} 1716 & = S + a_118 + a_218 ^ 2 \\ 1716 & = S + 18 \ left (228 - 45a_2 \ right) + a_218 ^ 2 \\ 1716 - S & = 18 \ left (228 - 45a_2 \ droite) + a_218 ^ 2 \\ -S & = 18 \ gauche (228 - 45a_2 \ droite) + a_218 ^ 2 - 1716 \\ -S & = 4104 - 810a_2 + a_218 ^ 2 - 1716 \\ S & = -4104 + 810a_2 - a_218 ^ 2 + 1716 \\ S & = 810a_2 - 324a_2 -2388 \\ S & = 486a_2 - 2388 \ end {aligné}$$

Avec une sélection limitée d'options pour $$$a_2$ il devient clair à quel point il est facile de choisir et de vérifier les valeurs $$$S$ . Il n'y a que cinq options.

Résolution du problème avec une arithmétique d'entier non sûre

Pour éliminer cette vulnérabilité, Shamir suggère d'utiliser l'arithmétique modulaire, en remplaçant $$$f (x)$ sur $$$f (x) \ mod p$ où $$$p \ in \ mathbb {P}: p> S, p> n$ et $$$\ mathbb {P}$ - l'ensemble de tous les nombres premiers.

Rappelez rapidement le fonctionnement de l'arithmétique modulaire. Une horloge avec des flèches est déjà un concept familier. Elle utilise des montres qui sont $$$\ mod 12$ . Dès que l'aiguille des heures passe à douze, elle revient à une. Une propriété intéressante de ce système est que, simplement en regardant l'horloge, nous ne pouvons pas déduire le nombre de tours effectués par l'aiguille des heures. Cependant, si nous savons que l'aiguille des heures a passé 12 fois quatre fois, nous pouvons déterminer entièrement le nombre d'heures écoulées en utilisant une formule simple $$$a = mq + r$ où $$$m$ Est notre diviseur (ici $$$m = 12$ ), $$$q$ Est le coefficient (combien de fois le diviseur sans reste va au nombre d'origine, ici $$$q = 4$ ) et $$$r$ Est le reste, qui renvoie généralement le module d'appel de l'opérateur (ici $$$r = 1,5$ ) Connaître toutes ces valeurs nous permet de résoudre l'équation de $$$a = 49,5$ mais si nous sautons le coefficient, nous ne pourrons jamais restaurer la valeur d'origine.

Vous pouvez démontrer comment cela améliore la sécurité de notre circuit en appliquant le circuit à notre exemple précédent et en utilisant $$$p = 73$ . Notre nouvelle fonction polynomiale $$$f ’(x) = 42 + 3x + 5x ^ 2 \ mod 73$ et de nouveaux points $$$(18, 37), (27, 45), (31, 49), (35, 67)$ . Maintenant, les détenteurs de clés peuvent à nouveau utiliser l'interpolation polynomiale pour restaurer notre fonction, mais cette fois, les opérations d'addition et de multiplication doivent être accompagnées d'une réduction modulo $$$p$ (par exemple $$ )

En utilisant ce nouvel exemple, supposons que l'attaquant ait reconnu deux de ces nouveaux points, $$$(18, 37), (27, 45)$ et information du public $$$k = 3, p = 73$ . Cette fois, l'attaquant, sur la base de toutes les informations dont il dispose, affiche les fonctions suivantes, où $$$\ mathbb {N}$ Est l'ensemble de tous les entiers positifs, et $$$q_x$ représente le coefficient du module $$$f ’(x)$ .

$$

$$\ begin {aligné} f '(x) & = S + a_1x + a_2x ^ 2 \ mod 73 \\ f' (x) & = S + a_1x + a_2x ^ 2 - 73q_x: q_x \ in \ mathbb {N} \\ f '(18) \ equiv 37 & = S + a_118 + a_218 ^ 2 - 73q_ {18} \\ f' (27) \ equiv 45 & = S + a_127 + a_227 ^ 2 - 73q_ {27} \ end {aligné}$$

Maintenant, notre attaquant retrouve $$$a_1$ en calculant $$$f ’(27) - f’ (18)$ :

$$

$$\ begin {aligné} 45 - 37 & = (S - S) + (27a_1 - 18a_1) + (729a_2 - 324a_2) + (-73q_ {27} - (-73q_ {18})) \\ 8 & = 9a_1 + 405a_2 + 73 (q_ {18} - q_ {27}) \\ -9a_1 & = -8 + 405a_2 + 73 (q_ {18} - q_ {27}) \\ 9a_1 & = 8 - 405a_2 - 73 (q_ {18} - q_ {27}) \\ a_1 & = \ frac {8 - 405a_2 - 73 (q_ {18} - q_ {27})} {9} \\ a_1 & = \ frac {8} {9} - 45a_2 - \ frac {73} {9} (q_ {18} - q_ {27}) \ end {aligné}$$

Puis il essaie à nouveau de se retirer $$$S$ remplacer $$$a_1$ dans $$$f ’(18)$ :

$$

$$\ begin {aligné} 37 & = S + 18 \ gauche (\ frac {8} {9} - 45a_2 - \ frac {73} {9} (q_ {18} - q_ {27}) \ droite) + a_218 ^ 2 - 73q_ {18} \\ -S & = 18 \ left (\ frac {8} {9} - 45a_2 - \ frac {73} {9} (q_ {18} - q_ {27}) \ right) + a_218 ^ 2 - 73q_ {18} - 37 \\ S & = -18 \ left (\ frac {8} {9} - 45a_2 - \ frac {73} {9} (q_ {18} - q_ {27} ) \ droite) - 324a_2 + 73q_ {18} + 37 \\ S & = 486a_2 + 21 + 219q_ {18} - 146q_ {27} \ end {aligné}$$

Cette fois, il a un grave problème. Il n'y a aucune valeur dans la formule $$$a_2$ , $$$q_ {18}$ et $$$q_ {27}$ . Puisqu'il existe un nombre infini de combinaisons de ces variables, il ne peut recevoir aucune information supplémentaire.

Considérations de sécurité

Le système de partage secret de Shamir offre une sécurité en termes de théorie de l'information . Cela signifie que les mathématiques sont résistantes même contre un attaquant avec une puissance de calcul illimitée. Cependant, le circuit contient toujours plusieurs problèmes connus.

Par exemple, le schéma de Shamir ne crée pas de fragments de test , c'est-à-dire que les gens peuvent présenter librement de faux fragments et interférer avec la restauration du secret correct. Un détenteur de fragments hostile avec suffisamment d'informations peut même produire un autre fragment en changeant $$$S$ à sa discrétion. Ce problème est résolu en utilisant des schémas de partage de secret vérifiés , tels que le schéma Feldman.

Un autre problème est que la longueur de tout fragment est égale à la longueur du secret correspondant, de sorte que la longueur du secret est facile à déterminer. Ce problème est résolu en remplissant trivialement le secret de nombres arbitraires jusqu'à une longueur fixe.

Enfin, il est important de noter que nos préoccupations en matière de sécurité peuvent dépasser la portée du système lui-même. Pour les applications cryptographiques du monde réel, il existe souvent une menace d'attaques sur des canaux tiers, lorsqu'un attaquant tente d'extraire des informations utiles du runtime d'application, de la mise en cache, des plantages, etc. Si cela pose problème, vous devez soigneusement envisager l'utilisation de sauvegardes pendant le développement, telles que les fonctions et la recherche avec un temps d'exécution constant, empêcher la mémoire d'être enregistrée sur le disque et prendre en compte un certain nombre d'autres choses qui dépassent le cadre de cet article.

Démo

Cette page présente une démonstration interactive du système de partage secret de Shamir. La démonstration a été faite sur la base de la bibliothèque ssss-js , qui est en soi le port JavaScript du populaire programme ssss . Notez que le calcul de grandes valeurs $$$k$ , $$$n$ et $$$S$ peut prendre un certain temps.