Plan du site  
français  English
pixel
pixel

Articles - Étudiants SUPINFO

Chapitre 06 - Systèmes R.S.A. et El Gamal

Système R.S.A.

Cette partie sera consacrée à l'étude de l'algorithme de cryptographie asymétrique R.S.A., qui sous certaines conditions est le plus sécurisé au monde.

Objectif

Rappelons tout d'abord (voir premier chapitre de ce cours) qu'un système de chiffrement est dit asymétrique si la clé utilisée lors du chiffrement est différente de celle utilisée lors du déchiffrement. Un tel système est aussi qualifié de système de chiffrement à clé publique.

Les correspondants ont chacun une clé qu’ils gardent secrète et une clé dite publique qu’ils communiquent à tous. Pour envoyer un message, on le chiffre à l’aide de la clé publique du destinataire. Celui-ci utilisera sa clé secrète pour le déchiffrer.

On va dans la suite de cette partie présenter le premier algorithme de cryptographie asymétrique, développé en 1977 par Ronald Rivest (1947-), Adi Shamir (1952-) et Leonard Max Adleman (1945-). Il fut décrit dans leur article "A method for obtaining digital signatures and public-key cryptosystems", disponible par exemple ici.

Génération des clés

La construction des clés, il y en a deux puisque ce chiffrement est asymétrique, est assez technique et mérite donc un peu d'attention. Elle repose sur une bonne utilisation des nombres premiers, voir le quatrième chapitre de ce cours pour des généralités sur ceux-ci.

Clés du sytème R.S.A.

On commence par choisir deux nombres premiers p et q distincts.

On pose alors n = p q et m = ( p - 1 ) ( q - 1 ) .

On choisit ensuite d très grand tel que d soit premier avec m.

Enfin, on détermine c, l’inverse multiplicatif modulo m de d.

La clé publique sera le couple ( c , n ) et la clé secrète sera l’entier d.

[Note]

Plus les nombres premiers choisis seront grands, plus le système sera sécurisé. Voir à ce sujet la sous-partie 1.5.

L’exemple qui suit est celui proposé par les auteurs du système dans leur article.

Example 1.1. Des clés pour le système R.S.A.

Soient p = 47 et q = 59 .

On a donc n = p q = 47 × 59 = 2773 et m = ( p - 1 ) ( q - 1 ) = 46 × 58 = 2668 .

On choisit alors d premier avec 2668 par exemple d = 157 .

On calcule ensuite c l’inverse multiplicatif de 157 modulo 2668, à l’aide des coefficients de Bézout de 157 et 2668 : 157 × 17 + 2668 × ( - 1 ) = 1 . On trouve ainsi c = 17 .

Dans cet exemple, la clé publique est donc le couple ( 17 , 2773 ) et la clé secrète l'entier 157.


Puisque cette génération de clés est bien particulière, nous proposons un petit exercice au lecteur afin qu'il soit sûr de bien en avoir saisi le principe.

Exercice corrigé

1.1.

Soient p = 53 et q = 97 .

Montrer que l'on peut choisir d = 4279 . Calculer alors la valeur de c.

On a donc n = p q = 53 × 97 = 5141 et m = ( p - 1 ) ( q - 1 ) = 52 × 96 = 4992 .

Pour répondre à la question portant sur d, il suffit de montrer que d et m sont premiers entre eux. Or une simple application de l'algorithme d'Euclide prouve bien que PGCD ( 4992 , 4279 ) = 1 ,

Il reste alors à calculer l'inverse multiplicatif de d modulo m. Cela se fait comme toujours en calculant la relation de Bézout entre ces deux entiers : 4279 × 7 + 4992 × ( - 6 ) = 1 . On trouve ainsi c = 7 .

Chiffrement

Comme pour les algorithmes du chapitre précédent il convient au préalable d'associer à chaque caractère un entier. Voici la convention utilisée en général lors de l'utilisation du système R.S.A.

Convention de représentation des caractères

