CnHongKe-Eswlnk Blog
智能摘要 AI
该文章描述了一次网络安全竞赛中的解题过程。题目涉及RSA加密，提供了一个RSA公钥`e=65537`和密文`c`，以及五轮生成的随机数`x`和`y`，用于干扰解密过程。解题者通过计算每轮生成的`x*p+m%p`和`y*p+m%q`的差值，提取出`p`和`q`的倍数，并利用这些倍数计算出`p`和`q`的真实值。最终利用`p`和`q`解密得到flag。尽管题目设计中包含一些不合理之处（如密码题过少），但整体上，解题者成功破解了挑战并获取了flag。

就三个小时，没有逆向没有pwn题，密码题还只有一道，当然有两道安卓，但是被队友做了。
sim卡号和硬件号我无语了，出题人有失水准。

CnHongKe-Eswlnk Blog

RSAbumber

enc.py:

#!/usr/bin/python
# encoding=utf-8
import random
from libnum import n2s, s2n
from Crypto.Util.number import getPrime

# 此flag并非最终flag x代表被隐藏的数据
flag = 'CnHongKe{xxxxxxxx}'

m = s2n(flag)
p = getPrime(1024)
q = getPrime(1024)
n = p * q
e = 65537
c = pow(m, e, n)
print ('n = ' + str(n))
print ('e = ' + str(e))
print ('c = ' + str(c))
for i in range(5):
    print ('Round ' + str(i) + ':')
    x = random.randint(1, 0xdeadbeef)
    y = random.randint(1, 0xc0ffee**2)
    print (x * p + m % p)
    print (y * p + m % q)

output:

n = 18230475022241107111502009638144846326462697444793977522162755140392028775630333139671570413968300055609624732905017576492318481049765719395178101917259078950491478404619212930712962176370474793458264542428174411648984385496415515888450236492639103655837968758912001127881298014373833492044054447538368777351959472828103490523519402499794625509544746224849131358391427803274660727365008334321515127913963267671553671133511956626749027063348684700062145214335868463058803066936646958127471845539276593962708044406490592998414273667232017530502712947165832917826753479338315450193449553506830399223036433213690635128087
e = 65537
c = 15001175319610946795222343924035487534008584709461878226143899906448843850120779928420944432465029785752971033689199065870408351794155945446686524700533470562991172384667710059451805009008305424805670596038911747645784329532786626324397778412957726495683422766522190746132188570946996332382787096032520348015914534837388916434188111744452280796833969638220556402855250673116813135921244590931278405785233581054716410417094016443403162280210104793301955569199264527668487539968506401974401995182691110545367915121198605642021603473376124400893881587208659717458033485422058304753162014771566156332810928502706804188737
Round 0:
47412728457745107106229027875259915648117103420044851871432992390178293593742914249866218522299698221781523771204375698745834487768864026409236512650009369501262196610608810334550791704365598969347066570672288841970107828704284424948297545299783041893922010965750083395574150504265229076349930292160436806574389307547
7151707571018794760876945899933828229145285573863576752865419158057935066014037290005780895245867810865116180154261908773240188847332693040946388709971429510641144658284756647717343337707189427886779134548103093596247917788448752584977147282207642265848763954965527098894273648060044295529160371099547280549240966801721056
Round 1:
86373908688190255108650922007330281242126635289292162039632402486539085755381492920050696186734107745876867540145298584182833089866456957702579079961268274186732194322193257970543632758510745323419171622735686426403527865980864189590088362168524820089760626009455736356904303430576008409321011228550702593460370154288
2739935163495322226296432842224432219815216025857635076958538964367641637837049807921996841802564467860170020056367256733719298729708060408741418149594763338760354925458404370138268461462191203576226734193278121792897686765638999384542960842700219908698775641786917353762507804532914821917178625996615671681334548749254429
Round 2:
15687554054832614360988742146490243595902020103032206429227782729844721078982137095466551882269747779142430460253454282190038058781992815802422733978085083098933991490277861599932099266191780563533577946414010597217513036108133130299260634025149883253291282013012600129526038544341494928677039830828249693520289847945
6435898081098312069193282341795915540261240598097490572271117490404376893304608004242439429312067951872804606757594603664301726541469229980157872229889782597976018733187194019143564854886058611915569783145503336546231380867908138879395210171706016651896401473392042420379329349589828280175940543607255416772431728188653211
Round 3:
124406465365494593150435052733515823072823170460491296026120656362244377437798061499623437952508101280479833325781339254475807502914410747844180618686595086868560892928752822875608133056170303090816121179406750530664088842659591750077533970086596825128053222046148639796312807976724883488231077768029334573827303301330
2613152126801235357605926409607555343634108914027445071424442563126602477314913418861534894059503269620876330215953120889484754924193784240242501571144710581424329983597503905140732556630904193447578828203223856219775397959234902308004140088085501789332051140882380419734289335488635960244365807950078568282028343410707589
Round 4:
284949676165523240398401316748486080499904237489742012461482352950411406038750742409921658105207491249100429933355996423446487597220482804381100033750232429224198596468209169113267880573088869328903032280568067097643797391791880140954369321732726087613395297706606074309398400985128432414291795513937986079041427040899
122752138534817317154139913828763607868537178753889435773820061347875458481657673655777638644954724226442684466601221000123146328227519319228427585553483003026793833527

