TH_Curve

题目描述：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
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)

题目分析：

映射关系如下：

https://hyperelliptic.org/EFD/g1p/data/twistedhessian/coordinates

故该曲线为：

\(a x^3+y^3+1=d x y\)

\(2 x^3+y^3+1=d x y\)

通过点Q求出d来从而得到完整的曲线方程

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

接下来解题思路参考：https://tangcuxiaojikuai.xyz/post/a6ee3e0e.html

通过以下方式换元：\(x = \frac{x'}{z'}，y = \frac{y'}{z'}\)

从而转换成以下三次齐次方程形式：\(2x'^3 + y'^3 + z'^3 \equiv dx'y'z' \pmod p\)

构建出椭圆曲线后使用 Pohlig Hellman 即可解出 Q = mG 中的 m

exp: 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
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

# construct ECC to get a solution of 2X^3+Y^3+Z^3=dXYZ
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))

baby_Curve

题目描述：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
#!/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'}

题目分析：

解方程得c，b（或者爆破），然后。。。sagemath10.4解、、

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
from Crypto.Util.number import *
import hashlib
p = 770311352827455849356512448287
x1, y1 = (584273268656071313022845392380, 105970580903682721429154563816)
x2, y2 = (401055814681171318348566474726, 293186309252428491012795616690)
c = ((y1 ** 2 - x1 ** 3) - (y2 ** 2 - x2 ** 3)) * inverse(x1 - x2, p) % p
b = (y1 ** 2 - x1 ** 3 - c * x1) % p
E = EllipticCurve(GF(p), [c, b])
G = E(x1 ,y1)
P = E(x2 ,y2)
k = P.log(G) # 2951856998192356
iv = 0xbae1b42f174443d009c8d3a1576f07d6
cipher = 0xff34da7a65854ed75342fd4ad178bf577bd622df9850a24fd63e1da557b4b8a4
key = hashlib.sha256(str(k).encode()).digest()[:16]
aes = AES.new(key, AES.MODE_CBC, long_to_bytes(iv))
m = aes.decrypt(long_to_bytes(cipher))
print(m)

或者网页版https://sagecell.sagemath.org/

1
2
3
4
5
6
p = 770311352827455849356512448287
E = EllipticCurve(GF(p), [-35, 98])
G = E(584273268656071313022845392380, 105970580903682721429154563816)
P = E(401055814681171318348566474726, 293186309252428491012795616690)
k = G.discrete_log(P)
print(k) # 2951856998192356

RSA_loss

题目描述：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
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 != message，说明message比n大\)

\(试着去简单(+kn)爆破一下没有爆出来\)

\(说明message应该比n大不少，既然如此那就去爆破message里面的每一位\)

参考：https://tangcuxiaojikuai.xyz/post/94c7e291.html

猜测 \(message \in [0-9, a-z, A-Z, \_]\)

那么对应的ascii码就在48~128里面

假设message长度为le

那么：\(newm = c = 256^{(le - 7)} * pre + 256 * m_0 + suf\)

(其中pre = b'DASCTF{'，suf = b'}'，m0为中间未知的数字串)

得到：\(m_0 \equiv 256^{-1} * (c - 256^{(le - 7)} * pre - suf) \pmod p\)

又：\(m_0 \equiv \sum_{i = 0}^{len - 7 - 1 - 1} 256^i * s_i \pmod p\)

得到：\(m_0 \equiv \sum_{i = 0}^{len - 7 - 1 - 1} 256^i * s_i + k * p\)

构造如下格（为了保证能规约出0，做题时可以给格的最后一列配上个大系数）：

\[ M = \begin{pmatrix} 1&&&&&1\\ &1&&&&256\\ &&\ddots&&&\vdots\\ &&&1&&256^{le - 9}\\ &&&&1&-m_0\\ &&&&&p \end{pmatrix} \]

