« Cryptosystème de Cramer-Shoup » : différence entre les versions

Contenu supprimé Contenu ajouté

Intégrés

Version du 1 septembre 2018 à 03:16

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].

Histoire et motivation

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].

Description du cryptosystème

Le cryptosystème de Cramer-Shoup repose sur trois algorithmes $(G,E,D)$ décrits ici^[1]^,^{[Note 1]}^,^[11].

Génération de clé

L'algorithme de « génération de clé » $G$ prend en entrée un paramètre de sécurité $\lambda$ . Il détermine un groupe cyclique $\mathbb {G}$ d'ordre $q$ et une fonction $H:\mathbb {G} ^{3}\to \mathbb {Z} /(q)$ . Le choix de $q$ et de la fonction $H$ dépend de $\lambda$ et se fait à partir de l'analyse de sécurité, voir plus bas.

L'algorithme donne deux générateurs aléatoires $g_{1},g_{2}$ de $\mathbb {G}$ et tire six exposants aléatoires $x_{1},x_{2},y_{1},y_{2},z_{1},z_{2}\in \mathbb {Z} /(q)$ . Il calcule alors :

c\gets g_{1}^{x_{1}}g_{2}^{x_{2}},\quad d\gets g_{1}^{y_{1}}g_{2}^{y_{2}},\quad {\text{et}}\quad h\gets g_{1}^{z_{1}}g_{2}^{z_{2}}

Finalement l'algorithme retourne une une clé publique ${\mathsf {pk}}=\{c,d,h\}$ , des paramètres publics ${\mathsf {pp}}=\{\lambda ,\mathbb {G} ,g_{1},g_{2},q,H\}$ , et la clé privée ${\mathsf {sk}}=\{x_{1},x_{2},y_{1},y_{2},z_{1},z_{2}\}$ .

Chiffrement

L'algorithme de chiffrement $E$ prend en entrée les paramètres publics, la clé publique, et un message $m\in \mathbb {G}$ . Un exposant $r\in \mathbb {Z} /(q)$ est choisi uniformément au hasard, puis l'algorithme calcule :

u_{1}\gets g_{1}^{r},\quad u_{2}\gets g_{2}^{r},\quad e\gets mh^{r},\quad \alpha \gets H(u_{1},u_{2},e)\quad {\text{et}}\quad v\gets (cd^{\alpha })^{r}

Le chiffré correspondant est ${\mathsf {ct}}=\{u_{1},u_{2},e,v\}\in \mathbb {G} ^{4}$ .

Déchiffrement

L'algorithme de déchiffrement $D$ prend en entrée les paramètres publics, la clé privée, et un chiffré ${\mathsf {ct}}=\{u_{1},u_{2},e,v\}\in \mathbb {G} ^{4}$ . Il calcule $\alpha \gets H(u_{1},u_{2},e)$ et vérifie $u_{1}^{x_{1}+\alpha y_{1}}\cdot u_{2}^{x_{2}+\alpha y_{2}}\ {\stackrel {?}{=}}\ v$ . Si l'égalité est fausse, l'algorithme de déchiffrement échoue et renvoie un symbole d'erreur ( $\bot$ ). Sinon, il renvoie $m\gets eu_{1}^{-z_{1}}u_{2}^{-z_{2}}$ .

Sécurité

Le cryptosystème de Cramer-Shoup est résistant aux attaques adaptatives à chiffrés choisis (IND-CCA2) lorsque la fonction $H$ 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 $\mathbb {G}$ ^[1]^,^{[Note 3]}.

Notes et références

Notes

↑ Il existe plusieurs présentations équivalentes, et plusieurs variantes non équivalentes, du cryptosystème. Pour des alternatives (simplifiées ou étendues) voir (Boneh et Shoup 2017, chap 12.5).
↑ Une fonction de hachage résistante aux collisions est a fortiori universelle à sens unique et peut donc être utilisée pour instancier ce cryptosystème.
↑ La preuve originelle de Cramer et Shoup opère par réduction directe d'un adversaire CCA2 au problème DDH. Une preuve alternative consiste à montrer la sécurité sémantique et la simulabilité, voir (Dent 2006), qui ensemble impliquent IND-CCA2, voir (Bellare et coll. 2001).

Références

