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密文
收藏了