# Cryptohack ECC
> Author: 堇姬Naup

## Background Reading
### 橢圓曲線:
$y^2 = x^3 + ax + b$
$4a^3 + 27b^2 ≠ 0$

- Why ECC need $4a^3 + 27b^2 ≠ 0$
https://www.quora.com/For-an-elliptic-curve-in-the-form-Y-2-X-3+AX+B-why-is-4A-3+27B-2-neq-0-the-condition-for-non-singularity


點加法:簡單來說就是兩點連線交點的映射

證明:(可以看我之前打的)
https://hackmd.io/@naup96321/H1nACqsH0

(a) P + O = O + P = P
(b) P + (−P) = O
(c) (P + Q) + R = P + (Q + R)
(d) P + Q = Q + P

### 有限域 (伽羅瓦域)
有限域 $GF(p)$ 指給定某個質數p，由0、1、2……p-1共p個元素組成的整數集合中定義的加減乘除運算

> Flag: crypto{ABELIAN}

### order階
$E$ 上有一點$P$ ，可以找到$nP=0$，$n$稱為order

### 橢圓曲線的離散對數問題
在橢圓曲線$E$上
給定$P$和$T$ 求出 $d$
$P+P+...+P+P=T=dP$

| 符號 | 意思 |
| --- | ----|
|T|public key|
|d|private key|
|P|Generate point|

### 橢圓曲線的離散對數問題 (Discrete Logarithm Problem with Elliptic Curves, ECDLP)

給定一個橢圓曲線$E$，$E$上的一點$P$經過了d次點加法得到$T$
現在已知$P$、$T$ 求出 $d$

## Point Negation
現在把它放入有限域中使他變成很多點的集合，代表運算時是模$F_p$下進行
$E(Fp) = \{(x,y) : x,y ∈ F_p | y^2 = x^3 + a x + b\} ∪ O$

當把$E$放入有限域後橢圓曲線不再是一條光滑曲線，而是一些不連續的點

### 題目
$E: Y^2 = X^3 + 497 X + 1768 , p: 9739$

利用上面的曲線和點 P(8045,6936)，求點 Q(x, y)，使得 P + Q = O。

### solve
因為P+Q=0
所以可以知道Q的x=8045，y為該P的y於該曲線上的對稱-6939，並且在有限域9739中運算故要mod 9739

Flag: crypto{8045,2803}

## Point Addition
- $P=0$ 則 $P+Q=Q$
- $Q=0$ 則 $P+Q=P$
(0為無窮遠點)
- $P=(x_p,y_p),Q=(x_q,y_q)$

則$x_p=x_q$且$y_p=-y_q$
$P+Q=0$

若$P,Q$為不同點，曲線$E$ 與 $P,Q$直線相交點的求反為$R(x_r,y_r)$
則$d=\frac{y_q-y_p}{x_q-x_p}$
$x_r=d^2-x_p-x_q$
$y_r=d(x_p-x_r)-y_p$

- 若$P,Q$重合

$d$則改用導數的方式呈現
$d=\frac{3x_p^2+a}{2y_p}$

$x_r=d^2-x_p-x_q$
$y_r=d(x_p-x_r)-y_p$

### 證明
https://blog.csdn.net/guyongqiangx/article/details/121793398

### 題目

$E: Y^2 = X^3 + 497 X + 1768, p: 9739$
Using the above curve, and the points P = (493, 5564), Q = (1539, 4742), R = (4403,5202), find the point S(x,y) = P + P + Q + R by implementing the above algorithm.

from sage.all import GF
class Point:
	def __init__(self,x,y,p):
		F = GF(p) #定義有限域
		self.x = F(x) #讓x,y在有限域下運算
		self.y = F(y)
		self.modulus = p #模數

def addition(p1 : Point, p2: Point, a,b):
	x1 = p1.x
	x2 = p2.x
	y1 = p1.y
	y2 = p2.y
	if x1 == x2 and y1 == y2: #如果P,Q重合
		d = (3*x1**2 + a) / (2*y1) 
	else: #P和Q不同兩點
		d = (y2 - y1) / (x2 - x1)
	x = d**2 - x1 - x2
	y = d*(x1 - x) - y1
	return Point(x,y,p1.modulus)

P = Point(493, 5564,9739)
Q = Point(1539, 4742,9739)
R = Point(4403,5202,9739)
x1 = addition(P,P,497,1768)
x2 = addition(x1,Q,497,1768)
x3 = addition(x2,R,497,1768)
assert x3.y**2 == x3.x**3 + 497*x3.x + 1768 #確認所運算是否在E上
print(x3.x, x3.y)


## Scalar Multiplication
We will work with the following elliptic curve, and prime:

E: $Y^2 = X^3 + 497 X + 1768, p: 9739$

Using the above curve, and the points P = (2339, 2213), find the point Q(x,y) = 7863 P by implementing the above algorithm.

from sage.all import GF
class Point:
	def __init__(self,x,y,p):
		F = GF(p) #定義有限域
		self.x = F(x) #讓x,y在有限域下運算
		self.y = F(y)
		self.modulus = p #模數

