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)

题目给出如下运算式子

P(x_1,y_1)\;Q(x_2,y_2)

x_3\equiv (x_1-y_1^2x_2y_2)(2x_1y_1x_2^2-y_2)^{-1}mod\;p

y_3\equiv (y_1y_2^2-2x_1^2x_2)(2x_1y_1x_2^2-y_2)^{-1}mod\;p

自定义了一个曲线上的计算

然后我们知道

Q=mG

这里我们的曲线方程实际是

2x^3+y^3+1\equiv dxy\;mod\;p

我们可以由 $Q\;\;G$ 解出来这里的 $d$

我们做一个换元

x=\frac{X}{Z}\;\;y=\frac{Y}{Z}

可得

2X^3+Y^3+Z^3\equiv dXYZ\;mod\;p

参照鸡块师傅的博客

2023-CryptoCTF-wp-crypto | 糖醋小鸡块的blog (tangcuxiaojikuai.xyz) ↗ Barak中，sage的EllipticCurve_from_cubic方法可以从一个三元多项式方程来衍生出一条标准维尔斯特拉斯椭圆曲线

我们可以由这个多项式衍生出一条标准的维尔斯特拉斯椭圆曲线，并且获得它和原曲线的映射关系，之后就是在这条标准曲线上做ECDLP即可

exp

from Crypto.Util.number import *

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

# Q = G * m
xg, yg = G
xq, yq = Q
d = (2*xg^3 + yg^3 + 1) * pow(xg*yg,-1,p) % p
# dd = (2*xq^3 + yq^3 + 1) * pow(xq*yq,-1,p) % p == d
A = [0,1,-1]
R.<x,y,z> = Zmod(p)[]
cubic = 2*x^3+y^3+z^3 - d*x*y*z
E = EllipticCurve_from_cubic(cubic, A,morphism=True) # 由多项式方程生成一个曲线
Ee = EllipticCurve_from_cubic(cubic, A,morphism=False)

# E包含映射关系
G = E(G)
Q = E(Q)
order = Ee.order()
print(order)
m = G.discrete_log(Q)
print(m)
flag = b"DASCTF{" + long_to_bytes(m) + b"}"
print(flag)
# DASCTF{e@sy_cuRvL_c0o!}

这里我们获得的E是包含映射关系的曲线，而Ee就是正常的维尔斯特拉斯曲线，所以用E进行坐标转化，用Ee来算阶即可，如果这里我们DLP出来的 $m$ 不满足范围的话再考虑加减几个曲线的阶爆破即可

Baby_Curve#

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'}

python

给出了曲线上点加的计算方式

P(x_1,y_1)\;Q(x_2,y_2)

x_3\equiv (x_1y_2+y_1x_2)(1-dx_1^2x_2^2)^{-1}mod\;p

y_3\equiv (y_1y_2+2ax_1x_2)(1+dx_1^2x_2^2)+2dx_1x_2(x_1^2+x_2^2)(1-dx_1^2x_2^2)^{-1}mod\;p

不是常规的椭圆曲线先不管往下看

我们先给出第一组曲线参数 $(a,d,p_1)$ ，以及点 $G_1$ 然后计算

P_1=c\cdot G_1\\Q_1=b\cdot G_1

然后再用 $(-c,b)$ 建立一条标准椭圆曲线，要你解ECDLP

P=k\cdot G

那么我们就考虑爆破求出 $b\;\;c$ 然后直接解AES即可

exp

import os
import hashlib
from sage.all import *
from Crypto.Cipher import AES
from Crypto.Util.Padding import pad
from tqdm import tqdm

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

a = 46
d = 20
p1 = 826100030683243954408990060837
K1 = (a, d, p1)
G1 = (560766116033078013304693968735, 756416322956623525864568772142)
P1 = (528578510004630596855654721810, 639541632629313772609548040620)
Q1 = (819520958411405887240280598475, 76906957256966244725924513645)

# -------------------------------------find b c------------------------------------------

for i in tqdm(range(-100, 100)):
    P2 = mul_curve(i, G1, K1)
    if P2 == P1:
        c = i
        break

for i in tqdm(range(-100, 100)):
    Q2 = mul_curve(i, G1, K1)
    if Q2 == Q1:
        b = i
        break

print(f"b = {b}, c = {c}")
# b = 98, c = 35
# --------------------------------------ECDLP--------------------------------------------

p = 770311352827455849356512448287
E = EllipticCurve(GF(p), [-c, b])
G = (584273268656071313022845392380 , 105970580903682721429154563816)
P = (401055814681171318348566474726 , 293186309252428491012795616690)
G = E(G)
P = E(P)
k = G.discrete_log(P)

