چالش RSA-GCD¶

صورت سوال¶

یک اسکرپیت پایتون به همراه یک فایل متنی به عنوان خروجی داده شده:

chall1.py
import math
from Crypto.Util.number import *
from secret import flag,p,q
from gmpy2 import next_prime
m = bytes_to_long(flag.encode())
n=p*q


power1=getPrime(128)
power2=getPrime(128)
out1=pow((p+5*q),power1,n)
out2=pow((2*p-3*q),power2,n)
eq1 = next_prime(out1)

c = pow(m,eq1,n)


with open('chall2.txt', 'w') as f:
    f.write(f"power1={power1}\npower2={power2}\neq1={eq1}\nout2={out2}\nc={c}\nn={n}")

chall2.txt
power1=281633240040397659252345654576211057861
power2=176308336928924352184372543940536917109
hint=411
eq1=2215046782468309450936082777612424211412337114444319825829990136530150023421973276679233466961721799435832008176351257758211795258104410574651506816371525399470106295329892650116954910145110061394115128594706653901546850341101164907898346828022518433436756708015867100484886064022613201281974922516001003812543875124931017296069171534425347946706516721158931976668856772032986107756096884279339277577522744896393586820406756687660577611656150151320563864609280700993052969723348256651525099282363827609407754245152456057637748180188320357373038585979521690892103252278817084504770389439547939576161027195745675950581
out2=224716457567805571457452109314840584938194777933567695025383598737742953385932774494061722186466488058963292298731548262946252467708201178039920036687466838646578780171659412046424661511424885847858605733166167243266967519888832320006319574592040964724166606818031851868781293898640006645588451478651078888573257764059329308290191330600751437003945959195015039080555651110109402824088914942521092411739845889504681057496784722485112900862556479793984461508688747584333779913379205326096741063817431486115062002833764884691478125957020515087151797715139500054071639511693796733701302441791646733348130465995741750305
c=11590329449898382355259097288126297723330518724423158499663195432429148659629360772046004567610391586374248766268949395442626129829280485822846914892742999919200424494797999357420039284200041554727864577173539470903740570358887403929574729181050580051531054419822604967970652657582680503568450858145445133903843997167785099694035636639751563864456765279184903793606195210085887908261552418052046078949269345060242959548584449958223195825915868527413527818920779142424249900048576415289642381588131825356703220549540141172856377628272697983038659289548768939062762166728868090528927622873912001462022092096509127650036
n=14478207897963700838626231927254146456438092099321018357600633229947985294943471593095346392445363289100367665921624202726871181236619222731528254291046753377214521099844204178495251951493800962582981218384073953742392905995080971992691440003270383672514914405392107063745075388073134658615835329573872949946915357348899005066190003231102036536377065461296855755685790186655198033248021908662540544378202344400991059576331593290430353385561730605371820149402732270319368867098328023646016284500105286746932167888156663308664771634423721001257809156324013490651392177956201509967182496047787358208600006325742127976151

برای کسانی که قبلا چالش های CryptoHack رو انجام دادن، ممکنه متوجه بشید که این چالش بسیار شبیه به یک چالش CryptoHack هست، توی بخش ریاضیات و چلنج Modular Binomials. خب ما بلافاصله متوجه این موضوع شدیم و به CryptoHack.org رفتیم و دوباره چلنج رو مطالعه و حل کردیم. توجه داشته باشید که تا زمانی که مسئله رو حل نکرده باشید، ممکنه راه حلی نداشته باشید. به هر حال من براتون راه حل رو با جزئیات توضیح میدم.

روش حل¶

در این چالش، معادلات زیر ارائه شده:

$out_1\equiv(p+5q)^{power_1}\pmod{n}$

$out_2\equiv(2p-3q)^{power_2}\pmod{n}$

که $p$ و $q$ اعداد اولی هستند که حاصلضرب اونا $n$ هست. ما البته باید اینها را پیدا کنیم تا رمزگذاری RSA ای را بشکنیم که متن رمزی آن $c$ است.

توجه کنید، با اینکه، out1 در فایل خروجی ما داده نشده! در عوض، eq1 به ما داده شده، که کوچکترین عدد اول بعد از out1 هست.

همچنین توجه داشته باشید یک متغیر hint توی فایل متنی بهمون داده شده ولی اگه دقت کنید توی هیج جا از اسکریپت پایتون استفاده نشده و در نتیجه کلا به درد ما نمیخوره.

ابتدا بیاین متغیرها را بازنویسی کنیم تا خوندنش کمی آسون تر بشه.

$o_1\equiv(p+5q)^{p_1}\pmod{n}$

$o_2\equiv(2p-3q)^{p_2}\pmod{n}$

حال بیاین معادلات خودمون رو هر یک را به توان دیگری برسونیم، یعنی:

$o_1^{p_2}\equiv(p+5q)^{p_1p_2}\pmod{n}$

$o_2^{p_1}\equiv(2p-3q)^{p_2p_1}\pmod{n}$

به دلیل Binomial Theorem، می دانیم که میتونیم صورت زیر ساده کنیم:

$o_1^{p_2}\equiv(p)^{p_1p_2} + (5q)^{p_1p_2}\pmod{n}$

$o_2^{p_1}\equiv(2p)^{p_2p_1} + (-3q)^{p_1p_2}\pmod{n}$

با توجه به اینکه سایر عبارت ها دارای یک $pq$ برابر $n$ هستند.

