RSA, déchiffrer sans la clé privée

 druide

Prés en bulles

Toute l'explication mathématique sur RSA provient des vidéos très bien faites de l'université de Lille1.

Le but de ce post ? La résolution d'un challenge avec, au passage, l'apprentissage de RSA. J'aurai pu utiliser Cryptool et résoudre le challenge en 30' sans rien y comprendre mais voilà... on se refait pas...

Mathématique

Commençons avec quelques définitions ou quelques bases nécessaires.

Congruences

On note une congruence ainsi :

𝑎 ≡ 𝑏 (𝐦𝐨𝐝 𝑛)

Ce qui signifie que 𝑎 et 𝑏 sont liés par 𝑎 (𝐦𝐨𝐝 𝑛) = 𝑏 (𝐦𝐨𝐝 𝑛). On trouve un exemple simple avec les heures, en effet, si on dit qu'il est 9h ou 21h, l'aiguille des heures se trouve dans les deux cas à la même place. Dans cet exemple, 𝑛 = 12 et 9 (𝐦𝐨𝐝 12) = 9 de même que 21 (𝐦𝐨𝐝 12) = 9.

Petit théorème de Fermat

Si 𝑝 est un nombre premier et 𝑎 ∈ ℤ alors

𝑎 𝑝 ≡ 𝑎 (𝐦𝐨𝐝 𝑝)

Corollaire du petit théorème de Fermat

Si 𝑝 ne divise pas 𝑎 alors


𝑎 𝑝 ∶ 𝑎 ≡ 𝑎 ∶ 𝑎 (𝐦𝐨𝐝 𝑝) 𝑎 𝑝 ∙ 𝑎 -1 ≡ 1 (𝐦𝐨𝐝 𝑝) 𝑎 𝑝-1 ≡ 1 (𝐦𝐨𝐝 𝑝)

Petit théorème de Fermat amélioré

Soit 𝑝 et 𝑞 deux nombres premiers distincts et soit 𝑛 = 𝑝𝑞, pour tout 𝑎 ∈ ℤ tel que PGDC(𝑎, 𝑛) = 1 alors

𝑎 (𝑝-1)(𝑞-1) ≡ 1 (𝐦𝐨𝐝 𝑛)
  • PGDC(𝑎, 𝑛) = 1 ⬄ 𝑝 et 𝑞 ne divise pas 𝑎

Exemple

𝑝 = 5, 𝑞 = 7
𝑛 = 𝑝 ∙ 𝑞 = 35
(𝑝-1) ∙ (𝑞-1) = 24
Pour 𝑎 = 1, 2, 3, 4, 5̶, 6, 7̶, 8, 9, 1̶0̶, 11, 12, 13, 1̶4̶, 1̶5̶, 16... ainsi

𝑎 24 ≡ 1 (𝐦𝐨𝐝 35)


5̶, 7̶, 1̶0̶, 1̶4̶, 1̶5̶ etc sont exclus car 𝑎 ne doit pas être divisible ni par 𝑝 = 5, ni par 𝑞 = 7

Démonstration

Notons

𝑐 = 𝑎 (𝑝-1)(𝑞-1)


Calculons 𝑐 (𝐦𝐨𝐝 𝑞)

𝑐 ≡ 𝑎 (𝑝-1)(𝑞-1)      | on sait que 𝑥 𝑎 ∙ 𝑏 = (𝑥 𝑎)𝑏 𝑐 ≡ (𝑎 (𝑝-1))(𝑞-1)      | on sait que 𝑎 𝑝-1 ≡ 1 (𝐦𝐨𝐝 𝑝) 𝑐 ≡ (1 (𝐦𝐨𝐝 𝑝))(𝑞-1)      | on sait que 1 (𝐦𝐨𝐝 𝑝) = 1 𝑐 ≡ 1 (𝑞-1)      | on sait que 1 𝑥 = 1 = 1 (𝐦𝐨𝐝 𝑞)

𝑐 ≡ 1 (𝐦𝐨𝐝 𝑞)

On peut faire la même chose avec 𝑐 (𝐦𝐨𝐝 𝑝)

