[idekCTF 2025] diamond ticket

很久没写了。最近的比赛不啥地，或者特别简单或者特别难。难的又找不到WP。

这个idek感觉非常好，但是找不着WP很苦恼。终于找到一个题的，记录一下。

WP: idekCTF 2025 - Connor M

先看看原题：

from Crypto.Util.number import *#Some magic from Willy Wonka
p = 170829625398370252501980763763988409583
a = 164164878498114882034745803752027154293
b = 125172356708896457197207880391835698381def chocolate_generator(m:int) -> int:return (pow(a, m, p) + pow(b, m, p)) % p#The diamond ticket is hiding inside chocolate
diamond_ticket = open("flag.txt", "rb").read()
assert len(diamond_ticket) == 26
assert diamond_ticket[:5] == b"idek{"
assert diamond_ticket[-1:] == b"}"
diamond_ticket = bytes_to_long(diamond_ticket[5:-1])flag_chocolate = chocolate_generator(diamond_ticket)
chocolate_bag = []#Willy Wonka are making chocolates
for i in range(1337):chocolate_bag.append(getRandomRange(1, p))#And he put the golden ticket at the end
chocolate_bag.append(flag_chocolate)#Augustus ate lots of chocolates, but he can't eat all cuz he is full now :D
remain = chocolate_bag[-5:]#Compress all remain chocolates into one
remain_bytes = b"".join([c.to_bytes(p.bit_length()//8, "big") for c in remain])#The last chocolate is too important, so Willy Wonka did magic again
P = getPrime(512)
Q = getPrime(512)
N = P * Q
e = bytes_to_long(b"idek{this_is_a_fake_flag_lolol}")
d = pow(e, -1, (P - 1) * (Q - 1))
c1 = pow(bytes_to_long(remain_bytes), e, N)
c2 = pow(bytes_to_long(remain_bytes), 2, N) # A small gift#How can you get it ?
print(f"{N = }")
print(f"{c1 = }")
print(f"{c2 = }") """
N = 85494791395295332945307239533692379607357839212287019473638934253301452108522067416218735796494842928689545564411909493378925446256067741352255455231566967041733698260315140928382934156213563527493360928094724419798812564716724034316384416100417243844799045176599197680353109658153148874265234750977838548867
c1 = 27062074196834458670191422120857456217979308440332928563784961101978948466368298802765973020349433121726736536899260504828388992133435359919764627760887966221328744451867771955587357887373143789000307996739905387064272569624412963289163997701702446706106089751532607059085577031825157942847678226256408018301
c2 = 30493926769307279620402715377825804330944677680927170388776891152831425786788516825687413453427866619728035923364764078434617853754697076732657422609080720944160407383110441379382589644898380399280520469116924641442283645426172683945640914810778133226061767682464112690072473051344933447823488551784450844649
"""

首先他给出了参数p,a,b并把flag的芯m作了个(a^m+b^m)%p的运算。

第二步取了1337个随机数并把上一步的c放到尾部然后取尾部5个值（显然1337个只用到后4个）连接成字符串再转整，也就是作了个前填充。

第三步作了个RSA，一个是c1=c^e%N,c2=c^2%N，这一步就是共模攻击很容易出

N,c1,c2 = ...
e = bytes_to_long(b"idek{this_is_a_fake_flag_lolol}")_, k1, k2 = xgcd(e, 2)
remain_bytes = long_to_bytes(pow(c1, k1, N) * pow(c2, k2, N) % N)
flag_chocolate = bytes_to_long(remain_bytes[-16:]) # 99584795316725433978492646071734128819

先列方程：c=a^m+b^m mod p 令b=a^k 则c = a^m + (a^m)^k 令X=a^m则有c =X+X^k

拿到这个式子实际上就可以计算了，但在sage上k有亿点大，理论小点的话是可解的。所以（这估计是个论文题，这种方法第一次见）就用到gcd方法。这里引入了一个所有解的公式：

g = pow(x, p, f) - x #g(x) = x^p -x 是所有线性因子的乘积（实际上是所有根）

这两个式子gcd就能得到想要的根（未完）

这里的m解出后实际上是m%p的值

p = 170829625398370252501980763763988409583
a = 164164878498114882034745803752027154293
b = 125172356708896457197207880391835698381c = 99584795316725433978492646071734128819
k = GF(p)(b).log(a)PR.<x> = PolynomialRing(GF(p))
f = x + x**k - c
#g(x) = x^p -x 是所有线性因子的乘积（实际上是所有根）
g = pow(x, p, f) - x
X = [r for r in f.gcd(g).roots()][0][0]
m = GF(p)(X).log(a)
print(f'{m = }') # 4807895356063327854843653048517090061

第三步就是用CVP算法，这里调用了ortools并用了github上的一个模块，用CVP求一个最近平面。

load('./linineq.py')p = 170829625398370252501980763763988409583
o = (p-1)//2
m = 4807895356063327854843653048517090061M = matrix([[256**i for i in reversed(range(20))]])
b = [m]
lb = [30]*20 
ub = [128]*20 for sol in solve_bounded_mod_gen(M, b, lb, ub, o, solver='ortools'):print(bytes(sol))

一道题学到不少东西。好题！