Considérez un scénario dans lequel vous devez sécuriser un coffre-fort bancaire. Il est considéré comme absolument imprenable sans clé, qui vous est remise dès le premier jour de travail. Votre objectif est de stocker la clé en toute sécurité.
Disons que vous décidez de garder la clé avec vous à tout moment, donnant accès au stockage selon vos besoins. Mais vous vous rendrez vite compte qu’une telle solution n’est pas très évolutive en pratique, car votre présence physique est requise à chaque ouverture du stockage. Et les vacances qu'on vous avait promises ? De plus, la question est encore plus effrayante : et si vous perdiez votre seule clé ?
En pensant à vos vacances, vous décidez de faire une copie de la clé et de la confier à un autre employé. Cependant, vous comprenez que ce n’est pas non plus l’idéal. En doublant le nombre de clés, vous doublez également les risques de vol de clés.
En désespoir de cause, vous détruisez le double et décidez de diviser la clé originale en deux. Maintenant, on pourrait penser que deux personnes de confiance possédant des fragments de clé devraient être physiquement présentes pour récupérer la clé et ouvrir le coffre-fort. Cela signifie qu'un voleur doit voler deux pièces, ce qui est deux fois plus difficile que de voler une clé. Cependant, vous vous rendrez vite compte que ce système n'est pas bien meilleur qu'une seule clé, car si quelqu'un perd la moitié d'une clé, la clé complète ne peut pas être récupérée.
Le problème peut être résolu avec une série de clés et de serrures supplémentaires, mais cette approche nécessitera rapidement много clés et serrures. Vous décidez que la conception idéale serait de partager 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 afin 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é envisagé par Adi Shamir en 1979 lors de la publication de son ouvrage . L'article explique brièvement ce qu'on appelle 
schéma de seuil pour diviser efficacement une valeur secrète (telle qu'une clé cryptographique) en les pièces. Alors, quand et seulement quand au moins de les pièces sont assemblées, vous pouvez facilement restaurer le secret .
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 à moins d'avoir au moins les pièces. Même la présence les pièces ne doivent fournir aucune information. Nous appelons cette propriété sécurité sémantique.
Interpolation polynomiale
Schéma de seuil Shamir construit autour du concept interpolation polynomiale. Si vous n’êtes pas familier avec ce concept, c’est en fait assez simple. En fait, 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é !
A travers deux points, vous pouvez tracer un nombre illimité de polynômes de degré 2. Pour choisir le seul parmi eux, vous avez besoin d'un troisième point. Illustration:
Considérons un polynôme de degré un, . Si vous souhaitez tracer cette fonction sur un graphique, de combien de points avez-vous besoin ? Eh bien, nous savons qu’il s’agit d’une fonction linéaire qui forme une ligne et qui nécessite donc au moins deux points. Considérons ensuite une fonction polynomiale de degré deux, . Il s’agit d’une fonction quadratique, donc au moins trois points sont nécessaires pour tracer le graphique. Que diriez-vous d’un polynôme de degré trois ? Au moins quatre points. Et ainsi de suite.
Ce qui est vraiment intéressant à propos de cette propriété, c'est que, étant donné le degré de la fonction polynomiale et au moins points, nous pouvons dériver des points supplémentaires pour cette fonction polynomiale. Nous appelons l'extrapolation de ces points supplémentaires interpolation polynomiale.
Inventer un secret
Vous avez peut-être déjà réalisé que c'est là que le plan astucieux de Shamir entre en jeu. Disons notre secret - Est . Nous pouvons tourner à un point du graphique et proposer une fonction polynomiale avec degré , ce qui satisfait ce point. Rappelons que sera notre seuil de fragments requis, donc si nous fixons le seuil à trois fragments, nous devons choisir une fonction polynomiale de degré deux.
Notre polynôme aura la forme Où и — des entiers positifs sélectionnés au hasard. Nous construisons simplement un polynôme de degré , où le coefficient libre - C'est notre secret , et pour chacun des suivants termes, il existe un coefficient positif sélectionné au hasard. Si nous revenons à l'exemple original et supposons que , alors on obtient la fonction .
À ce stade, nous pouvons générer des fragments en connectant entiers uniques dans Où (parce que c'est notre secret). Dans cet exemple, nous souhaitons distribuer quatre fragments avec un seuil de trois, nous générons donc des points de manière aléatoire et envoyez un point à chacune des quatre personnes de confiance, dépositaires de la clé. Nous faisons également savoir aux gens que , car cela est considéré comme une information publique et est nécessaire à la récupération .
Récupérer le secret
Nous avons déjà discuté du concept d'interpolation polynomiale et de la façon dont il sous-tend le schéma de seuil de Shamir. . Quand trois des quatre administrateurs veulent restaurer , il leur suffit d'interpoler avec ses propres points uniques. Pour ce faire, ils peuvent déterminer leurs points et calculez le polynôme d'interpolation de Lagrange en utilisant la formule suivante. Si la programmation est plus claire pour vous que les mathématiques, alors pi est essentiellement un opérateur for, qui multiplie tous les résultats, et sigma est for, ce qui additionne tout.
à nous pouvons le résoudre comme ceci et renvoyer notre fonction polynomiale d'origine :
Puisque nous savons que , récupération fait simplement :
Utilisation d'une arithmétique entière non sécurisée
Bien que nous ayons appliqué avec succès l'idée de base de Shamir , nous nous retrouvons face à un problème que nous avons ignoré jusqu’à présent. Notre fonction polynomiale utilise une arithmétique entière non sécurisée. Notez que pour chaque point supplémentaire qu'un attaquant obtient sur le graphique de notre fonction, il y a moins de possibilités pour d'autres points. Vous pouvez le constater de vos propres yeux lorsque vous tracez un nombre croissant de points pour une fonction polynomiale en utilisant l'arithmétique entière. Cela va à l’encontre de notre objectif de sécurité déclaré, car l’attaquant ne devrait absolument rien savoir tant qu’il n’a pas au moins fragments.
Pour démontrer la faiblesse du circuit arithmétique des nombres entiers, considérons un scénario dans lequel un attaquant a obtenu deux points. et connaît les informations publiques qui . De ces informations, il peut déduire , égal à deux, et insérez les valeurs connues dans la formule и .
L'attaquant peut alors trouver , en comptant :
Puisque nous avons défini en tant qu'entiers positifs sélectionnés au hasard, il existe un nombre limité de possibles . Grâce à ces informations, un attaquant peut déduire , puisque tout ce qui est supérieur à 5 fera l'affaire négatif. Cela s'avère vrai puisque nous avons déterminé
L'attaquant peut alors calculer les valeurs possibles remplacer в :
Avec des options limitées pour il devient clair à quel point il est facile de sélectionner et de vérifier les valeurs . Il n'y a que cinq options ici.
Résoudre le problème de l'arithmétique entière dangereuse
Pour éliminer cette vulnérabilité, Shamir suggère d'utiliser l'arithmétique modulaire, en remplaçant sur Où и — l'ensemble de tous les nombres premiers.
Rappelons rapidement comment fonctionne l'arithmétique modulaire. Une horloge à aiguilles est un concept familier. Elle utilise une montre qui est . Dès que l’aiguille des heures dépasse midi, elle revient à une. Une propriété intéressante de ce système est qu’en regardant simplement l’horloge, on ne peut pas déduire combien de tours l’aiguille des heures a fait. Cependant, si nous savons que l'aiguille des heures a dépassé 12 quatre fois, nous pouvons déterminer complètement le nombre d'heures qui se sont écoulées à l'aide d'une formule simple. Où est notre diviseur (ici ), est le coefficient (combien de fois le diviseur entre dans le nombre d'origine sans reste, ici ), et est le reste, qui renvoie généralement un appel d'opérateur modulo (ici ). Connaître toutes ces valeurs nous permet de résoudre l'équation de , mais si nous manquons le coefficient, nous ne pourrons jamais restaurer la valeur d'origine.
Nous pouvons démontrer comment cela améliore la sécurité de notre schéma en appliquant le schéma à notre exemple précédent et en utilisant . Notre nouvelle fonction polynomiale , et les nouveaux points . Désormais, les détenteurs de clés peuvent à nouveau utiliser l'interpolation polynomiale pour reconstruire notre fonction, mais cette fois les opérations d'addition et de multiplication doivent être accompagnées d'une réduction modulo. (par exemple ).
En utilisant ce nouvel exemple, supposons que l'attaquant ait appris deux de ces nouveaux points, , et l'information du public . Cette fois, l'attaquant, sur la base de toutes les informations dont il dispose, génère les fonctions suivantes, où est l'ensemble de tous les entiers positifs, et représente le coefficient de module .
Maintenant, notre attaquant retrouve , calculant :
Puis il réessaye remplacer в :
Cette fois, il a un sérieux problème. Valeurs manquantes de la formule , и . Puisqu’il existe un nombre infini de combinaisons de ces variables, il ne peut obtenir aucune information supplémentaire.
Considérations de sécurité
Le plan de partage secret de Shamir suggère la sécurité du point de vue de la théorie de l'information. Cela signifie que les mathématiques résistent même à un attaquant disposant d’une puissance de calcul illimitée. Cependant, le circuit contient encore plusieurs problèmes connus.
Par exemple, le schéma de Shamir ne crée pas fragments à vérifier, c'est-à-dire que les gens peuvent librement présenter de faux fragments et interférer avec la récupération du bon secret. Un gardien de fragment hostile disposant de suffisamment d'informations pourrait même produire un autre fragment en changeant à votre propre discrétion. Ce problème est résolu en utilisant schémas de partage de secrets vérifiables, comme le schéma de 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 peut être résolu de manière triviale rembourrage secret avec des nombres arbitraires jusqu'à une longueur fixe.
Enfin, il est important de noter que nos préoccupations en matière de sécurité peuvent s'étendre au-delà de la conception elle-même. Pour les applications cryptographiques réelles, il existe souvent une menace d'attaques par canal secondaire dans lesquelles un attaquant tente d'extraire des informations utiles sur le temps d'exécution de l'application, la mise en cache, les plantages, etc. Si cela constitue un problème, il convient d'accorder une attention particulière lors du développement à l'utilisation de mesures de protection telles que des fonctions et des recherches en temps constant, empêchant l'enregistrement de la mémoire sur le disque, ainsi qu'un certain nombre d'autres considérations qui dépassent le cadre de cet article.
Démo
Sur Il y a une démonstration interactive du système de partage de secrets de Shamir. Démonstration basée sur la bibliothèque , qui est lui-même un portage JavaScript du programme populaire . Notez que le calcul de grandes valeurs , и peut prendre un certain temps.
Source: habr.com