[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
'''

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()

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()