TD 5

Q1.

On rappelle que \(\mathcal{M}(n)\), le coût de multiplier deux entiers de taille \(\log n\), est en \(\mathcal{O}(\log^2 n)\) par la multiplication naïve. Il faut donc montrer que l'exponentiation modulaire peut prendre au total \(\mathcal{O}(\log e)\) multiplications. Pour cela, on utilise la méthode square-and-multiply :

Donc il y a un nombre constant de multiplications pour chaque bit de \(e\), et le nombre total de multiplications est en \(\mathcal{O}(\log e)\).

Q2.

Une dérécursification est donnée par :

expmod := proc(a, e, n)
    local r, i;
    r := 1;
    for i from ilog2(e) to 0 by -1 do
        r := r^2 mod n;
        if Bits:-GetBits(e, i) = 1 then
            r := r * a mod n;
        end if;
    end do;
    return r;
end proc;

La version itérative a la même complexité que la version récursive, et devrait avoir la même performance avec un compilateur optimisé. Cependant, dans le domaine de la cryptographie, on évite des optimisations pour limiter les attaques par canal auxiliaire, et donc on préfère la version itérative qui est moins gourmande en utilisation de la pile.

Q3.

Rappelons que dans Diffie-Hellman, on fait au total quatre exponentiations modulaires :

• Alice envoie \(A = g^a \mod p\) à Bob,
• Bob envoie \(B = g^b \mod p\) à Alice,
• Alice calcule \(K = B^a \mod p\),
• Bob calcule \(K = A^b \mod p\).

Donc le coût total est en \(\mathcal{O}((2\log(a)+2\log(b))\mathcal{M}(p))=\mathcal{O}(\log(\max(a,b))\mathcal{M}(p))\).

Q1.

Le piège de cette question est que l'entrée a en effet pour taille \(\log_{2}(n)\). Donc \(2n+3\) et \(n^2+7\) sont tous les deux exponentiels en \(\log_{2}(n)\). Spécifiquement,

• \(\log_{2}(2n+3) = \log_{2}(n)+\log_{2}(2+3/n) = \log_{2}(n)+\mathcal{O}(1)\), donc \(2n+3\in\mathcal{O}(2^{\log_{2}(n)})\).
• \(\log_{2}(n^2+7) = 2\log_{2}(n)+\log_{2}(1+7/n^2) = 2\log_{2}(n)+\mathcal{O}(1)\), donc \(n^2+7\in \mathcal{O}(2^{2\log_{2}(n)})\).

Bien sûr, \(2n+3\) est très inférieur à \(n^2+7\) pour \(n\) grand.

Q2.

On a \(2^{4\ell+1}=16\cdot 2^{4\ell}\), donc le nombre d'opérations augmente de 16 fois.

Q3.

Il suffit de montrer que \(\log_{2}(2^{\log^{\alpha}(n)})=\log^{\alpha}(n)\) est en \(o(\log(n))\). Effectivement, \(\frac{\log^{\alpha}(n)}{\log(n)}=\log^{\alpha-1}(n)\) tend vers 0 quand \(n\) tend vers l'infini, car \(\log(n)\) tend vers l'infini et \(\alpha-1<0\).

Il s'agit de questions du cours, mais je fais un rappel ici. Soit \(G\) un groupe cyclique d'ordre \(p\) engendré par \(g\), et \(h\) un élément de \(G\). Le problème du logarithme discret (DLP) est de trouver \(x\) tel que \(g^x=h\). Pour ce problème, l'algorithme de meilleure complexité est le baby-step giant-step (BSGS).

L'idée est la suivante : Soit \(s=\lceil\sqrt{p}\rceil\), on récrit \(x=qs+r\) avec \(0\leq r< s\), et \(g^x=h\) devient \(g^{r}=h\cdot (g^{-s})^q\). Comme \(x\) est entre 0 et \(p-1\), on a aussi \(0\leq q< s\). Pour trouver \(q\) et \(r\), on calcule les \(s\) baby-steps \(g^{i}\) pour \(0\leq i< s\) et les \(s\) giant-steps \(h\cdot (g^{-s})^{j}\) pour \(0\leq j< s\), et on cherche une collision entre les deux listes. Une fois \(q\) et \(r\) trouvés, on renvoie \(x=qs+r\).

La complexité de BSGS est donc en \(\mathcal{O}(\sqrt{p})\).

On a \(p=23\), \(g=11\) et \(h=3\), donc \(s=5\), \(g^{-s}=14\), et

• BS: \(g^0=1\), \(g^1=11\), \(g^2=6\), \(g^3=22\), \(g^4=13\).
• GS: \(h\cdot (g^{-s})^{0}=3\), \(h\cdot (g^{-s})^{1}=19\), \(h\cdot (g^{-s})^{2}=13\), …

On trouve une collision entre \(g^4\) et \(h\cdot (g^{-s})^{2}\), donc \(q=2\) et \(r=4\), et \(x=qs+r=2\cdot 5+4=14\).

Q1, Q2.

Rappelons que \(\mathbb{F}_{p}^{\times}\) consiste en les éléments de \(\mathbb{F}_{p}\) qui sont inversibles pour la multiplication modulo \(p\). Donc \(\mathbb{F}_{p}^{\times}\) est composé des éléments \(1\mod p\), \(2\mod p\), …, \(p-1\mod p\), et est de cardinal \(p-1\).

Q3.

Rappelons que l'ordre d'un élément \(a\) de \(\mathbb{F}_{p}^{\times}\), que l'on note \(\omega(a)\), est le plus petit entier \(k\) strictement positif tel que \(a^k=1\mod p\). Par le théorème de Lagrange, on a \(\omega(a)\mid p-1\).

Pour le reste de la question, voir Feuille 1, Exo 16, Q5.

Q4.

Si \(a\) n'est pas premier avec \(p\), alors \(a^p = a = 0 \mod p\).

Si \(a\) est premier avec \(p\), alors \(a \mod p\) est un élément de \(\mathbb{F}_{p}^{\times}\). Par la question précédente, \(a^{p-1} = (a^{\omega(a)})^{\frac{p-1}{\omega(a)}} = 1 \mod p\), et donc \(a^p = a \mod p\).

Q5.

On montre par récurrence sur \(n\).

• Si \(n=0\), un polynôme non nul de degré 0 est un constant non nul, donc a 0 racines.
• Supposons que l'énoncé est vrai pour \(n-1\). Soit \(P\) un polynôme de degré \(n\). Si \(P\) n'a pas de racines, on a fini. Sinon, soit \(a\) une racine de \(P\). Alors \(P(x) = (x-a)Q(x)\) pour un certain polynôme \(Q\) de degré \(n-1\). Par l'hypothèse de récurrence, \(Q\) a au plus \(n-1\) racines, donc \(P\) a au plus \(n\) racines. L'énoncé est donc vrai pour \(n\).

Q6.

Pour cette question, remplaçons "une unique sous-groupe" par "au plus un sous-groupe".

D'après l'énoncé, pour montrer que \(\mathbb{F}_{p}^{\times}\) est cyclique, il suffit de montrer que pour tout diviseur \(d\) de \(p-1\), il existe au plus un sous-groupe de cardinal \(d\). Or, pour un tel sous-groupe \(G\) de cardinal \(d\), chaque élément \(a\in G\) vérifie \(a^d=1\mod p\), et donc est une racine du polynôme \(X^d-1\). Comme ce polynôme a au plus \(d\) racines, \(G\) est exactement l'ensemble des racines de \(X^d-1\), et est donc unique.

Q7.

Soit \(g\) un générateur de \(\mathbb{F}_{p}^{\times}\). Pour tout élément \(a\in \mathbb{F}_{p}^{\times}\), il existe un unique entier \(x\) tel que \(a=g^x\mod p\). D'après Feuille 1, Exo 16, Q4, on a \(\omega(a)=\frac{p-1}{\gcd(p-1,x)}\), donc \(a\) est un générateur de \(\mathbb{F}_{p}^{\times}\) si et seulement si \(\gcd(p-1,x)=1\). \(\mathbb{F}_{p}^{\times}\) a donc \(\varphi(p-1)\) générateurs.

Q1.

L'ordre de 5 est un diviseur de \(p-1=22\), donc est soit 1, 2, 11 ou 22.

Or, on vérifie facilement que \(5^1=5\mod 23\), \(5^2=2\mod 23\), \(5^{11}=22\mod 23\), donc l'ordre de 5 est 22.

Q2.

\(5\) a un ordre assez grand par rapport à l'ordre du groupe, donc on peut utiliser Diffie-Hellman-Merkle.

(Ici, les deux ordres sont même égaux …)

Q3.

Il suffit d'expliquer proprement le protocole Diffie-Hellman-Merkle.

Attention ! Pour arriver à \(A=8\), il faut prendre \(a=6\) (que l'on peut calculer par BSGS).

Q1.

La clé publique \(k_{A}\) est telle que \(10=\alpha^{k_{A}}\mod p\), donc \(k_{A}=3\).

Q2.

Rappelons que \((c_1,c_2)=(\alpha^t,m\cdot \beta_{B}^{17})\mod p\). Il n'est pas difficile de trouver \((c_1,c_2)=(15,20)\).

Q3.

On a \(m=22\cdot(17^9)^{-1}\mod 23 = 13\mod 23\).

(Partiel 2019 - Exercice 4)