Maths-cours

COURS & EXERCICES DE MATHÉMATIQUES

Close

Cryptage RSA - Bac S Centres étrangers 2018 (spé)

Exercice 4 (5 points)

Candidats ayant choisi la spécialité « mathématiques »

Le but de cet exercice est d'envisager une méthode de cryptage à clé publique d'une information numérique, appelée système RSA, en l'honneur des mathématiciens Ronald Rivest, Adi Shamir et Leonard Adleman, qui ont inventé cette méthode de cryptage en 1977 et l'ont publiée en 1978.

Les questions 1 et 2 sont des questions préparatoires, la question 3 aborde le cryptage, la question 4 le décryptage.

  1. Cette question envisage de calculer le reste dans la division euclidienne par 5555 de certaines puissances de l'entier 88.

    1. Vérifier que 872mod558^7 \equiv 2 \mod 55.

      En déduire le reste dans la division euclidienne par 5555 du nombre 8218^{21}.

    2. Vérifier que 829mod558^2 \equiv 9 \mod 55, puis déduire de la question a. le reste dans la division euclidienne par 5555 de 8238^{23}.

  2. Dans cette question, on considère l'équation (E)(E)  23x40y=123 x - 40 y = 1, dont les solutions sont des couples (x ; y)(x~;~y) d'entiers relatifs.

    1. Justifier le fait que l'équation (E)(E) admet au moins un couple solution.

    2. Donner un couple, solution particulière de l'équation (E)(E).

    3. Déterminer tous les couples d'entiers relatifs solutions de l'équation (E)(E).

    4. En déduire qu'il existe un unique entier dd vérifiant les conditions 0d<400 \leqslant d < 40 et 23d1mod4023 d \equiv 1 \mod 40.

  3. Cryptage dans le système RSA

    Une personne A choisit deux nombres premiers pp et qq, puis calcule les produits N=pqN = p q 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)(N~;~c), qui est une clé publique permettant à quiconque de lui envoyer un nombre crypté.

    Les messages sont numérisés et transformés en une suite d'entiers compris entre 00 et N1N - 1.

    Pour crypter un entier aa de cette suite, on procède ainsi : on calcule le reste bb dans la division euclidienne par NN du nombre aca^c, et le nombre crypté est l'entier bb.

    Dans la pratique, cette méthode est sûre si la personne A choisit des nombres premiers pp et qq très grands, s'écrivant avec plusieurs dizaines de chiffres.

    On va l'envisager ici avec des nombres plus simples : p=5p = 5 et q=11q = 11.

    La personne A choisit également c=23c = 23.

    1. Calculer les nombres NN et nn, puis justifier que la valeur de cc vérifie la condition voulue.

    2. Un émetteur souhaite envoyer à la personne A le nombre a=8a = 8.

      Déterminer la valeur du nombre crypté bb.

  4. Décryptage dans le système RSA

    La personne A calcule dans un premier temps l'unique entier naturel dd vérifiant les conditions 0d<n0 \leqslant d < n et cd1modncd \equiv 1 \mod n.

    Elle garde secret ce nombre dd qui lui permet, et à elle seule, de décrypter les nombres qui lui ont été envoyés cryptés avec sa clé publique.

    Pour décrypter un nombre crypté bb, la personne A calcule le reste aa dans la division euclidienne par NN du nombre bdbd, et le nombre en clair -- c'est-à-dire le nombre avant cryptage -- est le nombre aa.

    On admet l'existence et l'unicité de l'entier dd, et le fait que le décryptage fonctionne.

    Les nombres choisis par A sont encore p=5p = 5, q=11q = 11 et c=23c = 23.

    1. Quelle est la valeur de dd ?

    2. En appliquant la règle de décryptage, retrouver le nombre en clair lorsque le nombre crypté est b=17b = 17.