L'algorithme RSA

Mis à jour le jeudi 10 janvier 2013
RSA

Explication Mathématique

Bonjour à toutes et à tous !

Ce chapitre va aborder des points mathématiques importants pour bien comprendre le cryptage RSA.

Tout d'abord nous allons voir la division euclidienne, ce qui va nous permettre de définir les congruences. Ensuite nous verrons les nombres premiers qui sont la base du cryptage RSA puisque ce sont deux nombres premiers que nous avions appelés p et q qui nous permettront de calculer n. Ensuite pour le décryptage, vous aurez besoin de factoriser n. Nous verrons donc la factorisation.

Évidemment, on est sur le www.siteduzero.com, je vais donc tout vous expliquer depuis le début (faut juste savoir un peu compter, multiplier, soustraire, additionner ; et encore ça sera souvent des programmes qui feront ça à notre place :D ), donc il n'y a pas vraiment de pré-requis spécifiques.

Vous êtes fort, grand, beau, intelligent, prêt ? Let's go.

La division euclidienne

Tout d'abord, avant de nous lancer dans les congruences, nous allons définir et expliquer la division euclidienne, dont on a grandement besoin de comprendre le fonctionnement pour attaquer la suite.

Un exemple pour une première approche

Nous allons commencer tout doucement ce tuto avec les divisions comme on les faisait en... CM2, c'est-à-dire avec uniquement des nombres entiers positifs. Qui a dit que ce tuto était réservé à une élite de mathématiciens ayant au moins un Bac + 5 ? :-°

Bien, nous allons donc prendre un exemple: diviser 1489 par 17, et sans calculatrice s'il vous plaît :

Image utilisateur

Mouais et c'est quoi ce truc moche ?

C'est sûr, c'est pas avec ça que vous allez inventer la poudre (quoique... ;) ), mais c'est déjà un début, alors qu'est-ce que j'ai fait là ?
Je suis parti de 1489, et j'ai vu qu'en mettant 80*17 je trouvais 1360, je soustrais donc 1360 à 1489, et il ne me reste plus que 129, or je remarque que 7*17=119, je prends donc le 129 auquel je soustrais 119, et je trouve 10.

Vous remarquez qu'à aucun moment je n'ai fait une soustraction de telle sorte que je me retrouve avec un reste négatif : il faut toujours avoir des nombres positifs, c'est important. Si jamais vous dépassez (par exemple 100*17 est plus grand que 1489), diminuez le 100, essayez avec 90, "Ha mince c'est encore trop grand", jusqu'à ce que vous trouviez le 80. Ensuite, une fois que vous avez le bon chiffre avec les dizaines, vous passez aux unités, pour trouver de la même manière un 7.

Bon, je me retrouve donc avec un 10 à la fin de ma division euclidienne.
Et là je fais quoi ? Ben rien, je laisse tel quel, "pourquoi donc?" me direz-vous.
Tout simplement parce que 10 est plus petit que 17 et que donc on ne peut plus continuer tel quel car, comme je vous l'ai dit plus haut, nous n'utilisons que des nombres entiers positifs.

Nous avons donc fait ce que nous appellerons à partir de maintenant la division euclidienne de 1489 par 17, nous avons trouvé comme quotient 87 et comme reste 10.
Nous remarquons que nous pouvons toujours retrouver 1489, en effet 17*87 +10 = 1489.

Une définition de la division euclidienne

Nous pouvons définir la division euclidienne de a par n telle que :
a=nq+r

Plusieurs remarques s'imposent :

  • a, n, q et r sont des entiers et nous n'emploierons dans le domaine de la cryptologie (et donc dans ce chapitre) que des entiers positifs (appelés encore entiers naturels).

  • Il faut absolument que r < n ; sinon, si r > n cela veut dire que nous n'avons pas fini la division. Un peu comme si j'avais dit que le reste dans l'exemple précédent était 129 au lieu de 10.
    Il faut aussi que r soit plus grand ou égal à 0. Si r est négatif, c'est que nous sommes allés trop loin.

  • Si vous effectuez la division euclidienne de a par n et que vous respectez les deux points ci-dessus, vous devez obtenir un (l'existence) et un seul (l'unicité) couple : q et r, qui sont respectivement le quotient et le reste de la division euclidienne de a par n.
    La démonstration n'est pas très utile à comprendre mais je la met pour la culture générale :

    On a a \geq b, on note E=\{ n \in \mathbb{N} \, tel \, que \, b \, divise \, n \, et \, n \geq a \}

  • Pour votre culture générale, on appelle a le dividende et n le diviseur ; si vous ne retenez pas cela, ce n'est pas très grave.

  • Lorsque le reste r est nul, alors a=nq : on dit que n divise a ou que a est un multiple de n.

