Voici un petit write-up pour le challenge "RSA" du ASIS CTF (prequals 2016).

$ ls
flag.enc  pubkey.pem  rsa.py

On a donc un flag en base64 chiffré avec RSA, une clef publique, et le script Python qui a été utilisé pour chiffrer le flag. Le but est bien évidemment de déchiffrer le flag.

La clef publique :

$ openssl rsa -pubin -text -noout < pubkey.pem
Public-Key: (256 bit)
Modulus:
    00:d8:e2:4c:12:b7:b9:9e:fe:0a:9b:c0:4a:6a:3d:
    f5:8a:2a:94:42:69:b4:92:b7:37:6d:f1:29:02:3f:
    20:61:b9
Exponent: 12405943493775545863 (0xac2ac3e0ca0f5607)

On voit que le modulus est très petit (256 bits), on peut donc le factoriser sans aucuns problèmes et retrouver l'exposant privé d.

Récupération du modulus et de l'exposant public :

$ openssl asn1parse  < pubkey.pem
    0:d=0  hl=2 l=  66 cons: SEQUENCE
    2:d=1  hl=2 l=  13 cons: SEQUENCE
    4:d=2  hl=2 l=   9 prim: OBJECT            :rsaEncryption
   15:d=2  hl=2 l=   0 prim: NULL
   17:d=1  hl=2 l=  49 prim: BIT STRING

$ openssl asn1parse  -strparse 17 < pubkey.pem
    0:d=0  hl=2 l=  46 cons: SEQUENCE
    2:d=1  hl=2 l=  33 prim: INTEGER
        :D8E24C12B7B99EFE0A9BC04A6A3DF58A2A944269B492B7376DF129023F2061B9

   37:d=1  hl=2 l=   9 prim: INTEGER
        :AC2AC3E0CA0F5607

Pour la factorisation du modulus, j'ai utilisé factordb.com, on trouve alors :

p = 311155972145869391293781528370734636009
q = 315274063651866931016337573625089033553
e = 12405943493775545863

Le flag à chiffrer étant assez grand (il est en fait concaténé 30 fois), un modulus de 256 bits n'est pas suffisant pour le chiffrer avec la norme PKCSv1.5.

Le script effectue alors une boucle pour augmenter la taille du modulus et de l'exposant public à partir des valeurs de départ, jusqu'à que le chiffrement devienne possible.

Voici le script Python qui génère une clef publique, et chiffre le flag :

#!/usr/bin/python

import gmpy
from Crypto.Util.number import *
from Crypto.PublicKey import RSA
from Crypto.Cipher import PKCS1_v1_5

flag = open('flag', 'r').read() * 30

def ext_rsa_encrypt(p, q, e, msg):
    m = bytes_to_long(msg)
    while True:
        n = p * q
        try:
            phi = (p - 1)*(q - 1)
            d = gmpy.invert(e, phi)
            pubkey = RSA.construct((long(n), long(e)))
            key = PKCS1_v1_5.new(pubkey)
            enc = key.encrypt(msg).encode('base64')
            return enc
        except:
            p = gmpy.next_prime(p**2 + q**2)
            q = gmpy.next_prime(2*p*q)
            e = gmpy.next_prime(e**2)

p = getPrime(128)
q = getPrime(128)
n = p*q
e = getPrime(64)
pubkey = RSA.construct((long(n), long(e)))
f = open('pubkey.pem', 'w')
f.write(pubkey.exportKey())
g = open('flag.enc', 'w')
g.write(ext_rsa_encrypt(p, q, e, flag))

Pour le déchiffrement, nous avons juste à effectuer la même boucle, en essayant de déchiffrer à chaque itération.

Voici le script permettant de déchiffrer le flag :

#!/usr/bin/python

from gmpy2 import *
from Crypto.Util.number import *
from Crypto.PublicKey import RSA
from Crypto.Cipher import PKCS1_v1_5

flag = open('flag.enc', 'r').read().decode("base64")

def ext_rsa_encrypt(p, q, e, msg):

    while True:
        n = p * q
        print "n = ", n
        try:
            phi = mul(mpz(p-1), (q-1))
            d = invert(e, phi)
            key = RSA.construct((long(n), long(e), long(d)))
            cipher = PKCS1_v1_5.new(key)
            enc = cipher.decrypt(msg, None)
            return enc
        except:
            p = next_prime(mul(mpz(p),mpz(p)) + mul(mpz(q),mpz(q)))
            q = next_prime(2*mul(mpz(p),mpz(q)))
            e = next_prime(e**2)

p = 311155972145869391293781528370734636009
q = 315274063651866931016337573625089033553
e = 12405943493775545863

print(ext_rsa_encrypt(p, q, e, flag))

Après un petit moment (les multiplications sont assez coûteuses en temps lorsque le modulus devient important), on obtient le flag :

ASIS{F4ct0R__N_by_it3rat!ng!}