2024羊城杯wp

两道题都跟曲线相关，但都是没见过的曲线，幸好在Maple的博客中看到查曲线网站，某看着不错的ppt总结

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+Q=(\frac{x_1-y_1^2x_2y_2}{ax_1y_1x_2^2-y_2},\frac{y_1y_2^2-ax_1^2x_2}{ax_1y_1x_2^2-y_2})$$

只要在网站上找到是twisted Hessian curves类型，那么用EllipticCurve_from_cubic函数转化后就能dlp了，运行时间挺长的，原先还以为这方法出不了，等洗完澡回来竟然结束了，不枉跑了半小时之久。程序参考自maple

p = 10297529403524403127640670200603184608844065065952536889
a = 2
d = 8817708809404273675545317762394593437543647288341187200
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))
P = (8879931045098533901543131944615620692971716807984752065, 4106024239449946134453673742202491320614591684229547464)
Q = (6784278627340957151283066249316785477882888190582875173, 6078603759966354224428976716568980670702790051879661797)
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(*P)
EQ = phiP(*Q)
print(EP.order(), EQ.order())
x = discrete_log(EQ, EP, operation='+')
print(x)

BabyCurve

#!/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'}

$$P+Q=(\frac{x_1y_2+y_1x_2}{1-dx_1^2x_2^2},\frac{(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})$$

参考论文

Jacobi quartics与一般方程的转换

$$y^2=ex^4-2dx^2+1\qquad s^2=r^3+ar+b\\ (r,s)=(2\frac{3(y+1)-dx^2}{3x^2}, 4\frac{(y+1)-dx^2}{x^3})\\ a=-4\frac{3e+d^2}{3},b=-\frac{16}{27}d(d^2-9e)$$

from Crypto.Util.number import *
def twist_to_weier(G):
    x, y = G
    r = 2*(3*(y+1) - d*x**2)*inverse(3*x**2, p)%p
    s = 4*((y+1)-d*x**2)*inverse(x**3, p)%p
    return (r, s)

d = -46
e = 20
p = 826100030683243954408990060837

A = -4*(3*e+d**2)*inverse(3, p)%p
B = -16*d*(d**2-9*e)*inverse(27, p)%p

G1 = (560766116033078013304693968735, 756416322956623525864568772142)
P1 = (528578510004630596855654721810, 639541632629313772609548040620)
Q1 = (819520958411405887240280598475, 76906957256966244725924513645)
E = EllipticCurve(GF(p), [A, B])
G1 = E(twist_to_weier(G1))
P1 = E(twist_to_weier(P1))
Q1 = E(twist_to_weier(Q1))
discrete_log(P1, G1)	# 35
discrete_log(Q1, G1)	# 98

c、d出来竟然这么小，后悔没直接爆破，起码也第一次靠论文做出题目；跟第一题一样，原先用discrete_log跑了很久，但没有出答案，看来这个点不够光滑，而且$E.order()=p+1$，smart attack也无法使用，试了MOV算法

c = 35
b = 98
p = 770311352827455849356512448287
Fp = GF(p)
E = EllipticCurve(Fp, [-c, b])
G = E((584273268656071313022845392380, 105970580903682721429154563816))
P = E((401055814681171318348566474726, 293186309252428491012795616690))

order = E.order()
k = 1
while (p**k - 1) % order:
    k += 1

K.<a> = Fp.extension(k)
EK = E.base_extend(K)
PK = EK(P)
GK = EK(G)
QK = EK.lift_x(a + 3)  # Independent from PK
AA = PK.tate_pairing(QK, E.order(), k)
GG = GK.tate_pairing(QK, E.order(), k)
key = AA.log(GG) # 2951856998192356

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

$$m=n_m+k*n\\ c\equiv m^e\equiv (n_m+k*n)^e$$

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

$$e-1\equiv-1\equiv mul\mod e$$

又是阶乘又是-1，似乎和威尔逊定理有些相像，可以取小数字打印过程，发现当e是质数时，mulmod都是-1，其余情况大多为0，特殊情况很少，小量可以爆破。

from Crypto.Util.number import *
from math import factorial
import sys
sys.setrecursionlimit(10000)

def decode_e(e, mul):
    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
        print(e, mul, mulmod)
        return mulmod + decode_e(e - 1, mul//(e-1))
    else:
        return 0

p = 137005750887861042579675520137044512945598822783534629619239107541807615882572096858257909592145785126427095471870315367525847725823941391135851384962433640952546093687945848986528958373691860995753297871619638780075391669495117388905134584566094832853663864356912013900594295175075123578366393694884648557219
n = 18770575776346636857117989716700159556553308603827318013591587255198383129370907809760732011993542700529211200756354110539398800399971400004000898098091275284235225898698802555566416862975758535452624647017057286675078425814784682675012671384340267087604803050995107534481069279281213277371234272710195280647747033302773076094600917583038429969629948198841325080329081838681126456119415461246986745162687569680825296434756908111148165787768172000131704615314046005916223370429567142992192702888820837032850104701948658736010527261246199512595520995042205818856177310544178940343722756848658912946025299687434514029951
c = 2587907790257921446754254335909686808394701314827194535473852919883847207482301560195700622542784316421967768148156146355099210400053281966782598551680260513547233270646414440776109941248869185612357797869860293880114609649325409637239631730174236109860697072051436591823617268725493768867776466173052640366393488873505207198770497373345116165334779381031712832136682178364090547875479645094274237460342318587832274304777193468833278816459344132231018703578274192000016560653148923056635076144189403004763127515475672112627790796376564776321840115465990308933303392198690356639928538984862967102082126458529748355566
q = n//p
phi = (p - 1) * (q - 1)
# e = 703440151
li = []
print(decode_e(100, factorial(99)))

既然e是质数取-1，那么函数基本等同于求e以内的质数个数，用sagemath统计下个数，之后对偏差值进行爆破。

from Crypto.Util.number import *
e = 703440151
li = prime_range(1, e)
print(len(li))	# 36421874

p = 137005750887861042579675520137044512945598822783534629619239107541807615882572096858257909592145785126427095471870315367525847725823941391135851384962433640952546093687945848986528958373691860995753297871619638780075391669495117388905134584566094832853663864356912013900594295175075123578366393694884648557219
n = 18770575776346636857117989716700159556553308603827318013591587255198383129370907809760732011993542700529211200756354110539398800399971400004000898098091275284235225898698802555566416862975758535452624647017057286675078425814784682675012671384340267087604803050995107534481069279281213277371234272710195280647747033302773076094600917583038429969629948198841325080329081838681126456119415461246986745162687569680825296434756908111148165787768172000131704615314046005916223370429567142992192702888820837032850104701948658736010527261246199512595520995042205818856177310544178940343722756848658912946025299687434514029951
c = 2587907790257921446754254335909686808394701314827194535473852919883847207482301560195700622542784316421967768148156146355099210400053281966782598551680260513547233270646414440776109941248869185612357797869860293880114609649325409637239631730174236109860697072051436591823617268725493768867776466173052640366393488873505207198770497373345116165334779381031712832136682178364090547875479645094274237460342318587832274304777193468833278816459344132231018703578274192000016560653148923056635076144189403004763127515475672112627790796376564776321840115465990308933303392198690356639928538984862967102082126458529748355566
q = n//p
phi = (p - 1) * (q - 1)
# e = 703440151
li = []
# print(decode_e(100, factorial(99)))

# e = abs(decode_e(703440151))
e = 36421874
for i in range(-100, 100):
    try:
        d = inverse(e+i, phi)
        tmp = long_to_bytes(pow(c, d, n))
        if tmp.startswith(b'DAS'):
            print(tmp)
    except:
        continue