espace a b c d e f g h i j k l
00 01 02 03 04 05 06 07 08 09 10 11 12
m n o p q r s t u v w x y z
13 14 15 16 17 18 19 20 21 22 23 24 25 26

Dans toute la suite, on confondra donc un caractère et le nombre le représentant.

[Note]

On pourrait également utiliser une table de conversion plus complète, incluant les lettres minuscules et majuscules, les lettres accentuées ainsi que les différents signes de ponctuation. Ces autres caractères seraient alors numérotés à partir de 27.

Grâce à la convention précédente, le message à chiffrer est donc converti en une suite de chiffres.

Le R.S.A. aura un caractère polygrammique. On va ainsi découper cette suite de chiffres en blocs de mêmes longueurs. On ajoutera éventuellement des 0 à la fin si besoin est. Une contrainte importante est que la valeur numérique de chaque bloc doit être inférieure à n.

Nous pouvons maintenant présenter la formule de chiffrement, qui n'utilisera donc que la clé publique du destinataire d'un message.

Formule de chiffrement du R.S.A.

Soit ( c , n ) une clé publique.

Un bloc de chiffres x du message d'origine tel que x < n sera chiffré par un bloc de chiffres y vérifiant y x c [ n ] .

[Note]

Le message chiffré sera donc une suite de blocs de chiffres.

[Note]

C’est en particulier ce calcul de puissance qui rend cet algorithme très lent quand il est utilisé avec de grands nombres.

Une méthode pour calculer une puissance plus rapidement que celle naïve consistant à multiplier un nombre par lui même autant de fois que son exposant est celle de l’exponentiation rapide. Voir cours 1ADS à ce sujet.

Poursuivons l'exemple de Rivest, Shamir et Adleman.

Example 1.2. Un chiffrement R.S.A.

On reprend la clé publique ( c , n ) = ( 17 , 2773 ) .

Imaginons que l'on veuille chiffrer "its all greek to me".

On convertit ce message en une suite de chiffres

09201900011212000718050511002015001305

La valeur numérique de chacun des blocs devant être inférieure à n = 2773 , on peut donc faire des blocs de quatre chiffres

0920 1900 0112 1200 0718 0505 1100 2015 0013 0500

A noter que l’on a rajouté deux 0 à la fin pour que le dernier bloc soit aussi de quatre chiffres.

Le premier bloc x = 0920 est alors chiffré en y 920 17 948 [ 2773 ] .

On procède de même pour les autres blocs, et l'on obtient

0948 2342 1084 1444 2263 2390 0778 0774 0219 1655

[Note]

Ce message est intraduisible littéralement en français. Nous dirions plutôt "c’est du chinois".

Déchiffrement

Le destinataire d'un message chiffré utilisera lui sa clé secrète pour retrouver le message d'origine.

Formule de déchiffrement du R.S.A.

Soit ( c , n ) une clé publique et d la clé secrète correspondante.

Un bloc de chiffres y du message chiffré correspondra au bloc de chiffres x du message d'origine vérifiant x y d [ n ] .

[Note]

Une fois la suite de chiffres initiale reconstituée, il ne restera plus qu’à la convertir en lettres.

La preuve suivante mérite un minimum d’attention, bien que les arguments utilisés soient relativement élémentaires. C'est ce qui fait d'ailleurs en partie la beauté des mathématiques, des choses simples conduisent à des résultats très puissants.

L'argument clé sera le petit théorème de Fermat, étudié dans le quatrième chapitre de ce cours.

Démonstration de la formule de déchiffrement

Le but est de montrer que si l'on applique la formule de déchiffrement à un y de la forme y x c [ n ] , alors le résultat est x. Cela revient à vérifier que x c d x [ n ] .

