Kolejne ciekawe zadanie z PicoCTF 2017, tym razem szyfrowanie RSA ale nie normalne a "dziwne RSA"...
Treść zagadki:
We recovered some data. It was labeled as RSA, but what in the world are "dq" and "dp"? Can you decrypt the ciphertext for us?
Zawartość pliku data:
c: 95272795986475189505518980251137003509292621140166383887854853863720692420204142448424074834657149326853553097626486371206617513769930277580823116437975487148956107509247564965652417450550680181691869432067892028368985007229633943149091684419834136214793476910417359537696632874045272326665036717324623992885 p: 11387480584909854985125335848240384226653929942757756384489381242206157197986555243995335158328781970310603060671486688856263776452654268043936036556215243 q: 12972222875218086547425818961477257915105515705982283726851833508079600460542479267972050216838604649742870515200462359007315431848784163790312424462439629 dp: 8191957726161111880866028229950166742224147653136894248088678244548815086744810656765529876284622829884409590596114090872889522887052772791407131880103961 dq: 3570695757580148093370242608506191464756425954703930236924583065811730548932270595568088372441809535917032142349986828862994856575730078580414026791444659
Szybki rekonesans mówi nam że mamy do czynienia z RSA-CRT czy specjalnej odmianie RSA która korzysta z Chińskiego twierdzenia o resztach (Chinese Remainder Theorem).
Odmiana ta pozwala łatwiej deszyfrować cipher text dzięki zastosowaniu dodatkowych parametrów dp i dq. Nie ma tutaj żadnego haczyka, wystarczy wygenerować klucz prywatny przy pomocy podanych parametrów i odszyfrować flagę.
Największym problemem jest brak narzędzia które szybko załatwi sprawę 🙂 Poniżej umieszczam skrypt python który napisałem do rozwiązania tego problemu. Być może komuś się przyda.
# PicoCTF 2017 "Weird RSA" # RSA decryption using the Chinese Remainder Theorem import gmpy2 from Crypto.Util.number import long_to_bytes c = 95272795986475189505518980251137003509292621140166383887854853863720692420204142448424074834657149326853553097626486371206617513769930277580823116437975487148956107509247564965652417450550680181691869432067892028368985007229633943149091684419834136214793476910417359537696632874045272326665036717324623992885 p = 11387480584909854985125335848240384226653929942757756384489381242206157197986555243995335158328781970310603060671486688856263776452654268043936036556215243 q = 12972222875218086547425818961477257915105515705982283726851833508079600460542479267972050216838604649742870515200462359007315431848784163790312424462439629 dp = 8191957726161111880866028229950166742224147653136894248088678244548815086744810656765529876284622829884409590596114090872889522887052772791407131880103961 dq = 3570695757580148093370242608506191464756425954703930236924583065811730548932270595568088372441809535917032142349986828862994856575730078580414026791444659 qinv = gmpy2.invert(q, p) def decrypt(c): m1 = pow(c, dp, p) m2 = pow(c, dq, q) h = (qinv * (m1 - m2)) % p m = m2 + h * q return long_to_bytes(m) print decrypt(c)
Aby skrypt działał musimy zainstalować gmpy2:
sudo apt-get install python-gmpy2
Makulatura: