M1 Cryptographie¶

Mise à niveau en arithmétique¶

Exercices à résoudre sur papier, n'utiliser l'ordinateur que comme calculette¶

Exercice 1¶

$\def\ZZ{{\mathbb Z}}$

  1. Calculer la table de multiplication de $\ZZ/9\ZZ$. On note $G_9$ le groupe de ses éléments inversibles.
  2. Donner la liste des éléments de $G_9$ et la valeur de $\varphi(9)$. Comparer avec la formule du cours pour $\varphi(n)$.
  3. Vérifier que 2 est d'ordre $\varphi(9)$. Quel est l'ordre de 4 ? Et celui de 8 ?
  4. Pour chaque élément de $G_9$ indiquer son inverse.
  5. Le groupe $G_9$ est-il cyclique ?
In [1]:
# 1.
def tabmul(n):
    print(' * |', end=' ')
    for y in range(1,n): 
        print ("%2d "% (y % n),end=' ') 
    print()
    print('-'*(4*n-1))
    for x in range(1,n): 
        print('%2d |'%x, end= ' ')
        for y in range(1,n): 
            print ("%2d "% ((x*y) % n),end=' ') 
        print()

tabmul(9)

 * |  1   2   3   4   5   6   7   8  
-----------------------------------
 1 |  1   2   3   4   5   6   7   8  
 2 |  2   4   6   8   1   3   5   7  
 3 |  3   6   0   3   6   0   3   6  
 4 |  4   8   3   7   2   6   1   5  
 5 |  5   1   6   2   7   3   8   4  
 6 |  6   3   0   6   3   0   6   3  
 7 |  7   5   3   1   8   6   4   2  
 8 |  8   7   6   5   4   3   2   1
  1. Les éléments inversibles sont ceux qui n'ont pas de diviseur commun avec 9, c'est à dire 1,2,4,5,7,8. Il y en a 6, donc par définition $\varphi(9)=6$.

La formule du cours donne $$\varphi(9)=9\left(1-\frac13\right)=9\times\frac23=6$$ ou encore $$\varphi(9)=\mu(9)1+\mu(3)3+\mu(1)9=0-3+9=6.$$

  1. $2^1=1$, $2^2=4$, $2^3=8$, $2^4=16\equiv 7$, $2^5=2\times 7=14\equiv 5$, $2^6=2\times 5=10\equiv 1$. Donc 2 est d'ordre 6.

Pour $4$, on a $4^2=7$, $4^3=7\times 4=28=1$ donc 4 est d'ordre 3.

Pour $8$, $8^2=64=63+1=1$, il est d'ordre 2.

2,3 et 6 sont bien des diviseurs de 6, comme prédit par le théorème de Lagrange.

  1. $1=1\times 1= 2\times 5=4\times 7=8\times 8$.

  2. 2 est d'ordre 6, donc le groupe $G_9$ est cyclique.

Exercice 2¶

Calculer le pgcd $d$ de $a=561$ et $b=476$ par l'algorithme d'Euclide étendu, et trouver $u$ et $v$ tels que $d=au+bv$.

Le tableau des divisions itérées style CM2 donne

      | 1   | 5  | 1  | 1  | 2
----------------------------------------------------------------
  561 | 476 | 85 | 51 | 34 | 17
-----------------------------------------------------------------
   85 |  51 | 34 | 17 |  0 |

Le dernier reste non nul est 17, qui est donc le pgcd.

On remonte le calcul : $17=51-34$, $34=85-51$, $85=561-476=a-b$, $51=476-5\times 85=b-5(a-b)=-5a+6b$, $34=(a-b)-(-5a+6b)=6a-7b$, $17=51-34=-5a+6b-(6a-7b)=-11a+13b$.

Exercice 3¶

On va utiliser le système RSA avec $p=11$, $q=13$.

  1. Calculer $n=pq$, et écrire $p,q,n$ en binaire.
  2. En conclure qu'on peut utiliser ce système pour chiffrer les caractères ASCII (codes de 0 à 127)
  3. Calculer $\varphi(n)$.
  4. Peut-on utiliser l'exposant public $e=3$ ? Pourquoi ?
  5. On choisit $e=17$. Calculer l'exposant privé $d$.
  6. Si on prenait $e=11$, quel serait l'exposant privé ?

  1. $n=11\times 13=143$. $11=\overline{1011}$, $13=\overline{1101}$, $143 =\overline{10001111}$.

  2. On a bien $127<143$.

  3. $\varphi(n)=(p-1)(q-1)=120$.

  4. 3 n'est pas inversible modulo 120, donc on ne peut pas.

  5. L'exposant privé $d$ est l'inverse de $e$ modulo 120. On a $17\times 7=119\equiv -1\mod 120$ donc l'inverse est $-7=113$.

  6. Si on prenait $e=11$, comme $11\times 11=121\equiv 1\mod 120$, l'exposant privé serait aussi égal à 11.

Exercice 4¶

Résoudre $$\left\{\begin{matrix}x\equiv 2\ [3]\\ x\equiv 3\ [5]\\ x\equiv 2 \ [7]\end{matrix}\right.$$

ensuite, regarder là.

On a $5\times 7=35\equiv 0 \mod 5$ et 7 par définition, et $35\equiv 2\mod 3$, donc si on multiplie 35 par l'inverse de 2 modulo 3, qui est 2, on trouve 70 qui vaut bien 1 modulo 3 et 0 modulo 5 et 7.

Ensuite, $3\times 7=21\equiv 1\mod 5$ donc il n'y a rien d'autre à faire.

De même, $3\times 5=15\equiv 1\mod 7$, donc là non plus.

Une solution est donc $2\times 70+3\times 21+2\times 15 = 233$. La plus petite solution positive s'obtient en réduisant ce nombre modulo $3\times 5\times 7=105$, ce qui donne $x=23$.

Exercice 5¶

  1. Calculer $42^{666}\mod 43$.

$42\equiv -1\mod 43$ donc $42^{666}\mod 43=1$.

  1. Sachant que $p=2^{107}-1$ est premier, calculer $2^{(2^{108})}\mod p$.

D'après Fermat, $2^{(2^{107})-2}\equiv 1\mod p$, donc $2^{(2^{107})}\equiv 2^2=4\mod p$, et $2^{2^{108}}=\left(2^{(2^{107})}\right)^2\equiv 4^2=16\mod p$.

  1. Prouver que $2^{70}+3^{70}$ est divisible par 13.

Il faut montrer que $2^{70}+3^{70}\equiv 0\ [13]$, donc calculer $2^{70}$ et $3^{70}$ modulo 13. Comme 13 est premier, tout entier non divisible par 13 vérifie $a^{12}\equiv 1\ [13]$.

On a $70\equiv 10 \mod 12$ donc $2^{70}+3^{70}\equiv 2^{10}+3^{10} \mod 13$. On a $2^5=32\equiv 6$ donc $2^{10}\equiv 36 \equiv 10\mod 13$ et $3^3=27\equiv 1 \mod 13$ donc $3^{10}\equiv 3$. Maintenant, $10+3=13$ ...

In [ ]: