M1 Cryptographie - Cryptographie asymétrique

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 système de Merkle-Hellman

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é.

RSA

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,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.$$

In [1]:
# Construisons une clef RSA de 512 bits
from random import randrange
from ent import *
In [2]:
a = randrange(2*255,2**256-1)
if not a%2: a+=1
a
Out[2]:
93849934275814665364380521196036496439903133802992627147626182444821617386459L
In [3]:
while not miller_rabin(a):a+=2
In [4]:
p=a
In [5]:
b = randrange(p,2**256-1)
if not b%2: b+=1
while not miller_rabin(b):b+=2
In [6]:
q=b
In [7]:
print '%x' % p
print '%x' %q
cf7d2e2e931a4cae19d3e984ecc7e1ab8cf28648c284560a5e85d98a3b052537
f4524937eac116bcfa1a72ce347d5b38af0be179937a445c79ade83f71009455

In [8]:
n = p*q
print n
10371330132332646588212884102988152812653606763850648450229721715154672682168017786704399862085527724522179211791402323333429362797294156857705474198939459

In [9]:
phi_n = (p-1)*(q-1)
e = 257
d = inversemod(e,phi_n)
print d
2945942022024448252683037118747607608263475851210495474189765312086735820226655175776358386561579964587909865786038895949382733633795042119528473165418617

In [10]:
d1, d2, q_inv  = d % (p-1), d % (q-1), inversemod(q,p)
In [11]:
print d1
print d2
print q_inv
71209094100326302513829578339405123757903155998379619820183290181868542375203
84279787868995395117059311543708370874209341396889600390847996201757201022801
18993374065257972577409701483294132708835214359891024253240491464723795009598

In [12]:
def text2int(t):
    assert len(t) <= 64 # 64*8 = 512 bits
    return int(t.encode('hex'),16)

def int2text(m):
    s = '%x' % m
    if len(s)%2: s = '0'+s
    return s.decode('hex')
In [13]:
msg = "L'arithmétique, c'est bien difficile !"
m = text2int(msg)
print m
2482049485033484295509148869034669333161266776700492625573073315249287942938347748044373827617

In [14]:
# Chiffrement
c = pow(m,e,n)
print c
4521084982110602308712789728257798738938560031304350767664951588308688155075895383213834917091399327126873709832812215731873698966897969857877198793891955

In [15]:
# Déchiffrement
test = pow(c,d,n)
print test
int2text(test)
2482049485033484295509148869034669333161266776700492625573073315249287942938347748044373827617

Out[15]:
"L'arithm\xc3\xa9tique, c'est bien difficile !"
In [16]:
# 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)
2482049485033484295509148869034669333161266776700492625573073315249287942938347748044373827617
L'arithmétique, c'est bien difficile !

In [17]:
print msg.encode('hex')
print '%x'%n
4c2761726974686dc3a974697175652c206327657374206269656e20646966666963696c652021
c606017533754f7aeb14e9d8c15e6e75bc6eaa6a32cf27ddf7f2fdfd479a79cc2f880acc08b1f1aa79f42339c41fc8712766af4078bec0731d6b6afad9392743

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.

In [18]:
def pad(D,k,random=True):
    assert len(D)<k-11
    m = k-3-len(D)
    s = open('/dev/urandom').read(m).replace('\x00','\xff')
    res = '\x00\x02'+s+'\x00'+D
    return res

pad(msg,64)
Out[18]:
"\x00\x02\x8a\xf6\xb6\x18^\x9c\xc6\x19\xf4K\xbd)m'\xe1n \x05\x84pB\xe2\x00L'arithm\xc3\xa9tique, c'est bien difficile !"
In [19]:
m = text2int(_)
m
Out[19]:
520229129444891891271646097321992478604247852293902707327259141580355068772320436633785285208398435389986561251602782918979702251252905451498359824417L
In [20]:
c = pow(m,e,n)
c
Out[20]:
2846548760364820416863451199687569172294280730873737914984759962650183096059347033731714849096820636611503127918066433050137768043798928753534375487893683L
In [21]:
test3 = pow(c,d,n)
int2text(test3)
Out[21]:
"\x02\x8a\xf6\xb6\x18^\x9c\xc6\x19\xf4K\xbd)m'\xe1n \x05\x84pB\xe2\x00L'arithm\xc3\xa9tique, c'est bien difficile !"

RSA en pratique

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.pub

On 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ètes est dans id_rsa, la clef publique dans id_rsa.pub.

Examinons ces fichiers.

In [22]:
!cat .ssh/id_rsa.pub
ssh-rsa AAAAB3NzaC1yc2EAAAADAQABAAABAQCt3GDhiTdIaoJazo6ywqWwFiNRYuv72fSbVA5uT+L+0uUbfbTwgUF9WZu7nJu2PKoVwPu1NsBe7OQygKWfMycaOrjNbvCQY944GrOiZnrAHgFugORrmfjfV5dvlcZ4eHZ1f/D3ivTapEfN/YQXb6afE6YbDKKh2FHyjD0dSehR45do2x7Nf0BXw83KmhVFXx4xpnOfHrXElBHB4jvebV8cTWCGt6PxL5PeWGceLddyF/eKwHmesCKzMSQiHQ6ZmWYZGF0cnKoJaB/HfNsOAuCq+gRof2dC8M/dHIUbnApW698CsrhfK5Rc0DmjMRIZ2WxQ8TlCSZmiB233cBA/kUz1 jyt@scriabine

In [23]:
!cat .ssh/id_rsa
-----BEGIN RSA PRIVATE KEY-----
MIIEoAIBAAKCAQEArdxg4Yk3SGqCWs6OssKlsBYjUWLr+9n0m1QObk/i/tLlG320
8IFBfVmbu5ybtjyqFcD7tTbAXuzkMoClnzMnGjq4zW7wkGPeOBqzomZ6wB4BboDk
a5n431eXb5XGeHh2dX/w94r02qRHzf2EF2+mnxOmGwyiodhR8ow9HUnoUeOXaNse
zX9AV8PNypoVRV8eMaZznx61xJQRweI73m1fHE1ghrej8S+T3lhnHi3Xchf3isB5
nrAiszEkIh0OmZlmGRhdHJyqCWgfx3zbDgLgqvoEaH9nQvDP3RyFG5wKVuvfArK4
XyuUXNA5ozESGdlsUPE5QkmZogdt93AQP5FM9QIDAQABAoIBAAX1VYSlNTXQIKOI
DK/np9H/EDrLzxaUg6OHH+974WWmSJ/GkRrk8x+eoI2vck6uiY2xTW8Kb1FRgQiS
DBsGn8JwXMD9mlT4dzcpAxr/tBk9bgMhe7KMVlEhKVlzopeiWTzxo4p4QqfzlVpj
49EBzI4LGFg4+KHfTf+n+rg0PjgALEubkmuoRpXcRK5QjmhOZmkfqidUoA3QCRK+
12QGeawB8gTTppz5UkSeowhqQPLus8mwRM+viql9gHx2UmShWUSoaVafvmc8aju8
UV/1bGcE5GloSPAEilxZqXqqzeMeXGdsIYAtLcmwws00UbRWDsBgTUPWicl7Akx0
WJELCYECgYEA1zgtJG7VdvsjOJMEAMsl9ael6opa/qq/hhOmiJYmC/S9Whjsyqlc
N4JeG/+jKzpuOHdVUAQ7e79Pbs7PHP5/urwWIxsahcLT4ALCoL9ccJmyATmqLDBv
vP3DLrYe6R3cu1nUr7zfykUI2AhqV7UbYwcl8y6vlUci78g0d4i41JECgYEAzs38
2Wc/Er/rv40ok5TNeqjEqgWhXQGn/gclzPFw2SP1dvQZVMOdpf9Sjcq7wb0PVbah
0O6IcfK5Ikt2MgKfuM/v/Xpupd+s7enSfjVBaPNFV36KMTxHz/p5RX1kcmK/aEzw
KlZOwcmGlZVnyvXApdkPs/AP6l2Jj8xzyVbrVCUCgYAg1Fvme9WqIaL8xUhOCq8O
qvUfMt2wjUFL5YF4wlapajrcHIM6Yt1DRmquoK82L+KSUHm+C/c66DLotzlWtees
B3blAgRotRB20lT4CljCgF9r2mz/8p+I17jHTlamvrxmA8zyxb/pbeBse9Qk7uZv
k66RSuTTw5crtoFyXnO7UQJ/dFNp5uAsml9aPGUqbdlFu7ky5nBEVAyackmS+bTV
xU50xHSJyyQ9iSIVTay78D5oYc5ZNyz1kyL1AFVyJq9TKKHOXMaBdsxaeXkM7fEG
2gH8/zougYNm4ZYCoRPnbHAfOowMi8QAiQDSs1FXENMrih6OtqhSS4JR3pEikB5U
QQKBgGdFuy8NBEw5VWkyoCDyzl6FZ8+tjqMqVkOuDf5T6BrOQGBEx3T2O4JGrHxU
wYhxNB+rXkrbxFvWBxVfcpqBsKEAdJRcccy79hoZi11nDf1kQlTbWIHP4ApJ81FZ
dWi47IA8AGkOB2Tsq8iU8MZuT0aMg0RqPl83A1qr3xrhbW1L
-----END RSA PRIVATE KEY-----

