Partage de clé secrète

Tout le monde se secoue ! 

J’ai commencé (il y a 19 heures) la rédaction d’un tutoriel au doux nom de « Partage de clé secrète » et j’ai pour objectif de proposer en validation un texte aux petits oignons. Je fais donc appel à votre bonté sans limites pour dénicher le moindre pépin, que ce soit à propos du fond ou de la forme. Vous pourrez consulter la bêta à votre guise à l’adresse suivante :

Merci !

Il s’agit d’un premier jet donc je dois encore repasser sur les tournures de phrases, l’orthographe, etc. Ce que je compte encore ajouter:

• Prouver que le polynome trouvé par la méthode de Lagrange est unique
• Des exemples de code qui programme tout ça
• Les calculs devraient être fait modulo p où p est un nombre premier > m. Je dois ajouter une section sur le pourquoi et ce que ça change
• Peut-être montrer qu’avec moins de k clés, aucune information ne fuit quant à la valeur du code secret

RAS du côté de la forme.

Salut,

Sur le fond :

Le contenu est clair. Plein de maths, mais en suivant le calcul au fur et à mesure, ça passe sans problème.

Outre la conclusion manquante, je pense que l’intro mériterait plus de détail. À quoi ça sert dans la vraie vie (car ça peut servir sans problème !), qui peut lire ce tuto… Mais ce sera à reprendre à la fin de l’écriture.

Il faudra veiller à rester cohérent lors des ajouts futurs.

En outre, je pense que le titre pourrait être plus claire.

En tout cas, début très prometteur.

Sur la forme :

Intro

récupér le message m.

récupérer

Interpolation de Lagrange

En utilisant les propriétés des polynômes lagrangien présentées ci-dessus, nous pouvons aisément conlure que L(xi​)=yi​,i∈0,…,n.

lagrangiens, conclure

Nous pouvons nous convaincre que ce résultat est correcte

correct

Génération des clés secrètes

Pour rappler, k est le nombre de clés suffisant à fournir lors de l’étape de reconstruction du code.

rappeler

Ces clés peuvent maintenant être distribuées au 5 personnes de confiance sans qu’aucune de ces clés individuellemnt ne dévoile quoi que ce soit quant à la valeur du code secret.

individuellement

Récupération du code à partir des clés secrètes

Manque une parenthèse dans « (x1,y1),(x2,y2),…,xk,yk)(x_1, y_1), (x_2, y_2), …, x_k, y_k)(x1​,y1​),(x2​,y2​),…,xk​,yk​) ».

Hello,

De mon côté je trouve le sujet intéressant mais comme j’ai arrêté les maths dans les premières années de sup, je suis dans l’incapacité de pouvoir suivre cela (sans faire des recherches annexes).

Je sais que le site ne s’appelle pas "Site du Zéro". Mais je trouve ça dommage alors je voulais le dire .

Tu pourrais expliquer ce que tu n’arrives pas à suivre en particulier ? J’imagine que c’est la partie sur l’interpolation de Lagrange mais tu ne suis pas ce que l’on essaie de faire ou plutôt comment on arrive à le faire ? Ou c’est autre chose qui bloque ?

Je pense ajouter des graphes dans la partie Interpolation de Lagrange, qui pourraient aider à mieux visualiser ce qu’il se passe. Tu penses que ça t’aiderait ?

Je t’avoue que j’ai dû regarder un peu à côté, notamment le paragraphe introductif et le graphe d’exemple sur Wikipédia pour avoir le contexte de l’interpolation lagrangienne et de ce que c’est censé faire. Mais après ça, je n’ai pas eu trop de mal à suivre le reste¹ qui nécessite surtout de savoir ce que sont les polynômes en général, j’ai l’impression.

Je suspecte que la mention aussi brusque de l’interpolation lagrangienne risque de faire butter pas mal de gens qui, pourtant, auraient le niveau de suivre le contenu. Il serait dommage de les perdre ainsi

Bonjour les agrumes !

La bêta a été mise à jour et décante sa pulpe à l’adresse suivante :

Merci d’avance pour vos commentaires.

Modifications:

• Correction des typos reportées par Gabbro (merci)
• Ajout des sections d’introduction sur les fonctions et les fonctions polynomiales
• Ajout d’un exemple rapide au début de la section sur l’interpolation de Lagrange
• Changement du titre

@sgble, @Nek: Pourriez-vous jeter un oeil au nouveau contenu et me dire si vous trouvez que c’est plus facile à suivre grâce aux deux nouvelles sections ? Ou si des clarifications supplémentaires vous semblent nécessaire ?

Ça n’a rien à voir c’est beaucoup mieux ! (encore un peu complexe à lire pour mon cerveau étriqué, mais bon, ça devient possible)

Hello, oui, je te confirme que c’est bien plus facile à lire pour un esprit non entraîné

Bonjour les agrumes !

La bêta a été mise à jour et décante sa pulpe à l’adresse suivante :

Merci d’avance pour vos commentaires.

Modifications:

• Ajout d’un logo
• Ajout d’une section sur l’aritméthique modulaire
• Suppression du TODO ajouter code, finalement je crois que je ne vais pas fournir d’implémentation
• Ajout d’une conclusion

Je pense que je m’approche petit à petit d’une version finale. Je vais peaufiner des passages par-ci, par-là mais je ne pense a priori plus ajouter / supprimer de sections ou apporter de grandes modifications.

Bonjour les agrumes !

La bêta a été mise à jour et décante sa pulpe à l’adresse suivante :

Merci d’avance pour vos commentaires.

Crypto

Petite remarque, je pense que c’est intéressant de dire pourquoi séparer la clef en k parties n’est pas suffisant. Si tu veux aller dans les détails, aussi expliquer pourquoi, même avec k-1 clefs, il est impossible de retrouver quoi que ce soit du secret.

Pour ce qui concerne le contenu scientifique, je ne sais pas si une personne qui ne sait pas ce qu’est une fonction pourra suivre jusqu’au bout. Par exemple, on voit les fonctions bien avant les symboles $\prod$ et $\sum$ qui ne sont pas tout à fait introduits.

Tu ne prouves pas non plus que le polynome d’interpolation est unique, je ne sais pas si c’est voulu ?

Bonjour les agrumes !

La bêta a été mise à jour et décante sa pulpe à l’adresse suivante :

Merci d’avance pour vos commentaires.

Crypto

Petite remarque, je pense que c’est intéressant de dire pourquoi séparer la clef en k parties n’est pas suffisant. Si tu veux aller dans les détails, aussi expliquer pourquoi, même avec k-1 clefs, il est impossible de retrouver quoi que ce soit du secret.

Je vois ce que tu veux dire. Je vais réfléchir à si et comment j’introduirais ceci.

Pour ce qui concerne le contenu scientifique, je ne sais pas si une personne qui ne sait pas ce qu’est une fonction pourra suivre jusqu’au bout. Par exemple, on voit les fonctions bien avant les symboles $\prod$ et $\sum$ qui ne sont pas tout à fait introduits.

J’ai essayé la plupart du temps de d’abord écrire la formule complète avant de passer à l’écriture avec $\sum$ et $\prod$ mais il y a des endroits où ce n’est pas le cas, je rectifierai ça. Je pense qu’expliquer ce que c’est deviendrait assez lourd mais je vais voir si c’est possible.

Euh… Pour une raison qui m’échappe, c’était bien présent dans une version précédente mais il semblerait que durant une des mes modifications, je l’ai supprimé… Bien vu de ta part, je l’ai rajouté (heureusement, on a un historique !)

Merci pour tes remarques !

Ça me paraît bien tout ça, continue sur cette lancée !

Bonjour les agrumes !

La bêta a été mise à jour et décante sa pulpe à l’adresse suivante :

Merci d’avance pour vos commentaires.

Modifications:

• Ajout d’une rapide explication sur les notations $\sum$ et $\prod$
• Explication des défauts de l’approche naïve et pourquoi nous avons besoin d’une méthode plus avancée
• Preuve que sans $k$ parties, nous n’obtenons aucune information sur $m4

Je pense que certaines parties sont peut-être un peu lourde à lire, je vais voir si je peux améliorer certaines explications par-ci par-là ou si je peux mieux formatter ça. Mais je pense que la structure est finalisée (dernière fois que j’ai dit ça, j’ai quand même ajouté 2 sections par la suite )

Je pense que certaines parties sont peut-être un peu lourde à lire, je vais voir si je peux améliorer certaines explications par-ci par-là ou si je peux mieux formatter ça.

Pro-tip : écris sans fioriture. Keep it simple, comme on dit. Une fois que le contenu est finalisé sur le fond, laisse décanter le contenu pendant quelques jours (il faut même "oublier" le contenu). Ensuite, à la relecture, les passages éventuellement à réécrire seront plus visibles.

Cela étant, d’ici là, fort probable que tu aies des retours. Je n’ai malheureusement pas le temps de faire une relecture d’ici à ce weekend, mais cette méthode marche généralement bien.

Une passe sur la forme

il esttoujours possible

espace manquant

$l_i(X) = \frac{X - x_0}{x_i - x_0} ... \frac{X - x_{i-1}}{x_i - x_{i+1}} \frac{X - x_{i+1}}{x_i - x_{i+1}} ... \frac{X - x_n}{x_i - x_n} = \prod^{n}_{j=0, j\neq i} \frac{X - x_j}{x_i - x_j}$

J’aurais mis des signes $\times$ avant les points de suspension, personnellement : $\displaystyle l_i(X) = \frac{X - x_0}{x_i - x_0} \times \cdots \times \frac{X - x_{i-1}}{x_i - x_{i+1}} \times \frac{X - x_{i+1}}{x_i - x_{i+1}} \times \cdots \times \frac{X - x_n}{x_i - x_n} =$

nous allons nous attarder à la génération des clés secrètes avant de s’intéresser

pas très heureux d’utiliser à la fois

. Pour rappeler,

pour rappel

