© Copyright Franck CHEVRIER 2019-2022 https://www.python-lycee.com.
Les activités partagées sur Capytale sont sous licence Creative Commons.
Pour exécuter une saisie Python, sélectionner la cellule et valider avec SHIFT+Entrée.
Cette activité propose, sous forme simplifiée, d'étudier le principe du chiffrement RSA.
1. Principe du chiffrement RSA
2. Échanges sécurisés de message
3. Principe d'authentification
4. Compléments arithmétiques
Archibald, chef d'une agence de détectives, souhaite que tous ses associés cryptent les messages qu'ils lui envoient. Il souhaite donc leur donner à tous la même méthode de chiffrement, mais -méfiant- souhaite aussi s'asssurer d'être le seul à pouvoir décoder les messages qui lui parviennent, au cas où un espion intercepterait un de ces messages.
Dans les activités de chiffrement précédentes, la connaissance de la clé de chiffrement permettait directement de déterminer la clé de déchiffrement, ce qui ne convient pas à Archibald.
Pour réaliser son chiffrement, Archibald :
Dans cette partie, on pose $p=11$ ; $q=23$ et $c=9$.
1.1. Vérifier que $p$ ; $q$ et $c$ vérifient bien les contraintes annoncées, et donner les valeurs de $n$ et $m$.
Archibald fournit le couple $(n;c)$ à ses associés, et garde les valeurs $p$ et $q$ secrètes.
Balthazar, un associé d'Archibald, souhaite coder un message à l'aide du couple $(n;c)$, appelé clé publique.
(pour simplifier, on suppose que le message est exclusivement composé d'espaces et de lettres majuscules, sans accents ni caractères spéciaux)
Pour cela, il commence par associer à chaque caractère de son message un entier $x$ compris entre $0$ et $26$ à l'aide du tableau de correspondance ci-dessous.
Ensuite, il associe à la valeur $x$ obtenue la valeur $y$ telle que $0 \leq y \leq n-1$ et $y \equiv x^{\;c} \;[n]$.
A | B | C | D | E | F | G | H | I | J | K | L | M | N | O | P | Q | R | S | T | U | V | W | X | Y | Z | (espace) |
---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|
0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 | 12 | 13 | 14 | 15 | 16 | 17 | 18 | 19 | 20 | 21 | 22 | 23 | 24 | 25 | 26 |
1.2. Balthazar souhaite envoyer le message "BINGO" à Archibald. Quelle succession de nombres va-t-il lui envoyer ?
$\;\;\;\;\;$On pourra utiliser une (des) zone(s) de saisie Python pour effectuer des calculs utiles.
#Utiliser si nécessaire cette zone pour les calculs en Python
1.3. On donne les fonctions Python chiffrage et chiffrement_RSA ci-dessous.
$\quad\;\;$À l'aide d'appels à ces fonctions, vérifier le résultat de la question 1.2.
#Mise en mémoire de l'alphabet (+espace)
Alphabet="ABCDEFGHIJKLMNOPQRSTUVWXYZ "
def chiffrage(message):
"""
Fonction qui renvoie la liste des valeurs correspondantes aux caractères du message
(A->0 , B->1 , ...)
"""
return [ Alphabet.index(caractere) for caractere in message ]
def chiffrement_RSA(n,c,liste_nombres):
"""
Fonction effectuant le codage RSA de la liste de valeurs avec la clé publique (n,c)
"""
code = []
for x in liste_nombres: # pour chaque valeur x de la liste donnée
y = x**c %n # on calcule y correspondant à x
code.append(y) # on complète la liste de valeurs avec y
return code
#Effectuer ici les appels aux fonctions chiffrage et chiffrement_RSA
1.4. Dans cette question, on souhaite effectuer le décodage du message à l'aide du triplet $(p;q;c)$, appelé clé privée.
$\;\;\;\;\;$a. Sans chercher à le déterminer, démontrer qu'il existe un unique entier $d$ tel que $1 \leq d < m$ et $cd \equiv 1 \;[m]$.
$\;\;\;\;\;$b. Déterminer cette valeur $d$ (on pourra commencer par appliquer l'algorithme d'Euclide).
$\;\;\;\;\;$c. À l'aide de saisies en Python, calculer $x^{cd}$ modulo $n$ pour différentes valeurs entières positives de $x$. Que constate-t-on ?
#Effectuer ici les calculs
$\;\;\;\;\;$d. On admet pour l'instant* que l'observation de la question 1.4.b. est correcte pour tout entier positif $x$, et on rappelle que $y$ vérifie $y \equiv x^{\;c} \;[n]$.
$\quad\quad$(*La démonstration mathématique de ce résultat sera détaillé dans la partie 4)
$\quad\quad$Exprimer $x$ en fonction de $y$ modulo $n$.
$\;\;\;\;\;$e. Effectuer le décodage des nombres de la question 1.2 et vérifier qu'on retrouve bien le message "BINGO".
$\;\;\;\;\;\;\;\;$On pourra utiliser une (des) zone(s) de saisie Python pour effectuer des calculs utiles.
#Utiliser si nécessaire cette zone pour les calculs en Python
1.5. On fournit ci-dessous la fonction Python inv qui reçoit en argument m et c, et renvoie d.
$\;\;\;\;\;\;$(NB : Cette fonction est basée sur une recherche de coefficients de Bézout ; elle est étudiée dans l'activité PGCD / Euclide / Bézout)
$\;\;\;\;\;\;$Vérifier que la fonction inv permet de retrouver la réponse à la question 1.5.a.
import numpy as np
def inv(m,c):
"""
Recherche de d, inverse de c modulo m
(passage par les coefficients de Bézout)
"""
a,b=m,c
q = a//b
P = np.array([ [ 0 , 1 ] , [ 1 , -q ] ])
while a%b!=0:
a,b = b,a%b
q = a//b
P = np.dot( np.array([ [ 0 , 1 ] , [ 1 , -q ] ]) , P )
u,v = P[0]
return int(v%m)
#Effectuer ici un appel à la fonction inv
1.6.a. Écrire une fonction Python dechiffre_RSA qui reçoit en argument p, q, c et code (liste de valeurs fournie par la fonction chiffrement_RSA) et qui effectue les instructions suivantes:
#Écrire ici la fonction dechiffre_RSA
$\;\;\;$b. On donne la fonction Python lettrage ci-dessous.
$\quad\;\;$Vérifier que votre fonction dechiffre_RSA et cette fonction lettrage permettent de décoder la liste de valeurs des questions 1.2 et 1.3.
def lettrage(code):
"""
Fonction qui convertit une liste de valeurs (comprises entre 0 et 26) en chaine de caractères
(0->A , 1->B , ...)
"""
message = ""
for y in code:
message += Alphabet[y]
return message
#Effectuer ici un appel à la fonction dechiffre_RSA
#Effectuer ici un appel à la fonction lettrage
$\;\;\;$c. Archibald reçoit ce code de la part de Casper, un autre de ses associés : $36, 5, 145, 36, 43, 0$.
$\;\;\;\;\;\;$Décoder ce message.
#Effectuer ici un appel à la fonction dechiffre_RSA
#Effectuer ici un appel à la fonction lettrage
On reprend dans cette partie les notations de la partie précédente.
2.1. Exécuter la cellule ci-dessous, qui permet de générer deux nombres premiers $p$ et $q$ distincts à 3 chiffres et un nombre entier $c$ tel que $c$ et $m=(p-1)(q-1)$ sont premiers entre eux avec $1<c<m$.
from random import randint
def PGCD(a,b):
"""
Fonction qui calcule le PGCD de a et b
"""
return a if b==0 else PGCD(b,a%b)
def est_premier(n):
"""
Fonction qui détermine si un entier est premier
"""
if n%2==0 or n==1: return False
for k in range(3,int(n**0.5)+1,2):
if n%k==0 : return False
return True
def premier(min=10**2,max=10**3-1):
"""
Fonction qui renvoie un nombre premier aléatoire compris entre min et max
"""
p=0
while not est_premier(p):
p=randint(min,max)
return p
#génération d'un nombre premier p à 3 chiffres
p = premier()
#génération d'un nombre premier q à 3 chiffres, distinct de p
q = p
while q == p : q = premier()
#génération de c premier avec m
m = (p-1)*(q-1)
c = 0
while PGCD(c,m)!=1: c = randint(2,m-1)
p,q,c
2.2. Effectuer les saisies nécessaires pour calculer $n$.
#Effectuer ici les saisies pour le calcul de n
2.3. Fournir à deux personnes B et C votre clé publique $(n,c)$.
$\;\;\;\;\;$B et C vous envoient alors un message codé à l'aide de la fonction chiffrement_RSA.
$\;\;\;\;\;$Décoder ces messages à l'aide de la fonction dechiffre RSA.
Si C interceptait le message codé envoyé par B, pourrait-il le décoder ?...
Pour décoder un message, il est nécessaire de connaître les valeurs de $p$ et $q$, afin de déterminer $m$ puis $d$.
Connaissant $n$, C devrait retrouver la décomposition en facteurs premiers $n=pq$.
La sécurité du code dépend donc de la difficulté à réaliser cette décomposition. Pour de petites valeurs de $n$, il est possible d'automatiser cette recherche avec un temps de calcul relativement court. C'est pourquoi, dans la pratique, les nombres $p$ et $q$ utilisés pour un chiffrement RSA sont des nombres premiers qui comportent plusieurs centaines de chiffres !
Par ailleurs, le chiffrement RSA procède en réalité par codage par blocs et non par caractères.
On reprend dans cette partie les notations des parties précédentes.
Archibald et Balthazar disposent chacun d'une clé publique et d'une clé privée pour le chiffrement RSA.
Archibald souhaite envoyer un message à Balthazar de telle sorte que celui-ci soit certain de l'origine du message.
Mais toutes les personnes qui écrivent à Balthazar utilisent la même clé publique...
Pour l'exemple traité dans cette partie, les clés sont données dans le tableau ci-après :
$\;\;\;$ | Archibald | $\;\;\;$ | Balthazar |
Clé privée | $$ p_A=11 \;;\; q_A=23 \;;\; c_A=9 $$ | $\;\;\;$ | $$ p_B=7 \;;\; q_B=13 \;;\; c_B=5 $$ |
Clé publique | $$n_A=253 \;;\; c_A=9$$ | $\;\;\;$ | $$n_B=91 \;;\; c_B=5$$ |
Supposons qu'Archibald souhaite envoyer le message "VOICI MON MESSAGE IMPORTANT" à Balthazar :
3.1. Dans la cellule ci-dessous, on a créé le message à envoyer, ainsi que le mot d'authentification.
$\quad\;$Utiliser les zones de saisie suivantes pour obtenir les deux listes de valeurs code1 et code2qu'Archibald va envoyer à Balthazar.
message = "VOICI MON MESSAGE IMPORTANT" #message à envoyer
mot_auth = message[:5] #partie du message pour l'authentification (ici le premier mot)
message , mot_auth
#Effectuer ici les saisies nécessaires pour convertir le message et le mot d'authentification en listes de nombres
#(on pourra nommer ces listes l1 et l2)
#Effectuer ici les saisies pour obtenir les listes envoyées par Balthazar
#(on pourra nommer ces listes code1 et code2)
3.2 On se place maintenant du côté de Balthazar, qui souhaite interpréter les deux codes reçus code1 et code2.
$\quad\;$a. Quelles sont les clés qu'il va appliquer à chacun de ces codes pour obtenir les valeurs initiales ?
$\quad\;$b. Effectuer les saisies Python correspondantes, et convertir les résultats en lettres.
#Effectuer les saisies pour interpréter code1 et code2
$\quad\;$c. Qu'est ce qui assure à Balthazar que le message provient bien d'Archibald ?
Théorème : Petit théorème de Fermat.
Soit $x \in \mathbb{N}$. Si $\begin{Bmatrix} p \text{ est un nombre premier} \\ p \text{ ne divise pas } x \end{Bmatrix}$ alors $x^{\;p-1} \equiv 1 \;[p]$.
On reprend dans cette partie les notations de la partie 1, notamment :
Le but de cette partie est de démontrer le résultat qui a été admis dans la question 1.4.c. :
On considère un entier positif $x$ et on souhaite démontrer que $x^{cd} \equiv x \;[n]$.
4.0. a. Justifier qu'il existe un entier $k$ tel que $cd = km+1$.
$\quad\;\;$b. Dresser la liste des diviseurs positifs de $n$ et en déduire les valeurs possibles de $PGCD(x,n)$.
4.1. On suppose dans cette question que $PGCD(x,n)=1$, c'est à dire que $x$ et $n$ sont premiers entre eux.
$\quad\;$a. Justifier que $x^{(p-1)(q-1)} \equiv 1 \;[p]$ et que $x^{(p-1)(q-1)} \equiv 1 \;[q]$.
$\quad\;$b. En déduire que $pq$ divise $x^{(p-1)(q-1)}-1$, et donc que $x^m \equiv 1 \;[n]$.
$\quad\;$c. À l'aide des questions 4.0.a et 4.1.b, démontrer que $x^{cd} \equiv x \;[n]$.
4.2. On suppose dans cette question que $PGCD(x,n)=pq$.
$\quad\;\;$Justifier que, dans ce cas, $x \equiv 0 \;[n]$ puis que $x^{cd} \equiv x \;[n]$.
4.3. On suppose dans cette question que $PGCD(x,n)=p$.
$\quad\;\;$a. Justifier que $p$ est un diviseur de $x^{cd}-x$.
$\quad\;\;$b. Démontrer que $x^{cd} = (x^{q-1})^{k(p-1)}x$.
$\quad\;\;$c. Justifier que $x^{q-1} \equiv 1 \;[q]$.
$\quad\;\;$d. Déduire des questions 4.3.b. et 4.3.c que $x^{cd} \equiv x \;[q]$, c'est à dire que $q$ est un diviseur de $x^{cd}-x$
$\quad\;\;$e. À l'aide des questions 4.3.a. et 4.3.d, justifier que $x^{cd} \equiv x \;[n]$.
4.4. Conclure.
Remarque : Le résultat de la question 4.1.b est un cas particulier du théorème d'Euler en arithmétique modulaire, qui est une généralisation du petit théorème de Fermat.
© Copyright Franck CHEVRIER 2019-2022 https://www.python-lycee.com.
Les activités partagées sur Capytale sont sous licence Creative Commons.
Remerciements particuliers à Nicolas EHRSAM pour sa précieuse collaboration.
Dernière modification de l'activité : Juillet 2022