↑ ^{a b c et d} (en) Ronald Cramer et Victor Shoup, « A practical public key cryptosystem provably secure against adaptive chosen ciphertext attack », dans Advances in Cryptology — CRYPTO '98, Springer Berlin Heidelberg, 1998 (ISBN 9783540648925, DOI 10.1007/bfb0055717, lire en ligne), p. 13–25
↑ (en) Ronald Cramer et Victor Shoup, « Universal Hash Proofs and a Paradigm for Adaptive Chosen Ciphertext Secure Public-Key Encryption », dans Advances in Cryptology — EUROCRYPT 2002, Springer Berlin Heidelberg, 2002 (ISBN 9783540435532, DOI 10.1007/3-540-46035-7_4, lire en ligne), p. 45–64
↑ ^{a b et c} (en) Dan Boneh, « Cramer–Shoup Public-Key System », dans Encyclopedia of Cryptography and Security, Springer US, 2011 (ISBN 9781441959058, DOI 10.1007/978-1-4419-5906-5_144, lire en ligne), p. 269–270
↑ (en) Alexander W. Dent, « The Cramer-Shoup Encryption Scheme Is Plaintext Aware in the Standard Model », dans Advances in Cryptology - EUROCRYPT 2006, Springer Berlin Heidelberg, 2006 (ISBN 9783540345466, DOI 10.1007/11761679_18, lire en ligne), p. 289–307
↑ (en) Isamu Teranishi et Wakaha Ogata, « Cramer-Shoup Satisfies a Stronger Plaintext Awareness under a Weaker Assumption », dans Lecture Notes in Computer Science, Springer Berlin Heidelberg, 2008 (ISBN 9783540858546, DOI 10.1007/978-3-540-85855-3_8, lire en ligne), p. 109–125
↑ (en) Charles Rackoff et Daniel R. Simon, « Non-Interactive Zero-Knowledge Proof of Knowledge and Chosen Ciphertext Attack », dans Advances in Cryptology — CRYPTO ’91, Springer Berlin Heidelberg, 11 août 1991 (ISBN 9783540551881, DOI 10.1007/3-540-46766-1_35, lire en ligne), p. 433–444
↑ (en) Mihir Bellare, Anand Desai, David Pointcheval et Phillip Rogaway, « Relations among notions of security for public-key encryption schemes », dans Advances in Cryptology — CRYPTO '98, Springer Berlin Heidelberg, 1998 (ISBN 9783540648925, DOI 10.1007/bfb0055718, lire en ligne), p. 26–45
↑ (en) Daniel Bleichenbacher, « Chosen ciphertext attacks against protocols based on the RSA encryption standard PKCS #1 », dans Advances in Cryptology — CRYPTO '98, Springer Berlin Heidelberg, 1998 (ISBN 9783540648925, DOI 10.1007/bfb0055716, lire en ligne), p. 1–12
↑ (en) Danny Dolev, Cynthia Dwork et Moni Naor, « Nonmalleable Cryptography », SIAM Review, vol. 45, n^o 4,‎ janvier 2003, p. 727–784 (ISSN 0036-1445 et 1095-7200, DOI 10.1137/s0036144503429856, lire en ligne, consulté le 1^er septembre 2018)
↑ (en) Hovav Shacham, « A Cramer-Shoup Encryption Scheme from the Linear Assumption and from Progressively Weaker Linear Variants », sur eprint.iacr.org, 2007 (consulté le 1^er septembre 2018)
↑ (en) Dan Boneh et Victor Shoup, « A Graduate Course in Applied Cryptography », sur crypto.stanford.edu, 2017 (consulté le 1^er septembre 2018)
↑ (en) Mori Naor et Moti Yung, « Universal one-way hash functions and their cryptographic applications », STOC '89 Proceedings of the twenty-first annual ACM symposium on Theory of computing, ACM,‎ 1^er février 1989, p. 33–43 (ISBN 0897913078, DOI 10.1145/73007.73011, lire en ligne, consulté le 1^er septembre 2018)

Portail de la cryptologie

[11] Il existe plusieurs présentations équivalentes, et plusieurs variantes non équivalentes, du cryptosystème. Pour des alternatives (simplifiées ou étendues) voir (Boneh et Shoup 2017, chap 12.5).

[14] Une fonction de hachage résistante aux collisions est a fortiori universelle à sens unique et peut donc être utilisée pour instancier ce cryptosystème.

