羊城杯2024复现

Th_Curve

$$x_{3}= \frac{x_{1}-y_{1}^{2}x_{2}y_{2}}{2x_{1}y_{1}x_{2}^{2}-y_{2}}\pmod{p}$$ $$y_{3}=\frac{y_{1}y_{2}^{2}-2x_{1}^{2}x_{2}}{2x_{1}y_{1}x_{2}^{2}-y_{2}}\pmod{p}$$

Tate-Halberstam 曲线：$a*x^{3}+y^{3}+1 = dxy$

$$x = \frac{X}{Z},y=\frac{Y}{Z}$$

映射：$aX^{3}+Y^{3}+Z^{3}=dXYZ$

#sage
G = (8879931045098533901543131944615620692971716807984752065, 4106024239449946134453673742202491320614591684229547464)
Q = (6784278627340957151283066249316785477882888190582875173, 6078603759966354224428976716568980670702790051879661797)
p = 10297529403524403127640670200603184608844065065952536889
a = 2

d = int(gmpy2.invert(G[0]*G[1],p))*(2*G[0] ^ 3 + G[1] ^ 3+1)%p
Zp = Zmod(p)
R.<xx,yy,zz> = Zp[]
cubic = a * xx^3 + yy^3 + zz^3 - d * xx * yy * zz
E = EllipticCurve_from_cubic(cubic, morphism=True)

GG = E(G)
QQ = E(Q)
dd = QQ.log(GG)
print(b'DASCTF{' + long_to_bytes(dd) + b'}')
"""
b'DASCTF{e@sy_cuRvL_c0o!}'

babyCurve

curve2: $y^{2}= x^{3}-cx +b$
直接把P,Q代入计算得c，b

G = (584273268656071313022845392380, 105970580903682721429154563816, 1)
P = (401055814681171318348566474726, 293186309252428491012795616690, 1)

PR.<c,b> = PolynomialRing(Zmod(p))
f1 = G[0]^3 - c * G[0] + b - G[1]^2
f2 = P[0]^3 - c * P[0] + b - P[1]^2
res = Ideal([f1,f2]).grobner_basis()
print(res)
"""
[c + 770311352827455849356512448252, b + 770311352827455849356512448189]
"""
c = -770311352827455849356512448252
b = -770311352827455849356512448189

p = 770311352827455849356512448287
E = EllipticCurve(GF(p),[-c,b])
E2 = EllipticCurve(GF(p^2, 'y'),[-c,b])

P2 = E2(G)
Q2 = E2(P)
n = E.order()
R = E2.random_element()
u = P2.weil_pairing(R,n)
v = Q2.weil_pairing(R,n)
key = v.log(u)
#key = 2951856998192356

iv = bytes.fromhex('bae1b42f174443d009c8d3a1576f07d6')
cipher = bytes.fromhex('ff34da7a65854ed75342fd4ad178bf577bd622df9850a24fd63e1da557b4b8a4')
key = hashlib.sha256(str(key).encode()).digest()[:16]
mc = AES.new(key,AES.MODE_CBC,iv)
flag = mc.decrypt(cipher)
print(flag)
"""
b'DASCTF{THe_C0rv!_1s_Aw3s0me@!!}\x01'

布什戈门，第一条曲线原来没用吗</small>
curve1 是 Jacobi quartics（Jacobi 四次曲线）: $y^2=x^4+2ax^{2}+1$

$$\frac{x_{1}y_{2}+y_{1}x_{2}}{1-dx_{1}^{2}x_{2}^{2}}\pmod{p}$$ $$\frac{(y_{1}y_{2}+2ax_{1}x_{2})(1+dx_{1}^{2}x_{2}^{2})+2dx_{1}x_{2}(x_{1}^{2}+x_{2}^{2})}{(1-dx_{1}^{2}x_{2}^{2})^{2}}\pmod{p}$$

RSA_loss

$m = newm+k*n$

方法一：爆破

——来自鸡块大佬