On va commencer par prouver que x c d x [ p ] . Par hypothèse on a c d 1 [ m ] , ainsi il existe un entier k tel que c d = 1 + k m . On va alors distinguer deux cas, selon que x soit ou pas divisible par p :

  • Si x n'est pas divisible par p :

    • D’après le petit théorème de Fermat, x p - 1 1 [ p ] .

    • On a alors x ( p - 1 ) ( q - 1 ) 1 [ p ] , i.e. x m 1 [ p ] , et par suite x k m 1 [ p ] .

    • D'où finalement x c d x 1 + k m x x k m x [ p ] .

  • Si x est divisible par p :

    • On a bien sûr aussi x c d divisible par p.

    • Ainsi x c d 0 [ p ] et x 0 [ p ] donc x c d x [ p ] .

Dans les deux cas on a obtenu ce que l'on souhaitait, i.e. x c d x [ p ] .

On montrerait de même que x c d x [ q ] .

On a donc prouvé que p | ( x c d - x ) et q | ( x c d - x ) .

Il est de plus immédiat que PGCD ( p , q ) = 1 , puisque ces deux nombres sont premiers.

D'après le corollaire du théorème de Gauss (cf. second chapitre de ce cours), on a alors p q | ( x c d - x ) , i.e. n | ( x c d - x ) . Ce qui signifie exactement que x c d x [ n ] . Q.E.D.

Terminons maintenant l'exemple de Rivest, Shamir et Adleman.

Example 1.3. Un déchiffrement R.S.A.

Rappelons que la clé publique était le couple ( c , n ) = ( 17 , 2773 ) et la clé secrète l'entier d = 157 .

Déchiffrons donc le message

0948 2342 1084 1444 2263 2390 0778 0774 0219 1655

Le premier bloc y = 0948 est alors déchiffré en x 948 157 920 [ 2773 ] . Ce bloc converti en lettres donne "it" qui était bien le début de notre message d'origine.

Il ne resterait plus qu'à faire de même pour les autres blocs.


Décryptement

La sécurité du R.S.A. repose principalement sur l’incapacité à l’heure actuelle de reconstituer en un temps raisonnable la clé secrète d connaissant la clé publique ( c , n ) .

Cette opération nécessite en effet de factoriser n en n = p q . Ceci est possible mais les délais de calculs sont énormes dès que n est assez grand.

On arrive pour l’instant à factoriser des nombres de 230 chiffres (clés de 768 bits). Mais l’on préconise pour des messages très sensibles d’utiliser le R.S.A. avec des nombres n de plus de 600 chiffres (clé de 2048 bits), dont on estime que l’on saura les factoriser en 2079.

[Note]

Ce délai de 2079 est donné en considérant que la puissance des ordinateurs double tous les 18 mois. C’est la fameuse loi de Moore. Il pourra cependant être considérablement réduit si on découvre un algorithme de factorisation plus puissant que ceux utilisés actuellement. Cette découverte a peut-être d’ailleurs déjà été effectuée dans le plus grand secret.

D'autres attaques sont possibles en cas de mauvaise utilisation du R.S.A. En particulier si l'on intercepte le même message envoyés à des destinataires différents. Une subtile utilisation du théorème des restes chinois (voir troisième chapitre) permet alors de reconstituer le message d'origine. Cette attaque dite de Hastad peut cependant être déjouée en introduisant des caractères arbitraires différents pour chaque destinataire.

[Note]

Le lecteur curieux trouvera ici d'autres attaques connues contre le R.S.A.

Système El Gamal

Nous allons dans cette partie présenter le système El Gamal, qui est un autre algorithme de cryptographie asymétrique. Il est certes moins puissant que le R.S.A. mais son fonctionnement est plus rapide, ce qui lui confère un certain intérêt.

Objectif

Le but principal est donc le même que celui de la première partie, à savoir implémenter un système de chiffrement à clé publique.

L'algorithme décrit dans la suite est l'oeuvre de Taher Elgamal (1955-). Il est en particulier utilisé dans certains logiciels libres de messagerie. Le lecteur trouvera ici l'article original dans lequel ce système fut présenté. Il s'intitule "A Public Key Cryptosystem and a Signature Scheme Based on Discrete Logarithms".