[15] La preuve originelle de Cramer et Shoup opère par réduction directe d'un adversaire CCA2 au problème DDH. Une preuve alternative consiste à montrer la sécurité sémantique et la simulabilité, voir (Dent 2006), qui ensemble impliquent IND-CCA2, voir (Bellare et coll. 2001).

[:0-1] {a b c et d} (en) Ronald Cramer et Victor Shoup, « A practical public key cryptosystem provably secure against adaptive chosen ciphertext attack », dans Advances in Cryptology — CRYPTO '98, Springer Berlin Heidelberg, 1998 (ISBN 9783540648925, DOI 10.1007/bfb0055717, lire en ligne), p. 13–25

[2] (en) Ronald Cramer et Victor Shoup, « Universal Hash Proofs and a Paradigm for Adaptive Chosen Ciphertext Secure Public-Key Encryption », dans Advances in Cryptology — EUROCRYPT 2002, Springer Berlin Heidelberg, 2002 (ISBN 9783540435532, DOI 10.1007/3-540-46035-7_4, lire en ligne), p. 45–64

[:1-3] {a b et c} (en) Dan Boneh, « Cramer–Shoup Public-Key System », dans Encyclopedia of Cryptography and Security, Springer US, 2011 (ISBN 9781441959058, DOI 10.1007/978-1-4419-5906-5_144, lire en ligne), p. 269–270

[4] (en) Alexander W. Dent, « The Cramer-Shoup Encryption Scheme Is Plaintext Aware in the Standard Model », dans Advances in Cryptology - EUROCRYPT 2006, Springer Berlin Heidelberg, 2006 (ISBN 9783540345466, DOI 10.1007/11761679_18, lire en ligne), p. 289–307

[5] (en) Isamu Teranishi et Wakaha Ogata, « Cramer-Shoup Satisfies a Stronger Plaintext Awareness under a Weaker Assumption », dans Lecture Notes in Computer Science, Springer Berlin Heidelberg, 2008 (ISBN 9783540858546, DOI 10.1007/978-3-540-85855-3_8, lire en ligne), p. 109–125

[6] (en) Charles Rackoff et Daniel R. Simon, « Non-Interactive Zero-Knowledge Proof of Knowledge and Chosen Ciphertext Attack », dans Advances in Cryptology — CRYPTO ’91, Springer Berlin Heidelberg, 11 août 1991 (ISBN 9783540551881, DOI 10.1007/3-540-46766-1_35, lire en ligne), p. 433–444

[7] (en) Mihir Bellare, Anand Desai, David Pointcheval et Phillip Rogaway, « Relations among notions of security for public-key encryption schemes », dans Advances in Cryptology — CRYPTO '98, Springer Berlin Heidelberg, 1998 (ISBN 9783540648925, DOI 10.1007/bfb0055718, lire en ligne), p. 26–45

[8] (en) Daniel Bleichenbacher, « Chosen ciphertext attacks against protocols based on the RSA encryption standard PKCS #1 », dans Advances in Cryptology — CRYPTO '98, Springer Berlin Heidelberg, 1998 (ISBN 9783540648925, DOI 10.1007/bfb0055716, lire en ligne), p. 1–12

[9] (en) Danny Dolev, Cynthia Dwork et Moni Naor, « Nonmalleable Cryptography », SIAM Review, vol. 45, n^o 4,‎ janvier 2003, p. 727–784 (ISSN 0036-1445 et 1095-7200, DOI 10.1137/s0036144503429856, lire en ligne, consulté le 1^er septembre 2018)

[10] (en) Hovav Shacham, « A Cramer-Shoup Encryption Scheme from the Linear Assumption and from Progressively Weaker Linear Variants », sur eprint.iacr.org, 2007 (consulté le 1^er septembre 2018)

[12] (en) Dan Boneh et Victor Shoup, « A Graduate Course in Applied Cryptography », sur crypto.stanford.edu, 2017 (consulté le 1^er septembre 2018)

[13] (en) Mori Naor et Moti Yung, « Universal one-way hash functions and their cryptographic applications », STOC '89 Proceedings of the twenty-first annual ACM symposium on Theory of computing, ACM,‎ 1^er février 1989, p. 33–43 (ISBN 0897913078, DOI 10.1145/73007.73011, lire en ligne, consulté le 1^er septembre 2018)

[1]

[2]

[3]

[4]

[5]

[6]

[7]

[8]

[9]

[10]

[Note 1]

[11]

[12]

[Note 2]

[Note 3]