Le PGCD

Avant de se lancer tête baissée dans l'abstrait, je vais vous donner un exemple pour essayer de vous faire comprendre la notion de PGCD :

Pierre et Marie (Curie) :D travaillent tous les deux dans la même entreprise et sont amis. Pierre travaille 8 heures par jours et Marie 6 heures. Le matin, ils commencent à travailler en même temps à 8 heures.
Sachant que Pierre et Marie ont le droit de faire des pauses pour aller boire un café toutes les X heures avec (X un nombre entier et qui doit être le même pour tous les deux fixés par tous les deux), sachant que leur première pause peut être faite après au moins une heure de travail, que leur dernière heure de travail doit aboutir à une dernière pause et qu'il n'y a pas de d'arrêt de travail pour le repas du midi (bouuhh le méchant patron qui laisse pas ses employés manger).
Seulement il n'y pas longtemps, Pierre et Marie se sont brouillés. Depuis ils s'évitent.

Combien de fois Pierre et Marie peuvent-ils au minimum se supporter se voir à la machine à café ? Et quelle sera alors la valeur de X ?

Allons-y avec de la méthode, on sait que Pierre travaille 8 heures par jour et qu'il faut qu'il fasse des pauses toutes les X heures et que sa dernière heure de travail doit aboutir à une pause, donc 8=Xn, n étant le nombre de pauses que Pierre fera ; de même Marie travaille 6 heures donc 6=Xn' avec n' le nombre de pauses que fera Marie.
Donc X divise 6 et 8 (en effet le reste est nul et n est un nombre entier).
Les diviseurs de 6 sont : 1, 2, 3, 6
Les diviseurs de 8 sont : 1, 2, 4, 8
Il faut donc prendre ce qui est en commun aux deux listes de diviseurs, c'est-à-dire que X peut valoir 1 ou 2.
C'est-à-dire : soit ils font une pause toutes les heures, et dans ce cas Pierre va faire 8 pauses, et Marie 6, auquel cas ils se verront 6 fois ; soit ils font une pause toutes les deux heures et dans ce cas Pierre va faire 4 pauses et Marie trois, dans ce cas ils se verront trois fois.
Comme ils sont brouillés, ils vont prendre la deuxième option, puisque c'est là qu'ils se verront le moins.
Mais la valeur de X sera 2, donc la plus grande des valeurs que pouvait prendre X.

