0KPR00FScore: 101Crypto, difficulty:Normal
Sh0w me the pr00f that y0u understand 0kpr00f. If its 0k, i'll give y0u what y0u want!
nc 47.254.47.63 13337
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()
Ct = [t**0, t**1, t**2, t**3, t**4, t**5, t**6]となる。
PKC = [G1*t**0, G1*t**1, G1*t**2, G1*t**3, G1*t**4, G1*t**5, G1*t**6]
PKCa = [a*G1*t**0, a*G1*t**1, a*G1*t**2, a*G1*t**3, a*G1*t**4, a*G1*t**5, a*G1*t**6]
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
pairing(VKa, PiC) = pairing(G2, PiCa)となるPiC, PiCa, PiHを入力することでフラグを得ることができる。
pairing(G2, PiC) = pairing(VKz, PiH)
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
楕円曲線のペアリングの性質として、
e(P, Q+R) = e(P, Q)*e(P, R)より、
e(P+Q, R) = e(P, R)*e(Q, R)
e(a*P, Q) = e(P, a*Q) = e(P, Q)**a
pairing(VKa, PiC) = pairing(G2, PiCa)VKa = a*G2なので、pairing(VKa, PiC) = pairing(a*G2, PiC) = pairing(G2, a*PiC)
したがって、pairing(G2, PiC) = pairing(VKz, PiH)VKz = (t-1)*(t-2)*(t-3)*(t-4)*G2より、pairing(VKz, PiH) = pairing((t-1)*(t-2)*(t-3)*(t-4)*G2, PiH) = pairing(G2, (t-1)*(t-2)*(t-3)*(t-4)*PiH)
PiCa = a*PiCPiHにG1を適用することで、PiC, PiCa, PiHを求めることができる。
PiC = (t-1)*(t-2)*(t-3)*(t-4)*PiH = (t**4 - 10*t**3 + 35*t**2 - 50*t + 24)*PiH
PiH = G1PiH、PiC、PiCaを求めるプログラムは次の通り。
PiC = t**4*G1 - 10*t**3*G1 + 35*t**2*G1 - 50*t*G1 + 24*G1
= 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]
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
PK = ([(1, 2), (6951158980176023808672944052330889760482237855327193887807935495478570808642, 17908888220283291625531314275972104628236311407176528569109534955078754769105), (18901928226760644830513160068234084069922194040431438515132150914220828048108, 15654368433618756732770875139641381270966509158952057127466508623044552223548), (10402829170097144260590441127593915274060143821877921964578566788272400218808, 16945758728076495812604523985293120334237244493463161019483862214883437869437), (10882799501868362079687182580425887447643004994279269632588887193657945065681, 13584860258034637211660415483386320283321552331750096485350966687939605822059), (20338730205424621285473726618647183068251457802061517360093181360024919937798, 18041596372811728194793277057117328423603596981500611475592318838031136515948), (1908179672416088679548828039785263003841933793017957983485643138922098190694, 1461736854479442556312787492486542322267159405618254706198156788708298006119)], [(2755286556932053935732074074652948734719308587331382609322327363667944871556, 6443993305305179591670486209357610205344864402376428648159984658469938918416), (7281280718878434895774687564471683708914040684368975387001707493965619000127, 2468148688528445086289242182898381558066459201477704832289877907223065116665), (17899854767572753776559148635910658933704043743895643043967175639135936543672, 15128119548546358989344382389045909618233622936610346645129750311379239899113), (16921033913112737102481002928667683753884890325996253668788751068369739277097, 19353983169964573455451593298095160492409167433812498648213579879173651132781), (11335331284820005797549195812537509528738634517391069726828669994538127370901, 20145142547921108524982689259164728613327370901047022787078069009352392471024), (21440973202324113772836077051131572545181819246459224087082541174977455394815, 21778185593826989204928344332224528536705666523413412025139324875306121915229), (8066276198295105926861821968292432786280580634830298759620637288586361993983, 8951238231599903435597581357944487345101424624979642827105300367893202204224)])
PKC = [(FQ(a), FQ(b)) for a, b in PK[0]]
PKCa = [(FQ(a), FQ(b)) for a, b in PK[1]]
PiH = G1
PiC = PKC[4]
PiC = add(PiC, neg(multiply(PKC[3], 10)))
PiC = add(PiC, multiply(PKC[2], 35))
PiC = add(PiC, neg(multiply(PKC[1], 50)))
PiC = add(PiC, multiply(PKC[0], 24))
PiCa = PKCa[4]
PiCa = add(PiCa, neg(multiply(PKCa[3], 10)))
PiCa = add(PiCa, multiply(PKCa[2], 35))
PiCa = add(PiCa, neg(multiply(PKCa[1], 50)))
PiCa = add(PiCa, multiply(PKCa[0], 24))
print(PiC, PiCa, PiH)
b'===========================\n'b'=WELCOME TO 0KPR00F SYSTEM=\n'b'===========================\n'b'([(1, 2), (6951158980176023808672944052330889760482237855327193887807935495478570808642, 17908888220283291625531314275972104628236311407176528569109534955078754769105), (18901928226760644830513160068234084069922194040431438515132150914220828048108, 15654368433618756732770875139641381270966509158952057127466508623044552223548), (10402829170097144260590441127593915274060143821877921964578566788272400218808, 16945758728076495812604523985293120334237244493463161019483862214883437869437), (10882799501868362079687182580425887447643004994279269632588887193657945065681, 13584860258034637211660415483386320283321552331750096485350966687939605822059), (20338730205424621285473726618647183068251457802061517360093181360024919937798, 18041596372811728194793277057117328423603596981500611475592318838031136515948), (1908179672416088679548828039785263003841933793017957983485643138922098190694, 1461736854479442556312787492486542322267159405618254706198156788708298006119)], [(2755286556932053935732074074652948734719308587331382609322327363667944871556, 6443993305305179591670486209357610205344864402376428648159984658469938918416), (7281280718878434895774687564471683708914040684368975387001707493965619000127, 2468148688528445086289242182898381558066459201477704832289877907223065116665), (17899854767572753776559148635910658933704043743895643043967175639135936543672, 15128119548546358989344382389045909618233622936610346645129750311379239899113), (16921033913112737102481002928667683753884890325996253668788751068369739277097, 19353983169964573455451593298095160492409167433812498648213579879173651132781), (11335331284820005797549195812537509528738634517391069726828669994538127370901, 20145142547921108524982689259164728613327370901047022787078069009352392471024), (21440973202324113772836077051131572545181819246459224087082541174977455394815, 21778185593826989204928344332224528536705666523413412025139324875306121915229), (8066276198295105926861821968292432786280580634830298759620637288586361993983, 8951238231599903435597581357944487345101424624979642827105300367893202204224)])\n'b'now give me your proof\n'(21348779946651574597961960204512750391701998143752788884255868899236735890665, 19901659748119950009164763102312342484229400563449780547593779415410533167802) (647121105526769008859192496408882822606951812640292730048477416083000546744, 3836740433026658496669540696629457982221173205425799331909096872890670417671) (1, 2)b'Congratulations!Here is flag:rwctf{How_do_you_feel_about_zero_knowledge_proof?}\n'
