Chiffrement RSA

Chiffrement RSA

algebra

On commence par récapituler toute l’arithmétique des entiers, connue depuis la L1, et sans faire appel à la théorie des groupes. On détaille ensuite un exemple pratique de chiffrement RSA, et on explique les mathématiques se trouvant derrière à l’aide de la première partie.

Arithmétique dans

Divisibilité dans

Définition 1. Soient et deux entiers relatifs. On dit que divise (ou que est un multiple de ) s’il existe tel que . On note ceci par .

Exemple 2.

  • donc et sont des diviseurs de . Les diviseurs dans de sont : , , et .

  • donc , , et sont des diviseurs de . Les diviseurs dans de sont : , , , , , , , , , , et .

Proposition 3.

  1. Tout entier relatif divise (car ).

  2. divise tout entier relatif (car ).

  3. Si et alors pour tout , .

Démonstration. Montrons le dernier point : il existe , tels que et . Donc . D’où . ◻

Définition 4. Un nombre entier est dit premier si ses seuls diviseurs positifs sont et lui-même.

Exemple 5. , , , , et sont des nombres premiers et il en existe une infinité.

Division euclidienne

Théorème 6 (Division euclidienne dans ). Soient et . On appelle division euclidienne de par , l’opération qui à , associe le couple d’entiers tel que . Un tel couple existe forcément et est unique.

Démonstration. Si , alors il suffit de prendre et . Nous supposerons donc dans la suite .

  • Existence : On note l’ensemble des entiers naturels qui s’écrivent . Cet ensemble est non vide (car il contient ) et comme c’est un sous-ensemble de , il admet un plus petit élément . On a forcément (sinon serait dans et serait plus petit que ). Donc et ce couple vérifie les conditions données par le théorème.

  • Unicité : On suppose qu’il existe un deuxième couple vérifiant les conditions du théorème. On a , donc . Comme alors . De plus , donc en additionnant les inégalités on a . Comme on a (i.e. ) et donc . D’où .

 ◻

Définition 7. En reprenant les notations du théorème, s’appelle le dividende, le diviseur, le quotient et le reste de la division euclidienne.

Remarque 8. Il est possible d’étendre le principe de la division euclidienne aux entiers relatifs. La condition pour le reste devient alors .

Exemple 9. On souhaite effectuer la division euclidienne de par . Détaillons étape par étape :

  • On cherche combien de fois est contenu dans (cela ne sert à rien de commencer par car ). On a et donc, on écrit sous le diviseur et le reste . Puis, on abaisse le chiffre des unités qui est .

  • On recommence : combien de fois est-il contenu dans ? Comme et , est contenu fois dans et il reste .

  • Comme , la division euclidienne est terminée : on a .

Donnons, pour finir, une propriété qui nous sera utile dans la sous-section suivante.

Proposition 10. Soit . Deux entiers relatifs et ont le même reste dans la division euclidienne par si et seulement si est un multiple de .

Démonstration. Supposons que et ont le même reste dans la division euclidienne par i.e. et . Alors par différence, donc est un multiple de .

Réciproquement, si est un multiple de alors il existe tel que . En effectuant la division euclidienne de par , on a , d’où . Ainsi, avec , ce que l’on voulait. ◻

Voici également un énoncé qui sera utilisé par la suite. C’est un corollaire du théorème de théorème de Bézout.

Proposition 11 (Corollaire du théorème de Bézout). Soient et deux entiers naturels non nuls premiers entre eux. Alors, il existe , tels que .

Démonstration. On note par l’ensemble des entiers naturels strictement positifs qui s’écrivent , . Cet ensemble est non-vide (car il contient ) et comme c’est un sous-ensemble de , il admet un plus petit élément .

  • On a (car et ) donc .

  • Faisons la division euclidienne de par : on a donc (car sinon on aurait mais et est le plus petit élément de ). Donc divise et par le même raisonnement, divise . Donc divise leur plus grand diviseur commun positif qui est . Donc .

D’où finalement . ◻

Remarque 12. Il est possible de trouver de tels entiers et en effectuant la division euclidienne de par , puis de par le reste de la division précédente, etc…et en remontant. Il s’agit de la remontée de l’algorithme d’Euclide.

Corollaire 13. Soient et deux entiers naturels non nuls premiers entre eux. Soit tel que et . Alors .

Démonstration. On écrit et . De plus, par le Proposition 11, il existe et tels que . En multipliant l’égalité par , on obtient . D’où le résultat. ◻

Lemme 14 (Euclide). Soit un nombre premier et et deux entiers. Si alors ou .

Démonstration. Soit un nombre premier tel que . Supposons que ne divise pas . Alors comme est premier, ses seuls diviseurs sont et . Comme n’est pas divisible par , le plus grand diviseur commun positif à et est . Donc par le Proposition 11 il existe , tels que . En multipliant par on obtient . Ainsi . ◻

Congruences dans

Dans toute cette sous-section, on fixe un entier naturel .

Définition 15. On dit que deux entiers relatifs et sont congrus modulo si et ont le même reste dans la division euclidienne par . On note alors .

Remarque 16. On remarque que est un multiple de si et seulement si .

On signale que la congruence est une relation d’équivalence.

Proposition 17. Pour tout , , :

  1. (réflexivité)

  2. Si , alors (symétrie)

  3. Si , et si , alors (transitivité)

De plus, le congruence est compatible avec les opérations usuelles sur les entiers relatifs.

Théorème 18. Soient , , et tels que et . Alors on a la compatibilité avec :

  1. L’addition : .

  2. La multiplication : .

  3. Les puissances : pour tout , .

