2024-NepCTF-wp-crypto

包含三个题的题解，剩下的对称和哈希确实是太不会了(๑¯ω¯๑)

ezRSA

题目描述：

Easy RSA, easy strategy. No need to brute force.

题目：

from Crypto.Util.number import getStrongPrime, getRandomNBitInteger, GCD, inverse, long_to_bytes, bytes_to_long
from flag import flag


def gen_parameters(bits_leak, beta):
    p = getStrongPrime(1024)
    q = getStrongPrime(1024)
    N = p*q
    phi = (p-1)*(q-1)

    while True:
        d = getRandomNBitInteger(int(2048*beta))
        if GCD(d, phi) == 1:
            break
    e = inverse(d, phi)

    gift1 = d & ((1<<bits_leak) - 1)
    gift2 = phi & ((1<<bits_leak) - 1)
    print(f'e={hex(e)}')
    print(f'N={hex(N)}\n')
    print(f'gift1={hex(gift1)}')
    print(f'gift2={hex(gift2)}')
    return e, d, N, gift1, gift2, p, q

def main():
    e, d, N, _, _, _, _ = gen_parameters(bits_leak=450, beta=0.47)
    
    flag_head = b'NepCTF{'
    assert flag.startswith(flag_head)
    pt = bytes_to_long(flag[len(flag_head):-1])
    ct = pow(pt, e, N)
    print(f'ct={hex(ct)}')

main()

"""
e=0xa14e64d0948eaa7df3eb514802e74ff6070d3ea7f16f712646ff794f2b50aa787e4b829ce09dee1d3e1add7c55d870b931b415b1e282259af005c46ce1bc38388fa530d3931b8b8d7a163fb4ca4252e4b77625e80354b8fb3fce7455dac4bdcbe04dfe743d3f628ad1093ecf22f97fa17eb67445f5edc507eb368b364bc9d77da6fcfce7896ef3259fc7a4e66835f99c3c10ca6e6013dd8f01036b26b08dd5ddfddba35e3037c7a4187edd3323685d888ff3b99edf1caf8b93b4a851dc2af95a216b313192b368c1ed77f2a4ac6ddb2c46383806659d7037c25533c0bf5e4f1f665f2bd5529ebbadba40b07ea9b4dee91f42e0ac69bcbe28573e8c4f5744847
N=0xbb4efd151c65add72c7ff259687c11ee9d2d82d4058485d2a8abf80839f9da4d2bb1191b97b05d4a581f28e62f91784a2da912f98c2ef95273b311fc8c5dd4c468d82dee499874a88dda554aedc1d417dcacfc9bd787854db7a70575abb48e7c20d2662a2484391518357af55c18eb424687c2990ca10e89efcf019ff945705851bcc58673c2534c592a461bffbfc5369aeb31bc28998dfcaa0e7b3ab044005376fba8364151933ce73a12a4c3b7df7902cb462a95fc2e6d9596f3bebd712da63329bb4d45f1274852e81f04764fa610f5a86424e6026b10fc41c079d2649699be28716aa2da8c6e36276ea4f80eb3b2b4d921bd829046b5b6bd62e401116b47
gift1=0x265e264a10862ccc5ede757362bc872ab562d201ddda1a4bec70cbe6becd71a411b1fc0bbc627f32fa0ee2ea0ceb91712d5c5187d8a2b0cb7
gift2=0x2a1d29d36d731c528cc0cdd27e8b60a0596de783b591f85fb3f8c78bbe28e7d7d9710b41778789ad0dca7088e244c1df4aaf4d27a2afec428

ct=0x71ac11e0b2bf7fca3e0ba051f74c90c4615ffca644fb69e7ed6c4dc1432d76049ad70ff1a9c3117c7d7db0c4fdc35518ef72068b2edb82dfeb9f7858376d4354633c63414b30584e28a70d90d5c5894d61a4e677721684e51ea52ac5747e33aa467f6a4e3e856f6ef08834d3fc70fec2d7229d14ccb761675be67ec87614b3e24f9c0d07463d2c636186d6ff7514a681ade1e5901afead97c6fa3df938cee004bef836cf32b07a33edfdc4268847e69d0cbc4b1b316ffdcf0e11cc03e03090e43789ae414f07be7d23be02f28f2bc507c72054bba6341265c64e52c038633023ff4b13e8d863816a29114a0773b62568912b4d22a8162ab0d7bf2bb8af265e21
"""

题目用1024bit的素数p、q组成RSA模数n，并且用960bit的d当作RSA的私钥之后，计算出加密指数e，并对flag进行加密。

此外，题目还额外给出了d和phi的低450bit，要求还原明文。

有高低位泄露，基本确定是copper的，而由于d本身也很小，所以自然用的是下面这个式子：

$$ed = 1 + k\phi$$

把已知的低位信息加入其中就得到：

$$e(2^{450}d_h + d_l) = 1 + k(2^{450}\phi_h + \phi_l)$$

模掉2^450就有：

$$ed_l = 1 + k\phi_l \quad(mod\;2^{450})$$

