Le cryptosystème RSA 1

Le cryptosystème RSA (partie 1)

Préambule

Il existe sur internet de nombreux articles sur le cryptosystème RSA, je ne prétends ni les remplacer ni réaliser un article de meilleure qualité. Je souhaite uniquement réaliser une présentation différente, j'espère qu'elle pourra éclairer le lecteur sur un système de cryptographie paradoxalement très simple et complexe. Simple car il n'est pas nécessaire d'être mathématicien pour en comprendre le fonctionnement et complexe car les notions mises en jeu et la taille des nombres manipulés sont colossaux. Notamment les nombres premiers qui sont aux limites de nos connaissances.

Pour les plus réfractaires au mathématiques, sachez qu'il est tout de même nécessaire d'avoir quelques connaissances basiques. Pour le reste je tenterais d'expliquer ce qui peut l'être simplement.

Toutes les définitions ne seront pas formalisées afin de ne pas alourdir l'article de concepts mathématiques qui pourraient sembler un peu lourds aux moins « matheux ».

L'informatique, c'est des maths !

Pour s'en convaincre il suffit de se plonger dans histoire de cette jeune discipline pour se rendre compte que la majorité des grands noms de l'informatique étaient des mathématiciens (Turing, Von Neumann ...)

De nombreux cryptosystèmes font intervenir des notions mathématiques avancées. Ainsi pour le RSA les pré-requis suivants seraient nécessaires :

• calcul du pgcd
• arithmétique des nombres premiers (dans N)
• classe d'équivalences (théorie des groupes)
• arithmétique modulaire
• résolution de systèmes congruentiels d'équations diophantiennes
• théorème de Bézout
• algorithme d'Euclide étendu
• et quelques autres notions.... ;-)

Je ne m'attacherais pas à expliciter ces notions qui dépasseraient très largement le cadre de cet article. Cependant si la demande m'en était faite, je réaliserais un article dédié avec plaisir.

Il est tout de même important de connaître la notion de congruence.

Lorsque l'on dit qu'un nombre a est congru à b modulo n. Cela signifie que le reste de la division euclidienne (celle que l'on apprend à l'école primaire) de a par n est égal à celui de b par n et on écrit a = b (mod n). Par exemple :

le reste de la division de 10 par 3 est 1 (10/3= 3*3 + 1)

et le reste de la division de 1 par 3 est également 1 (1/3 = 0*3 + 1)

donc 10 = 1 (mod 3)

Dit autrement a-b = kn (avec k entier) soit la différence de a par b est divisible par n.

simplissime non ?

