Chargement de l'audio en cours
Plus

Plus

TP2. Système cryptographique RSA
P.155

Mode édition
Ajouter

Ajouter

Terminer

Terminer

TP INFO


2
Système cryptographique RSA




Énoncé

Une personne A cherche à recevoir des messages de manière sécurisée et une personne B cherche à lui en envoyer.
Les messages sont numérisés et transformés en une suite d’entiers. L’objectif est donc de transmettre des entiers sans que quiconque, autre que la personne A, puisse les décrypter.
Pour cela, la personne A choisit deux nombres premiers pp et qq puis calcule les produits N=pq\mathrm{N}=pq et n=(p1)(q1)n=(p-1)(q-1).
Elle choisit également un entier naturel cc premier avec nn. La personne A publie le couple (N ; c)(\mathrm{N} ; c), appelé clé publique, permettant à quiconque de lui envoyer un nombre crypté.
  • Pour crypter un entier aa compris entre 00 et N1\mathrm{N}-1, la personne B calcule le reste bb dans la division euclidienne de aca^c par N\mathrm{N}. Le nombre crypté qu’elle envoie à la personne A est b.b.
  • Pour décrypter le message, la personne A commence par calculer l’unique entier dd compris entre 00 et n1n-1 tel que cd1[n]c d \equiv 1[n]. Il est alors possible de montrer que cet entier dd vérifie bda[N]b^{d} \equiv a[\mathrm{N}], ce qui permet donc à la personne A de retrouver le nombre aa.

Question préliminaire :

Pourquoi la personne A est‑elle, en pratique, la seule capable de calculer l’entier dd et de déchiffrer les messages ?
Voir les réponses

Objectif

Mettre en œuvre l’algorithme de cryptage et de décryptage du système RSA dans le cas où p=5\boldsymbol{p=5}, q=11\boldsymbol{q=11} (c’est‑à‑dire N=55\boldsymbol{\mathrm{N}=55} et n=40\boldsymbol{n=40}) et c=23\boldsymbol{c=23}, à l’aide d’une des deux méthodes.
MÉTHODE DE RÉSOLUTION 1
TABLEUR

1. La personne B veut crypter le nombre a=3a=3.
Réaliser une feuille de calcul comme ci‑dessous afin de calculer l’entier bb dans la cellule D2. (Fichier téléchargeable ici.)

maths expertes - chapitre 5 - Nombres premiers - TP2. Système cryptographique RSA - méthode 1

Quelle est la valeur de l’entier bb que la personne B doit transmettre à la personne A ?


2. a. À l’aide d’une feuille de calcul, calculer toutes les valeurs de c×dc \times d, pour dd compris entre 00 et n1n-1.
Vérifier que l’entier dd, que doit calculer la personne A, est égal à 77. ici.)


b. Réaliser la feuille de calcul suivante donnant la liste des valeurs de bdb^d modulo N\mathrm{N}, en faisant dérouler la formule écrite en C2.

maths expertes - chapitre 5 - Nombres premiers - TP2. Système cryptographique RSA - méthode 1

Vérifier que la personne A va bien retrouver la valeur de aa, si elle reçoit la valeur bb transmise par la personne B dans la question 1..
Voir les réponses
MÉTHODE DE RÉSOLUTION 2
PYTHON

1. Écrire en Python une fonction cryptage, prenant en argument a, N et c et permettant à B de trouver l’entier bb. Faire un test avec a=8a=8.



2. Pour déchiffrer le message, la personne A doit déterminer l’entier dd, compris entre 00 et n1n-1, tel que cd1[n]c d \equiv 1[n]. Elle écrit le programme ci‑dessous.

def chercher_exposant(c, n):
	F = 0
	d = 0
	while ... :
		d = d + 1
		F = c*d % n
	return(d)

a. Expliquer chaque ligne du programme puis compléter la ligne 4.


b. Déterminer l’entier dd pour c=23c=23 et n=40n=40.


c. Quelle méthode plus efficace pourrait‑on utiliser pour déterminer dd ?


3. Écrire une fonction en langage Python ayant pour arguments b, d et N et retournant l’entier a.



Voir les réponses

Pour aller plus loin


Voir exercice
77
p. 162
.
Utilisation des cookies
En poursuivant votre navigation sans modifier vos paramètres, vous acceptez l'utilisation des cookies permettant le bon fonctionnement du service.
Pour plus d’informations, cliquez ici.