本次密码还算友好

RSAloss

思路：m mod n情况，已知高位为b'DASCTF'，低位为b'}'，中间未知，约为200bit。造格爆破未知部分高位，最终在爆破三字节情况下格求解得到准确结果。

import itertools
from Crypto.Util.number import *
import re
from gmpy2 import gcd

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

string = ''
for i in range(33,127):
    string += chr(i)

for i in range(208,512,8):
    print(i)
    S = []
    for i0 in itertools.product(string, repeat=(i-200)//8):
        A = ''
        for i1 in i0:
            A += i1
        S.append(A)
        # print(S)
    for ii in S:
        K0 = bytes_to_long(b'DASCTF{'+ii.encode())*2**208
        K1 = bytes_to_long(b'}')
        KK = (K0+K1-m_mod)
        M = matrix(ZZ,[[n,0],[KK,2**200]])
        mm = M.LLL()
        m = long_to_bytes(abs(int(mm[1][0]))*inverse(2**8,n)%n)
        if re.fullmatch(b'[0-9a-zA-Z_{}]+', m):
            print(m)

TH_curve

问GPT是Hessian curves，maple有过转换推导：

from Crypto.Util.number import *

# def re(x1,y1,p,d2):
#     u = (12*(d2**3-1)*inverse(d2+x1+y1,p)-9*d2**2)%p
#     v= 36*(y1-x1)*(d2**3-1)*inverse(d2+x1+y1,p)%p
#     return u,v

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

d = inverse(G[1]*G[0],p)*(1+a*G[0]**3+G[1]**3) % p
c = 1

F = GF(p)
x, y, z = QQ["x,y,z"].gens()
eq = a * x ^ 3 + y ^ 3 + c * z ^ 3 - d * x * y * z
phi = EllipticCurve_from_cubic(eq)
E = phi.codomain().change_ring(GF(p))

fx, fy, fz = map(lambda f: f.change_ring(F), phi.defining_polynomials())
phiP = lambda x, y, z=1: E(fx(x, y, z) / fz(x, y, z), fy(x, y, z) / fz(x, y, z))
EP = phiP(*G)
EQ = phiP(*Q)
factors, exponents = zip(*factor(E.order()))
primes = [factors[i] ^ exponents[i] for i in range(len(factors))][:-2]
# print(primes)
primes=[ 9, 49, 11, 19, 29, 1361, 6421, 3376343, 1815576031,295369272787]

dlogs = []
for fac in primes:
    t = int(int(EP.order()) // int(fac))
    # dlog = discrete_log(t*EQ,t*EP,operation="+")
    dlog=(t*EP).discrete_log(t*EQ)
    dlogs += [dlog]
    print("factor: "+str(fac)+", Discrete Log: "+str(dlog)) #calculates discrete logarithm for each prime order

x = crt(dlogs,primes)
print(x)

od = EP.order()  # the generator doesn't have full order
print(
    [
        flag
        for i in range(E.order() // od)
        if (flag := long_to_bytes(int(x + od * i))).isascii()
    ]
)

babycurve

b,c居然可以爆破出来，难评。。。后面就是ph问题，求出ecdlp的x值即可：

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

b = 98
c = 35
p = 770311352827455849356512448287
E = EllipticCurve(GF(p), [-c, b])
G = E(584273268656071313022845392380, 105970580903682721429154563816)
P = E(401055814681171318348566474726, 293186309252428491012795616690)
pfactor = [i for i,_ in E.order().factor()][:-1]
print(pfactor)
dislog = []
for i in pfactor:
    t = int(E.order())//int(i)
    dislog.append(discrete_log(P*t,t*G,operation = '+'))
    # dislog.append((t * G).discrete_log(t * A))
    print(f'pfactor {i} have done')
k = crt(dislog,pfactor)


# k = 2951856998192356
key = hashlib.sha256(str(k).encode()).digest()[:16]
iv = long_to_bytes(0xbae1b42f174443d009c8d3a1576f07d6)
cipher = AES.new(key, AES.MODE_CBC, iv)
flag = cipher.decrypt(long_to_bytes(0xff34da7a65854ed75342fd4ad178bf577bd622df9850a24fd63e1da557b4b8a4))
print(flag)

TheoremPlus

我们直接输入一个小值给原题目函数先看看，发现是统计素数个数-2，欧式筛一分钟左右即可。（只不过也看到有师傅用sagemath自带的prime_range函数，学到了，