Mathématiques · term

Cryptographie et arithmétique modulaire

Ce que tu dois retenir

Chapitre 1 — Congruences : compter en cycles

Deux nombres sont congrus modulo n s'ils diffèrent d'un multiple de n.

Chapitre 2 — Addition, multiplication et puissances

On peut additionner, multiplier et élever à une puissance en réduisant modulo n à chaque étape.

Chapitre 3 — Chiffrement affine : y ≡ ax + b [26]

Le décodage repose sur l'inverse modulaire de a modulo 26.

Chapitre 4 — L'idée du RSA : grands nombres premiers

La sécurité du RSA vient de la difficulté pratique de factoriser n en p×q.

Teste-toi

1. Que signifie a ≡ b [n] ?

AA. a et b ont le même quotient dans la division par n
BB. a et b ont le même reste dans la division par n
CC. a divise b
DD. n divise a et b
Voir la réponse

Réponse : B — B. a et b ont le même reste dans la division par n

La congruence modulo n signifie que les deux nombres ont le même reste dans la division euclidienne par n, donc n divise leur différence.

2. Quel est le reste de 2024 dans la division par 7 ?

AA. 0
BB. 1
CC. 2
DD. 3
Voir la réponse

Réponse : B — B. 1

2024 = 7×289 + 1, donc le reste est 1.

3. Si a ≡ 3 [5] et b ≡ 4 [5], alors a×b ≡ ? [5]

AA. 0
BB. 1
CC. 2
DD. 3
Voir la réponse

Réponse : C — C. 2

3×4 = 12, et 12 ≡ 2 [5] car 12 = 2×5 + 2.

4. Quel est l'inverse de 3 modulo 7 ?

AA. 2
BB. 3
CC. 4
DD. 5
Voir la réponse

Réponse : D — D. 5

3×5 = 15 = 2×7 + 1, donc 5 est l'inverse de 3 modulo 7.

5. Dans le chiffrement affine y ≡ 3x+2 [26], quelle est la lettre codée pour x=0 (A) ?

AA. A
BB. B
CC. C
DD. D
Voir la réponse

Réponse : C — C. C

y = 3×0 + 2 = 2, et avec A=0, B=1, C=2, la lettre est C.

6. Pour que le chiffrement affine y ≡ ax+b [26] soit décodable, il faut que :

AA. a soit pair
BB. a et 26 soient premiers entre eux
CC. b soit premier
DD. a > 26
Voir la réponse

Réponse : B — B. a et 26 soient premiers entre eux

L'inverse de a modulo 26 n'existe que si PGCD(a,26)=1, c'est-à-dire si a et 26 sont premiers entre eux.

7. Dans RSA, la clé publique contient :

AA. p et q
BB. n et e
CC. φ(n) et d
DD. p et d
Voir la réponse

Réponse : B — B. n et e

La clé publique RSA est le couple (n, e) ; p, q, φ(n) et d restent secrets.

8. Pourquoi le RSA est-il considéré comme sûr ?

AA. Parce que les ordinateurs ne savent pas multiplier
BB. Parce que factoriser un grand nombre en produit de deux nombres premiers est très difficile
CC. Parce que les messages sont envoyés en morse
DD. Parce que la clé publique est secrète
Voir la réponse

Réponse : B — B. Parce que factoriser un grand nombre en produit de deux nombres premiers est très difficile

La sécurité repose sur la difficulté pratique de factoriser n = p×q lorsque p et q sont de très grands nombres premiers.

Retour au cours ruedusavoir.com · Apprendre, c'est avancer.