X divise 8 et 6. Quand X=2, X est le plus grand diviseur commun de 8 et 6 : on dit donc que X est le PGCD (8, 6) (PGCD = Plus Grand Commun Diviseur. L'inversion entre commun et diviseur est volontaire ; en effet, pour la petite histoire, sachez que les Anglais appellent ça le GCD (Greatest common divisor), comme ça ils comprennent notre "PGCD" :lol: ).

Si vous prenez deux nombres entiers positifs quelconques, ils ont au moins un diviseur en commun qui est 1. On a dans tous les cas un diviseur commun, il y a donc un de ces diviseurs qui est plus grand que tous les autres, donc le PGCD existe quels que soient ces nombres.

Déterminer le PGCD de deux nombres

On sait que, pour tout couple de nombres entiers, il existe un PGCD. Nous allons maintenant déterminer le PGCD de deux nombres : 1352 et 124. Pour cela, nous allons faire... plusieurs divisions euclidiennes, que nous appelons algorithme d'Euclide:

1352=124*10+112//on pose la division euclidienne du plus grand nombre par le plus petit
124=112*1+12//on refait une division euclidienne mais le diviseur 124 devient dividende et le reste 112 devient diviseur
112=12*9+4//on continue en interchangeant les nombres de la même manière
12=4*3+0

Une fois qu'on a atteint le 0, c'est qu'on a fini, ouf !

Mais il est où le PGCD dans tout ça ?

Le PGCD est le dernier reste non nul. Autrement dit, dans la dernière division euclidienne, on avait le reste nul : il faut donc prendre le reste du dessus, c'est-à-dire 4, donc PGCD (1352, 124)=4.

J'ai rien compris,. Comment tu sais que c'est lui le PGCD et pas un autre, ? Et puis pourquoi t'as fait des divisions euclidiennes ? T'aurais pu prendre les deux nombres les soustraire, mettre à la racine carrée en passant le tout au cosinus.

Oui, mais cette méthode donne le PGCD. Je ne peux pas vous le démontrer car c'est assez difficile à comprendre, mais vous pouvez vérifier par vous-même sur ce lien sur Wikipedia.

Retenez le principe uniquement si vous voulez vous-même coder un programme pour obtenir le PGCD. Sinon, vous trouverez, sur le lien précédent, le code source de l'algorithme d'Euclide dans beaucoup de langages (pratique pour vos programmes de cryptage ;) .

Nombres premiers entre eux

Deux nombres sont premiers entre eux lorsque leur PGCD vaut 1. Cela veut dire que, si on met ces nombres en fraction (l'un en dénominateur, l'autre en numérateur), cette fraction n'est pas simplifiable.
Par exemple 8/6=4/3
PGCD (8, 6) = 2 : on peut donc simplifier la fraction en divisant en haut et en bas par 2 ce qui nous amène au 4/3 ; en revanche, PGCD (4, 3)=1 : on ne peut donc plus simplifier cette fraction.
On dit que cette fraction est irréductible gaulois qui résistent encore et toujours à l'envahisseur... Pardon je m'emporte là :p .

Conséquences de la division euclidienne

Si vous avez compris ce qu'était une division euclidienne, vous serez d'accord avec moi : le reste de la division euclidienne de la division de a par 2 est un nombre positif inférieur à 2, il n'y a donc que deux restes possibles : 1 et 0.
Ainsi : a=2q+0
Ou : a'=2q+1

Dans le premier cas, nous avons un nombre qui vaut deux fois q (avec q un nombre entier), ce nombre est donc un nombre pair. Dans le deuxième cas, nous avons a' qui vaut un nombre pair (2q) ajouté à 1, nous avons donc a' qui est un nombre impair.

Il faut que vous compreniez que tous les nombres entiers peuvent s'écrire 2q ou 2q+1 (ben ouais, facile : un nombre entier est soit pair, soit impair). Mais il faut surtout que vous compreniez que, de la même manière, tous les nombres entiers peuvent s'écrire 3q, 3q +1 ou 3q+2. On peut encore aller plus loin et faire avec 4 : 4q, 4q+1, 4q+2, 4q+3 etc...

Il existe donc des nombres qui ont le même reste dans la division euclidienne par n. Par exemple, tous les nombres impairs ont pour reste 1, dans la division euclidienne par 2.
Autre exemple : si on fait la division euclidienne de 23 par 5 et de 18 par 5.
23 = 5 * 4 +3
18 = 5 * 3 +3

On a donc le même reste qui vaut 3.

Deux nombres a et a' qui ont le même reste r dans la division euclidienne par n peuvent s'écrire :
a=nq'+r
a'=nq'+ r
Si on soustrait les deux égalités, on obtient :
a-a'=nq +r -(nq' + r) =nq -nq'
On peut donc factoriser à droite par n et obtenir : a-a'=n(q-q')

On voit donc que a-a' est un multiple de n.

On peut alors établir que, lorsque deux nombres ont le même reste par la division euclidienne par n, la différence de ces deux nombres est un multiple de n.

Nous voilà donc aux congruences : a et a' sont congrus modulo n si et seulement si ils ont le même reste dans la division euclidienne par n.

Les congruences

Nous allons maintenant attaquer

Image utilisateur

un point important de ce chapitre : les congruences. Nous avons vu avant que deux nombres étaient congrus modulo à un nombre n lorsque la différence de ces deux nombres est divisible par n. Nous allons maintenant voir plus en profondeur les congruences.

La notation

