Aller au menu - Aller au contenu

Icône Et le chiffrage, comme ça se passe ?

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 !

Mise à jour : 09/09/2009
1 105 visites depuis 7 jours, dont 160 sur ce chapitre classé 112/786
Après avoir créé les clés publique et privée, nous allons voir comment fait-on pour chiffrer un message quelconque (texte / chiffres ...) grâce au système RSA...
Sommaire du chapitre :
Icône du chapitre
Chapitre précédent Sommaire Chapitre suivant

Tout fonctionne avec des chiffres !

Vous vous doutez surement que l'on va utiliser des chiffres pour chiffrer nos messages. Il va donc falloir trouver un moyen d'associer à chaque caractère un nombre. J'ai deux solutions à vous proposer :
  1. Remplacer chaque caractère par sa position dans l'alphabet ;
  2. Remplacer chaque caractère par sa valeur dans la table.ASCII


Quelle solution prendre ?



Chacune des deux solutions a son avantage et son inconvénient. L'avantage de la solution 1) est qu'elle nous permet de gérer de très petits nombres (de 0 à 25), ce qui serait pratique pour les calculs. Son inconvénient découle directement de son avantage, on ne peut gérer que 26 caractères (donc pas de majuscules, pas d'espaces, pas de chiffres, pas d'accents...) Bref, vous avez compris ce n'est pas la meilleure solution pour nous, qui voulons chiffrer n'importe quel caractère.

Nous allons donc choisir la deuxième solution qui nous permet de gérer énormément de caractères, avec des chiffres, des espaces, des accents, etc...

Je vous conseille de mettre ce lien http://www.asciitable.com/ en favori, car nous allons devoir nous y référer assez souvent.


Bien, passons à la suite :p

Un programme de calcul