print(f"found key = {k}")
# found key = 2951856998192356
# ------------------------------------- AES Decrypt ------------------------------------------


iv = bytes.fromhex('bae1b42f174443d009c8d3a1576f07d6')
ciphertext = bytes.fromhex('ff34da7a65854ed75342fd4ad178bf577bd622df9850a24fd63e1da557b4b8a4')
key = hashlib.sha256(str(k).encode()).digest()[:16]
cipher = AES.new(key, AES.MODE_CBC, iv)
flag = cipher.decrypt(ciphertext)

print(flag)
# DASCTF{THe_C0rv!_1s_Aw3s0me@!!}\x01

python

RSA_Loss#

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
#b'X\xee\x1ey\x88\x01dX\xf6i\x91\x80h\xf4\x1f!\xa7"\x0c\x9a\x06\xc8\x06\x81\x15'

给出了RSA解密的一个小 $m$ ，但不是我们的预期解猜测原因是 $M>n$ 导致的,简单爆破 $M=kn+m$ 不可行

我们仍有

M\equiv m\;mod\; n

这里尝试利用我们的flag的组成规律即

m = b'DASCTF{' + ?????? + b'}'

中间的??????字符串大致20~60字节且是可打印字符可以考虑来爆破，我们知道flag最小的情况是

m0 = b'DASCTF{' + b'\x00' * i + b'}'

最大是

m1 = b'DASCTF{' + b'\xff' * i + b'}'

我们就很自然的能想尝试去进行个爆破

设m的长度是i+8，可以计算出上下界m0~m1，我们又知道必有 $M-m\equiv 0\;mod\; n$ ,然后去找这个解即可

运气很好能直接爆出来，需要大概15分钟

from Crypto.Util.number import *
from tqdm import tqdm
import string

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'
m = bytes_to_long(newm)
n = p * q

# --------------------brute_crack--------------------------------------
for i in tqdm(range(20, 60)):
    flag0 = b"DASCTF{" + b"\x00" * i + b"}"
    flag1 = b"DASCTF{" + b"\xff" * i + b"}"
    m0 = bytes_to_long(flag0)
    m1 = bytes_to_long(flag1)
    k0 = (m0 - m) // n
    k1 = (m1 - m) // n
    
    k = k0
    while k <= k1:                
        pm = k * n + m
        pmes = long_to_bytes(pm)
        if (pmes.startswith(b"DASCTF{") and pmes.endswith(b"}") and all(32 <= byte <= 126 for byte in pmes)): 
            print(f"Found potential flag (i={i}, k={k}): {pmes}")
            break
        if pm % 256 == ord('}'):
            k += 256  
        else:
            k += 1    

# Found potential flag (i=28, k=181321970727117606593880360): b'DASCTF{o0p5_m3ssaGe_to0_b1g_nv93nd0}'

但是这个解法不够优雅我们还能再进行一个优化

前面提到我们有

M\equiv m\;mod\; n

根据bytes_to_long函数的特性我们已知，对于字符串

a_0a_1a_2a_3\cdots a_n

它的转换长整数结果会是

long=a_n256^0+a_{n-1}256^{1}+\cdots+a_{n-i}2^{i}+\cdots+a_22^{n-2}+a_12^{n-1}+a_02^{n}

这里我们的前缀是DASCTF{ 后缀是}，我们都是知道的也就是说我们能得到中间的?????的byts_to_long结果就转化为求它了,设这里是flag

我们可以得到

