#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

'''

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

#Sage

a = 1234577

b = 3213242

p = 7654319

#EllipticCurve([a1, a2, a3, a4, a6]) -- y^2+(a1)xy+(a3)y=x^3+(a2)x^2+(a4)x+(a6)

E = EllipticCurve(GF(p), [0, 0, 0, a, b])

base = E([5234568,2287747 ])

pub = E([2366653, 1424308])

c1 = E([5081741, 6744615])

c2 = E([610619,6218 ])

X = base

n=base.order()

#Bruteforce secret k

for i in range(1, n):

    if X == pub:

        k = i

        print("[+] secret k = ", i)

        break

    else:

        X = X + base

m = c2 - (c1 * k)

print("[+] x = ", m[0])

print("[+] y = ", m[1])

print("[+] x+y = ", m[0] + m[1])

#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!

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

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

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