Considérons un scénario où il est nécessaire d'assurer la sécurité d'un coffre-fort bancaire. Il est considéré comme absolument impénétrable sans la clé, qui vous est remise dès le premier jour de travail. Votre objectif est de conserver la clé de manière fiable.

Supposons que vous ayez décidé de garder la clé sur vous en permanence, en donnant accès au coffre-fort selon les besoins. Mais vous réaliserez rapidement que cette solution ne se déploie pas efficacement en pratique, car chaque fois que l'on doit ouvrir le coffre, votre présence physique est nécessaire. Et qu'en est-il des congés qui vous ont été promis ? De plus, la question qui fait encore plus peur est : et si vous perdez la seule clé ?

En pensant à vos congés, vous décidez de faire une copie de la clé et de la confier à un collègue. Cependant, vous comprenez que cela n'est pas non plus idéal. En doublant le nombre de clés, vous avez également doublé les risques de vol de la clé.

Désespéré, vous détruisez le duplicata 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 présentes physiquement pour assembler la clé et ouvrir le coffre-fort. Cela signifie qu'un voleur doit voler deux fragments, ce qui est deux fois plus difficile que de voler une clé unique. Cependant, vous réalisez rapidement que ce schéma n'est guère meilleur qu'une simple clé, car si quelqu'un perd la moitié de la clé, la clé complète ne pourra pas être rétablie.

Le problème peut être résolu par une série de clés et de serrures supplémentaires, mais avec cette approche, il sera rapidement nécessaire beaucoup de clés et de serrures. Vous décidez que dans un schéma idéal, la clé doit être divisée afin que la sécurité ne repose pas entièrement sur une seule personne. Vous concluez également qu'il doit exister un certain seuil de nombre de fragments, afin que, même en cas de perte d'un fragment (ou si la personne est en congé), la clé reste fonctionnelle.

Comment diviser un secret

Un tel type de schéma de gestion des clés a été pensé par Adi Shamir en 1979, lorsqu'il a publié son travail « Comment diviser un secret ». Dans l'article, il explique brièvement ce qu'on appelle le schéma de seuil pour une séparation efficace d'une valeur secrète (par exemple, une clé cryptographique) en parties. Ensuite, lorsque et seulement lorsque au moins de parties sont réunies, il est possible de restaurer facilement le secret. .

D'un point de vue de la sécurité, une propriété importante de ce schéma est que l'attaquant ne doit rien connaître du tout s'il n'a pas au moins des fragments. Même la possession de fragments ne devrait donner aucune information. Nous appelons cela la sécurité sémantique.

L'interpolation polynomiale

Le schéma de Shamir est construit autour du concept de l'interpolation polynomiale. Si vous n'êtes pas familier avec ce concept, il est en réalité assez simple. En fait, si vous avez déjà dessiné des points sur un graphique et les avez ensuite reliés par des lignes ou des courbes, vous l'avez déjà utilisé !À travers deux points, on peut tracer un nombre illimité de polynômes de degré 2. Pour choisir l'unique parmi eux, il nous faut un troisième point. Illustration :

Considérons un polynôme de degré un, Wikipedia

. Si vous souhaitez tracer cette fonction sur un graphique, combien de points vous faut-il ? Eh bien, nous savons que c'est une fonction linéaire qui forme une ligne, donc il faut au moins deux points. Ensuite, prenons une fonction polynomiale de degré deux, . C'est une fonction quadratique, donc il faut au moins trois points pour tracer le graphique. Qu'en est-il d'un polynôme de degré trois ? Au moins quatre points. Et ainsi de suite. La véritable beauté de cette propriété réside dans le fait que, connaissant le degré de la fonction polynomiale et au moins

points, nous pouvons déduire des points supplémentaires pour cette fonction polynomiale. L'extrapolation de ces points supplémentaires est ce que nous appelons l'interpolation polynomiale Construction du secret.

Vous avez peut-être déjà compris que le schéma intelligent de Shamir entre en jeu ici. Supposons que notre secret

. Nous pouvons transformer — ce sont des en un point sur le graphique et inventer une fonction polynomiale de degré , qui satisfait à ce point. Rappelons que sera notre seuil de fragments requis, donc si nous fixons le seuil à trois fragments, nous devrions sélectionner une fonction polynomiale de degré deux. Notre polynôme sera de la forme

— des entiers positifs choisis au hasard. Nous ne faisons que construire un polynôme de degré , où et , où le coefficient libre est notre secret  , et chacun des suivants . Un membre a un coefficient positif choisi au hasard. Si nous revenons à l'exemple initial et supposons que , alors nous obtiendrons une fonction .

À ce stade, nous pouvons générer des fragments en connectant des entiers uniques dans , où (car 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 et envoyons un point à chacune des quatre personnes de confiance, les gardiens de la clé. Nous informons également les gens que , car c'est considéré comme une information publique et nécessaire pour la reconstruction .

Reconstruction du secret

Nous avons déjà discuté du concept d'interpolation polynomiale et de ce qu'il implique dans le schéma de partage de secret de Shamir . Lorsque trois des quatre personnes de confiance souhaitent récupérer , elles n'ont qu'à interpoler avec leurs points uniques. Pour cela, elles peuvent définir leurs points et calculer le polynôme d'interpolation de Lagrange en utilisant la formule suivante. Si la programmation vous est plus familière que les mathématiques, alors pi est essentiellement un opérateur for, qui multiplie tous les résultats, et sigma est for, qui additionne tout.

En cas Nous pouvons le résoudre de la manière suivante et retrouver notre fonction polynomiale d'origine :

Puisque nous savons que , la reconstruction se fait simplement :

Utilisation de l'arithmétique entière non sécurisée

Bien que nous ayons appliqué avec succès l'idée principale de Shamir , il nous reste un problème que nous avons ignoré jusqu'à présent. Notre fonction polynomiale utilise de l'arithmétique entière non sécurisée. Gardez à l'esprit que pour chaque point supplémentaire qu'un attaquant obtient sur le graphique de notre fonction, il reste moins de possibilités pour d'autres points. Vous pouvez le voir par vous-même lorsque vous tracez un graphique en augmentant le nombre de points pour une fonction polynomiale utilisant de l'arithmétique entière. C'est contre-productif pour notre objectif de sécurité déclaré, car un malfaiteur ne doit absolument rien savoir tant qu'il n'a pas au moins des fragments.

Pour démontrer à quel point le schéma utilisant l'arithmétique entière est faible, considérons un scénario où un attaquant a obtenu deux points et sait que l'information publique est que . De ces informations, il peut déduire , égal à deux, et intégrer les valeurs connues dans la formule et .

Ensuite, l'attaquant peut trouver , en calculant :

Puisque nous avons défini comme des entiers positifs choisis au hasard, il y a un nombre limité de possibles . Avec ces informations, l'attaquant peut déduire , car tout ce qui est supérieur à 5 rendra négatif. Cela s'avère vrai, car nous avons défini

Ensuite, l'attaquant peut calculer les valeurs possibles , en remplaçant dans :

Avec un ensemble limité d'options pour il devient clair à quel point il est facile de deviner et de vérifier les valeurs . Il y a ici seulement cinq options.

Résolution du problème de l'arithmétique entière non sécurisée

Pour éliminer cette vulnérabilité, Shamir propose d'utiliser l'arithmétique modulaire, en remplaçant sur , où et — l'ensemble de tous les nombres premiers.

Rappelons rapidement comment fonctionne l'arithmétique modulaire. Les horloges à aiguilles sont une notion déjà familière. Elles utilisent des heures qui sont . Dès que l'aiguille des heures passe le douze, elle revient à une. Une caractéristique intéressante de ce système est que simplement en regardant l'horloge, nous ne pouvons pas déduire combien de tours l'aiguille des heures a effectués. 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 écoulées avec une simple formule , où  — c'est notre diviseur (ici ),  — c'est le coefficient (combien de fois le diviseur rentre sans reste dans le nombre initial, ici ), tandis que  — c'est le reste, que renvoie généralement l'opérateur modulo (ici ). Connaître toutes ces valeurs nous permet de résoudre l'équation pour , mais si nous omettons le coefficient, nous ne pourrons jamais reconstruire la valeur initiale.

On peut 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 . Maintenant, les gardiens de clé 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 (p. ex. ).

En utilisant ce nouvel exemple, supposons que l'attaquant a découvert deux de ces nouveaux points, , et les informations publiques . Cette fois, l'attaquant utilise toutes les informations disponibles pour déduire les fonctions suivantes, où  — est l'ensemble de tous les entiers positifs, et représente le coefficient du module .

Maintenant, notre agresseur retrouve à nouveau , en calculant :

Ensuite, il essaie à nouveau de déduire , en remplaçant dans :

Cette fois, il a un problème sérieux. Les valeurs manquent dans la formule , et . Étant donné qu'il existe une infinité de combinaisons de ces variables, il ne peut obtenir aucune information supplémentaire.

Considérations de sécurité

Le schéma de partage de secrets de Shamir propose une sécurité du point de vue de la théorie de l'information. Cela signifie que la mathématique est robuste même contre un attaquant ayant une puissance de calcul illimitée. Cependant, le schéma présente encore plusieurs problèmes connus.

Par exemple, le schéma de Shamir ne crée pas des fragments vérifiables, c'est-à-dire que les gens peuvent facilement présenter de faux fragments et entraver la récupération du bon secret. Un gardien hostile de fragments ayant suffisamment d'informations peut même produire un autre fragment, modifiant à sa guise. Ce problème est résolu par des schémas de partage de secrets vérifiables, tels que le schéma de Feldman.

Un autre problème est que la longueur de tout fragment est égale à celle du secret correspondant, rendant la longueur du secret facile à déterminer. Ce problème est résolu par un remplissage du secret avec des nombres arbitraires jusqu'à une longueur fixe.

Enfin, il est important de noter que nos inquiétudes concernant la sécurité peuvent aller au-delà du schéma lui-même. Pour les applications cryptographiques réelles, il existe souvent la menace d'attaques par des canaux auxiliaires, où un attaquant essaie d'extraire des informations utiles à partir des temps d'exécution de l'application, de la mise en cache, des plantages, etc. Si cela constitue une préoccupation, il convient d'examiner minutieusement, lors du développement, l'utilisation de mesures de protection, telles que des fonctions et des recherches avec un temps d'exécution constant, d'éviter d'écrire en mémoire sur disque, et de réfléchir à plusieurs autres éléments qui dépassent le cadre de cet article.

Démo

Sur cette page il y a une démonstration interactive du schéma de partage de secrets de Shamir. La démonstration est basée sur la bibliothèque ssss-js, qui est elle-même un port JavaScript d'un programme populaire ssssVeuillez noter que le calcul de grandes valeurs , et peut prendre un certain temps.

Source : habr.com