Ils sont manifestement encodés en base64. Essayons de déchiffrer leur contenu, en commençant par la clef publique qui est plus simple.

In [24]:
p = open('.ssh/id_rsa.pub').read()
In [25]:
kp = p[p.index('A'):p.index('jyt')].decode('base64')
kp
Out[25]:
'\x00\x00\x00\x07ssh-rsa\x00\x00\x00\x03\x01\x00\x01\x00\x00\x01\x01\x00\xad\xdc`\xe1\x897Hj\x82Z\xce\x8e\xb2\xc2\xa5\xb0\x16#Qb\xeb\xfb\xd9\xf4\x9bT\x0enO\xe2\xfe\xd2\xe5\x1b}\xb4\xf0\x81A}Y\x9b\xbb\x9c\x9b\xb6<\xaa\x15\xc0\xfb\xb56\xc0^\xec\xe42\x80\xa5\x9f3\'\x1a:\xb8\xcdn\xf0\x90c\xde8\x1a\xb3\xa2fz\xc0\x1e\x01n\x80\xe4k\x99\xf8\xdfW\x97o\x95\xc6xxvu\x7f\xf0\xf7\x8a\xf4\xda\xa4G\xcd\xfd\x84\x17o\xa6\x9f\x13\xa6\x1b\x0c\xa2\xa1\xd8Q\xf2\x8c=\x1dI\xe8Q\xe3\x97h\xdb\x1e\xcd\x7f@W\xc3\xcd\xca\x9a\x15E_\x1e1\xa6s\x9f\x1e\xb5\xc4\x94\x11\xc1\xe2;\xdem_\x1cM`\x86\xb7\xa3\xf1/\x93\xdeXg\x1e-\xd7r\x17\xf7\x8a\xc0y\x9e\xb0"\xb31$"\x1d\x0e\x99\x99f\x19\x18]\x1c\x9c\xaa\th\x1f\xc7|\xdb\x0e\x02\xe0\xaa\xfa\x04h\x7fgB\xf0\xcf\xdd\x1c\x85\x1b\x9c\nV\xeb\xdf\x02\xb2\xb8_+\x94\\\xd09\xa31\x12\x19\xd9lP\xf19BI\x99\xa2\x07m\xf7p\x10?\x91L\xf5'

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é :

In [26]:
import struct
ll = struct.unpack('!4B7sI3BI257c',kp)
print ll
(0, 0, 0, 7, 'ssh-rsa', 3, 1, 0, 1, 257, '\x00', '\xad', '\xdc', '`', '\xe1', '\x89', '7', 'H', 'j', '\x82', 'Z', '\xce', '\x8e', '\xb2', '\xc2', '\xa5', '\xb0', '\x16', '#', 'Q', 'b', '\xeb', '\xfb', '\xd9', '\xf4', '\x9b', 'T', '\x0e', 'n', 'O', '\xe2', '\xfe', '\xd2', '\xe5', '\x1b', '}', '\xb4', '\xf0', '\x81', 'A', '}', 'Y', '\x9b', '\xbb', '\x9c', '\x9b', '\xb6', '<', '\xaa', '\x15', '\xc0', '\xfb', '\xb5', '6', '\xc0', '^', '\xec', '\xe4', '2', '\x80', '\xa5', '\x9f', '3', "'", '\x1a', ':', '\xb8', '\xcd', 'n', '\xf0', '\x90', 'c', '\xde', '8', '\x1a', '\xb3', '\xa2', 'f', 'z', '\xc0', '\x1e', '\x01', 'n', '\x80', '\xe4', 'k', '\x99', '\xf8', '\xdf', 'W', '\x97', 'o', '\x95', '\xc6', 'x', 'x', 'v', 'u', '\x7f', '\xf0', '\xf7', '\x8a', '\xf4', '\xda', '\xa4', 'G', '\xcd', '\xfd', '\x84', '\x17', 'o', '\xa6', '\x9f', '\x13', '\xa6', '\x1b', '\x0c', '\xa2', '\xa1', '\xd8', 'Q', '\xf2', '\x8c', '=', '\x1d', 'I', '\xe8', 'Q', '\xe3', '\x97', 'h', '\xdb', '\x1e', '\xcd', '\x7f', '@', 'W', '\xc3', '\xcd', '\xca', '\x9a', '\x15', 'E', '_', '\x1e', '1', '\xa6', 's', '\x9f', '\x1e', '\xb5', '\xc4', '\x94', '\x11', '\xc1', '\xe2', ';', '\xde', 'm', '_', '\x1c', 'M', '`', '\x86', '\xb7', '\xa3', '\xf1', '/', '\x93', '\xde', 'X', 'g', '\x1e', '-', '\xd7', 'r', '\x17', '\xf7', '\x8a', '\xc0', 'y', '\x9e', '\xb0', '"', '\xb3', '1', '$', '"', '\x1d', '\x0e', '\x99', '\x99', 'f', '\x19', '\x18', ']', '\x1c', '\x9c', '\xaa', '\t', 'h', '\x1f', '\xc7', '|', '\xdb', '\x0e', '\x02', '\xe0', '\xaa', '\xfa', '\x04', 'h', '\x7f', 'g', 'B', '\xf0', '\xcf', '\xdd', '\x1c', '\x85', '\x1b', '\x9c', '\n', 'V', '\xeb', '\xdf', '\x02', '\xb2', '\xb8', '_', '+', '\x94', '\\', '\xd0', '9', '\xa3', '1', '\x12', '\x19', '\xd9', 'l', 'P', '\xf1', '9', 'B', 'I', '\x99', '\xa2', '\x07', 'm', '\xf7', 'p', '\x10', '?', '\x91', 'L', '\xf5')

L'exposant public est 0x010001 = 65537, et le module $n$ est obtenu à partir des 257 octets suivant la longueur 257 :

In [27]:
nn=ll[10:]
N = int(''.join(map(lambda x: "%02X"%x, map(ord,nn))),16)
print N
21947899418871057600547899600184164286535255686393813848883369539005061966974903632717975547404405377688498698246119115336761797962233119164437937686592348499677702821266248725943408426019416886413266273553580418869329534789408368764644114492743904291759191138798142473379848917157263694338221998233137828316506059658363210784426355829209932750437744915644699589368215604393500512570251448439039174339234594943882252432930148389356065431278080075740904827955486653002978803661178349765543916476670622130238033772643613412029439474122674191196141662398737216668538662719085873248696923636708893334918005871170049625333

