CTF-CRYPTO-ECC(2)

橢圓加密

4.BSGS(小步大步法)

[HITCTF 2021 ]

task.py

#Elliptic Curve: y^2 = x^3 + 7 mod N which is secp256k1

N = 2**256-2**32-2**9-2**8-2**7-2**6-2**4-1

E = EllipticCurve(GF(N), [0, 7])

xG = 0x79be667ef9dcbbac55a06295ce870b07029bfcdb2dce28d959f2815b16f81798

yG = 0x483ada7726a3c4655da4fbfc0e1108a8fd17b448a68554199c47d08ffb10d4b8

G = (xG,yG)

n = [secret0,secret1,secret2]

#flag = "HITCTF2021{"+''.join([hex(i) for i in n])

for i in n:

    assert i<1048575

    print(i*G)

cipher0 = (76950424233905085841024245566087362444302867365333079406072251240614685819574 , 85411751544372518735487392020328074286181156955764536032224435533596344295845)

cipher1 = (42965775717446397624794967106656352716523975639425128723916600655527177888618 , 32441185377964242317381212165164045554672930373070033784896067179784273837186)

cipher2 = (26540437977825986616280918476305280126789402372613847626897144336866973077426 , 1098483412130402123611878473773066229139054475941277138170271010492372383833)

assert n[0]*G == cipher0

assert n[1]*G == cipher1

assert n[2]*G == cipher2

#Find n and recover the flag. Good luck!

這題的有N比較小，而且有多個(gè)點(diǎn)，所以我們才用bsgs

設(shè)求解

只要找到一組i,j使得最后一個(gè)式子成立就行

通過枚舉j，遞推出a^j mod p的乘法逆元 枚舉i，遞推出所有等式右邊，每得到一個(gè)值后，從hash表中查找該值，如果存在，取出其對應(yīng)的j，x=im+j，就是要的值

具體操作詳見

https://oi.men.ci/bsgs-notes/

EXP

from sage.groups.generic import bsgs

N = 2**256-2**32-2**9-2**8-2**7-2**6-2**4-1

E = EllipticCurve(GF(N), [0, 7])

xG = 0x79be667ef9dcbbac55a06295ce870b07029bfcdb2dce28d959f2815b16f81798

yG = 0x483ada7726a3c4655da4fbfc0e1108a8fd17b448a68554199c47d08ffb10d4b8

G = E([xG,yG])

cipher0 = E([76950424233905085841024245566087362444302867365333079406072251240614685819574 , 85411751544372518735487392020328074286181156955764536032224435533596344295845])

cipher1 = E([42965775717446397624794967106656352716523975639425128723916600655527177888618 , 32441185377964242317381212165164045554672930373070033784896067179784273837186])

cipher2 = E([26540437977825986616280918476305280126789402372613847626897144336866973077426 , 1098483412130402123611878473773066229139054475941277138170271010492372383833])

m1 = bsgs(G,cipher0,(1,1000000),operation='+')

m2 = bsgs(G,cipher1,(1,1000000),operation='+')

m3 = bsgs(G,cipher2,(1,1000000),operation='+')

print(m1,m2,m3)

n = [m1,m2,m3]

flag = "NSSCTF{" + ''.join([hex(i)[2:] for i in n])+"}"

print(flag)

總結(jié)

以上是生活随笔為你收集整理的CTF-CRYPTO-ECC(2)的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。