def addition(p1 : Point, p2: Point, a,b):
	x1 = p1.x
	x2 = p2.x
	y1 = p1.y
	y2 = p2.y
	if x1 == x2 and y1 == y2: #如果P,Q重合
		d = (3*x1**2 + a) / (2*y1) 
	else: #P和Q不同兩點
		d = (y2 - y1) / (x2 - x1)
	x = d**2 - x1 - x2
	y = d*(x1 - x) - y1
	return Point(x,y,p1.modulus)

#np->快速冪
def scalar_multiplication(p: Point, n,a,b):
	q = p
	r = 0
	while n > 0:
		if n % 2 == 1:
			try:
				r = addition(r,q,a,b)
			except:
				r = q
		q = addition(q,q,a,b)
		n = n//2
	return r 

p = Point(2339, 2213,9739)
a = scalar_multiplication(p,7863 ,497,1768)
print(a.x, a.y)

## Curves and Logs
### 敘述
Alice generates a secret random integer $n_A$ and calculates $Q_A$ = $n_AG$

Bob generates a secret random integer $n_B$ and calculates $Q_B$ = $n_BG$

Alice sends Bob $Q_A$, and Bob sends Alice $Q_B$. Due to the hardness of ECDLP, an onlooker Eve is unable to calculate $n_A,n_B$ in reasonable time.

Alice then calculates $n_AQ_B$, and Bob calculates $n_BQ_A$.

Due to the associativity of scalar multiplication, $S = n_AQ_B = n_BQ_A$.

Alice and Bob can use $S$ as their shared secret.

由於$n_A,n_B$不可知(求出$n_A,n_B$涉及ECDLP)，所以中間人沒辦法知道$S$是多少

### 題目
Using the curve, prime and generator:

$E: Y^2 = X^3 + 497 X + 1768, p: 9739, G: (1804,5368)$

Calculate the shared secret after Alice sends you $Q_A$ = (815, 3190), with your secret integer $n_B$ = 1829.

Generate a key by calculating the SHA1 hash of the x coordinate (take the integer representation of the coordinate and cast it to a string). The flag is the hexdigest you find.

### solve

class Point:
	def __init__(self,x,y,p):
		F = GF(p)
		self.x = F(x)
		self.y = F(y)
		self.modulus = p

def addition(p1 : Point, p2: Point, a,b):
	x1 = p1.x
	x2 = p2.x
	y1 = p1.y
	y2 = p2.y

	if x1 == x2 and y1 == y2:
		lamda = (3*x1**2 + a) / (2*y1)
	else:
		lamda = (y2 - y1) / (x2 - x1)
	x = lamda**2 - x1 - x2
	y = lamda*(x1 - x) - y1
	return Point(x,y,p1.modulus)
def scalar_multiplication(p: Point, n,a,b):
	q = p
	r = 0
	while n > 0:
		if n % 2 == 1:
			try:
				r = addition(r,q,a,b)
			except:
				r = q
		q = addition(q,q,a,b)
		n = n//2
	return r 


q = Point(815, 3190,9739)

a = scalar_multiplication(q,1829,497,1768)
print(a.x,a.y)

import hashlib

x_coordinate = str(7929)

hash_object = hashlib.sha1(x_coordinate.encode())
sha1_hash = hash_object.hexdigest()

print(sha1_hash)

## Efficient Exchange
公鑰不需要發送$x,y$，因為不管對方收到的$x,y$是啥，只要兩人約定的$E$一致，那$x$就會相同，所以可以直接以$x$來當作約定的公鑰

### solve

import hashlib
from sympy.ntheory import sqrt_mod
from sage.all import *


class Point:
	def __init__(self,x,y,p):
		F = GF(p)
		self.x = F(x)
		self.y = F(y)
		self.modulus = p

def addition(p1 : Point, p2: Point, a,b):
	x1 = p1.x
	x2 = p2.x
	y1 = p1.y
	y2 = p2.y

	if x1 == x2 and y1 == y2:
		lamda = (3*x1**2 + a) / (2*y1)
	else:
		lamda = (y2 - y1) / (x2 - x1)
	x = lamda**2 - x1 - x2
	y = lamda*(x1 - x) - y1
	return Point(x,y,p1.modulus)
def scalar_multiplication(p: Point, n,a,b):
	q = p
	r = 0
	while n > 0:
		if n % 2 == 1:
			try:
				r = addition(r,q,a,b)
			except:
				r = q
		q = addition(q,q,a,b)
		n = n//2
	return r 

x = 4726
n_b = 6534

[y1,y2] = sqrt_mod(x**3 + 497*x + 1768, 9739, True)
p1 = Point(x,y1,9739)
p2 = Point(x,y2,9739)
a1 = scalar_multiplication(p1,n_b,497,1768)
a2 = scalar_multiplication(p2,n_b,497, 1768)

shared_secret1 = a1
shared_secret2 = a2 

print(a1.x,a2.x,a1.y,a2.y)


from Crypto.Cipher import AES
from Crypto.Util.Padding import pad, unpad
import hashlib


