RSA et le reste chinois

Dans cet article, nous expliquons comment le théorème des restes chinois permet d’optimiser les calculs avec la clé privée de RSA. Notons que ce théorème peut aussi être utilisé pour « casser » le chiffrement RSA sous certaines hypothèses.

Si vous vérifiez le contenu via OpenSSL d’une de vos clés privées vous obtiendrez très probablement quelque chose de similaire à ça :

jshmendes@host:~$ openssl asn1parse -in prik128
    0:d=0  hl=2 l=  98 cons: SEQUENCE
    2:d=1  hl=2 l=   1 prim: INTEGER           :00
    5:d=1  hl=2 l=  17 prim: INTEGER           :C925F755E4C90549E83899451F9DB64B
   24:d=1  hl=2 l=   3 prim: INTEGER           :010001
   29:d=1  hl=2 l=  16 prim: INTEGER           :6FEC322D96F9CB78919A4F85F11A4401
   47:d=1  hl=2 l=   9 prim: INTEGER           :E9E950909283A501
   58:d=1  hl=2 l=   9 prim: INTEGER           :DC249F02A3D15F4B
   69:d=1  hl=2 l=   9 prim: INTEGER           :BB3584C970B9F401
   80:d=1  hl=2 l=   8 prim: INTEGER           :2DA2E1DBD83E0535
   90:d=1  hl=2 l=   8 prim: INTEGER           :1BE3176D387AF685

Y a beaucoup de choses là dedans… En cherchant un peu, on trouve comment interpréter ces données. Selon PKCS#1, une clé privée peut se représenter de plusieurs façons. Pour l’une d’elles, la structure ASN.1 est la suivante :

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,  -- (inverse of q) mod p
  otherPrimeInfos   OtherPrimeInfos OPTIONAL
}

Ca ressemble assez à ce que nous avons obtenu avec OpenSSL… Mais autant on peut comprendre la nécessité d’avoir n,p,q,e,d dans la clé privée autant le reste est surprenant : à quoi cela sert-il d’avoir d \mod q-1  dans la clé privée ?

Rappelons avant d’aborder la suite qu’une opération de chiffrement ou signature pour RSA, c’est mathématiquement la même chose : Cette opération nécessite une exponentiation modulaire qui est particulièrement couteuse lorsque N est grand (ce qui est le cas dans la pratique).  Il serait donc intéressant si nous trouvions une méthode qui soit moins gourmande et qui nous fournisse le même résultat.

C’est là qu’intervient le théorème du reste chinois. Il permet une optimisation majeure dans les temps de calculs mais en contrepartie il doit utiliser des informations dérivées de la clé privée. Son utilisation est donc réservée aux opérations de signature ou déchiffrement.

On pose les notations suivantes :

d_p = d \mod (p-1)
d_q = d \mod (q-1)
qInv = q^{-1} \mod p

L’opération M = c^d \mod n est alors équivalente aux suivantes :

S_p = c^{d_p} \mod p
S_q = c^{d_q} \mod q
h = qInv.(S_p - S_q) \mod p
S = S_q + h.q

Soit S = (((S_p - S_q) * q^{-1} ) \mod p) * q +S_q

Notons que cette dernière égalité est aussi connue sous le nom de « formule de Garner« .

Rien de trivial à tout cela : démontrons donc ici que M = S

Il faut utiliser le théorème d’Euler et remarquerque

d = x*\phi(p) + d \mod \phi(p)

Nous pouvons alors montrer que : m^{d_p} \mod p = m^{d} \mod p
De même :  m^{d_q} \mod q = m^{d} \mod q

Reprenons : S = (((S_p - S_q) * q^{-1} ) \mod p) * q +S_q

En mettons le tout modulo q :

S \mod q = ( (((S_p - S_q) * q^{-1} ) \mod p) * q ) \mod p+S_q \mod q

Comme le premier membre à droite de l’égalité est un multiple de q, on peut simplifier :

S \mod q = S_q \mod q

Or par définition S_q est déjà inférieur à q, nous avons alors  :

S \mod q = S_q

De même pour le calcul modulo p:

S \mod p = ((S_p-S_q)*q^{-1} \mod p *q + S_q) \mod p
S \mod p = (S_p-S_q)*q^{-1} *q \mod p + S_q \mod p
S \mod p = (S_p-S_q) \mod p + S_q \mod p
S \mod p = S_p \mod p

Et comme définition S_p  est déjà inférieur à p, nous avons alors  :
S \mod p = S_p

En utilisant ce qui est écrit plus haut, on retombe bien sur :
S \mod p = c^d \mod p
S \mod q = c^d \mod q

Enfin en utilisant l’unicité de la solution avec le théorème du reste chinois, on a directement : S \mod n= c^d \mod n

On y est presque mais pas encore, il reste à montrer que  S \in \{0, \cdots, n-1\}

S est positif par compositions de sommes et produits d’entiers positifs. De plus,

S = (((S_q - S_p) * p^{-1} ) \mod q) * p +S_p \leq (q-1)*p+p-1 = qp-1 = n-1 < n

Donc S = M

CQFD

Vous allez me dire que nous venons de déchiffrer un message en effectuant deux exponentiations modulaires au lieu d’une… Et vous avez raison, simplement remarquons que les exponentiations modulaires sont indifférentes de l’opération de déchiffrement et peuvent donc être précalculées : d’où leurs présences dans la clé privée.

Publicités

A propos JoMendes

Amateur de mathématiques et d'hexadécimal. Je m'intéresse de près ou de loin suivant mon niveau à tous les sujets de sécurité de l'information.
Cet article, publié dans Cryptographie Asymétrique, est tagué , , . Ajoutez ce permalien à vos favoris.

Un commentaire pour RSA et le reste chinois

  1. Ping : Les classiques de RSA | Cryptobourrin

Laisser un commentaire

Entrez vos coordonnées ci-dessous ou cliquez sur une icône pour vous connecter:

Logo WordPress.com

Vous commentez à l'aide de votre compte WordPress.com. Déconnexion / Changer )

Image Twitter

Vous commentez à l'aide de votre compte Twitter. Déconnexion / Changer )

Photo Facebook

Vous commentez à l'aide de votre compte Facebook. Déconnexion / Changer )

Photo Google+

Vous commentez à l'aide de votre compte Google+. Déconnexion / Changer )

Connexion à %s