𝑐 ≡ 𝑎 (𝑝-1)(𝑞-1)      | on sait que 𝑥 𝑎 ∙ 𝑏 = (𝑥 𝑎)𝑏 𝑐 ≡ (𝑎 (𝑞-1))(𝑝-1)      | on sait que 𝑎 𝑞-1 ≡ 1 (𝐦𝐨𝐝 𝑞) 𝑐 ≡ (1 (𝐦𝐨𝐝 𝑞))(𝑝-1)      | on sait que 1 (𝐦𝐨𝐝 𝑞) = 1 𝑐 ≡ 1 (𝑝-1)      | on sait que 1 𝑥 = 1 = 1 (𝐦𝐨𝐝 𝑝)

𝑐 ≡ 1 (𝐦𝐨𝐝 𝑝)

Donc
𝑐 ≡ 1 (𝐦𝐨𝐝 𝑝) et 𝑐 ≡ 1 (𝐦𝐨𝐝 𝑞)

Déduction de 𝑐 ≡ 1 (𝐦𝐨𝐝 𝑝𝑞)

  • comme 𝑐 ≡ 1 (𝐦𝐨𝐝 𝑝) alors il existe 𝛼 ∈ ℤ tel que 𝑐 = 1 + 𝛼𝑝
  • comme 𝑐 ≡ 1 (𝐦𝐨𝐝 𝑞) alors il existe 𝛽 ∈ ℤ tel que 𝑐 = 1 + 𝛽𝑞
  • donc 𝑐 - 1 = 𝛼𝑝 = 𝛽𝑞 ⇒ 𝛼 = 𝛽𝑞 ∶ 𝑝 on dit aussi que 𝑝∣𝛽𝑞 (que 𝑝 divise 𝛽𝑞)
  • comme 𝑝 et 𝑞 sont premier entre eux et selon le lemme de Gauss, 𝑝∣𝛽
  • il existe donc 𝛽' ∈ ℤ tel que 𝛽 = 𝛽'𝑝 qui est issu de 𝛽' = 𝛽 ∶ 𝑝
  • ainsi, 𝑐 = 1 + 𝛽𝑞 = 1 + 𝛽'𝑝𝑞
  • donc 𝑐 ≡ 1 (𝐦𝐨𝐝 𝑝𝑞)
  • ce qui revient à dire que 𝑎 (𝑝-1)(𝑞-1) ≡ 1 (𝐦𝐨𝐝 𝑛)


Lemme de Gauss : si un nombre entier 𝑎 divise le produit de deux autres nombres entier 𝑏 et 𝑐 et si 𝑎 est premier avec 𝑏, alors 𝑎 divise 𝑐

Inverse modulo

Soit 𝑎 ∈ ℤ, on dit que 𝑥 ∈ ℤ est un inverse modulo de 𝑎 (𝐦𝐨𝐝 𝑛) si


𝑎 ∙ 𝑥 ≡ 1 (𝐦𝐨𝐝 𝑛)

Règles

  • 𝑎 admet un inverse 𝐦𝐨𝐝 𝑛 ssi PGDC(𝑎, 𝑛) = 1
  • si 𝑎𝓾 + 𝑛𝓿 = 1 alors 𝓾 est un inverse de 𝑎 (𝐦𝐨𝐝 𝑛)

Exemple simple

Si on prend 𝑛 = 13

22 ≡ 9 (𝐦𝐨𝐝 13) et 3 est l'inverse modulo 13 de 9 car 3 ∙ 9 ≡ 1 (𝐦𝐨𝐝 13) en effet, 3 ∙ 9 = 27 et 27 (𝐦𝐨𝐝 13) = 1

Formalisme

PGDC(𝑎, 𝑛) = 1
      ⬄ ∃𝓾 , 𝓿 ∈ ℤ tel que 𝑎𝓾 + 𝑛𝓿 = 1
      ⬄ ∃𝓾 ∈ ℤ tel que 𝑎𝓾 ≡ 1 (𝐦𝐨𝐝 𝑛)

RSA

RSA se base sur

  • un problème difficile, à savoir, la factorisation de nombres premiers distincts
  • une clé publique et une clé privée trouvées grâce à l'algorithme d'Euclide et les coefficients de Bézout
  • tout les calculs sont effectués 𝐦𝐨𝐝
  • le déchiffrement se réalise grâce au petit théorème de Fermat