可以看出只有k是未知的，所以在模2^450下解方程，得到的结果就是可能的k低位。有了k的低位之后再代回刚才的式子得到：

$$e(2^{450}d_h + d_l) = 1 + (2^{450}k_h + k_l)\phi$$

又因为有：

$$\phi = 2^{450}\phi_h + \phi_l = n - (p+q) + 1$$

所以在模2^450下有：

$$\phi_l = n - (p+q)_l + 1 \quad(mod\;2^{450})$$

所以我们其实也就有p+q的低位，综上所述，最终的式子为：

$$e(2^{450}d_h + d_l) = 1 + (2^{450}k_h + k_l)[n - (2^{450}(p+q)_h + (p+q)_l) + 1]$$

模e得到：

$$f = 1 + (2^{450}k_h + k_l)[n - (2^{450}(p+q)_h + (p+q)_l) + 1] \quad(mod\;e)$$

显然有：

$$f(x,y) = 1 + (2^{450}x + k_l)[n - (2^{450}y + (p+q)_l) + 1] \quad(mod\;e)$$ $$f(k_h,(p+q)_h) = 0 \quad(mod\;e)$$

由于k与d数量级相当，p+q也并不大，所以两者均为小根，二元copper即可。

exp：

from Crypto.Util.number import *
import itertools

def small_roots(f, bounds, m=1, d=None):
	if not d:
		d = f.degree()

	R = f.base_ring()
	N = R.cardinality()
	
	f /= f.coefficients().pop(0)
	f = f.change_ring(ZZ)

	G = Sequence([], f.parent())
	for i in range(m+1):
		base = N^(m-i) * f^i
		for shifts in itertools.product(range(d), repeat=f.nvariables()):
			g = base * prod(map(power, f.variables(), shifts))
			G.append(g)

	B, monomials = G.coefficients_monomials()
	monomials = vector(monomials)

	factors = [monomial(*bounds) for monomial in monomials]
	for i, factor in enumerate(factors):
		B.rescale_col(i, factor)

	B = B.dense_matrix().LLL()

	B = B.change_ring(QQ)
	for i, factor in enumerate(factors):
		B.rescale_col(i, 1/factor)

	H = Sequence([], f.parent().change_ring(QQ))
	for h in filter(None, B*monomials):
		H.append(h)
		I = H.ideal()
		if I.dimension() == -1:
			H.pop()
		elif I.dimension() == 0:
			roots = []
			for root in I.variety(ring=ZZ):
				root = tuple(R(root[var]) for var in f.variables())
				roots.append(root)
			return roots

	return []

e=0xa14e64d0948eaa7df3eb514802e74ff6070d3ea7f16f712646ff794f2b50aa787e4b829ce09dee1d3e1add7c55d870b931b415b1e282259af005c46ce1bc38388fa530d3931b8b8d7a163fb4ca4252e4b77625e80354b8fb3fce7455dac4bdcbe04dfe743d3f628ad1093ecf22f97fa17eb67445f5edc507eb368b364bc9d77da6fcfce7896ef3259fc7a4e66835f99c3c10ca6e6013dd8f01036b26b08dd5ddfddba35e3037c7a4187edd3323685d888ff3b99edf1caf8b93b4a851dc2af95a216b313192b368c1ed77f2a4ac6ddb2c46383806659d7037c25533c0bf5e4f1f665f2bd5529ebbadba40b07ea9b4dee91f42e0ac69bcbe28573e8c4f5744847
N=0xbb4efd151c65add72c7ff259687c11ee9d2d82d4058485d2a8abf80839f9da4d2bb1191b97b05d4a581f28e62f91784a2da912f98c2ef95273b311fc8c5dd4c468d82dee499874a88dda554aedc1d417dcacfc9bd787854db7a70575abb48e7c20d2662a2484391518357af55c18eb424687c2990ca10e89efcf019ff945705851bcc58673c2534c592a461bffbfc5369aeb31bc28998dfcaa0e7b3ab044005376fba8364151933ce73a12a4c3b7df7902cb462a95fc2e6d9596f3bebd712da63329bb4d45f1274852e81f04764fa610f5a86424e6026b10fc41c079d2649699be28716aa2da8c6e36276ea4f80eb3b2b4d921bd829046b5b6bd62e401116b47
dl=0x265e264a10862ccc5ede757362bc872ab562d201ddda1a4bec70cbe6becd71a411b1fc0bbc627f32fa0ee2ea0ceb91712d5c5187d8a2b0cb7
phil=0x2a1d29d36d731c528cc0cdd27e8b60a0596de783b591f85fb3f8c78bbe28e7d7d9710b41778789ad0dca7088e244c1df4aaf4d27a2afec428
ct=0x71ac11e0b2bf7fca3e0ba051f74c90c4615ffca644fb69e7ed6c4dc1432d76049ad70ff1a9c3117c7d7db0c4fdc35518ef72068b2edb82dfeb9f7858376d4354633c63414b30584e28a70d90d5c5894d61a4e677721684e51ea52ac5747e33aa467f6a4e3e856f6ef08834d3fc70fec2d7229d14ccb761675be67ec87614b3e24f9c0d07463d2c636186d6ff7514a681ade1e5901afead97c6fa3df938cee004bef836cf32b07a33edfdc4268847e69d0cbc4b1b316ffdcf0e11cc03e03090e43789ae414f07be7d23be02f28f2bc507c72054bba6341265c64e52c038633023ff4b13e8d863816a29114a0773b62568912b4d22a8162ab0d7bf2bb8af265e21
beta=0.47
dbit = int(2048*beta)
bits_leak=450

