# ELLIPTIC CURVES IN CRYPTOGRAPHY

## Đường cong Elliptic

### Lý thuyết

Một đường cong Elliptic là tập hợp các nghiệm của phương trình có dạng $y^2 = x^3 + ax + b$. Ví dụ như


### Định luật cộng

Đường cong elliptic có một định luật cộng giữa hai điểm trên một đường cong và sẽ tạo ra đường thứ ba nhưng mà không giống như một số phép cộng thông thường. Cho P và Q là hai điểm trên đường cong elliptic E, ta vẽ đường thằng L qua P và Q. Đường L này cắt E tại ba điểm, cụ thể là P, Q và 1 điểm R. Chúng lấy điểm R đó phản xạ qua trục hoành để thu được một điểm R'. Điểm R' này được gọi là tổng của P và Q. Hiện tại thì người ta ký hiệu định luật cộng này bằng ký hiệu ⊕. $P ⊕ Q = R'$.

Ví dụ như sau:

Ta có đường cong $y^2 = x^3 - 15x + 18$

Ta lấy 2 điểm $P = (7,16)$ và $Q = (1,2)$ trên đường cong E. Đường thẳng L đi qua cả P và Q có phương trình $L: Y = \frac{7}{3}x - \frac{1}{3}$.

Ta sẽ được hình như sau:


$$(\frac{7}{3}x - \frac{1}{3})^2 = x^3 - 15x +18$$
$$\frac{49}{9}x^2 - \frac{14}{9}x + \frac{1}{9} = x^3 - 15x + 18$$
$$x^3 - \frac{49}{9}x^2 - \frac{121}{9}x + \frac{161}{9} = 0$$

$$(x-7)(x-1)(x+\frac{23}{9}) = 0$$
$$\text{=> Có nghiệm là } x = -\frac{23}{9}.$$
$$P ⊕ Q = (-\frac{23}{9},\frac{170}{27})$$

Thế nếu $P \equiv Q$ thì sao, thì ta sẽ được như này


Thế giờ ta muốn cộng hai điểm $P = (a,b)$ và $P' = (-a,b)$ thì sao ??? Không có điểm giao nhau thứ ba, vì vậy giải pháp là tạo thêm một điểm $O$ ở vô cực. Chính xác hơn là điểm $O$ không tồn tại trên mặt phẳng XY, sau đó ta thiết lập $P ⊕ P' = O$.


Và điểm $O$ này hoạt động như là một số không trong đường cong elliptic, thế nên $P ⊕ O = P$.

Cho $E: y^2 = x^3 + ax + b$, cho hai điểm $P = (x1,y1)$ và $Q = (x2,y2)$, thuật toán tính tổng của hai điểm P và Q như sau:
- Nếu $x1 = x2$ và $y1 = -y2$ thì $P + Q = O$
- Ngược lại thì ta có như sau:
$$\lambda = \frac{y2 - y1}{x2 - x1} \text{ nếu } P \neq Q$$
$$\lambda = \frac{3x_1^2 + a}{2y_1} \text{ nếu } P = Q$$
- Và ta có như sau
$\hspace{2cm} x_3 = \lambda^2 - x_1 - x_2 \hspace{1cm} \text{và} \hspace{1cm} y_3 = \lambda(x_1 - x_3) - y_1$
- Từ đó: $P + Q = (x_3,y_3)$.

### Định luật cộng cũng là một nhóm Abel

Cho $E$ là đường cong elliptic, phép cộng trong đường cong $E$ thỏa mãn các tính chất như sau:
- $P + O = O + P = P \hspace{3,6cm} \forall P \in E$
- $P + (-P) = O \hspace{4,8cm} \forall P \in E$
- $(P + Q) + R = P + (Q + R) \hspace{1,9cm} \forall P, Q, R \in E$
- $P + Q = Q + P \hspace{4,6cm} \forall P,Q \in E$

--> Phép cộng trong Elliptic là một nhóm giao hoán Abel.

