{"id":328,"date":"2014-03-04T19:56:50","date_gmt":"2014-03-04T17:56:50","guid":{"rendered":"http:\/\/calypt.com\/blog\/?p=328"},"modified":"2014-03-05T16:32:41","modified_gmt":"2014-03-05T14:32:41","slug":"boston-key-party-2014-write-mind-ps-qs-crypto-100","status":"publish","type":"post","link":"https:\/\/www.calypt.com\/blog\/index.php\/boston-key-party-2014-write-mind-ps-qs-crypto-100\/","title":{"rendered":"Boston Key Party 2014 \u2013 Write-up Mind your P’s and Q’s! CRYPTO 100"},"content":{"rendered":"

\"Boston<\/p>\n

Fichiers de l’\u00e9preuve<\/strong> (fournis par Boston Key Party)<\/strong> : challenge-cd6d19866c42e274cd09604adaf4077b.tar<\/a><\/p>\n

Description<\/strong> : \u00ab The flag has been split into several files, and encrypted under RSA-OAEP. Can you break ALL of the ciphertexts, and reassemble the key \u00bb<\/p>\n

 <\/p>\n

On est face \u00e0 un challenge RSA classique<\/a>. Le titre nous met sur la piste de param\u00e8tres p<\/span> et q<\/span> mal choisis. \u00c9tant donn\u00e9 que l’archive est compos\u00e9e de 24 chiffr\u00e9s \/ clefs publiques associ\u00e9es, une bonne fa\u00e7on de mal choisir p<\/span> et q<\/span> serait d’utiliser plusieurs fois les m\u00eames. On s’aper\u00e7oit rapidement que c’est effectivement le cas : en faisant des gcd<\/a> sur les param\u00e8tres n<\/span> des clefs publiques, ont retrouve des p<\/span> communs.<\/p>\n

Pour r\u00e9soudre le challenge on construit donc la liste d[] des clefs priv\u00e9es puis on d\u00e9chiffre en utilisant la librairie pycrypto<\/a> et plus particuli\u00e8rement le module OAEP<\/a>. Sage 6.1.1<\/a> embarque pycrypto et on peut donc r\u00e9soudre le challenge avec le code suivant :<\/p>\n

[pastacode provider=”manual” lang=”python”]<\/p>\n

from Crypto.Cipher import PKCS1_OAEP\r\nfrom Crypto.PublicKey import RSA\r\n\r\npub_keys=[]; p=[]; q=[]; d=[]\r\n\r\n#I - import des clefs publiques\r\nfor i in xrange(24): \r\n    pub_keys.append(RSA.importKey(open('\/tmp\/challenge\/'+str(i)+'.key').read()))\r\n\r\n#II - calculs des d[] : l'exposant priv\u00e9\r\nfor i in xrange(24): \r\n    p.append(1)\r\n    tmp=0\r\n    while p[i]<2 or p[i]>=pub_keys[i].n: #recherche d'un p commun parmis les clefs pub\r\n        p[i]=gcd(pub_keys[i].n,pub_keys[tmp].n)\r\n        tmp=tmp+1\r\n    q.append(pub_keys[i].n\/p[i])\r\n    d.append(inverse_mod(pub_keys[i].e,(p[i]-1)*(q[i]-1)))\r\n\r\n#III - dechiffrement RSA OAEP\r\nflag=''\r\nfor i in xrange(24):\r\n    key = RSA.construct((long(pub_keys[i].n),long(pub_keys[i].e),long(d[i])))\r\n    cipher = PKCS1_OAEP.new(key)\r\n    flag+=cipher.decrypt(open(\"\/tmp\/challenge\/\"+str(i)+\".enc\").read())\r\nprint flag<\/code><\/pre>\n
[\/pastacode]<\/p>\n","protected":false},"excerpt":{"rendered":"
Fichiers de l’\u00e9preuve (fournis par Boston Key Party) : challenge-cd6d19866c42e274cd09604adaf4077b.tar Description : \u00ab The flag has been split into several files, and encrypted under RSA-OAEP. Can you break ALL of the ciphertexts, and reassemble the key \u00bb   On est face \u00e0 un challenge RSA classique. Le titre nous met sur la piste de param\u00e8tres […]<\/p>\n","protected":false},"author":4,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"_mi_skip_tracking":false},"categories":[53,17,23,40,39],"tags":[57,48,45],"yoast_head":"\n\n\n\n\n\n\n\n\n\n\n\n\n\t\n