Pour chiffrer nos messages, nous allons principalement utiliser le "modulo" et les "puissances". Ce genre d'opérations n'est pas facile à faire de tête (à moins d'être un vrai génie ^^ ). De plus, nous allons nous servir (malgré nos efforts) de nombres relativement grands. Toutes les calculatrices ne sont pas capables d'effectuer les opérations "modulo" et "puissance" avec de grands nombres. C'est pourquoi, je vous conseille d'installer un petit programme qui va faire tout juste ce que l'on veut. Pas plus, pas moins.

Il est disponible sous GNU/Linux et sous Windows.

  • L'installation sous Linux se fait de la manière suivante : vous ouvrez une console, et vous y copiez les instructions suivantes :

      Si vous n'avez pas installé GMP, il faudra le faire ^^ ; copiez ce code, il l'installera pour vous :

      Code : Console
      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

      Pour installer le programme de calcul, copiez ces instructions : Code : Console
      cd ~
      mkdir RSA
      cd RSA
      wget http://tuxweb79.free.fr/Calculs_RSA_linux.zip
      unzip Calculs_RSA_linux.zip
      cd Calculs_RSA
      make
      chmod +x calculs_RSA

  • Pour Windows, téléchargez le programme de calcul ici.
    Puis extrayez l'archive. Pour lancer le programme ouvrez l'invite de commandes (Démarrer -> executer -> "cmd"), puis :

    Code : Console
    cd chemin/vers/le/dossier/du/programme/



Voilà, c'est installé ; on va maintenant s'en servir :D

Le chiffrage proprement dit

On va reprendre nos deux camarades, Alice et Bob. La situation est toujours la même, Bob veut envoyer un message chiffré à Alice. Il va donc récupérer sa clé publique. Dans l'annuaire, il voit :

Annuaire RSA
PersonneClé publique
... (N, C)
Jean (N = 187, C = 3)
Alice (N= 5141, C = 7)
Lucie (N= 4183, C = 19)
... (N, C)


Il prend la clé publique d'Alice : (N = 5141, C = 7). (J'ai volontairement repris la même clé que dans le chapitre précédent afin que vous sachiez les valeurs de P Q et tout ce qui s'ensuit)

Etape 1 : remplacement des caractères par leurs valeurs ASCII



Bob veut envoyer le message "Bonjour !" à Alice. On a vu précédemment, qu'on devait travailler avec des nombres. On se réfère à la table ASCII, et on effectue le remplacement.


B \Leftrightarrow 66 \\o \Leftrightarrow 111 \\n \Leftrightarrow 110 \\j \Leftrightarrow 106 \\o \Leftrightarrow 111 \\u \Leftrightarrow 117 \\r \Leftrightarrow 114 \\(espace)  \Leftrightarrow 32 \\! \Leftrightarrow 33\\


Etape 2 : Premier calcul, la puissance



Ensuite, on va élever chaque sous-message (nombre) à la puissance C (7, dans notre cas)
On a alors :


B \Leftrightarrow 66 \Rightarrow 66^7 \\o \Leftrightarrow 111 \Rightarrow 111^7 \\n \Leftrightarrow 110 \Rightarrow 110^7 \\j \Leftrightarrow 106 \Rightarrow 106^7 \\o \Leftrightarrow 111 \Rightarrow 111^7 \\u \Leftrightarrow 117 \Rightarrow 117^7 \\r \Leftrightarrow 114 \Rightarrow 114^7 \\(espace)  \Leftrightarrow 32 \Rightarrow 32^7 \\! \Leftrightarrow 33 \Rightarrow 33^7 \\


Vous pouvez à l'aide du programme de calcul, calculez les valeurs précédentes (66^7, etc..) en tapant simplement

Code : Console
./calculs_RSA 66 7


dans la console et appuyez sur "entrée" pour voir le résultat.

Sous Windows, tapez simplement "calculs_RSA"


Etape 3 : Deuxième et dernier calcul : le modulo



Le modulo, c'est quoi ? o_O

Le modulo, c'est le reste de la division euclidienne d'un nombre entier par un autre.

Un exemple de modulo :



"16 modulo 3" \Leftrightarrow 16mod(3) = 1
Et oui, car dans 16, on peut placer 5 fois 3 (ce qui donne 15 ^^ ) et il reste 16 - 15 = 1.
Ainsi on note 16mod(3) = 1.


Nous avons effectué notre premier calcul, nous allons maintenant faire le deuxième calcul, à partir des résultats que l'on a obtenu précédemment.

On va calculer le modulo du résultat obtenu précédemment par N (le N de la clé publique)

Il est important d'utiliser le programme de calcul à partir de ce moment, sans quoi vous ne pourrez pas trouver la valeur finale...


On obtient (grâce au programme) :



B \Leftrightarrow 66 \Rightarrow 66^7 \Rightarrow (66^7)mod(5141) = 386 \\o \Leftrightarrow 111 \Rightarrow 111^7 \Rightarrow (111^7)mod(5141) = 1858 \\n \Leftrightarrow 110 \Rightarrow 110^7 \Rightarrow (110^7)mod(5141) = 2127 \\j \Leftrightarrow 106 \Rightarrow 106^7 \Rightarrow (106^7)mod(5141) = 2809 \\o \Leftrightarrow 111 \Rightarrow 111^7 \Rightarrow (111^7)mod(5141) = 1858 \\u \Leftrightarrow 117 \Rightarrow 117^7 \Rightarrow (117^7)mod(5141) = 1774 \\r \Leftrightarrow 114 \Rightarrow 114^7 \Rightarrow (114^7)mod(5141) = 737 \\(espace)  \Leftrightarrow 32 \Rightarrow 32^7 \Rightarrow (32^7)mod(5141) = 3675 \\! \Leftrightarrow 33 \Rightarrow 33^7 \Rightarrow (33^7)mod(5141) = 244 \\


Pour calculer ces valeurs avec le programme de calcul il suffit de taper et de valider par "entrée" pour voir le résultat :

Code : Console
./calculs_RSA 66 7 5141



On a fini :D



Voilà, plus de calculs à faire. Ainsi avec la clé publique d'Alice (N = 5141, C = 7), le message "Bonjour !" devient "386 1858 2127 2809 1858 1774 737 3675 244"

A partir du moment où le message est chiffré, on ne peut plus le déchiffrer sans l'aide de la clé privée. Même Bob, qui est l'auteur du message, ne peut le déchiffrer (même si en théorie, il connait le message ^^ )

Effectuer le chiffrage grâce à une seule et unique fonction



On peut facilement ramener les deux opérations précédentes en une seule et unique fonction.
La voici : f(x) = x^C mod(N). Dans cette fonction "x" représente la valeur ASCII du caractère à chiffrer.
Cette fonction élève x à la puissance C et calcule le reste de la division euclidienne de xC par N.

Ainsi on a :


B \Leftrightarrow 66 \Rightarrow f(66) = 386 \\\cdots \\! \Leftrightarrow 33 \Rightarrow f(33) = 244 \\

On utilisera cette fonction dans le programme que l'on réalisera dans la partie pratique du tutoriel.
Voilà, vous savez maintenant comment on chiffre des messages.

Vous pouvez vous entrainer à chiffrer d'autres messages, en créer d'autres clés. Cela peut être intéressant.

Dans le chapitre suivant, nous allons voir comment peut-on faire pour déchiffrer le message.
Chapitre précédent Sommaire Chapitre suivant

Partager

9 commentaires pour "Et le chiffrage, comme ça se passe ?"
Note moyenne : 3.71 / 4 (31 votes)
Pseudo Commentaire
Hors ligne TuxWeb # Posté le 19/10/2009 à 08:02:40
Avatar

Ville : Compiègne
Pays : France métropolitaine
Études : UTC

@sebsheep : cf ici, 3ieme fonction...

Citation : Emmanuel KANT
Je n'ai pas besoin de penser pourvu que je puisse payer ; d'autre se chargeront bien de cette besogne.

 
Hors ligne maxmatch # Posté le 25/12/2009 à 13:36:54

L'alphabet est un des points faibles du chiffrage, il est par défaut limité, il ne doit pas être prédictible B après A, plus il est étendu plus il contient d'indices, la ponctuation est aussi un indice ainsi que les formes de politesse.

Chiffer un no de carte de crédit ne doit pas retourner un autre nombre de 16 chiffres, le préfixe peut être deviner facilement.

Je pense qu'avant de continuer tu devrais nous présenter la stratégie globale pratique:

Comment tu veus communiquer? Email
Comment on calcul une paire de nombre premiers de 256 caractères de long mais assez divergents?
Comment on calcul et affiche leur produit pour les transmettrent?
Comment les correspondants introduisent des nombres de 512 chiffres sans se tromper?
Comment sont stockées les informations confidentielles?

Où sont stockées les informations qui passent par le clipboard ou qui entrent dans l'ALU lors d'opération Puissance/Modulo???

Sinon mathématiquement c'est intéressant. Il y a des solutions hard clés usb scanner d'empreintes: A chiffre un message, à réception je le crypte avec ma clé et lui retourne, il le déchiffre à moitié avec sa clé me le retourne, enfin, je le déchiffre complétement.
Hors ligne gusfl # Posté le 01/02/2012 à 14:32:35

Avis : Mitigé

bonjour.juste une remarque:prenont le B de bonjour avec la clée publique(e=7,N=5141)

B=66
66^7=279936
279936%5141=2322

et 2332 est differant de 386!! :(

Code : PHP
1
2
3
4
<?php

    $boss =(gusfl)?true:false;
?>

:ange:
 
Hors ligne gusfl # Posté le 06/02/2012 à 10:04:20

Avis : Mitigé

Je t'ai renvoyé un MP, mais comme tu n'a pas répondu je te poste ici la reponce,(qui sait, peut etre vera-tu l'email automatique envoyé ;) )


Citation : gusfl
ah....oui désolé ca dois etre la calculatrice qui a bugé,ou moi qui me suis gourré dans les calculs :honte:


sinon:
  • je suis volontaire pour reprendre le tutoriel, toujours avec la bibliothèque GMP.....mais en C car je ne maitrise pas le language python.Qu'en pense tu?

  • pourrai on (ou pourai-je ;) )avoir le code source du programme pour trouver U (le programme qui fait l'algorithme de Bézout), que tu a mis en ligne ici ? Ca m'aiderai pour mon TPE sur le cryptage(je suis un lycéen en première et je fait mon TPE sur le cryptage)

  • je n'arrive pas a instaler la librairie gmp sous linux.tu a une idée de pourquoi ca beuge?Image utilisateur


merci beaucoup :D


Edit: j'ai trouvé pourquoi ca beuge: il existe une macro dont(la macro "M4") dont GMP a besoin,mais qui n'existe pas par défaut sur linux :



donc dans ton code d'installation de la GMP sous linux il faut ajouter :

Code : Console
sudo apt-get install m4


normalement il vas vous demander votre mot de passe. si la macro est déjà installée,cela ne stoppe pas le code, mais ca affiche juste un message : voir cette capture d'écran

donc le code complet d'installation serai:

Code : Console
sudo apt-get install m4
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

Code : PHP
1
2
3
4
<?php

    $boss =(gusfl)?true:false;
?>

:ange:
 
Hors ligne LaurentDupuy # Posté le 24/04/2012 à 16:27:54

1/ Le terme "chiffrage" n'est pas du domaine de la cryptographie.
Chiffrage d'un programme politique, du chiffrage d'un plan de développement, du chiffrage d'un stock de marchandises ou du chiffrage du prix de revient d'une construction.
On en parle aussi dans le solfège (partitions musicales)

Source: wikipedia.org

2/ RSA n'est pas utilisé pour chiffrer des messages, mais pour chiffrer les clefs utilisées pour des algorihmes de chiffrement symétriques.

Voir tous les commentaires