TD2

Exercice 1

Exemple de transposition : ‘Meet us at the park today’ Clé de 5x4:

meetu
satth
epark
today

Chiffré : mseteapoetadttrauhky

SUTSTRUISREERYNAOCTAOSCIIOPDTIPCS

SEC
URI
TYI
SNO
TAP
ROD
UCT
ITI
SAP
ROC
ESS

Message: SECURITY IS NOT A PRODUCT IT IS A PROCESS

21 34 42 44 54-44 52 34: 44 23 15 11 33 43 52 15 42 44 34 31 24 21 15

Pk = (e, n) ; sk = (p, q) Chiffrer : $C = M^{e} mod n$ Dechiffrer : $M = C^{d} = (M^{e})^{d} = M mod n$

$p = 3$ , $q = 11$ $n = p . q = 33$ $ϕ (n) = (p - 1) (q - 1) = 20$
$e = 7$ , $M = 2$ $2^{7} mod 33 = 29 mod 33$
$d = e^{- 1}$ , $e = 7 mod 20$
yep
$c_{1} . c_{2} = m_{1}^{e} . m_{2}^{e} = (m_{1} . m_{2})^{e}$ donc RSA est homomorphique avec la

Chiffrement de ElGamal: $P k = (g, h)$ , $S k = a$ Chiffrer : $C = (c_{1}, c_{2}) = (g^{k}, m . h^{k})$ Déchiffrer : $m = c_{2} . (c_{1}^{a})^{- 1}$
$a = 2$ , $(p, g) = (5, 3)$ $h = g^{a} mod p = 4 mod 5$ $C = (4, 2)$ , $2. (4^{2})^{- 1} mod 5 = 3 mod 5$
$r = 2$ $C = (g^{r}, m . h^{r}) = (3^{2}, 2. 4^{2}) = (4, 2)$
Etant donnée $y = g^{x} mod p$ , il est difficile de retrouver x.
Propriété homomorphique sur ElGamal: $C_{1} = (c_{1}, c_{2}) = (g^{r_{1}}, m_{1} . h^{r_{1}})$ $C_{2} = (c_{1}, c_{2}) = (g^{r_{2}}, m_{2} . h^{r_{2}})$ $C_{1} . C_{2} = (g^{r_{1} + r_{2}}, m_{1} . m_{2} . h^{r_{1} + r_{2}})$

a. Expression de $Dec (c_{1} \times c_{2})$ en fonction de $m_{1}$ et $m_{2}$ . $Dec (c_{1} \times c_{2}) = Dec (E n c (m_{1} \times m_{2}))$ b. Le challenge est $c$ qu’on ne peut pas déchiffrer. Mais on peut déchiffrer tout autre message. On peut générer $m^{'}$ une valeur aléatoire et demander à l’oracle de chiffrement de chiffrer $m^{'}$ en tant que $c^{'}$ . Puis demander à l’oracle de déchiffrement de déchiffrer $(c \times c^{'})$ qui nous donne $m \times m^{'}$ et récupérer $m$ en divisant par $m^{'}$ .

Avec $G$ et $H$ des fonctions de hachage connu : Chiffrer : $f (r) ∣∣ (G (r) \oplus (x ∣∣ H (x)))$ Dechiffrer :