Nous ne présenterons qu'une version particulière de ce système, basée sur l'unique utilisation des nombres entiers. Il en existe une version plus générale, reposant sur la notion de groupe cyclique.

Génération des clés

La construction des deux clés repose comme pour le R.S.A. sur le concept de nombre premier.

Clés du système El Gamal

On commence par choisir un nombre premier p.

On choisit ensuite deux entiers a et m tels que 0 a p - 2 et 0 m p - 1 .

On pose alors n m a [ p ] .

La clé publique sera le triplet ( p , m , n ) et la clé secrète sera l'entier a.

Donnons de suite un exemple, pour bien fixer les idées.

Example 1.4. Des clés pour le système El Gamal

Soit p = 661 .

Choisissons a = 7 et m = 23 .

On a alors n m a [ p ] 23 7 [ 661 ] 566 [ 661 ] .

Dans cet exemple, la clé publique est donc le triplet ( 661 , 23 , 566 ) et la clé secrète l'entier 7.


Chiffrement

On conserve la même convention de représentation des caractères en nombres que pour le système R.S.A. On convertit de la même façon le message à chiffrer en une suite de chiffres.

Le système El Gamal sera lui aussi polygrammique, donc on découpera cette suite de chiffres en blocs de mêmes longueurs, avec ajouts éventuels de 0 à la fin si besoin est. Une contrainte importante est que la valeur numérique de chaque bloc doit être inférieure à p.

La formule de chiffrement n'utilise bien sûr que la clé publique du destinataire.

Formule de chiffrement El Gamal

Soit ( p , m , n ) une clé publique.

On commence par choisir un entier k aléatoirement tel que 0 k p - 1 .

Un bloc de chiffres x du message d'origine tel que x < p sera alors chiffré par un couple de blocs de chiffres ( y 1 , y 2 ) vérifiant

y 1 m k [ p ] et y 2 x n k [ p ]
[Note]

Le message chiffré sera donc une suite de couples de blocs de chiffres.

On perçoit ici l'un des défauts de cet algorithme, le message chiffré est deux fois plus long que le message d'origine.

Poursuivons l'exemple de la sous-partie précédente.

Example 1.5. Un chiffrement El Gamal

On reprend la clé publique ( p , m , n ) = ( 661 , 23 , 566 ) .

Cherchons à chiffrer "supinfo".

On convertit ce message en une suite de chiffres

19211609140615

La valeur numérique de chacun des blocs devant être inférieure à p = 661 , on peut donc faire des blocs de trois chiffres

192 116 091 406 150

A noter que l’on a rajouté un 0 à la fin pour que le dernier bloc soit aussi de trois chiffres.

On choisit aléatoirement l'entier k = 13 .

Le premier bloc x = 192 est alors chiffré en

y 1 23 13 105 [ 661 ] et y 2 192 × 566 13 237 [ 661 ]

On procède de même pour les autres blocs, et l'on obtient

( 105 , 237 ) ( 105 , 515 ) ( 105 , 102 ) ( 105 , 150 ) ( 105 , 495 )

[Note]

Dans cet exemple, nous avons pour simplifier la présentation utilisé le même nombre aléatoire k pour tous les blocs. Pour une meilleure sécurité il faudrait bien sûr en changer à chaque fois.

Déchiffrement

L'utilisation de sa clé secrète va permettre au destinataire d'un message de le déchiffrer.

Formule de déchiffrement El Gamal

Soit ( p , m , n ) une clé publique et a la clé secrète correspondante.

Un couple de blocs de chiffres ( y 1 , y 2 ) du message chiffré correspondra au bloc de chiffres x du message d'origine vérifiant x y 1 p - 1 - a y 2 [ p ] .

[Note]

Une fois la suite de chiffres initiale reconstituée, il ne restera plus qu’à la convertir en lettres.

Comme pour le R.S.A., le petit théorème de Fermat va permettre de justifier la relation de déchiffrement.