C'est donc $N$ qu'il faut factoriser si on veut craquer la clef.

Le décodage de la clef privée est plus complexe. Elle est encodée avec le système DER de l'Union Internationale des Télécommunications. Il existe un module Python, pyasn1, qui peut décoder.

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
}
In [28]:
s = open('.ssh/id_rsa').read()
s
Out[28]:
'-----BEGIN RSA PRIVATE KEY-----\nMIIEoAIBAAKCAQEArdxg4Yk3SGqCWs6OssKlsBYjUWLr+9n0m1QObk/i/tLlG320\n8IFBfVmbu5ybtjyqFcD7tTbAXuzkMoClnzMnGjq4zW7wkGPeOBqzomZ6wB4BboDk\na5n431eXb5XGeHh2dX/w94r02qRHzf2EF2+mnxOmGwyiodhR8ow9HUnoUeOXaNse\nzX9AV8PNypoVRV8eMaZznx61xJQRweI73m1fHE1ghrej8S+T3lhnHi3Xchf3isB5\nnrAiszEkIh0OmZlmGRhdHJyqCWgfx3zbDgLgqvoEaH9nQvDP3RyFG5wKVuvfArK4\nXyuUXNA5ozESGdlsUPE5QkmZogdt93AQP5FM9QIDAQABAoIBAAX1VYSlNTXQIKOI\nDK/np9H/EDrLzxaUg6OHH+974WWmSJ/GkRrk8x+eoI2vck6uiY2xTW8Kb1FRgQiS\nDBsGn8JwXMD9mlT4dzcpAxr/tBk9bgMhe7KMVlEhKVlzopeiWTzxo4p4QqfzlVpj\n49EBzI4LGFg4+KHfTf+n+rg0PjgALEubkmuoRpXcRK5QjmhOZmkfqidUoA3QCRK+\n12QGeawB8gTTppz5UkSeowhqQPLus8mwRM+viql9gHx2UmShWUSoaVafvmc8aju8\nUV/1bGcE5GloSPAEilxZqXqqzeMeXGdsIYAtLcmwws00UbRWDsBgTUPWicl7Akx0\nWJELCYECgYEA1zgtJG7VdvsjOJMEAMsl9ael6opa/qq/hhOmiJYmC/S9Whjsyqlc\nN4JeG/+jKzpuOHdVUAQ7e79Pbs7PHP5/urwWIxsahcLT4ALCoL9ccJmyATmqLDBv\nvP3DLrYe6R3cu1nUr7zfykUI2AhqV7UbYwcl8y6vlUci78g0d4i41JECgYEAzs38\n2Wc/Er/rv40ok5TNeqjEqgWhXQGn/gclzPFw2SP1dvQZVMOdpf9Sjcq7wb0PVbah\n0O6IcfK5Ikt2MgKfuM/v/Xpupd+s7enSfjVBaPNFV36KMTxHz/p5RX1kcmK/aEzw\nKlZOwcmGlZVnyvXApdkPs/AP6l2Jj8xzyVbrVCUCgYAg1Fvme9WqIaL8xUhOCq8O\nqvUfMt2wjUFL5YF4wlapajrcHIM6Yt1DRmquoK82L+KSUHm+C/c66DLotzlWtees\nB3blAgRotRB20lT4CljCgF9r2mz/8p+I17jHTlamvrxmA8zyxb/pbeBse9Qk7uZv\nk66RSuTTw5crtoFyXnO7UQJ/dFNp5uAsml9aPGUqbdlFu7ky5nBEVAyackmS+bTV\nxU50xHSJyyQ9iSIVTay78D5oYc5ZNyz1kyL1AFVyJq9TKKHOXMaBdsxaeXkM7fEG\n2gH8/zougYNm4ZYCoRPnbHAfOowMi8QAiQDSs1FXENMrih6OtqhSS4JR3pEikB5U\nQQKBgGdFuy8NBEw5VWkyoCDyzl6FZ8+tjqMqVkOuDf5T6BrOQGBEx3T2O4JGrHxU\nwYhxNB+rXkrbxFvWBxVfcpqBsKEAdJRcccy79hoZi11nDf1kQlTbWIHP4ApJ81FZ\ndWi47IA8AGkOB2Tsq8iU8MZuT0aMg0RqPl83A1qr3xrhbW1L\n-----END RSA PRIVATE KEY-----\n'
In [29]:
s = s[s.index('\n')+1:]
s = s.replace('\n','')
s = s[:s.index('-')]
s=s.decode('base64')
s
Out[29]:
'0\x82\x04\xa0\x02\x01\x00\x02\x82\x01\x01\x00\xad\xdc`\xe1\x897Hj\x82Z\xce\x8e\xb2\xc2\xa5\xb0\x16#Qb\xeb\xfb\xd9\xf4\x9bT\x0enO\xe2\xfe\xd2\xe5\x1b}\xb4\xf0\x81A}Y\x9b\xbb\x9c\x9b\xb6<\xaa\x15\xc0\xfb\xb56\xc0^\xec\xe42\x80\xa5\x9f3\'\x1a:\xb8\xcdn\xf0\x90c\xde8\x1a\xb3\xa2fz\xc0\x1e\x01n\x80\xe4k\x99\xf8\xdfW\x97o\x95\xc6xxvu\x7f\xf0\xf7\x8a\xf4\xda\xa4G\xcd\xfd\x84\x17o\xa6\x9f\x13\xa6\x1b\x0c\xa2\xa1\xd8Q\xf2\x8c=\x1dI\xe8Q\xe3\x97h\xdb\x1e\xcd\x7f@W\xc3\xcd\xca\x9a\x15E_\x1e1\xa6s\x9f\x1e\xb5\xc4\x94\x11\xc1\xe2;\xdem_\x1cM`\x86\xb7\xa3\xf1/\x93\xdeXg\x1e-\xd7r\x17\xf7\x8a\xc0y\x9e\xb0"\xb31$"\x1d\x0e\x99\x99f\x19\x18]\x1c\x9c\xaa\th\x1f\xc7|\xdb\x0e\x02\xe0\xaa\xfa\x04h\x7fgB\xf0\xcf\xdd\x1c\x85\x1b\x9c\nV\xeb\xdf\x02\xb2\xb8_+\x94\\\xd09\xa31\x12\x19\xd9lP\xf19BI\x99\xa2\x07m\xf7p\x10?\x91L\xf5\x02\x03\x01\x00\x01\x02\x82\x01\x00\x05\xf5U\x84\xa555\xd0 \xa3\x88\x0c\xaf\xe7\xa7\xd1\xff\x10:\xcb\xcf\x16\x94\x83\xa3\x87\x1f\xef{\xe1e\xa6H\x9f\xc6\x91\x1a\xe4\xf3\x1f\x9e\xa0\x8d\xafrN\xae\x89\x8d\xb1Mo\noQQ\x81\x08\x92\x0c\x1b\x06\x9f\xc2p\\\xc0\xfd\x9aT\xf8w7)\x03\x1a\xff\xb4\x19=n\x03!{\xb2\x8cVQ!)Ys\xa2\x97\xa2Y<\xf1\xa3\x8axB\xa7\xf3\x95Zc\xe3\xd1\x01\xcc\x8e\x0b\x18X8\xf8\xa1\xdfM\xff\xa7\xfa\xb84>8\x00,K\x9b\x92k\xa8F\x95\xdcD\xaeP\x8ehNfi\x1f\xaa\'T\xa0\r\xd0\t\x12\xbe\xd7d\x06y\xac\x01\xf2\x04\xd3\xa6\x9c\xf9RD\x9e\xa3\x08j@\xf2\xee\xb3\xc9\xb0D\xcf\xaf\x8a\xa9}\x80|vRd\xa1YD\xa8iV\x9f\xbeg<j;\xbcQ_\xf5lg\x04\xe4ihH\xf0\x04\x8a\\Y\xa9z\xaa\xcd\xe3\x1e\\gl!\x80--\xc9\xb0\xc2\xcd4Q\xb4V\x0e\xc0`MC\xd6\x89\xc9{\x02LtX\x91\x0b\t\x81\x02\x81\x81\x00\xd78-$n\xd5v\xfb#8\x93\x04\x00\xcb%\xf5\xa7\xa5\xea\x8aZ\xfe\xaa\xbf\x86\x13\xa6\x88\x96&\x0b\xf4\xbdZ\x18\xec\xca\xa9\\7\x82^\x1b\xff\xa3+:n8wUP\x04;{\xbfOn\xce\xcf\x1c\xfe\x7f\xba\xbc\x16#\x1b\x1a\x85\xc2\xd3\xe0\x02\xc2\xa0\xbf\\p\x99\xb2\x019\xaa,0o\xbc\xfd\xc3.\xb6\x1e\xe9\x1d\xdc\xbbY\xd4\xaf\xbc\xdf\xcaE\x08\xd8\x08jW\xb5\x1bc\x07%\xf3.\xaf\x95G"\xef\xc84w\x88\xb8\xd4\x91\x02\x81\x81\x00\xce\xcd\xfc\xd9g?\x12\xbf\xeb\xbf\x8d(\x93\x94\xcdz\xa8\xc4\xaa\x05\xa1]\x01\xa7\xfe\x07%\xcc\xf1p\xd9#\xf5v\xf4\x19T\xc3\x9d\xa5\xffR\x8d\xca\xbb\xc1\xbd\x0fU\xb6\xa1\xd0\xee\x88q\xf2\xb9"Kv2\x02\x9f\xb8\xcf\xef\xfdzn\xa5\xdf\xac\xed\xe9\xd2~5Ah\xf3EW~\x8a1<G\xcf\xfayE}drb\xbfhL\xf0*VN\xc1\xc9\x86\x95\x95g\xca\xf5\xc0\xa5\xd9\x0f\xb3\xf0\x0f\xea]\x89\x8f\xccs\xc9V\xebT%\x02\x81\x80 \xd4[\xe6{\xd5\xaa!\xa2\xfc\xc5HN\n\xaf\x0e\xaa\xf5\x1f2\xdd\xb0\x8dAK\xe5\x81x\xc2V\xa9j:\xdc\x1c\x83:b\xddCFj\xae\xa0\xaf6/\xe2\x92Py\xbe\x0b\xf7:\xe82\xe8\xb79V\xb5\xe7\xac\x07v\xe5\x02\x04h\xb5\x10v\xd2T\xf8\nX\xc2\x80_k\xdal\xff\xf2\x9f\x88\xd7\xb8\xc7NV\xa6\xbe\xbcf\x03\xcc\xf2\xc5\xbf\xe9m\xe0l{\xd4$\xee\xe6o\x93\xae\x91J\xe4\xd3\xc3\x97+\xb6\x81r^s\xbbQ\x02\x7ftSi\xe6\xe0,\x9a_Z<e*m\xd9E\xbb\xb92\xe6pDT\x0c\x9arI\x92\xf9\xb4\xd5\xc5Nt\xc4t\x89\xcb$=\x89"\x15M\xac\xbb\xf0>ha\xceY7,\xf5\x93"\xf5\x00Ur&\xafS(\xa1\xce\\\xc6\x81v\xccZyy\x0c\xed\xf1\x06\xda\x01\xfc\xff:.\x81\x83f\xe1\x96\x02\xa1\x13\xe7lp\x1f:\x8c\x0c\x8b\xc4\x00\x89\x00\xd2\xb3QW\x10\xd3+\x8a\x1e\x8e\xb6\xa8RK\x82Q\xde\x91"\x90\x1eTA\x02\x81\x80gE\xbb/\r\x04L9Ui2\xa0 \xf2\xce^\x85g\xcf\xad\x8e\xa3*VC\xae\r\xfeS\xe8\x1a\xce@`D\xc7t\xf6;\x82F\xac|T\xc1\x88q4\x1f\xab^J\xdb\xc4[\xd6\x07\x15_r\x9a\x81\xb0\xa1\x00t\x94\\q\xcc\xbb\xf6\x1a\x19\x8b]g\r\xfddBT\xdbX\x81\xcf\xe0\nI\xf3QYuh\xb8\xec\x80<\x00i\x0e\x07d\xec\xab\xc8\x94\xf0\xc6nOF\x8c\x83Dj>_7\x03Z\xab\xdf\x1a\xe1mmK'