def is_pkcs7_padded(message):
    padding = message[-message[-1]:]
    return all(padding[i] == len(padding) for i in range(0, len(padding)))


def decrypt_flag(shared_secret: int, iv: str, ciphertext: str):
    # Derive AES key from shared secret
    sha1 = hashlib.sha1()
    sha1.update(str(shared_secret).encode('ascii'))
    key = sha1.digest()[:16]
    # Decrypt flag
    ciphertext = bytes.fromhex(ciphertext)
    iv = bytes.fromhex(iv)
    cipher = AES.new(key, AES.MODE_CBC, iv)
    plaintext = cipher.decrypt(ciphertext)

    if is_pkcs7_padded(plaintext):
        return unpad(plaintext, 16).decode('ascii')
    else:
        return plaintext.decode('ascii')


shared_secret = 1791
iv = 'cd9da9f1c60925922377ea952afc212c'
ciphertext = 'febcbe3a3414a730b125931dccf912d2239f3e969c4334d95ed0ec86f6449ad8'

print(decrypt_flag(shared_secret, iv, ciphertext))

## Smooth Criminal
### Source code

from Crypto.Cipher import AES
from Crypto.Util.number import inverse
from Crypto.Util.Padding import pad, unpad
from collections import namedtuple
from random import randint
import hashlib
import os

# Create a simple Point class to represent the affine points.
Point = namedtuple("Point", "x y")

# The point at infinity (origin for the group law).
O = 'Origin'

FLAG = b'crypto{??????????????????????????????}'


def check_point(P: tuple):
    if P == O:
        return True
    else:
        return (P.y**2 - (P.x**3 + a*P.x + b)) % p == 0 and 0 <= P.x < p and 0 <= P.y < p


def point_inverse(P: tuple):
    if P == O:
        return P
    return Point(P.x, -P.y % p)


def point_addition(P: tuple, Q: tuple):
    # based of algo. in ICM
    if P == O:
        return Q
    elif Q == O:
        return P
    elif Q == point_inverse(P):
        return O
    else:
        if P == Q:
            lam = (3*P.x**2 + a)*inverse(2*P.y, p)
            lam %= p
        else:
            lam = (Q.y - P.y) * inverse((Q.x - P.x), p)
            lam %= p
    Rx = (lam**2 - P.x - Q.x) % p
    Ry = (lam*(P.x - Rx) - P.y) % p
    R = Point(Rx, Ry)
    assert check_point(R)
    return R


def double_and_add(P: tuple, n: int):
    # based of algo. in ICM
    Q = P
    R = O
    while n > 0:
        if n % 2 == 1:
            R = point_addition(R, Q)
        Q = point_addition(Q, Q)
        n = n // 2
    assert check_point(R)
    return R


def gen_shared_secret(Q: tuple, n: int):
    # Bob's Public key, my secret int
    S = double_and_add(Q, n)
    return S.x


def encrypt_flag(shared_secret: int):
    # Derive AES key from shared secret
    sha1 = hashlib.sha1()
    sha1.update(str(shared_secret).encode('ascii'))
    key = sha1.digest()[:16]
    # Encrypt flag
    iv = os.urandom(16)
    cipher = AES.new(key, AES.MODE_CBC, iv)
    ciphertext = cipher.encrypt(pad(FLAG, 16))
    # Prepare data to send
    data = {}
    data['iv'] = iv.hex()
    data['encrypted_flag'] = ciphertext.hex()
    return data


# Define the curve
p = 310717010502520989590157367261876774703
a = 2
b = 3

# Generator
g_x = 179210853392303317793440285562762725654
g_y = 105268671499942631758568591033409611165
G = Point(g_x, g_y)

# My secret int, different every time!!
n = randint(1, p)

# Send this to Bob!
public = double_and_add(G, n)
print(public)

# Bob's public key
b_x = 272640099140026426377756188075937988094
b_y = 51062462309521034358726608268084433317
B = Point(b_x, b_y)

# Calculate Shared Secret
shared_secret = gen_shared_secret(B, n)

# Send this to Bob!
ciphertext = encrypt_flag(shared_secret)
print(ciphertext)

### output

Point(x=280810182131414898730378982766101210916, y=291506490768054478159835604632710368904)

{'iv': '07e2628b590095a5e332d397b8a59aa7', 
'encrypted_flag': '8220b7c47b36777a737f5ef9caa2814cf20c1c1ef496ec21a9b4833da24a008d0870d3ac3a6ad80065c138a2ed6136af'}

### 分析

p = 310717010502520989590157367261876774703
a = 2
b = 3

建構了一個橢圓曲線
$Y^2 = X^3 + 2 X + 3 , p: 310717010502520989590157367261876774703$

$G$ :

g_x = 179210853392303317793440285562762725654
g_y = 105268671499942631758568591033409611165
G = Point(g_x, g_y)

$n$是我的secret key，我把它做$G \times n$，這就是我們的公鑰

$B$ :

b_x = 272640099140026426377756188075937988094
b_y = 51062462309521034358726608268084433317
B = Point(b_x, b_y)

Bob用$B \times n$來產生Shared Secret去加密flag

