Cryptographie : Signature numérique et Chiffrement

Algorithmes de cryptographie asymétrique

RSA

Le RSA est encore le système cryptographique à clé publique le plus utilisé de nos jours.
La solidité de RSA repose uniquement sur la difficulté de décomposer le nombre n (public) en deux nombres premiers : Dit autrement, il suffit de résoudre l'équation n = p.q
Le record établi en 1999, avec l'algorithme le plus performant et des moyens matériels considérables (CRAY4), est la factorisation d'un entier à 155 chiffres (soit une clé de 512 bits, 2512 étant proche de 10155).
Il faut donc, pour garantir une certaine sécurité, choisir des clés plus grandes : les experts recommandent des clés de 768 bits pour un usage privé, et des clés de 1024, voire 2048 bits, pour un usage sensible. Si l'on admet que la puissance des ordinateurs double tous les 18 mois (loi de Moore), une clé de 2048 bits devrait tenir jusqu'en ... 2079.

Choix de la clef

Alice choisit deux entiers premiers p et q (Ici on prend des nombres à 7 bits soit inférieurs à 27 (128)) et fait leur produit n = p·q.
Puis elle choisit un entier e premier avec (p-1)·(q-1).
Enfin, elle publie dans un annuaire, par exemple sur Internet, sa clef publique: (RSA, n, e).
p=53 q=97 donc n=5141 e=7 et d=4279

Chiffrement

Bob veut donc envoyer un message à Alice. Il cherche dans l'annuaire la clef de chiffrement qu'elle a publiée.
Il sait maintenant qu'il doit utiliser le système RSA avec les deux entiers 5141 et 7.
Il transforme en nombres son message en remplaçant par exemple chaque lettre par son rang dans l'alphabet.
"JEVOUSAIME" devient : "10 05 22 15 21 19 01 09 13 05".
Puis il découpe son message chiffré en blocs de même longueur (En partant de la droite) représentant chacun un nombre le plus grand possible tout en restant plus petit que n.
Cette opération est essentielle, car si on ne faisait pas des blocs assez longs (par exemple si on laissait des blocs de 2 dans notre exemple), on retomberait sur un simple chiffre de substitution que l'on pourrait attaquer par l'analyse des fréquences.
Son message devient : "010 052 215 211 901 091 305"
Un bloc B est chiffré par la formule C = Be mod n, où C est un bloc du message chiffré que Bob enverra à Alice.
Après avoir chiffré chaque bloc, le message chiffré s'écrit : "0755 1324 2823 3550 3763 2237 2052".

Déchiffrement

Alice calcule à partir de p et q, qu'elle a gardés secrets, la clef d de déchiffrage (c'est sa clef privée).
Celle-ci doit satisfaire l'équation e·d mod ((p-1)(q-1)) = 1. Ici, d=4279
Chacun des blocs C du message chiffré sera déchiffré par la formule B = Cd mod n. Elle retrouve : "010 052 215 211 901 091 305"
En regroupant les chiffres deux par deux et en remplaçant les nombres ainsi obtenus par les lettres correspondantes, elle sait enfin que Bob l'aime secrètement, sans que personne d'autre ne puisse le savoir.

Algorithme de Diffie-Hellman

Cette algorithme est très simple pour l'échange des clefs et s'utilise à la place de RSA :
Soient 2 personnes A et B désirant communiquer sans utiliser une clef secrète.
Pour cela ils se mettent d'accord sur 2 nombres g et n tels que n soit supérieur à g et g supérieur à 1, et cela sur un canal non sécurisé (il faut que n soit grand: de l'ordre de 512 ou 1024 bits pour que l'échange des clefs soit sécurisé).
Ils prennent chacun chez eux un nombre aléatoire :
Ainsi le pirate peut intercepter X, et Y mais il lui est très très difficile d'en déduire x et y (c'est sur ce principe que repose la sécurité de l'algorithme).
Une fois dans son coin, A calcule k=Yx mod n et B calcule k'=Xy mod n.
Si l'on regarde de plus près on voie quelque chose de très intéressant: k=k'=gxy mod n.
Ainsi, A et B ont réussi à créer un clef privée dont ils sont les seuls détenteurs...
et le pirate malgrès la vision qu'il a eut de l'échange ne peut calculer la clef privée...
L'échange des clefs ayant fonctionné A et B peuvent communiquer par un bête algorithme à clef privée.

PGP

Le PGP (Pretty Good Privacy) est un algorithme de chiffrement à destination des particuliers.
Il est surtout utilisé pour chiffrer des messages envoyés par courrier électronique, même s'il peut aussi être utilisé pour chiffrer tous les fichiers.
PGP a été mis au point en 1991 par Philip Zimmermann, et ceci lui valut divers problèmes avec la justice.
D'une part, le PGP utilise l'algorithme RSA, qui est breveté aux Etats-Unis.
D'autre part, la NSA a tout fait pour tenter d'empêcher la diffusion du PGP.
La plainte de la NSA a été classée sans suite par le gouvernement début 1996 sous la pression des internautes qui se sont mobilisés pour défendre Zimmermann.

PGP utilise le meilleur de la cryptographie symétrique (rapidité du chiffrement) et de la cryptographie asymétrique (sécurité de l'échange de clés).

Il fonctionne suivant le principe suivant :
  1. Compression : le texte à envoyer est compressé. Cette étape permet de réduire le temps de transmission des données, et améliore également la sécurité. En effet, la compression détruit les modèles du texte (fréquences des lettres, mots répétés). Et on sait que ces modèles sont souvent utilisés dans les analyses cryptographiques.
  2. Chiffrement du message : un mot de passe aléatoire est générée (On parle ici de clé de session), et le message est chiffré par un algorithme symétrique à l'aide de cette clé de session. L'algorithme utilisé a varié au cours du temps : il s'agissait au début de DES, puis de CAST.
  3. Chiffrement de la clé de session : la clé de session est chiffrée en utilisant la clé publique du Destinataire (et l'algorithme RSA).
  4. Envoi et réception du message : l'expéditeur envoie le couple message chiffré / clé de session chiffrée au Destinataire. Celui récupère d'abord la clé de session, en utilisant sa clé privée, puis il déchiffre le message grâce à la clé de session.
Le PGP implémente aussi les fonctions de certificat et de signature électroniques. Il n'y a pas d'autorité centrale de certification, mais un grand rôle joué à la proximité sociale : les amis de mes amis sont mes amis !
En 2006, Zimmermann a créé Zfone, un logiciel de chiffrement de communication de téléphonie sur Internet au standard ouvert SIP, fonctionnant en P2P.