wp脚本：

from Crypto.Util.number import *
from gmpy2 import *
from libnum import n2s, s2n

n = 18230475022241107111502009638144846326462697444793977522162755140392028775630333139671570413968300055609624732905017576492318481049765719395178101917259078950491478404619212930712962176370474793458264542428174411648984385496415515888450236492639103655837968758912001127881298014373833492044054447538368777351959472828103490523519402499794625509544746224849131358391427803274660727365008334321515127913963267671553671133511956626749027063348684700062145214335868463058803066936646958127471845539276593962708044406490592998414273667232017530502712947165832917826753479338315450193449553506830399223036433213690635128087
e = 65537
c = 15001175319610946795222343924035487534008584709461878226143899906448843850120779928420944432465029785752971033689199065870408351794155945446686524700533470562991172384667710059451805009008305424805670596038911747645784329532786626324397778412957726495683422766522190746132188570946996332382787096032520348015914534837388916434188111744452280796833969638220556402855250673116813135921244590931278405785233581054716410417094016443403162280210104793301955569199264527668487539968506401974401995182691110545367915121198605642021603473376124400893881587208659717458033485422058304753162014771566156332810928502706804188737

o = [[47412728457745107106229027875259915648117103420044851871432992390178293593742914249866218522299698221781523771204375698745834487768864026409236512650009369501262196610608810334550791704365598969347066570672288841970107828704284424948297545299783041893922010965750083395574150504265229076349930292160436806574389307547,
7151707571018794760876945899933828229145285573863576752865419158057935066014037290005780895245867810865116180154261908773240188847332693040946388709971429510641144658284756647717343337707189427886779134548103093596247917788448752584977147282207642265848763954965527098894273648060044295529160371099547280549240966801721056]
,
[86373908688190255108650922007330281242126635289292162039632402486539085755381492920050696186734107745876867540145298584182833089866456957702579079961268274186732194322193257970543632758510745323419171622735686426403527865980864189590088362168524820089760626009455736356904303430576008409321011228550702593460370154288,
2739935163495322226296432842224432219815216025857635076958538964367641637837049807921996841802564467860170020056367256733719298729708060408741418149594763338760354925458404370138268461462191203576226734193278121792897686765638999384542960842700219908698775641786917353762507804532914821917178625996615671681334548749254429]
,
[15687554054832614360988742146490243595902020103032206429227782729844721078982137095466551882269747779142430460253454282190038058781992815802422733978085083098933991490277861599932099266191780563533577946414010597217513036108133130299260634025149883253291282013012600129526038544341494928677039830828249693520289847945,
6435898081098312069193282341795915540261240598097490572271117490404376893304608004242439429312067951872804606757594603664301726541469229980157872229889782597976018733187194019143564854886058611915569783145503336546231380867908138879395210171706016651896401473392042420379329349589828280175940543607255416772431728188653211]
,
[124406465365494593150435052733515823072823170460491296026120656362244377437798061499623437952508101280479833325781339254475807502914410747844180618686595086868560892928752822875608133056170303090816121179406750530664088842659591750077533970086596825128053222046148639796312807976724883488231077768029334573827303301330,
2613152126801235357605926409607555343634108914027445071424442563126602477314913418861534894059503269620876330215953120889484754924193784240242501571144710581424329983597503905140732556630904193447578828203223856219775397959234902308004140088085501789332051140882380419734289335488635960244365807950078568282028343410707589]
,
[284949676165523240398401316748486080499904237489742012461482352950411406038750742409921658105207491249100429933355996423446487597220482804381100033750232429224198596468209169113267880573088869328903032280568067097643797391791880140954369321732726087613395297706606074309398400985128432414291795513937986079041427040899,
122752138534817317154139913828763607868537178753889435773820061347875458481657673655777638644954724226442684466601221000123146328227519319228427585553483003026793833527]]

y = []
for i in range(1, 5):
    tmp1 = abs(o[i][0] - o[0][0])
    tmp2 = abs(o[i][1] - o[0][1])
    y.append(int(gcd(tmp1, tmp2)))
print(y)

p = gcd(y[0], y[1])
print(p)
print(n % p)

q = n // p

print(n == p * q)

phi = (p-1)*(q-1)
d = invert(e, phi)

m = pow(c, d, n)
print(m)
print(type(m))
print(n2s(int(m)))

记每轮输出的第一个数为oi1,第二个数为oi2，任选两轮，记为第m轮和第n轮，om1-on1为p的abs(xm-xn)倍，om2-on2为p的abs(ym-yn)倍。取om1-on1和om2-on2公约数，即为p的gcd(abs(xm-xn), abs(ym-yn))倍。

我们要求出p，接下来就是搞掉这个gcd(abs(xm-xn), abs(ym-yn))。

由于共有5轮，因而列出组合数C52共对应10个数，均为p的gcd(abs(xm-xn), abs(ym-yn))倍，x,y为每轮随机数。故可取这10个数的gcd，一般就能求出p(严格意义上还是p的k倍，但是出题人必须保证能恰好求出p来)。

事实上，我只随便选了两组数，恰好求出p(意思是此时gcd(abs(xm-xn), abs(ym-yn))恰好是gcd(abs(xm-xn), abs(ym-yn))。