La cryptographie classique (symétrique) permet à deux utilisateurs A (Alice) et B (Bob) de communiquer confidentiellement en partageant une clef secrète $K$. Ainsi, Eve (eavesdropper) qui intercepte la communication ne peut pas la déchiffrer.
Le problème qui s'est immédiatement posé avec l'apparition des réseaux informatiques est celui de la distribution des clefs. Avec un réseau de $N$ noeuds, tous susceptibles de communiquer entre eux ou d'intercepter le traffic, chaque utilisateur devrait posséder $\frac{N(N-1)}{2}$ clefs, une pour chaque lien bidirectionnel, ce qui est évidemment impossible.
En 1976, dans un article historique, Diffie et Hellman ont proposé (sans savoir à l'époque comment la réaliser), l'idée de cryptographie à clef publique, avec laquelle chaque utilisateur du réseau posséderait deux clefs, une publique $K_P$, accessible à tous les autres, et une secrète $K_S$, connue de lui seul.
On devrait pouvoir chiffrer un message destiné à un utilisateur en connaissant seulement sa clef publique, mais ne pouvoir déchiffrer le cryptogramme qu'en connaissant en plus sa clef secrète.
Plusieurs systèmes ont alors été proposés pour satisfaire ces contraintes, apparemment inconciliables. L'idée générale est d'utiliser des problèmes algorithmiquement difficiles, mais dont certaines instances sont faciles.
Le premier système proposé, dû à Merkle et Hellman, reposait sur le problème du sac-à-dos : il est généralement difficile de savoir si un grand nombre $N$ peut s'écrire comme somme d'une sous-liste d'une liste de nombres donnée, mais le problème est trivial si la liste en question est par exemple $1,2,4,8,\ldots,2^m$ : cela revient à écrire $N$ en binaire. Il existe d'autres instances faciles, les suites super-croissantes, c'est à dire, dans lesquelles chaque terme est strictement supérieur à la somme des précédents.. On en choisit une qu'on garde secrète, $A=[a_0,a_1,\ldots,a_{n-1}]$ et on publie $B=[b_0,b_1,\ldots,b_{n-1}$ où $b_i=ka_i\mod M$ où $M$ est un grand nombre $>a_0+a_1+\cdots+a_n$, et $k$ un entier inversible modulo $M$. On pose $d=k^{-1}\mod M$.
La clef publique est $B$, la clef secrète est $(A,k,M)$. Les messages sont des blocs de $n$ bits.
Le cryptogramme de $$m = (m_0,\ldots,m_{n-1})\in \{0,1\}^n$$ est $$c = \sum_{i=0}^{n-1}m_i b_i$$ Pour déchiffrer, le destinataire calcule $$ s = lc\mod M = \sum_{i=0}^{n-1}m_ia_i$$ et retrouve les $m_i$ en résolvant le problème facile.
Ce système a été rapidement craqué, et par conséquent abandonné.
Le premier système à résister sérieusement a été RSA, initiales de Rivest-Shamir-Adelman. Il est encore le plus utilisé. Il repose sur la difficulté de la factorisation des grands entiers. Si on multiplie deux grands nombres premiers $p$ et $q$, il est impossible en pratique de retrouver $p$ et $q$ à partir de $n=pq$.
Pour construire une clef RSA, on tire au hasard deux nombres premiers $p<q$ de $N$ bits, et on calcule $n=pq$ (le module). On calcule aussi $\varphi(n)=(p-1)(q-1)$ (indicatrice d'Euler).
On choisit ensuite un exposant public $2\lt e\lt n-1$, qui doit être inversible modulo $\varphi(n)$, et on calcule son inverse $d = e^{-1}\mod \varphi(n)$ (l'exposant privé). On a donc $ed=1+k\varphi(n)$ pour un certain $k$.
Dans la description originale, $d$ est choisi au hasard et $e$ calculé ensuite, mais pour des raisons pratiques on utilise souvent les valeurs $e=3,17,257$ ou $65537$.
La clef publique est $(n,e)$, la clef secrète est $(p,q,d)$.
Les messages à chiffrer sont des blocs de $2N$ bits, interprétés comme des entiers modulo $n$. Pour chiffrer un tel message $m$, on calcule $$ c= m^e \mod n.$$ Pour déchiffrer $c$, le destinataire calcule $$ c^d \mod n = m^{ed} \mod n = m^{1+k\varphi(n)} \mod n = m^1 (m^{\varphi(n)})^k \mod n = m$$ au moins si $m$ est premier avec $\varphi(n)$ d'après le théorème d'Euler, et en fait dans tous les cas, à cause de la forme spéciale de $n$.
On a $$c^d = m(m^{k(q-1)})^{p-1}\equiv m \mod p$$ $$c^d = m(m^{k(p-1)})^{q-1}\equiv m \mod q$$ d'après le théorème de Fermat, et on peut donc retrouver $m$ à partir de $m_p = c^d\mod p$ et $m_q=c^d\mod q$ en appliquant le théorème des reste chinois.
En pratique, on complète la clef secrète avec $$d_p = d\mod (p-1)$$ $$d_q = d\mod (q-1)$$ $$q_{inv} = q^{-1}\mod p$$ et le déchiffrement est obtenu en calculant $$m_1 = c^{d_p}\mod p$$ $$m_2 = c^{d_q}\mod q$$ $$h = (m_1-m_2)q_{inv} \mod p$$ $$ m = m_2+hq.$$
# Construisons une clef RSA de 512 bits
from random import randrange
from ent3 import *
a = randrange(2*255,2**256-1)
if not a%2: a+=1
a
while not miller_rabin(a):a+=2
p=a
b = randrange(p,2**256-1)
if not b%2: b+=1
while not miller_rabin(b):b+=2
q=b
print ('%x' % p)
print ('%x' % q)
n = p*q
print (n)
phi_n = (p-1)*(q-1)
e = 257
d = inversemod(e,phi_n)
print (d)
d1, d2, q_inv = d % (p-1), d % (q-1), inversemod(q,p)
print (d1)
print (d2)
print (q_inv)
from codecs import encode, decode
def text2int(t):
assert len(t) <= 64 # 64*8 = 512 bits
if isinstance(t,str):
return int(encode(t.encode(),'hex'), 16) # t.encode() nécessaire en Python 3 pour avoir des bytes
elif isinstance(t,bytes):
return int(encode(t,'hex'), 16)
def int2text(m):
s = '%x' % m
if len(s)%2: s = '0'+s
return decode(s, 'hex')
msg = "L'arithmétique, c'est bien difficile !"
m = text2int(msg)
print (m)
msg.encode() # l'encodage par défaut est celui du système
msg.encode('utf8')
# Chiffrement
c = pow(m,e,n)
print (c)
# Déchiffrement
test = pow(c,d,n)
print (test)
int2text(test)
print(_.decode('utf8'))
# Déchiffrement accéléré avec les paramètres précalculés
m1, m2 = pow(c,d1,p), pow(c,d2,q)
h = (m1-m2)*q_inv % p
test2 = m2 + h*q
print (test2)
print (int2text(test2).decode('utf8'))
print (encode(msg.encode(),'hex'))
print ('%x'%n)
Notre message était sensiblement plus court que la clef. En pratique, pour éviter de chiffrer des blocs de zéros, qui risqueraient de révéler des indications sur la clef secrère, et pour éviter que deux messages identiques soient chiffrés de la même manière, on remplace les octets nuls par un bourrage aléatoire, respectant une norme telle que PKCS #1.
Par exemple, avec un module de $k$ octets, on transmettra des entiers $D$ de moins de $k-11$ octets, sous forme de blocs de $k$ octets ayant la structure
00 02 ||bourrage||00||D
où le bourrage est consitué d'octets aléatoires non nuls.
def pad(D,k,random=True):
assert len(D)<k-11
m = k-3-len(D)
s = open('/dev/urandom','rb').read(m).replace(b'\x00',b'\xff')
res = b'\x00\x02'+s+b'\x00'+D
return res
D = msg.encode()
P = pad(D,64); P
len(D)
m = text2int(P)
m
c = pow(m,e,n)
c
test3 = pow(c,d,n)
int2text(test3)
Le premier endroit où observer des clefs RSA sur un système Unix est le répertoire .ssh d'un utilisateur.
Avant un première utilisation, on crée les clefs par la commande
$ ssh-keygen
Generating public/private rsa key pair.
Enter file in which to save the key (/home/jyt/.ssh/id_rsa): ./.ssh/id_rsa
Enter passphrase (empty for no passphrase):
Enter same passphrase again:
Your identification has been saved in ./.ssh/id_rsa.
Your public key has been saved in ./.ssh/id_rsa.pub.
The key fingerprint is:
56:1d:12:06:7d:4d:96:52:1d:83:d5:de:c6:3b:39:f7 jyt@scriabine
The key's randomart image is:
+--[ RSA 2048]----+
| .o+..+**o|
| ..oo+o +|
| .... o.|
| . =|
| S .o|
| . =.|
| =|
| E|
| |
+-----------------+
$ ls .ssh
id_rsa id_rsa.pubOn n'a pas précisé de paramètres, la commande a donc crée par défaut une clef RSA de 2048 bits.
La clef secrète est dans id_rsa, la clef publique dans id_rsa.pub.
Examinons ces fichiers.
!cat .ssh/id_rsa.pub
!cat .ssh/id_rsa
Ils sont manifestement encodés en base64. Essayons de déchiffrer leur contenu, en commençant par la clef publique qui est plus simple.
p = open('.ssh/id_rsa.pub','rb').read()
kp = decode(p[p.index(b'A'):p.index(b'jyt')], 'base64') # on découpe le morceau intéressant
kp
On voit que la structure décodée se compose des 4 octets 0,0,0,7, de la chaîne « ssh-rsa ». Il y a ensuite un entier sur 32 bits en big-endian donnant la longueur de l'exposant public e (en octets, ici 3) , suivi de sa valeur, puis de la longueur de n (même système) et de sa valeur. On peut décoder avec le module struct sans trop de difficulté :
import struct
ll = struct.unpack('!4B7sI3BI257c',kp)
print (ll)
L'exposant public est 0x010001 = 65537, et le module $n$ est obtenu à partir des 257 octets suivant la longueur 257 :
nn=ll[10:]
N = int(''.join(map(lambda x: "%02X"%x, map(ord,nn))),16)
print (N)
Structure de la clef privée :
-----BEGIN RSA PRIVATE KEY-----
base64data
-----END RSA PRIVATE KEY-----
base64data DER structure:
RSAPrivateKey ::= SEQUENCE {
version Version,
modulus INTEGER, -- n
publicExponent INTEGER, -- e
privateExponent INTEGER, -- d
prime1 INTEGER, -- p
prime2 INTEGER, -- q
exponent1 INTEGER, -- d mod (p - 1)
exponent2 INTEGER, -- d mod (q - 1)
coefficient INTEGER -- q^-1 mod p
}
s = open('.ssh/id_rsa').read()
s
s = s[s.index('\n')+1:]
s = s.replace('\n','')
s = s[:s.index('-')]
s= decode(s.encode(), 'base64')
s
C'est à ce stade qu'il vaut mieux faire appel au décodeur de pyasn1 :
from pyasn1.codec.der import decoder
der=decoder.decode(s)
der
(version, n, e, d, p, q, e1, e2, c) = (int(x) for x in der[0])
print ("e = %d" % e)
print (hex(e))
print ("d = ",d)
print ("e*d mod (p-1)*(q-1) = ", e*d % ((p-1)*(q-1)))
print ("p*q-n = ", p*q-n)
print ("N-n = ", N-n)
Il existe un module rsa pour Python qui permet toutes ces manipulations de clefs.
import rsa
help(rsa)
La cryptographie à clef publique permet de signer numériquement un document. Le principe est le suivant. On calcule un hachage $h= H(x)$ du document $x$, et on le chiffre avec sa clef privée. La signature est $(h,s) = E(h,K_S))$ Alors, tout le monde peut déchiffrer $s$ avec la clef publique, recalculer le hachage et comparer les résultats.
Bien entendu, il y a des précautions à prendre dans le choix des paramètres, du bourrage, etc. Les protocoles autorisés sont décrits dans ce document.
Le module rsa gère les signatures de façon transparente.
(KP,KS) = rsa.newkeys(512)
print (KP)
print (KS)
message = 'La clef du coffre est dans le pot de fleurs'
signature = rsa.sign(message.encode(), KS, 'SHA-1')
print (message)
signature
rsa.verify(message.encode(), signature, KP)
help(rsa.verify)
En pratique, la mise en oeuvre du RSA nécessite certaines précautions, décrites dans les RFC et autres standards officiels.
L'attaque la plus évidente est la factorisation du module. Ce qui est impossible aujourd'hui sera peut-être possible demain, avec la découverte de nouveaux algorithmes et l'augmentation de la puissance des machines.
Ce risque est bien illustré par l'affaire des cartes bancaires. Jusqu'à une date récente, un paiement par carte bancaire se déroulait ainsi. La mémoire de la carte est divisée en deux zones, une accessible avec n'importe quel lecteur, et une autre (zone secrète) qui n'est accessible qu'au processeur de la carte, et illisible autrement. La zone publique contient une valeur d'authentification, qui est obtenue en chiffrant des données publiques (comme le numéro de la carte et sa date d'expiration) avec une clé RSA secrète. Les terminaux de paiement et les distributeurs de billets connaissent la clé publique, et l'utilisent pour vérifier la valeur d'authentification, qui est précisément une signature numérique RSA, sans hachage vu le petit nombre de données.
Si la signature est correcte, la carte est considérée comme authentique, et le code est demandé au client. Le terminal envoie le code à la carte qui le compare avec celui contenu dans sa zone secrète, et répond « oui » ou «non ». Si la réponse est « oui », le paiement est accepté.
Seulement voilà. Les cartes émises vers 1998 utilisaient la clé publique
$$e=3, \quad n = 2135987035920910082395022704999628797051095341826417406442524165008583957746445088405009430865999$$Cette clé était trop courte, les algorithmes ayant progressé, elle a pu être factorisée. A partir de ce moment, il devenait possible de fabriquer de fausses cartes, en chiffrant des données d'authentification fantaisistes sur une carte programmable, et en programmant la carte pour qu'elle réponde « oui » (les deux octets 0x90, 0x00 dans son langage) quelle que soit la question posée (les fameuses yescards).
L'histoire était racontée sur ce site (qui n'existe plus, mais archive.org peut nous le retrouver).
Le programme msieve répond en 18 secondes sur une station de travail moyennement récente.
S'il est en général impossible de retrouver $p$ et $q$ à partir de $n = pq$ pour deux grands nombres premiers $p$ et $q$, on connaît de nombreux cas particuliers dans lesquels il est possible de craquer la clé RSA. On trouvera ici un exposé récent de l'état de l'art dans ce domaine. Une première chose à réaliser, c'est que si on connaît $\varphi(n)$, alors on peut factoriser $n$. En effet, $\varphi(n) = (p-1)(q-1)$, donc $p$ et $q$ sont les deux racines de l'équation du second degré $x^2-(n-\varphi(n)+1)x+n = 0$.
Bien sûr, $\varphi(n)$ n'est pas public, mais dans certaines circonstances, on peut le retrouver. C'est le cas si $3d<n^{1/4}$, $q<p<2q$ (attaque de Wiener). Il existe de nombreuses variantes de cette attaque, et d'autres types de clés faibles. Le programme wiener.py montre comment la mettre en oeuvre. Il utilise quelques fonctions de ent.py, une petite collection d'exemples écrite par W. Stein (maître d'oeuvre du projet SAGE) pour illustrer son cours de cryptographie. Ce fichier sera donné au prochain TD.
Même si la clé est résistante, un mauvais usage du système peut être catastrophique.
Par exemple, supposons que $B$ et $B'$ aient le même module $n$ et des exposants publics $e$ et $e'$, avec $pgcd(e,e')=1$.
A envoie un même message $x$ aux deux, donc $y=x^e \mod n$ à $B$ et $y' = x^{e'} \mod n$ à $B'$. Si O intercepte $y$ et $y'$, il peut retrouver x sans factoriser la clé. (Problème du module commun).
Si $B$, $B'$ et $B''$ ont pour modules $n$, $n'$, et $n''$ (deux à deux premiers entre eux) et un même exposant public $e$ (c'est fréquent, beaucoup de systèmes utilisent $e=3$ par exemple), A envoie $x^3 \mod n, n'$ et $n''$ aux trois. O intercepte la communication et peut retrouver x sans factoriser la clé.
Il y en a beaucoup, voir ici pour plus d'information.