Skynet is using a very small list of primes for RSA style encryption purposes. In fact their list is only the size of the smallest odd prime. One of the robots sent a message to three other robots. These are futuristic robots with the ability to use quantum computing and so they don’t mind prime factoring huge numbers.You can’t do that though. Find out what message the robot sent to his friends. Flag is in flag{} format. https://mega.nz/#!7WZg2I5I!UiyBukv8_IjartojnY86nhN5jsQFKE4tPCEF1lPqsQ8
廢話一大堆 概括: 破解RSA
e: 65537
c1: 5024836662627906750454817701922271080214720765897113783786369197810770999608528443597447448508876214100063962982376037712548944474807897847869334582773452689962992522987755069402952836848501053684233233850594080254869
n1: 10603199174122839808738169357706062732533966731323858892743816728206914395320609331466257631096646511986506501272036007668358071304364156150345138983648630874220488837685118753574424686204595981514561343227316297317899
c2: 130884437483098301339042672379318680582507704056215246672305503902799253294397268030727540524911640778691710963573363763216872030631281953772411963153320471648783848323158455504315739311667392161460121273259241311534
n2: 5613358668671613665566510382994441407219432062998832523305840186970780370368271618683122274081615792349154210168307159475914213081021759597948038689876676892007399580995868266543309872185843728429426430822156211839073
c3: 40136988332296795741662524458025734893351353026652568277369126873536130787573840288544348201399567767278683800132245661707440297299339161485942455489387697524794283615358478900857853907316854396647838513117062760230880
n3: 43197226819995414250880489055413585390503681019180594772781599842207471693041753129885439403306011423063922105541557658194092177558145184151460920732675652134876335722840331008185551706229533179802997366680787866083523
讓人聯想到了廣播攻擊, 但是實際并不是, 因為低加密指數廣播攻擊需要e個相同明文的不同密文, 但是這裡e = 0x10001比較大, 而密文僅3條, 是以不能廣播攻擊, 考慮基本思路, 分解大數, 發現第一個數在factordb裡有解, emm然後就解就行了…
直接上腳本(引用某位大佬的腳本)
e = 65537
c1 = 5024836662627906750454817701922271080214720765897113783786369197810770999608528443597447448508876214100063962982376037712548944474807897847869334582773452689962992522987755069402952836848501053684233233850594080254869
n1 = 10603199174122839808738169357706062732533966731323858892743816728206914395320609331466257631096646511986506501272036007668358071304364156150345138983648630874220488837685118753574424686204595981514561343227316297317899
c2 = 130884437483098301339042672379318680582507704056215246672305503902799253294397268030727540524911640778691710963573363763216872030631281953772411963153320471648783848323158455504315739311667392161460121273259241311534
n2 = 5613358668671613665566510382994441407219432062998832523305840186970780370368271618683122274081615792349154210168307159475914213081021759597948038689876676892007399580995868266543309872185843728429426430822156211839073
c3 = 40136988332296795741662524458025734893351353026652568277369126873536130787573840288544348201399567767278683800132245661707440297299339161485942455489387697524794283615358478900857853907316854396647838513117062760230880
n3 = 43197226819995414250880489055413585390503681019180594772781599842207471693041753129885439403306011423063922105541557658194092177558145184151460920732675652134876335722840331008185551706229533179802997366680787866083523
#use factordb
p1 = 1173821128899717744763168991586024137475923012574062580049287532012184965219319828285650431646942194944437493
q1 = 9033062119150775356115605417902072538098631081058159551678022048966520848600866260935959311606867286026034943
p2 = 0
q2 = 0
p3 = 0
q3 = 0
def egcd(a, b):
if a == 0:
return (b, 0, 1)
else:
g, y, x = egcd(b % a, a)
return (g, x - (b // a) * y, y)
def modinv(a, m):
g, x, y = egcd(a, m)
if g != 1:
raise Exception('modular inverse does not exist')
else:
return x % m
# ed mod phi = 1 M^e mod n = c M = c^d mod n
phi = (q1-1)*(p1-1) # 245841236512478852752909734911568644502940792175517415934560
d=modinv(e,phi)
m=pow(c1,d,n1) # M = c^d mod n
f=bytes.fromhex(hex(m)[2:])
print("[+] Message 1 is : ",f)
得到flag
flag{will_he_be_back}
總結
def egcd(a, b):
if a == 0:
return (b, 0, 1)
else:
g, y, x = egcd(b % a, a)
return (g, x - (b // a) * y, y)
def modinv(a, m):
g, x, y = egcd(a, m)
if g != 1:
raise Exception('modular inverse does not exist')
else:
return x % m
# ed mod phi = 1 M^e mod n = c M = c^d mod n
phi = (q1-1)*(p1-1)
d=modinv(e,phi)
m=pow(c1,d,n1) # M = c^d mod n
f=bytes.fromhex(hex(m)[2:])
print(f)
這段腳本已經很凝練了, 可用于解已知p,q的RSA密文
收藏了