حال بیاین هر دو معادله به صورت $(mod; q)$ در نظر بگیریم. با این کار، $q$ ها در معادلات ما وجود ندارند و نتیجه به این صورت میشه:

$o_1^{p_2}\equiv(p)^{p_1p_2}\pmod{q}$

$o_2^{p_1}\equiv(2p)^{p_2p_1}\pmod{q}$

حالا اگه معادله اول رو در $(2)^{p_1p_2}$ ضرب کنیم میشه:

$o_1^{p_2} \cdot 2^{p_1p_2} \equiv(p)^{p_1p_2} \cdot 2^{p_1p_2}\pmod{q}$

$o_2^{p_1}\equiv(2p)^{p_2p_1}\pmod{q}$

بنابراین داریم:

$o_1^{p_2} \cdot 2^{p_1p_2} =(2p)^{p_1p_2}\pmod{q}$

$o_2^{p_1}\equiv(2p)^{p_2p_1} + k_2q$

با توجه به تعریف حساب پیمانه ای یا (Modular Arithmetic) میتونیم بنویسیم:

$o_1^{p_2} \cdot 2^{p_1p_2} =(2p)^{p_1p_2} + k_1q$

$o_2^{p_1}\equiv(2p)^{p_2p_1} + k_2q$

معادله دوم رو از اولی کم میکنیم و بنابراین:

$x = o_1^{p_2} \cdot 2^{p_1p_2} - o_2^{p_1} = (2p)^{p_1p_2} + k_1q - ((2p)^{p_2p_1} + k_2q)\equiv(k_1 - k_2)q$

خب حالا عددی تولید کرده ایم که مضرب $q$ هست. بنابراین $gcd(x, n)$ , ‍‍ $q$ را برمی گرداند.

حالا اگه مقدار ‍‍out_1 میدونستیم کار تموم بود. اما متاسفانه نمیدونیم. ما فقط کوچکترین عدد اول بزرگتر از اون رو میدونیم که eq1 هست. پس چجوری می تونیم این کار را انجام بدیم؟

برای پیدا کردن out_1 میایم تمامی اعداد متوالی کمتر از ‍eq1 بررسی میکنیم تا به اولین عدد اول برسیم و در واقع اون out_1 هست.

find_out1.py
x1 = pow(2, power1*power2, n)
x2 = pow(out2, power1, n)

for i in range(10000):
    diff = abs(pow(eq1, power2, n)*x1 - x2)
    q = gcd(diff, n)
    if q > 1:
        break
    eq1 -= 1
    if is_prime(eq1):
        break

خب الان $q$ رو داریم، به سادگی رویه استاندارد RSA رو جلو میریم و فلگ رو بدست بیاریم:

solve.py
from gmpy2 import next_prime, gcd, is_prime
from Crypto.Util.number import *

power1=281633240040397659252345654576211057861
power2=176308336928924352184372543940536917109
hint=411
eq1=2215046782468309450936082777612424211412337114444319825829990136530150023421973276679233466961721799435832008176351257758211795258104410574651506816371525399470106295329892650116954910145110061394115128594706653901546850341101164907898346828022518433436756708015867100484886064022613201281974922516001003812543875124931017296069171534425347946706516721158931976668856772032986107756096884279339277577522744896393586820406756687660577611656150151320563864609280700993052969723348256651525099282363827609407754245152456057637748180188320357373038585979521690892103252278817084504770389439547939576161027195745675950581
out2=224716457567805571457452109314840584938194777933567695025383598737742953385932774494061722186466488058963292298731548262946252467708201178039920036687466838646578780171659412046424661511424885847858605733166167243266967519888832320006319574592040964724166606818031851868781293898640006645588451478651078888573257764059329308290191330600751437003945959195015039080555651110109402824088914942521092411739845889504681057496784722485112900862556479793984461508688747584333779913379205326096741063817431486115062002833764884691478125957020515087151797715139500054071639511693796733701302441791646733348130465995741750305
c=11590329449898382355259097288126297723330518724423158499663195432429148659629360772046004567610391586374248766268949395442626129829280485822846914892742999919200424494797999357420039284200041554727864577173539470903740570358887403929574729181050580051531054419822604967970652657582680503568450858145445133903843997167785099694035636639751563864456765279184903793606195210085887908261552418052046078949269345060242959548584449958223195825915868527413527818920779142424249900048576415289642381588131825356703220549540141172856377628272697983038659289548768939062762166728868090528927622873912001462022092096509127650036
n=14478207897963700838626231927254146456438092099321018357600633229947985294943471593095346392445363289100367665921624202726871181236619222731528254291046753377214521099844204178495251951493800962582981218384073953742392905995080971992691440003270383672514914405392107063745075388073134658615835329573872949946915357348899005066190003231102036536377065461296855755685790186655198033248021908662540544378202344400991059576331593290430353385561730605371820149402732270319368867098328023646016284500105286746932167888156663308664771634423721001257809156324013490651392177956201509967182496047787358208600006325742127976151
e = eq1

x1 = pow(2, power1*power2, n)
x2 = pow(out2, power1, n)
for i in range(10000):
    diff = abs(pow(eq1, power2, n)*x1 - x2)
    q = gcd(diff, n)
    if q > 1:
        break
    eq1 -= 1
    if is_prime(eq1):
        break

p = n//q
phi = (p - 1)*(q - 1)
d = inverse(e, n)
print(long_to_bytes(pow(c, d, n)))

FLAG

0xL4ugh{you_know_how_factor_N!}

نویسنده

MohamadAli