c^{'}\equiv flag\mod n

flag又可以拆成

f_nf_{n-1}f_{n-2}\cdots f_1f_0

flag=f_l256^{l}+f_{l-1}256^{l-1}+\cdots+f_1256^1+f_0256^0

这不就是个背包格问题吗？

我们要求的 $f$ 的值是ASCII码满足

33<f<125

我们直接令

x+79=f

就得到了一个很小小量的 $x$ 的方程这里 $x$ 满足

|{x}|<46

带入上面已有的方程就是

c^{'}\equiv\sum^{l}_{i=0}(x_i+79)256^{i}\mod n

简单移项

x_{l-1}256^{l-1}+x_{l-2}256^{l-2}+\cdots+x_1256^1+x_0256^0\equiv c^{'}-79\sum^{l-1}_{i=0}256^i\mod n

那就是

x_{l-1}256^{l-1}+x_{l-2}256^{l-2}+\cdots+x_1256^1+x_0256^0= c^{'}-79\sum^{l-1}_{i=0}256^i+k n

做换元

C=c^{'}-79\sum^{l-1}_{i=0}256^i

造格子

(x_0,x_1,\cdots,x_{l-1},k,1)\begin{pmatrix}1 & 0 & \cdots & 0 & 0 & t \cdot 256^0 &0\\ 0 & 1 & \cdots & 0 & 0 & t \cdot 256^1 &0\\ \vdots & \vdots & \ddots & \vdots & \vdots & \vdots&\vdots \\ 0 & 0 & \cdots & 0 & 1 & t \cdot 256^{k-1} &0\\ 0 & 0 & \cdots & 0 & 0 & -t \cdot C' &0\\ 0 & 0 & \cdots & 0 & 0 & t\cdot n&R\end{pmatrix}=(x_0,x_1,\cdots,x_{l-1},0,R)

这里格的大小是

det(M)=tRC^{'}

取 $l+2$ 次根，这里的 $C$ 是200比特左右需要我们的 $t$ 配大一点点取 $2^{200}$ 先试试

调不出来参考N0wayBack师傅的题解造这样的格子效果更好

(x_0,x_1,\cdots,x_{l-1},1,k)\begin{pmatrix}1 & 0 & \cdots & 0 & 0 &0 & t \cdot 256^0 \\ 0 & 1 & \cdots & 0 & 0 &0 & t \cdot 256^1\\ \vdots & \vdots & \ddots & \vdots & \vdots & \vdots&\vdots \\ 0 & 0 & \cdots & 0 & 1 &0 & t \cdot 256^{k-1} \\ 0 & 0 & \cdots & 0 & 0 &1& -t \cdot C' \\ 0 & 0 & \cdots & 0 & 0 &0& n\cdot t\end{pmatrix}=(x_0,x_1,\cdots,x_{l-1},1,0)

exp

from Crypto.Util.number import *
from tqdm import tqdm
import string

c = 356435791209686635044593929546092486613929446770721636839137
p = 898278915648707936019913202333
q = 814090608763917394723955024893
n = p * q
newm = b'X\xee\x1ey\x88\x01dX\xf6i\x91\x80h\xf4\x1f!\xa7"\x0c\x9a\x06\xc8\x06\x81\x15'
c = bytes_to_long(newm)

prefix = b"DASCTF{"
suffix = b"}"
t = n
centerMark = 79

# 遍历flag的长度
for i in tqdm(range(20, 40)):
    length = i
    k = length - len(prefix) - len(suffix)
    pc = c
    # 剥离前后缀的影响
    pc = (pc - bytes_to_long(prefix) * pow(256, k + len(suffix), n) - bytes_to_long(suffix)) % n

    # 获得明文的对应长整数
    cc = pc * inverse_mod(256, n) % n
    sumConstant = sum(256^j for j in range(k))
    C = (cc - centerMark * sumConstant) % n

    # 造格子 规约
    M = matrix(ZZ, k + 2, k + 2)
    for index in range(k):
        M[index, index] = 1
        M[index, k+1] = t * 256^index
    M[k, k] = 1
    M[k, k + 1] = -t * C
    M[k + 1, k + 1] = t * n
    L = M.BKZ()
    # print(L)

    # 筛选可能的答案
    for row in L:
        tag = 1
        for num in row[:-2]:
            if num < 33 - centerMark or num > 126 - centerMark:
                tag = 0
                break
                
        if tag:
            flag = ""
            for num in row[:-2][::-1]:
                flag += chr(num + centerMark)
            if chr(centerMark) * 4  not in flag:
                pflag = b"DASCTF{" + flag.encode() + b"}"    
                print(f"length {i} , flag {pflag}")
    
'''
100%|██████████| 20/20 [00:00<00:00, 323.41it/s]
length 36 , flag b'DASCTF{o0p5_m3ssaGe_to0_b1g_nv93nd0}'
length 37 , flag b'DASCTF{+[ML"sIDDTCQ[,)Av6|LU.?-+rcB|}'
length 38 , flag b'DASCTF{O=V-MT"B=oe2&T@3i}oXKE2:"DfV>n}'
length 39 , flag b'DASCTF{@NmMm^1Pk@J3QXIA5D<OPXFF(HA{cVQ}'
length 39 , flag b'DASCTF{cU5AW:?Gg!cR8Y*CK@kQAaMxAIH]l<Q}'
length 39 , flag b'DASCTF{n^[ERBLa$Xe}^YhWP7nTLa0*@^%fToN}'
length 39 , flag b'DASCTF{CBEL|Qs>g@qC9IMcWenU$j\\TZ)2$%T5}'
length 39 , flag b"DASCTF{eA671MFQzT'C7:[7vX]J^G]OH^C>-ms}"
'''

python

后面也换了一下centerMark有点玄学的建议是75~100之间多选点师傅的88和我的79都能规约出来，这道题的 $t$ 参数配平倒是没那么重要

Theorem_Plus#

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 = 18770575776346636857117989716700159556553308603827318013591587255198383129370907809760732011993542700529211200756354110539398800399971400004000898098091275284235225898698802555566416862975758535452624647017057286675078425814784682675012671384340267087604803050995107534481069279281213277371234272710195280647747033302773076094600917583038429969629948198841325080329081838681126456119415461246986745162687569680825296434756908111148165787768172000131704615314046005916223370429567142992192702888820837032850104701948658736010527261246199512595520995042205818856177310544178940343722756848658912946025299687434514029951
c = 2587907790257921446754254335909686808394701314827194535473852919883847207482301560195700622542784316421967768148156146355099210400053281966782598551680260513547233270646414440776109941248869185612357797869860293880114609649325409637239631730174236109860697072051436591823617268725493768867776466173052640366393488873505207198770497373345116165334779381031712832136682178364090547875479645094274237460342318587832274304777193468833278816459344132231018703578274192000016560653148923056635076144189403004763127515475672112627790796376564776321840115465990308933303392198690356639928538984862967102082126458529748355566
'''

RSA问题 $e$ 由函数decode_e给出，然后就是解一个相邻素数的RSA

先分析decode_e函数

首先计算e-1的阶乘mul

随后的判断式子e - mul % e - 1 == 0 用到了Wilson’s Theorem 本质是判断是否为素数

即式子

(p-1)!\equiv-1\mod p

当且仅当 $p$ 是素数时成立

如果 $e$ 是素数，那么就有

mulmod+e\equiv(e-1)!\mod e

由Wilson’s Theorem 这里的 $mulmod$ 是 $-1$

如果 $e$ 是合数，假设存在分解

e=a\cdot b

那么在计算阶乘的时候，必有

mul=x\cdot y\cdot z\cdots a\cdot b\cdots \cdot (e-1)

也就必定有

e|mul

此时的 $mulmod$ 就是0

但是存在几个例外如果 $e$ 为 $4$

那么

mul=6

mulmod =2

综上对于式子decode_e(p)我们只需要计算小于等于 $p$ 的素数个数对于所有的素数 $mulmod$ 自减1，对于除开 $4$ 之外的合数 $mulmod$ 不变尝试写个脚本跑一下？但是时间复杂度太高有什么办法简化吗，考虑对这种大范围使用素数筛法即Sieve of Eratosthenes

exp

from Crypto.Util.number import *
from tqdm import tqdm
import numpy as np
n = 18770575776346636857117989716700159556553308603827318013591587255198383129370907809760732011993542700529211200756354110539398800399971400004000898098091275284235225898698802555566416862975758535452624647017057286675078425814784682675012671384340267087604803050995107534481069279281213277371234272710195280647747033302773076094600917583038429969629948198841325080329081838681126456119415461246986745162687569680825296434756908111148165787768172000131704615314046005916223370429567142992192702888820837032850104701948658736010527261246199512595520995042205818856177310544178940343722756848658912946025299687434514029951
c = 2587907790257921446754254335909686808394701314827194535473852919883847207482301560195700622542784316421967768148156146355099210400053281966782598551680260513547233270646414440776109941248869185612357797869860293880114609649325409637239631730174236109860697072051436591823617268725493768867776466173052640366393488873505207198770497373345116165334779381031712832136682178364090547875479645094274237460342318587832274304777193468833278816459344132231018703578274192000016560653148923056635076144189403004763127515475672112627790796376564776321840115465990308933303392198690356639928538984862967102082126458529748355566
goal = 703440151

res = 0
def count_primes_with_sieve(p):
    if p < 2:
        return 0
    is_prime = np.ones(p + 1, dtype=bool)
    is_prime[0] = is_prime[1] = False
    for i in range(2, int(p**0.5) + 1):
        if is_prime[i]:
            is_prime[i*i::i] = False
    return np.sum(is_prime) 
num =  count_primes_with_sieve(goal) 
e = abs(num * -1 + 2)
pp = floor(sqrt(n))
for i in range(-10000, 10000):
    p = pp + i
    if n % p == 0:
        q = n // p
        phi = (p-1) * (q-1)
        assert gcd(e,phi) == 1
        d = inverse_mod(e, phi)
        print(long_to_bytes(pow(c,d,n)))

# b'DASCTF{Ot2N63D_n8L6kJt_f40V61m_zS1O8L7}'

羊城杯2024

TH_Curve#

Baby_Curve#

RSA_Loss#

Theorem_Plus#