### 解法
目標找出 shared_secret ，我們要找出n是多少，另外目前我們知道 $G \times n$ ，所以我們必須解決 ECDLP 問題

可以來看看Pohlig-Hellman是否可行
首先我們先嘗試找出 $E$ 的**order**

質因數分解他

$\sqrt{179317983307} 近似 423459$
BSGS 的複雜度為 O(sqrt(n))
所以可以用`.discrete_log`


from sage.all import *

p = 310717010502520989590157367261876774703
a = 2
b = 3
E = EllipticCurve(GF(p),[a,b])

g_x = 179210853392303317793440285562762725654
g_y = 105268671499942631758568591033409611165
G = E(g_x, g_y)

b_x = 272640099140026426377756188075937988094
b_y = 51062462309521034358726608268084433317
B = E(b_x, b_y)

publickey=E(280810182131414898730378982766101210916,291506490768054478159835604632710368904)

print("n:",G.discrete_log(publickey))

算出$n=47836431801801373761601790722388100620$
接下來就是解密了

from Crypto.Cipher import AES
from Crypto.Util.number import inverse
from Crypto.Util.Padding import pad, unpad
from collections import namedtuple
from random import randint
import hashlib
import os
O = 'Origin'
def check_point(P: tuple):
    if P == O:
        return True
    else:
        return (P.y**2 - (P.x**3 + a*P.x + b)) % p == 0 and 0 <= P.x < p and 0 <= P.y < p


def point_inverse(P: tuple):
    if P == O:
        return P
    return Point(P.x, -P.y % p)

def point_addition(P: tuple, Q: tuple):
    # based of algo. in ICM
    if P == O:
        return Q
    elif Q == O:
        return P
    elif Q == point_inverse(P):
        return O
    else:
        if P == Q:
            lam = (3*P.x**2 + a)*inverse(2*P.y, p)
            lam %= p
        else:
            lam = (Q.y - P.y) * inverse((Q.x - P.x), p)
            lam %= p
    Rx = (lam**2 - P.x - Q.x) % p
    Ry = (lam*(P.x - Rx) - P.y) % p
    R = Point(Rx, Ry)
    assert check_point(R)
    return R

def double_and_add(P: tuple, n: int):
    # based of algo. in ICM
    Q = P
    R = O
    while n > 0:
        if n % 2 == 1:
            R = point_addition(R, Q)
        Q = point_addition(Q, Q)
        n = n // 2
    assert check_point(R)
    return R


def gen_shared_secret(Q: tuple, n: int):
    # Bob's Public key, my secret int
    S = double_and_add(Q, n)
    return S.x


def decrypt_flag(shared_secret: int, iv: bytes, ciphertext: bytes):
    # Derive AES key from shared secret
    sha1 = hashlib.sha1()
    sha1.update(str(shared_secret).encode('ascii'))
    key = sha1.digest()[:16]
    # Encrypt flag
    
    cipher = AES.new(key, AES.MODE_CBC, iv)
    ciphertext = cipher.decrypt(pad(ciphertext, 16))
    print(ciphertext)

p = 310717010502520989590157367261876774703
a = 2
b = 3


Point = namedtuple("Point", "x y")

b_x = 272640099140026426377756188075937988094
b_y = 51062462309521034358726608268084433317
B = Point(b_x, b_y)
n=47836431801801373761601790722388100620

shared_secret = gen_shared_secret(B, n)
print(shared_secret)

iv=bytes.fromhex('07e2628b590095a5e332d397b8a59aa7') 
c=bytes.fromhex('8220b7c47b36777a737f5ef9caa2814cf20c1c1ef496ec21a9b4833da24a008d0870d3ac3a6ad80065c138a2ed6136af')

decrypt_flag(shared_secret,iv,c)


### BSGS(大步小步算法)
$\mathbb{F}_p$是一個有限群，在裡面求離散對數的解$\log_gh$ (換句話說 $g^x = h$，求出$x$)非常難。

目標$g^x = h$，求出$x$

假設現在有個數 $T=\sqrt{order(g)}$ ( $order(g)=p-1$ )，可以假設$aT+b$ ( $0 \leq a,b \leq T$ )，這樣就可以枚舉(0 ~ p-1)

$g^{aT+b} = h$
$g^{aT} = h \times g^{-b}$

左邊$g^{aT}$和右邊$g^{-b}$有$T$個，可以暴力枚舉$a,b$，將他寫進一張表，看看有無碰撞
找到$a,b$就可以求$aT+b=x$

(本質上跟 meet in the middle很像)

也就是最後的複雜度是$O(\sqrt{order(g)})$

BSGS可以求解任意群的離散對數

https://blog.csdn.net/qq_58207591/article/details/123954286

https://luckyglass.github.io/2019/OldVer12/

https://chenliang.org/2021/06/06/attack-dicrete-logarithm/

https://zhuanlan.zhihu.com/p/523658036

### smooth數
如果一個數所有的質因數都小於等於$B$，就稱為這個數叫做$B-smooth$
如: $15750=2 \times 3^2 \times 5^3 \times 7$，是個$7-smooth$

