CTF-CRYPTO
椭圆加密
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比较小,而且有多个点,所以我们才用bsgs
设求解
\[a^x \equiv b\mod p \]\[a^{im+j}\equiv b\ mod \ p \]\[a^j\equiv b*a^{-im}\ mod\ p \]\[a^j\equiv b*(a^{(-m)i}) \ mod\ p \]只要找到一组i,j使得最后一个式子成立就行
通过枚举j,递推出a^j mod p的乘法逆元 枚举i,递推出所有等式右边,每得到一个值后,从hash表中查找该值,如果存在,取出其对应的j,x=im+j,就是要的值
具体操作详见
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)
标签:CRYPTO,yG,xG,CTF,mod,bsgs,equiv From: https://www.cnblogs.com/ink599/p/18667534