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 :
[pastacode provider=”manual” lang=”python”]
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[/pastacode]