Étape I

  1. Alice choisit deux nombre premiers 𝑝 et 𝑞 de plusieurs centaines de chiffres. Elle calcul

    𝑛 = 𝑝 ∙ 𝑞
    𝜑(𝑛) = (𝑝-1) ∙ (𝑞-1)

  2. Elle choisit ensuite 𝑒 ∈ ℤ tel que PGDC(𝑒, 𝜑(𝑛)) = 1 et que 𝑒 < 𝜑(𝑛)
  3. Elle termine la préparation des clés en calculant 𝑑 l'inverse de 𝑒 modulo 𝜑(𝑛) tel que 𝑑 ∙ 𝑒 ≡ 1 (𝐦𝐨𝐝 𝜑(𝑛)) grâce aux coefficients de Bézout et à l'algorithme d'Euclide étendu


Alice possède alors sa clé privée composée de (𝑑, 𝑛) et sa clé publique composée de (𝑒, 𝑛).

Chiffrement

Soit 𝑑 l'inverse de 𝑒 𝐦𝐨𝐝 𝜑(𝑛) avec 𝑛 = 𝑝𝑞 et (𝑝 ≠ 𝑞)

Si 𝑥 ≡ 𝑚 𝑒 (𝐦𝐨𝐝 𝑛) alors 𝑚 ≡ 𝑥 𝑑 (𝐦𝐨𝐝 𝑛)

Exemple

Soit :

Le message chiffré
1221452609927320607780724
1070635318622894620123042
1234660723733489496548997
1187680576276238932467507
0462335466800705147652322
0155857522345508720927245
0734726920089060482937205
0717552499748517415525649
0216175998279034013180163
0744631996076889398831580
0843146475217094457104881
0196052595269218722591822
1204699116114648990915780
1425141587631982783760667
𝑛 = 1487932939581322413763429 𝑒 = 157

Trouver 𝑝 et 𝑞

Après avoir compilé et installé le programme msieve, je lui demande de me fournir les deux nombres premiers

druide@druid.es:~$ ./msieve -v 1487932939581322413763429
  Msieve v. 1.52 (SVN unknown)
  Sat May  2 18:20:56 2015
  random seeds: 9c4ad4bd d1d88f0f
  factoring 1487932939581322413763429 (25 digits)
  prp11 factor: 21646157677
  prp14 factor: 68738894069977
  elapsed time 00:00:00

𝑝 = 21646157677
𝑞 = 68738894069977

Trouve la clé privée 𝑑

Pour trouver la clé privée à partir de ce qui est connu, on doit utiliser L'algorithme d'Euclide étendu à partir de 𝑝 et 𝑞. On trouve une explication de cet algorithme sur Wikipédia. Pour l'implémentation, j'ai utilisé la libraire openssl et les BIGNUM.


     ...
    /* Initialisation */
    BN_copy(_r, e); BN_copy(_rp, phi_n);
    BN_one(_u);BN_zero(_v);BN_zero(_up);BN_one(_vp);


    /* Calcul */
    while(BN_is_zero(_rp) == 0)
    {
        BN_div(_q, _rem, _r, _rp, ctx);
        BN_copy(_rs, _r);BN_copy(_us, _u);BN_copy(_vs, _v);
        BN_copy(_r, _rp);BN_copy(_u, _up);BN_copy(_v, _vp);
        BN_mul(_tmp, _q, _rp, ctx);BN_sub(_rp, _rs, _tmp);BN_clear(_tmp);
        BN_mul(_tmp, _q, _up, ctx);BN_sub(_up, _us, _tmp);BN_clear(_tmp);
        BN_mul(_tmp, _q, _vp, ctx);BN_sub(_vp, _vs, _tmp);BN_clear(_tmp);
    }

    BN_copy(d, _u); /* on a 𝑑 */

druide@druid.es:~$ ./findd
𝑑=653932310995966683273685

Déchiffrement

Il ne reste plus qu'à appliquer 𝑚 ≡ 𝑥 𝑑 (𝐦𝐨𝐝 𝑛) en utilisant pour 𝑥 les valeurs, lignes par lignes, du message chiffré. Openssl, fournit la fonction
BN_mod_exp(result, x, d, n, ctx);


On obtient alors le message

bravo tu connais le vigenere la cle est de trois lettres et le texte a decrypter qui sera le pass a valider est **************** bon courage

That's all folks

Liens

Wikipedia

  • 4 years 1 week before
  • |