Soient deux nombres a et b qui sont congrus modulo n. Nous allons noter la congruence de manière mathématique :
a\equivb [n] qui se lit a et b congrus modulo n.

Oui mais là tu dis que ces deux nombres sont égaux, ce qui n'est pas forcément le cas.

Non le [n] veut dire "modulo n" et enlève donc toutes ambiguïtés et / ou absurdités, de plus le signe \equiv n'est pas un égal, puisqu'il y a trois barres.

Plusieurs remarques

  • On sait que si a\equivb [n] cela veut dire que a-b=qn, q étant un entier relatif (c'est-à-dire un entier positif ou négatif). Donc, si b=0 alors qn=a-0=a donc n divise a.

  • Il existe plusieurs notations pour les modulo :
    a\equivb (mod. n)
    a\equivb (n)
    Pendant la suite du tuto, j'utiliserai plus volontiers la dernière notation qui est plus simple à utiliser. :-°

  • Si a\equivb (n), alors b\equiva (n).

  • Si n=1, alors a-b est toujours divisible par 1. En effet, on peut toujours écrire un nombre x tel que x=x*1). Donc a\equivb (1) quels que soient a et b. C'est pour ça que les congruences modulo 1 n'ont pas un grand intérêt. On utilisera donc n plus grand ou égal à 2.

  • Lorsque n=10, il faut que a-b=10q. Il faut donc que a et b aient la même unité. Par exemple : 37-17=20 donc 37\equiv17 (10).

  • La division euclidienne de a par n est définie par a=qn+r, donc a-r=qn. Donc, a-r est divisible par n, donc a\equivr (n). Cela est noté a%n = r.

Un programme pour vérifier la congruence

Vous vous souvenez dans le premier chapitre nous faisions des calculs avec les modulos, comme ici :

Citation :

072565 % 283189 = 80488

Imaginez un moment que vous avez peur et que vous voulez vérifier vos calculs mais que vous n'avez pas envie de faire ça de tête. Pas de problème ! Il suffit de faire un petit programme où vous n'aurez qu'à rentrer vos trois nombres dans la console. Votre programme fait alors la différence des deux premiers nombres et voit si la division de la différence par le troisième nombre est une division dont le résultat est un entier (positif ou négatif car la soustraction de deux entiers naturels peut donner un nombre négatif ^^ ). Dans le cas contraire, les deux nombres ne sont pas congrus entre eux.

En clair si \frac{072^{565}-80488}{283189} donne un nombre entier alors c'est bon :) .

Les nombres premiers

Une définition

Prenons par exemple le nombre 24. Nous pouvons dire, grâce à nos souvenirs des tables de multiplication, que 24=12*2=6*4. Mais avec le nombre 17, si on cherche des nombres entiers a et b tels que a*b=17, on ne trouve pas beaucoup de possibilités : soit c'est a=1 et b=17, soit c'est l'inverse ; les diviseurs de 17 sont donc 17 et 1.

La définition d'un nombre premier est donc : un nombre est premier si et seulement s'il n'a que deux diviseurs positifs, à savoir 1 et lui-même.

Quelques remarques :

  • 0 n'est pas premier. En effet, on peut écrire que 0=a*0, quel que soit a. 0 ayant une infinité de diviseurs, il n'est pas un nombre premier.

  • 1 n'est pas non plus premier. En effet, pour être premier, un nombre doit avoir deux diviseurs ; or 1 n'a qu'un seul diviseur : lui-même.

  • 2 est divisible uniquement par 2 et par 1 : c'est donc un nombre premier. Tous les nombres pairs étant de la forme 2q, ils sont toujours divisibles par 2. Lorsque q est plus grand que 1, on a un nombre pair divisible par 2 nombres différents de 1 : 2 et q, donc 2 est le seul nombre pair premier.

  • Il existe une infinité de nombres premiers, le démontrer est assez difficile car cela nécessite des propriétés supplémentaires dont on n'a pas vraiment besoin. Cependant, voici un lien de Wikipédia si vous voulez comprendre.
    En tout cas, c'est plutôt une bonne nouvelle pour vos données car plus vous prendrez des nombres premiers élevés, plus n sera élevé et donc ça sera sécurisé.

Comment vérifier qu'un nombre est premier ?

Vous voulez crypter en utilisant le système RSA et vous avez choisi deux nombres dont vous n'êtes pas sûr qu'ils soient premiers. Il va donc falloir le vérifier, sinon votre cryptage ne marchera pas.
Il va falloir créer un petit programme qui va vérifier si le nombre que vous mettez est bien premier. Celui ci sera écrit en C histoire d'alterner avec le python, mais si vous le comprenez dans un langage vous le comprendrez dans l'autre :p .
Le voici dans sa totalité, les explications du programme sont juste en-dessous :

#include <stdio.h>
#include <stdlib.h>
#include <math.h> 

int main(int argc, char *argv[])
{
    long nombre = 0;
    long premier = 0;
    long essai = 0;
printf ("Bonjour, ce programme permet de tester la primalité d'un nombre!\n\n");
printf ("Entrez un nombre entier positif :");
scanf ("%ld", &nombre);
if ( nombre % 2 == 0 )
        {
    premier = 3;
        }
else
{
for (essai = 3 ; sqrt (nombre) >= essai  ; essai+=2)
        {
         if (nombre % essai == 0)
                {
                premier = essai;
                }
        }   
}

if (nombre == 2)
{
premier = 0;
}
if (nombre == 1)
{
premier = 1;
}
if ( premier == 0)
{
printf ("ce nombre est premier\n\n\n");
}
else
{
printf ("Ce nombre n'est pas premier\n\n\n");
}

getchar();
return 0;
}

Explication:
Pour la première partie : le if
Nous savons qu'aucun nombre pair, sauf 2, n'est premier.

if ( nombre % 2 == 0 )
        {
    premier = 3;
        }

Le code ci-dessus nous permet de savoir si le nombre est pair. S'il est pair (et différent de 2), il n'est pas premier. Il va donc falloir que la variable premier prenne une valeur différente de 0 (ici 3). En effet, à la fin, le code teste la variable premier et indique qu'un nombre est premier si la variable premier est nulle. Il faut cependant retenir que 2 est le seul nombre pair premier ; il faut donc ensuite faire un test pour voir si le nombre rentré par l'utilisateur est 2 ou pas ; si c'est le cas, il faut que la variable premier soit égale à 0, d'où le

if (nombre == 2)
{
premier = 0;
}

Ce bout de code doit être inséré après le test qui permet de dire si le nombre est pair ou pas. Si ce n'est pas le cas, la variable premier prendra, dans le cas où le nombre est deux, d'abord la valeur 0, puis la valeur 3.

Deuxième partie : le else
Pour comprendre cette partie, il faut que vous sachiez une chose : un nombre non premier a des diviseurs autres que un et lui-même. Ça, vous le savez, mais ce que je ne vous ai pas dit, c'est que, parmi ces diviseurs, il y a au minimum un nombre premier : par exemple, dans le cas du nombre 36, ses diviseurs sont (en gras les diviseurs qui sont premiers) :
1, 2, 3, 4, 6, 9, 12, 18, 36

Donc, en fait, ça serait simple : il suffirait de prendre un nombre et de le diviser par tous les nombres premiers inférieurs à ce nombre, et voir si un de ces nombres premiers est bien un diviseur ?

Oui, mais cela suppose de connaître tous les nombres premiers qui sont inférieurs à ce nombre, et ce n'est pas dit que ça soit le cas : vous pouvez me réciter tous les nombres premiers inférieurs à 4787 :-° ?
Alors, pour le programme, on va devoir diviser par d'autres nombres que des nombres premiers. Essayer tous les nombres serait trop long mais on sait déjà que tous les nombres pairs supérieurs à 2 ne sont pas premiers : on n'a donc qu'à faire des tests pour des nombres impairs supérieurs à 3 et incrémenter la variable essai de 2 pour éviter d'avoir des nombres pairs, d'où ceci :

for (essai = 3 ; sqrt (nombre) >= essai  ; essai+=2)

Oui mais pourquoi la racine carrée (représenté par sqrt) ?

Excellente question :p , la question est aussi intéressante que la réponse sera compliquée. :o

Vous êtes d'accord pour dire que, si on prend un nombre a positif, alors on a : a=\sqrt{a}*\sqrt{a}.
Dans la pratique, a aura des diviseurs ; on peut donc dire que certains seront supérieurs ou égaux à \sqrt{a} et d'autres seront inférieurs ou égaux à \sqrt{a}.
Supposons que b et c soient des diviseurs de a tels que a=bc et que \sqrt{a}> b.
Si on prend cette égalité, que l'on multiplie tout par \sqrt{a}, on obtient :\sqrt{a}*\sqrt{a}>b*\sqrt{a}
soit a > \sqrt{a}*b, mais on sait aussi que a=bc, on remplace donc a par bc.
Donc b*c> b* \sqrt{a}en divisant par b : c> \sqrt{a}
Et là tout s'éclaire o_O , non ?
Ça veut dire qu'un nombre quelconque a autant de diviseurs supérieurs (ou égaux) à racine de a que de diviseurs inférieurs à racine de a.
D'ailleurs, on le voit avec les diviseurs de 36 : 1, 2, 3 et 4 sont inférieurs à 6 tandis que 9, 12, 18 et 36 sont supérieurs à 6.
Donc, si on fait des tests avec des nombres inférieurs à racine de a et qu'on ne trouve pas de diviseur, c'est qu'il n'y en aura pas non plus au-dessus de racine de a. Le nombre est donc premier.
A contrario, il suffit de trouver un nombre qui divise a pour que a ne soit plus premier. Et il faut donc changer la variable premier et lui mettre une autre valeur : j'ai pris la valeur essai dans mon programme, mais je peux très bien mettre 4 ou tout autre nombre différent de 0.

Troisième partie : les tests

Il suffit de tester avec des if si le nombre premier est nul ou pas. S'il est nul, le nombre est premier ; dans le cas contraire, il n'est pas premier. Il faut aussi faire attention au 1, qui n'est pas premier. Il faut donc modifier la variable premier en faisant un test.

Il est évident que si ce test vous a permis de vérifier que 11 était effectivement premier en quelques dixièmes de secondes, il est beaucoup plus lent. Tester la primalité d'un nombre (la primalité étant le fait qu'un nombre soit premier) demande des ordinateurs beaucoup plus puissants et des algorithmes plus avancés.

Générer des nombres premiers

On arrive à trouver des expressions où, en faisant varier un entier positif n, on peut aboutir à la génération de certains nombres premiers ; mais il faut être prudent car cela ne marche pas à tous les coups. Je vais donc vous donner 3 suites, ce qui vous permet déjà de créer quelques nombres premiers :

Une première suite

Soit l'équation p=n²-n+41 avec n un nombre entier positif. Si nous faisons varier n, nous voyons que p prend des valeurs de nombre premier. Ci-dessous le tableau des premières valeurs de p :

valeur de n

valeur que prend p

p premier ?

0

41

Oui

1

41

Oui

2

43

Oui

3

47

Oui

4

53

Oui

5

61

Oui

de 5 à 39

...

Oui

40

1601

Oui

41

41²-41+41=41²=1681

Non

Et là c'est le drame car pour n=41, p=41² : ce n'est pas un nombre premier car il a au moins 3 diviseurs : un, lui-même et 41.

Cette suite ne marche pas : dommage ça aurait été un bon moyen de créer une suite de nombres premiers. Si vous avez un tableau de nombres premiers sous les yeux, vous pouvez vous apercevoir que, pour des valeurs de n qui vont de 0 à 40, ça marche mais pas au-delà :( .

Vous pouvez aussi remarquer que cette suite ne donne pas tous les nombres premiers. En effet, il y avait de grands écarts au bout d'un moment entre deux valeurs de p consécutives alors qu'il y avait plein d'autres nombres premiers au milieu. Mais cette suite peut quand même vous donner des nombres premiers jusqu'à 1601.
Le problème, c'est que si tout le monde utilisait les nombres premiers de cette suite, les pirates le sauraient et ils n'auraient plus qu'à prendre le nombre n et à le diviser par les nombres de la suite pour des valeurs de n inférieures à 41. Ils pourraient donc en un rien de temps factoriser n. Il va falloir donc trouver autre chose.

Les nombres de Fermat

Pierre de Fermat a conjecturé (sans le prouver) il y a quatre siècles que les nombres du genre p=22n+1 étaient premiers.

Avec cette suite, ça a marché jusqu'à n=4 où on avait un nombre premier p = 65 537, mais Euler (si vous êtes en Première ou en Terminale S, vous avez sûrement entendu parler d'Euler et de la méthode d'Euler pour les approximations affines) démontra que, pour n=5, on avait p=4 294 967 297, ceci étant (comme chacun sait :D ) le produit de 6 700 417 par 641.

Nous n'avons donc pas beaucoup de nombres premiers sûrs avec cette suite mais elle donne quelques valeurs assez grandes de nombres premiers. D'ailleurs, il existe d'autres nombres premiers qui sont supérieurs au contre-exemple d'Euler, mais on ne sait pas s'il y en a une infinité ou pas. Donc il faudra faire des vérifications.

Une autre suite : les nombres de Mersenne

Les nombres de Mersenne sont des nombres du genre : 2p-1 avec p un nombre premier. Cette suite donne des nombres qui ne sont pas forcément premiers mais qui ont une possibilité de l'être. Il faut donc faire un test de primalité grâce au programme que je vous ai montré ci-dessus.
Cependant, les nombres de Mersenne peuvent quand même donner de grands nombres premiers. Par exemple, le nombre 124575026[&]053967871 est un nombre premier comprenant exactement 9 808 358 chiffres (si vous retenez que ça fait presque 10 millions de chiffres, vous comprendrez pourquoi je peux pas l'écrire en entier :-° ) .

Il existe beaucoup de méthodes différentes de créer des nombres premiers ou des nombres ayant une forte probabilité de l'être, il est évident que les gens qui utilisent le système RSA pour des transactions de banques ne vont pas se servir que des nombres de Mersenne :p et autres...

Conclusion

Vous pouvez donc générer pas mal de nombres premiers en faisant un programme qui va choisir aléatoirement, entre ces trois suites (veuillez noter qu'il existe d'autres suites de ce genre), deux d'entre elles (si c'est la même suite c'est pas très grave) et générer deux nombres premiers q et p pour le cryptage RSA. Mais n'oubliez pas que, pour la première suite que je vous ai donnée, il faut que n soit inférieur à 41. Il faudra également faire des tests de primalité si vous utilisez les deux autres suites.
Évidemment, je vous ai présenté des moyens simples de créer des nombres premiers, il est évident qu'il existe d'autres algorithmes plus performant mais aussi plus compliqué :) .

Vous pouvez aussi intégrer dans votre programme les autres suites que je vous ai données en lien pour augmenter le nombre de nombres premiers que vous pouvez faire.

La factorisation

La factorisation est un point important dans le décryptage, en effet, en connaissant n, il faut trouver les nombres p et q.
C'est ce qu'on appelle la factorisation.

Première approche : qu'est-ce que la factorisation ?

Vous avez peut-être appris en classe que k(a+b)=ka+kb (si vous ne l'avez encore jamais vu, maintenant au moins c'est fait :-° ), par exemple 12(5+4)=12*5+12*4.

Lorsque l'on passe de k(a+b) à ka+k,b cela s'appelle développer.
Et dans l'autre sens, c'est la factorisation : cela veut dire que quand vous avez une somme de plusieurs produits, vous prenez ce qui est commun à tous ces produits et vous le multipliez par le reste que vous mettez dans des parenthèses.

Concrètement cela donne : 8*6+8*7+1568*8+67*8-8*3+8
On remarque que dans chacun des différents produits il y a un 8. On met donc 8 en facteur et on obtient :
8*6+8*7+1568*8+67*8-8*-3+8*1=8(6+7+1568+67-3+1).
Ainsi, si vous voulez calculer le résultat, vous avez moins d'opérations à faire : il suffit de calculer le résultat de la parenthèse et de le multiplier ensuite par 8. Vous gagnez donc un temps précieux et ce même en faisant le calcul avec votre calculatrice car vous réduisez le risque d'erreur en rentrant vos nombres.

Deux petites remarques :

  • Je n'ai pris la propriété qu'avec trois nombres k, a et b mais, comme vous le voyez dans l'exemple, on peut en mettre beaucoup plus : en fait vous en mettez autant que vous voulez. :D

  • Vous remarquez qu'il y a 1 à la fin : c'est tout simplement parce que 8=8*1. Si j'oublie ce 1, je modifie le résultat, ce qui n'est pas bon. ^^

Maintenant voyons ce qu'est la décomposition en produit de facteurs premiers.

La décomposition : ça va nous aider à trouver n

On a vu au-dessus qu'on pouvait factoriser, c'est-à-dire mettre sous forme de différents facteurs. C'est ce que nous allons maintenant faire mais cette fois-ci nous allons partir d'un seul nombre n et le décomposer.

Tout d'abord on peut dire que tous les nombres sont soit premiers soit un produit de nombres premiers, par exemple :

7 est premier
8=4*2=2*2*2=23 avec 2 qui est premier,
42=7*6=7*3*2 avec 7, 3, 2 qui sont premiers,
etc.

Cette décomposition est unique, si on ne tient pas compte de l'ordre dans lequel on met les différents facteurs (voilà le lien de Wikipédia pour la démonstration).

Il va donc falloir maintenant savoir comment factoriser n :

vous prenez un nombre et vous voyez s'il est divisible par deux. Si c'est le cas, notez son résultat et notez que vous avez mis un 2. Ensuite vous divisez ce résultat par deux si vous le pouvez. Si vous ne pouvez pas vous passez au nombre premier suivant, c'est-à-dire 3, vous le divisez par 3 autant de fois que vous pouvez, et après vous passez à 5, etc.
Prenons un exemple pour bien comprendre. On va décomposer 3960 :

Image utilisateur

On part de la valeur 3960 et on la divise par le premier nombre premier qui est 2 : on note qu'on a divisé une fois par 2 à droite. On voit qu'on obtient 1980, un nombre encore divisible par 2 : on rajoute donc un autre 2 à droite. Une fois cela fait, on passe à trois, puis à 5 et pour finir à 11.
Au final on trouve 1. Cela veut dire qu'on a fini la factorisation. En effet : 2 *2 *2 *3 *3 * 5 *11=2³*3²*5*11=3960. On a donc bien décomposé 3960 en facteurs de nombres premiers. Dans la pratique, la décomposition est plus simple dans la mesure où n est un produit de deux nombres premiers : il n'y a donc que deux nombres à trouver, p et q, mais cela nécessite beaucoup plus de temps. En effet, le nombre n ne sera sûrement pas divisible par 2, par 3 ou par 5. Souvenez-vous que nous préférons mettre de grands nombres premiers.

Si vous regardez le code permettant de trouver p et q qui vous a été donné pour faire le programme de décryptage, vous verrez que cela correspond à ce que nous avons fait au dessus, seulement là c'est l'ordinateur qui fait tout pour vous, chanceux ! :D

Voilà, j'espère que vous avez beaucoup appris et que vous comprenez mieux ces notions mathématiques essentielles pour bien maîtriser le système RSA sur le bout des doigts.
J'ai essayé de faire en sorte que ce chapitre ne soit pas un cours de maths classique souvent bien ennuyeux, car l'objectif est surtout de vous faire comprendre des points importants du cryptage RSA. C'est pour ça que j'ai décidé de ne pas vous mettre de QCM

Image utilisateur

.

Pour tout remerciement, critique, suggestion, insulte, admiration, signalement d'erreur, manque de clarté, vous pouvez poster un message dans les commentaires.

Rédigé par L01c.

Et voilà, c'est fini, vous avez maintenant toutes les cartes en main pour pouvoir crypter / décrypter ce que vous voulez (tant qu'il ne s'agit pas de décrypter le code secret de mon compte en banque :-° ) . Vous pouvez, si vous le voulez, refaire vous-même un gros programme : pourquoi pas un programme avec de jolies fenêtres qui vous permet de crypter / décrypter, en faisant le gros du travail, c'est-à-dire en créant des nombres premiers, en générant les clefs publiques et secrètes etc. ? Vous voyez, même après avoir lu ce tuto, vous avez encore du travail. o_O

Have fun !

Si vous voyez des erreurs, fautes d'orthographe ou des points obscurs, n'hésitez pas à nous les signaler.

Un grand merci aux Validateurs et aux zCorrecteurs, sans qui rien n'aurait été possible. :)

Les auteurs

Exemple de certificat de réussite
Exemple de certificat de réussite