糖醋小鸡块的blog
0%

2024-羊城杯-wp-crypto

发表于 更新于 分类于 Valine：

水篇博客。

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)

由题目名字的TH，以及点加的公式可以知道这是一个Twisted Hessian Curve，其方程为：

由于有P、Q坐标，所以任取其中一点就可以求出d来。

求出d之后要解一个Twisted Hessian Curve上的DLP得到m，这一部分当然可以去搜这种曲线向ECC的映射来做，但是更方便的是直接通过转为三次齐次方程的方式，再用sage自带的EllipticCurve_from_cubic来做映射，就像CryptoCTF 2023的Barak一样。

之后检查曲线的order可以发现，即使去除掉最后一个稍大的因子，也已经有足够bit可以求DLP了，所以简单log就行。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
from Crypto.Util.number import *

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


########################################################### part1 get d
d = (a*P[0]^3 + P[1]^3 + 1) * inverse(P[0]*P[1], p) % p

########################################################### part2 dlp
R.<x,y,z> = Zmod(p)[]
cubic = a*x^3 + y^3 + z^3 - d*x*y*z
E = EllipticCurve_from_cubic(cubic,morphism=True)
P = E(P)
Q = E(Q)
r = 60869967041981
m = (r*Q).log(r*P)
print(long_to_bytes(m))


#e@sy_cuRvL_c0o!



BabyCurve

题目：

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
65
66
67
68
#!/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'}

这题的曲线似乎是一个Twisted Edwards Curve，但是不重要，因为这条Curve只是为了帮助我们求出最后的ECC的参数c、b，然而由于我们有G、P两点，所以直接groebner就可以有参数c、b了。

有了曲线参数后还是要解决一个DLP问题，检查一下曲线order的分解发现并不是特别的光滑，最后一个因子有五十多bit，虽然求是可以求的，但肯定很慢。

然而再仔细检查下，会发现说这其实是一条超奇异椭圆曲线，阶是p+1，所以嵌入度是2，所以用MOV attack映射到Fp2上去dlog比较高效。

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
43
44
45
import hashlib
from Crypto.Cipher import AES

p = 770311352827455849356512448287
G = (584273268656071313022845392380 , 105970580903682721429154563816)
P = (401055814681171318348566474726 , 293186309252428491012795616690)


########################################################### part1 get a,b
PR.<c,b> = PolynomialRing(Zmod(p))
f1 = G[1]^2 - (G[0]^3 - c*G[0] + b)
f2 = P[1]^2 - (P[0]^3 - c*P[0] + b)
res = Ideal([f1,f2]).groebner_basis()
print(res)
a = 770311352827455849356512448252
b = -770311352827455849356512448189


########################################################### part2 mov attack
if(1):
    E = EllipticCurve(GF(p), [a, b])
    E2 = EllipticCurve(GF(p**2, 'y'), [a, b])

    P2 = E2(G)
    Q2 = E2(P)

    n = E.order()
    R = E2.random_element()
    tP = P2.weil_pairing(R, n)
    tQ = Q2.weil_pairing(R, n)

    key = tQ.log(tP)
    print(key)
key = 2951856998192356


########################################################### part3 get flag
iv = bytes.fromhex('bae1b42f174443d009c8d3a1576f07d6')
c = bytes.fromhex('ff34da7a65854ed75342fd4ad178bf577bd622df9850a24fd63e1da557b4b8a4')
key = hashlib.sha256(str(key).encode()).digest()[:16]
cipher = AES.new(key, AES.MODE_CBC, iv)
print(cipher.decrypt(c))


#DASCTF{THe_C0rv!_1s_Aw3s0me@!!}



RSA_loss

题目描述：

1
RSA怎么解不出来了呢？

题目：

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

题目兜了个圈子，对flag先加密再解密，最后得到：

所以是flag大于n的原因，导致解出来是乱码，那么任务就是缩减flag的长度，从而使剩余的部分小于n。而最简单的思路就是先爆破flag串的长度，把flag头尾用上，也就是把flag拆成头a、尾b和中间部分t(假设t长度为l)：

所以就有：