## Đường cong Elliptic trong trường hữu hạn (Fp)

### Lý thuyết

Vẫn như lý thuyết ở trên thôi, nhưng mà giờ ở trong trường hữu hạn p.
$$y^2 = x^3 + ax + b \pmod{p}$$

Trong đó a và b là các hệ số thỏa mãn điều kiện $4a^3 + 27b^2 \neq 0$.

Đường cong trong trường hữu hạn có tính chất khó tính ngược lại, tạo ra một cơ chế bảo mật mạnh để sử dụng trong các giao thức mật mã học như là mã hóa khóa công khai hoặc là chữ kỹ số.

### Phép cộng

Cũng khá giống trong trường số thực, trường số nguyên tố thì chỉ cần mod với số nguyên tố p nữa thui.

Ta có: $E: y^2 = x^3 + 2x + 2 \pmod{17}$ và $P = (5,1)$. Giờ ta muốn cộng 2 điểm $P$ này thì sao

Ta sẽ tính được như sau


Tính toán bằng python thì sao nhỉii

from Crypto.Util.number import*
def add_point(P, Q, p, a, b):
    if P== (0, 0):
        return Q
    if Q == (0,0):
        return P
    
    x1, y1 = P
    x2, y2 = Q

    if x1 == x2 and y1 == -y2:
        return (0, 0)

    s = 0
    if P == Q:
        s = ((3*pow(x1,2,p)+a) * inverse(2*y1, p))
    else:
        s = ((y2-y1) * inverse(x2-x1, p))
        
    x3 = (pow(s, 2) - x1 - x2) % p
    y3 = (s*(x1 - x3) - y1) % p 
    return (x3, y3)

#E = EllipticCurve(GF(17),[2,2])
P = (5,1)
print(add_point(P,P,17,2,2))
#Output: (6, 3)

Tính toán bằng sagemath

E = EllipticCurve(GF(17),[2,2])
P = E(5,1)
Q = P + P
Q
(6 : 3 : 1)

### Phép nhân
Ta có: $E: y^2 = x^3 + 2x + 2 \pmod{17}$ và $P = (5,1)$. Ta sẽ được bảng như sau


Ta sẽ sử dụng thuật toán ``double-and-add`` như sau:

Input: P in E(Fp) and an integer n > 0
1. Set Q = P and R = O.
2. Loop while n > 0.
  3. If n ≡ 1 mod 2, set R = R + Q.
  4. Set Q = 2 Q and n = ⌊n/2⌋.
  5. If n > 0, continue with loop at Step 2.
6. Return the point R, which equals nP.

Sử dụng thuật toán đó vào python

from Crypto.Util.number import*
def add_point(P, Q, p, a, b):
    if P== (0, 0):
        return Q
    if Q == (0,0):
        return P
    
    x1, y1 = P
    x2, y2 = Q

    if x1 == x2 and y1 == -y2:
        return (0, 0)

    s = 0
    if P == Q:
        s = ((3*pow(x1,2,p)+a) * inverse(2*y1, p))
    else:
        s = ((y2-y1) * inverse(x2-x1, p))
        
    x3 = (pow(s, 2) - x1 - x2) % p
    y3 = (s*(x1 - x3) - y1) % p 
    return (x3, y3)

def Scalar_Mul(P, n):
    Q = P
    R = (0, 0)
    while n > 0:
        if n % 2 == 1:
            R = add_point(R, Q, 17, 2, 2)
        Q = add_point(Q, Q, 17, 2, 2)
        n = n//2
    return R 
# E = EllipticCurve(GF(17),[2,2])
P = (5,1)
print(Scalar_Mul(P,16))
# Output: (10, 11)

Sử dụng trong sage

sage: E = EllipticCurve(GF(17),[2,2])
....: P = E(5,1)
sage: 3*P
(10 : 6 : 1)
sage: 16*P
(10 : 11 : 1)

### Order của đường cong Elliptic

