Comment crée-t-on nos clés ?!

Pour créer notre clé publique il nous faut choisir deux nombres premiers.



Soit P et Q, ces deux nombres premiers.
(Je vais prendre des valeurs à titre d'exemple pour P et Q, mais n'hésitez pas à les changer...)
Je prends P = 53 et Q = 97

Ensuite, on va prendre un autre nombre, N, tel que :
Dans mon cas, j'ai N = 53 x 97 = 5141

On pose .


J'obtiens pour ma part, M = (53 - 1) x (97 - 1) = 4992

Pour créer notre clé publique, il ne nous reste plus qu'à choisir un nombre C, qui soit premier avec M.
(Il en existe, là aussi, une infinité.) Je choisis C = 7.



Au final, notre clé publique est composée de (N, C). Dans mon cas, j'ai (N = 5141, C = 7) comme clé publique.

Pour créer notre clé privée, on va calculer un nombre U, qui va nous permettre "d'inverser la fonction de chiffrement" très facilement (On verra dans quelques chapitres comment faire). C'est ce nombre qui sera important, et secret !

Pour calculer U, on va reprendre les nombres C et M, calculés lors de la création de la clé publique.

Un mathématicien, du nom d'Etienne de Bezout, a démontré que deux nombres a et b sont premiers entre eux, si et seulement s'il existe des solutions u et v telles que (u et v étant des nombres entiers). Or, on a dit peu avant que C et M devaient être premiers entre eux. Il existe donc deux nombres entiers u et v qui répondent à l'équation.

Nous allons chercher U, tel que (Note : la valeur de V ne nous servira pas)

Comment trouver U ?

Pour trouver U, il faut utiliser un algorithme spécial. Le but de ce chapitre n'est pas de vous montrer comment fonctionne cet algorithme, mais plutôt ce que l'on peut faire avec. On va donc utiliser un petit programme qui permet de trouver la valeur de U cherchée.
Le programme est disponible pour GNU/Linux (cf un peu pour loin pour l'installation), et ici pour Windows.

• Sous GNU/Linux, nous allons devoir compiler ce programme. Pour ce faire il faut auparavant avoir installé la bibliothèque GMP. (C'est la bibliothèque que l'on utilisera dans toute la partie II du tutoriel. Il faudra donc installer la bibliothèque GMP à un moment où un autre (Pour Windows, j'expliquerais comment faire dans le chapitre I de la partie II))
  Ouvrez une console et copiez-y ce code, ça fera tout pour vous
  Code : Console - Installation du programme : GNU/Linux

  cd ~ mkdir RSA cd RSA wget http://ftp.sunet.se/pub/gnu/gmp/gmp-4.2.2.tar.gz tar xfz gmp-4.2.2.tar.gz cd gmp-4.2.2 ./configure --enable-cxx make make check sudo make install cd .. rm gmp-4.2.2 gmp-4.2.2.tar.gz cd /usr/lib/ sudo ln -s /usr/local/lib/libgmpxx.so.4 libgmpxx.so.4 cd ~/RSA wget http://tuxweb79.free.fr/Bezout_linux.zip unzip Bezout_linux.zip cd Bezout make chmod +x bezout

  
  Ceci aura pour effet de compiler, puis d'attribuer les droits d'exécution au programme (en ayant installé la bibliothèque GMP avant...) ;
• Sous windows, vous extrayez l'archive .zip. Le programme est déjà compilé, il vous suffit de le lancer depuis la ligne de commande en faisant : démarrer > exécuter > "cmd" puis :
  
  Code : Console - Installation du programme : Windows

  cd chemin/vers/le/dossier/du/programme/

Comment fonctionne le programme ?

Il vous suffit de lancer le programme avec comme arguments C et M, comme ceci.

Code : Console - Programme Bezout


Dans mon cas, j'ai :

Code : Console - Programme Bezout
Ainsi, je connais U.

U = -713 n'est pas acceptable !

Bah.. pas tout à fait. L'algorithme du système RSA a besoin d'un U tel que , or là, on voit clairement que U est inférieur à 2 (dans mon exemple, mais ça arrive souvent )

Comment faire pour y remédier ?

En appliquant la formule suivante (avec U₀ la solution trouvée précédemment) : . On peut trouver d'autre solution à l'équation précédente correspondant à nos besoins. Il suffit de faire varier l'entier K pour obtenir une valeur dans l'intervale . On pose U une valeur de tel que .

Trouver directement un U valable grâce au programme précédent

Pour trouver directement un U qui convient, il suffit de lancer le programme Bezout, avec l'option "-rsa". Voici ce que j'obtiens dans mon cas :

Code : Console - Programme Bezout
Je retiens U = 4279.

Ca y est !

Voilà, notre clé privée est (U, N). J'ai (U = 4279 et N = 5141) comme clé privée

Je ne sais pas si vous avez remarqué, mais on construit nos clés seulement à partir de P et Q.
De plus, tout le monde peut connaitre N (qui est le produit de P et Q), car N fait partie de la clé publique. Il suffirait donc à n'importe qui (notre espion , par exemple) de décomposer N en un produit de deux facteurs premiers (P et Q) pour ensuite recalculer M, et grâce à M avoir la possibilité de trouver U... (Ce qui permettrait à l'espion de déchiffrer les messages)




En effet, ce n'est pas très sécurisé si P et Q sont de petits nombres premiers. En réalité, P et Q sont des nombres composés d'une bonne centaine de chiffres, ce qui fait qu'il est très difficile de décomposer N pour retrouver P et Q. Même des machines sur-puissantes reliées entre elles ne pourraient pas casser N en un temps raisonnable...

Mais, pour nous, on va prendre des petits nombres premiers... Ça va permettre de simplifier grandement les calculs

Quelques exemples de vrais facteurs

Voici un exemple de factorisation :

N = 31074182404900437213507500358885679300373460228427275457201619488232064405
18081504556346829671723286782437916272838033415471073108501919548529007337
724822783525742386454014691736602477652346609

qui est décomposable en :

P = 16347336458092538484431338838650908598417836700330
92312181110852389333100104508151212118167511579

Q = 1900871281664822113126851573935413975471896789968
515493666638539088027103802104498957191261465571

(Il a fallut faire travailler 80 processeurs Opteron de 2.2GHz pendant 5 mois. pour trouver P et Q )