这道题m大于newm太多，不能直接爆破，所以需要去缩减flag的长度，让需要计算的剩余部分小于n
先爆破flag的长度，用上flag的头尾拆成a,b,和中间的t(长度为l)

$$(2^{8})^{l+1}a+2^{8}t+b = newm\pmod{n}$$

即：

$$t = 2^{-8}(newm-b-(2^{8})^{l+1}a)\pmod{n}$$

这样需要t小于n才行，尝试后发现没有全是可见字符的t，所以把t拆开，前几个字符爆破（题目中选择3个），后面的用来求解

from Crypto.Util.number import *
import string
from itertools import *
p = 898278915648707936019913202333
q = 814090608763917394723955024893
n = q*p
newm = bytes_to_long(b'X\xee\x1ey\x88\x01dX\xf6i\x91\x80h\xf4\x1f!\xa7"\x0c\x9a\x06\xc8\x06\x81\x15')
  
t = string.digits+string.ascii_letters+"_"
k = 3
for i in product(t,repeat = k):
    ff = bytes_to_long(b'DASCTF{'+"".join(i).encode()+b'\x00'*25+b'}')
    try:
        flag = "".join(i) + long_to_bytes((newm-ff)*inverse(2**8,n)%n).decode()
        if (all(i in t for i in flag)):
            print("DASCTF{"+flag+"}")
    except:
        pass
"""
DASCTF{o0p5_m3ssaGe_to0_b1g_nv93nd0}

方法二：构造格

——来自博客

[羊城杯 2024] Crypto_2024年羊城杯-CSDN博客
怎么感觉gao一gao碰碰运气的感觉（）

TheoremPlus

首先费马质数分解得到p和q
接着找e，从题目中可以得知e为自定义的函数输入703440151的结果的绝对值，而函数则是输出所有小于输入结果的数$(x-1)!\pmod{x}$的和
阶乘，有威尔逊定理可知当p为素数时，$(p-1)!=-1\pmod{p}$
而合数则有除4以外$(p-1)!=0\pmod{p}$
简单证明：
若合数p为完全平方数，大于4的完全平方数$p>2\sqrt{p}$，因此有$2\sqrt{p}\sqrt{p}=0\pmod{p}$
若合数p不为完全平方数，显然有$k_{1},k_{2}<p$使$p = k_{1}k_{2}$，因此有$k_{1}k_{2}=0\pmod{p}$
而$(4-1)!mod{4}=2$

• 使用函数prime_pi()得到不大于实数 x 的素数的个数

#sage
import gmpy2
from Crypto.Util.number import *

n = 18770575776346636857117989716700159556553308603827318013591587255198383129370907809760732011993542700529211200756354110539398800399971400004000898098091275284235225898698802555566416862975758535452624647017057286675078425814784682675012671384340267087604803050995107534481069279281213277371234272710195280647747033302773076094600917583038429969629948198841325080329081838681126456119415461246986745162687569680825296434756908111148165787768172000131704615314046005916223370429567142992192702888820837032850104701948658736010527261246199512595520995042205818856177310544178940343722756848658912946025299687434514029951
c = 2587907790257921446754254335909686808394701314827194535473852919883847207482301560195700622542784316421967768148156146355099210400053281966782598551680260513547233270646414440776109941248869185612357797869860293880114609649325409637239631730174236109860697072051436591823617268725493768867776466173052640366393488873505207198770497373345116165334779381031712832136682178364090547875479645094274237460342318587832274304777193468833278816459344132231018703578274192000016560653148923056635076144189403004763127515475672112627790796376564776321840115465990308933303392198690356639928538984862967102082126458529748355566

tmp = gmpy2.iroot(n,2)[0]
q = gmpy2.next_prime(tmp)
p = n//q
phi = (p - 1) * (q - 1)

e = abs(-prime_pi(703440151)+2)
d = gmpy2.invert(e,phi)
print(long_to_bytes(pow(c,d,n)))

"""
b'DASCTF{Ot2N63D_n8L6kJt_f40V61m_zS1O8L7}'

---

参考鸡块大佬的blog复现