Démonstration.

  1. Comme , et , alors et sont des multiples de . Donc il existe deux entiers relatifs et tels que et . En additionnant ces deux égalités on trouve que . Donc par la Remarque 16, .

  2. Comme précédemment, on a et . En multipliant les deux égalités on trouve que . Donc par la Remarque 16, .

  3. On utilise la compatibilité avec la multiplication : et donc . De même, on a . Il suffit de répéter l’opération fois et on a .

 ◻

Exemple 19. Comme , et , on a .

Nous utiliserons le résultat suivant dans la sous-section suivante.

Théorème 20 (Petit théorème de Fermat). Soit un nombre premier et un entier quelconque. Alors .

Démonstration. Soit un nombre premier et soit tel que ne divise pas . Notons :

  • .

  • le reste de la division euclidienne de par pour tout tel que .

  • .

Montrons que . Il suffit en fait de réordonner les facteurs de : De plus, est le reste de la division euclidienne de par donc . Par , . , donc ne peut pas être divisible par . Ainsi, par le Lemme 14, n’est pas divisible par et donc .

Soit tel que et . Montrons que est divisible par . Comme et sont respectivement le reste de la division euclidienne de et par , on a donc est divisible par . Comme ne divise pas , par le Lemme 14, on a divise . Et comme , on en déduit que .

Pour tout , on a . De plus, par ce qui précède, on a qui sont tous différents les uns des autres. Donc Ainsi, .

Enfin, on a et , donc, on a . De par la définition des congruences modulo , on a divisible par et . Comme divise mais que pour tout tel que , ne divise pas , alors, en appliquant le Lemme 14 à chaque facteur de , il en résulte que divise .

Pour conclure, comme alors et donc . Nous venons de montrer que pour tout non divisible par , on a . Soit maintenant un entier divisible par . Alors et donc . D’où . ◻

Exemple 21. Cherchons le reste de la division euclidienne de par .

Posons et . En faisant la division euclidienne de par , on a donc . Donc .

RSA par un exemple

Calcul de le clé publique et de la clé privée

Alice souhaite envoyer un code à Bob et uniquement à lui à travers un groupe de messagerie. Pour éviter de communiquer son code à tous les autres membres du groupe de messagerie, ils cherchent donc un moyen pour que seul Bob soit capable de le lire et de le déchiffrer : ils vont employer la méthode de chiffrement RSA.

Ce chiffrement se base sur le choix de deux nombres premiers et distincts. On pose alors et , puis on choisit premier avec .

Définition 22. Le couple est la clé publique de ce chiffrement et est utilisée pour chiffrer des nombres, des caractères, des mots, ...

Pour déchiffrer un nombre, on détermine deux entiers et vérifiant (ils existent par le Proposition 11). On pose comme le reste de la division euclidienne de par .

Définition 23. Le triplet est la clé privée du chiffrement.

Dans notre exemple, c’est Bob qui va générer la clé publique et la clé privée. Ainsi, il choisit , (donc et ) et . Comme , alors .

Il communique sa clé publique (qui est ) dans la conversation et garde bien précieusement sa clé privée (qui est ).

Chiffrement du code

Le code d’Alice est , elle le décompose en chacun de ses chiffres : , , et . Pour tout , elle calcule ensuite qui est le reste de la division euclidienne de par . Ainsi, elle obtient :

Par conséquent, elle écrit dans la conversation :

À titre d’exemple, pour calculer , il s’agit de calculer le reste de la division euclidienne de par . On peut, par exemple, procéder comme ceci :

Déchiffrement du code

Bob a donc reçu, une suite de quatre nombres avec , , et . Pour déchiffrer la suite en une suite , il s’agit alors pour tout , de calculer le reste de la division euclidienne de par . Ce reste est . Ainsi, dans le cadre de notre exemple, cela nous donne :

Le code déchiffré est donc :

Ce qui correspond bien au code qu’Alice a voulu transmettre. De plus, seul Bob connaît le nombre qui permet de déchiffrer le code. Leur objectif est donc atteint.

L’algorithme RSA est dit asymétrique car pour chiffrer un message, il suffit de connaître la clé publique . Cependant, pour déchiffrer un message, il faut connaître et . Or, se calcule à partir de et en trouvant les nombres premiers et qui divisent . Donc finalement, pour déchiffrer un message, il faut connaître la clé privée .

Dans cet exemple, les nombres et ont été choisis petits de manière à simplifier les calculs, mais si on souhaitait mettre en place cet algorithme de chiffrement dans un cadre plus sécuritaire, il faudrait ainsi choisir des nombres et beaucoup plus grands.

Le chiffrement demande donc de pouvoir vérifier que de très grands nombres sont des nombres premiers, pour pouvoir trouver et , mais aussi que le produit de ces deux très grands nombres, ne soit pas factorisable pratiquement. En effet les algorithmes efficaces connus qui permettent de vérifier qu’un nombre n’est pas premier ne fournissent pas de factorisation.

tikzpicture-1

Explication mathématique

Soient et des nombres premiers distincts.

Notation 24. On note et .

Prouvons tout d’abord l’existence de la clé publique ainsi que l’existence de la clé privée.

Proposition 25. Soit un entier premier avec soit . Alors il existe tel que .

Démonstration. En effet, par le Proposition 11, il existe et tels que . Donc, on a et ainsi . Il suffit alors de poser le reste de la division euclidienne de par . ◻

Montrons enfin que ce chiffrement est valide.

Proposition 26. Soit un entier naturel strictement inférieur à que nous souhaitons (dé-)chiffrer. On pose le reste de la division euclidienne de par . Alors, .

Démonstration. On a et donc il existe tel que . Comme et sont deux nombres premiers, alors par le Théorème 20, on a et . Donc . En faisant le même raisonnement, on a . Ainsi, est un multiple de et de (deux premiers distincts), donc aussi de par le Corollaire 13. On conclue que . ◻