RSA

Le premier algorithme de chiffrement à clé publique (chiffrement asymétrique) a été développé par R.Merckle et M.Hellman en 1977. Il fut vite rendu obsolète grâce aux travaux de Shamir, Zippel et Herlestman, de célèbres cryptanalistes.

En 1978, l'algorithme à clé publique de Rivest, Shamir, et Adelman (d'où son nom RSA) apparaît. Cet algorithme servait encore en 2002 à protéger les codes nucléaires de l'armée américaine et russe.

Fonctionnement

Le fonctionnement du cryptosystème RSA est basé sur la difficulté de factoriser de grands entiers. Appelons Alice l'émettrice et Bob le récepteur du message.

Pour qu'Alice puisse communiquer de façon asymétrique il lui faut créer sa paire de clef pour cela elle choisit:

• deux nombres premiers p et q
• d un entier tel que $d<\phi$ et que d soit premier avec $\phi$

$\phi$ est l'indicatrice d'Euler : $\phi = (p-1)*(q-1)$ .

Le nombre $d$ constitue ainsi la clé privée.

La clé publique est alors le doublet $(n,e)$ créé à l'aide de la clé privée par les transformations suivantes :

⚠️ Attention pour le calcul de e ci dessus $d^{-1}$ correspond à l'algorithme d'Euclide étendu !

$(n,e) = (pq, d^{-1} mod(\phi))$

Rappel :

• $pgcd(d,\phi(n)) = 1$ signifie que d et $\phi$ sont premiers entre eux.
• Un nombre premier est un nombre que l'on peux diviser par 1 ou par lui même
• Pour trouver un nombre premier on peux utiliser le crible de Sundaram, Le crible d'Eratosthène , etc ...

⚠️ Utiliser p et q identique est une très mauvaise idée, car la factorisation devient triviale $n = p^2$ , mais dans ce cas particulier, noter que $\phi$ se calcule $\phi = (p − 1)^2$

⚠️ Les clés sont renouvelées régulièrement afin d'éviter tous risques de divulgation de la clé privée. Il est indispensable de ne jamais utiliser plusieurs fois la même valeur de p ou q pour éviter des attaques par recherche de PGCD.

Example

• Chiffrement :

Chiffrer le message "RSA" (encodé 82,83,65 en décimal) avec la clé publique $(n,e) = (1022117,101)$ Soit $C$ le message chiffré :

$C = 828365^{101} mod (1022117) = 436837$

Donc le message chiffré est 436837.

• Déchiffrement :

Déchiffrer le message $C=436837$ avec la clé publique $(n,e) = (1022117,101)$ et la clé privée $d = 767597$ soit D le message déchiffré :

$D = 436837^{767597} mod (1022117) = 828365$

828365 est le message clair (soit les lettres "RSA")

Le Certificat RSA

Un certificat RSA est un fichier texte contenant les données utiles à un échange cryptographique par RSA.

Il existe 2 types de certificat :

• Le certificat public, qui commence par -----BEGIN PUBLIC KEY----- et qui contient les valeurs des clés publiques N et e .
• Le certificat privé, qui commence par -----BEGIN RSA PRIVATE KEY----- et qui contient toutes les valeurs : N , e , d , q et p . Ce fichier est généralement conservé précieusement et ne doit jamais être divulgué.

Format

Exemple d'une clef publique :

-----BEGIN PUBLIC KEY-----
MIHeMA0GCSqGSIb3DQEBAQUAA4HMADCByAKBwHfR4yv+QfsHYSvLlS6LGW2cMDlB
3RlH1PteD7gN6nU4KhyMlRznOUQI7cgB082btMWs1usPYfUSrqkDs+1EDrzzw42M
G683YvLlJRfcO2syc+YNJTDqtVHW5V3SNJ2J+WKCw0A5+ab2qA+sfhRFhvPJ7gsL
vUj+blt5qweyGVheMOQvy+WXI+Vi/jwtlW3it25kBLZUoESDBg+HZKnxz3MgcJ6X
roMdjPPwTH2f8sOrCTI1jJzNUYxJ9JQ0QPTrxwIDAQAB
-----END PUBLIC KEY-----

• Extraire les infos d'une clef publique avec openssl : openssl rsa -pubin -in pubkey.txt -text -noout

Ici le résultat de la commande donne :

RSA Public-Key: (1535 bit)
Modulus:
    77:d1:e3:2b:fe:41:fb:07:61:2b:cb:95:2e:8b:19:
    6d:9c:30:39:41:dd:19:47:d4:fb:5e:0f:b8:0d:ea:
    75:38:2a:1c:8c:95:1c:e7:39:44:08:ed:c8:01:d3:
    cd:9b:b4:c5:ac:d6:eb:0f:61:f5:12:ae:a9:03:b3:
    ed:44:0e:bc:f3:c3:8d:8c:1b:af:37:62:f2:e5:25:
    17:dc:3b:6b:32:73:e6:0d:25:30:ea:b5:51:d6:e5:
    5d:d2:34:9d:89:f9:62:82:c3:40:39:f9:a6:f6:a8:
    0f:ac:7e:14:45:86:f3:c9:ee:0b:0b:bd:48:fe:6e:
    5b:79:ab:07:b2:19:58:5e:30:e4:2f:cb:e5:97:23:
    e5:62:fe:3c:2d:95:6d:e2:b7:6e:64:04:b6:54:a0:
    44:83:06:0f:87:64:a9:f1:cf:73:20:70:9e:97:ae:
    83:1d:8c:f3:f0:4c:7d:9f:f2:c3:ab:09:32:35:8c:
    9c:cd:51:8c:49:f4:94:34:40:f4:eb:c7
Exponent: 65537 (0x10001)

Ainsi (n,e) = (..., 65537)

Les formats de clé RSA sont définis au moins dans les RFC 3447 et RFC 5280. Le format est basé sur ASN.1 et inclut plus que le module brut et l'exposant.

Si vous décodez l'ASN.1 encodé en base 64, vous trouverez un habillage (comme un identifiant d'objet) ainsi qu'une chaîne de bits ASN.1 interne

On retrouve les mêmes résultats. Cyberchef

SEQUENCE
  SEQUENCE
    ObjectIdentifier rsaEncryption (1 2 840 113549 1 1 1)
    NULL
  BITSTRING, encapsulates
    SEQUENCE
      INTEGER 77d1e32bfe41fb07612bcb952e8b196d..(total 192bytes)..0932358c9ccd518c49f4943440f4ebc7
      INTEGER 010001