这样能做的条件是t小于n，也就是说t要小于等于25字节才行，然而实际测试出来这样做t并不是可见字符串，所以接下来继续把t拆成两部分，第一部分t1用来爆破几个字符，第二部分用来求解就可以了。

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
from Crypto.Util.number import *
from itertools import *
import string

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

if(1):
    table = string.digits + string.ascii_letters + "_"
    nums = 3
    for j in product(table,repeat = nums):
        fix = bytes_to_long(b"DASCTF{" + "".join(j).encode() + b"\x00"*25 + b"}")
        try:
            flag = "".join(j) + long_to_bytes((cc - fix)*inverse(256,n) % n).decode()
            if(all(i in table for i in flag)):
                print("DASCTF{" + flag + "}")
                break
        except:
            pass

#DASCTF{o0p5_m3ssaGe_to0_b1g_nv93nd0}



TheoremPlus

题目描述：

1
相信这里的Theorem你也能知道^V^

题目：

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 *
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，但是其私钥p、q以及加密指数e都不知道，所以这两部分都要求。

p、q的部分很好办，由于q是p的nextprime，所以开根过后小范围搜一下就有p、q了。关键部分在于e，他是一个奇怪的decode_e函数对输入703440151的输出结果的绝对值，而直接跑的话根本跑不完，所以要理解一下这个函数内部过程。

但是这个函数实在太简单了，假设对于输入x，那么他的输出其实就是所有小于x的所有正整数t的(t-1)!模t的值之和，当这个值恰好等于t-1的话那么则会返回-1。既然是阶乘，肯定考的是威尔逊定理，由威尔逊定理首先知道，当t为素数时有：

所以小于x的所有素数会给最终输出结果贡献一个-1，因此关键在于非素数究竟会贡献多少。

其实自己简单测一测可以发现除了4以外，剩下的所有非素数t的这个阶乘结果都是0，这里用最常规的证明思路简单证明一下。

分成两种情况，第一种情况，t是完全平方数，即$t=k^2$，又因为：

所以有：

所以(t-1)!就含有k和2k两个因子，因此有：

第二种情况，t不是完全平方数，而由于t是合数，所以一定可以拆成$t = k_1k_2$，显然k1和k2都小于t，所以(t-1)!就含有k1和k2两个因子，因此有：

证明就结束了，这也代表着非素数对于decode_e函数的输出贡献是0。

因此寻找加密指数，其实就是寻找703440151有多少个素数而已，用sage内置的prime_pi就好了，最后还需要再把x=4对应的2加上。

exp：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
from Crypto.Util.number import *
from tqdm import *
from gmpy2 import *

n = 18770575776346636857117989716700159556553308603827318013591587255198383129370907809760732011993542700529211200756354110539398800399971400004000898098091275284235225898698802555566416862975758535452624647017057286675078425814784682675012671384340267087604803050995107534481069279281213277371234272710195280647747033302773076094600917583038429969629948198841325080329081838681126456119415461246986745162687569680825296434756908111148165787768172000131704615314046005916223370429567142992192702888820837032850104701948658736010527261246199512595520995042205818856177310544178940343722756848658912946025299687434514029951
c = 2587907790257921446754254335909686808394701314827194535473852919883847207482301560195700622542784316421967768148156146355099210400053281966782598551680260513547233270646414440776109941248869185612357797869860293880114609649325409637239631730174236109860697072051436591823617268725493768867776466173052640366393488873505207198770497373345116165334779381031712832136682178364090547875479645094274237460342318587832274304777193468833278816459344132231018703578274192000016560653148923056635076144189403004763127515475672112627790796376564776321840115465990308933303392198690356639928538984862967102082126458529748355566

if(0):
    p = iroot(n,2)[0]
    for i in range(1000):
        p += 1
        if(n % p == 0):
            print(p)

p = 137005750887861042579675520137044512945598822783534629619239107541807615882572096858257909592145785126427095471870315367525847725823941391135851384962433640952546093687945848986528958373691860995753297871619638780075391669495117388905134584566094832853663864356912013900594295175075123578366393694884648557429
q = n // p
e = abs(-prime_pi(703440151)+2)
print(long_to_bytes(int(pow(c,inverse(e,(p-1)*(q-1)),n))))


#DASCTF{Ot2N63D_n8L6kJt_f40V61m_zS1O8L7}