if(0):#test
    def gen_parameters(bits_leak, beta):
        p = getStrongPrime(1024)
        q = getStrongPrime(1024)
        N = p*q
        phi = (p-1)*(q-1)

        while True:
            d = getRandomNBitInteger(int(2048*beta))
            if GCD(d, phi) == 1:
                break
        e = inverse(d, phi)

        gift1 = d & ((1<<bits_leak) - 1)
        gift2 = phi & ((1<<bits_leak) - 1)
		
        pqh = ((p+q) - ((p+q) % 2^bits_leak)) >> bits_leak
        k = (e*d-1)//phi
        kh = (k - (k % 2^bits_leak)) >> bits_leak
        return e, d, N, gift1, gift2, p, q, pqh, kh
	
    e, d, N, dl, phil, p, q, pqhh, khh = gen_parameters(bits_leak, beta)

kl = var('kl')
kls = solve_mod([e*dl - kl*phil - 1 == 0], 2^bits_leak)
pql = (N + 1 - phil) % 2^bits_leak

PR.<kh,pqh> = PolynomialRing(Zmod(e))
for kl in kls:
    kl = int(kl[0])
    f = 1 + (2^bits_leak*kh + kl)*(N - 2^bits_leak*pqh - pql + 1)
    res = small_roots(f, (2^(dbit-bits_leak),2^(1024-bits_leak)), m=4,d=3)
    if(res != []):
        pqh = int(res[0][1])
        p_q = 2^bits_leak*pqh + pql
        break

PR.<p,q> = PolynomialRing(ZZ)
f1 = p+q-p_q
f2 = p*q-N
p = int(f1.sylvester_matrix(f2, q).det().univariate_polynomial().monic().roots()[0][0])
q = N // p
print(long_to_bytes(int(pow(ct,inverse(e,(p-1)*(q-1)),N))))


#NepCTF{YOu_m4k3_a_n3w_rec0rd_on_RS4_L5B_attack(bushi)}

ezRNG

题目描述：

后门在哪里？

题目：

