# Crypto - Théorie de l’information et Cryptographie Chapitre précédent : [Introduction](https://notes.ar-lacroix.fr/s/8BiRh5595) ### Chiffrement parfaitement sûr --- Un chiffrement est parfaitement sûr si le chiffré ne donne aucune information sur le message. On peut le traduire par $H(C|M) = H(C)$ $$ H(C|M) = H(C) \\ \iff H(C,M) - H(M) = H(C) \\ \iff H(C, M) = H(C) + H(M) \\ \implies H(C, K) = H(C) + H(M) \\ \implies H(C) + H(K) \geq H(C,K) = H(C) + H(M) \\ \implies H(K) \geq H(M) \\ \implies |K| \geq |M| $$ Si on considère qu’un chiffrement est parfaitement sûr, alors nécessairement $$ |K| \geq |M| $$ C’est-à-dire : la taille de la clé est plus grande que la taille du message ### Construction d’un chiffrement parfaitement sûr --- Exemple: Chiffre de Vernam (Masque jetable / One Time Pad) **Propriété de sécurité #1** Pour une clé tirée de manière uniforme, la sortie suit une distribution uniforme ($P(c_i) = \frac{1}{2}$) **Propriété de sécurité #2** Pour un chiffre donné, tout clair est possible ⇒ On a une bijection avec le xor, il suffit de faire : $(m \bigoplus k)\bigoplus k = m$ **Le chiffre de Vernam est-il parfaitement sûr ?** Cela revient à prouver: $H(C|M) = H(C)$ (Prouver que l’entropie du chiffre sachant le message est la même chose que l’entropie du chiffre) On va calculer cette entropie $H(C|M)$ $$ H(C|M) = \sum_i \sum_j p(c_i, m_j)\ log_2(\frac{1}{p(c_i|m_j)}) $$ | k | m | c | | --- | --- | --- | | 0 | 0 | 0 | | 0 | 1 | 1 | | 1 | 0 | 1 | | 1 | 1 | 0 | $$ p (c_i = 0, m_j = 0) = \frac{1}{4} \\ p (c_i = 0, m_j = 1) = \frac{1}{4} \\ p (c_i = 1, m_j = 0) = \frac{1}{4} \\ p (c_i = 1, m_j = 1) = \frac{1}{4} \\ $$ $$ p(c_i = 0 | m_j = 0) = \frac{1}{2} \\ p(c_i = 0 | m_j = 1) = \frac{1}{2} \\ p(c_i = 1 | m_j = 0) = \frac{1}{2} \\ p(c_i = 1 | m_j = 1) = \frac{1}{2} \\ $$ Donc $$ H(C|M) = \sum_i \sum_j p(c_i, m_j)\ log_2(\frac{1}{p(c_i|m_j)}) \\ \sum_i\ \sum_j\ \frac{1}{4}\ log_2(\frac{1}{\frac{1}{2}})\\ \sum_i\ \sum_j\ \frac{1}{4}\ log_2(2) =log_2(2) = 1 = H(C) $$ On a donc un chiffrement parfaitement sûr. ### Pourquoi l’OTP n’est pas utilisé en pratique ? Le chiffrement est modifiable sans remettre en cause le processus de déchiffrement (on ne peut pas détecter la modification du chiffré) On peut par exemple effectuer des bit-flips pour modifier le clair. On ne peut pas non plus utiliser la même clé 2 fois (le XOR de deux chiffrés est égal au XOR des clairs) $c_1 \oplus c_2 = (m1 \oplus k) \oplus (m_2 \oplus k) = m_1 \oplus m_2$ **Maléabilité** Un attaquant veut échanger un message N en message Y et vice-versa, comment faire ? $$ c = n \oplus k \\ c' = c \oplus n \oplus y \\ c' = n \oplus k \oplus n \oplus y \\ c' = k \oplus y $$ On a le principe de confidentialité, mais on n’a pas l’intégrité. Pour l’utiliser en pratique on peut alors utiliser des méthodes pour vérifier l’intégrité des messages. **Partage de secret** Si y est uniformément distribué sur M, alors papa (qui a $y$) et maman (qui a $y \oplus M$) ne peuvent pas déclencher de guerre individuellement Distribution uniforme : Si tu émets des 0 et des 1, alors autant de 0 que de 1, pas de pattern qui se répète, etc. $p(0) = p(1) = \frac{1}{2}$ prochain cours : [ici](https://notes.ar-lacroix.fr/s/2XfonpbGs#)