Ta có đường cong $E: y^2 = x^3 + 3x + 8 \pmod{13}$. Ta có được:
$E(\mathbb{F}_{13}) = \{ O, (1,5), (1,8), (2,3), (2,10), (9,6), (9,7), (12,2), (12,11) \}.$ Qua đó $E(\mathbb{F}_{13})$ bao gồm 9 điểm. Ta nói Order của đường cong $E$ này là 9.

Bây giờ, ta có thể dùng định lý Hasse để có thể giới hạn được order của một đường cong $E$ theo công thức như sau:
$$p + 1 - 2\sqrt{p} \leq |E(\mathbb{F}_p)| \leq p + 1 + 2\sqrt{p}$$ Như ví dụ trên, ta có được $8 \leq |E(\mathbb{F}_p)| \leq 20$ thì $E(\mathbb{F}_p) = 9$.

# Đường cong Elliptic ứng dụng trong mật mã
### Elliptic Diffie–Hellman Key Exchange

| Alice | Bob |
|:--------------------:|:-----------------------:|
| Chọn cùng 1 số nguyên tố $p$ lớn | Chọn cùng 1 số nguyên tố $p$ lớn |
| Chọn cùng 1 đường cong $E$ | Chọn cùng 1 đường cong $E$ |
| Chọn cùng 1 điểm $P$ | Chọn cùng 1 điểm $P$ |
| Chọn số bí mật $n_A$ | Chọn số bí mật $n_B$ |
| Tính toán $Q_A = n_A.P$| Tính toán $Q_B = n_B.P$ |
|Gửi cho Bob số $Q_A$|Gửi cho Alice số $Q_B$|
|Tính toán điểm $n_A.Q_B$|Tính toán điểm $n_B.Q_A$|
|Cả hai đều có cùng một điểm bí mật|Cả hai đều có cùng một điểm bí mật|

Ví dụ: Ta có đường cong $E: y^2 = x^3 + 324x + 1287 \pmod{3851}$ và điểm $P = E(920,303)$

Số bí mật của Alice là $n_A = 1194$, ta tính được $Q_A = n_A.P = E(2067,2178)$.
Số bí mật của Bob là $n_B = 1759$, ta tính được $Q_B = n_B.P = E(3684,3125)$.

Giờ Alice và Bob trao đổi cho nhau $Q_A$ và $Q_B$.

Cuối cùng, cả hai đều có:
$$\text{Alice:} \hspace{1cm} n_AQ_B = 1194(3684,3125) = (3347,1242)$$

$$\text{Bob:} \hspace{1cm} n_BQ_A = 1759(2067,2178) = (3347,1242) $$
Sau đó cả hai sẽ sử dụng tọa độ điểm $x=3347$ để làm giá trị bí mật chung để trao đổi. Thường là sẽ hash để lấy làm key cho các hệ mã hóa đối xứng.n

### ECDSA Sign
ECDSA Sign cũng là một phần rất quan trọng trong đường cong Elliptic. Đây cũng là một dạng chữ ký số phổ biến hiện nay. Thuật toán của ECDSA như sau:

- Chọn một đường cong Elliptic và chọn điểm $G \in E(F_p)$ với một số nguyên tố $p$ và $q$ an toàn.
- Quá trình tạo khóa:
- Chọn một số bất kỳ là $\text{Private Key}$ $s$ sao cho $1 < s < q - 1$
- $\text{Public Key}$ sẽ được tính bằng $V = sG \in E(F_p)$
- Quá trình ký số
- Gọi văn bản cần ký là $d \pmod{q}$
- Chọn một số bất kỳ $e \pmod{q}$
- $s_1 = (eG)[x] \pmod{q}$
- $s_2 = e^{-1}.(d + ss_1) \pmod{q}$
- Công khai chữ ký $(s_1, s_2)$
- Quá trình xác minh
- Ta tính $v_1 = d.s_2^{-1} \pmod{q}$
- Ta tính $v_2 = s_1.s_2{-1} \pmod{q}$
- Ta tính $v_1G + v_2V \in E(F_p)$
- Ta xác minh $(v_1G + v_2V)[x] \pmod{q}$ với $s_1$. Nếu bằng nhau thì là True.


