Cliquez pour atteindre la page correspondante...

La sécurité sur le Net

 La cryptologie :
le RSA

Introduction

Législation
réglementation française
lois françaises
certification

Cryptologie :
à clés secrètes
à clés publiques

Stéganographie

Algorithme
 RSA

Signature électronique

 

R.S.A., acronyme de Rivest-Shamir-Adleman, a été inventé par Ron Rivest, Adi Shamir et Leonard Adleman d'où ce nom, en 1977 et le brevet de cet algorithme appartient à la société américaine RSA Data Security, propiété de Security Dynamics et de Public Key Parteners, (PKP à Sunnyvale, Californie, Etats-Unis). RSA est un algorithme à clé publique qui sert tant à la cryptographie qu'à l'authentification.

Le principe de RSA repose sur le fait qu'il est très difficile et très long de factoriser un très grand nombre en deux facteurs premiers alors que la multiplication de ces deux facteurs est courte.

Soient p  q deux nombres premiers, n = p.q, et soit e un entier premier à (p - 1)(q - 1). Alors il existe d tel que e.d  1 mod (p - 1)(q - 1), et , le système RSA travaille avec l’hypothèse qu’il est difficile d'obtenir p et q à partir de n.

La génération des clés

La première étape consiste à générer deux nombres premiers p et q très grands (de l'ordre de 100 chiffres) puis on trouve le nombre n facilement selon la relation n=p.q . Ensuite il nous faut trouver un entier e compris entre 2 et j(n). j(n) est la fonction indicatrice d'Euler, c'est en fait le nombre d'entiers inférieurs à n qui sont premiers avec lui, ici on a j(n)=(p-1)(q-1) ce qui se calcule simplement. Les nombres n et e forment ici notre clé publique que l'on notera [n,e]. Il nous faut calculer le nombre d qui sera nécessaire au décryptage.

Selon la théorie de RSA, nous devons avoir d tel que (e.d-1) soit divisible par j(n). Pour trouver d nous devons alors résoudre l'équation diophantienne d+k.j(n)=1 à l'aide de l'arithmétique. Comme e et j(n) sont premiers entre eux, le théorème de Bezout prouve qu'il existe d et k dans Z tel que e.d+k.j(n)=1. Donc après une série de calcul la clé privée d est trouvée et permet de décrypter les données.

Nous pouvons à présent rendre publique notre clé publique [n,e] et garder secrète notre clé privée d. Quant aux nombres p, q et j(n), on doit, soit les conserver secrets, soit les détruire car ils ne serviront plus.

Le cryptage

Pour crypter des données m, il faut commencer par fragmenter les données tel que m soit inférieur à n. Puis le chiffrement s'effectue par une simple opération mathématique, où c est le message crypté.

Le décryptage

Pour décrypter des données cryptées c, il nous faut effectuer l'opération , où d est la clé privée pour obtenir m qui correspond aux données en clair.

L'authentification

L'authentification d'un document, c'est le fait d'être sûr de l'identité de l'auteur d'un document. Cette authentification peut s'avérer indispensable pour la justice lors d'un litige sur un contrat par exemple. L'authentification se fait toujours sur un contrat papier par une signature manuscrite, à priori infalsifiable. Le problème de l'authentification d'un document "informatique", est l'impossibilité physique d'y apposer une signature manuscrite à sa fin. On va donc y apposer une signature "digitale". Pour ne pas être falsifiable, on va crypter cette signature par exemple avec l'algorithme RSA.

Pour bien prouver qu'un document a été composé par nous, il nous suffira de crypter par exemple notre nom, prénom et fonction ou n'importe quoi d'autre, avec notre clé privée (en théorie connue de nous seul). Ainsi, quiconque qui voudra vérifier l'auteur de ce document, n'aura qu'à utiliser notre clé publique pour le décryptage. Et si le décryptage fonctionne, cela veut bien dire que la signature a été "forgée" avec notre clé privée.

Complément : RSA99.pdf par Jean Berstel

Retour haut

Contact : securinet@free.fr

Dernière mise à jour :