2024羊城杯
2024羊城杯，这次学到了很多新东西，但是先知社区发晚了，就放这里了
TH_curve
题目
from Crypto.Util.number import *
from secret import flag
def add_THcurve(P, Q):
if P == (0, 0):
return Q
if Q == (0, 0):
return P
x1, y1 = P
x2, y2 = Q
x3 = (x1 - y1 ** 2 * x2 * y2) * pow(a * x1 * y1 * x2 ** 2 - y2, -1, p) % p
y3 = (y1 * y2 ** 2 - a * x1 ** 2 * x2) * pow(a * x1 * y1 * x2 ** 2 - y2, -1, p) % p
return x3, y3
def mul_THcurve(n, P):
R = (0, 0)
while n > 0:
if n % 2 == 1:
R = add_THcurve(R, P)
P = add_THcurve(P, P)
n = n // 2
return R
p = 10297529403524403127640670200603184608844065065952536889
a = 2
G = (8879931045098533901543131944615620692971716807984752065, 4106024239449946134453673742202491320614591684229547464)
FLAG = flag.lstrip(b'DASCTF{').rstrip(b'}')
assert len(FLAG) == 15
m = bytes_to_long(FLAG)
assert m < p
Q = mul_THcurve(m, G)
print("Q =", Q)
# Q = (6784278627340957151283066249316785477882888190582875173, 6078603759966354224428976716568980670702790051879661797)
分析
注意到
def add_THcurve(P, Q):
if P == (0, 0):
return Q
if Q == (0, 0):
return P
x1, y1 = P
x2, y2 = Q
x3 = (x1 - y1 ** 2 * x2 * y2) * pow(a * x1 * y1 * x2 ** 2 - y2, -1, p) % p
y3 = (y1 * y2 ** 2 - a * x1 ** 2 * x2) * pow(a * x1 * y1 * x2 ** 2 - y2, -1, p) % p
return x3, y3
符合https://www.hyperelliptic.org/EFD/g1p/auto-twistedhessian.html 的定义
而且题目确实叫th_curve
得到式子如下：
ax3+y3+1=dxy
a = 2已知，需要求的是d
2x3+y3+1=dxy
把d带进去就是d = (2x3+y3+1)/(xy)
所以按照上面的文章里面所说的进行换元
x’=X/Z
y’=Y/Z
得到
ax’^3+y’^3+z’^3=dx’*y’*z'
这样构造出了齐次式子之后就可以构造椭圆曲线了
构造完成之后就是ecdlp 听佬们说还有一种解法是把这个th_curve转换成Weierstrass型曲线（就是最常见的y^2 = x^3 + a*x + b）然后后面就一样了，有兴趣的师傅可以尝试一下
exp
from Crypto.Util.number import *
p = 10297529403524403127640670200603184608844065065952536889
a = 2
P = (8879931045098533901543131944615620692971716807984752065, 4106024239449946134453673742202491320614591684229547464)
Q = (6784278627340957151283066249316785477882888190582875173, 6078603759966354224428976716568980670702790051879661797)
d = (a * Q[0] ** 3 + Q[1] ** 3 + 1) * inverse(Q[0] * Q[1], p) % p
R.<x,y,z> = Zmod(p)[]
cubic = 2 * x^3 + y^3 + z^3 - d*x*y*z
E = EllipticCurve_from_cubic(cubic,morphism=True)
P = E(P)
Q = E(Q)
P_ord = P.order()
def Pohlig_Hellman(n,P,Q):
factors, exponents = zip(*factor(n))
primes = [factors[i] ^ exponents[i] for i in range(len(factors))][:-1]
print(primes)
dlogs = []
for fac in primes:
t = int(int(P.order()) // int(fac))
dlog = discrete_log(t*Q,t*P,operation="+")
dlogs += [dlog]
print("factor: "+str(fac)+", Discrete Log: "+str(dlog)) #calculates discrete logarithm for each prime order
num2 = crt(dlogs,primes)
return num2
num2 = Pohlig_Hellman(P_ord,P,Q)
print(long_to_bytes(num2))
babycruve
题目
#!/usr/bin/env python
# -*- coding: UTF-8 -*-
import os
import hashlib
from sage.all import *
from Crypto.Cipher import AES
from Crypto.Util.Padding import pad
from secret import c, b, key, FLAG
def add_curve(P, Q, K):
a, d, p = K
if P == (0, 0):
return Q
if Q == (0, 0):
return P
x1, y1 = P
x2, y2 = Q
x3 = (x1 * y2 + y1 * x2) * pow(1 - d * x1 ** 2 * x2 ** 2, -1, p) % p
y3 = ((y1 * y2 + 2 * a * x1 * x2) * (1 + d * x1 ** 2 * x2 ** 2) + 2 * d * x1 * x2 * (x1 ** 2 + x2 ** 2)) * pow(
(1 - d * x1 ** 2 * x2 ** 2) ** 2, -1, p) % p
return x3, y3
def mul_curve(n, P, K):
R = (0, 0)
while n > 0:
if n % 2 == 1:
R = add_curve(R, P, K)
P = add_curve(P, P, K)
n = n // 2
return R
def AES_encrypt(k):
key = hashlib.sha256(str(k).encode()).digest()[:16]
iv = os.urandom(16)
cipher = AES.new(key, AES.MODE_CBC, iv)
cipher = cipher.encrypt(pad(FLAG, 16))
data = {}
data["iv"] = iv.hex()
data["cipher"] = cipher.hex()
return data
a = 46
d = 20
p1 = 826100030683243954408990060837
K1 = (a, d, p1)
G1 = (560766116033078013304693968735, 756416322956623525864568772142)
P1 = mul_curve(c, G1, K1)
Q1 = mul_curve(b, G1, K1)
print("P1 =", P1)
print("Q1 =", Q1)
# P1 = (528578510004630596855654721810, 639541632629313772609548040620)
# Q1 = (819520958411405887240280598475, 76906957256966244725924513645)
p = 770311352827455849356512448287
E = EllipticCurve(GF(p), [-c, b])
G = E.gens()[0]
P = G * key
data = AES_encrypt(key)
print("G =", G)
print("P =", P)
print("data =",data)
# G = (584273268656071313022845392380 : 105970580903682721429154563816 : 1)
# P = (401055814681171318348566474726 : 293186309252428491012795616690 : 1)
# data = {'iv': 'bae1b42f174443d009c8d3a1576f07d6', 'cipher': 'ff34da7a65854ed75342fd4ad178bf577bd622df9850a24fd63e1da557b4b8a4'}
分析
爆破一下得到b,c然后就是常规的dlp
exp
爆破b,c
a = 46
d = 20
p1 = 826100030683243954408990060837
K1 = (a, d, p1)
G1 = (560766116033078013304693968735, 756416322956623525864568772142)
P1 = (528578510004630596855654721810, 639541632629313772609548040620)
Q1 = (819520958411405887240280598475, 76906957256966244725924513645)
def add_curve(P, Q, K):
a, d, p = K
if P == (0, 0):
return Q
if Q == (0, 0):
return P
x1, y1 = P
x2, y2 = Q
x3 = (x1 * y2 + y1 * x2) * pow(1 - d * x1 ** 2 * x2 ** 2, -1, p) % p
y3 = ((y1 * y2 + 2 * a * x1 * x2) * (1 + d * x1 ** 2 * x2 ** 2) + 2 * d * x1 * x2 * (x1 ** 2 + x2 ** 2)) * pow(
(1 - d * x1 ** 2 * x2 ** 2) ** 2, -1, p) % p
return x3, y3
def mul_curve(n, P, K):
R = (0, 0)
while n > 0:
if n % 2 == 1:
R = add_curve(R, P, K)
P = add_curve(P, P, K)
n = n // 2
return R
def solve_for_scalars(P1, Q1, G1, K1):
for c in range(1, 1000000):
if mul_curve(c, G1, K1) == P1:
for b in range(1, 1000000):
if mul_curve(b, G1, K1) == Q1:
return b, c
return None, None
b, c = solve_for_scalars(P1, Q1, G1, K1)
print(f"b = {b}, c = {c}")
求出k
p = 770311352827455849356512448287
E = EllipticCurve(GF(p), [-35, 98])
G = E(584273268656071313022845392380, 105970580903682721429154563816)
P = E(401055814681171318348566474726, 293186309252428491012795616690)
k = G.discrete_log(P)
print(k)
aes
import hashlib
import os
from Crypto.Cipher import AES
from Crypto.Util.Padding import pad, unpad
iv = 'bae1b42f174443d009c8d3a1576f07d6'
cipher = 'ff34da7a65854ed75342fd4ad178bf577bd622df9850a24fd63e1da557b4b8a4'
key = 2951856998192356
def AES_encrypt(k):
key = hashlib.sha256(str(k).encode()).digest()[:16]
iv = os.urandom(16)
cipher = AES.new(key, AES.MODE_CBC, iv)
encrypted = cipher.encrypt(pad(FLAG, AES.block_size))
data = {
"iv": iv.hex(),
"cipher": encrypted.hex()
}
return data
def AES_decrypt(k, iv_hex, cipher_hex):
key = hashlib.sha256(str(k).encode()).digest()[:16]
iv = bytes.fromhex(iv_hex)
cipher = bytes.fromhex(cipher_hex)
aes = AES.new(key, AES.MODE_CBC, iv)
decrypted_padded = aes.decrypt(cipher)
print(decrypted_padded)
try:
decrypted = unpad(decrypted_padded, 16)
except ValueError as e:
print(f"Padding error: {e}")
return None
return decrypted
decrypted_message = AES_decrypt(key, iv, cipher)
if decrypted_message:
print("Decrypted message:", decrypted_message.decode('UTF-8'))
else:
print("Decryption failed.")
RSAloss
题目
from Crypto.Util.number import *
from gmpy2 import *
p = getPrime(100)
q = getPrime(100)
n = p * q
e = 65537
message = b""
m = bytes_to_long(message)
c = pow(m, e, n)
print(f'c = {c}')
print(f'p = {p}')
print(f'q = {q}')
d = invert(e,(p-1)*(q-1))
newm = pow(c, d, n)
print(long_to_bytes(newm))
# c = 356435791209686635044593929546092486613929446770721636839137
# p = 898278915648707936019913202333
# q = 814090608763917394723955024893
# newm = b'X\xee\x1ey\x88\x01dX\xf6i\x91\x80h\xf4\x1f!\xa7"\x0c\x9a\x06\xc8\x06\x81\x15'
分析
看到newm时第一时间想到了是m < n的情形，然后尝试爆破了一下newm+k*n没出来
然后现在是复现的呜呜呜
其实这个格子和背包密码那个格子基本一样，参考一下就好了
注：以下 分析 部分的代码均为latex，请自行找个latex编辑器查看
设 pre = b’DASCTF{’,suf = b’}' newm = c = 256 ^{(le−7)}∗pre + 256∗m_0 + suf
意识到这个题目满足以下式子
latex
m_0 = {\textstyle \sum_{i = 1}^{le-7-1-1}} 256^i *s_i (mod \quad p)
构造如下一个格子
latex
M0 =
\begin{pmatrix}
1 & & & & & 256^0 \\
& 1 & & & & 256^1 \\
& & \ddots & & & \vdots \\
& & & 1 & & 256^{le-9} \\
& & & & 1 & -m_0 \\
& & & & & n \\
\end{pmatrix}
然后有如下的式子可以获得我们的目标向量，由于长度le未知所以我们需要进行爆破(爆破这个长度的范围)
latex
(s_0,s_1,\dots ,s_{le-9},1,k) * M = (s_0,s_1,\dots ,s_{le-9},1,0)
这样并没有成功爆破出正确答案，所以考虑进行优化 注意到s_i的范围应该是[48,128],于是令r_i = s_i - 48 对应的修改如下
latex
m_0 = {\textstyle \sum_{i = 1}^{le-7-1-1}} 256^i *(r_i + 48) (mod \quad p)
latex
M1 =
\begin{pmatrix}
1 & & & & & 256^0 \\
& 1 & & & & 256^1 \\
& & \ddots & & & \vdots \\
& & & 1 & & 256^{le-9} \\
& & & & 1 & -(m_0-{\textstyle \sum_{i = 1}^{le-7-1-1}} 256^i *40) \\
& & & & & n \\
\end{pmatrix}
这样仍然没有爆破出来于是进行了第二次优化 注意到r_i的范围应该是[0,80] 令t_i = r_i - 40 则t_i 范围[-40,40]
latex
m_0 = {\textstyle \sum_{i = 1}^{le-7-1-1}} 256^i *(t_i + 48 + 40) (mod \quad p)
latex
M2 =
\begin{pmatrix}
1 & & & & & 256^0 \\
& 1 & & & & 256^1 \\
& & \ddots & & & \vdots \\
& & & 1 & & 256^{le-9} \\
& & & & 1 & -(m_0-{\textstyle \sum_{i = 1}^{le-7-1-1}} 256^i * (40 + 48)) \\
& & & & & n \\
\end{pmatrix}
这样就求解成功了，这个优化是真的长知识了
exp
是二次优化之后的哈
from Crypto.Util.number import *
p1 = 898278915648707936019913202333
q1 = 814090608763917394723955024893
newm = bytes_to_long(b'X\xee\x1ey\x88\x01dX\xf6i\x91\x80h\xf4\x1f!\xa7"\x0c\x9a\x06\xc8\x06\x81\x15')
p = p1 * q1
c = newm
prefix = b"DASCTF{"
suffix = b"}"
for le in range(33, 40):
length = le - len(prefix) - len(suffix)
#part1 remove prefix and suffix
c -= 256^(len(suffix) + length) * bytes_to_long(prefix)
c -= bytes_to_long(suffix)
c = c * inverse(256,p) % p
L = Matrix(ZZ,length+2,length+2)
for i in range(length):
L[i,i] = 1
L[i,-1] = 256^i
#删除这两行就是M0了
c -= 256^i*48
c -= 256^i*40
#
L[-2,-2] = 1
L[-2,-1] = -c
L[-1,-1] = p
L[:,-1:] *= p
res = L.BKZ()
for i in res[:-1]:
flag0 = "DASCTF{"
flag = ""
if(all(abs(j) <= 40 for j in i[:-2])):
if(i[-2] == 1):
for j in i[:-2][::-1]:
flag += chr(48 + 40 + j)
elif i[-2] == -1:
for j in i[:-2][::-1]:
flag += chr(48 + 40 - j)
if(flag != ""):
flag += '}'
flag0 += flag
print(flag0)
#print(le)
c = newm
# DASCTF{o0p5_m3ssaGe_to0_b1g_nv93nd0}
TheoremPlus
题目
from Crypto.Util.number import *
from gmpy2 import *
from secret import flag
def decode_e(e):
if e > 1:
mul = 1
for i in range(1, e):
mul *= i
if e - mul % e - 1 == 0:
mulmod = mul % e - e
else:
mulmod = mul % e
return mulmod + decode_e(e - 1)
else:
return 0
q = getPrime(1024)
p = next_prime(q)
n = p * q
phi = (p - 1) * (q - 1)
e = abs(decode_e(703440151))
c = pow(bytes_to_long(flag), e, n)
print('n = {}\n'
'c = {}'.format(n, c))
'''
n =
c =
'''
分析
首先看到这里
def decode_e(e):
if e > 1:
mul = 1
for i in range(1, e):
mul *= i
if e - mul % e - 1 == 0:
mulmod = mul % e - e
else:
mulmod = mul % e
return mulmod + decode_e(e - 1)
else:
return 0
注意到这里有一个e - mul % e ?= 1 的判断 而mul的值是(e-1)! 所以这个式子就符合了威尔逊定理 只要e是素数就为1 否则为0 为0的原因:如果e不是素数那就一定是A1X1+……+AnXn的格式，且这{A1,……,An}{X1,……Xn}都 <= e-1 可以被(e-1)!整除，所以必然为0 也就是说这道题目生成的e就是小于输入的e的素数的个数，使用prime_pi即可得到e,然后进行费马分解就可以得到flag
exp
from Crypto.Util.number import *
from gmpy2 import *
#获取e
'''sage
e = 703440151
a = prime_pi(e)
e = a - 2
#为什么减掉2呢?首先这里面是不包括这个初始e本身的(没错e是素数)，所以-1,其次4也是一个特殊值,再-1
'''
e = 36421873
n = 18770575776346636857117989716700159556553308603827318013591587255198383129370907809760732011993542700529211200756354110539398800399971400004000898098091275284235225898698802555566416862975758535452624647017057286675078425814784682675012671384340267087604803050995107534481069279281213277371234272710195280647747033302773076094600917583038429969629948198841325080329081838681126456119415461246986745162687569680825296434756908111148165787768172000131704615314046005916223370429567142992192702888820837032850104701948658736010527261246199512595520995042205818856177310544178940343722756848658912946025299687434514029951
c = 2587907790257921446754254335909686808394701314827194535473852919883847207482301560195700622542784316421967768148156146355099210400053281966782598551680260513547233270646414440776109941248869185612357797869860293880114609649325409637239631730174236109860697072051436591823617268725493768867776466173052640366393488873505207198770497373345116165334779381031712832136682178364090547875479645094274237460342318587832274304777193468833278816459344132231018703578274192000016560653148923056635076144189403004763127515475672112627790796376564776321840115465990308933303392198690356639928538984862967102082126458529748355566
tmp = gmpy2.iroot(n,2)[0]
p = gmpy2.next_prime(tmp)
q = n//p
print("p =",p)
print("q =",q)
phi = (p-1)*(q-1)
d = invert(e,phi)
m = pow(c,d,n)
print(long_to_bytes(m))
嗯，就这样