[0CTF 2024]ZKPQC1

Problem: [0CTF 2024]ZKPQC1

题目基于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都要使E_0走到E_A，这也就是题目多的那个判断

  显然RA是其中一个

• 通过ZKP

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

问题1

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

虽然没有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

思考

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

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

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

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

• 包含E_0 \rightarrow E_0这种环路

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

拆成：

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

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

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