C'est à ce stade qu'il vaut mieux faire appel au décodeur de pyasn1 :

In [30]:
from pyasn1.codec.der import decoder
der=decoder.decode(s)
der
Out[30]:
(Sequence(componentType=NamedTypes(), tagSet=TagSet((), Tag(tagClass=0, tagFormat=32, tagId=16))).setComponents(Integer(0, tagSet=TagSet((), Tag(tagClass=0, tagFormat=0, tagId=2))), Integer(21947899418871057600547899600184164286535255686393813848883369539005061966974903632717975547404405377688498698246119115336761797962233119164437937686592348499677702821266248725943408426019416886413266273553580418869329534789408368764644114492743904291759191138798142473379848917157263694338221998233137828316506059658363210784426355829209932750437744915644699589368215604393500512570251448439039174339234594943882252432930148389356065431278080075740904827955486653002978803661178349765543916476670622130238033772643613412029439474122674191196141662398737216668538662719085873248696923636708893334918005871170049625333, tagSet=TagSet((), Tag(tagClass=0, tagFormat=0, tagId=2))), Integer(65537, tagSet=TagSet((), Tag(tagClass=0, tagFormat=0, tagId=2))), Integer(752170256416747720689543044417865220982928487291766573150923111900229933897273808063911577879217762154025482952542587134692875752981912288376453118758661744209776470338343144154735421591461469504008362457868709595808690283916126710795286344365820971959216065699385507350216529104707482147239675420474351319074827895626800077452976607090200352272179206116092705663238953896262736780547569375398172405580017192790111271843829483760709381374398618148457325158556605527041257189035520673675867416662220333297076159385037014779874896103379889164645966815598986280556450522881117230688302684084039068901794849731713370497, tagSet=TagSet((), Tag(tagClass=0, tagFormat=0, tagId=2))), Integer(151132229550931998028954785465498110958408961173188789701671792523790550849941050188464490622045299867266663413469369660730808999250631440291185738591991314179344640828752492162085882700315963215012927499631429869149825715450601026733743628800649098151861979942565897046929301818778286265460750223094054442129, tagSet=TagSet((), Tag(tagClass=0, tagFormat=0, tagId=2))), Integer(145223156464283828233675354131584912470516439230919681655995583241316827086852671556242526573601767577111794530222553939121422626535924932156999713176351858669714807356993569807066527593900547613671018892060638201103718359773049212466225848738822417773654377381123814159194472660844378904445265858731694576677, tagSet=TagSet((), Tag(tagClass=0, tagFormat=0, tagId=2))), Integer(23053678056985629252108900167822521861714976041753030053978865524212797913344533297741421071281670854220743002341475632060147665677534255589834503085343198008009343948686065339340716989716628534423062334464736017850844678233053976597299770467370936024294127187479305930667443280625090068141830110933842901841, tagSet=TagSet((), Tag(tagClass=0, tagFormat=0, tagId=2))), Integer(319088980741518093071841112576837929654307753623944247653437966137443323626451999696338310062997307339428085087081309294497533579827779578415367787622177817850053134250989121446169033881954908774716980033518957244898842544018174261793132462859002214922963064267235748339472421123359179734197755217012741185, tagSet=TagSet((), Tag(tagClass=0, tagFormat=0, tagId=2))), Integer(72520336693795880620748422422090463496328066748690567826651695964311333929233430888821701328088551809372237996216826425089887409434787020615727363564332466190190086024709963875616786812026958589053132389557242832195662985403886408609546368238558286058995485357430777128577542563065086388035707237712582765899, tagSet=TagSet((), Tag(tagClass=0, tagFormat=0, tagId=2)))),
 '')