from random import randint
from hashlib import sha256
from secret import FLAG,secret
from gmpy2 import next_prime
from Crypto.Util.number import inverse,getPrime
assert FLAG == b'NepCTF{'+ secret + b'}'
class RNG():
    def __init__(self, EllipticCurve):
        self.E = EllipticCurve
        self.G = E.gens()[0]

        self.mask = randint(1,1 << (bits//4))
        self.k = getPrime(bits//2)
        self.P = self.G * self.k
        self.save = 0
        self.check = 0
        self.init()
        self.r = 0

    def init(self):
        self.g = self.mask * self.P
        self.state = self.g 

    def next(self):
        if self.check :
            self.r = -self.save
        else:
            self.r = -self.r+1

        self.state = self.g + self.r*self.G
        self.check = self.check^^1
        self.save = self.r

    def generate(self):
        result = self.state
        self.next()
        return int(result.x()) % (2**192)

def LuanGao(m,e):
    q = 11091427946088586538326341642081147908870478369361079372527019919422720334995105276694411660643624940624081943057158631573866470376362760554084973766546671
    p = 7164778143059850549407362450312125862993617607522974512258134374430678370277239436047396839637741848829691805270124657225690426144253093636119389335193487
    e = next_prime(e)
    d = inverse(e,(q-1)*(p-1))
    n = p*q
    c = pow(m,e,n)
    assert pow(c,d,n) == m
    return c

p = 0xffffffff00000001000000000000000000000000ffffffffffffffffffffffff
a = 0xffffffff00000001000000000000000000000000fffffffffffffffffffffffc
b = 0x5ac635d8aa3a93e7b3ebbd55769886bc651d06b0cc53b0f63bce3c3e27d2604b
bits = 256
E = EllipticCurve(GF(p), [a, b])
ECRNG = RNG(E)

mask = randint(1,1 << (bits//4))
r = randint(1,1 << 50)

hint = ECRNG.mask * ECRNG.k
print(f'[+] hint1 = {mask * ECRNG.k + r}')
print(f'[+] hint2 = {LuanGao( int(hint), int(ECRNG.g.x() ) )}')
rngs = []
for _ in range(11):
    rng = ECRNG.generate()
    rngs.append(rng)
print(f'[+] RNG = {rngs}')

assert secret == sha256(str(ECRNG.k).encode()).hexdigest()[:32]
'''
[+] hint1 = 949922372122218046965376048123327949376059750438908466789
[+] hint2 = 42661446485198521271563058189095752632693753444357982122758630843460108543281128080768183549656737420326730293402550080264919238271649443935367948621363611575578331951338206643961231301011934223378959132807605885282642130943670906793105685979458606431074604742691074803447316574328163268414104662367677573967
[+] RNG = [4198417781636735201616143091518824554303140448918234022822, 5934409889673636438564616521101931172645172047323840506005, 3545002769746467918593131186352102479907282194938281480964, 2052948548433827202413664681039848372904955567280762860403, 2409094928081781569924602821161748044701954566232724831425, 1384139093745169579221979501259712235516420223327557162332, 2939419134440891551148261965652575020956010158334816580524, 494864169851388494465000363130678068052130861967409621970, 3170747752017462050285295477866296066114421905697920861241, 3947558462622235401389908529480430195424430102289969854250, 5945090099574459201888181110413355524959030561838939467012]
'''

题目基于一个ECRNG发生器，曲线是NIST-256p，具体来说其给出参数的流程是：

• 初始化曲线NIST-256p，得到生成元G

• 随机生成ECRNG的mask和k，分别是64bit和128bit

• 计算：

  $$P = k \cdot G$$ $$g = mask \cdot P$$

• 给出g以及以下点的横坐标的低192位MSB：

  $$g \pm i \cdot G \quad , \quad i \in[1,2,3,4,5]$$

• 生成另外的mask和r，分别是64bit和50bit(注意和ECRNG的mask区分开)

• 计算：

  $$hint = mask_{ECRNG} \cdot k_{ECRNG}$$ $$hint_1 = mask \cdot k_{ECRNG} + r$$ $$hint_2 = hint^{g_x + \delta} \quad(mod\;n)$$

• 给出hint1、hint2，并且其中组成n的大素数p、q是已知的

由题目得到，解出ECRNG的k就是得到了flag，所以步骤应该为：

• 解出点g的横坐标，从而解hint2对应的RSA得到hint
• 由hint和hint1得到ECRNG的k

第一步其实很明显是个ECHNP，其核心思路在之前的西湖论剑中的一个题目我有提到过：

2022-西湖论剑-wp-crypto | 糖醋小鸡块的blog (tangcuxiaojikuai.xyz)

而上一次阿里云CTF已经出现过了含最新上界的copper解法，这个题目上界明显足够，所以可以沿用上一次比赛的代码，这次比赛我用了lem0师傅的：

https://blog.csdn.net/qq_41626232/article/details/137045277?spm=1001.2014.3001.5502

求出gx之后就很好办，由于hint是k和一个小mask的乘积，所以其实直接yafu都可以得到k。

预期应该是用Multivariate polynomial approach的AGCD，这一部分可以参考今年高校密码挑战赛的wp里面的12题。

exp：

from sage.all import *
from Crypto.Util.number import *
from re import findall
from subprocess import check_output
import fgb_sage
from itertools import *

def flatter(M):
    # compile https://github.com/keeganryan/flatter and put it in $PATH
    z = "[[" + "]\n[".join(" ".join(map(str, row)) for row in M) + "]]"
    ret = check_output(["flatter"], input=z.encode())
    return matrix(M.nrows(), M.ncols(), map(int, findall(b"-?\\d+", ret)))
def LLL_mononimals(ff,bounds,debug = False):
    G = Sequence([], ff[0].parent())
    for i in range(len(ff)):
        G.append(ff[i])
    B, monomials = G.coefficients_monomials()
    monomials = vector(monomials)
    factors = [monomial(*(bounds)) for monomial in monomials]
    for i, factor in enumerate(factors):
        B.rescale_col(i, factor)
    print("dim",B.nrows(),B.ncols())
    print('s flatter')
    # B = B.dense_matrix().LLL()
    B = flatter(B)
    print('e flatter')
    B = B.change_ring(QQ)
    for i, factor in enumerate(factors):
        B.rescale_col(i, 1 / factor)
    R = B*monomials
    if debug:
        for i in range(len(R)):
            if R[i](*([e0]+EE)) == 0:
                print(i)
    Res = []
    V = fgb_sage.groebner_basis(R[8:20])
    XX = [x0,y1,y2,y3,y4,y5]
    for i in range(len(XX)):
        Res.append(XX[i] - V[i])
    return Res

####################################################################################### part1 get gx
p = 0xffffffff00000001000000000000000000000000ffffffffffffffffffffffff
a = 0xffffffff00000001000000000000000000000000fffffffffffffffffffffffc
b = 0x5ac635d8aa3a93e7b3ebbd55769886bc651d06b0cc53b0f63bce3c3e27d2604b
E = EllipticCurve(GF(p),[a,b])
G = E.gens()[0]
n = G.order()
def leak(Point,k):
    t1 = (ZZ(Point.xy()[0]) >> k) << k
    t2 = ZZ(Point.xy()[0])-t1
    return t2
def Get(AA,i,R):
    return leak(AA+i*R,192)
def Coe(H,Qx,h0,a,b,p):
    inv = inverse(2^192,p)
    A = (H*(h0-Qx)^2-2*h0^2*Qx-2*(a+Qx^2)*h0-2*a*Qx-4*b)*inv^3 % p
    B = (2*(H*(h0-Qx)-2*h0*Qx-a-Qx^2))*inv^2 % p
    C = ((H-2*Qx))*inv^1 % p
    D = ((h0-Qx)^2)*inv^2 % p
    E = (2*(h0-Qx))*inv^1 % p
    return A%p,B%p,C%p,D%p,E%p

hint1 = 949922372122218046965376048123327949376059750438908466789
hint2 = 42661446485198521271563058189095752632693753444357982122758630843460108543281128080768183549656737420326730293402550080264919238271649443935367948621363611575578331951338206643961231301011934223378959132807605885282642130943670906793105685979458606431074604742691074803447316574328163268414104662367677573967
h = [4198417781636735201616143091518824554303140448918234022822, 5934409889673636438564616521101931172645172047323840506005, 3545002769746467918593131186352102479907282194938281480964, 2052948548433827202413664681039848372904955567280762860403, 2409094928081781569924602821161748044701954566232724831425, 1384139093745169579221979501259712235516420223327557162332, 2939419134440891551148261965652575020956010158334816580524, 494864169851388494465000363130678068052130861967409621970, 3170747752017462050285295477866296066114421905697920861241, 3947558462622235401389908529480430195424430102289969854250, 5945090099574459201888181110413355524959030561838939467012]
h0 = h[0]
Hs = [h[2*i+1] + h[2*i+2] for i in range(5)]
Qs = []

n,d,t = 5,2,1
for i in range(1,n+1):
    Q = i*G
    Qs.append(Q)
As,Bs,Cs,Ds,Es = [],[],[],[],[]
for i in range(n):
    Ai,Bi,Ci,Di,Ei = Coe(Hs[i],Qs[i].xy()[0],h0,a,b,p)
    As.append(ZZ(Ai))
    Bs.append(ZZ(Bi))
    Cs.append(ZZ(Ci))
    Ds.append(ZZ(Di))
    Es.append(ZZ(Ei))
PR.<x0,y1,y2,y3,y4,y5> = PolynomialRing(ZZ)
y = [y1,y2,y3,y4,y5]
Fs = []
for i in range(n):
    fi = As[i] + Bs[i]*x0 + Cs[i]*x0^2 + Ds[i]*y[i] + Es[i]*x0*y[i] + x0^2*y[i]
    Fs.append(fi)
Exp_res =[]
for i in range(2^5):
    t = [int(j) for j in bin(i)[2:].zfill(5)]
    Exp_res.append(t)
def Get_js(exp):
    j = [exp[i]*(i+1) for i in range(len(exp)) if exp[i]!=0]
    return j
def get_row1(k,js):
    res = 1
    for u in range(len(js)):
        if u!=k:
            res*=(x0^2+Es[js[u]-1]*x0+Ds[js[u]-1])
    return res
def get_row2(k,js):
    res = x0
    for u in range(len(js)):
        if u!=k:
            res*=(x0^2+Es[js[u]-1]*x0+Ds[js[u]-1])
    return res
def get_M(js):
    G = Sequence([], Fs[0].parent())
    for i in range(len(js)):
        G.append(get_row1(i,js))
    for i in range(len(js)):
        G.append(get_row2(i,js))
    M , mons = G.coefficients_monomials()
    M = M[:,::-1]
    return M
def Get_prodF(u,js,y):
    ttf = y[js[u-1]-1]
    for i in range(len(js)):
        if i!=(u-1):
            ttf *= Fs[js[i]-1]
    return ttf
ff = []
n,d,t = 5,2,1
for i0 in range(2*d):
    for l in range(d+1):
#         f_temp=1
#         bounds = [(2^86)]*6
        if 1 <= l <= d and 0 <= i0 <= (2*l-1):
            f_temp = p^(d+1-l)
        if 0 <= l <= d and 2*l <= i0 <= 2*d:
            f_temp = p^(d-l)
        if l == 0 and 0 <= i0 <= 2*d:
            ft = x0^i0
            ft = f_temp*ft.change_ring(ZZ)
            ff.append(ft)
        if l == 1 and 0 <= i0 <= 1:
            for exps in Exp_res:
                if sum(exps) == l:
                    ft = x0^i0*prod(map(pow,y,exps))
                    ft = f_temp*ft.change_ring(ZZ)
                    ff.append(ft)
        if 1 <= l <= d  and 2*l <= i0 <= 2*d:
            for exps in Exp_res:
                if sum(exps) == l:
                    ft = x0^(i0-2*l)*prod(map(pow,Fs,exps))
                    ft = f_temp*ft.change_ring(ZZ)
#                     print(,l,i0)
                    ff.append(ft)
        if 2 <= l <= d  and 0 <= i0 <= (2*l-1):
            for exps in Exp_res:
                if sum(exps) == l:
                    ft = 0
                    js = Get_js(exps)
                    M = get_M(js)
                    M = M.change_ring(Zmod(p^(l-1)))
                    W = M.inverse()
                    W = W.change_ring(ZZ)
                    for u in range(1,l+1):
                        for v in range(2):
                            ft += W[i0,u+l*v-1] * x0^v * Get_prodF(u,js,y)
                    ft = f_temp*(ft.change_ring(ZZ) %p^(l-1))
                    ff.append(ft)
def Get_H(u,js):
    ttf = y[js[u-1]-1]
    for i in range(len(js)):
        if i!=(u-1):
            ttf *= Fs[js[i]-1]
    return ttf
def Get_J(u,js):
    ttf = Cs[js[u-1]-1]
    for i in range(len(js)):
        if i!=(u-1):
            ttf *= Fs[js[i]-1]
    return ttf
def Get_K(u,js):
    ttf = Bs[js[u-1]-1]-Cs[js[u-1]-1]*Es[js[u-1]-1]
    for i in range(len(js)):
        if i!=(u-1):
            ttf *= Fs[js[i]-1]
    return ttf

for i0 in range(t+1):
    l = d+1
#     bounds = [(2^86)]*6
    for exps in Exp_res:
        if sum(exps) == l:
#             print(exps)
            ft = 0
            js = Get_js(exps)
#             print(js)
            M = get_M(js)
            M = M.change_ring(Zmod(p^(l-1)))
            W = M.inverse()
            W = W.change_ring(ZZ)
            H,J,K = 0,0,0
            for u in range(1,l+1):
                for v in range(2):
                    H += W[i0,u+l*v-1] * x0^v * Get_H(u,js)
            for u in range(1,l+1):
                for v in range(2):
                    J +=W[i0,u+l*v-1] * x0^v * Get_J(u,js)
            for u in range(1,l+1):
                K += W[i0,u+l-1] * Get_K(u,js)
#             print(H(*([e0]+EE)) %p^3,J(*([e0]+EE)) %p^3,K(*([e0]+EE)) %p^3)
            ft = (H+J+K) %p^d
            ff.append(ft)

res = LLL_mononimals(ff,[2^(256-192)]*6)
e0 = res[0]
gx = h0 + 2^192*e0
print(gx)



####################################################################################### part2 AGCD
q = 11091427946088586538326341642081147908870478369361079372527019919422720334995105276694411660643624940624081943057158631573866470376362760554084973766546671
p = 7164778143059850549407362450312125862993617607522974512258134374430678370277239436047396839637741848829691805270124657225690426144253093636119389335193487
e = gx
e = next_prime(e)
d = inverse(e,(p-1)*(q-1))
hint = pow(hint2,d,p*q)

################################################ gen data
m = 1
rho = 50
N = hint
a = ["pad"] + [hint1]

def attack():
    ################################################ params
    t,k = 30,10
    R = 2^rho
    indices = []
    for i in product([i for i in range(t+1)] , repeat=m):
        if(sum(list(i)) <= t):
            indices.append(["pad"] + list(i))


    ################################################ attack
    PR = ZZ[tuple(f"X{i}" for i in range(m))]
    X = ["pad"] + list(PR.gens())
    poly = []
    monomials=set()
    for i in indices:
        f = 1
        for ij in range(1,len(i)):
            f *= (X[ij] - a[ij])^i[ij]
        l = max(k-sum(i[1:]),0)
        f *= N^l
        poly.append(f)
        for mono in f.monomials():
            monomials.add(mono)


    ################################################# LLL and resultant to find roots
    L = Matrix(ZZ,len(poly),len(monomials))
    monomials = sorted(monomials)
    for row,shift in enumerate(poly):
        for col,monomial in enumerate(monomials):
            L[row,col] = shift.monomial_coefficient(monomial)*monomial(*([R]*m))


    res = L.LLL()
    vec1 = res[0]

    h = 0
    for idx,monomial in enumerate(monomials):
        h += (vec1[idx] // monomial(*([R]*m))) * monomial
    h = h.change_ring(ZZ)
    res1 = h.monic().roots()

    if(res1 != []):
        return res1

print(attack())
r = int(attack()[0][0])
k = GCD(hint1,hint-r)
#k = 321747659653024134968440983624672831433  #just yafu
print(k)

from hashlib import sha256
secret = sha256(str(k).encode()).hexdigest()[:32]
print("NepCTF{" + secret + "}")


#NepCTF{bc56ce053f45647508a94f495d7fb16f}

bard

题目描述：

Do you like poetry? If you can understand my poetry, I'll give you what you want!

题目：

from Crypto.Util.number import *
from Crypto.Util.Padding import pad
from pwn import xor
import os
from hashlib import *
from random import *

# Hint: SEED is a short phrase composed of printable characters.
SEED = ?
FLAG = b"NepCTF{" + md5(SEED).hexdigest().encode() + b"}"
EFFECTIVE_ROW = 6


class gen_LCG:
    lcg_a = getPrime(256)
    lcg_b = getPrime(256)
    lcg_p = getPrime(256)

    def __init__(self, lcg_seed):
        self.state = lcg_seed

    def next(self):
        self.state = (self.state * self.lcg_a + self.lcg_b) % self.lcg_p
        return self.state


def get_secret():
    with open("secret.txt", "r") as file:
        secret = [line.strip().encode() for line in file if line.strip()]
    return secret


def gen_ezprime(x):
    while 1:
        p = getPrime(x)
        if isPrime(p // 2):
            break
    return p


def encrypt(secret: list, nums: list):
    m = nums[-randint(10, 20)]
    n = gen_ezprime(260)

    u = os.urandom(32)
    V = (
        [nums[-i] for i in range(1, 3)]
        + [getrandbits(256)]
        + [nums[-j] for j in range(3, 5)]
        + [getrandbits(256)]
    )
    S = [
        int((v * m + bytes_to_long(xor(pad(R, 32)[::-1], u))) % (n - 1))
        for v, R in zip(V, secret)
    ]

    return S, V, n


if __name__ == "__main__":
    secret = get_secret()
    seed = bytes_to_long(SEED)
    lcg = gen_LCG(seed)

    nums = [lcg.next() for _ in range(len(bin(seed)[2:]))]
    S, V, n = encrypt(secret[:EFFECTIVE_ROW], nums)

    print("S =", S)
    print("V =", V)
    print("n =", n)


'''
S = [928793047459267358924804875366212621786968786279243654351646169069161477249047, 491304970278362752479695846381706615539198720144696200170026767641848031231651, 514691510485769847714107534528547472726074415167389606708976762616359610201884, 583316942762322781104571877950487576782419258930107975643467565860957333536646, 634063289592889225648808740745714401588395681407222060304565718149215218115165, 413138909071651695616514922234580608044888221033679197648293164288990896791137]
V = [60973044572559210771075312766213601999489350657872948067682466650802806244594, 74440454568935738324039622889455066795046310110499562562685948913498998588128, 16522902311286065998128377067214609251139861887925252094274904565189173305971, 51650184431537099680082851583510542229373637927388945176247149041860030192399, 17686531553919237689990021678609641031724628142525712248187449572744576324522, 14711325564133495819039523654116859871177893131222463045449067761200499313844]
n = 956199991395839947373337051427365524140130846846315248997021735263168625537543
'''

secret.txt：

In every step, pave,
In every air, thrive,
Every challenge, courage saves, our mettle we brave.

In every day, quest,
In every night, gaze,
Every silence, love resounds, our souls abound.

--an anonymous bard,
  "Steps and Silences"


# Bard thinks equations like 'a * x + b' are very cool, right?

题目加密数据过程如下：

• 先读取secret.txt，并取其前六行(除空行)用于encrypt
• flag是SEED，用它初始化LCG的seed，并next其比特长度次，所有结果存在nums中
• 进行encrypt加密并给出数据

而encrypt的过程为：

• 随机取nums中的一个数字当作m，其索引在[-10,20]之间

• 随机生成一个260bit、2p+1类型的安全素数n，并随机生成32字节串u

• 取nums的最后四个值，并在中间插入两个256bit的随机数，这个长为6的数组是V

• 按如下方式计算S(其中Ri就是secret对应行代表的字节串)：

  ti = pad(Ri,32)[::-1]

  $$s_i = v_im + (t_i \oplus u) \quad(mod\;n-1)$$

• 最后给出V、S和n

由于flag就是SEED，所以目标是还原LCG的所有参数a、b、p，从而逆推出SEED来。

由于V中有LCG的四个状态，所以只需要再找一个就可以完全恢复LCG，而要找的这一个很显然就是m了。而要恢复m显然只能从S下手，回顾以下S的计算过程是：

$$s_i = v_im + (t_i \oplus u) \quad(mod\;n-1)$$

虽然n是260bit，剩下的vi、m、ti、u都是256bit，似乎可以格一格，但是数据只有六组，太不够了，所以要找更小的量。

而更小的量就直接来自secret的每一行的关系，不妨把secret用于encrypt的前六行pad到32作一下观察：

b'In every step, pave,\x0c\x0c\x0c\x0c\x0c\x0c\x0c\x0c\x0c\x0c\x0c\x0c'

b'In every air, thrive,\x0b\x0b\x0b\x0b\x0b\x0b\x0b\x0b\x0b\x0b\x0b'

b'Every challenge, courage saves, our mettle we brave.\x0c\x0c\x0c\x0c\x0c\x0c\x0c\x0c\x0c\x0c\x0c\x0c'

b'In every day, quest,\x0c\x0c\x0c\x0c\x0c\x0c\x0c\x0c\x0c\x0c\x0c\x0c'

b'In every night, gaze,\x0b\x0b\x0b\x0b\x0b\x0b\x0b\x0b\x0b\x0b\x0b'

b'Every silence, love resounds, our souls abound.\x11\x11\x11\x11\x11\x11\x11\x11\x11\x11\x11\x11\x11\x11\x11\x11\x11'

可以看出，1、4和2、5两组值有很大的重合部分，因为他们的前后缀都一样。这里以1、4两组为例，它们对应的si就是：

$$s_1 = v_1m + (h + 2^{72}\delta_1 + l) \quad(mod\;n-1)$$ $$s_4 = v_4m + (h + 2^{72}\delta_4 + l) \quad(mod\;n-1)$$

虽然h、l由于u的存在，并不知道他们具体的值，但是他们对于s1和s4来说一样，因此两式作差就得到：

$$s_1 - s_4 = m(v_1-v_4) + 2^{72}(\delta_1-\delta_4) \quad (mod\;n-1)$$

同理，s2和s5也有：

$$s_2 - s_5 = m(v_2-v_5) + 2^{72}(\delta_2-\delta_5) \quad (mod\;n-1)$$

两式结合把m消掉之后，式子就只剩下两个差值代表的小量了，之后用格或者二元copper规约出这两个小差值，就可以计算出m来了。

得到m之后，结合V里的四个值就有了LCG的五个状态，只是m位置不太确定，所以简单爆破一下就可以恢复LCG的全部参数，之后就能逆推SEED了。

exp：

from Crypto.Util.number import *
from hashlib import *

S = [928793047459267358924804875366212621786968786279243654351646169069161477249047, 491304970278362752479695846381706615539198720144696200170026767641848031231651, 514691510485769847714107534528547472726074415167389606708976762616359610201884, 583316942762322781104571877950487576782419258930107975643467565860957333536646, 634063289592889225648808740745714401588395681407222060304565718149215218115165, 413138909071651695616514922234580608044888221033679197648293164288990896791137]
V = [60973044572559210771075312766213601999489350657872948067682466650802806244594, 74440454568935738324039622889455066795046310110499562562685948913498998588128, 16522902311286065998128377067214609251139861887925252094274904565189173305971, 51650184431537099680082851583510542229373637927388945176247149041860030192399, 17686531553919237689990021678609641031724628142525712248187449572744576324522, 14711325564133495819039523654116859871177893131222463045449067761200499313844]
n = 956199991395839947373337051427365524140130846846315248997021735263168625537543
secret = [b'In every step, pave,', b'In every air, thrive,', b'Every challenge, courage saves, our mettle we brave.', b'In every day, quest,', b'In every night, gaze,', b'Every silence, love resounds, our souls abound.', b'--an anonymous bard,', b'"Steps and Silences"', b"# Bard thinks equations like 'a * x + b' are very cool, right?"]
secret = secret[:6]

############################################ part1 get m
PR.<m,delta1,delta2> = PolynomialRing(Zmod(n-1))
f1 = (V[0]-V[3])*m + 2^72*delta1 - (S[0]-S[3])
f2 = (V[1]-V[4])*m + 2^72*delta2 - (S[1]-S[4])
h = f1.sylvester_matrix(f2, m).det()
#print(h)
#234374922288562089477448209467836016757285531217448072527666487179544974507836*delta1 + 175762328347324857078929323306800184560231396589437768457927485076657738747718*delta2 + 617555474892856652652396170657538869359645164600808689783650329883813246780522

L = Matrix(ZZ,[
    [1,0,0,234374922288562089477448209467836016757285531217448072527666487179544974507836],
    [0,1,0,175762328347324857078929323306800184560231396589437768457927485076657738747718],
    [0,0,2^80,617555474892856652652396170657538869359645164600808689783650329883813246780522],
    [0,0,0,n-1]
])

L[:,-1:] *= n
L = L.LLL()
res = L[0]
delta1 = -res[0]
delta2 = -res[1]
m = ((S[0]-S[3] - 2^72*delta1) * inverse(V[0]-V[3],n-1)) % (n-1)
assert ((V[1]-V[4])*m + 2^72*delta2 - (S[1]-S[4])) % (n-1) == 0

############################################ part2 recover LCG
x4,x3,x2,x1 = V[0],V[1],V[3],V[4]
PR.<a,b> = PolynomialRing(ZZ)
f1 = a*x1+b-x2
f2 = a*x2+b-x3
f3 = a*x3+b-x4

def brute(x,times):
    for i in range(times):
        x = a*x + b
    return x

if(0):
    for i in range(1,200):
        f4 = brute(a*m+b,i)-x1
        res = Ideal([f1,f2,f3,f4]).groebner_basis()
        if(res != [1]):
            print(i,res)
#15 [a + 43557028724851631210594686957113259564335494047238542191770913094495789566207, b + 73995412223860242605096134970302967010396912758007118282864231938356196696313, 75036014223311934744315490492596796700592810688843048058467742348733161100097]

p = 75036014223311934744315490492596796700592810688843048058467742348733161100097
b = p-73995412223860242605096134970302967010396912758007118282864231938356196696313
a = p-43557028724851631210594686957113259564335494047238542191770913094495789566207
x = x4
for i in range(200):
    x = int((x - b) * inverse(a,p) % p)
    try:
        long_to_bytes(x).decode()
        print(long_to_bytes(x), b"NepCTF{" + md5(long_to_bytes(x)).hexdigest().encode() + b"}")
    except:
        pass


#b'l3g3nd_b4rd' b'NepCTF{9bce7170d051f9296148f8af38b9ddad}'