2024-0CTF-wp-crypto

应该是今年打的最后一场CTF了，记录一下自己有看的三个题目的解法。

Signin

题目描述：

Do you miss pure lwe?

题目：

from Crypto.Util.number import bytes_to_long
from string import ascii_lowercase
from sympy import nextprime
from secret import FLAG
import numpy as np
import random
import signal
import os


def _handle_timeout(signum, frame):
    raise TimeoutError('function timeout')

timeout = 60
signal.signal(signal.SIGALRM, _handle_timeout)
signal.alarm(timeout)


def uniform_sample(n, bound, SecureRandom):
    return [SecureRandom.randrange(-bound, bound) for _ in range(n)]


def ternary_sample(n, ternaryL, SecureRandom):
    return [ternaryL[int(_)] for __ in range(n // 5) for _ in np.base_repr(ord(SecureRandom.choice(ascii_lowercase)), 3)]

n = 137
m = 220
q = nextprime(1337)
e_L = [0, 101, 731]
R_s= random.SystemRandom()
s = np.array(uniform_sample(n, q//2, R_s))
R_e = random.SystemRandom()
e = np.array(ternary_sample(m, e_L, R_e))
seed = os.urandom(16)
R_A = random
R_A.seed(seed)
A = np.array([uniform_sample(n, q, R_A) for _ in range(m)])
b = (A.dot(s) + e) % q
print(f"{seed.hex() = }")
print(f"{b.tolist() = }")
s_ = input("Give me s: ")
if s_ == str(s.tolist()):
    print("Congratulations! You have signed in successfully.")
    print(FLAG)
else:
    print("Sorry, you cannot sign in.")

题目基于$(m,n)=(220,137)$的LWE：

$$b = sA + e$$

给出$A,b$，需要我们在60s内解出私钥$s$并提交给靶机，从而拿到flag。

对于这个题目的LWE来讲，能利用的地方主要有：

• $(m,n)$不算很大
• $e$仅由三个值[0, 101, 731]组成

并且仔细观察一下生成$e$的函数：

def ternary_sample(n, ternaryL, SecureRandom):
    return [ternaryL[int(_)] for __ in range(n // 5) for _ in np.base_repr(ord(SecureRandom.choice(ascii_lowercase)), 3)]

其步骤为：

• $e$以五个值为一组生成
• 对于每一组，是在小写字母里随机选择一个值，并且取他的ASCII码的三进制表示作为索引，在[0, 101, 731]按顺序选

而由于所有小写字母的三进制表示都是1开头的，所以每一组的第一个值被固定为了101，因此$e$有$44=\frac{220}{5}$个位置是确定的。

回到题目来，要求这样一个LWE的话，主要有下面几个优化可以用。

减小error

这个很简单，既然$e$仅由三个值[0, 101, 731]组成，所以类似easy_mod，可以用线性的方式约减一下系数到一个较小值。简单爆破一下会发现在乘283的时候，[0, 101, 731]会对应变成[0, 2, 1]，再做一个减1就可以进一步得到[-1, 1, 0]，这样的集合就很符合我们的预期。

降维

既然$e$有44个位置已知，那么我们不妨把这些已知位置统一移到前面，记为$e_1$，未知的部分记为$e_2$，对应的，重组一下矩阵方程就是：

$$(b_1 \;|\; b_2) = s (A_1 \;|\; A_2) + (e_1 \;|\; e_2)$$

显然对于第一部分，可以提取出一个矩阵方程来：

$$b_1 = sA_1 + e_1$$

这个方程以$s$的137个变量作为未知数，总共是44组方程，所以实际上解空间只剩下了$93=137-44$维，也就是可以固定$s$的前44个值，记为$s_1$，而只待定后93个变量，记为$s_2$。

既然$s$又做了分段，我们就可以进一步把矩阵方程分块成：

$$(b_1 \;|\; b_2) = (s_1 \;|\; s_2) (\frac{A_{11}}{A_{12}} | \frac{A_{21}}{A_{22}}) + (e_1 \;|\; e_2)$$

所以刚才的方程就是：

$$b_1 = s_1A_{11} + s_2A_{12} + e_1$$

固定$s_1$，并用$s_2$表示他：

$$s_1 = b_1 - (s_2A_{12}A_{11}^{-1} + e_1A_{11}^{-1})$$

而对于未知的$e_2$对应部分有：

$$b_2 = s_1A_{21} + s_2A_{22} + e_2$$

把刚才得到的关于$s_1$的部分代入，就可以消掉$s_1$：

$$b_2 = (b_1 - (s_2A_{12}A_{11}^{-1} + e_1A_{11}^{-1}))A_{21} + s_2A_{22} + e_2$$

整理一下就得到了一个新的LWE实例：

$$b' = b_2 - b_1A_{21} + e_1A_{11}^{-1}A_{21}$$ $$A' = A_{22} - A_{12}A_{11}^{-1}A_{21}$$ $$\rightarrow b' = s_2A' + e_2$$

如此就实现了第一个降维。

primal attack

这也是个降维技巧，之前我的博客有记录过，主要思想在于利用线性处理使得可以只规约出$e$而不规约$s$，可以参考：

LWE | 糖醋小鸡块的blog (tangcuxiaojikuai.xyz)

此时格的维数进一步降到了$177\times177$。

此时已经足够解决题目，用BKZ(block_size=10)极高概率可以解掉，大约三四秒钟。

exp

########################################################################## part1 get data
from Crypto.Util.number import *
from pwn import process, context, remote
import random

def uniform_sample(n, bound, SecureRandom):
    return [SecureRandom.randrange(-bound, bound) for _ in range(n)]

context.log_level = "critical"
#sh = process(["python3", "task.py"])
sh = remote("instance.penguin.0ops.sjtu.cn", 18433)

sh.recvuntil(b"seed.hex() = ")
SEED = bytes.fromhex(sh.recvline().strip().decode()[1:-1])
sh.recvuntil(b"b.tolist() = ")
b = eval(sh.recvline().strip().decode())

n = 137
m = 220
q = next_prime(1337)
R_A = random
R_A.seed(SEED)
A = Matrix(Zmod(q), ([uniform_sample(n, q, R_A) for _ in range(m)])).T
b = vector(Zmod(q), b)

########################################################################## part2 block A, b
A1 = Matrix(Zmod(q), n, 0)
A2 = Matrix(Zmod(q), n, 0)
b1 = []
b2 = []
known = m // 5
for i in range(m // 5):
    A1 = A1.augment(A[:, 5*i:5*i+1])
    A2 = A2.augment(A[:, 5*i+1:5*i+5])
    b1.append(b[5*i])
    b2 += b[5*i+1:5*i+5]
b1 = vector(Zmod(q), b1)
b2 = vector(Zmod(q), b2)

A11 = A1[:known, :]
A12 = A1[known:, :]
A21 = A2[:known, :]
A22 = A2[known:, :]

########################################################################## part3 convert to (137-44)-LWE
X = A12*A11^(-1)
Y = (b1 - vector(Zmod(q), [101]*known))*A11^(-1)

#new LWE sample: b_ = s2*A_ + e
A_ = A22 - X*A21
b_ = b2 - Y*A21

########################################################################## part4 *283 - 1 to make error -> (1,0,-1) and get e2
def primal_attack2(A,b,m,n,p):
    L = block_matrix(
        [
            [matrix(Zmod(p), A).T.echelon_form().change_ring(ZZ), 0],
            [matrix.zero(m - n, n).augment(matrix.identity(m - n) * p), 0],
            [matrix(ZZ, b), 1],
        ]
    )
    L = L.BKZ(block_size=10)
    res = L[0]
    if(res[-1] == 1):
        e2 = res[:-1]
    else:
        e2 = -res[:-1]
    return e2

nums = m - known
e2 = primal_attack2(283*A_.T[:nums], (283*b_-vector(Zmod(q), [1]*len(b_)))[:nums], nums, n-known, q)

########################################################################## part5 get s and get flag
e = (vector(Zmod(q), [1]*known + e2.list()) + (vector(Zmod(q), [1]*m))) * 731
s = (A1.augment(A2)).solve_left(vector(Zmod(q), b1.list()+b2.list()) - e).list()
for i in range(len(s)):
    if(s[i] > q // 2):
        s[i] = int(s[i]) - q

sh.recvuntil(b"Give me s: ")
sh.sendline(str(s).encode())
print(sh.recvline())
print(sh.recvline())

#0ops{7he_S3cur1ty_0f_LWE_Do5e_not_Re1y_on_the_Secret_Distribution, but_the_3rr0r_Distribu7ion~~~~~~}

继续降维

虽然题目已经完美解决了，但其实维还可以继续降，注意到上方exp的part4中有一个变量nums，默认是176，也就是把所有列全部取上。但其实要规约出我们需要的error其实不一定要这么多约束，尝试一下会发现只取其中150组对应的等式，用BKZ(block_size=12)都可以相当稳定的规约出来了。而只要能求出超过$s_2$变量数93的error，就可以解出$s_2$来。

总的来说这道题虽然不长，但可以研究的东西其实相当多，基本上用上了目前知道的大部分规约优化:)

ZKPQC 1

题目描述：

Prove to me that you are a master of isogeny.

The version of SageMath is 10.5 in remote server.

题目：

import signal
from hashlib import sha256
from Crypto.Util.number import bytes_to_long
from secret import FLAG

def _handle_timeout(signum, frame):
    raise TimeoutError('function timeout')

FAKE_NUM = 3

# Base field
a = 49
b = 36
p = 2**a * 3**b - 1


def get_canonical_basis(E, l, e):
    assert (p+1) % l^e == 0
    P = E(0)
    while (l^(e-1))*P == 0:
        P = ((p+1) // l^e) * E.random_point()
    Q = P
    while P.weil_pairing(Q, l^e)^(l^(e-1)) == 1:
        Q = ((p+1) // l^e) * E.random_point()
    return P, Q

def gen_torsion_points(E):
    Pa, Qa = get_canonical_basis(E, 2, a)
    Pb, Qb = get_canonical_basis(E, 3, b)
    return Pa, Qa, Pb, Qb


def hash_function(J):
    return (bytes_to_long(sha256(str(J[0]).encode()).digest()) // 2 * 2 + 1)  % 2^a, \
        (bytes_to_long(sha256(str(J[1]).encode()).digest()) // 2 * 2 + 1) % 2^a


def get_Fp2(i):
    return int(input()) + int(input())*i


def get_ECC_and_points():
    Ea4 = get_Fp2(i)
    Ea6 = get_Fp2(i)
    Ea = EllipticCurve(Fp2, [0, 6, 0, Ea4, Ea6])
    P = Ea(get_Fp2(i), get_Fp2(i))
    Q = Ea(get_Fp2(i), get_Fp2(i))
    return Ea, P, Q


class ZKP:

    def __init__(self, E, kernel):
        self.P0, self.Q0 = get_canonical_basis(E, 3, b)
        self.E0 = E
        self.chall_lst = []
        self.CHALL_NUM = 16
        self.kernel = kernel
        self.ker_phi = self.E0.isogeny(self.kernel, algorithm="factored")
        print(f"{self.P0 = }")
        print(f"{self.Q0 = }")


    def _commit(self):
        print("Give me E2:")
        E2a4 = get_Fp2(i)
        E2a6 = get_Fp2(i)
        self.E2 = EllipticCurve(Fp2, [0, 6, 0, E2a4, E2a6])

        self.P2, self.Q2 = get_canonical_basis(self.E2, 3, b)
        print(f"{self.P2 = }")
        print(f"{self.Q2 = }")

        self.E3, self.P3, self.Q3 = get_ECC_and_points()
        assert self.E3.is_supersingular()


    def _challenge(self, c=None):
        if c is None:
            self.chall = randint(0,1)
        else:
            self.chall = c
        print(f"chall = {self.chall}")


    def _verify(self):
        print("Your response:")

        if self.chall:
            Kphi_ = self.E2(get_Fp2(i), get_Fp2(i))
            assert 2^a * self.E2(Kphi_) == self.E2(0)
            phi_ = self.E2.isogeny(Kphi_, algorithm="factored")
            assert self.E3.j_invariant() == phi_.codomain().j_invariant()
            assert phi_(self.P2) == self.P3 and phi_(self.Q2) == self.Q3
        else:
            resp = input()
            sigma, delta = [int(_) for _ in resp.split(",")]
            Kbar_psi = sigma * self.P2 + delta * self.Q2
            Kbar_psi_ = sigma * self.P3 + delta * self.Q3
            assert 3^b * Kbar_psi == self.E2(0) and 3^b * Kbar_psi_ == self.E3(0)
            E0_ = self.E2.isogeny(Kbar_psi, algorithm="factored").codomain()
            E1_ = self.E3.isogeny(Kbar_psi_, algorithm="factored").codomain()
            assert E0.j_invariant() == E0_.j_invariant() and EA.j_invariant() == E1_.j_invariant()
            assert self.ker_phi.codomain().j_invariant() == E1_.j_invariant()
        return True


    def run(self):
        self.chall_lst = [randint(0,1) for _ in range(self.CHALL_NUM)]
        while sum(self.chall_lst) == 0 or sum(self.chall_lst) == self.CHALL_NUM:
            self.chall_lst = [randint(0, 1) for _ in range(self.CHALL_NUM)]

        for _ in range(self.CHALL_NUM):
            print(f"Now, for the {_} round of PoK:")
            self._commit()
            self._challenge(self.chall_lst[_])
            if not self._verify():
                return False
        return True

timeout = 90
signal.signal(signal.SIGALRM, _handle_timeout)
signal.alarm(timeout)

Fpx = PolynomialRing(GF(p), "x")
x = Fpx.gen()
Fp2.<i> = GF(p**2, modulus=[1,0,1])

E0 = EllipticCurve(Fp2, [0, 6, 0, 1, 0])
E0.set_order((p+1)**2)

Pa,Qa,Pb,Qb = gen_torsion_points(E0)
print(f"Pa = {Pa}")
print(f"Qa = {Qa}")
print(f"Pb = {Pb}")
print(f"Qb = {Qb}")

Ea, phiPb, phiQb = get_ECC_and_points()
assert Ea.is_supersingular()

Sb = randint(0, 3^b-1)
Tb = randint(0, 3^b-1)
R = Sb * Pb + Tb * Qb
psi = E0.isogeny(R, algorithm="factored")
Eb, psiPa, psiQa = psi.codomain(), psi(Pa), psi(Qa)
print(f"{Eb}")
print(f"psiPa = {psiPa}")
print(f"psiQa = {psiQa}")

J = Ea.isogeny(Sb * phiPb + Tb * phiQb, algorithm="factored").codomain().j_invariant()
Sa, Ta = hash_function(J)
EA = E0.isogeny(Sa * Pa + Ta * Qa, algorithm="factored").codomain()

s = set()
for _ in range(FAKE_NUM):
    print("Give me your share: ")

    kernel = E0(get_Fp2(i), get_Fp2(i))
    assert 2^a * kernel == E0(0) and 2^(a-2) * kernel != E0(0)
    zkp = ZKP(E0, kernel)

    if all(kernel.weil_pairing(PP, 2^a) != 1 for PP in s) and zkp.run():
        print("Good Job!")
        s.add(kernel)
    else:
        print("Out, you are cheating!")
        break

if len(s) == FAKE_NUM:
    print("You are a master of isogeny and ZKP.")
    print(FLAG)

题目基于isogeny的ZKP，题目流程相当长所以不梳理了，直接进做法。

对于题目中的一些量，后面均会用这样表示：

• 题目中的起始曲线E0 = EllipticCurve(Fp2, [0, 6, 0, 1, 0])，我不记作$E_0$，而记作$E_6$
• $E_0$记为$y^2=x^3+x$这条曲线
• 题目中的EA = E0.isogeny(Sa * Pa + Ta * Qa, algorithm="factored").codomain()，这个秘密同源的kernel记为$RA$

大致来说，题目是完成了这篇文章section5.1对应的一个ZK：

1023.pdf (iacr.org)

唯一的区别在于chall=0的最后一行，题目多了一个判断是：

assert self.ker_phi.codomain().j_invariant() == E1_.j_invariant()

而我们要解决下面几个问题：

• 拿到SIDH协议交换的共享密钥$J$，并计算出$E_A$以及$RA$

• 找到三个weil配对互不相同且阶为$2^a$或$2^{a-1}$的kernel，这三个kernel都需要满足：

  EA.j_invariant() = E0.isogeny(kernel, algorithm="factored").codomain().j_invariant()

  也就是在同构意义下，这些kernel都要使E0走到EA，这也就是题目多的那个判断

  显然RA是其中一个

• 通过ZKP

把这三个问题记为问题1、2、3分别来解决。

问题1

在进入ZKP前，题目先走了一遍SIDH的协议得到共享密钥$J$，并用$J$做哈希，计算出了最后的$RA$并得到$EA$。

虽然没有Bob的私钥，但是由于我们在协议里扮演的是Alice，因此我们可以很轻松的从Bob的公钥计算出$J$。

这里赛中我是真的犯大病了，由于要输入的东西太多，所以脑袋很昏，先后想了下面两个办法求$J$。第一个办法是：

• 令$E_a$为$E_6$以$3P_b$为kernel同源到的曲线
• 此时，在$S_b$为3的倍数且$T_b$不为3的倍数的时候，用于从$E_a$出发计算$E_{ab}$的kernel等价于$\phi_a(Q_b)$，就可以计算出私钥了，这个概率为$\frac{2}{9}=\frac{1}{3}\frac{2}{3}$

第二个方法更笨，直接调个CD attack求Bob的私钥，大概要四五十秒XD

赛后@hash_hash跟我说直接走协议就可以拿$J$的时候我恍然大悟，实在没绷住赛中究竟是怎么想的，可能被过多的输入搞昏了

问题3

之所以先说问题3原因很简单，问题3只需要照着论文走一遍流程即可，大概流程图和协议框架为：

这个协议走一遍并不麻烦，完全照着步骤一步步写就好了。

但其实我赛中第一反应并不是这么做的，由于对输入的限制并不是很严格，所以完全可以这样bypass：

• $E_2$直接取为$E_6$，$E_3$对应就取为$E_A$，此时$E_2$到$E_3$的同源就是$E_6$到$E_A$的
• chall=1时对应把给的$P_2,Q_2$做映射到$E_3$就得到$P_3,Q_3$
• chall=0时，可以令$\sigma, \delta$均为0，此时kernel都是无穷远点$O$，所以均会同源到自身，就可以通过challenge

然而我还是实现了一遍，因为赛中觉得可能这个协议会和问题2有关。

问题2

这个问题最麻烦，由于$RA$显然是个符合要求的kernel，所以我们实际要找的是两个kernel，他们要满足下面的限制：

• 两两weil配对值不为1
• 阶要为$2^a$或者$2^{a-1}$
• 要满足同构意义下$E_6$走到$E_A$

比赛的时候看到这里相当懵，没啥思路，卡着卡着@deebato提到了自同构。

想了一下确实有道理，主要在于：

• $E_6$有个2-isogeny的邻居$E_0$，也就是$y^2 = x^3+x$，把这个2-isogeny记为$\Phi_1$
• 在$E_0$上存在一个已知的非平凡自同构$\textbf{i}: (x, y) \rightarrow (-x, iy)$，把这个自同构记为$\Phi_2$
• $\Phi_1$的对偶$\hat{\Phi_1}$可以将$E_0$走回$E_6$

而把这三个映射复合起来，可以得到$E_6$的自同态环的一个特殊元素，也就是$2\textbf{i}$。那么当$RA$对应的同源路径恰好会经过$E_0$时，将$RA$通过$\Phi_1$走到$E_0$得到$\Phi_1(RA)$，此时对他做非平凡自同构$\textbf{i}$之后再映射回去，这样最终得到的kernel就应该和$RA$是等价的。

事实也确实如此，然而这样会发现得到的kernel阶会是$2^{a-2}$的，不符合题意。

这个时候瞎测一下会发现对$\Phi_1(RA)$的2阶division points做映射回来就可以符合要求，阶是$2^a$或者$2^{a-1}$的，然而符合weil配对要求的只有一个，也就是说现在我们可以通过前两次了。

继续瞎测会发现一个更令人震惊的事实：对于$\Phi_1(RA)$的2阶division points做映射回来不符合要求的那些点，加上一个$RA$居然就可能符合要求了，此时就找到了第三个点。

而要成功，对$RA$是有一定要求的，不过反复重连就可以了。

exp

###################################################################### exp
context.log_level = "critical"

while(1):
    try:
        print(1)
        sh = remote("instance.penguin.0ops.sjtu.cn", 18433)
        #sh = process(["sage", "task.sage"])

        Pa = convert_2_point(E0, sh.recvline().strip().decode()[5:])
        Qa = convert_2_point(E0, sh.recvline().strip().decode()[5:])
        Pb = convert_2_point(E0, sh.recvline().strip().decode()[5:])
        Qb = convert_2_point(E0, sh.recvline().strip().decode()[5:])

        ###################################################################### part1 send Ea, phiPb, phiQb
        phi = E0.isogeny(3*Pb, algorithm="factored")
        Ea, phiPb, phiQb = phi.codomain(), phi(Pb), phi(Qb)
        sendFp2(Ea.a4())
        sendFp2(Ea.a6())
        sendFp2(phiPb.x())
        sendFp2(phiPb.y())
        sendFp2(phiQb.x())
        sendFp2(phiQb.y())

        if(1):
            sh.recvuntil(b"Elliptic Curve defined by y^2 = x^3 + 6*x^2 + ")
            Eb = sh.recvline().strip().decode().strip(" over Finite Field in i of size 84495767949234467194240606666751^2").split("*x + ")
            Eb = EllipticCurve(Fp2, [0, 6, 0, eval(Eb[0][1:-1]), eval(Eb[1][1:-1])])
            psiPa = convert_2_point(Eb, sh.recvline().strip().decode()[8:])
            psiQa = convert_2_point(Eb, sh.recvline().strip().decode()[8:])


        ###################################################################### part2 get EA
        J = Ea.isogeny(phiQb, algorithm="factored").codomain().j_invariant()
        Sa, Ta = hash_function(J)
        RA = Sa * Pa + Ta * Qa
        assert RA.weil_pairing(E0(1,2^26*3^18), 2^a) == p-1
        EA = E0.isogeny(RA, algorithm="factored").codomain()

        def find_equ_ker(RA):
            Ej = EllipticCurve(Fp2, [0, 0, 0, 1, 0])
            phi1 = E0.isogeny(E0(0, 0),  algorithm="factored").codomain().isomorphism_to(Ej)*E0.isogeny(E0(0, 0))
            TT = [RA]
            for j in Ej.automorphisms()[3:]:
                PHI = phi1.dual()*j
                for kk in phi1(RA).division_points(2):
                    if(E0.isogeny(PHI(kk),  algorithm="factored").codomain().j_invariant() == EA.j_invariant()):
                        if(PHI(kk).order() > 2^(a-2)):
                            TT.append(PHI(kk))
                    if(E0.isogeny(PHI(kk)+RA,  algorithm="factored").codomain().j_invariant() == EA.j_invariant()):
                        if((PHI(kk)+RA).order() > 2^(a-2)):
                            TT.append(PHI(kk)+RA)
                
            TT = list(set(TT))
            for tt in range(len(TT)):
                for kk in range(tt, len(TT)):
                    for rr in range(kk, len(TT)):
                        if(TT[tt].weil_pairing(TT[kk], 2^a) != 1 and TT[rr].weil_pairing(TT[tt], 2^a) != 1 and TT[rr].weil_pairing(TT[kk], 2^a) != 1):
                            print()
                            return TT[kk], TT[tt], TT[rr]

        li = find_equ_ker(RA)

        ###################################################################### part3 ZKP
        for j in range(3):
            ppa,qqa = get_canonical_basis(E0, 3, b)

            while(1):
                ker = randint(0,p)*ppa + randint(0,p)*qqa
                if(ker.order() == 3^b):
                    break
            Φ2 = E0.isogeny(ker, algorithm="factored")
            E2 = Φ2.codomain()

            sh.recvuntil(b"Give me your share: ")
            sendFp2(li[j].x())
            sendFp2(li[j].y())


            for _ in trange(16):
                sh.recvuntil(b"Give me E2:\n") # send E0
                sendFp2(E2.a4())
                sendFp2(E2.a6())
                P2 = convert_2_point(E2, sh.recvline().strip().decode()[10:])
                Q2 = convert_2_point(E2, sh.recvline().strip().decode()[10:])

                KΦ = Φ2(li[j])
                Φ3 = E2.isogeny(KΦ, algorithm="factored")
                E3 = Φ3.codomain()
                P3, Q3 = Φ3(P2),Φ3(Q2)

                sendFp2(E3.a4())
                sendFp2(E3.a6())
                sendFp2(P3.x())
                sendFp2(P3.y())
                sendFp2(Q3.x())
                sendFp2(Q3.y())

                chall = sh.recvline()
                if(b"0" in chall):
                    sh.recvuntil(b"Your response:\n")
                    while(1):
                        ttt = 2^a*E0.random_element()
                        if(ttt.weil_pairing(ker, 3^b)^(3^(b-1)) != 1 and ttt.weil_pairing(ker, 3^b)^(3^b) == 1):
                            Kker = Φ2(ttt)
                            if(Kker.order() == 3^b):
                                break
                    Kbar_psi = E2.isogeny(Kker, algorithm="factored")
                    assert E0.j_invariant() == Kbar_psi.codomain().j_invariant() # dual
                    d = discrete_log(Kker.weil_pairing(P2, 3^b), Q2.weil_pairing(P2, 3^b), ord=3^b, operation="*")
                    c = discrete_log(Kker.weil_pairing(Q2, 3^b), P2.weil_pairing(Q2, 3^b), ord=3^b, operation="*")
                    assert c*P2 + d*Q2 == Kker
                    sh.sendline((str(c)+","+str(d)).encode())

                elif(b"1" in chall):
                    sh.recvuntil(b"Your response:\n")
                    sendFp2(KΦ.x())
                    sendFp2(KΦ.y())
            print(sh.recvline())

        print(sh.recvline())
        print(sh.recvline())
        print(sh.recvline())

    except:
        pass


#0ops{https://eprint.iacr.org/2022/475.pdf_1s_ju5t_a_proof_0f_know1edge.>.<.././././}\n

思考

赛后和@hash_hash讨论了一下，发现这样的做法基于一个事实：

• $E_0$这个曲线非常特殊，他有一个2-isogeny的邻居是他自己

在我之前写的关于同源的笔记有提到过这种，比如这副同源图中的4这个节点：

他自己到自己有一个环路，所以放回到题目来说，$RA$的特殊性可以具体化为：

• 包含$E_0 \rightarrow E_0$这种环路

而找等价同源的方法就是拆除掉这种环路，比如如果把：

$$E_6 \rightarrow E_0 \rightarrow E_0 \rightarrow E_6$$

拆成：

$$E_6 \rightarrow E_0 \rightarrow E_6$$

而后续路径不变，那么同源的终点自然还是$E_A$，但是同源路径的长度减少了1，与之对应的，同源的度就减少了1，kernel的阶也就从$2^a$降低到了$2^{a-1}$，要做的仅仅是对于拆除后的新路径，计算出他在$E_6$对应的kernel就可以了。

而实际上如果真的包含这种环路的话：

$$E_6 \rightarrow E_0 \rightarrow E_0 \rightarrow E_6$$

那么可以同时找到阶$2^a,2^{a-1},2^{a-2},2^{a-3}$的kernel，相当有意思。

dbot

题目描述：

I don't bother to know what is OT

题目：

from Crypto.Util.number import getPrime, bytes_to_long, inverse
from Crypto.Random.random import randrange, getrandbits
from math import prod
from secret import FLAG
import os
import signal


def _handle_timeout(signum, frame):
    raise TimeoutError('function timeout')

timeout = 600
signal.signal(signal.SIGALRM, _handle_timeout)
signal.alarm(timeout)

def Level(level, primes, ROUND):
    print(f"This is level {level}!")
    N = prod(primes)
    phi = prod([(pp - 1) for pp in primes])
    d = inverse(0x10001, phi)
    m = bytes_to_long(os.urandom(N.bit_length() // 8 - 2))
    
    c = pow(m, 0x10001, N)

    idx = int(input("Choose one prime you prefer: "))
    assert idx in list(range(len(primes))), "No such prime"
    mod = primes.pop(idx)
    print(f"Here is your prime: {mod}")
    print(f"{c = }")
    print(f"{N = }")

    if level == 0:
        a = [getrandbits(496) for _ in range(ROUND)]
        b = getrandbits(248)
        c = [getrandbits(496) for _ in range(ROUND)]
        e = b
        ph1 = [prod([(primes[0] + a[i]), (primes[1] + b)]) for i in range(ROUND)]
        ph2 = [prod([(-primes[0] + c[i]), (primes[1] + e)]) for i in range(ROUND)]
    else:
        a = [getrandbits(160) for _ in range(ROUND)]
        b = a
        c = [ai + 1 for ai in a]
        e = c
        ph1 = [prod([(primes[0] + a[i]), (primes[1] + b[i])]) for i in range(ROUND)]
        ph2 = [prod([(primes[0] - c[i]), (primes[1] + e[i])]) for i in range(ROUND)]

    for i in range(ROUND):
        x0 = randrange(0, N)
        x1 = randrange(0, N)
        print(f"{x0 = }")
        print(f"{x1 = }")
        v = int(input("Give me v: "))
        m0 = (pow(v - x0, d, mod) + ph1[i]) % mod
        m1 = (pow(v - x1, d, mod) + ph2[i]) % mod
        print(f"{m0 = }")
        print(f"{m1 = }")
    m_ = int(input("Give me m: "))
    if m_ == m:
        print("Good job!")
        return True
    else:
        print("Try again!")
        return False


primes1 = [getPrime(512) for _ in range(3)]
primes2 = [getPrime(512) for _ in range(4)]
if Level(0, primes1, 80) and Level(1, primes2, 80):
    print("This is your flag:", FLAG)

一个需要通过两个level的OT协议，自然就分成两个问题来讲了。

level0

level0的数据有：

• 3个素数，记为$p,q,r$，可以获得其中一个，不妨就获取$r$，并且有他们的乘积$N=pqr$
• 两个长为ROUND=80的列表$a,c$，均为496bit的数字组成
• 一个248bit的数字$b$

每一次OT对应的两个量分别是：

• $ph_1 = (p+a_i)(q+b)$
• $ph_2 = (c_i-p)(q+b)$

OT看上去就是正常的RSA的OT，所以一次交互要么老老实实拿其中一个，要么拿$k\cdot ph_1 + ph_2$这种形式的和。

事实上这完全不正常，level1里面再讲XD

一个很简单的想法是直接令$v = \frac{x_0+x_1}{2}$，这样把$m_0$和$m_1$加起来就可以拿两者的和，也就是：

$$h_i = (p+a_i)(q+b) + (c_i-p)(q+b) \quad(mod\;r)$$

显然可以合并一下系数得到：

$$h_i = (c_i+a_i)(q+b) \quad(mod\;r)$$

移项就变成：

$$(q+b)^{-1}h_i = c_i+a_i \quad(mod\;r)$$

由于$a_i+c_i$也就是497bit数量级的，所以这个问题可以转化成HNP来做，然后就可以拿到$q+b$的值，记为$K$。

而由于$b$更小，仅有248bit，所以相当于如下方程在模$q$下有个248bit的小根：

$$f = K - x$$

而由于$q$本身是个素数，所以可以从$K$的LSB判断出$b$的LSB，因此方程可以进一步变为：

$$f = K - 2x \quad or \quad f = K - 2x - 1$$

此时小根是247bit的，因此可以用X=2^247, beta=0.499,epsilon=0.016这个参数花三四秒钟时间高概率copper解决，得到$q$之后就可以求解出level0的明文了。

level1

level1的数据有：

• 4个素数，记为$p,q,r,s$，可以获得其中一个，不妨就获取$r$，并且有他们的乘积$N=pqrs$
• 一个长为ROUND=80的列表$a$，均为160bit的数字组成

每一次OT对应的两个量分别是：

• $ph_1 = (p+a_i)(q+a_i)$
• $ph_2 = (p-a_i-1)(q+a_i+1)$

我的第一个思路是MT，因为level0中[getrandbits(496) for _ in range(ROUND)]这样的生成方式实在太显眼了，似乎可以预测level1中的所有值。

然而实际上，由于题目使用的是from Crypto.Random.random import randrange, getrandbits而不是from random import getrandbits，而@WCjrCK尝试了一下发现说题目的调用会不断更新state，所以就没办法预测了。

但是@WCjrCK注意到了这样一个问题，由于OT的值是模$r$下的，这是一个素数，而不是通常来说未知分解的合数，因此：

$$m_0 = (v - x_0)^d + ph_1 \quad (mod\;r)$$ $$m_1 = (v - x_1)^d + ph_2 \quad (mod\;r)$$

这里面的$d$在模$r$下是可以算的，因此我们完全可以拿到所有的$ph_1$和$ph_2$，而又因为每次能拿到两个方程，却只新增一个变量$a_i$，所以只要方程比变量多的时候就可以很轻松的用groebner解掉了，所以三组就行。

但这很显然是个非预期，因为题目给了600s的timeout，然而实际上两个level加起来也就几秒钟，预期是正交格+copper，可以参考官方的wp：

ctf-challenge/0CTF2024/dbot at main · sh1k4ku/ctf-challenge (github.com)

exp

####################################################################### exp
from Crypto.Util.number import *

def sol_0(phis, N, c, mod):
    M = Matrix(ZZ, 82, 82)
    for i in range(80):
        M[i, i] = mod
        M[-2, i] = -phis[i]
        M[-1, i] = -2^496
    M[-2, -2] = 1
    M[-1, -1] = 1

    Q = diagonal_matrix(ZZ, [2^15]*80 + [1] + [mod])
    M = M * Q
    M = M.LLL()
    M = M / Q
    M = Matrix(ZZ, M)
    for i in M:
        if(i[-1] == -1 and abs(i[-2])> 2^500):
            Kinv = int(i[-2])
            K = int(inverse(Kinv, mod))
            while(len(bin(K)[2:]) < 512):
                K += mod
            break
        elif(i[-1] == 1 and abs(i[-2])> 2^500):
            Kinv = mod-int(i[-2])
            K = int(inverse(Kinv, mod))
            while(len(bin(K)[2:]) < 512):
                K += mod
            break

    pq = N // mod
    Psh.<x> = PolynomialRing(Zmod(pq))
    f = K - 2*x
    if(K % 2 == 0):
        f -= 1
    f = f.monic()
    res = f.small_roots(X=2^247, beta=0.499,epsilon=0.016)
    if(res != []):
        q = gcd(int(f(res[0])),pq)
        p = (N//mod)//q
        primes = [p,q,mod] 
        phi = prod([(pp - 1) for pp in primes])
        d = int(inverse(0x10001, phi))
        m = int(pow(c,d,N))
        return m

    return None

def sol_1(hints, hints2, m0_list, m1_list, N, c, mod):
    PR.<p, q, a1, a2, a3> = PolynomialRing(Zmod(mod))
    f10 = (p + a1)*(q + a1) - m0_list[0]
    f11 = (p - a1 - 1)*(q + a1 + 1) - m1_list[0]
    f20 = (p + a2)*(q + a2) - m0_list[1]
    f21 = (p - a2 - 1)*(q + a2 + 1) - m1_list[1]
    f30 = (p + a3)*(q + a3) - m0_list[2]
    f31 = (p - a3 - 1)*(q + a3 + 1) - m1_list[2]

    res = Ideal([f10, f11, f20, f21, f30, f31]).groebner_basis()
    p = mod-ZZ(res[0].univariate_polynomial()(0))
    q = mod-ZZ(res[1].univariate_polynomial()(0))
    while(len(bin(p)[2:]) < 512):
        p += mod
    while(len(bin(p)[2:]) < 512):
        q += mod
    
    assert isPrime(p) and isPrime(q)
    s = (N//mod)//q//p
    primes = [p,q,mod,s] 
    phi = prod([(pp - 1) for pp in primes])
    d = int(inverse(0x10001, phi))
    m = int(pow(c,d,N))
    return m

####################################################################### interactive
from pwn import process, remote, context
from Crypto.Util.number import *

context.log_level = "critical"
#sh = process(["python3","task.py"])
sh = remote("instance.penguin.0ops.sjtu.cn", 18432)

####################################################################### level 0
sh.recvuntil(b"Choose one prime you prefer: ")
sh.sendline(b'2')
sh.recvuntil(b"Here is your prime: ")
r = int(sh.recvline().strip().decode())
sh.recvuntil(b'c = ')
c = int(sh.recvline().strip().decode())
sh.recvuntil(b'N = ')
N = int(sh.recvline().strip().decode())
mod = r 
phis = []
for i in range(80):
    sh.recvuntil(b'x0 = ')
    x0 = int(sh.recvline().strip().decode())
    sh.recvuntil(b'x1 = ')
    x1 = int(sh.recvline().strip().decode())
    v = int((x0+x1) * inverse(2, N) % N)
    sh.recvuntil(b'Give me v: ')
    sh.sendline(str(v).encode())
    sh.recvuntil(b'm0 = ')
    m0 = int(sh.recvline().strip().decode())
    sh.recvuntil(b'm1 = ')
    m1 = int(sh.recvline().strip().decode())
    ph1i_ph2i = int((m0+m1) % mod)
    phis.append(ph1i_ph2i)

m0 = sol_0(phis, N, c, mod)
sh.recvuntil(b'Give me m: ')
sh.sendline(str(m0).encode())
print(sh.recvline())

####################################################################### level 1
sh.sendlineafter(b"prefer: ", b"3")
sh.recvuntil(b"prime: ")
mod = int(sh.recvline()[:-1].decode())
d1 = inverse(65537, mod - 1)
sh.recvuntil(b"c = ")
c = int(sh.recvline()[:-1].decode())
sh.recvuntil(b"N = ")
N = int(sh.recvline()[:-1].decode())
hints = []
hints2 = []
m0_list = []
m1_list = []
for i in range(80):
    sh.recvuntil(b"x0 = ")
    x0 = int(sh.recvline()[:-1].decode())
    sh.recvuntil(b"x1 = ")
    x1 = int(sh.recvline()[:-1].decode())
    v = (x0 + x1) * pow(2, -1, mod) % mod
    sh.sendlineafter(b"v: ", str(v).encode())
    sh.recvuntil(b"m0 = ")
    m0 = int(sh.recvline()[:-1].decode())
    m0 = (m0 - pow(v - x0, d1, mod)) % mod
    sh.recvuntil(b"m1 = ")
    m1 = int(sh.recvline()[:-1].decode())
    m1 = (m1 - pow(v - x1, d1, mod)) % mod
    hints.append((m0 + m1) % mod)
    hints2.append((m0 - m1) % mod)
    m0_list.append(m0)
    m1_list.append(m1)

m1 = sol_1(hints, hints2, m0_list, m1_list, N, c, mod)
sh.recvuntil(b'Give me m: ')
sh.sendline(str(m1).encode())
print(sh.recvline())
print(sh.recvline())


#0ops{oh------f4ke_OT_cant_d3c3ive_your_ey35.:o:p:d?.?./.}