signin
from Crypto.Util.number import *
from random import *
from sage.all import *
flag = b'--hidden_message--'
data1 = getPrime(256)
data2 = getPrime(256)
m = bytes_to_long(flag)+data2
prec = 600
ring = RealField(prec)
data3 = ring(data1) / ring(data2)
print(data3)
while True:
p = randint(2**255, data1)
q = randint(2**255, data2)
if isPrime(p) and isPrime(q) and p!=q:
break
n = p*q
e = 65537
leak = pow(p-q, data1, data1*data2)
c = pow(m, e, n)
print(c)
print(n)
print(leak)
'''
1.42870767357206600351348423521722279489230609801270854618388981989800006431663026299563973511233193052826781891445323183272867949279044062899046090636843802841647378505716932999588
1046004343125860480395943301139616023280829254329678654725863063418699889673392326217271296276757045957276728032702540618505554297509654550216963442542837
2793178738709511429126579729911044441751735205348276931463015018726535495726108249975831474632698367036712812378242422538856745788208640706670735195762517
1788304673303043190942544050868817075702755835824147546758319150900404422381464556691646064734057970741082481134856415792519944511689269134494804602878628
'''
解题思路：
- 恢复$data1$和$data2$
- 根据$leak$求出$p-q$整体
- 结合$n=p\cdot q$和$p-q$解方程求出$p、q$
第一步
先看这部分，第一次见，作下记录：
prec = 600
ring = RealField(prec)
data3 = ring(data1) / ring(data2)
创建了一个精度为600的实数域，并将data1和data2转600精度实数后相除的结果存入data3。可以看下转化后的结果：
data1 = 67102441031318323159886907634296426799081933019797544062238673025254134738749
data2 = 110100788358518610971858866170403859599614165252676798441791491985976469818781
prec = 600
ring = RealField(prec)
data3 = ring(data1) / ring(data2)
print(ring(data1))
print(ring(data2))
'''
6.71024410313183231598869076342964267990819330197975440622386730252541347387490000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000e76
1.10100788358518610971858866170403859599614165252676798441791491985976469818781000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000e77
'''
为什么要转实数域再计算data3而不直接相除呢，这是为了提高精度，直接相处默认的是浮点数类型，通常只有15-16位。
关于如何恢复data1和data2，需要用到连分数的思想，之前再winner attack中解出过，但也只是仅作了解，没有深入学习，也不会用来解决实际问题。
#sage
c = continued_fraction(data3)
print(c)
alist = c.convergents()
print(alist)
for i in alist:
a = str(i).split('/')
if len(a) > 1 and gcd(int(a[0]), int(a[1])) == 1 and is_prime(int(a[0])) and is_prime(int(a[1])) and int(
a[0]).bit_length() == 256 and int(a[1]).bit_length() == 256:
print(a)
#data1 = 97093002077798295469816641595207740909547364338742117628537014186754830773717
#data2 = 67958620138887907577348085925738704755742144710390414146201367031822084270769
其中，**continued_fraction()**是sage里的内置函数，对于一个连分数：$x = a_0+\frac{1}{a_1 + \frac{1}{a_2+\frac{1}{\cdots+\frac{1}{a_n}}}}$
continued_fraction(x) = $[a_0;a_1,a_2,\cdots,a_n]$
对于$x = \frac{5}{3} = 1+\frac{1}{1+\frac{1}{2}} = [1;1,2]$
#sage
x = 5.0/3.0
print(continued_fraction(x))
#[1; 1, 2]
当然这个函数也可以用python实现：
def continued_fraction(dn,n):
res = []
while dn % n:
res.append(dn//n)
dn, n = n, dn % n
res.append(dn//n)
print(res)
return res
print(continued_fraction(5,3))
#[1, 1, 2]
**convergents()**同样也是sage里的内置函数，用于计算收敛函数。
收敛函数
设有理数 $\alpha = [a_0;a_1,a_2,\cdots,a_n]$，其收敛分数为 $[a_0],[a_0;a_1],\cdots[a_0;a_1,a_2,\cdots,a_n]$
可以理解为把连分数某一项后面的全扔掉，得到一个 $\alpha$ 的近似值。收敛分数是有限的，并且越后面（就是项数越多）就越逼近 $\alpha$。
对于$x = \frac{5}{3} = 1+\frac{1}{1+\frac{1}{2}} = [1;1,2]$的收敛函数：
$[1]\to 1$
$[1;1]\to 1+\frac{1}{1}=2.0$
$[1;1,2]\to 1+\frac{1}{1+\frac{1}{2}}=\frac{5}{3}\approx 1.67$
python实现：
def Convergence_function(continued):
res =[]
for i in range(1,len(continued)+1):
tmp = 1
conver = continued[:i][::-1]
tmp = conver[0]
for j in conver[1:]:
tmp = j + 1/tmp
res.append(tmp)
return res
print(Convergence_function(continued_fraction(5,3)))
#[1, 2.0, 1.6666666666666665]
sage实现：
x = 5.0/3.0
c = continued_fraction(x)
print(c.convergents())
#[1, 2, 5/3]
参考：密码学学习笔记之连分数 | Van1sh的小屋 (jayxv.github.io)
很显然，对于两互质的数$x、y$相除$(\frac{y}{x})$，已知相除的结果，对结果求收敛函数，最后一项即为$\frac{y}{x}$
第二步
利用费马小定理解出$p-q$：
- $(p-q)^{d1} \equiv (p-q) \space mod \space d1$
- $leak = (p-q)^{d1} \space mod \space (d1\cdot d2)$
可得$(p-q) = leak \space mod \space d1$
第三步
解方程求$p、q$，这步没什么好说的。
总体代码：
e = 65537
data3 = 1.42870767357206600351348423521722279489230609801270854618388981989800006431663026299563973511233193052826781891445323183272867949279044062899046090636843802841647378505716932999588
c = 1046004343125860480395943301139616023280829254329678654725863063418699889673392326217271296276757045957276728032702540618505554297509654550216963442542837
n = 2793178738709511429126579729911044441751735205348276931463015018726535495726108249975831474632698367036712812378242422538856745788208640706670735195762517
leak = 1788304673303043190942544050868817075702755835824147546758319150900404422381464556691646064734057970741082481134856415792519944511689269134494804602878628
#sage
'''
c = continued_fraction(data3)
print(c)
alist = c.convergents()
#print(alist)
for i in alist:
a = str(i).split('/')
if len(a) > 1 and gcd(int(a[0]), int(a[1])) == 1 and is_prime(int(a[0])) and is_prime(int(a[1])) and int(
a[0]).bit_length() == 256 and int(a[1]).bit_length() == 256:
print(a)
'''
data1 = 97093002077798295469816641595207740909547364338742117628537014186754830773717
data2 = 67958620138887907577348085925738704755742144710390414146201367031822084270769
t = leak % data1
p,q = symbols('p q')
eq1 = Eq(p*q, n)
eq2 = Eq(p-q, t)
sol = solve((eq1, eq2), (p, q))
print(sol)
p = 89050782851818876669770322556796705712770640993210984822169118425068336611139
q = 31366133449465349655535843217834713141354178841659172525867412449648339136903
d = inverse(e,(p-1)*(q-1))
m = pow(c,d,n)
print(long_to_bytes(m - data2))
CrazyTreat
from Crypto.Util.number import *
from random import randint
from secret import flag
def TrickPrime(bits):
p = getPrime(bits)
q = getPrime(bits)
cut = randint(1,256)
temp = p*q
print('clown =',temp)
game = (p&(2**bits-1)) >>cut<<cut #p高位需要给出
print("trick =",game)
return p,q
def CrazyPrime(nbits):
p = getPrime(nbits)
q = getPrime(nbits)
r = getPrime(nbits)
n = p * q * r
print("n =", n)
m = getPrime(256)
P = pow(m, p, n)
Q = pow(m, q, n)
R = pow(m, r, n)
print("P =", P)
print("Q =", Q)
print("R =", R)
return m
P,Q = TrickPrime(512)
R = CrazyPrime(512)
N =P*Q*R
phi = (P-1)*(Q-1)*(R-1)
e = 65537
d = inverse(e,phi)
m = bytes_to_long(flag)
c = pow(m,e,N)
print("c = ",c)
'''
clown = 128259792862716016839189459678072057136816726330154776961595353705839428880480571473066446384217522987161777524953373380960754160008765782711874445778198828395697797884436326877471408867745183652189648661444125231444711655242478825995283559948683891100547458186394738621410655721556196774451473359271887941209
trick = 13053422630763887754872929794631414002868675984142851995620494432706465523574529389771830464455212126838976863742628716168391373019631629866746550551576576
n = 924936528644761261915490226270682878749572154775391302241867565751616615723850084742168094776229761548826664906020127037598880909798055174894996273670320006942669796769794827782190025101253693980249267932225152093301291975335342891074711919668098647971235568200490825183676601392038486178409517985098598981313504275523679007669267428032655295176395420598988902864122270470643591017567271923728446920345242491655440745259071163984046349191793076143578695363467259
P = 569152976869063146023072907832518894975041333927991456910198999345700391220835009080679006115013808845384796762879536272124713177039235766835540634080670611913370463720348843789609330086898067623866793724806787825941048552075917807777474750280276411568158631295041513060119750713892787573668959642318994049493233526305607509996778047209856407800405714104373282610244944206314614906974275396096712817649817035559000245832673082730407216670764400076473183825246052
Q = 600870923560313304359037202752076267074889238956345564584928427345594724253036201151726541881494799597966727749590645445697106549304014936202421316051605075583257261728145977582815350958084624689934980044727977015857381612608005101395808233778123605070134652480191762937123526142746130586645592869974342105683948971928881939489687280641660044194168473162316423173595720804934988042177232172212359550196783303829050288001473419477265817928976860640234279193511499
R = 502270534450244040624190876542726461324819207575774341876202226485302007962848054723546499916482657212105671666772860609835378197021454344356764800459114299720311023006792483917490176845781998844884874288253284234081278890537021944687301051482181456494678641606747907823086751080399593576505166871905600539035162902145778102290387464751040045505938896117306913887015838631862800918222056118527252590990688099219298296427609455224159445193596547855684004680284030
c = 10585127810518527980133202456076703601165893288538440737356392760427497657052118442676827132296111066880565679230142991175837099225733564144475217546829625689104025101922826124473967963669155549692317699759445354198622516852708572517609971149808872997711252940293211572610905564225770385218093601905012939143618159265562064340937330846997881816650140361013457891488134685547458725678949
'''
解题思路：
- 根据$TrickPrime$求解$P、Q$
- 根据$CrazyPrime$求解$R$
第一步
稍作分析可知属于已知p的高位攻击
第二步
有下面的关系：
- $P \equiv m^p mod n$
- $Q \equiv m^q mod n$
- $R = m^r mod n$
利用费马小定理，$P = m^p \equiv m \space mod \space p = m + k1 \cdot p$
$P - m = k1 \cdot p$
类似还可得：
$Q - m = k2 \cdot q、$$R - m = k3 \cdot r$
三式相乘：
$(P-m) \cdot (Q-m) \cdot (R-m) = k \cdot n \equiv 0 \space mod \space n$
展开解方程求m即可。
整体代码如下：
#sage
'''
clown = ...
trick = ...
for cut in range(1,256):
p4 = trick >> cut << cut
PR.<x> = PolynomialRing(Zmod(clown))
f = x + p4
roots = f.small_roots(X=2^cut,beta=0.4)
if roots:
P = p4 + int(roots[0])
Q = clown // p
print("P: " + str(P))
print("Q: " + str(Q))
'''
P = 13053422630763887754872929794631414002868675984142851995620494432706465523574529389771830464531559991042565319610790540616696456104018890243275374098291711
Q = 9825759610390416003138880321039057063786120681277009947660201742655391150627525256689197020107593156663696181775606008771199371337506657207530847665591719
#sage
'''
n = ...
P = ...
Q = ...
R = ...
PR.<m> = PolynomialRing(Zmod(n))
f = P*Q*R - (P*Q+P*R+Q*R) * m + (P+Q+R) * m^2 - m^3
R = f.monic().small_roots(X=2^256, beta=0.4,epsilon=0.01)
print(R)
'''
R = 105960538296223496551922954965164644267919720177702173352061963871195469608683
N =P*Q*R
phi = (P-1)*(Q-1)*(R-1)
e = 65537
d = inverse(e,phi)
m = pow(c,d,N)
print(long_to_bytes(m))
#b'SYC{N0b0dy_Kn0vvs_CryPt0_be7t3r_7haN_Me}'
Alexei needs help
from random import randint
import gmpy2 as gp
from Crypto.Util.number import *
from Crypto.Cipher import AES
from hashlib import md5
from binascii import *
from secret import flag
a,b = randint(2,2**512), randint(2,2**512)
m = getPrime(512)
n = 2023
seq = [randint(2,2**512) for _ in range(10)]
def seqsum(i):
ans = 0
for j in range(len(seq)):
ans += gp.powmod(i,j,m)*seq[j]
return ans
def homework(i):
if i == 1:
return 1
if i == 2:
return 1
else:
return (a*homework(i-1)+b*homework(i-2)+seqsum(i))%m
ans = homework(n)
k = unhexlify(md5(str(ans).encode()).hexdigest())
aes = AES.new(k,AES.MODE_ECB)
data = flag + (16-len(flag)%16)*b"\x00"
ct = hexlify(aes.encrypt(data))
print('a = ',a)
print('b = ',b)
print('m = ',m)
print('seq = ',seq)
print('ct = ',ct)
'''
a = 12760960185046114319373228302773710922517145043260117201359198182268919830481221094839217650474599663154368235126389153552714679678111020813518413419360215
b = 10117047970182219839870108944868089481578053385699469522500764052432603914922633010879926901213308115011559044643704414828518671345427553143525049573118673
m = 9088893209826896798482468360055954173455488051415730079879005756781031305351828789190798690556659137238815575046440957403444877123534779101093800357633817
seq = [1588310287911121355041550418963977300431302853564488171559751334517653272107112155026823633337984299690660859399029380656951654033985636188802999069377064, 12201509401878255828464211106789096838991992385927387264891565300242745135291213238739979123473041322233985445125107691952543666330443810838167430143985860, 13376619124234470764612052954603198949430905457204165522422292371804501727674375468020101015195335437331689076325941077198426485127257539411369390533686339, 8963913870279026075472139673602507483490793452241693352240197914901107612381260534267649905715779887141315806523664366582632024200686272718817269720952005, 5845978735386799769835726908627375251246062617622967713843994083155787250786439545090925107952986366593934283981034147414438049040549092914282747883231052, 9415622412708314171894809425735959412573511070691940566563162947924893407832253049839851437576026604329005326363729310031275288755753545446611757793959050, 6073533057239906776821297586403415495053103690212026150115846770514859699981321449095801626405567742342670271634464614212515703417972317752161774065534410, 3437702861547590735844267250176519238293383000249830711901455900567420289208826126751013809630895097787153707874423814381309133723519107897969128258847626, 2014101658279165374487095121575610079891727865185371304620610778986379382402770631536432571479533106528757155632259040939977258173977096891411022595638738, 10762035186018188690203027733533410308197454736009656743236110996156272237959821985939293563176878272006006744403478220545074555281019946284069071498694967]
ct = 37dc072bdf4cdc7e9753914c20cbf0b55c20f03249bacf37c88f66b10b72e6e678940eecdb4c0be8466f68fdcd13bd81
'''
homework类似斐波那契函数，有很多多余的计算，利用循环记录中间的值，减少不必要的运算：
a = ...
b = ...
m = ...
seq = [...]
ct = '...'
n = 2023
def seqsum(i):
ans = 0
for j in range(len(seq)):
ans += (powmod(i,j,m)*seq[j])%m #加个模运算，可以减小规模加快运算，不加其实也很快了
return ans
t = [1,1]
def homework(i):
for _ in range(3, i+2):
t.append((a*t[-1] + b*t[-2] + seqsum(_))%m) # 利用循环代替递归，避免重复运算
return t[i-1]
ans = homework(n)
k = unhexlify(hashlib.md5(str(ans).encode()).hexdigest())
aes = AES.new(k,AES.MODE_ECB)
m = aes.decrypt(long_to_bytes(int(ct,16)))
print(m)
安洵杯2023 Writeup - 星盟安全团队 (xmcve.com)
安洵杯2023wp - ukfc战队_UmVfX1BvaW50的博客-CSDN博客
安洵杯2023 Writeup -Polaris战队 (qq.com)
转载请注明来源，欢迎对文章中的引用来源进行考证，欢迎指出任何有错误或不够清晰的表达。可以在下面评论区评论，也可以邮件至 1666739907@qq.com