### pohlig-hellman
https://www.ruanx.net/pohlig-hellman/
https://lazzzaro.github.io/2020/11/07/crypto-ECC/index.html#Pohlig-Hellman%E7%AE%97%E6%B3%95
#### 說明

求解 $Q=lP \pmod p$
$P的order = n$
這裡將$n$分解
$n={p_1}^{e_1}+{p_2}^{e_2}+ ... {p_r}^{e_r}$
將因數取出來
$l_i \equiv l \pmod {{p_i}^{e_i}}$
$i=[1,r]$

也就是
$l_1 \equiv l \pmod {{p_1}^{e_1}}$
$l_2 \equiv l \pmod {{p_2}^{e_2}}$
$...$
$l_r \equiv l \pmod {{p_r}^{e_r}}$

若求得 $l_i, i=[1,r]$ ，用crt可以求得 $l$

開始求出 $l_i$
將 $l_i$ 設為 $p_i$ 的多項式， $l_i = {z_0}+{z_1}{p_i}+{z_2}{p_i}^2+...+{z_{e-1}}{p_i}^{e-1}$
$z=[0,p_{i-1}-1]$

這邊要計算 $z_i$

分別取 $P_0、Q_0$(用來構造子群，更快求解)
$P_0=\frac{n}{p_i}P$
$Q_0=\frac{n}{p_i}Q$

這樣可以知道 $Q_0=\frac{n}{p_i}Q=\frac{n}{p_i}lP=l(\frac{n}{p_i}P)=lP_0$

相當於在原式兩邊同乘$\frac{n}{p_i}$ ($Q_0=lP_0$)

回到$l_i$ 求解$z_0$
$l_iP_0=Q_0$
$({z_0}+{z_1}{p_i}+{z_2}{p_i}^2+...+{z_{e-1}}{p_i}^{e-1})P_0=Q_0$
$({z_0})P_0=Q_0$

這邊已經將$P$域上的離散對數分解到$P_0$域上
所以這邊已經可以用${p_i}$的order來求解$z_0$了(很明顯$p_i$遠遠小於 $n$，可以用更高效來求解)

> 這邊為甚麼說$order=p_i$呢?

我們知道找order是指$nP=O$($P的order=n$)
我們使用
$P_0=\frac{n}{p_i}P$
${p_i}P_0={n}P=O$
所以$P_0$的$order=p_i$

回到原來，這樣就可以用$order=p_i$來求解$z_0$
接下來開始推到$z_1、z_2 ...$

$({z_0}+{z_1}{p_i}+{z_2}{p_i}^2+...+{z_{e-1}}{p_i}^{e-1})P_0=Q_0$
$({z_1}{p_i}+{z_2}{p_i}^2+...+{z_{e-1}}{p_i}^{e-1})P_0=Q_0-{z_0}P_0$
$z_1p_i=Q_0-z_0P_0$

求解$z_1$
依序求所有的$z$就可以得到$l_1$

再根據此作法推到所有的$l_i$
CRT後可以求出$l$ 了，而複雜度是$\sqrt {p_r}$ 中間求解子群的離散對數可以用BSGS求解(複雜度就是根號order)

from Crypto.Util.number import *
from sympy.polys.galoistools import gf_crt
from sympy.polys.domains import ZZ
import gmpy2
import random

