Loading AI tools
Cryptosystème prouvé IND-CCA2 dans le modèle standard sous l'hypothèse DDH De Wikipédia, l'encyclopédie libre
En cryptologie, le cryptosystème de Cramer-Shoup est un chiffrement à clé publique introduit en 1998 par les cryptologues Ronald Cramer et Victor Shoup[1],[2],[3]. Historiquement, il s'agit du premier cryptosystème combinant les trois propriétés suivantes : il est résistant aux attaques adaptatives à chiffrés choisis (IND-CCA2), il est prouvé sûr dans le modèle standard, et il est efficace[1],[3]. Ces propriétés et d'autres le rendent particulièrement attrayant pour construire des mécanismes d'encapsulation de clés[4],[5].
La résistance aux attaques adaptatives à chiffrés choisis (IND-CCA2), introduite par Rackoff et Simon en 1991[6], correspond au plus haut niveau de sécurité atteignable par un cryptosystème pour le chiffrement[7]. La nécessité pratique d'une telle sécurité a été mise en avant par Bleichenbacher en 1998[8].
Plusieurs constructions IND-CCA2 ont été proposées dans le modèle de l'oracle aléatoire, notamment OAEP. Par ailleurs, des transformations génériques permettent d'atteindre ce niveau de sécurité, mais ils reposent sur des preuves à divulgation nulle de connaissance et s'avèrent très inefficaces. Jusqu'à l'introduction du cryptosystème de Cramer-Shoup, aucun chiffrement IND-CCA2 efficace n'était connu, dont la sécurité pouvait être prouvée dans le modèle standard[3]. La première preuve que de tels cryptosystèmes existent pourtant est due à Dolev, Dwork et Naor[9].
Le cryptosystème de Cramer-Shoup est une extension de celui d'ElGamal qui bloque la malléabilité du chiffré. Le prix à payer est que les clés et les chiffrés sont beaucoup plus larges que pour ElGamal (4 éléments de groupe pour le chiffré). De nombreuses variantes de Cramer-Shoup proposées depuis cherchent à réduire ce phénomène, quitte à réintroduire des hypothèses hors du modèle standard[10].
Le cryptosystème de Cramer-Shoup repose sur trois algorithmes décrits ici[1],[note 1],[11].
L'algorithme de « génération de clé » prend en entrée un paramètre de sécurité . Il détermine un groupe cyclique d'ordre et une fonction . Le choix de et de la fonction dépend de et se fait à partir de l'analyse de sécurité, voir plus bas.
L'algorithme donne deux générateurs aléatoires de et tire six exposants aléatoires . Il calcule alors :
Finalement l'algorithme retourne une clé publique , des paramètres publics , et la clé privée .
L'algorithme de chiffrement prend en entrée les paramètres publics, la clé publique, et un message . Un exposant est choisi uniformément au hasard, puis l'algorithme calcule :
Le chiffré correspondant est .
L'algorithme de déchiffrement prend en entrée les paramètres publics, la clé privée, et un chiffré . Il calcule et vérifie . Si l'égalité est fausse, l'algorithme de déchiffrement échoue et renvoie un symbole d'erreur (). Sinon, il renvoie .
Le cryptosystème de Cramer-Shoup est résistant aux attaques adaptatives à chiffrés choisis (IND-CCA2) lorsque la fonction est choisie dans une famille de fonctions de hachage universelles à sens unique[12],[note 2] par réduction, dans le modèle standard, à la difficulté du problème décisionnel de Diffie-Hellman dans [1],[note 3].
Seamless Wikipedia browsing. On steroids.
Every time you click a link to Wikipedia, Wiktionary or Wikiquote in your browser's search results, it will show the modern Wikiwand interface.
Wikiwand extension is a five stars, simple, with minimum permission required to keep your browsing private, safe and transparent.