(C) Copyright Franck CHEVRIER 2019-2020 http://www.python-lycee.com/
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
[ k**9 %253 for k in [1,8,13,6,14] ]
[1, 216, 72, 200, 136]
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
liste = chiffrage("BINGO")
chiffrement_RSA(253,9,liste)
[1, 216, 72, 200, 136]
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).
On a $m=(p-1)(q-1)=10\times22=220$ et $c=9$.Algorithme d'Euclide | Recherche des coefficients de Bézout |
$220 = 9 \times 24 + 4$ | $4 = 220 - 9 \times 24 = m - 24c$ |
$9 = 4 \times 2 +1$ | $1 = 9 - 4 \times 2 = c - (m-24c) \times 2 = -2m+49c$ |
$4 = 4 \times 1 +0$ |
$\;\;\;\;\;$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
c = 9
d = 49
n = 253
[ x**(c*d) %n for x in [13,50,77,80] ] #tests pour diverses valeurs de x
[13, 50, 77, 80]
$\;\;\;\;\;$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
c = 9
d = 49
n = 253
[y**d %n for y in [1, 216, 72, 200, 136] ]
[1, 8, 13, 6, 14]
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
p = 11 ; q = 23
m = (p-1)*(q-1) ; c = 9
d = inv(m,c)
d
49
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
def dechiffre_RSA(p,q,c,code):
"""
Fonction effectuant le décodage RSA du code à partir des nombres premiers p et q
"""
n = p*q #calcul de n
m = (p-1)*(q-1) #calcul de m
d = inv(m,c) #calcul de d
return [y**d %n for y in code] #renvoie la liste des valeurs correspondantes aux valeurs y du code
$\;\;\;$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
liste = dechiffre_RSA(11,23,9,[1, 216, 72, 200, 136])
liste
[1, 8, 13, 6, 14]
#Effectuer ici un appel à la fonction lettrage
lettrage(liste)
'BINGO'
$\;\;\;$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
liste=dechiffre_RSA(11,23,9,[36, 5, 145, 36, 43, 0])
liste
[4, 20, 17, 4, 10, 0]
#Effectuer ici un appel à la fonction lettrage
lettrage(liste)
'EUREKA'
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
(607, 151, 78391)
2.2. Effectuer les saisies nécessaires pour calculer $n$.
#Effectuer ici les saisies pour le calcul de n
n = p*q
n
91657
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.
#Saisies effectuées par B pour générer son message codé
message_de_B="SALUT"
code=chiffrement_RSA(n,c,chiffrage(message_de_B))
code
[73240, 0, 86762, 15374, 75670]
#Saisies effectuées pour décoder le message
lettrage(dechiffre_RSA(p,q,c,code))
'SALUT'
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
('VOICI MON MESSAGE IMPORTANT', 'VOICI')
#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)
l1 = chiffrage(message)
l2 = chiffrage(mot_auth)
l1 , l2
([21, 14, 8, 2, 8, 26, 12, 14, 13, 26, 12, 4, 18, 18, 0, 6, 4, 26, 8, 12, 15, 14, 17, 19, 0, 13, 19], [21, 14, 8, 2, 8])
#Effectuer ici les saisies pour obtenir les listes envoyées par Balthazar
#(on pourra nommer ces listes code1 et code2)
code1 = chiffrement_RSA(91,5,l1) #codage du message à l'aide de la clé publique de Balthazar
code2 = dechiffre_RSA(11,23,9,l2) #codage du mot d'authentification à l'aide de la clé privée d'Archibald
code1 , code2
([21, 14, 8, 32, 8, 52, 38, 14, 13, 52, 38, 23, 44, 44, 0, 41, 23, 52, 8, 38, 71, 14, 75, 80, 0, 13, 80], [175, 15, 62, 193, 62])
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
lettrage(dechiffre_RSA(7,13,5,code1)) , lettrage(chiffrement_RSA(253,9,code2))
('VOICI MON MESSAGE IMPORTANT', 'VOICI')
$\quad\;$c. Qu'est ce qui assure à Balthazar que le message provient bien d'Archibald ?
Seul Archibald a pu déterminer la liste de valeurs code2 qui redonne le mot d'authentification "VOICI" quand on lui applique sa clé publique.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)$.
Nous allons maintenant procéder à la démonstration par disjonction des cas.
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]$.
Comme $x^m \equiv 1 [n]$, on en déduit en élevant à la puissance $k$ que $(x^m)^k \equiv 1 [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]$.
$x^{cd} \equiv x \;[q]$ donne $x^{cd}-x \equiv 0 \;[q]$, ce qui prouve que $q$ divise $x^{cd}-x$. On a finalement démontré que $p$ et $q$ sont deux facteurs premiers distincts de la décomposition de $x^{cd}-x$ en produit de facteurs premiers.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.
(C) Copyright Franck CHEVRIER 2019-2020 http://www.python-lycee.com/
Remerciements particuliers à Nicolas EHRSAM pour sa précieuse collaboration.