====== RSA ======

===== Principe du chall =====

  While sniffing HZV network, you just caught an encrypted message for John. Might contain interesting stuff.

Après détarrage du .tar, on se retrouve avec 4 fichiers et un dossier :

<code bash>
% tar xvf rsa.tar
librsa/
librsa/__init__.pyc
librsa/__init__.py
decrypt.py
flag.asc
john.pub
README
% cat flag.asc
----- BEGIN MESSAGE -----
eJw1krt1HUEMQ3NVosiHIMFfD68J5wrcf2TM7Crce0gQwOz3zz98fRCgkT5DEjWfr7+fjU6rxWA2
3A+CO6NsTN9cuygYHWRsrTHzMG/mTld1Gwd3DB5M93SaC98DgslEc3zuIrgENlZkgwd12HDHNPkr
JaMdbr0zI3xYdSZg1dDdfkzMSjyHxZ6IZ1POfGxNGQIP89J1erlVbV+2x49ceBjsHcPRC3SHwj3W
FN3G4TgpM2+myqytE7QLbyhjWA3YYDheVqMOvWRNk/U4Wa5i9God9cx5+8LpUtUTzVNSri6G9xr6
dac4Mh8qWW9xV1Mtekjw+O23uUrEdkVQD33Vasow0yrEG++BU5oKVgIp4j2qh1HfEaN/oMX+/AcX
TXp2
-----  END MESSAGE  -----
% cat john.pub 
----- BEGIN PUBLIC KEY -----
KG4gPSAxNTQ5Mzg4MzAyOTk5NTE5LCBlID0gMTAxKQ==
-----  END PUBLIC KEY  -----
% echo "KG4gPSAxNTQ5Mzg4MzAyOTk5NTE5LCBlID0gMTAxKQ==" | base64 -d
(n = 1549388302999519, e = 101)
</code>
Comme le nom du chall l'indique, nous avons donc affaire à du RSA.
''decrypt.py'' sert à déchiffrer le flag en fonction de la clé privée que l'on doit trouver.

Pour plus d'informations sur le système RSA, voir wikipedia : https://fr.wikipedia.org/wiki/Rivest_Shamir_Adleman


===== Détermination de la clé privée =====
La clé publique étant donnée (''john.pub''), et ayant donc **n** et **e**, il nous faut, tout d'abord, déterminer les deux facteurs premiers de **n** : **p** et **q**. Ici, **n** étant petit ( **n** < 2⁵¹) il est possible de déterminer **p** et **q** par un simple bruteforce.

Le programme suivant effectue un simple test de division de **n** par un nombre premier **p** et test si le résultat de cette division est un autre nombre premier **q** :
<code bash>
% ./refactor
Found ! p = 31834349 ; q = 48670331
PubKey  : 1549388302999519:101
PrivKey : 1549388302999519:d
Phi(1549388302999519) : 1549388222494840
</code>
On trouve donc **p** = 31834349 et **q** = 48670331.

Connaissant **p**, **q**, **n** et **e**, nous pouvons alors déterminer **d** via l'inverse modulaire de e mod φ(n). Pour garder un peu de lisibilité dans ce write up, nous utiliserons ici un module perl pré-existant pour déterminer **d** :
<code perl>
#!/usr/bin/perl
use strict;
use warnings;

use Crypt::OpenSSL::RSA;
use Crypt::OpenSSL::Bignum;
use Crypt::OpenSSL::Bignum::CTX;

my $n = Crypt::OpenSSL::Bignum->new_from_decimal("1549388302999519");

my $e = Crypt::OpenSSL::Bignum->new_from_decimal("101");

my $p = Crypt::OpenSSL::Bignum->new_from_decimal("31834349");

my $q = Crypt::OpenSSL::Bignum->new_from_decimal("48670331");

my $ctx = Crypt::OpenSSL::Bignum::CTX->new();
my $one = Crypt::OpenSSL::Bignum->one();
my $d = $e->mod_inverse($p->sub($one)->mul($q->sub($one), $ctx), $ctx);

print $d->to_decimal;
</code>
<code bash>
% perl decrypt.pl
1165876286233741
</code>

On peut alors lancer ''decrypt.py'' avec la clé privée trouvée :
     _________
   _|      ___|_
  |  ___  |   | |   HZV
  | |___| |___| |
  |_           _|	  challenge by benjamin
    |  _   _  |
    |_| |_| |_|     c9132f892055ea81fd91a9ed0e54a859