In [31]:
(version, n, e, d, p, q, e1, e2, c) = (int(x) for x in der[0])
In [32]:
print "e = %d" % e
print hex(e)
print "d = ",d
print e*d % ((p-1)*(q-1))
print "pq-n = ", p*q-n
N-n
e = 65537
0x10001
d =  752170256416747720689543044417865220982928487291766573150923111900229933897273808063911577879217762154025482952542587134692875752981912288376453118758661744209776470338343144154735421591461469504008362457868709595808690283916126710795286344365820971959216065699385507350216529104707482147239675420474351319074827895626800077452976607090200352272179206116092705663238953896262736780547569375398172405580017192790111271843829483760709381374398618148457325158556605527041257189035520673675867416662220333297076159385037014779874896103379889164645966815598986280556450522881117230688302684084039068901794849731713370497
1
pq-n =  0

Out[32]:
0L

On peut décoder les clefs RSA en ligne de commande avec openssl :

$ openssl rsa   -in id_rsa -text
Private-Key: (2048 bit)
modulus:
    00:ad:dc:60:e1:89:37:48:6a:82:5a:ce:8e:b2:c2:
    a5:b0:16:23:51:62:eb:fb:d9:f4:9b:54:0e:6e:4f:
    e2:fe:d2:e5:1b:7d:b4:f0:81:41:7d:59:9b:bb:9c:
    9b:b6:3c:aa:15:c0:fb:b5:36:c0:5e:ec:e4:32:80:
    a5:9f:33:27:1a:3a:b8:cd:6e:f0:90:63:de:38:1a:
    b3:a2:66:7a:c0:1e:01:6e:80:e4:6b:99:f8:df:57:
    97:6f:95:c6:78:78:76:75:7f:f0:f7:8a:f4:da:a4:
    47:cd:fd:84:17:6f:a6:9f:13:a6:1b:0c:a2:a1:d8:
    51:f2:8c:3d:1d:49:e8:51:e3:97:68:db:1e:cd:7f:
    40:57:c3:cd:ca:9a:15:45:5f:1e:31:a6:73:9f:1e:
    b5:c4:94:11:c1:e2:3b:de:6d:5f:1c:4d:60:86:b7:
    a3:f1:2f:93:de:58:67:1e:2d:d7:72:17:f7:8a:c0:
    79:9e:b0:22:b3:31:24:22:1d:0e:99:99:66:19:18:
    5d:1c:9c:aa:09:68:1f:c7:7c:db:0e:02:e0:aa:fa:
    04:68:7f:67:42:f0:cf:dd:1c:85:1b:9c:0a:56:eb:
    df:02:b2:b8:5f:2b:94:5c:d0:39:a3:31:12:19:d9:
    6c:50:f1:39:42:49:99:a2:07:6d:f7:70:10:3f:91:
    4c:f5
publicExponent: 65537 (0x10001)
privateExponent:
    05:f5:55:84:a5:35:35:d0:20:a3:88:0c:af:e7:a7:
    d1:ff:10:3a:cb:cf:16:94:83:a3:87:1f:ef:7b:e1:
    65:a6:48:9f:c6:91:1a:e4:f3:1f:9e:a0:8d:af:72:
    4e:ae:89:8d:b1:4d:6f:0a:6f:51:51:81:08:92:0c:
    1b:06:9f:c2:70:5c:c0:fd:9a:54:f8:77:37:29:03:
    1a:ff:b4:19:3d:6e:03:21:7b:b2:8c:56:51:21:29:
    59:73:a2:97:a2:59:3c:f1:a3:8a:78:42:a7:f3:95:
    5a:63:e3:d1:01:cc:8e:0b:18:58:38:f8:a1:df:4d:
    ff:a7:fa:b8:34:3e:38:00:2c:4b:9b:92:6b:a8:46:
    95:dc:44:ae:50:8e:68:4e:66:69:1f:aa:27:54:a0:
    0d:d0:09:12:be:d7:64:06:79:ac:01:f2:04:d3:a6:
    9c:f9:52:44:9e:a3:08:6a:40:f2:ee:b3:c9:b0:44:
    cf:af:8a:a9:7d:80:7c:76:52:64:a1:59:44:a8:69:
    56:9f:be:67:3c:6a:3b:bc:51:5f:f5:6c:67:04:e4:
    69:68:48:f0:04:8a:5c:59:a9:7a:aa:cd:e3:1e:5c:
    67:6c:21:80:2d:2d:c9:b0:c2:cd:34:51:b4:56:0e:
    c0:60:4d:43:d6:89:c9:7b:02:4c:74:58:91:0b:09:
    81
prime1:
    00:d7:38:2d:24:6e:d5:76:fb:23:38:93:04:00:cb:
    25:f5:a7:a5:ea:8a:5a:fe:aa:bf:86:13:a6:88:96:
    26:0b:f4:bd:5a:18:ec:ca:a9:5c:37:82:5e:1b:ff:
    a3:2b:3a:6e:38:77:55:50:04:3b:7b:bf:4f:6e:ce:
    cf:1c:fe:7f:ba:bc:16:23:1b:1a:85:c2:d3:e0:02:
    c2:a0:bf:5c:70:99:b2:01:39:aa:2c:30:6f:bc:fd:
    c3:2e:b6:1e:e9:1d:dc:bb:59:d4:af:bc:df:ca:45:
    08:d8:08:6a:57:b5:1b:63:07:25:f3:2e:af:95:47:
    22:ef:c8:34:77:88:b8:d4:91
prime2:
    00:ce:cd:fc:d9:67:3f:12:bf:eb:bf:8d:28:93:94:
    cd:7a:a8:c4:aa:05:a1:5d:01:a7:fe:07:25:cc:f1:
    70:d9:23:f5:76:f4:19:54:c3:9d:a5:ff:52:8d:ca:
    bb:c1:bd:0f:55:b6:a1:d0:ee:88:71:f2:b9:22:4b:
    76:32:02:9f:b8:cf:ef:fd:7a:6e:a5:df:ac:ed:e9:
    d2:7e:35:41:68:f3:45:57:7e:8a:31:3c:47:cf:fa:
    79:45:7d:64:72:62:bf:68:4c:f0:2a:56:4e:c1:c9:
    86:95:95:67:ca:f5:c0:a5:d9:0f:b3:f0:0f:ea:5d:
    89:8f:cc:73:c9:56:eb:54:25
exponent1:
    20:d4:5b:e6:7b:d5:aa:21:a2:fc:c5:48:4e:0a:af:
    0e:aa:f5:1f:32:dd:b0:8d:41:4b:e5:81:78:c2:56:
    a9:6a:3a:dc:1c:83:3a:62:dd:43:46:6a:ae:a0:af:
    36:2f:e2:92:50:79:be:0b:f7:3a:e8:32:e8:b7:39:
    56:b5:e7:ac:07:76:e5:02:04:68:b5:10:76:d2:54:
    f8:0a:58:c2:80:5f:6b:da:6c:ff:f2:9f:88:d7:b8:
    c7:4e:56:a6:be:bc:66:03:cc:f2:c5:bf:e9:6d:e0:
    6c:7b:d4:24:ee:e6:6f:93:ae:91:4a:e4:d3:c3:97:
    2b:b6:81:72:5e:73:bb:51
exponent2:
    74:53:69:e6:e0:2c:9a:5f:5a:3c:65:2a:6d:d9:45:
    bb:b9:32:e6:70:44:54:0c:9a:72:49:92:f9:b4:d5:
    c5:4e:74:c4:74:89:cb:24:3d:89:22:15:4d:ac:bb:
    f0:3e:68:61:ce:59:37:2c:f5:93:22:f5:00:55:72:
    26:af:53:28:a1:ce:5c:c6:81:76:cc:5a:79:79:0c:
    ed:f1:06:da:01:fc:ff:3a:2e:81:83:66:e1:96:02:
    a1:13:e7:6c:70:1f:3a:8c:0c:8b:c4:00:89:00:d2:
    b3:51:57:10:d3:2b:8a:1e:8e:b6:a8:52:4b:82:51:
    de:91:22:90:1e:54:41
coefficient:
    67:45:bb:2f:0d:04:4c:39:55:69:32:a0:20:f2:ce:
    5e:85:67:cf:ad:8e:a3:2a:56:43:ae:0d:fe:53:e8:
    1a:ce:40:60:44:c7:74:f6:3b:82:46:ac:7c:54:c1:
    88:71:34:1f:ab:5e:4a:db:c4:5b:d6:07:15:5f:72:
    9a:81:b0:a1:00:74:94:5c:71:cc:bb:f6:1a:19:8b:
    5d:67:0d:fd:64:42:54:db:58:81:cf:e0:0a:49:f3:
    51:59:75:68:b8:ec:80:3c:00:69:0e:07:64:ec:ab:
    c8:94:f0:c6:6e:4f:46:8c:83:44:6a:3e:5f:37:03:
    5a:ab:df:1a:e1:6d:6d:4b
writing RSA key
-----BEGIN RSA PRIVATE KEY-----
MIIEoAIBAAKCAQEArdxg4Yk3SGqCWs6OssKlsBYjUWLr+9n0m1QObk/i/tLlG320
8IFBfVmbu5ybtjyqFcD7tTbAXuzkMoClnzMnGjq4zW7wkGPeOBqzomZ6wB4BboDk
a5n431eXb5XGeHh2dX/w94r02qRHzf2EF2+mnxOmGwyiodhR8ow9HUnoUeOXaNse
zX9AV8PNypoVRV8eMaZznx61xJQRweI73m1fHE1ghrej8S+T3lhnHi3Xchf3isB5
nrAiszEkIh0OmZlmGRhdHJyqCWgfx3zbDgLgqvoEaH9nQvDP3RyFG5wKVuvfArK4
XyuUXNA5ozESGdlsUPE5QkmZogdt93AQP5FM9QIDAQABAoIBAAX1VYSlNTXQIKOI
DK/np9H/EDrLzxaUg6OHH+974WWmSJ/GkRrk8x+eoI2vck6uiY2xTW8Kb1FRgQiS
DBsGn8JwXMD9mlT4dzcpAxr/tBk9bgMhe7KMVlEhKVlzopeiWTzxo4p4QqfzlVpj
49EBzI4LGFg4+KHfTf+n+rg0PjgALEubkmuoRpXcRK5QjmhOZmkfqidUoA3QCRK+
12QGeawB8gTTppz5UkSeowhqQPLus8mwRM+viql9gHx2UmShWUSoaVafvmc8aju8
UV/1bGcE5GloSPAEilxZqXqqzeMeXGdsIYAtLcmwws00UbRWDsBgTUPWicl7Akx0
WJELCYECgYEA1zgtJG7VdvsjOJMEAMsl9ael6opa/qq/hhOmiJYmC/S9Whjsyqlc
N4JeG/+jKzpuOHdVUAQ7e79Pbs7PHP5/urwWIxsahcLT4ALCoL9ccJmyATmqLDBv
vP3DLrYe6R3cu1nUr7zfykUI2AhqV7UbYwcl8y6vlUci78g0d4i41JECgYEAzs38
2Wc/Er/rv40ok5TNeqjEqgWhXQGn/gclzPFw2SP1dvQZVMOdpf9Sjcq7wb0PVbah
0O6IcfK5Ikt2MgKfuM/v/Xpupd+s7enSfjVBaPNFV36KMTxHz/p5RX1kcmK/aEzw
KlZOwcmGlZVnyvXApdkPs/AP6l2Jj8xzyVbrVCUCgYAg1Fvme9WqIaL8xUhOCq8O
qvUfMt2wjUFL5YF4wlapajrcHIM6Yt1DRmquoK82L+KSUHm+C/c66DLotzlWtees
B3blAgRotRB20lT4CljCgF9r2mz/8p+I17jHTlamvrxmA8zyxb/pbeBse9Qk7uZv
k66RSuTTw5crtoFyXnO7UQJ/dFNp5uAsml9aPGUqbdlFu7ky5nBEVAyackmS+bTV
xU50xHSJyyQ9iSIVTay78D5oYc5ZNyz1kyL1AFVyJq9TKKHOXMaBdsxaeXkM7fEG
2gH8/zougYNm4ZYCoRPnbHAfOowMi8QAiQDSs1FXENMrih6OtqhSS4JR3pEikB5U
QQKBgGdFuy8NBEw5VWkyoCDyzl6FZ8+tjqMqVkOuDf5T6BrOQGBEx3T2O4JGrHxU
wYhxNB+rXkrbxFvWBxVfcpqBsKEAdJRcccy79hoZi11nDf1kQlTbWIHP4ApJ81FZ
dWi47IA8AGkOB2Tsq8iU8MZuT0aMg0RqPl83A1qr3xrhbW1L
-----END RSA PRIVATE KEY-----

Il existe un module rsa pour Python qui permet toutes ces manipulations de clefs.

In [33]:
import rsa
In [34]:
help(rsa)
Help on package rsa:

NAME
    rsa - RSA module

FILE
    /usr/lib/python2.7/site-packages/rsa/__init__.py

DESCRIPTION
    Module for calculating large primes, and RSA encryption, decryption, signing
    and verification. Includes generating public and private keys.
    
    WARNING: this implementation does not use random padding, compression of the
    cleartext input to prevent repetitions, or other common security improvements.
    Use with care.
    
    If you want to have a more secure implementation, use the functions from the
    ``rsa.pkcs1`` module.

PACKAGE CONTENTS
    _compat
    _version133
    _version200
    asn1
    bigfile
    cli
    common
    core
    key
    parallel
    pem
    pkcs1
    prime
    randnum
    transform
    util
    varblock

