TD 7

Q1.

On pose \(x=r^e\mod n\) à clair \(r\) choisi. Le chiffré du message \(xc\) est \(s=(xc)^d \mod n=x^d c^d\mod n=r^{ed}m^{ed}\mod n=rm\mod n\). Si \(r\) est inversible modulo \(n\), on a \(m=r^{-1}s\mod n\). Sinon, le PGCD de \(r\) et \(n\) est un facteur non trivial de \(n\), et on a la factorisation de \(n\), ce qui nous permet de déchiffrer le message.

Q2.

Ne jamais signer et chiffrer avec les mêmes clés.

Q3.

On calcule la relation de Bézout \(u_1e_1+u_2e_2=1\), et on a \(m=m^{u_1e_1+u_2e_2}={m^{e_1}}^{u_1}{m^{e_2}}^{u_2}={c_1}^{u_1}{c_2}^{u_2} \mod n\).

Q4.

Ne jamais partager les secrets.

Q5.

On veut que pour un message \(m^\prime\) de notre choix, on ait un clé publique \((e_B^\prime,n_B^\prime)\) de sorte que le nouveau couple chiffré-signature soit le même que le couple original. Pour cela, si on identifie \(n_B^\prime\) à \(n_B\), il suffit de choisir \(e_B^\prime\) tel que \(m^{e_B}={m^\prime}^{e_B^\prime} \mod n_B\).

Pour le dernier, on prend une perturbation de \(m^\prime\) de sorte qu'il soit un générateur de \(\mathbb{Z}/n_B\mathbb{Z}^{\times}\), et on calcule \(x\) tel que \({m^\prime}^x=m \mod n_B\) par BSGS. On a donc \(m^{e_B}={m^\prime}^{xe_B} \mod n_B\), et donc on choisit \(e_B^\prime=xe_B\).

Q6.

Ne jamais chiffrer puis signer.

Q1.

Oui : si \(N_1\) et \(N_2\) ne sont pas premiers entre eux, le calcul de PGCD de \(N_1\) et \(N_2\) nous permet de trouver un facteur commun, et donc de factoriser \(N_1\) et \(N_2\).

Q2.

On a \(c_i = m^3 \mod N_i\) pour tout \(i\), donc le CRT nous permet de trouver \(c=m^3 \mod N_1N_2N_3N_4\).

La complexité est donc \(\mathcal{O}(\log^2(N_1N_2N_3N_4))\).

Q3.

C'est clair car \(m< N_i\) pour tout \(i\) (on peut même remplacer \(m^3\) par \(m^4\) dans l'énoncé).

Q4.

D'après la question 3, \(m^3=c \mod N_1N_2N_3N_4\) implique \(m^3=c\). L'attaque consiste donc à calculer \(c\) par le CRT, puis de calculer la racine cubique de \(c\). Cette attaque fonctionne encore si on connaît trois valeurs parmi les quatre \(c_i\), mais ne fonctionne pas si on connaît seulement deux valeurs parmi les quatre \(c_i\) (dans ce cas la valeur de \(m^3\) ne peut pas pas déterminée).

Q1.

Pour \(n=21=3\times 7\), on a \(\varphi(n)=(3-1)(7-1)=12\). Par définition de RSA, \(ed = 1\mod\varphi(n)\), donc \(e\) est inversible modulo \(\varphi(n)\), soit \(1\), \(5\), \(7\) ou \(11\). De plus, \(e\) ne doit pas être \(1\), sinon le chiffrement est trivial. Donc \(e=5\) ou \(7\) ou \(11\).

Q2.

Pour \(n=221=13\times 17\), \(d=121\) et \(C=2\), on calcule

• \(C^d\mod 13 = C^{d\% 12}\mod 13 = 2^1\mod 13 = 2\mod 13\),
• \(C^d\mod 17 = C^{d\% 16}\mod 17 = 2^9\mod 17 = 2\mod 17\).

Puis, on applique le théorème des restes chinois pour trouver \(C^d\mod 221\). Ici, il est assez évident que \(C^d=2\mod 221\). Donc, le chiffrement est trivial, ce qui montre que le choix de \(d\) n'est pas optimal …