Cryptohack ECC

Author: 堇姬Naup

Background Reading

橢圓曲線:

y^{2} = x^{3} + a x + b

4 a^{3} + 27 b^{2} \neq 0

Why ECC need
$4 a^{3} + 27 b^{2} \neq 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

有限域 (伽羅瓦域)

有限域

G F (p)

指給定某個質數p，由0、1、2……p-1共p個元素組成的整數集合中定義的加減乘除運算

Flag: crypto{ABELIAN}

order階

E

上有一點

P

，可以找到

n P = 0

，

n

稱為order

橢圓曲線的離散對數問題

在橢圓曲線

E

上
給定

P

和

T

求出

d

P + P + . . . + P + P = T = d P

符號	意思
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 (F p) = {(x, y) : x, y \in F_{p} | y^{2} = x^{3} + a x + b} \cup 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{3 x_{p}^{2} + a}{2 y_{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:

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_{A} G

Bob generates a secret random integer

n_{B}

and calculates

Q_{B}

n_{B} G

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_{A} Q_{B}

, and Bob calculates

n_{B} Q_{A}

Due to the associativity of scalar multiplication,

S = n_{A} Q_{B} = n_{B} Q_{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(大步小步算法)

F_{p}

是一個有限群，在裡面求離散對數的解

\log_{g} h

(換句話說

g^{x} = h

，求出

x

)非常難。

目標

g^{x} = h

，求出

x

假設現在有個數

T = \sqrt{o r d e r (g)}

(

o r d e r (g) = p - 1

)，可以假設

a T + b

(

0 \leq a, b \leq T

)，這樣就可以枚舉(0 ~ p-1)

g^{a T + b} = h

g^{a T} = h \times g^{- b}

左邊

g^{a T}

和右邊

g^{- b}

有

T

個，可以暴力枚舉

a, b

，將他寫進一張表，看看有無碰撞
找到

a, b

就可以求

a T + b = x

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

也就是最後的複雜度是

O (\sqrt{o r d e r (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 - s m o o t h

如:

15750 = 2 \times 3^{2} \times 5^{3} \times 7

，是個

7 - s m o o t h

pohlig-hellman

https://www.ruanx.net/pohlig-hellman/
https://lazzzaro.github.io/2020/11/07/crypto-ECC/index.html#Pohlig-Hellman算法

說明

求解

Q = l P (\mod p)

P 的 o r d e r = n

這裡將

n

分解

n = {p_{1}}^{e_{1}} + {p_{2}}^{e_{2}} + . . . {p_{r}}^{e_{r}}

將因數取出來

l_{i} \equiv l (\mod {p_{i}}^{e_{i}})

i = [1, r]

也就是

l_{1} \equiv l (\mod {p_{1}}^{e_{1}})

l_{2} \equiv l (\mod {p_{2}}^{e_{2}})

. . .

l_{r} \equiv l (\mod {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}} l P = l (\frac{n}{p_{i}} P) = l P_{0}

相當於在原式兩邊同乘

\frac{n}{p_{i}}

(

Q_{0} = l P_{0}

)

回到

l_{i}

求解

z_{0}

l_{i} P_{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

，可以用更高效來求解)

這邊為甚麼說
$o r d e r = p_{i}$ 呢?

我們知道找order是指

n P = O

(

P 的 o r d e r = n

)
我們使用

P_{0} = \frac{n}{p_{i}} P

p_{i} P_{0} = n P = O

所以

P_{0}

的

o r d e r = p_{i}

回到原來，這樣就可以用

o r d e r = 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_{1} p_{i} = Q_{0} - z_{0} P_{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())

可以看到

o r d e r (G)

是

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

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

x_{A} = G \times n_{A} (64 b i t s)

先找出

n_{A}

就可以找出

s h a r e d

了

s h a r e d = 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如果太小，就算

o r d e r (G)

不是smooth，也可以破解

另外
如果你有該

E

上一點的x，可以用這個來找回y，變回一組點

E.lift_x(ZZ())

Cryptohack ECC

Background Reading

橢圓曲線:

有限域 (伽羅瓦域)

order階

橢圓曲線的離散對數問題

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

Point Negation

題目

solve

Point Addition

證明

題目

Scalar Multiplication

Curves and Logs

敘述

題目

solve

Efficient Exchange

solve

Smooth Criminal

Source code

output

分析

解法

BSGS(大步小步算法)

smooth數

pohlig-hellman

說明

Exceptional Curves

source code

output.txt

檢查

solve

Micro Transmissions

source code

output.txt

解法

Read more

Pwn-heap note

Pwn-Stack based attack

ROP-EZROP(b33f adv_pwn)

CGGC Qual 2024-writeup