Boston Key Party 2014 – Write-up Mind your P’s and Q’s! CRYPTO 100

Published on: Mar 04 2014 by Loïc

Boston Key Party

Fichiers de l’épreuve (fournis par Boston Key Party) : challenge-cd6d19866c42e274cd09604adaf4077b.tar

Description : « The flag has been split into several files, and encrypted under RSA-OAEP. Can you break ALL of the ciphertexts, and reassemble the key »

 

On est face à un challenge RSA classique. Le titre nous met sur la piste de paramètres p et q mal choisis. Étant donné que l’archive est composée de 24 chiffrés / clefs publiques associées, une bonne façon de mal choisir p et q serait d’utiliser plusieurs fois les mêmes. On s’aperçoit rapidement que c’est effectivement le cas : en faisant des gcd sur les paramètres n des clefs publiques, ont retrouve des p communs.

Pour résoudre le challenge on construit donc la liste d[] des clefs privées puis on déchiffre en utilisant la librairie pycrypto et plus particulièrement le module OAEP. Sage 6.1.1 embarque pycrypto et on peut donc résoudre le challenge avec le code suivant :

from Crypto.Cipher import PKCS1_OAEP
from Crypto.PublicKey import RSA

pub_keys=[]; p=[]; q=[]; d=[]

#I - import des clefs publiques
for i in xrange(24): 
    pub_keys.append(RSA.importKey(open('/tmp/challenge/'+str(i)+'.key').read()))

#II - calculs des d[] : l'exposant privé
for i in xrange(24): 
    p.append(1)
    tmp=0
    while p[i]<2 or p[i]>=pub_keys[i].n: #recherche d'un p commun parmis les clefs pub
        p[i]=gcd(pub_keys[i].n,pub_keys[tmp].n)
        tmp=tmp+1
    q.append(pub_keys[i].n/p[i])
    d.append(inverse_mod(pub_keys[i].e,(p[i]-1)*(q[i]-1)))

#III - dechiffrement RSA OAEP
flag=''
for i in xrange(24):
    key = RSA.construct((long(pub_keys[i].n),long(pub_keys[i].e),long(d[i])))
    cipher = PKCS1_OAEP.new(key)
    flag+=cipher.decrypt(open("/tmp/challenge/"+str(i)+".enc").read())
print flag
Filed under: Boston Key Party, Challenge Crypto, Crypto, RSA, Sage
Tags: , ,

Leave a Reply

*

*