picoCTF - Crack The Power

W tym poście chciałbym opisać rozwiązanie zadania Crack The Power z działu Cryptography PicoCTF.

Do zadania został dołączony plik tekstowy z następującymi danymi:

Jest to RSA do którego podano wartości modułu RSA (n), wykładnika szyfrowania (e), szyfrogram (c).

W RSA liczby n oraz e tworzą klucz publiczny. c natomiast jest szyfrogramem, czyli wynikiem potęgowania wiadomości m.

Na samym początku myślimy o rozkładzie modułu n na czynniki pierwsze (jak w zadaniu EVEN RSA CAN BE BROKEN???) 

Okazuje się jednak, że liczba ma 1233 cyfry i nie da się jej rozłożyć w taki sposób. W związku z tym, że n jest dużą liczbą odpada sprawdzenie wartości p i q. To ma zastosowanie tylko do małych liczb. 

Natomiast w przypadku tego zadania faktoryzacja nie jest potrzebna. Podatność jaką wykorzystano w tym zadaniu wynika z błędnego użycia RSA, a nie ze słabości samego modułu. 

Prześledźmy dokładnie dane. Widzimy, że wykładnik e wynosi 20. W poprawnie zaimplementowanym RSA stosuje się padding, który powoduje, że wiadomość m ma zbliżony rozmiar do n. Bez niego mamy do czynienia z błędną implementacją RSA, co pozwala na przeprowadzenie prostego ataku. 

Teraz należy sprawdzić czy szyfrogram c jest mniejszy od modułu n. Widać to po ilości cyfr w ciągu. Więc w tym przypadku jest mniejszy. 

Teraz musimy zweryfikować czy c jest idealną potęgą 20-tego stopnia. Jeżeli c okaże się idealną potęgą 20-tego stopnia to oznacza, że podczas szyfrowania nie doszło do redukcji modulo n. Więc c = m^20. Pozwoli to na odzyskanie m przez obliczenie pierwiastka 20 stopnia. 

Należy zastosować binarne wyszukiwanie ponieważ liczby są bardzo duże. 

1. n = 386950223174327627276259046842865988384331307082298626492414147713197384686718059841674125485405247260012399384424232709643530096669677437000034401943419385490488047272573960229102125709392697217719912631789891176738864998957072778346491398319550264009992376396144732371747950536839287549051176828472873913845491648586191659090301020071582176144802639116366604814431874438820848398156275910294260646510475127661906467599774663656840953753976729461641813728777109965812274665573167454085169592582398083739363414621343920952878195803602810225656852269443119499642385380938060732892078572342300548430884334998686712600767344217002681759770383758623691412606776602855010801507680073286786620729930330168256015382446870100169251675993379646046602620375491151885142873833739378178866064763953962955471745775803504165698866034972684683499370387499194686636975689903142734276807777740264534454698386643039992393253473686408362598109793124370038621792324931198792738010528655803974783201812330654773944984424099414929410873259965054431824762145800626429907914499803707695912398364507287735319527317313406675641429766214642836037780048691586005273694836905600475643858215734460794518718962736436266178246129912334912120471048779522082472197479
2. e = 20
3. c = 640637430810406857500566702096274080295167731635479640274760705704329834745477874965672179442241380279649152291050969332091830976943198847734415977548283171453481035282640484509583761270819296888257025423610485662327686746807124249949801573622622025474105445411840040848707900538974836502204083674934003917014859170779890252120520936707231672530138550675052950661474192855295453830397195247783998452664323732349420008517294161050124199670265314439879598381647127314712772548808612160779354709720895650121981177223490008248201450405152764628551694278264566165847529527374683997923166335487870492633337964403006300189760469566049124557315678595808047255318170512104170886552702569378959458824295010481695843284719354153292787385820974271650396981741339320687983380628305498834020090930469888563923010239874356737632339575780299779123268795656555862306591438587341766174657770814212432221156762042052091807416027774410855528501728964161702794878631542708859539338820717896541175233336294156172568901530237626544862910267079985279152762092723288118416875741016667540126137577917228529419644972932304443300913541487225113046155490500715183529932578432401
4.  
5. # Binarne wyszukiwanie
6. def integer_nth_root(k: int, n: int) -> tuple[int, bool]:
7.     if k < 0:
8.         raise ValueError("k musi być >= 0")
9.     if n <= 0:
10.         raise ValueError("n musi być > 0")
11.     if k in (0, 1):
12.         return k, True
13.        
14.     hi = 1 << ((k.bit_length() + n - 1) // n)
15.     lo = 0
16.  
17.     while lo + 1 < hi:
18.         mid = (lo + hi) // 2
19.         p = mid ** n
20.         if p == k:
21.             return mid, True
22.         elif p < k:
23.             lo = mid
24.         else:
25.             hi = mid
26.  
27.     return lo, (lo ** n == k)
28.  
29. m, exact = integer_nth_root(c, e)
30. print("C idealna potęga 20 stopnia - ", exact)
31. print("Czy m^e == c?", (m ** e == c))
32. print("m^e < n - ", (m ** e < n))
33. print("m =", m)

Wynik działania:

1. C idealna potęga 20 stopnia -  True
2. Czy m^e == c? True
3. m^e < n -  True
4. m = 2756326214127165272055984685514956804684656899272666658429

Wynik należy jeszcze zamienić na HEX a następnie na ASCII:

1. m = 2756326214127165272055984685514956804684656899272666658429
2.  
3. hex_m = hex(m)[2:]
4. print(hex_m)
5.  
6. msg_bytes = bytes.fromhex(hex_m)
7. print(msg_bytes.decode("ascii"))

Po uruchomieniu dostajemy szukaną flagę:

1. 7069636f4354467b74316e795f655f38333764373232367d
2. picoCTF{t1ny_e_837d7226}

Jak widać w przedstawionym zadaniu RSA może być matematycznie bezpieczne, a mimo to całkowicie podatne na atak. Jeśli zostanie zaimplementowane bez paddingu i z niewłaściwymi parametrami.