type
Post
status
Published
date
Jul 11, 2022
slug
ECC
summary
ECC
tags
Crypto
CTF
category
CRYPTO
icon
password
[HGAME 2022 week4]ECC
题目
#sage from Crypto.Util.number import getPrime from libnum import s2n from secret import flag p = getPrime(256) a = getPrime(256) b = getPrime(256) E = EllipticCurve(GF(p),[a,b]) m = E.random_point() G = E.random_point() k = getPrime(256) K = k * G r = getPrime(256) c1 = m + r * K c2 = r * G cipher_left = s2n(flag[:len(flag)//2]) * m[0] cipher_right = s2n(flag[len(flag)//2:]) * m[1] print(f"p = {p}") print(f"a = {a}") print(f"b = {b}") print(f"k = {k}") print(f"E = {E}") print(f"c1 = {c1}") print(f"c2 = {c2}") print(f"cipher_left = {cipher_left}") print(f"cipher_right = {cipher_right}") ''' p = 74997021559434065975272431626618720725838473091721936616560359000648651891507 a = 61739043730332859978236469007948666997510544212362386629062032094925353519657 b = 87821782818477817609882526316479721490919815013668096771992360002467657827319 k = 93653874272176107584459982058527081604083871182797816204772644509623271061231 E = Elliptic Curve defined by y^2 = x^3 + 61739043730332859978236469007948666997510544212362386629062032094925353519657*x + 12824761259043751634610094689861000765081341921946160155432001001819005935812 over Finite Field of size 74997021559434065975272431626618720725838473091721936616560359000648651891507 c1 = (14455613666211899576018835165132438102011988264607146511938249744871964946084 : 25506582570581289714612640493258299813803157561796247330693768146763035791942 : 1) c2 = (37554871162619456709183509122673929636457622251880199235054734523782483869931 : 71392055540616736539267960989304287083629288530398474590782366384873814477806 : 1) cipher_left = 68208062402162616009217039034331142786282678107650228761709584478779998734710 cipher_right = 27453988545002384546706933590432585006240439443312571008791835203660152890619 '''
只要求m就行了
c1=m + r * K=m+r * G * k
c2=r * G
m=c1-c2*k=m+r * G * k-r * G * k
exp
#sage from Crypto.Util.number import * p = 74997021559434065975272431626618720725838473091721936616560359000648651891507 a = 61739043730332859978236469007948666997510544212362386629062032094925353519657 b = 87821782818477817609882526316479721490919815013668096771992360002467657827319 k = 93653874272176107584459982058527081604083871182797816204772644509623271061231 E = EllipticCurve(GF(p),[a,b]) c1 = E(14455613666211899576018835165132438102011988264607146511938249744871964946084 , 25506582570581289714612640493258299813803157561796247330693768146763035791942) c2 = E(37554871162619456709183509122673929636457622251880199235054734523782483869931 , 71392055540616736539267960989304287083629288530398474590782366384873814477806) cipher_left = 68208062402162616009217039034331142786282678107650228761709584478779998734710 cipher_right = 27453988545002384546706933590432585006240439443312571008791835203660152890619 m=c1-c2*k cl=cipher_left//m[0] cr=cipher_right//m[1] print(long_to_bytes(int(cl))) print(long_to_bytes(int(cr)))
[HITCTF 2021]Baby ECC
题目
#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 = E(76950424233905085841024245566087362444302867365333079406072251240614685819574 , 85411751544372518735487392020328074286181156955764536032224435533596344295845) cipher1 = E(42965775717446397624794967106656352716523975639425128723916600655527177888618 , 32441185377964242317381212165164045554672930373070033784896067179784273837186) cipher2 = E(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!
exp
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) n=[] n.append(discrete_log(cipher0,G,operation='+')) n.append(discrete_log(cipher1,G,operation='+')) n.append(discrete_log(cipher2,G,operation='+')) flag = "HITCTF2021{"+''.join([hex(i) for i in n])
[ctfshow 击剑杯]依稀稀
题目
from Crypto.Util.number import * import random class Point: global p, a, b def __init__(self, x, y): self.x = x % p self.y = y % p def __str__(self): return f'({self.x}, {self.y})' def __add__(self, B): x1, y1, x2, y2 = self.x, self.y, B.x, B.y if (x1 == 0 and y1 == 0): return B if (x2 == 0 and y2 == 0): return self if (x1 == x2 and (y1 + y2) % p == 0): return Point(0, 0) if (x1 != x2 or y1 != y2): lam = (y2 - y1) * inverse(x2-x1, p) % p else: lam = (3*x1**2+a) * inverse(2*y1, p) % p x = (lam**2 - x1 - x2) % p y = (lam * (x1 - x) - y1) % p return Point(x, y) def __rmul__(self, k): B = Point(0, 0) k = f'{k:b}' for k_i in k: B = B + B if (k_i == '1'): B = B + self return B def __eq__(self, B): return self.x == B.x and self.y == B.y p = 115792089210356248762697446949407573530086143415290314195533631308867097853951 order = 115792089210356248762697446949407573529996955224135760342422259061068512044369 a = -3 b = 41058363725152142129326129780047268409114441015993725554835256314039467401291 WELCOME = """ Welcome to my YiXiXi! As I have mentioned before, to predict the value of Q, the possibility is only about O(yixixi)! If you know how to capture the probability of O(yixixi), you can capture the flag! """ def main(): print(WELCOME) x, y = map(int, input("Enter the coordinate of point P: ")[1:-1].split(', ')) P = Point(x, y) k = random.randint(1,order) Q = k * P print("As we all have known, Q = kP") print("Now with the probability of O(yixixi), please tell me ---") x, y = map(int, input("Enter the coordinate of point Q: ")[1:-1].split(', ')) Q_ = Point(x, y) if Q_ == Point(0, 0) or Q_ == P: print("Not that easy") elif Q_ == Q: print("Amazing! You have captured the probability of O(yixixi) successfully!") with open('flag.txt') as f: flag = f.read() print(f"Here is your flag: {flag}") else: print("Uh-oh! You have not captured the probability of O(yixixi)...") print("Maybe next time...") if __name__ == '__main__': main()
这道题有一个漏洞就是没有验证输入的点是否在曲线上
题目需要输入G,随机生成k,预测 P=kG的坐标
并且P=G和P=O都是不行的
也就是构造G=O和2G=O都不行
于是就能想到构造3G=O(想不到)
去猜测P=2G的坐标
也就是2G=-G
可以得到(3,4)他的二倍点是(3,-4)满足
exp
from pwn import * re=remote("pwn.challenge.ctf.show",28147) re.recvuntil(b'Enter the coordinate of point P: ') re.sendline(b'(3, 4)') re.recvuntil(b'Enter the coordinate of point Q: ') re.sendline(b'(3, -4)') re.interactive()
- 作者:Putao0v0
- 链接:https://tangly1024.com/article/ECC
- 声明:本文采用 CC BY-NC-SA 4.0 许可协议,转载请注明出处。
相关文章