Dans la suite de l'article nous utiliserons n=26, pour les 26 lettres de l'alphabet (nous nous placerons donc dans l'anneau( Z/26Z, + , . ) pour les matheux), ainsi si les lettres sont numérotées a=0, b=1, c=2 …..z=25 pour des valeurs supérieures à 25 nous utiliserons la congruence. Ainsi :

26 = 1 (mod 26) , 27 = 2 (mod 26), 28 = 3 (mod 26) par exemple 0, 26, 52, …, 2600, … seront équivalents à la lettre a.

1. LA CRYPTOGRAPHIE

1. introduction

Avant d'aborder le RSA il est intéressant de présenter ce qu'est la cryptographie ainsi que quelque-uns des algorithmes les plus utilisés par le passé.

La cryptographie a pour but de transmettre un message entre deux personnes de manière sure et confidentielle par le biais d'un canal non sécurisé. Traditionnellement l'émetteur et le destinataire du message sont appelés Alice et Bob. La méchante et fallacieuse personne interceptant les communications est nommée Oscar.(toute ressemblance avec des personnes existantes ou ayant existé n'est que pure coïncidence ;-) )

Tout le problème se résume donc à la question suivante : Comment Alice et Bob peuvent-ils communiquer sans qu'Oscar ne puisse ni connaître le contenu du message ni le falsifier ?

Répondre à cette question de manière formelle et définitive n'est pas compliquée. C'est impossible dans l'état actuel des connaissances !

Tout système de cryptographie peut être mis à mal et tout message peut être déchiffré. Comment faire dans ce cas ? Sans toutefois rendre un message indéchiffrable, il est possible de faire en sorte que le temps et les ressources nécessaires soient tellement grands qu'il ne soit pas possible de le faire, à l'échelle d'une, deux ou quelques milliers de vies humaines.

Que ce soit pour des raisons civiles ou militaires, chiffrer (c'est le terme que nous utiliserons ici, car comme nous le verrons tout message n'est qu'une suite de nombres) est primordial et le chiffrement a été utilisé très tôt dans l'histoire.

Tout message peut être représenté par des chiffres. Un texte peut, par exemple être représenté par le numéro d'ordre des lettres de l'alphabet (a=0, b=1, c=2 …), une image par les trois couleurs de chaque pixel ...etc. Le cœur du problème est bien de transformer des chiffres pour qu'ils ne puissent plus donner d'indication sur le contenu. Dans un souci de simplicité des explications, nous considérerons que tous les messages sont sous forme de texte, plus facilement représentable ici, mais nous pourrions faire de même avec des suites de chiffres, ou de notes de musique ….

2. Cryptosystème

Qu'est ce qu'un système de cryptographie ?

Une définition formelle peut être la suivante :

il s'agit d'un quintuplet (A,B,K,C,D) où :

• A est l'ensemble (fini) des éléments composant le message clair
• B est l'ensemble (fini) des éléments composant le message chiffré
• K est l'espace des clés possibles
• C est l'ensemble des applications de chiffrement
• D est l'ensemble des applications de déchiffrement

Nous appelons ce quintuplet « cryptosystème ».

Pour chiffrer un message une application (ou plusieurs) utilise une clé, et réciproquement pour déchiffrer le message.

3. clés publiques et clés privées

Jules César utilisait le protocole de chiffrement suivant :

La ligne du bas remplace celle du haut :

a

b

c

d

e

f

g

h

i

j

k

l

m

n

o

p

q

r

s

t

u

v

w

x

y

z

Y

W

U

S

Q

O

M

K

Z

G

E

C

A

B

D

F

H

J

L

N

P

R

T

V

X

I

Les deux ligne ci-dessus sont une clé de chiffrement (et de déchiffrement).

L'application de chiffrement est la substitution des lettres de la première ligne par celles de la seconde et l'application de déchiffrement est la substitution inverse.

Ainsi le message « l attaque aura lieu demain » devient :

C YNNYHPQ YPJY CZQP SQAYZB

Ce type de cryptosystème est un chiffrement par substitution. Ce codage peut paraître simple et rudimentaire mais le nombre de substitutions possible est de 26! soit 403291461126605635584000000 possibilités (un peu plus de 4.10^26) . Quand on sait qu'il faut une vie entière pour compter jusqu'à 10^9 ….

Et encore l'exemple précédent ne tient pas compte des lettres accentuées ni de la casse...

Jules César pouvait dormir sur ses deux oreilles … mais aujourd'hui avec les ordinateurs, capables non seulement de réaliser des comparaisons de manière très rapide mais aussi d'analyser la fréquence d'apparition de chaque lettre, ce type de cryptosystème serait mis à mal très rapidement. Nous verrons par la suite des systèmes plus robustes.

Revenons à notre clé. Dans un cryptosystème de ce type il est évident que certains éléments doivent rester secrets, bien entendu le texte clair, mais aussi la clé. Si Alice souhaite envoyer un message à Bob, il est donc nécessaire qu'Alice et Bob connaissent la clé sans qu'Oscar n'en ait connaissance.

Ce problème est épineux car il nécessite un canal de communication sûr afin de donner cette précieuse information, au moins une fois.

Bien entendu ceci n'est valable que si la clé utilisée par l'application de chiffrement est identique à celle de déchiffrement. Dans le cas contraire il n'est pas nécessaire de communiquer la clé de déchiffrement.

Dans ce cas, où la clé qui sert à chiffrer est la même que celle qui sert à déchiffrer, elle doit être secrète. Il s'agit donc d'une clé privée et symétrique. Lorsque l'on ne peut pas communiquer la clé, il est alors possible d'utiliser un couple clé privé/clé publique. On parle alors de chiffrement asymétrique, le RSA fait parti de cette famille.

4. quelques cryptosystèmes (à clé privé)

• Par décalage

L'un des plus naturels est le chiffrement par décalage. Il suffit de faire correspondre un numéro (a= 0, b=1, c= 2 …) à chaque lettre. La clé est dans ce cas un nombre qui correspond au décalage (modulo n) des lettres. Par exemple avec une clé k=5 la lettre a = 0 correspond à 0+5 soit f, la lettre z=25 correspond à 25+5 = 4 (mod 26) soit la lettre e.
Si l'on nomme C la clé et L la lettre à chiffrer, l'application de chiffrement est donc L+C (mod26) et celle de déchiffrement est L-C (mod 26).
Les fonctions de chiffrement et de déchiffrement sont bijectives, donc tout message chiffré peut être déchiffré et inversement.
Le nombre de clé possible est seulement de 26, donc une analyse (on parle alors de cryptanalyse) permet de trouver facilement la clé.

• Chiffrement affine

Ce protocole de chiffrement utilise les propriétés d'inversibilité des éléments d'un anneau Z_n ( le symbole « _ » signifiant « indice »). Cette phrase vous donnera peut être mal à la tête, donc je ne détaillerais la méthode permettant de déchiffrer. Il s'agit en fait de l'utilisation d'une fonction affine (type ax + b) permettant de chiffrer et de sa fonction inverse permettant de déchiffrer.

Ce cryptosystème est un cas particulier du chiffrement par substitution, il permet d'obtenir une clé plus « compacte » et qui peut être traité de manière automatisée.

• Chiffrement de Vigénère

Le chiffre inventé par Blaise Vigénère (XVI°) est un chiffrement poly-alphabétique. Il applique à chaque caractère un décalage différent, grâce à un mot ou une phrase qui sert de clé. Cette technique est plus robuste que les précédentes car il utilise des clés plus longues (notamment plus longues que celles de César). Cependant une analyse de la longueur de clé (par la méthode de l'indice de coïncidence par exemple) puis une analyse des répétitions permet de cryptanalyser.

La fiabilité de la méthode repose sur la longueur de la clé, (et du texte).

Une variante consiste a créer une clé de la taille du texte, donnant ainsi un chiffrement extrêmement fiable, mais difficile à mettre en œuvre.

Si Alice veut transmettre un message à Bob elle devra le chiffrer et envoyer à Bob une clé de la même taille que le texte (donc souvent à usage unique) par un canal sûr, donc autant envoyer directement le message par ce canal !

Tous ces cryptosystèmes sont uniquement des exemples historiques (Vigénère était utilisé par les Allemands durant la seconde guerre mondiale à l'aide d'une machine appelée « Enigma »), il sont aujourd'hui dépassés par les capacités des ordinateurs (ou réseaux d'ordinateurs) et surtout par les analyses statistiques des langues.

Cependant d'autres cryptosystèmes à clé privé sont mis en œuvre de nos jours, je pourrais éventuellement rédiger un article si une demande est faite (par le biais de commentaires par exemple)

La suite de l'article sur le RSA sera publiée prochainement...