Giải thích vì sao $(v_1G + v_2V)[x] \pmod{q} == s_1$:
$$v_1G + v_2V = ds_2^{-1}G + s_1s_2^{-1}(sG)$$
$$v_1G + v_2V = (s_2^{-1}G)(d+ss_1)$$
$$v_1G + v_2V = (s_2^{-1}G)(es_2)$$
$$v_1G + v_2V = (G)(e)$$

Đoạn code sage minh họa như sau:

import hashlib
from random import randint

p = 115792089237316195423570985008687907853269984665640564039457584007908834671663
a = 0
b = 7
E = EllipticCurve(GF(p), [a, b])
P = E(55066263022277343669578718895168534326250603453777594175500187360389116729240,
     32670510020758816978083085130507043184471273380659243275938904335757337482424)
q = 115792089237316195423570985008687907852837564279074904382605163141518161494337
Fn = FiniteField(q)


s = 12345
V = s*P
print("Public Key:", V)

message = "Hello KCSC"
hash_message = int(hashlib.sha256(message.encode('utf-8')).hexdigest(), 16) % q

# Signing
e = 123456789
s1 = Fn((P * e)[0])
s2 = (pow(e, -1, q) * (hash_message + s * s1)) % q
print("Signature: ", ((s1), (s2)))

# Verification
v1 = (pow(s2, -1, q) * hash_message) % q
v2 = (pow(s2, -1, q) * s1) % q
Verify = (P * ZZ(v1)) + (V * ZZ(v2))
x,y = Verify.xy()
if (Fn(x)) == s1:
    print("Valid")
else:
    print("Invalid")

# Cryptohack
### Background Reading
**Flag: crypto{Abelian}**
### Point Negation

Chall này ta chỉ cần tìm điểm $P'$ sao cho nó là điểm đối xứng với $P$ qua trục hoành.

sage: E = EllipticCurve(GF(9739),[497,1768])
sage: P = E(8045,6936)
sage: -P
(8045 : 2803 : 1)

**Flag: crypto{8045,2803}**
### Point Addition

Chall này ta chỉ cần cộng các điểm trên đường cong lại với nhau thui là được hihihi :kissing_smiling_eyes:

sage: E = EllipticCurve(GF(9739),[497,1768])
sage: P = E(493, 5564)
sage: Q = E(1539, 4742)
sage: R = E(4403,5202)
sage: P + P + Q + R
(4215 : 2162 : 1)

**Flag: crypto{4215,2162}**
### Scalar Multiplication

Chall này chỉ là nhân điểm trong đường cong với một số tự nhiên thui.

sage: E = EllipticCurve(GF(9739),[497,1768])
sage: P = E(2339, 2213)
sage: 7863*P
(9467 : 2742 : 1)

**Flag: crypto{9467,2742}**
### Curves and Logs
The Elliptic Curve Discrete Logarithm Problem (ECDLP) là bài toán rời rạc logarit tìm số nguyên n sao cho $Q = nP$.

Dạng này khá là giống Diffie Hellman vì đều là dạng trao đổi và bí mật chung.

Alice và Bob đều đồng ý một đường cong $E$, một số nguyên tố $p$ và một điểm $G$ trên đường cong $E$.

Alice lấy số bí mật của cô ấy là $n_A$ và tính được $Q_A = n_A.G$

Bob cũng thế, tính được $Q_B = n_B.G$ với $n_B$ là số bí mật.

Alice sẽ tính được $n_A.Q_B$ và Bob sẽ tính được $n_B.Q_A$

Do tính kết hợp, ta có được rằng:
$$S = n_A.Q_B = n_B.Q_A$$

Và $S$ sẽ là số chung của hai người để trao đổi.

