Exercice corrigé Ancien programme

codage par chiffrement rsa

Partie A

Soit p et q deux nombres premiers et m un entier premier avec p et q.

1. Sachant que (modulo p) et que (modulo q) ( petit théorème de Fermat), montrer que (modulo pq).

2. Soit e un entier premier avec Démontrer qu'il existe un entier d tel que (modulo ) .

3. Démontrer que (modulo pq).

Partie B. Mise en œuvre

RSA repose sur le fait qu'il est très difficile de décomposer un entier en facteurs premiers lorsqu'il est grand (plusieurs centaines de chiffres).

Antoine veut envoyer un message codé à Christophe que lui seul pourra lire : Christophe choisit deux nombres premiers p et q, et un entier e premier avec Il rend public les nombres et e.

Antoine, qui a codé son message alphabétique en un équivalent numérique m, envoie à Christophe le nombre c égal au reste de la division de me par n.

Christophe décode le message en déterminant d tel que :

(modulo ).

(Lui seul peut le faire car il est le seul à connaître p et q).

Christophe rend public les nombres Antoine veut lui envoyer
le message « RDV À UNE HEURE ». Il commence par numéroter chaque lettre :
A correspond à 00, B à 01, . . . , Z à 25 et code le nombre obtenu par bloc de 3 chiffres.

1. Déterminer le message codé que reçoit Christophe.

2. Christophe veut décoder le message reçu ( et ).

a. À l'aide de l'algorithme d'Euclide, déterminer d tel que :

(modulo ).

b. Retrouver le message envoyé par Antoine.

Partie A.

1. (modulo p) et (modulo q).

Donc p et q divisent , et puisque, alors p et q apparaissent

dans la décomposition en facteurs premiers de. Donc pq divise , d'où (modulo pq).

2. Comme e est un entier premier avec, alors, d'après le théorème

de Bézout (1), il existe un couple tel que .

D'où

3. D'après la question 2. :

(modulo pq)

(modulo pq)

(modulo pq) d'après la question 1.b.

Partie B.

1. En numérotant les lettres, le message RDVAUNEHEURE devient :

170321002013040704201704

On dresse le tableau suivant :

x

170

321

002

013

040

704

201

704

x7 (modulo 1 037)

170

76

128

684

82

709

669

709

Le message reçu est 170076128684082709669709.

2. .

a. À l'aide de l'algorithme d'Euclide, on trouve que,

donc d'où .

On choisit ainsi.

b. (modulo 1 037), donc :

(modulo 1 037).

À l'aide d'une calculatrice et après de longs calculs, on trouve que :

(modulo 1 037),

(modulo 1 037),

(modulo 1 037),

(modulo 1 037),

(modulo 1 037),

et (modulo 1 037).

Le nombre obtenu 170321002013040704201704 permet bien de retrouver le message d'origine.

Accéder à tous les contenus
dès 6,79€/mois

  • Les dernières annales corrigées et expliquées
  • Des fiches de cours et cours vidéo/audio
  • Des conseils et méthodes pour réussir ses examens
  • Pas de publicités
S'abonner