姜姜酱 |

rwctf2023体验赛/正赛 crypto writeup

2023-01-10

babyCurve

#!/usr/bin/env python3
from random import randrange
from Crypto.Cipher import AES

p = 193387944202565886198256260591909756041

i = lambda x: pow(x, p-2, p)

def add(A, B):
    (x1, y1), (x2, y2) = A, B
    assert x1 != x2 or y1 == y2
    if x1 == x2: m = (3*x1*x2 + 4*x1 + 1) * i(y1+y2)
    else: m = (y2-y1) * i(x2-x1)
    y = m*m - x1 - x2 - 2
    z = m*(x1-y) - y1
    return y % p, z % p

def mul(t, A, B=0):
    if not t: return B
    return mul(t//2, add(A,A), B if not t&1 else add(B,A) if B else A)

x = randrange(p)
aes = AES.new(x.to_bytes(16, 'big'), AES.MODE_CBC, bytes(16))
flag = open('flag.txt').read().strip()
cipher = aes.encrypt(flag.ljust((len(flag)+15)//16*16).encode())
print(*mul(x, (4, 10)), cipher.hex(), file=open('flag.enc', 'w'))

'''
65639504587209705872811542111125696405 125330437930804525313353306745824609665 b3669dc657cef9dc17db4de5287cd1a1e8a48184ed9746f4c52d3b9f8186ec046d6fb1b8ed1b45111c35b546204b68e0
'''

hxp2018原题基础上有小改动。关键要求出AES的密钥$x$，也就是提供的点关于点$(4,10)$的离散对数(ECDLP)。主要思路首先是由曲线通项公式和add()函数判断出曲线表达式：

$y^2\equiv x^3+2x^2+x\equiv x(x+1)^2(\bmod p)$

一般定义的椭圆曲线方程$y^2=x^3+ax+b$要求系数满足$4a^3+27b^2\not = 0$。这样的椭圆曲线存在渐近线。当$4a^3+27b^2 = 0$，此时椭圆曲线是一种退化后的形式，称为奇异曲线(singular curve)，分两种情况讨论：

$a=b=0$，两段曲线交于$(0,0)$一点，且在交点处的两条切线重合，这样的点称为尖点(cusp)

$a,b\not =0$，两段曲线交于某一点，且在交点处的两条切线不重合，这样的点称为结点(node)

$F_p$上的奇异曲线与$p-1$阶乘法群同构，可以更快解决DLP。

注意到该曲线是一条singlar curve，将其映射到乘法群$F_p$上：

from random import randrange
from Crypto.Cipher import AES
from Crypto.Util.number import *

i = lambda x: pow(x, p-2, p)

def add(A, B):
    (x1, y1), (x2, y2) = A, B
    assert x1 != x2 or y1 == y2
    if x1 == x2: m = (3*x1*x2 + 4*x1 + 1) * i(y1+y2)
    else: m = (y2-y1) * i(x2-x1)
    y = m*m - x1 - x2 - 2
    z = m*(x1-y) - y1
    return y % p, z % p

def mul(t, A, B=0):
    if not t: return B
    return mul(t//2, add(A,A), B if not t&1 else add(B,A) if B else A)

p = 193387944202565886198256260591909756041
P.<x> = GF(p)[]
f = x^3 + 2*x^2 + x
P = (4, 10)
Q = (65639504587209705872811542111125696405, 125330437930804525313353306745824609665)

f_ = f.subs(x=x-1)

t = GF(p)(-1).square_root()
u = (P[1] - t * (P[0] + 1))/(P[1] + t * (P[0] + 1)) % p
v = (Q[1] - t * (Q[0] + 1))/(Q[1] + t * (Q[0] + 1)) % p
k = v.log(u)
x = k + u.multiplicative_order()
print(*mul(x, (4, 10)))
aes = AES.new(x.to_bytes(16, 'big'), AES.MODE_CBC, bytes(16))
flag = long_to_bytes(0xb3669dc657cef9dc17db4de5287cd1a1e8a48184ed9746f4c52d3b9f8186ec046d6fb1b8ed1b45111c35b546204b68e0)
cipher = aes.decrypt(flag)
print(cipher)

OKPROOF

#!/usr/bin/env python3

import signal
import socketserver
import string
import os
from secret import flag
from py_ecc import bn128

lib = bn128
FQ, FQ2, FQ12, field_modulus = lib.FQ, lib.FQ2, lib.FQ12, lib.field_modulus
G1, G2, G12, b, b2, b12, is_inf, is_on_curve, eq, add, double, curve_order, multiply = \
  lib.G1, lib.G2, lib.G12, lib.b, lib.b2, lib.b12, lib.is_inf, lib.is_on_curve, lib.eq, lib.add, lib.double, lib.curve_order, lib.multiply
pairing, neg = lib.pairing, lib.neg

LENGTH = 7


def Cx(x,length=LENGTH):
    res = []
    for i in range(length):
        res.append(pow(x,i,curve_order) % curve_order)
    return res

def C(x,y,length=LENGTH):
    assert len(x) == len(y) == length
    res = multiply(G1, curve_order)
    for i in range(length):
        res = add(multiply(x[i],y[i]),res) 
    return res 

def Z(x):
    return (x-1)*(x-2)*(x-3)*(x-4) % curve_order


def genK(curve_order,length=LENGTH):
    t = int(os.urandom(8).hex(),16) % curve_order
    a = int(os.urandom(8).hex(),16) % curve_order
    Ct = Cx(t)
    PKC = []
    for ct in Ct:
        PKC.append(multiply(G1, ct))
    PKCa = []
    for ct in Ct:
        PKCa.append(multiply(multiply(G1, ct), a))

    PK = (PKC,PKCa)
    VKa = multiply(G2, a)
    VKz = multiply(G2, Z(t))
    VK = (VKa,VKz)
    return PK,VK

def verify(proof,VK):
    VKa,VKz = VK
    PiC,PiCa,PiH = proof

    l = pairing(VKa, PiC)
    r = pairing(G2, PiCa)
    if l !=r:
        return False
    l = pairing(G2,PiC)
    r = pairing(VKz,PiH)
    if l !=r:
        return False
    return True


class Task(socketserver.BaseRequestHandler):
    def __init__(self, *args, **kargs):
        super().__init__(*args, **kargs)


    def OKPROOF(self,proof,VK):
        return verify(proof,VK)


    def dosend(self, msg):
        try:
            self.request.sendall(msg.encode('latin-1') + b'\n')
        except:
            pass

    def timeout_handler(self, signum, frame):
        raise TimeoutError

    def handle(self):
        try:
            signal.signal(signal.SIGALRM, self.timeout_handler)
            self.dosend('===========================')
            self.dosend('=WELCOME TO 0KPR00F SYSTEM=')
            self.dosend('===========================')
            PK,VK = genK(curve_order)
            self.dosend(str(PK))
            self.dosend('now give me your proof')
            msg = self.request.recv(1024).strip()
            msg = msg.decode('utf-8')
            tmp = msg.replace('(','').replace(')','').replace(',','')
            tmp = tmp.split(' ')
            assert len(tmp) == 6
            PiC = (FQ(int(tmp[0].strip())),FQ(int(tmp[1].strip())))
            PiCa = (FQ(int(tmp[2].strip())),FQ(int(tmp[3].strip())))
            PiH = (FQ(int(tmp[4].strip())),FQ(int(tmp[5].strip())))
            proof = (PiC,PiCa,PiH)
            if self.OKPROOF(proof,VK):
                self.dosend("Congratulations！Here is flag:"+flag)
            else:
                self.dosend("sorry")
            

        except TimeoutError:
            self.dosend('Timeout!')
            self.request.close()
        except:
            self.dosend('Wtf?')
            self.request.close()


class ThreadedServer(socketserver.ForkingMixIn, socketserver.TCPServer):
    pass

if __name__ == "__main__":
    HOST, PORT = '0.0.0.0', 13337
    server = ThreadedServer((HOST, PORT), Task)
    server.allow_reuse_address = True
    server.serve_forever()

题目中给出了要用到的bn128曲线的库py_ecc，提供的公钥$PK$(实际上是向量承诺)，所有元素都在$G_1$上，$a$是$\mathbb{Z}_p$上的随机数：

$\begin{aligned} PKC&=\{G_1^{t^0}, G_1^{t^1}, G_1^{t^2}, G_1^{t^3}, G_1^{t^4}, G_1^{t^5}, G_1^{t^6}\} \\ PKCa&=\{G_1^{t^0a}, G_1^{t^1a}, G_1^{t^2a}, G_1^{t^3a}, G_1^{t^4a}, G_1^{t^5a}, G_1^{t^6a}\} \end{aligned}$

验证密钥$VK$，所有元素都在$G_2$上:

$\begin{aligned} VKa&=G_2^a \\ VKz&=G_2^{(t-1)(t-2)(t-3)(t-4)} \end{aligned}$

成功条件是使得双线性配对$e:G_1\times G_2\rightarrow G_T$验证通过：

$\begin{aligned} e(G_2, PiC)&=e(G_2^{(t-1)(t-2)(t-3)(t-4)},PiH)\\ e(G_2^a,PiC)&=e(G_2,PiCa) \end{aligned}$

虽然不知道$t$和$a$的值，但可以利用返回的$PK$来构造$(PiC, PiCa,PiH)$。由双线性对的性质：

$\begin{aligned} PiC &= G_1^{(t-1)(t-2)(t-3)(t-4)}\\ PiH &= G_1 \\ PiCa &= G_1^{a(t-1)(t-2)(t-3)(t-4)} \end{aligned}$

sage代码：

# GF(p)
p = 21888242871839275222246405745257275088696311157297823662689037894645226208583

F1 = GF(p)
G1 = EllipticCurve(F1,[0,3])
P1 = G1(1,2)
rev = ([G1(1, 2), G1(12634587734867345779923022940292181443558285587050818763065229149202894039283, 10694431093643956247616156239776406618083705658003165544249763851117830634777), G1(19966160771227176410398522389691772605718481584431049081277968564299713462607, 4675694108236602701470610220829271602207702697669072707005068465960783999029), G1(5295595387360986098717588647519286285494204232232229640163321068642463197494, 5468404437624818015883608347372142659092450509816884367689767172835376362835), G1(12976516847948090440613452943665766191145343826830984063037221571706352413122, 21881532903998970231834756191425446971145510248658365275503409396400778709409), G1(20737086716279207343439321031990505834011873934955301190324476515781185779177, 5173539055331640470887541930947239331810487512515483313761449160512937425069), G1(8433948793372369642092002088663055366803076152745412986154550745360539646492, 3042518052342448279890913775197983226384042755194717968574699700013187454643)], [G1(21298034894188468253863936122397844807940040392978095681402771832942943111677, 4097298912181484378640845756789133350561837868426974714402807402569558743979), G1(18302718821486572691257585886518112531499674422732738024775374663775501512673, 597181006271960418091320972557859750483383974730836970677708879919553000193), G1(7006808936778869952427923784953840537499239953493031067400500956190062808388, 19427857033202464435310039030180575265354530861695818591549784617800916724611), G1(3418774925111105430768808332329589724534326657054333081710712814871406993772, 18435402000607857201600558020957994996270491122552058132591092200285832883030), G1(16891960009772082695253315359430973505206354034499655384028848566531817379191, 997421905222517397998456679072431794616100175877489093847111227566078909809), G1(17474948273843330972012911666456412407279451369959221598751487945085040098780, 17111745637366152502061819500253402626710495776069611237627548700747255267566), G1(9904286627956461874829859092452324772869766648459603411100874950699004998060, 7077337925663027667774728985408447182260312450030540489641964124790773462458)])
PKC,PKCa = rev[0], rev[1]
    
PiC = PKC[4] - 10 * PKC[3] + 35 * PKC[2] - 50 * PKC[1] + 24 * PKC[0]
PiCa = PKCa[4] - 10 * PKCa[3] + 35 * PKCa[2] - 50 * PKCa[1] + 24 * PKCa[0]
PiH = G1
print(str(PiC.xy()[0])+' '+ str(PiC.xy()[1]) + ' '+ str(PiCa.xy()[0]) + ' ' + str(PiCa.xy()[1]) + ' 1 2')

本文作者: 姜姜酱
本文链接: https://qsang.xin/2023/01/10/rwctf2023/
版权声明: 本网站所有文章除特别声明外,均采用 CC BY-NC-ND 4.0 许可协议。转载请注明出处!