RSA

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 :

% 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)

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

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 :

% ./refactor
Found ! p = 31834349 ; q = 48670331
PubKey  : 1549388302999519:101
PrivKey : 1549388302999519:d
Phi(1549388302999519) : 1549388222494840

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 :

#!/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;

% perl decrypt.pl
1165876286233741

On peut alors lancer decrypt.py avec la clé privée trouvée :

   _________
 _|      ___|_
|  ___  |   | |   HZV
| |___| |___| |
|_           _|	  challenge by benjamin
  |  _   _  |
  |_| |_| |_|     c9132f892055ea81fd91a9ed0e54a859