La vidéo du jour traite d’un algorithme de cryptographie qui m’a semblé au premier abord invraisemblable…Cela fait plusieurs fois que je traite de cryptographie, et je n’ai pas encore épuisé le sujet, loin de là !
Quelques précisions d’usage sur des points que je traite dans la vidéo.
J’ai parlé du chiffre de Vigenere (sans le nommer d’ailleurs, pour pas complexifier) sans forcément élaborer sur le fait que ça n’est pas la seule méthode de chiffrement qui nécessite une clé. D’ailleurs si la clé est trop courte, il est lui aussi peu robuste aux attaques statistiques. En effet des méthodes de répétition de motifs permettent assez facilement de deviner la longueur de la clé, et à partir de là de faire des statistiques sur chaque lettre indépendamment pour essayer de percer la clé.
Sur les racines primitives (de l’unité) modulo p, je n’ai pas voulu trop assommer l’auditoire, mais il y aurait plein de choses à dire ! Par exemple, pour qu’un nombre soit une racine primitive modulo p, il n’est pas obligé que p soit premier. De façon général, il faut prendre un nombre de la forme \(p^k\) ou \(2p^k\) pour qu’une racine primitive existe.
Un point que j’ai aussi à peine évoqué, c’est le fait qu’on utilise surtout aujourd’hui des variantes ou extensions de Diffie-Hellman, notamment sa variante « courbes elliptiques » (et oui, il faudra un jour que je parle des courbes elliptiques !)
4 Comments
Sujet très intéressant et vidéo très qualitative. Hâte de a prochaine sur comment générer des nombres aléatoires… qui sait, peut-être découvrirons-nous que ce n’est pas si aléatoire que ça ! Ahah ! 😄
Merci pour cette vidéo encore entre pédagogique.
Un autre outil très utilisé aujourd’hui en cryptographie et contre-intuitif à première vue sont les preuves à divulgation nulle de connaissance (zero knowledge proof). Je ne sais pas si ce sujet a déjà était traité mais il s’illustre/vulgarise assez bien avec des exemples bien choisis. Une application concrète de ces preuves est, par exemple, la connaissance d’un log discret (d’où ce commentaire).
Bonjour David,
Je regarde tes vidéos sur youtube (et parfois les billets) depuis un moment déjà, mais c’est la première fois que je commente alors je voudrais commencer par te remercier et te féliciter pour la qualité de ton contenu, j’apprends plein de choses et c’est toujours présenté de façon super pédagogique !
En tant qu’ancien matheux reconverti dans la crypto pratique, j’ai particulièrement apprécié la façon dont tu as réussi à couvrir tous les points importants de Diffie-Hellman dans cette vidéo et en particulier l’existence de mauvais choix pour g, expliquée de façon très exacte sans terme technique.
Par contre, j’ai trouvé dommage que la section d’intro, motivant le besoin d’avoir une clé partagée, se termine sur le Vigenere sans une petite phrase pour dire qu’en fait ce n’est pas ce qu’on utilise de nos jours, mais que de toutes façons on a besoin d’une clé partagée. J’ai apprécié que le billet précise un peu, mais pour une fois je trouve que la réalité est bien moins nuancée que ça : le Vigenere c’est de la crypto-jouet qui n’a qu’un intérêt historique ou pédagogique.
Casser le Vigenere est un exercice classique de début de cours de crypto. C’est par exemple l’exercice 1.5 du livre « exercices et problèmes de cryptographie » de Damien Vergnaud, ou le challenge 1.6 de cryptopals. Alors que casser DH (avec des paramètres réalistes) ça serait probablement une médaille Fields ou un prix Turing ou ce genre de choses ! On ne peut pas les mettre sur le même plan.
Bon, je te fais partiellement un mauvais procès parce que tu n’as à aucun moment explicitement mis le Vigenere et DH sur le même plan, mais je trouve que dans l’esprit d’une personne qui regarde la vidéo il peut vraiment sembler y avoir un parallèle entre « pour que la méthode soit assez robuste il faut utiliser un mot-clé suffisamment long » (3:56) et l’explication plus loin du fait qu’il faut bien choisir « g » pour DH.
Ce n’est pas le cas : DH correctement mis en œuvre (en particulier, couplé à une méthode d’authentification) répond autant qu’on sache à toutes les exigences modernes, alors que le Vigenere en est très loin : non seulement il ne permet pas de chiffrer des gros volumes de données avec une clé de taille raisonnable, mais il n’offre pas la moindre résistance à une attaque à clair connu, alors qu’on exige bien plus de nos jours (mot-clé : IND-CCA2).
Bon désolé, j’ai fait bien long pour un point relativement simple, alors pour conclure je vais dire que justement une chose que j’admire dans tes vidéos c’est ta capacité à expliquer plein de choses en peu de temps, tout en gardant un rythme posé qui permet de suivre.
Bonne journée et encore merci pour la qualité de ton travail !
Concernant les racines primitives de l’unité mod p, je ne veux surtout pas te décourager de te pencher dessus car il y a de jolies maths, mais en pratique on ne souhaite pas forcément que g engendre tout le groupe.
Par exemple, le RFC 7919 choisit p tel que p = 2q + 1 avec q premier, et g engendrant le sous-groupe d’ordre q. Le RFC 5114 choisir g engendrant un groupe d’ordre premier plus petit. Il est indispensable que l’ordre du groupe engendré par g ait un facteur premier assez grand, et c’est pratique de choisir cet ordre premier tout court, comme ça tous les éléments de ce groupe ont le même ordre (alors que si g engendre tout (Z/pZ)* il a forcément des puissances d’ordre faible, par exemple une d’ordre deux).
Complètement hors-sujet pour la vidéo, mais j’ai pensé que ça pourrait t’intéresser. J’ai remarqué que les bouquins/polys de maths qui parlent de crypto l’utilisent souvent comme un prétexte pour parler de certains sujets intéressants mais pas forcément pertinents dans la crypto réellement pratiquée. Par exemple à l’époque j’avais fait les TD d’un cours où on faisait Diffie-Hellman et El Gamal dans des corps à p^n éléments alors que dans le vraie vie tout le monde utilise des corps à p éléments (beaucoup plus simple à mettre en œuvre).
En tout cas je me réjouis d’avance de voir tes prochaines vidéos parlant de crypto, et si jamais tu as envie d’une relecture technique à un moment, ça serait avec plaisir !