CLASSES
    rsa.key.AbstractKey(__builtin__.object)
        rsa.key.PrivateKey
        rsa.key.PublicKey
    rsa.pkcs1.CryptoError(exceptions.Exception)
        rsa.pkcs1.DecryptionError
        rsa.pkcs1.VerificationError
    
    class DecryptionError(CryptoError)
     |  Raised when decryption fails.
     |  
     |  Method resolution order:
     |      DecryptionError
     |      CryptoError
     |      exceptions.Exception
     |      exceptions.BaseException
     |      __builtin__.object
     |  
     |  Data descriptors inherited from CryptoError:
     |  
     |  __weakref__
     |      list of weak references to the object (if defined)
     |  
     |  ----------------------------------------------------------------------
     |  Methods inherited from exceptions.Exception:
     |  
     |  __init__(...)
     |      x.__init__(...) initializes x; see help(type(x)) for signature
     |  
     |  ----------------------------------------------------------------------
     |  Data and other attributes inherited from exceptions.Exception:
     |  
     |  __new__ = <built-in method __new__ of type object>
     |      T.__new__(S, ...) -> a new object with type S, a subtype of T
     |  
     |  ----------------------------------------------------------------------
     |  Methods inherited from exceptions.BaseException:
     |  
     |  __delattr__(...)
     |      x.__delattr__('name') <==> del x.name
     |  
     |  __getattribute__(...)
     |      x.__getattribute__('name') <==> x.name
     |  
     |  __getitem__(...)
     |      x.__getitem__(y) <==> x[y]
     |  
     |  __getslice__(...)
     |      x.__getslice__(i, j) <==> x[i:j]
     |      
     |      Use of negative indices is not supported.
     |  
     |  __reduce__(...)
     |  
     |  __repr__(...)
     |      x.__repr__() <==> repr(x)
     |  
     |  __setattr__(...)
     |      x.__setattr__('name', value) <==> x.name = value
     |  
     |  __setstate__(...)
     |  
     |  __str__(...)
     |      x.__str__() <==> str(x)
     |  
     |  __unicode__(...)
     |  
     |  ----------------------------------------------------------------------
     |  Data descriptors inherited from exceptions.BaseException:
     |  
     |  __dict__
     |  
     |  args
     |  
     |  message
    
    class PrivateKey(AbstractKey)
     |  Represents a private RSA key.
     |  
     |  This key is also known as the 'decryption key'. It contains the 'n', 'e',
     |  'd', 'p', 'q' and other values.
     |  
     |  Supports attributes as well as dictionary-like access. Attribute accesss is
     |  faster, though.
     |  
     |  >>> PrivateKey(3247, 65537, 833, 191, 17)
     |  PrivateKey(3247, 65537, 833, 191, 17)
     |  
     |  exp1, exp2 and coef don't have to be given, they will be calculated:
     |  
     |  >>> pk = PrivateKey(3727264081, 65537, 3349121513, 65063, 57287)
     |  >>> pk.exp1
     |  55063
     |  >>> pk.exp2
     |  10095
     |  >>> pk.coef
     |  50797
     |  
     |  If you give exp1, exp2 or coef, they will be used as-is:
     |  
     |  >>> pk = PrivateKey(1, 2, 3, 4, 5, 6, 7, 8)
     |  >>> pk.exp1
     |  6
     |  >>> pk.exp2
     |  7
     |  >>> pk.coef
     |  8
     |  
     |  Method resolution order:
     |      PrivateKey
     |      AbstractKey
     |      __builtin__.object
     |  
     |  Methods defined here:
     |  
     |  __eq__(self, other)
     |  
     |  __getitem__(self, key)
     |  
     |  __init__(self, n, e, d, p, q, exp1=None, exp2=None, coef=None)
     |  
     |  __ne__(self, other)
     |  
     |  __repr__(self)
     |  
     |  ----------------------------------------------------------------------
     |  Data descriptors defined here:
     |  
     |  coef
     |  
     |  d
     |  
     |  e
     |  
     |  exp1
     |  
     |  exp2
     |  
     |  n
     |  
     |  p
     |  
     |  q
     |  
     |  ----------------------------------------------------------------------
     |  Methods inherited from AbstractKey:
     |  
     |  save_pkcs1(self, format='PEM')
     |      Saves the public key in PKCS#1 DER or PEM format.
     |      
     |      :param format: the format to save; 'PEM' or 'DER'
     |      :returns: the DER- or PEM-encoded public key.
     |  
     |  ----------------------------------------------------------------------
     |  Class methods inherited from AbstractKey:
     |  
     |  load_pkcs1(cls, keyfile, format='PEM') from __builtin__.type
     |      Loads a key in PKCS#1 DER or PEM format.
     |      
     |      :param keyfile: contents of a DER- or PEM-encoded file that contains
     |          the public key.
     |      :param format: the format of the file to load; 'PEM' or 'DER'
     |      
     |      :return: a PublicKey object
     |  
     |  ----------------------------------------------------------------------
     |  Data descriptors inherited from AbstractKey:
     |  
     |  __dict__
     |      dictionary for instance variables (if defined)
     |  
     |  __weakref__
     |      list of weak references to the object (if defined)
    
    class PublicKey(AbstractKey)
     |  Represents a public RSA key.
     |  
     |  This key is also known as the 'encryption key'. It contains the 'n' and 'e'
     |  values.
     |  
     |  Supports attributes as well as dictionary-like access. Attribute accesss is
     |  faster, though.
     |  
     |  >>> PublicKey(5, 3)
     |  PublicKey(5, 3)
     |  
     |  >>> key = PublicKey(5, 3)
     |  >>> key.n
     |  5
     |  >>> key['n']
     |  5
     |  >>> key.e
     |  3
     |  >>> key['e']
     |  3
     |  
     |  Method resolution order:
     |      PublicKey
     |      AbstractKey
     |      __builtin__.object
     |  
     |  Methods defined here:
     |  
     |  __eq__(self, other)
     |  
     |  __getitem__(self, key)
     |  
     |  __init__(self, n, e)
     |  
     |  __ne__(self, other)
     |  
     |  __repr__(self)
     |  
     |  ----------------------------------------------------------------------
     |  Class methods defined here:
     |  
     |  load_pkcs1_openssl_der(cls, keyfile) from __builtin__.type
     |      Loads a PKCS#1 DER-encoded public key file from OpenSSL.
     |      
     |      @param keyfile: contents of a DER-encoded file that contains the public
     |          key, from OpenSSL.
     |      @return: a PublicKey object
     |  
     |  load_pkcs1_openssl_pem(cls, keyfile) from __builtin__.type
     |      Loads a PKCS#1.5 PEM-encoded public key file from OpenSSL.
     |      
     |      These files can be recognised in that they start with BEGIN PUBLIC KEY
     |      rather than BEGIN RSA PUBLIC KEY.
     |      
     |      The contents of the file before the "-----BEGIN PUBLIC KEY-----" and
     |      after the "-----END PUBLIC KEY-----" lines is ignored.
     |      
     |      @param keyfile: contents of a PEM-encoded file that contains the public
     |          key, from OpenSSL.
     |      @return: a PublicKey object
     |  
     |  ----------------------------------------------------------------------
     |  Data descriptors defined here:
     |  
     |  e
     |  
     |  n
     |  
     |  ----------------------------------------------------------------------
     |  Methods inherited from AbstractKey:
     |  
     |  save_pkcs1(self, format='PEM')
     |      Saves the public key in PKCS#1 DER or PEM format.
     |      
     |      :param format: the format to save; 'PEM' or 'DER'
     |      :returns: the DER- or PEM-encoded public key.
     |  
     |  ----------------------------------------------------------------------
     |  Class methods inherited from AbstractKey:
     |  
     |  load_pkcs1(cls, keyfile, format='PEM') from __builtin__.type
     |      Loads a key in PKCS#1 DER or PEM format.
     |      
     |      :param keyfile: contents of a DER- or PEM-encoded file that contains
     |          the public key.
     |      :param format: the format of the file to load; 'PEM' or 'DER'
     |      
     |      :return: a PublicKey object
     |  
     |  ----------------------------------------------------------------------
     |  Data descriptors inherited from AbstractKey:
     |  
     |  __dict__
     |      dictionary for instance variables (if defined)
     |  
     |  __weakref__
     |      list of weak references to the object (if defined)
    
    class VerificationError(CryptoError)
     |  Raised when verification fails.
     |  
     |  Method resolution order:
     |      VerificationError
     |      CryptoError
     |      exceptions.Exception
     |      exceptions.BaseException
     |      __builtin__.object
     |  
     |  Data descriptors inherited from CryptoError:
     |  
     |  __weakref__
     |      list of weak references to the object (if defined)
     |  
     |  ----------------------------------------------------------------------
     |  Methods inherited from exceptions.Exception:
     |  
     |  __init__(...)
     |      x.__init__(...) initializes x; see help(type(x)) for signature
     |  
     |  ----------------------------------------------------------------------
     |  Data and other attributes inherited from exceptions.Exception:
     |  
     |  __new__ = <built-in method __new__ of type object>
     |      T.__new__(S, ...) -> a new object with type S, a subtype of T
     |  
     |  ----------------------------------------------------------------------
     |  Methods inherited from exceptions.BaseException:
     |  
     |  __delattr__(...)
     |      x.__delattr__('name') <==> del x.name
     |  
     |  __getattribute__(...)
     |      x.__getattribute__('name') <==> x.name
     |  
     |  __getitem__(...)
     |      x.__getitem__(y) <==> x[y]
     |  
     |  __getslice__(...)
     |      x.__getslice__(i, j) <==> x[i:j]
     |      
     |      Use of negative indices is not supported.
     |  
     |  __reduce__(...)
     |  
     |  __repr__(...)
     |      x.__repr__() <==> repr(x)
     |  
     |  __setattr__(...)
     |      x.__setattr__('name', value) <==> x.name = value
     |  
     |  __setstate__(...)
     |  
     |  __str__(...)
     |      x.__str__() <==> str(x)
     |  
     |  __unicode__(...)
     |  
     |  ----------------------------------------------------------------------
     |  Data descriptors inherited from exceptions.BaseException:
     |  
     |  __dict__
     |  
     |  args
     |  
     |  message

