TP Bonus : cryptographie RSA

Remarque : nous aurons besoin de vos fonctions des TP1, TP2 et TP3.

1. Programme préliminaire

1.1 Indicatrice d'Euler

On définit la fonction indicatrice d'Euler phi(n) d'un entier naturel strictement positif n par le nombre d'entiers inférieurs ou égaux à n et premiers avec n.

  • Construire une fonction phi(n).

Exemple :

In [3]:
print(phi(13))
print(phi(15))
print(phi(18))

12
8
6
  • Si n est premier, que vaut phi(n) ?
  • Vérifier empiriquement que si p et q des nombres premiers distincts, alors phi(pq) = (p-1)(q-1).

2. Création de nombres premiers "relativement" grands.

2.1 Exercice : temps de calcul

  • Construire une fonction primal_temps(n,tps) qui recherche un un diviseur de n tant que le temps de calcul ne dépasse pas tps (en seconde). Cette fonction devra retourner
    • un booléen caractérisant le fait que n est premier ou non (si le temps de calcul n'a pas dépassé tps).
    • le message "temps" dès que le temps de calcul dépasse tps.

Remarque : Votre programme devra arrêter la recherche de diviseur dès que le temps de calcul dépasse tps.

Exemple :

In [5]:
print(primal_temps(2147483649,0.3))
print(primal_temps(2147483647,0.3))

False
True
In [6]:
print(primal_temps(100000002251,0.3))
print(primal_temps(100000002251,1))

temps
True
In [7]:
print(primal_temps(67280421310721 ,10))
print(primal_temps(67280421310721 ,20))

temps
True

2.2 Exercice : "grands" nombres de Mersenne premiers

Les nombres de Mersenne sont ceux s'écrivant $2^{n}-1$, avec n premier. Attention, tous ne sont pas des nombres premiers.
Par exemple :
$2^{19}-1$ est premier, mais $2^{23}-1$ ne l'est pas.

  • Construire une fonction mersenne_grand(tps) qui retourne le plus grand nombre de Mersenne, premier, dont le temps de calcul est inférieur à tps.

Exemple :

In [11]:
print(mersenne_grand(0.0005))
print(mersenne_grand(0.005))
print(mersenne_grand(0.5))
print(mersenne_grand(5))

8191
524287
2147483647
2147483647

Le plus grand nombre obtenu en moins d'une minute devrait être $2^{31}-1$, c'est à dire 2 147 483 647.
Pour information, le prochain nombre de Mersenne premier est $2^{61}-1$, c'est à dire 2 305 843 009 213 693 951. Il m'a fallu plus de 5min pour l'obtenir.
Il n'a pu être calculé qu'à la fin du 19e siècle.

3. Cryptographie RSA

L'efficacité du chiffrement RSA repose sur les faits suivants :

  • il est "simple" de créer des nombres premiers $p$ et $q$ grands (plusieurs dizaines de chiffres)
  • étant donné un nombre $n=pq$, il est difficile de retrouver les valeurs de $p$ et de $q$ à partir de $n$.

Exemple :

In [12]:
n = 524287*2147483647
temps(decomposition,n)

360.809386

A partir de nombres premiers $p$ et $q$ crées en moins d'une seconde, il a fallu plus de 300 sec pour les retrouver si on ne connait que n.

Le principe du chiffrement repose sur cette difficulté.

  • Pour chiffrer, on a besoin de $n$.
  • Pour déchiffrer, on a besoin de phi(n), c'est à dire de $(p-1)(q-1)$, c'est à dire de $p$ et de $q$.

principe du chiffrement RSA

Explication du chiffrement RSA

Exemple : On choisit

In [13]:
p = 41
q = 103
e = 19

d vaut alors :

In [14]:
print(inverse(19,(p-1)*(q-1)))

859
  • Créer une fonction chiffrementRSA(m,n,e) qui chiffre un message m à l'aide de la clef publique n,e.

Exemple : on veut chiffre 192 avec les clefs précédentes.

In [16]:
print(chiffrementRSA(192,p*q,19))

1864
  • Créer une fonction dechiffrementRSA(c,p,q,d) qui déchiffre un message codé c à l'aide de la clef privée p, q, d.
In [18]:
dechiffrementRSA(1864,p,q,859)
Out[18]:
192