Aller au menu - Aller au contenu

2 602 Zéros connectés
298 525 Zéros inscrits
Inscription
Connexion
- Pseudo
- Mot de passe
- Mot de passe oublié ?
- Connexion auto.
- Connexion avec un compte :

Informatique
- Informatique
- Sciences
- Cours
- Forums
- Participez
- Études
- Emploi
- Boutique
+

> Le Site du Zéro - Informatique

> Cours

> Tutoriels

> Programmation

> Algorithmique

> La cryptographie asymétrique : RSA

> La théorie

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

> Lecture du tutoriel

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

L'auteur de ce cours cherche un repreneur pour continuer son travail
Parfois, certains auteurs de cours n'ont plus le temps de rédiger et de mettre à jour leur travail. Ils recherchent alors un nouvel auteur pour "reprendre" leur tutoriel (voir la liste des tutoriels en attente de repreneur).
Contactez l'auteur si vous aimeriez continuer la rédaction !

Par

Simon Chabot (TuxWeb) et Avatar

Toulousaing

Mise à jour : 09/09/2009

Creative Commons BY-SA

1 105 visites depuis 7 jours, dont 200 sur ce chapitre classé 112/786

Dans cette partie nous allons apprendre à créer les clés privée et publique qui nous servirons plus tard à chiffrer et déchiffrer les messages.
Il faut quelques notions en mathématiques, mais je vais faire de mon mieux pour être le plus explicite possible.

Sommaire du chapitre :

Icône du chapitre

Création de la clé publique
Création de la clé privée
Des clés sécurisées
Q.C.M.

Chapitre précédent

Sommaire

Chapitre suivant

Création de la clé publique

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

Un nombre premier est un nombre supérieur ou égal à 2 qui possède deux diviseurs positifs distincts et uniquement deux (1 et lui-même). On peut prendre pour exemple 2, 3, 7, 53, 89... Il existe une infinité de 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 : $N = P \times Q$
Dans mon cas, j'ai N = 53 x 97 = 5141

On pose $M = (P-1) \times (Q-1)$ .

Ce nombre "M" est appelé indicatrice d'Euler, il correspond au nombre d'entiers naturels (0, 1, 2, 3, etc...) inférieurs ou égaux à N qui lui sont premiers

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.

Deux nombres sont premiers entre eux si et seulement s'ils n'ont aucun facteur commun (à l'exception de 1 et -1). Par exemple, 16 et 12 ne sont pas premiers entre eux, car ils ont au moins un facteur commun (ici, on a 2 et 4 en commun (12 = 6 * 2 = 3 * 4 et 16 = 8 * 2 = 4 * 4)

Pour savoir facilement si deux sont premiers entre eux, il suffit que calculer le PGCD de ces deux nombres. S'il est égal à 1, alors ces deux nombres sont premiers entre eux. (J'ai bien PGCD(4992, 7) = 1)...

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

Création de la clé privée

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 Bézout, 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 $a \times u + b \times v = 1$ (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 $C \times U + M \times V = 1$ (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.

Pour ceux qui seraient intéressés par cet algorithme, des informations sont disponibles ici.

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

./bezout C M

Sous Windows, au lieu de taper "./bezout", il faut taper "Bezout.exe".

Dans mon cas, j'ai :

Code : Console - Programme Bezout

./bezout 7 4992
PGCD = 1
u = -713
v = 1

Ainsi, je connais U.

U = -713 n'est pas acceptable !

Comment ça ? c'est pas bon ?! o_O

o_O

Bah.. pas tout à fait. L'algorithme du système RSA a besoin d'un U tel que $2 < U < M$ , 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) : $2 < (U_0 - K \times M) < M$ . On peut trouver d'autres solutions à l'équation précédente correspondant à nos besoins. Il suffit de faire varier l'entier K pour obtenir une valeur dans l'intervale $]2 ; M[$ . On pose U une valeur de $(U_0 - K \times M)$ tel que $2 < (U_0 - K \times M) < M$ .

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

./bezout -rsa 7 4992
4279

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

Des clés sécurisées

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 Image utilisateur

Image utilisateur

, 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)

La décomposition de n'importe quel nombre en facteurs premiers est unique (à l'ordre près). Ainsi, si on décompose N, on retrouve forcement les valeurs de P et Q initiales, et pas d'autres !

Eh ! tu me fais peur là !? C'est pas si sécurisé que ça ton truc !

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

)

Voilà, maintenant que nous savons créer nos clés, nous allons voir dans le chapitre suivant comment chiffrer un message.

Chapitre précédent

Sommaire

Chapitre suivant

Partager

Partager via Email

Partager via Twitter

Partager via Facebook

Imprimer

21 commentaires pour "Comment crée-t-on nos clés ?"

Note moyenne : 3.71 / 4 (31 votes)

Pseudo

Commentaire

Hors ligne

Meryama03

# Posté le 06/03/2011 à 05:16:13

Avis : Très bon

L'installation de GMP ne marche pas

Hors ligne

igoris

# Posté le 11/10/2011 à 19:19:31

Merci beaucoup pour ce tutoriel.

Hors ligne

igoris

# Posté le 12/10/2011 à 14:39:20

doublon.

Hors ligne

Maxwell Edison

# Posté le 27/10/2011 à 14:23:21

Études : ICAM Nantes

Citation : Meryama03

L'installation de GMP ne marche pas

J'ai réussi en faisant (sous Ubuntu)

Code : Console

sudo apt-get install build-essential m4

Puis le code de kzl31.

Hors ligne

Krapow

# Posté le 07/11/2011 à 21:05:39

GOAAAL

Tuto super intéressant, je suis pas un pro des math donc je sais pas si certaines simplifications n'arrachent pas les cheveux de certains, mais moi ça me va tout a fait

Merci beaucoup

Image utilisateur

Voir tous les commentaires