FUNCTIONS
    decrypt(crypto, priv_key)
        Decrypts the given message using PKCS#1 v1.5
        
        The decryption is considered 'failed' when the resulting cleartext doesn't
        start with the bytes 00 02, or when the 00 byte between the padding and
        the message cannot be found.
        
        :param crypto: the crypto text as returned by :py:func:`rsa.encrypt`
        :param priv_key: the :py:class:`rsa.PrivateKey` to decrypt with.
        :raise DecryptionError: when the decryption fails. No details are given as
            to why the code thinks the decryption fails, as this would leak
            information about the private key.
        
        
        >>> import rsa
        >>> (pub_key, priv_key) = rsa.newkeys(256)
        
        It works with strings:
        
        >>> crypto = encrypt('hello', pub_key)
        >>> decrypt(crypto, priv_key)
        'hello'
        
        And with binary data:
        
        >>> crypto = encrypt('\x00\x00\x00\x00\x01', pub_key)
        >>> decrypt(crypto, priv_key)
        '\x00\x00\x00\x00\x01'
        
        Altering the encrypted information will *likely* cause a
        :py:class:`rsa.pkcs1.DecryptionError`. If you want to be *sure*, use
        :py:func:`rsa.sign`.
        
        
        .. warning::
        
            Never display the stack trace of a
            :py:class:`rsa.pkcs1.DecryptionError` exception. It shows where in the
            code the exception occurred, and thus leaks information about the key.
            It's only a tiny bit of information, but every bit makes cracking the
            keys easier.
        
        >>> crypto = encrypt('hello', pub_key)
        >>> crypto = crypto[0:5] + 'X' + crypto[6:] # change a byte
        >>> decrypt(crypto, priv_key)
        Traceback (most recent call last):
        ...
        DecryptionError: Decryption failed
    
    encrypt(message, pub_key)
        Encrypts the given message using PKCS#1 v1.5
        
        :param message: the message to encrypt. Must be a byte string no longer than
            ``k-11`` bytes, where ``k`` is the number of bytes needed to encode
            the ``n`` component of the public key.
        :param pub_key: the :py:class:`rsa.PublicKey` to encrypt with.
        :raise OverflowError: when the message is too large to fit in the padded
            block.
            
        >>> from rsa import key, common
        >>> (pub_key, priv_key) = key.newkeys(256)
        >>> message = 'hello'
        >>> crypto = encrypt(message, pub_key)
        
        The crypto text should be just as long as the public key 'n' component:
        
        >>> len(crypto) == common.byte_size(pub_key.n)
        True
    
    newkeys(nbits, accurate=True, poolsize=1)
        Generates public and private keys, and returns them as (pub, priv).
        
        The public key is also known as the 'encryption key', and is a
        :py:class:`rsa.PublicKey` object. The private key is also known as the
        'decryption key' and is a :py:class:`rsa.PrivateKey` object.
        
        :param nbits: the number of bits required to store ``n = p*q``.
        :param accurate: when True, ``n`` will have exactly the number of bits you
            asked for. However, this makes key generation much slower. When False,
            `n`` may have slightly less bits.
        :param poolsize: the number of processes to use to generate the prime
            numbers. If set to a number > 1, a parallel algorithm will be used.
            This requires Python 2.6 or newer.
        
        :returns: a tuple (:py:class:`rsa.PublicKey`, :py:class:`rsa.PrivateKey`)
        
        The ``poolsize`` parameter was added in *Python-RSA 3.1* and requires
        Python 2.6 or newer.
    
    sign(message, priv_key, hash)
        Signs the message with the private key.
        
        Hashes the message, then signs the hash with the given key. This is known
        as a "detached signature", because the message itself isn't altered.
        
        :param message: the message to sign. Can be an 8-bit string or a file-like
            object. If ``message`` has a ``read()`` method, it is assumed to be a
            file-like object.
        :param priv_key: the :py:class:`rsa.PrivateKey` to sign with
        :param hash: the hash method used on the message. Use 'MD5', 'SHA-1',
            'SHA-256', 'SHA-384' or 'SHA-512'.
        :return: a message signature block.
        :raise OverflowError: if the private key is too small to contain the
            requested hash.
    
    verify(message, signature, pub_key)
        Verifies that the signature matches the message.
        
        The hash method is detected automatically from the signature.
        
        :param message: the signed message. Can be an 8-bit string or a file-like
            object. If ``message`` has a ``read()`` method, it is assumed to be a
            file-like object.
        :param signature: the signature block, as created with :py:func:`rsa.sign`.
        :param pub_key: the :py:class:`rsa.PublicKey` of the person signing the message.
        :raise VerificationError: when the signature doesn't match the message.
        
        .. warning::
        
            Never display the stack trace of a
            :py:class:`rsa.pkcs1.VerificationError` exception. It shows where in
            the code the exception occurred, and thus leaks information about the
            key. It's only a tiny bit of information, but every bit makes cracking
            the keys easier.

DATA
    __all__ = ['newkeys', 'encrypt', 'decrypt', 'sign', 'verify', 'PublicK...
    __author__ = 'Sybren Stuvel, Barry Mead and Yesudeep Mangalapilly'
    __date__ = '2015-11-05'
    __version__ = '3.2.3'

VERSION
    3.2.3

DATE
    2015-11-05

AUTHOR
    Sybren Stuvel, Barry Mead and Yesudeep Mangalapilly



Signature numérique RSA (DSA, Digital Signature Algorithm)

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.

In [35]:
(KP,KS) = rsa.newkeys(512)
print KP
print KS
message = 'La clef du coffre est dans le pot de fleurs'
signature = rsa.sign(message, KS, 'SHA-1')
print message
signature
PublicKey(9462576490545467844319027004139731912085203641764140107500636774309932308371598249550868269337954653357656638572272611864966278011678640859485449715432251, 65537)
PrivateKey(9462576490545467844319027004139731912085203641764140107500636774309932308371598249550868269337954653357656638572272611864966278011678640859485449715432251, 65537, 1979810623592160994267398542514365991401991429816285291576494673990841688436657843502398362266452424687138678776875634435082544317333473791530356871726977, 5638718646821333633482907185573892401961248045345762066534541647032107735145757919, 1678143046892351102795359365622102567250534089910255147862126474903515429)
La clef du coffre est dans le pot de fleurs

Out[35]:
'\x02D\xc9\xdc\x8fk\x95\xa0,gt\xb2\xc0p4\xf5\r\x88\x84\xf9\xef\xb2\x9f\xc2\xdd\xb1\xd7NJ\x1d\x04%\xab\xc3)\xb7[x\xc4\xccz\xeb\xaa\xdaY`\xbe\xa79:\xe7?\xb0I\xdf\t\x18\xc0Y\xd0Y\x1c\x8e\xfa'
In [36]:
rsa.verify(message, signature, KP)
Out[36]:
True

Attaques contre le RSA

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 aujorud'hui sera peut-être possible demain, avec la découverte de nouveaux algorithmes et l'augmentation de la puissance des machines.

Factorisation du module

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

$$ K = 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) quelque soit la question posée (les fameuses yescards).

L'histoire est racontée sur ce site (qui, officiellement, n'existe plus, il faut revenir en arrière après la redirection).

Le programme msieve répond en environ 20 minutes sur une station de travail moyennement récente.

Les clefs faibles

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.

Les erreurs de protocole

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é.

Autres attaques

Il y en a beaucoup, voir ici pour plus d'information.

In [103]:
 
In []: