RSA ?

RSA est une méthode de chiffrement asymétrique. Le terme asymétrique signifie qu’il y a deux clés. Une clé qui permet de chiffrer (et qui est publique), et une qui permet de déchiffrer (qui est privée). Naturellement, la clé privée sert à déchiffrer les message chiffrés avec la clé publique associée. Normalement, on ne peut pas calculer la clé de déchiffrement (privée) à partir de la clé de chiffrement (publique).

Si A veut envoyer un message à B, il faut que B ait généré sa paire de clés (la publique et la privée) RSA. Il distribue ensuite (sur Internet par exemple) sa clé publique. C’est la clé publique de B qui est utilisée par A pour envoyer un message à B.

Les clés publiques sont composées essentiellement de 2 nombres : l’exposant $e$ et le module $n$. Généralement, le module est un très grand nombre entier (plusieurs centaines de chiffres). L’exposant peut être plus petit (il est généralement assez petit, par exemple 65537), mais pas trop tout de même. L’exposant est souvent un nombre premier (ce n’est pas une condition nécessaire, mais il faut que l’exposant soit premier avec un autre nombre, qu’on calcule à partir de $n$, et cette condition est généralement remplie si $e$ est premier)

Ces deux nombres, l’exposant $e$ et le module $n$ constituent la clé publique.

La clé privée est constitué de 2 autres nombres, l’exposant $d$ et le même module que dans la clé public $n$.

Format de distribution des clés

Plutôt que de donner les clés publiques RSA en donnant les deux nombres, il y a plusieurs formats, un peu moins lisibles par un humain, qui sont utilisés.

L’un de ces formats présente les clés sous cette forme :

-----BEGIN PUBLIC KEY-----
MFwwDQYJKoZIhvcNAQEBBQADSwAwSAJBANeGRhEkLOjAVkEGWfB4YClJgTvvTH2B
vU0G31PqDsWOPDObTZJggp8l0Zzu5ZxxeR3X8Ii+p+9553HpTLcB+1cCAwD+Lw==
-----END PUBLIC KEY-----

Il s’agit du format PEM. Les 2 lignes du milieu sont le résultat de l’encodage de données binaires en base64.

Ces données binaires sont au format DER. Ce sont des données encodées en ASN.1.

Ça fait beaucoup d’étapes à franchir si on doit faire le décodage de la clé sans outils, pour retrouver les deux valeurs de $n$ et $e$ (mais ça reste possible). Heureusement, pour atteindre notre objectif – connaître $e$ et $n$ pour pouvoir travailler sur le défi – nous n’avons pas à passer par toutes ces étapes. Il suffit d’avoir les bons outils…

Outils Python

Le module Python nommé pycrypto contient des outils pour, entre autres, relire des clés :

from Crypto.PublicKey import RSA
s = """\
-----BEGIN PUBLIC KEY-----
MFwwDQYJKoZIhvcNAQEBBQADSwAwSAJBANeGRhEkLOjAVkEGWfB4YClJgTvvTH2B
vU0G31PqDsWOPDObTZJggp8l0Zzu5ZxxeR3X8Ii+p+9553HpTLcB+1cCAwD+Lw==
-----END PUBLIC KEY-----"""

pkey = RSA.importKey(s)
print("n =",pkey.n)
print("e =",pkey.e)
n = 1128793433274874033756697492600803855010811843758206
    6991706728430558948736528061738292175100804540944571
    300943769533674065284596085323344168423742236654423
e = 65071

Voilà les deux valeurs $n$ et $e$ qui constituent la clé publique.

Outil openssl

L’outil en ligne de commande openssl permet aussi de manipuler des clés. Si la clé publique est contenue dans le fichier pkey.pem, la commande suivante nous donnera les informations que nous cherchons :

> openssl  rsa -pubin  -text -in pkey.pem 

Public-Key: (512 bit)
Modulus:
    00:d7:86:46:11:24:2c:e8:c0:56:41:06:59:f0:78:
    60:29:49:81:3b:ef:4c:7d:81:bd:4d:06:df:53:ea:
    0e:c5:8e:3c:33:9b:4d:92:60:82:9f:25:d1:9c:ee:
    e5:9c:71:79:1d:d7:f0:88:be:a7:ef:79:e7:71:e9:
    4c:b7:01:fb:57
Exponent: 65071 (0xfe2f)
writing RSA key
-----BEGIN PUBLIC KEY-----
MFwwDQYJKoZIhvcNAQEBBQADSwAwSAJBANeGRhEkLOjAVkEGWfB4YClJgTvvTH2B
vU0G31PqDsWOPDObTZJggp8l0Zzu5ZxxeR3X8Ii+p+9553HpTLcB+1cCAwD+Lw==
-----END PUBLIC KEY-----

L’exposant est donné en décimal et en hexa (ligne Exponent). Le module est donné par une suite d’octets en hexadécimal. Il n’est pas très difficile de reconstruire le nombre à partir de la série d’octets : si la série d’octets était simplement 01:d7:86, il suffirait de convertir le nombre héxadécimal 01d786 en décimal.

Conclusion

Voilà pour ce premier point, vous disposez d’un moyen pour extraire les valeurs de $e$ et $n$ d’une clé publique donnée au format PEM. Ce sera utile dans les défis : les Avengers Cryptalanystes II et (pas encore publié) : la Team Rocket chiffre avec RSA

Dans un prochain billet, nous verrons comment on utilise $n$ $e$ et $d$ pour réaliser les opérations de chiffrement et de déchiffrement : Comment chiffrer (et déchiffrer) avec RSA.