Démonstration de la formule de déchiffrement

Le but est de montrer que si l'on applique la formule de déchiffrement à un couple ( y 1 , y 2 ) de la forme

y 1 m k [ p ] et y 2 x n k [ p ]

alors le résultat est x.

Par construction de la clé on a également n m a [ p ] .

Si l'on remplace y 1 , y 2 et n dans la formule de déchiffrement par les expressions précédentes, on obtient

y 1 p - 1 - a y 2 ( m k ) p - 1 - a x n k m k ( p - 1 - a ) x m k a m k ( p - 1 ) x [ p ]

Or, d'après le petit théorème de Fermat, m p - 1 1 [ p ] . Donc m k ( p - 1 ) 1 [ p ] , et par suite m k ( p - 1 ) x x [ p ] . Q.E.D.

On peut dès lors terminer l'exemple des sous-parties précédentes.

Example 1.6. Un déchiffrement El Gamal

Rappelons que la clé publique était le triplet ( p , m , n ) = ( 661 , 23 , 566 ) et la clé secrète l'entier a = 7 .

Déchiffrons donc le message

( 105 , 237 ) ( 105 , 515 ) ( 105 , 102 ) ( 105 , 150 ) ( 105 , 495 )

Le premier couple de blocs ( y 1 , y 2 ) = ( 105 , 237 ) est alors déchiffré en x 105 661 - 1 - 7 × 237 192 [ 661 ] . Ce qui était bien le début de notre message.

Il ne resterait plus qu'à faire de même pour les autres blocs.


Décryptement

Comme pour le R.S.A., la sécurité du système El Gamal repose sur la difficulté de calculer la clé secrète a alors que l'on connait la clé publique ( p , m , n ) .

Cette opération revient en effet à retrouver la valeur de a à partir de celle de n m a [ p ] . Ce problème, connu sous le nom de calcul du logarithme discret, est certes résolvable mais en un temps relativement long.

A l'heure actuelle, il n'existe par exemple pas d'algorithme à complexité polynomiale effectuant cette tâche.

A propos de SUPINFO | Contacts & adresses | Enseigner à SUPINFO | Presse | Conditions d'utilisation & Copyright | Respect de la vie privée | Investir
Logo de la société Cisco, partenaire pédagogique de SUPINFO, la Grande École de l'informatique, du numérique et du management Logo de la société IBM, partenaire pédagogique de SUPINFO, la Grande École de l'informatique, du numérique et du management Logo de la société Sun-Oracle, partenaire pédagogique de SUPINFO, la Grande École de l'informatique, du numérique et du management Logo de la société Apple, partenaire pédagogique de SUPINFO, la Grande École de l'informatique, du numérique et du management Logo de la société Sybase, partenaire pédagogique de SUPINFO, la Grande École de l'informatique, du numérique et du management Logo de la société Novell, partenaire pédagogique de SUPINFO, la Grande École de l'informatique, du numérique et du management Logo de la société Intel, partenaire pédagogique de SUPINFO, la Grande École de l'informatique, du numérique et du management Logo de la société Accenture, partenaire pédagogique de SUPINFO, la Grande École de l'informatique, du numérique et du management Logo de la société SAP, partenaire pédagogique de SUPINFO, la Grande École de l'informatique, du numérique et du management Logo de la société Prometric, partenaire pédagogique de SUPINFO, la Grande École de l'informatique, du numérique et du management Logo du IT Academy Program par Microsoft, partenaire pédagogique de SUPINFO, la Grande École de l'informatique, du numérique et du management

SUPINFO International University
Ecole d'Informatique - IT School
École Supérieure d'Informatique de Paris, leader en France
La Grande Ecole de l'informatique, du numérique et du management
Fondée en 1965, reconnue par l'État. Titre Bac+5 certifié au niveau I.
SUPINFO International University is globally operated by EDUCINVEST Belgium - Avenue Louise, 534 - 1050 Brussels