Cryptographie et arithmétique modulaire
Fiche de révision · Mathématiques · Term
L'essentiel du cours
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 · 8 questions
1.Que signifie a ≡ b [n] ?
Voir la réponseMasquer la réponse
Réponse : 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 ?
Voir la réponseMasquer la réponse
Réponse : 1
2024 = 7×289 + 1, donc le reste est 1.
3.Si a ≡ 3 [5] et b ≡ 4 [5], alors a×b ≡ ? [5]
Voir la réponseMasquer la réponse
Réponse : 2
3×4 = 12, et 12 ≡ 2 [5] car 12 = 2×5 + 2.
4.Quel est l'inverse de 3 modulo 7 ?
Voir la réponseMasquer la réponse
Réponse : 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) ?
Voir la réponseMasquer la réponse
Réponse : 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 :
- A.b soit premier
- B.a > 26
- C.a et 26 soient premiers entre eux
- D.a soit pair
Voir la réponseMasquer la réponse
Réponse C : 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 :
- A.p et d
- B.p et q
- C.φ(n) et d
- D.n et e
Voir la réponseMasquer la réponse
Réponse D : 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 ?
Voir la réponseMasquer la réponse
Réponse : 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.