def Pohlig_Hellman(g, h, p):
    # 模数分解
    p_1 = p - 1
    d, factors = 2, []
    while d*d <= p_1:
        while (p_1 % d) == 0:
            factors.append(d)
            p_1 //= d
        d += 1
    if p_1 > 1:
        factors.append(p)
    factors = [[i, factors.count(i)] for i in set(factors)]

    # 求每个素因子进制下的c_i
    x = []
    for factor in factors:
        c_i_list = []
        for i in range(factor[1]):
            if i != 0:
                beta = (beta * pow(g, -(c_i_list[-1] * (factor[0] ** (i - 1))), p)) % p
            else:
                beta = h
            e1 = pow(beta, (p-1) // (factor[0] ** (i + 1)), p)
            e2 = pow(g, (p-1) // factor[0], p)
            for c_i in (range(factor[0])):
                if pow(e2, c_i, p) == e1:
                    c_i_list.append(c_i)
                    break
        x.append(c_i_list)

    # 将模p_i意义下的p_i进制表示转换为模p_i意义下的十进制
    system = []
    for i, factor in enumerate(factors):
        res = 0
        for j, x_j in enumerate(x[i]):
            res += x_j * (factor[0] ** j)
        res = res % (factor[0] ** factor[1])
        system.append(res)

    # 中国剩余定理
    factors = [factors[i][0] ** factors[i][1] for i in range(len(factors))]
    result = gf_crt(system, factors, ZZ)
    return result

#Sage Code 1
p = 
a = 
b = 
gx = 
gy = 
px = 
py = 

E = EllipticCurve(GF(p), [a, b])
G = E(gx, gy)
n = E.order()
QA = E(px, py)

factors = list(factor(n))
m = 1
moduli = []
remainders = []
print(factors)

for i, j in factors:
    if i > 10**9:
        print(i)
        break
    mod = i**j
    g2 = G*(n//mod)
    q2 = QA*(n//mod)
    r = discrete_log(q2, g2, operation='+')
    remainders.append(r)
    moduli.append(mod)
    m *= mod

r = crt(remainders, moduli)
print(r)

#Sage Code 2
E = EllipticCurve(GF(p), [a, b])
G = E()
Q = E()

factors, exponents = zip(*factor(E.order()))
primes = [factors[i] ^ exponents[i] for i in range(len(factors))][:-2]
print(primes)
dlogs = []
for fac in primes:
	t = int(int(G.order()) // int(fac))
	dlog = discrete_log(t*Q,t*G,operation="+")
	dlogs += [dlog]
	print("factor: "+str(fac)+", Discrete Log: "+str(dlog)) #calculates discrete logarithm for each prime order

l = crt(dlogs,primes)
print(l)

## Exceptional Curves

### source code

from Crypto.Cipher import AES
from Crypto.Util.Padding import pad, unpad
from random import randint
import hashlib

FLAG = b'crypto{??????????????????????}'


def gen_public_key():
    private = randint(1, E.order() - 1)
    public = G * private
    return(public, private)


def shared_secret(public_key, private_key):
    S = public_key * private_key
    return S.xy()[0]


def encrypt_flag(flag):
    # Bob's public key
    b_x = 0x7f0489e4efe6905f039476db54f9b6eac654c780342169155344abc5ac90167adc6b8dabacec643cbe420abffe9760cbc3e8a2b508d24779461c19b20e242a38
    b_y = 0xdd04134e747354e5b9618d8cb3f60e03a74a709d4956641b234daa8a65d43df34e18d00a59c070801178d198e8905ef670118c15b0906d3a00a662d3a2736bf
    B = E(b_x, b_y)
    # Calculate shared secret
    A, nA = gen_public_key()
    print(f'Public Key: {A}')
    secret = shared_secret(B, nA)
    # Derive AES key from shared secret
    sha1 = hashlib.sha1()
    sha1.update(str(secret).encode('ascii'))
    key = sha1.digest()[:16]
    # Encrypt flag
    iv = os.urandom(16)
    cipher = AES.new(key, AES.MODE_CBC, iv)
    ciphertext = cipher.encrypt(pad(FLAG, 16))
    # Prepare encryption to send
    data = {}
    data['iv'] = iv.hex()
    data['encrypted_flag'] = ciphertext.hex()
    return data


# Curve params
p = 0xa15c4fb663a578d8b2496d3151a946119ee42695e18e13e90600192b1d0abdbb6f787f90c8d102ff88e284dd4526f5f6b6c980bf88f1d0490714b67e8a2a2b77
a = 0x5e009506fcc7eff573bc960d88638fe25e76a9b6c7caeea072a27dcd1fa46abb15b7b6210cf90caba982893ee2779669bac06e267013486b22ff3e24abae2d42
b = 0x2ce7d1ca4493b0977f088f6d30d9241f8048fdea112cc385b793bce953998caae680864a7d3aa437ea3ffd1441ca3fb352b0b710bb3f053e980e503be9a7fece

# Define curve
E = EllipticCurve(GF(p), [a, b])

# Protect against Pohlig-Hellman Algorithm
assert is_prime(E.order())

# Create generator
G = E.gens()[0]
print(f'Generator: {G}')

encrypted_flag = encrypt_flag(FLAG)
print(encrypted_flag)

### output.txt

Generator: (3034712809375537908102988750113382444008758539448972750581525810900634243392172703684905257490982543775233630011707375189041302436945106395617312498769005 : 4986645098582616415690074082237817624424333339074969364527548107042876175480894132576399611027847402879885574130125050842710052291870268101817275410204850 : 1)
Public Key: (4748198372895404866752111766626421927481971519483471383813044005699388317650395315193922226704604937454742608233124831870493636003725200307683939875286865 : 2421873309002279841021791369884483308051497215798017509805302041102468310636822060707350789776065212606890489706597369526562336256272258544226688832663757 : 1)
{'iv': '719700b2470525781cc844db1febd994', 'encrypted_flag': '335470f413c225b705db2e930b9d460d3947b3836059fb890b044e46cbb343f0'}

### 檢查

我發現了 $E$ 的order跟 $p$ 一樣

sage: p = 0xa15c4fb663a578d8b2496d3151a946119ee42695e18e13e90600192b1d0abdbb6f787f90c8d102ff88e284dd4526f5f6b6c980bf88f1d0490714b67e8a2a2b77
....: a = 0x5e009506fcc7eff573bc960d88638fe25e76a9b6c7caeea072a27dcd1fa46abb15b7b6210cf90caba982893ee2779669bac06e267013486b22ff3e24abae2d42
....: b = 0x2ce7d1ca4493b0977f088f6d30d9241f8048fdea112cc385b793bce953998caae680864a7d3aa437ea3ffd1441ca3fb352b0b710bb3f053e980e503be9a7fece
....:
....: E = EllipticCurve(GF(p),[a,b])
....: print(E.order())
....: print(E.order()==p)
....:
8451139905551902831160354990243448994735923344327179631310525520435196861496551764162970081762137226285330762159796842785356834064520159547540428116601719
True

可以使用 **Smart’s Attack**

證明:
https://wstein.org/edu/2010/414/projects/novotney.pdf

def SmartAttack(P,Q,p):
    E = P.curve()
    Eqp = EllipticCurve(Qp(p, 2), [ ZZ(t) + randint(0,p)*p for t in E.a_invariants() ])

    P_Qps = Eqp.lift_x(ZZ(P.xy()[0]), all=True)
    for P_Qp in P_Qps:
        if GF(p)(P_Qp.xy()[1]) == P.xy()[1]:
            break

    Q_Qps = Eqp.lift_x(ZZ(Q.xy()[0]), all=True)
    for Q_Qp in Q_Qps:
        if GF(p)(Q_Qp.xy()[1]) == Q.xy()[1]:
            break

    p_times_P = p*P_Qp
    p_times_Q = p*Q_Qp

    x_P,y_P = p_times_P.xy()
    x_Q,y_Q = p_times_Q.xy()

    phi_P = -(x_P/y_P)
    phi_Q = -(x_Q/y_Q)
    k = phi_Q/phi_P
    return ZZ(k)

### solve

from Crypto.Cipher import AES
from Crypto.Util.number import inverse
from Crypto.Util.Padding import pad, unpad
from collections import namedtuple
from random import randint
import hashlib
from sage.all import *

def SmartAttack(P,Q,p):
    E = P.curve()
    Eqp = EllipticCurve(Qp(p, 2), [ ZZ(t) + randint(0,p)*p for t in E.a_invariants() ])

    P_Qps = Eqp.lift_x(ZZ(P.xy()[0]), all=True)
    for P_Qp in P_Qps:
        if GF(p)(P_Qp.xy()[1]) == P.xy()[1]:
            break

    Q_Qps = Eqp.lift_x(ZZ(Q.xy()[0]), all=True)
    for Q_Qp in Q_Qps:
        if GF(p)(Q_Qp.xy()[1]) == Q.xy()[1]:
            break

    p_times_P = p*P_Qp
    p_times_Q = p*Q_Qp

    x_P,y_P = p_times_P.xy()
    x_Q,y_Q = p_times_Q.xy()

    phi_P = -(x_P/y_P)
    phi_Q = -(x_Q/y_Q)
    k = phi_Q/phi_P
    return ZZ(k)


def shared_secret(public_key, private_key):
    S = public_key * private_key
    return S.xy()[0]

p = 0xa15c4fb663a578d8b2496d3151a946119ee42695e18e13e90600192b1d0abdbb6f787f90c8d102ff88e284dd4526f5f6b6c980bf88f1d0490714b67e8a2a2b77
a = 0x5e009506fcc7eff573bc960d88638fe25e76a9b6c7caeea072a27dcd1fa46abb15b7b6210cf90caba982893ee2779669bac06e267013486b22ff3e24abae2d42
b = 0x2ce7d1ca4493b0977f088f6d30d9241f8048fdea112cc385b793bce953998caae680864a7d3aa437ea3ffd1441ca3fb352b0b710bb3f053e980e503be9a7fece

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

G = E.gens()[0]
public=E(4748198372895404866752111766626421927481971519483471383813044005699388317650395315193922226704604937454742608233124831870493636003725200307683939875286865 , 2421873309002279841021791369884483308051497215798017509805302041102468310636822060707350789776065212606890489706597369526562336256272258544226688832663757)


private_key=SmartAttack(G,public,p)

print("private key:",private_key)

b_x = 0x7f0489e4efe6905f039476db54f9b6eac654c780342169155344abc5ac90167adc6b8dabacec643cbe420abffe9760cbc3e8a2b508d24779461c19b20e242a38
b_y = 0xdd04134e747354e5b9618d8cb3f60e03a74a709d4956641b234daa8a65d43df34e18d00a59c070801178d198e8905ef670118c15b0906d3a00a662d3a2736bf
B = E(b_x, b_y)

secret = shared_secret(B, private_key)

sha1 = hashlib.sha1()
sha1.update(str(secret).encode('ascii'))
key = sha1.digest()[:16]

iv= bytes.fromhex('719700b2470525781cc844db1febd994')
encrypted_flag=bytes.fromhex('335470f413c225b705db2e930b9d460d3947b3836059fb890b044e46cbb343f0')

cipher = AES.new(key, AES.MODE_CBC, iv)
m=cipher.decrypt(pad(encrypted_flag, 16))

print(m)


## Micro Transmissions

### source code

from Crypto.Util.number import getPrime
from Crypto.Random import random
from Crypto.Cipher import AES
from Crypto.Util.number import inverse
from Crypto.Util.Padding import pad, unpad
import hashlib

FLAG = b"crypto{???????????????????}"


def gen_key_pair(G, nbits):
    n = random.getrandbits(nbits)
    P = n*G
    return P.xy()[0], n


def gen_shared_secret(P, n):
	S = n*P
	return S.xy()[0]


def encrypt_flag(shared_secret: int):
    # Derive AES key from shared secret
    sha1 = hashlib.sha1()
    sha1.update(str(shared_secret).encode('ascii'))
    key = sha1.digest()[:16]
    # Encrypt flag
    iv = os.urandom(16)
    cipher = AES.new(key, AES.MODE_CBC, iv)
    ciphertext = cipher.encrypt(pad(FLAG, 16))
    # Prepare data to send
    data = {}
    data['iv'] = iv.hex()
    data['encrypted_flag'] = ciphertext.hex()
    return data


# Efficient key exchange
nbits = 64
pbits = 256

# Curve parameters
p = getPrime(pbits)
a = 1
b = 4
E = EllipticCurve(GF(p), [a,b])
G = E.gens()[0]

print(f"Sending curve parameters:")
print(f"{E}")
print(f"Generator point: {G}\n")

# Generate key pairs
ax, n_a = gen_key_pair(G, nbits)
bx, n_b = gen_key_pair(G, nbits)

print(f"Alice sends public key: {ax}")
print(f"Bob sends public key: {bx}\n")

# Calculate point from Bob
B = E.lift_x(bx)

# Encrypted flag with shared secret
shared_secret = gen_shared_secret(B,n_a)
encrypted_flag = encrypt_flag(shared_secret)

print(f"Alice sends encrypted_flag: {encrypted_flag}")

### output.txt

Sending curve parameters:
Elliptic Curve defined by y^2 = x^3 + x + 4 over Finite Field of size 99061670249353652702595159229088680425828208953931838069069584252923270946291
Generator point: (43190960452218023575787899214023014938926631792651638044680168600989609069200 : 20971936269255296908588589778128791635639992476076894152303569022736123671173 : 1)

Alice sends public key: 87360200456784002948566700858113190957688355783112995047798140117594305287669
Bob sends public key: 6082896373499126624029343293750138460137531774473450341235217699497602895121

Alice sends encrypted_flag: {'iv': 'ceb34a8c174d77136455971f08641cc5', 'encrypted_flag': 'b503bf04df71cfbd3f464aec2083e9b79c825803a4d4a43697889ad29eb75453'}

### 解法
這題應該算pohlig-hellman的進階利用，首先先確認order(G)

from sage.all import *
p = 99061670249353652702595159229088680425828208953931838069069584252923270946291
a = 1
b = 4
E = EllipticCurve(GF(p), [a,b])
G=E(43190960452218023575787899214023014938926631792651638044680168600989609069200 , 20971936269255296908588589778128791635639992476076894152303569022736123671173)
factor(G.order())

可以看到$order(G)$是

7 * 11 * 17 * 191 * 317 * 331 * 5221385621 * 5397618469 * 210071842937040101 * 637807437018177170959577732683

發現最後兩個質因數非常大，如果要用pohlig-hellman複雜度會太高，但是可以看到secret key的bit只有64，所以可以不管最後兩個


$x_A=G \times n_A(64 bits)$
先找出$n_A$就可以找出$shared$了

$shared=B \times n_A$

from Crypto.Cipher import AES
from Crypto.Util.number import inverse
from Crypto.Util.Padding import pad, unpad
from collections import namedtuple
from random import randint
import hashlib
from sage.all import *


def gen_shared_secret(P, n):
	S = n*P
	return S.xy()[0]

p = 99061670249353652702595159229088680425828208953931838069069584252923270946291
a = 1
b = 4
E = EllipticCurve(GF(p), [a,b])
G=E(43190960452218023575787899214023014938926631792651638044680168600989609069200 , 20971936269255296908588589778128791635639992476076894152303569022736123671173)
A = E.lift_x(ZZ(87360200456784002948566700858113190957688355783112995047798140117594305287669))


orderG = G.order()

# 少取後兩個factor
factors = list(factor(orderG))[:-2]
m = 1
moduli = []
remainders = []
print(factors)

# pohlig-hellman
for i, j in factors:

    mod = i**j
    g2 = G*(orderG//mod)
    q2 = A*(orderG//mod)
    r = discrete_log(q2, g2, operation='+')
    remainders.append(r)
    moduli.append(mod)
    m *= mod

n_a = crt(remainders, moduli)
print("n_a:",n_a)

# 產生secret key
B=E.lift_x(ZZ(6082896373499126624029343293750138460137531774473450341235217699497602895121))
secret=gen_shared_secret(B,n_a)

# 解密
sha1 = hashlib.sha1()
sha1.update(str(secret).encode('ascii'))
key = sha1.digest()[:16]

iv= bytes.fromhex('ceb34a8c174d77136455971f08641cc5')
encrypted_flag=bytes.fromhex('b503bf04df71cfbd3f464aec2083e9b79c825803a4d4a43697889ad29eb75453')

cipher = AES.new(key, AES.MODE_CBC, iv)
m=cipher.decrypt(pad(encrypted_flag, 16))

print(m)

由此可知 $n$ 的bit如果太小，就算$order(G)$不是smooth，也可以破解

另外
如果你有該$E$上一點的x，可以用這個來找回y，變回一組點

E.lift_x(ZZ())