La plupart des méthodes de cryptographie actuelles dépendent de la difficulté de factoriser les nombres qui sont le produit de deux grands nombres premiers. Si je comprends bien, cela n'est difficile que tant que la méthode utilisée pour générer les grands nombres premiers ne peut pas être utilisée comme raccourci pour factoriser le nombre composite résultant (et que la factorisation des grands nombres elle-même est difficile).
Il semble que les mathématiciens trouvent de meilleurs raccourcis de temps en temps, et les systèmes de cryptage doivent donc être mis à niveau périodiquement. (Il est également possible que l'informatique quantique finisse par rendre la factorisation un problème beaucoup plus facile, mais cela ne surprendra personne si la technologie rattrape la théorie.)
Certains autres problèmes s'avèrent difficiles. Deux exemples qui me viennent à l'esprit sont les variations du problème du sac à dos et du problème des vendeurs ambulants.
Je sais que Merkle – Hellman a été brisé, que Nasako – Murakami reste sécurisé et que les problèmes de sac à dos peuvent être résistants à l'informatique quantique. (Merci, Wikipedia.) Je n'ai rien trouvé à propos de l'utilisation du problème du voyageur de commerce pour la cryptographie.
Alors, pourquoi des paires de grands nombres premiers semblent-elles gouverner la cryptographie?
- Est-ce simplement parce qu'il est actuellement facile de générer des paires de grands nombres premiers faciles à multiplier mais difficiles à factoriser?
- Est-ce parce que la factorisation de paires de grands nombres premiers s'est avérée difficile à un degré prévisible qui est assez bon?
- Les paires de grands nombres premiers sont-elles utiles autrement que par la difficulté, comme la propriété de travailler à la fois pour le chiffrement et la signature cryptographique?
- Le problème de la génération d'ensembles de problèmes pour chacun des autres types de problèmes qui sont suffisamment difficiles pour le but cryptographique lui-même est-il trop difficile à réaliser?
- Les propriétés d'autres types de problèmes sont-elles insuffisamment étudiées pour être fiables?
- Autre.
Réponses:
Boaz Barak en a parlé dans un article de blog
Ce que je retiens de son article (en gros), c'est que nous savons seulement comment concevoir des primitives cryptographiques en utilisant des problèmes de calcul qui ont une certaine structure, que nous exploitons. Sans structure, nous ne savons pas quoi faire. Avec trop de structure, le problème devient efficacement calculable (donc inutile à des fins cryptographiques). Il semble que la quantité de structure doit être juste.
la source
Tout ce que je vais dire est bien connu (tous les liens sont vers Wikipédia), mais voilà:
Il existe d'autres approches de la cryptographie, notamment la cryptographie sur réseau qui repose sur certains problèmes difficiles sur les réseaux (trouver des points avec une petite norme sur le réseau, par exemple) pour implémenter la cryptographie à clé publique. Il est intéressant de noter que certains de ces systèmes sont éprouvables , c'est-à-dire qu'ils peuvent être brisés si et seulement si le problème dur correspondant dans la théorie du réseau peut être résolu. C'est en contraste avec, disons RSA qui n'offre pas le même garant . Notez que l'approche basée sur le réseau est supposée ne pas être NP-difficile (mais semble plus difficile que la factorisation entière pour l'instant).
Il y a une préoccupation distincte pour le partage de clés, à savoir la révélation secrète , qui a des propriétés théoriques de complexité très intéressantes. Je ne connais pas les détails, mais la théorie des protocoles de connaissance zéro permet à Alice de révéler à Bob sa connaissance d'un secret qui est NP difficile à calculer (graphique hamiltonien) sans révéler le secret lui-même (le chemin dans ce cas).
Enfin, vous voudrez peut-être consulter la page sur la cryptographie post-quantique pour voir quelques approches alternatives aux cryptosystèmes à clé publique qui reposent sur des problèmes difficiles.
la source