有：\((s_0,s_1,...,s_{(le - 9)}, 1, k) * M = (s_0,s_1,...,s_{(le-9)}, 1, 0)\)

此时：\(s_i \in (48, 128)\)

有点大，优化一下：\(t_i = s_i - 48\)

得到：\(m_0 \equiv \sum_{i = 0}^{len - 9} 256^i * (t_i + 48) \pmod p\)

得到：\(m_0 - 48 * \sum_{i = 0}^{len - 9} 256^i = \sum_{i = 0}^{len - 9} 256^i * t_i = m_1\)

此时 \(t_i \in (0, 80)，目标向量为：(t_0,t_1,...,t_{(le-9)}, 1, 0)\)

测试之后发现只有在 \(le <= 33\) 才能出结果，带入题中数据没得到结果说明 \(len(flag) > 33\)

既然如此，再优化下：\(t_i = s_i - 48 - 40\)

得到：\(m_0 \equiv \sum_{i = 0}^{len - 9} 256^i * (t_i + 48 + 40) \pmod p\)

此时：\(t_i \in (-40, 40)，目标向量为：(t_0,t_1,...,t_{(le-9)}, 1, 0)\)

正好，能出

exp: 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
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
        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]:
        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 != ""):
            print(flag)
    c = newm
# o0p5_m3ssaGe_to0_b1g_nv93nd0

TheoremPlus

题目描述：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
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
'''

题目分析：

函数 decode_e(a) 中的逻辑：

\(如果(a - 1)的阶乘\ mul \equiv (a - 1)! \equiv -1 \pmod a, 那么\ mulmod = -1，否则\ mulmod = mul \%a\)

\(\text{威尔逊定理：对于素数 }p\text{ 有 }(p-1)!\equiv-1\pmod{p}\)

所以(1, a)范围内的数字中，素数的mulmod = -1

那么接下来看看合数的mulmod，合数一定能由小于它的数组成，或者说合数一定能由小于它的素数组成（4除外），比如 6 = 2 * 3，8 = 2 * 4 = 2 * 2 * 2，...

\(故 如果e为合数（4除外），那么一定有(e - 1) ! = k * e（感叹号为阶乘符号），所以此时的\ mulmod = mul \% e =k * e \%e = 0\)

可以去打印一下看看，也是符合的：

既然如此，那么我们只要知道在1~703440151中有多少个素数，我们就能求出e

exp: 

1
2
3
4
5
6
7
8
9
10
11
from Crypto.Util.number import *
from sympy import primepi
from gmpy2 import *
n = 18770575776346636857117989716700159556553308603827318013591587255198383129370907809760732011993542700529211200756354110539398800399971400004000898098091275284235225898698802555566416862975758535452624647017057286675078425814784682675012671384340267087604803050995107534481069279281213277371234272710195280647747033302773076094600917583038429969629948198841325080329081838681126456119415461246986745162687569680825296434756908111148165787768172000131704615314046005916223370429567142992192702888820837032850104701948658736010527261246199512595520995042205818856177310544178940343722756848658912946025299687434514029951
c = 2587907790257921446754254335909686808394701314827194535473852919883847207482301560195700622542784316421967768148156146355099210400053281966782598551680260513547233270646414440776109941248869185612357797869860293880114609649325409637239631730174236109860697072051436591823617268725493768867776466173052640366393488873505207198770497373345116165334779381031712832136682178364090547875479645094274237460342318587832274304777193468833278816459344132231018703578274192000016560653148923056635076144189403004763127515475672112627790796376564776321840115465990308933303392198690356639928538984862967102082126458529748355566
e = primepi(703440151) - 2
p = next_prime(iroot(n,2)[0])
q = n // p
phi = (p - 1) * (q - 1)
d = invert(int(e), phi)
print(long_to_bytes(pow(c, d, n)))
浅记一下：

关键词: ECC，curve，G.discrete_log( P)，Pohlig Hellman，格，优化，阶乘，primepi