糖醋小鸡块的blog
0%

2024-SEKAICTF-wp-crypto

发表于 更新于 分类于 Valine：

来的比较晚，比赛的时候就去做了一道很简单的CSIDH，赛后看wp研究了几个题发现是真的厉害，所以写篇博客记录一下部分题目(不包含0day)。

参考：

Neobeo/SekaiCTF2024 (github.com)

Some Trick

题目描述：

1
2
Bob and Alice found a futuristic version of opunssl and replaced all their needs for doofy wellmen.
Author: deut-erium

题目：

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
import random
from secrets import randbelow, randbits
from flag import FLAG

CIPHER_SUITE = randbelow(2**256)
print(f"oPUN_SASS_SASS_l version 4.0.{CIPHER_SUITE}")
random.seed(CIPHER_SUITE)

GSIZE = 8209
GNUM = 79

LIM = GSIZE**GNUM


def gen(n):
    p, i = [0] * n, 0
    for j in random.sample(range(1, n), n - 1):
        p[i], i = j, j
    return tuple(p)


def gexp(g, e):
    res = tuple(g)
    while e:
        if e & 1:
            res = tuple(res[i] for i in g)
        e >>= 1
        g = tuple(g[i] for i in g)
    return res


def enc(k, m, G):
    if not G:
        return m
    mod = len(G[0])
    return gexp(G[0], k % mod)[m % mod] + enc(k // mod, m // mod, G[1:]) * mod


def inverse(perm):
    res = list(perm)
    for i, v in enumerate(perm):
        res[v] = i
    return res


G = [gen(GSIZE) for i in range(GNUM)]


FLAG = int.from_bytes(FLAG, 'big')
left_pad = randbits(randbelow(LIM.bit_length() - FLAG.bit_length()))
FLAG = (FLAG << left_pad.bit_length()) + left_pad
FLAG = (randbits(randbelow(LIM.bit_length() - FLAG.bit_length()))
        << FLAG.bit_length()) + FLAG

bob_key = randbelow(LIM)
bob_encr = enc(FLAG, bob_key, G)
print("bob says", bob_encr)
alice_key = randbelow(LIM)
alice_encr = enc(bob_encr, alice_key, G)
print("alice says", alice_encr)
bob_decr = enc(alice_encr, bob_key, [inverse(i) for i in G])
print("bob says", bob_decr)

题目一眼看不出在做什么，就从头理一理加密过程吧，连接上靶机后会做：

  • 给出用于初始化random的种子，之后生成一个长为79的列表G，G中的每个元素是一个8209内数字的随机置换

  • 给FLAG两边都填充上一些随机bit，填充比特的数量不固定

  • 依次给出以下几组值：

要求还原FLAG。

那么就要明确一下题目的几个函数到底干了个什么事情：

  • gexp(g, e)：用快速幂计算置换g的e次方
  • inverse(perm)：求置换perm的逆置换
  • enc(k, m, G)：这个函数稍微复杂一点，可以把它梳理成以下步骤：
    • 把k、m都转化成mod进制数，把每个数位记为ki、mi
    • 计算$t_i = gexp(G_i, k_i)$
    • 把ti[mi]当作mod进制数的数位，组合成一个大整数，当作enc的输出结果

由于连上靶机就给了我们种子，所以我们自然就可以调用gen函数得到完整的G，所以主要问题在于如何把这几次enc的结果和FLAG的求解联系起来。

如果我们把后两次的enc结果转为mod进制数，那么他们的每一个数位对应：

1
gexp(G[i], ki)[mi]

为什么不用第一次而用后两次呢？因为第一次的enc对于我们来说，FLAG和keyb都不知道，但对于后两次的enc结果来说，只有keya和keyb是未知的，也就是说上面的式子里我们唯一不知道的是索引mi。

而这个mi的范围仅仅是0-8209而已，所以我们逐个爆破就可以拿到完整的keya和keyb了。

拿到keyb之后，第一个enc的式子就只有FLAG是未知的了，也就是说同样的这个式子，mi变成了已知，而ki变成了未知部分：

1
gexp(G[i], ki)[mi]

而ki既然也是mod进制的数位，所以范围还是只有0-8209这个小区间内，所以依然靠爆就好了。一个细节是这里不需要调他的gexp来算置换的幂次，只需要依次累加就可以极大缩短时间。

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
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
from Crypto.Util.number import *
from tqdm import *
import random
from pwn import *

############################################################# part1 generate G
sh = remote("sometrick.chals.sekai.team", 1337, ssl = True)
sh.recvuntil(b"oPUN_SASS_SASS_l version 4.0.")
CIPHER_SUITE = int(sh.recvline().strip().decode())
random.seed(CIPHER_SUITE)

GSIZE = 8209
GNUM = 79
LIM = GSIZE**GNUM

def gen(n):
    p, i = [0] * n, 0
    for j in random.sample(range(1, n), n - 1):
        p[i], i = j, j
    return tuple(p)

def gexp(g, e):
    res = tuple(g)
    while e:
        if e & 1:
            res = tuple(res[i] for i in g)
        e >>= 1
        g = tuple(g[i] for i in g)
    return res

def enc(k, m, G):
    if not G:
        return m
    mod = len(G[0])
    return gexp(G[0], k % mod)[m % mod] + enc(k // mod, m // mod, G[1:]) * mod

def inverse(perm):
    res = list(perm)
    for i, v in enumerate(perm):
        res[v] = i
    return res

G = [gen(GSIZE) for i in range(GNUM)]
mod = len(G[0])


############################################################# part2 get DH_data
sh.recvuntil(b"bob says ")
bob_encr = int(sh.recvline().strip().decode())
sh.recvuntil(b"alice says")
alice_encr = int(sh.recvline().strip().decode())
sh.recvuntil(b"bob says ")
bob_decr = int(sh.recvline().strip().decode())


############################################################# part3 get Alice's and Bob's key
####################################### get Alice's key
A1 = alice_encr
B1 = bob_encr
c_alice_mod = []
c_bob_mod = []
while(1):
    c_alice_mod.append(A1 % mod)
    c_bob_mod.append(B1 % mod)
    A1 //= mod
    B1 //= mod
    if(A1 == 0 and B1== 0):
        break
Alice_key = []
for i in range(len(G)):
    temp = gexp(G[i], c_bob_mod[i])
    for j in range(mod):
        if(temp[j] == c_alice_mod[i]):
            Alice_key.append(j)
#print(Alice_key)

####################################### get Bob's key
B2 = bob_decr
A2 = alice_encr
c_bob_mod = []
c_alice_mod = []
while(1):
    c_alice_mod.append(A2 % mod)
    c_bob_mod.append(B2 % mod)
    A2 //= mod
    B2 //= mod
    if(A2 == 0 and B2== 0):
        break
Bob_key = []
inv_G = [inverse(i) for i in G]
for i in range(len(inv_G)):
    temp = gexp(inv_G[i], c_alice_mod[i])
    for j in range(mod):
        if(temp[j] == c_bob_mod[i]):
            Bob_key.append(j)
#print(Bob_key)


############################################################# part4 decrypt
B3 = bob_encr
c_bob_mod = []
while(1):
    c_bob_mod.append(B3 % mod)
    B3 //= mod
    if(B3== 0):
        break
FLAG = 0
for i in trange(len(G)):
    tt = G[i]
    for j in range(mod):
        if(tt[Bob_key[i]] == c_bob_mod[i]):
            FLAG += mod**i * j
            break
        tt = tuple(tt[oo] for oo in G[i])

for i in range(8):
    flag = long_to_bytes(FLAG>>i)
    if(b"SEKAI" in flag):
        print(flag)
        break


#SEKAI{7c124c1b2aebfd9e439ca1c742d26b9577924b5a1823378028c3ed59d7ad92d1}



はやぶさ

题目描述：

1
2
3
4
5
6
7
One day, a bird set out for the edge of the universe.

Will he make it back without breaking his wing...?

GOOD LUCK!

Author: kanon

题目：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
from falcon import falcon
from flag import flag
from timeout_decorator import timeout

@timeout(30)
def main():
    sk = falcon.SecretKey(64)
    pk = falcon.PublicKey(sk)
    print(pk)

    your_sig = bytes.fromhex(input("what is your sig? >"))

    if pk.verify(b"Can you break me", your_sig):
        print("well done!!")
        print(flag)
        exit()

    print("Broken your wing T_T")


main()

题目要伪造一个falcon的签名，其中n=64.

由于我一点都不了解falcon，所以要先读一读它的代码：

tprest/falcon.py: A python implementation of the signature scheme Falcon (github.com)

然后发现说他Secretkey使用的推荐参数最小都是128的，而64相比起来太小了，所以这也是他的突破点。而falcon的私钥主要是四个多项式f、g、F、G，而公钥是一个多项式。由于我们只有公钥，所以要利用的肯定是公钥对应的式子，也就是：

而他们在的环为：

所以其实核心就是在商环下解个NTRU而已，由于64比较小所以可以用LLL、BKZ之类的规约出来满足要求的f、g，进而可以计算出F、G从而算出签名，由于本身没装这个falcon，感觉后面伪造签名的步骤也许比较繁琐，所以这里偷懒就不做了。



マスタースパーク

题目描述：

1
2
3
恋符「マスタースパーク」

Author: kanon

题目：

challenge.sage：

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
69
70
71
72
73
74
75
from Crypto.Util.number import *
import os
from timeout_decorator import timeout, TimeoutError

load("GA.sage")

FLAG = os.getenv("FLAG")
secret = getPrime(256)
choice = set()


@timeout(60)
def T_T(p, primes, secret):

    assert isPrime(p)
    assert len(primes) > 3

    Fp = GF(p)
    Fp2.<j> =  GF(p ^ 2, modulus=x ^ 2 + 1)
    ls = len(factor(p + 1)) - 2

    m = ceil((sqrt(p) ** (1 / ls) - 1) / 2)
    alice_priv = [randrange(-m, m + 1) for _ in range(len(primes))]
    bob_priv = [randrange(-m, m + 1) for _ in range(len(primes))]
    EC = montgomery(Fp2, 0)
    P = EC.gens()[0]
    k = 1
    alice_pub, Q = group_action(p, primes, Fp, Fp2, 0, alice_priv, k * P)
    share_bob, Q = group_action(p, primes, Fp, Fp2, alice_pub, bob_priv, secret * Q)
    bob_pub, P = group_action(p, primes, Fp, Fp2, 0, bob_priv, P)
    share_alice, P = group_action(p, primes, Fp, Fp2, bob_pub, alice_priv, P)
    return P, Q


def check(p):
    assert isPrime(p)
    assert p.bit_length() <= 96
    assert ((p + 1) // 4) % 2 == 1
    prime_list = []
    cnt = 0

    for p, i in factor((p + 1) // 4):
        assert not p in choice
        if i > 1:
            cnt += 1
            choice.add(p)
            assert int(p).bit_length() <= 32
        else:
            prime_list.append(p)
            choice.add(p)

    assert all([int(p).bit_length() <= 16 for p in prime_list])
    assert cnt == 1

    return prime_list


def main():
    while True:
        try:
            p = int(input("input your prime number or secret > "))
            if int(p).bit_length() == 256:
                if p == secret:
                    print(FLAG)
                    exit()
                print("not flag T_T")
            else:
                prime_list = check(p)
                P, Q = T_T(p, prime_list, secret)
                print(P.xy())
                print(Q.xy())
        except:
            print("T_T")
            exit()
main()

GA.sage：

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
from random import randint

# I received advice from Mitsu to write this program. I appreciate it very much

def montgomery(Fp2, A):
    return EllipticCurve(Fp2, [0, A, 0, 1, 0])

def to_montgomery(Fp, Fp2, E, G):
    Ep = E.change_ring(Fp).short_weierstrass_model()
    a, b = Ep.a4(), Ep.a6()
    P.<x> = PolynomialRing(Fp)
    r = (x^3 + a*x + b).roots()[0][0]
    s = sqrt(3 * r^2 + a)
    if not is_square(s):
        s = -s
    A = 3 * r / s
    phi = E.isomorphism_to(EllipticCurve(Fp2, [0, A, 0, 1, 0]))
    return Fp(A), phi(G)

def group_action(p, primes, Fp, Fp2, pub, priv, G):
    E = montgomery(Fp2, pub)
    es = priv[:]
    while any(es):
        x = Fp.random_element()
        P = E.lift_x(x)
        s = 1 if P[1] in Fp else -1
        S = [i for i, e in enumerate(es) if sign(e) == s and e != 0]
        k = prod([primes[i] for i in S])
        Q = ((p + 1) // k) * P
        
        for i in S:
            R = (k // primes[i]) * Q
            if R.is_zero():
                continue
            phi = E.isogeny(R)
            E = phi.codomain()
            Q, G = phi(Q), phi(G)
            es[i] -= s
            k //= primes[i]
    return to_montgomery(Fp, Fp2, E, G)

题目基于CSIDH，在60s内我们有无限次交互机会，每次交互可以传给他一个素数p，他会对p进行如下检查：

  • 如果p是个256bit的素数，那么会检查p是否等于secret，如果相等则发送flag
  • 否则检查p是否满足以下要求：
    • 比特长度小于等于96
    • (p+1)//4是奇数
    • (p+1)//4的因子里需要有且仅有一个平方项，且该平方项比特长度小于等于32
    • 剩余的所有因子次数只能为1，并且比特长度小于等于16
  • 如果p满足上述要求，那么所有一次的因子会被记录在primelist中返回，并且(p+1)//4的所有因子不能在下一次交互中使用了

然后他会用我们给出的p去生成超奇异椭圆曲线，并随机生成A、B的私钥列表后在上面进行CSIDH。

突破点在于，和imaginary的coast一样，他的CSIDH不仅给了起始和终止的两条曲线，还给了经过映射的点，不妨把下面这个点记作G：

1
P = EC.gens()[0]

那么对于返回的P、Q来说，它们分别是：

所以就有：

那么事情就很好办了，由于二次曲线的阶就是我们构造的(p+1)//4的素因子组成的，所以我们只需要选不重复的光滑数之后求dlp，最后crt起来就行。

一个奇怪的事实是返回的有时候会满足：

所以还需要爆破一下正负号去crt

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
46
47
48
49
50
51
52
53
54
55
56
from Crypto.Util.number import *
from sage.all import *
from pwn import *
from itertools import *
from tqdm import *

def runcmd(command):
    ret = subprocess.run(command,shell=True,stdout=subprocess.PIPE,stderr=subprocess.PIPE,encoding="utf-8")
    if ret.returncode == 0:
        print("success:",ret)
    else:
        print("error:",ret)


io = remote(*'master-spark.chals.sekai.team 1337'.split(), ssl=True)
io.recvuntil(b'proof of work: ')
cmd = io.recvline().strip().decode()
res = runcmd(cmd)
io.sendlineafter(b'solution: ', res.encode())


pp = [8669547031167394626545563, 93196891599402720144058171, 114950807536953966770987203, 603383564646916990332259, 691975520588667023093600707, 5474437438664916806477851]

modd = []
c = []
for p in tqdm(pp):
    Fp = GF(p)
    Fp2.<j> =  GF(p ^ 2, modulus=x ^ 2 + 1)

    io.recvuntil(b"input your prime number or secret > ")
    io.sendline(str(p).encode())
    Px,Py = eval(io.recvline().strip().decode())
    Qx,Qy = eval(io.recvline().strip().decode())

    A = Fp2((Fp2(Py)^2 - (Fp2(Px)^3 + Fp2(Px))) * Fp2(Px)^(-2))
    EA = EllipticCurve(Fp2, [0, A, 0, 1, 0])
    P = EA(Px,Py)
    Q = EA(Qx,Qy)
    modd.append(Q.order())
    c.append((Q.log(P), Q.log(-P)))

for i in product([0,1],repeat=len(pp)):
    try:
        t = [c[j][i[j]] for j in range(len(pp))]
        secret = crt(t,modd)
        if(len(bin(secret)) == 258):
            print(secret)
            io.sendline(str(secret).encode())
            print(io.recvline())
            print(io.recvline())
            print(io.recvline())
    except:
        pass

    
#SEKAI{(h0w_4b0u7_70uh0u_pr0j3c7??_OH_WAIT_Help_me,ERINNNNNNNNNNNN!!_https://youtu.be/X8z23t428kU?si=4ufTbouKxwQ6Lbhm}



Squares vs. Cubes

题目描述：

1
Author: Neobeo

题目：

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
from Crypto.Util.number import bytes_to_long, getPrime
from secrets import token_bytes, randbelow
from flag import FLAG

padded_flag = bytes_to_long(FLAG + token_bytes(128 - len(FLAG)))

p, q, r = getPrime(512), getPrime(512), getPrime(512)
N = e = p * q * r
phi = (p - 1) * (q - 1) * (r - 1)
d = pow(e, -1, phi)

# Genni likes squares and SBG likes cubes. Let's calculate their values
value_for_genni = p**2 + (q + r * padded_flag)**2
value_for_sbg   = p**3 + (q + r * padded_flag)**3

x0 = randbelow(N)
x1 = randbelow(N)

print(f'{N = }')
print(f'{x0 = }')
print(f'{x1 = }')
print('\nDo you prefer squares or cubes? Choose wisely!')

# Generate a random k and send v := (x_i + k^e), for Oblivious Transfer
# This will allow you to calculate either Genni's or SBG's value
# I have no way of knowing who you support. Your secret is completely safe!
v = int(input('Send me v: '))

m0 = (pow(v - x0, d, N) + value_for_genni) % N
m1 = (pow(v - x1, d, N) + value_for_sbg) % N
print(f'{m0 = }')
print(f'{m1 = }')

真正需要记录的就是这个题和下面那道题了。题目基于RSA的Oblivious Transfer，具体来说题目先会用p、q、r三个素数的乘积同时当作公钥N和e，然后计算如下两个值：

其中m是pad到128字节的flag。

然后随机生成两个值x0、x1，并给出N、x0和x1的值，此时可以输入一个值v，靶机会返回：

要求还原flag。

在这里先了解一下Oblivious Transfer的背景，假设有A、B两方，B有多个消息，A想获得其中的一个消息，因此要和B进行通信。而用最简单的话来理解一下Oblivious Transfer的概念的话，这场通信主要就是要满足以下两点要求：

  • A仅能从B那里获取最多一个消息，对A来说，剩下的消息的“任何相关信息”他都完全不知道
  • B不能知道A究竟获取了哪个信息

那么对于RSA的Oblivious Transfer来说，我们可以看一看他符不符合这个要求。比如A来说，如果他想要获得genni的value，那么他就任取k，并输入：

那么m0、m1就分别是：

那么分别看这样满不满足Oblivious Transfer的两点要求：

  • 第一点是满足的，因为A知道k的值，所以显然他可以通过m0计算出genni的value来；而由于A不知道d的值，所以他没办法计算出sbg的value，m1对于他来说和随机数没什么两样

  • 第二点也是满足的，因为B虽然能知道A输入的v是多少，但由于他不知道k的值，所以自然也无法判断出A究竟是想要获得genni还是sbg了。

    这里可能会觉得，B既然有私钥d的值，那么他只需要把v减去x0之后再求d次方，不就可以获得k了吗？

    然而这个说法是站不住脚的，因为B不知道A究竟想要x0还是x1，所以他不知道该减x0还是x1，而减x1后再求d次方同样可以得到一个值，所以B依然无法判断哪个才是A选择的k

而这种“满足要求“是对于genni和sbg的value都是未知值而言的，这个题目我们知道了这两个value的形式这一个额外信息，所以有了可乘之机。

具体来说我们可以就简单输入x0，就得到：

既然要利用genni和sbg两个value的形式，那么把他们写开：

为了方便记录，记：

因为p是N的因子，所以式子可以转到模p下来：

由于有未知的d次方，而消掉他的唯一办法就是求e次幂，所以进行如下移项：

对第二个式子两边乘e次幂就有：

那么现在我们就有了两个在模p下以t为公共根的多项式：

所以如果有p的话，就可以求GCD得到一个模p下的公因式$(x - t)$，就有t的值了。

虽然第二个多项式度很大，但是由于第一个多项式度仅为2，所以在商环下算GCD就好了

然而问题在于我们没有p，只有p的倍数N，因此我们得到的一次式应该是：

其中$t_1 = t + kp$

而我们知道f1在模p下也是以t为根的，那么就有：

所以作差后与N做gcd就得到p了，得到p后自然也就有t的值。

之后就是如何由t的值求解flag，由于我们知道t是：

m是128字节，r是512bit，所以可以认为我们得到的t要么就是本身的值，要么也就模掉了几个N而已。而到底模掉几个N是可以爆的，因此我们不妨就假设我们得到的t就是本身的值。因为我们有p，所以我们自然有qr的乘积，又因为t的大小几乎是由rm决定的，所以有：

又因为m是”SEKAI{“开头，因此我们用这个当作m的近似m’，就有：

同理因为：

所以有：

有了q的高位自然就会想copper，而要copper最好就要把式子里多余的r、m给消掉，而消掉的最好办法就是模，我们只需要给式子两边同时乘上q，得到：

那么就有以q为根的多项式：

将高位代入进去copper就可以得到完整的q了，之后也就得到了r，最后就得到了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
32
33
34
35
36
37
38
39
40
41
42
43
44
45
from Crypto.Util.number import *

################################################################## part1 get data
if(1):
    from pwn import *
    sh = remote("squares-vs-cubes.chals.sekai.team", 1337, ssl=True)
    sh.recvuntil(b"N = ")
    N = int(sh.recvline().strip().decode())
    sh.recvuntil(b"x0 = ")
    x0 = int(sh.recvline().strip().decode())
    sh.recvuntil(b"x1 = ")
    x1 = int(sh.recvline().strip().decode())

    sh.sendline(str(x0).encode())
    sh.recvuntil(b"m0 = ")
    m0 = int(sh.recvline().strip().decode())
    sh.recvuntil(b"m1 = ")
    m1 = int(sh.recvline().strip().decode())

################################################################## part2 get p and q+rm
def polypow(base, exp, mod):
    return (mod.parent().quo(mod)(base) ** exp).lift()

PR.<x> = PolynomialRing(Zmod(N))
p = gcd(N, ZZ((polypow(x**3 - m1, N, x**2 - m0) + x0 - x1).monic()[0]**2 - m0))
qr = N // p
t = ZZ(-(polypow(x**3 + p**3 - m1, N, x**2 + p**2 - m0) + x0 - x1).monic()[0])


################################################################## part3 get q,r
qh = qr*bytes_to_long(b'SEKAI{' + b"\x00"*122) // t
PR.<x> = PolynomialRing(Zmod(qr))
f = (qh + x)^2 - t*(qh + x)
f = f.monic()
res = f.small_roots(X = 2^(512-6*8),beta=1,epsilon=0.05)
q = qh + int(res[0])
r = qr // q


################################################################## part4 flag
m = (t - q) // r
print(long_to_bytes(m))


#SEKAI{this_challenge_was_originally_called_oblivion_but_there_was_an_ACSC_crypto_also_called_that}



√163

题目描述：

1
The square root of 163 is a magical number.

题目：

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 ast import literal_eval
from hashlib import sha256
from Crypto.Cipher import AES

ells = [*primes(3, 128), 163]
p = 4 * prod(ells) - 1
F = GF(p)

def csidh(A, priv):
    E = EllipticCurve(F, [0, A, 0, 1, 0])
    for sgn in [1, -1]:
        for e, ell in zip(priv, ells):
            for i in range(sgn * e):
                while not (P := (p + 1) // ell * E.random_element()):
                    pass
                E = E.isogeny_codomain(P)
        E = E.quadratic_twist()
    return E.montgomery_model().a2()

# This is the private key for the 163-isogeny, given by [0, 0, ..., 0, 1]
priv_163 = [int(ell == 163) for ell in ells]
pub_163 = csidh(0, priv_163)

# This is the private key for the sqrt(163)-isogeny, such that if you square it you get the 163-isogeny
priv_rt163 = literal_eval(input("Enter private key: "))
pub_rt163 = csidh(0, priv_rt163)

assert csidh(pub_rt163, priv_rt163) == pub_163, "Your private key does not define a sqrt(163)-isogeny!"

ct = 'efee2dfd387fe42a983089c517d4e479c98242da5687c62548ca12a06096962e6271ef268600406fde4f0ee50c844f42aac23cd9cf0f07e4822c4045daf917d4'
print(AES.new(sha256(str(pub_rt163).encode()).digest(), AES.MODE_ECB).decrypt(bytes.fromhex(ct)).decode())

这个题让我自己做是做不出来一点的，复现的时候觉得太厉害了，所以写篇wp记录一下。题目依然基于CSIDH，题意也很简单，给了一个私钥列表priv_163：

要求我们给出一个私钥列表priv_rt163，使得连续使用两次priv_rt163进行CSIDH的结果应该等于使用priv_163的结果，也就是题目中的“开根”。

由于我们知道CSIDH对于每个私钥指数来说都构成一个循环子群，所以如果我们能知道群阶的话，就可以取群阶意义下的1/2作为指数列表的最后一个值，从而得到我们需要的sqrt163对应的私钥。

然而这个群阶我完全不知道能怎么求，看了wp知道可以这样：

1
pari.quadclassunit(-4*p)

这样求出来的是整个模p下超奇异椭圆曲线群的阶，因此所有子群阶其实都是他的因子。所以做到这一步我们已经可以找到满足条件的指数列表了，也就是刚才说的取群阶意义下的1/2作为指数列表的最后一个值。然而还有个问题就是，题目是会把输入的指数列表实际用进去进行CSIDH的，所以指数太大的话，是计算不出来sqrt163对应的那条曲线的，因此还要想办法找一组比较小的私钥列表才行。

检验一下可以发现对于3的isogeny来说，其构成的循环群就是整个群，这也代表着3-isogeny可以生成整个群。因此在某种意义上，这其实像是把整个模p下超奇异椭圆曲线群同构到了一个乘法群。而既然3-isogeny是生成元，那么自然所有t-isogeny的操作都可以用多次3-isogeny的操作来表示。

而分解一下群阶发现还是比较光滑的，因此可以求DLP得到所有t-isogeny究竟等价于多少次3-isogeny。之后的问题就简单了，我们只需要利用DLP的结果，去找到一个和下面私钥等价的小私钥就行：

用LLL就可以轻松做到了。

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
46
47
48
49
50
51
52
53
54
55
56
57
58
59
from hashlib import sha256
from Crypto.Cipher import AES
from tqdm import *

ells = [*primes(3, 128), 163]
p = 4 * prod(ells) - 1
F = GF(p)

def csidh(A, priv):
    E = EllipticCurve(F, [0, A, 0, 1, 0])
    for sgn in [1, -1]:
        for e, ell in zip(priv, ells):
            for i in range(sgn * e):
                while not (P := (p + 1) // ell * E.random_element()):
                    pass
                E = E.isogeny_codomain(P)
        E = E.quadratic_twist()
    return E.montgomery_model().a2()

priv_163 = [int(ell == 163) for ell in ells]
pub_163 = csidh(0, priv_163)


################################################################### part1 get order of cyclic group
#print(pari.quadclassunit(-4*p))
order = 102019419125180345266808265
q3 = pari.Qfb(3, 2, (p + 1) // 3)
assert q3^order == q3^0


################################################################### part2 dlog to get equivalent base
if(0):
    dlogs = []
    for ell in tqdm(ells[1:]):
        qfb = pari.Qfb(ell, 2, (p + 1) // ell)
        dlog = discrete_log(qfb, q3, order, operation=None, identity=q3^0, inverse=lambda x:x^-1, op=lambda a,b:a*b)
        dlogs.append(dlog)
    print(f'{dlogs = }')


################################################################### part3 LLL to get computable priv
dlogs = [99277373102719610806018318, 83421842872387889334089797, 56025662040177681113282671, 49118499040862518947572689, 15645397576648648377412663, 61665764328525124260421806, 40759403716184792525659432, 31140627057263348551498094, 78905162375544758325347534, 68648809775830894573699528, 27796094893603291570999031, 78112521103814979835264292, 71297227107539993495048581, 5454556439229721216822295, 34681014828399246267433987, 1131661496461019698848506, 19470946870768387275356752, 28023327100560354609957208, 100760725121150163662605029, 47438315827128855974764291, 22463776763940393335995788, 57476506252950753777492233, 38279636483214683683465573, 72876847482914625705898507, 92908295887796648693653575, 11507826156847169190868322, 100199642765699100371989608, 26514294093065170664931843, 71477976132429316196420873, 3805079142319255203702393]
L = block_matrix(ZZ,[
    [identity_matrix(len([1]+dlogs)+1),Matrix(ZZ,[1]+dlogs+[-mod(1/2, order)*dlogs[-1]]).T],
    [matrix.zero(1, len([1]+dlogs)+1),order]
])
L[:,-1:] *= 2^1024
if(1):
    res = L.LLL()
    for i in res[:-1]:
        vec = i[:-1]
        if(vec[-1] == 1):
            priv_rt163 = vec
            pub_rt163 = csidh(0, priv_rt163)
            if(csidh(pub_rt163, priv_rt163) == pub_163):
                ct = 'efee2dfd387fe42a983089c517d4e479c98242da5687c62548ca12a06096962e6271ef268600406fde4f0ee50c844f42aac23cd9cf0f07e4822c4045daf917d4'
                flag = AES.new(sha256(str(pub_rt163).encode()).digest(), AES.MODE_ECB).decrypt(bytes.fromhex(ct)).decode()
                print(flag)
                break