picoCTF 2017 – ciekawe zadania – LEVEL 2 Weird RSA

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:

Dodaj komentarz

Twój adres email nie zostanie opublikowany. Pola, których wypełnienie jest wymagane, są oznaczone symbolem *