$(x_i,y_j)=(x_i,P(x_i)$

manque une parenthèse

distribuées au 5 personnes

aux

$\frac{1525}{3}$

En arithmétique modulaire, on n’utilise jamais de fractions, parce que ça porte beaucoup à confusion. Les gens qui ne s’y connaissent pas ont tendance à croire que $\frac 13 \mod 4 = 0.333333 \mod 4$. À la place, on écrit $1525 \cdot 3^{-1}$.

sans qu’aucune de ces clés individuellement ne dévoile quoi que ce soit quant à la valeur du code secret.

Peut-être rajouter "comme nous allons le voir par la suite" ?

En ce qui concerne la preuve de l’absence d’information avec moins de $k$ parties, je trouve la démonstration un peu légère : c’est une explication ad hoc sur un exemple, et le fait que 6301 n’est pas divisible par $3$ ne permet pas de conclure immédiatement (ceci dit, on n’a pas de garantie que $m_2 - m_1$ ne soit pas divisible par 3 non plus, et plus important la valeur des $m_i$ dépend de la valeur des $a_i$, donc change à chaque fois).

J’aurais plutôt utilisé l’approche de Shamir : pour chaque valeur possible du secret $m$, il existe un et un unique polynôme passant par ce point et les $k-1$ autres valeurs. Ainsi, par construction, en inversant le raisonnement, pour les parts que l’on connaît, il y a tout autant de probabilité que le secret soit égal à $m$ ou $m'$ ou n’importe quel autre élément i.e. le schéma dispose d’une sécurité parfaite dont il a déjà été fait mention ailleurs sur ce site, BAM la SEO en folie. La même preuve est expliquée plus en longueur ici : https://crypto.stackexchange.com/questions/64082/formal-proof-of-shamirs-secret-sharing-scheme-security/64095#64095

Ah et dernier point, refaire un tour orthographique sur polynôme/polynome.

Pour le fond, j’ai quand même une remarque que j’avais oublié de mettre dans le précédent message : à quel public t’adresses-tu ? D’un côté tu donnes une introduction aux fonctions, de l’autre on parle d’arithmétique modulaire. Je doute qu’une personne qui ne se souvienne pas de ce qu’est une fonction puisse aller aussi loin dans le tuto. Après je peux me tromper.

Je dirais que tu peux viser un public de niveau bac S, qui a potentiellement oublié à quoi ressemblait un polynôme donc tu peux tout à fait garder l’intro dessus. Pour ce qui est des fonctions, j’ai quand même un doute qu’on l’oublie autant, et qu’on lise des tutos de maths. Dans cette optique, la partie sur les fonctions me semble superflue, mais encore une fois, ce n’est que mon avis, je ne sais pas ce qu’en pensent les autres.

Merci beaucoup pour le retour. Je corrigerai les fautes d’orthographe et les phrases mal construites dans les jours qui viennent.

$\frac{1525}{3}$

En arithmétique modulaire, on n’utilise jamais de fractions, parce que ça porte beaucoup à confusion. Les gens qui ne s’y connaissent pas ont tendance à croire que $\frac 13 \mod 4 = 0.333333 \mod 4$. À la place, on écrit $1525 \cdot 3^{-1}$.

En effet. J’ai fait ça pour garder les mêmes calculs que plus haut mais tu as raison que ce n’est pas correct, je vais changer ça.

sans qu’aucune de ces clés individuellement ne dévoile quoi que ce soit quant à la valeur du code secret. En ce qui concerne la preuve de l’absence d’information avec moins de $k$ parties, je trouve la démonstration un peu légère : c’est une explication ad hoc sur un exemple, et le fait que 6301 n’est pas divisible par $3$ ne permet pas de conclure immédiatement (ceci dit, on n’a pas de garantie que $m_2 - m_1$ ne soit pas divisible par 3 non plus, et plus important la valeur des $m_i$ dépend de la valeur des $a_i$, donc change à chaque fois).

J’aurais plutôt utilisé l’approche de Shamir : pour chaque valeur possible du secret $m$, il existe un et un unique polynôme passant par ce point et les $k-1$ autres valeurs. Ainsi, par construction, en inversant le raisonnement, pour les parts que l’on connaît, il y a tout autant de probabilité que le secret soit égal à $m$ ou $m'$ ou n’importe quel autre élément i.e. le schéma dispose d’une sécurité parfaite dont il a déjà été fait mention ailleurs sur ce site, BAM la SEO en folie. La même preuve est expliquée plus en longueur ici : https://crypto.stackexchange.com/questions/64082/formal-proof-of-shamirs-secret-sharing-scheme-security/64095#64095

En fait j’ai utilisé l’approche donnée sur Wikipedia anglophone. Mais ce qu’ils font, c’est montrer que sans l’arithmétique modulaire, on arrive à gagner de l’information alors qu’une fois qu’on utilise mod, c’est réglé. Je vais jeter un oeil à ton lien, je dois avouer que je n’étais pas 100% convaincu par cette section donc je serais content de pouvoir l’améliorer.

J’ai appris l’existence de cette méthode en lisant le livre "Joy of Cryptography" (enfin, j’en avais déjà entendu parler avant) et je me suis dit que ça pouvait en faire un chouette tutoriel. Mon approche à la base est plutôt de présenter ça à des développeurs car au final, il s’agit d’un algorithme qui peut être implémenté pour faire de la cryptographie. C’est d’ailleurs pour ça qu’à la base, je voulais aussi ajouter des exemples d’implémentation. Finalement, je pense que ça ne rajouterait pas grand chose au tutoriel pour le moment.

Tout ça pour dire que j’aimerais que ça puisse servir au plus grand public possible. Je pense que l’interpolation de Lagrange peut être relativement simple à comprendre sans avoir un fort bagage mathématique. Par contre, l’arithmétique modulaire, je suis tout à fait d’accord que ça ne sera pas vraiment compris par des gens n’ayant pas des bases plus ou moins solides en maths. Mais c’est aussi pour ça que j’ai mis un encart précisant que l’arithmétique modulaire est importante pour que l’algorithme soit réellement correct mais ne change pas grand chose à l’idée de base et peut donc être ignoré par les gens moins férus de maths.

Bonjour les agrumes !

La bêta a été mise à jour et décante sa pulpe à l’adresse suivante :

Merci d’avance pour vos commentaires.

Modifications:

• Correction de tournures de phrases et fautes d’orthographe
• Remplacement des fractions pour $X^{-1}$ dans les calculs avec modulo
• Réécriture de la preuve de la sûreté de l’algorithme.

Bonjour les agrumes !

La bêta a été mise à jour et décante sa pulpe à l’adresse suivante :

Merci d’avance pour vos commentaires.

Modifications:

• Correction de fautes d’orthographe par-ci par-là (polynome )
• Utilisation cohérente de code et partie partout dans le tutoriel