sage: E = EllipticCurve(GF(9739),[497,1768])
sage: Q_a = E(815,3190)
sage: n_b = 1829
sage: Q_a*n_b
(7929 : 707 : 1)
sage: from hashlib import*
sage: print(sha1(b"7929").hexdigest())
80e5212754a824d3a4aed185ace4f9cac0f908bf

**Flag: crypto{80e5212754a824d3a4aed185ace4f9cac0f908bf}**
### Efficient Exchange

Chall này thì cho ta tọa độ $x$ của điểm $Q_A$, giờ ta cần phải tìm được tọa độ $y$ của điểm $Q_A$ này.

Ta có rằng $y^2 = x^3 + 467x + 1768 \pmod{9739}$. Thế nên giờ ta sẽ thay giá trị $x$. Ta thu được $y^2 = 5507 \pmod{9739}$.

Giờ ta sẽ sử dụng kiến thức trong phần Mathematics để làm cái này.

Vì $p \equiv 3 \pmod{4}$ thế nên ta có thể sử dụng như trong bài **LEGENDRE SYMBOL**.

Tọa độ y của $Q_A$ sẽ được tính bằng công thức $y = 5507^\frac{p+1}{4} \pmod{p}$

Từ đó ta tính được $y = 6287$

Giờ ta lấy điểm đó nhân với $n_B$ là sẽ tìm được secret thuiii

sage: E = EllipticCurve(GF(9739),[497,1768])
sage: x = 4726
sage: y_square = x**3 + 497*x + 1768
sage: y_square = y_square % 9739
sage: y_square
5507
sage: y = pow(y_square,(9739+1)//4,9739)
sage: y
6287
sage: Q_a = E(x,y)
sage: nB = 6534
sage: Q_a*nB
(1791 : 2181 : 1)

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)
    else:
        return plaintext

data = {'iv': 'cd9da9f1c60925922377ea952afc212c', 'encrypted_flag': 'febcbe3a3414a730b125931dccf912d2239f3e969c4334d95ed0ec86f6449ad8'}
iv = data["iv"]
encrypted_flag = data['encrypted_flag']
shared_secret = 1791
print(decrypt_flag(shared_secret, iv,encrypted_flag))

**Flag: crypto{3ff1c1ent_k3y_3xch4ng3}**

### Smooth Criminal

Source code của chall như sau:

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

Ta thấy rằng, đường cong Elliptics này sử dụng số nguyên tố $p$ không đủ lớn, thế nên ta có thể sử dụng hàm ``discrete_log`` được giá trị $n$ khi biết được $G$ và $Q_A$.

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)
    else:
        return plaintext

p = 310717010502520989590157367261876774703
a = 2
b = 3

E = EllipticCurve(GF(p),[a,b])
Q_A = E(280810182131414898730378982766101210916, 291506490768054478159835604632710368904)
Q_B = E(272640099140026426377756188075937988094, 51062462309521034358726608268084433317)
G = E(179210853392303317793440285562762725654, 105268671499942631758568591033409611165)

n = G.discrete_log(Q_A)
print(n)
print("SECRET:", n*Q_B)

x = 171172176587165701252669133307091694084
data = {'iv': '07e2628b590095a5e332d397b8a59aa7', 'encrypted_flag': '8220b7c47b36777a737f5ef9caa2814cf20c1c1ef496ec21a9b4833da24a008d0870d3ac3a6ad80065c138a2ed6136af'}
iv = data["iv"]
encrypted_flag = data['encrypted_flag']
print(decrypt_flag(x, iv,encrypted_flag))

**Flag: crypto{n07_4ll_curv3s_4r3_s4f3_curv3s}**

### Exceptional Curves

Source code như sau:

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 như sau:

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

Bài này không còn như bài trước nữa, vì E.order đã là số nguyên tố. Mình thử hiển thị E.order thì nó đúng bằng giá trị p. Sau khi mình tra google với từ khóa E.order is prime and equal p thì mình thu được một đường [**link**](https://crypto.stackexchange.com/questions/70454/why-smarts-attack-doesnt-work-on-this-ecdlp) này.

Bài này thuộc dạng tấn công [**Smart Attack**](https://wstein.org/edu/2010/414/projects/novotney.pdf) nên mình có được hàm sau đây:

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)

Giờ thì giải bài thôi nào

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

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

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)

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

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

G = E(3034712809375537908102988750113382444008758539448972750581525810900634243392172703684905257490982543775233630011707375189041302436945106395617312498769005,4986645098582616415690074082237817624424333339074969364527548107042876175480894132576399611027847402879885574130125050842710052291870268101817275410204850)

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

A = E(4748198372895404866752111766626421927481971519483471383813044005699388317650395315193922226704604937454742608233124831870493636003725200307683939875286865, 2421873309002279841021791369884483308051497215798017509805302041102468310636822060707350789776065212606890489706597369526562336256272258544226688832663757)

n_A = SmartAttack(G, A, p)

x = (ZZ(n_A)*B)[0]
data = {'iv': '719700b2470525781cc844db1febd994', 'encrypted_flag': '335470f413c225b705db2e930b9d460d3947b3836059fb890b044e46cbb343f0'}
iv = data["iv"]
encrypted_flag = data['encrypted_flag']
print(decrypt_flag(x, iv,encrypted_flag))

**Flag: crypto{H3ns3l_lift3d_my_fl4g!}**
### Micro Transmissions

Source code của chall như sau:

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}")

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

Bài này ta thấy rằng số nguyên tố $p$ có độ dài là 256 bits, còn số $n$ thì sẽ có độ dài là 64 bits thế nên $n < 18446744073709551615$. Ta sẽ sử dùng Pohlig-Hellman để tấn công challenge này. Bạn có thể tham khảo tại 2 nguồn [**Này**](https://koclab.cs.ucsb.edu/teaching/ecc/project/2015Projects/Sommerseth+Hoeiland.pdf) và [**Này**](https://wstein.org/edu/2010/414/projects/novotney.pdf). Ngoài ra bạn cũng có thể coi [**Video**](https://www.youtube.com/watch?v=BXFNYVmdtJUs) này để có thể hiểu về Pohlig-Hellman.

Order của đường cong này được factor như sau: $7 * 11 * 17 * 191 * 317 * 331 * 5221385621 * 5397618469 * 210071842937040101 * 637807437018177170959577732683$, mà số $n < 18446744073709551615$, thế nên ta sẽ bỏ 2 số nguyên tố cuối cùng và sử dụng hàm $discrete_log$ như challenge ``Smooth`` trên.

Code sage như sau:

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

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

p = 99061670249353652702595159229088680425828208953931838069069584252923270946291
E = EllipticCurve(GF(p), [1,4]) 
G = E(43190960452218023575787899214023014938926631792651638044680168600989609069200, 20971936269255296908588589778128791635639992476076894152303569022736123671173)
A = E.lift_x(87360200456784002948566700858113190957688355783112995047798140117594305287669)
B = E.lift_x(6082896373499126624029343293750138460137531774473450341235217699497602895121)
order = G.order()
print(factor(order))

max_value_n = 18446744073709551615

results = []
factors = []
mul = 1
for prime, exponent in factor(order):
    e = (order//(prime**exponent))
    G_new = G*e
    A_new = A*e
    dlog = G_new.discrete_log(A_new)
    print(prime, dlog)
    results.append(dlog)
    factors.append(prime**exponent)
    mul *= prime
    if mul > max_value_n:
        break

n_A = crt(results,factors)
print("Found:",n_A)

x = (ZZ(n_A)*B)[0]
data = {'iv': 'ceb34a8c174d77136455971f08641cc5', 'encrypted_flag': 'b503bf04df71cfbd3f464aec2083e9b79c825803a4d4a43697889ad29eb75453'}
iv = data["iv"]
encrypted_flag = data['encrypted_flag']
print(decrypt_flag(x, iv,encrypted_flag))

**Flag: crypto{d0nt_l3t_n_b3_t00_sm4ll}**