Vocabulaire et algorithmes
de la cryptographie
Présentation des principaux algorithmes de la cryptographie: RSA et Diffie-Hellman, ainsi que des concepts de bases du chiffrement.
Cette introduction vise à présenter,
pour tous ceux qui, nouveaux approchants du domaine, s'intéressent
à la cryptographie informatique, les principaux concepts,
méthodes, enjeux et algorithmes de ce domaine essentiel et
vaste.
La cryptographie (du grec kruptos, caché et graphein,
écrire) protège les communications, notamment par e-mail,
et répond à différents besoins : la confidentialité, le contrôle
d'accès, l'intégrité des données, l'identification ou la non répudiation.
Ses applications sont multiples : échanges de mails, conversations
téléphoniques, transactions bancaires, paiements à distance
Un peu de vocabulaire
La clef est l'outil utilisé pour chiffrer et déchiffrer un
code. Dans le cadre d'une cryptographie symétrique, la même
clef est utilisé pour chiffrer et déchiffrer. La cryptographie
asymétrique est plus évoluée : Les clefs de chiffrement et de
déchiffrement sont différentes. L'utilisateur possède une clef privée,
qu'il conserve, et une clef publique, qu'il distribue. Il faudra
chiffrer un message avec sa clef publique pour lui écrire. Il le
déchiffrera avec sa clef privée.
Tout système de cryptage est composé d'un algorithme de codage,
description explicite de la manière dont un calcul particulier doit
être effectué. Son efficacité peut être mesurée au nombre d'étapes
nécessaires au déchiffrage du code sans en connaître la clef, et
à la longueur de ces étapes.
Dans les algorithmes symétriques, on distingue le chiffrement
par bloc et le chiffrement continu. Dans le premier,
un bloc est un sous-ensemble du message en clair, remplacé par un
groupe de caractères de taille égale ou plus importante, appartenant
à un ou plusieurs alphabets de chiffrement. Pour le second, chaque
unité (lettre dans le cas d'un e-mail) du message en clair est codée
une par une.
Clefs asymétriques : les algorithmes
de factorisation
Le RSA, du nom de ses inventeurs Rivest Shamir et Adleman,
est un des algorithmes à clef publique les plus utilisés.
Le codage RSA repose sur la factorisation d'un entier. Soient p
et q deux entiers premiers distincts, il est facile de calculer
leur produit n = pq. Toutefois, étant donné n, il est difficile
de retrouver p et q (factorisation). Partons donc
de la formule suivante :
n = pq
Pour créer une clef publique, il faut trouver un entier
impair e premier avec le nombre d'entiers inférieurs
à n qui sont premiers avec lui, ce dernier nombre
déterminé grâce à la fonction indicatrice
d'Euler :
E(n) = (p - 1) ( q - 1)
e est donc premier avec (p-1)(q-1). Les nombres e et
n forment la clé publique, notée (e,n).
Pour créer la clef privée, il faut calculer le nombre
d nécessaire au déchiffrement, tel que :
e.d = 1 mod E(n)
d est la clef privée. Il faut maintenant divulguer (e,n)
et conserver p, q et E(n) secrets ou les détruire
car ils ne serviront plus.
Le chiffrement du message m s'effectuera selon la formule
: c = (m^e) mod (n)
Le déchiffrement pour récupérer m s'effectuera
selon la formule : m = (c^d) mod (n)
La taille de la clef doit excéder 1024 bits (c'est à dire 10^300)
afin de garantir une bonne marge de sécurité. Une clef de 2048 bits,
par exemple, convient bien.
Le système de chiffrement Rabin est proche du RSA. La différence
est que Rabin utilise un exposant pair (comme 2) au lieu d'exposants
impairs pour le RSA.
Clefs asymétriques : la classe des
logarithmes discrets
Les logarithmes discrets se basent sur la difficulté de retrouver
n dans la formule :
h = g^n
où g et h sont des entiers donnés, n
un entier.
Le Diffie-Hellman est le protocole à logarithme discret
le plus utilisé pour l'échange de clef, si deux parties souhaitent
communiquer sans pour autant posséder de clef secrète commune, et
donc sans pouvoir utiliser de systèmes de chiffrement à clef. Ce
protocole permet de construire une clef secrète commune sur un réseau
de communication peu sûr. On le considère comme plus sûr
encore que RSA.
Pour ce faire, chacune des deux parties choisit une valeur privée,
respectivement a et b. Ces valeurs sont modifiées
avec des paramètres communs. Deux valeurs publiques sont
alors produites et échangées :
A=(g^a) mod p et B=(g^b) mod p
où g et p sont fixés au préalable
en faisant l'objet d'un accord entre les deux parties. Idéalement,
p doit être grand pour une meilleure sécurité.
Chacun calcule ensuite de la manière suivante :
k(a,b) = (B^a) mod p et k(b,a) = (A^b)
mod p
La clef secrète commune k est donc dégagée
car :
k(a,b) = k(b,a) = k
La sécurité de ce protocole repose sur le fait qu'il
est quasi-impossible, compte tenu des moyens existants, de calculer
k = (g^ab) mod p, en possédant
les deux valeurs publiques pré-citées (A et
B), si p est suffisamment grand.
Il existe d'autres algorithmes basés sur les logarithmes
discrets, utilisés en conjonction avec Diffie-Hellman, ou
l'étendant. Nous les laissons de côté dans cet
article d'introduction.
Les logarithmes à clefs symétriques
Mentionnons les S-Boxes, qui sont des tables de substitution
conçues en suivant des principes mathématiques précis que
nous ne détaillons pas ici, ou le réseau
de Feistel, qui permet de coder des blocs d'un message en
appliquant des transformations de ronde (fonction de n bits
à n bits) pour produire une fonction réversible (bijection)
de 2n bits à 2n bits.
Nous tenterons, dans de futurs articles, de donner certains exemples
d'implémentation de ces différentes technologies,
en utilisant divers langages, d'examiner, sous cette lumière,
les outils du marché, ou encore d'étudier la fiabilité
des algorithmes.
[Serge Descombes
27 août 2002
, JDNet]
|