# 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.
```python=
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.
```python=
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
```python=
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)
```
```python=
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
```py
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)
```
```python=
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
```python3=
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`
```python=
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$
接下來就是解密了
```python=
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)
```python=
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
```
```python=
#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)
```
```python=
#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
```python=
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=
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
```python=
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
```python=
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
```python
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)
```sage=
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$
```python=
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())
```
Sign in with Wallet
Connect another wallet