# I. Background
## 1. Background Reading
### Description (*Translated*)
- Elliptic Curve Cryptography (ECC) là một giao thức mật mã bất đối xứng như RSA và Diffie-Hellman (DH), hoạt động dựa trên một hàm một chiều (hay trapdoor function, là hàm dễ dàng tính theo chiều xuôi nhưng hàm ngược rất khó giải).
- Đối với RSA, hàm một chiều dựa trên tính phức tạp của phân tích thừa số nguyên tố một số nguyên lớn. Đối với DH, hàm lại dựa trên vấn đề logarit rời rạc (discrete logarithm hay dlog). Với cả RSA và DH, việc tính toán và các bước đã rất quen thuộc nhưng với ECC không còn đơn giản nữa.
- Trong ECC ta sẽ nghiên cứu về phương trình chuẩn Weierstrass có dạng
```
Y^2 = X^3 + a*X + b
Điều kiện: 4*a^3 + 27*b^2 ≠ 0
```
- Về định nghĩa: một đường cong elliptic E là tập hợp các điểm có tọa độ là nghiệm của phương trình trên. Trên hệ tọa độ Oxy có chứa E, quy tắc cộng có các tính chất sau:
```
(a) P + O = O + P = P
(b) P + (−P) = O
(c) (P + Q) + R = P + (Q + R)
(d) P + Q = Q + P
```
- Trong ECC, trường được nghiên cứu ở đây là trường hữu hạn modulo p, kí hiệu là `Fp`, khiến cho đồ thị E trên không thực sự là một đường cong nữa mà trở thành một quỹ tích các điểm có tọa độ `(x; y)` là các số nguyên trong trường `Fp` thỏa mãn phương trình.
- Câu hỏi: tính chất `(d)` nói trên đã cho thấy tính giao hoán của quy tắc cộng. Flag là tên một nhóm có tính chất này.
### Flag
> ~~`crypto{abelian}`~~
### Note
- Tên của nhóm trong đại số trừu tượng là nhóm giao hoán, hay nhóm Abel (trong Tiếng Anh là Abelian group)
---
# II. STARTER
## 2. Point Negation
### Description (*Translated*)
- Ta xét đường cong elliptic có dạng phương trình `(E): Y^2 = X^3 + a*X + b` nhưng đặt trong trường hữu hạn `Fp`, (E) không còn là đường cong nữa mà trở thành tập hợp các điểm có tọa độ thỏa mãn:
```
E(Fp) = {(x,y) : x,y ∈ Fp satisfying: y^2 = x^3 + a x + b} ∪ O
```
với O là điểm vô cùng và là phần tử trung hòa
- Tất cả các challs trong phần STARTER sẽ đều xét tới phương trình `(E): Y^2 = X^3 + 497*X + 1768` và `p = 9739` (trường hữu hạn `F9739`).
- Cho `P(8045; 6936)`, tìm điểm `Q(x; y)` thỏa `P+Q = 0`
### Solution
- Biết được `P + Q = 0` nên `Q` là phần tử đối của `P`, nói cách khác `Q` đối xứng với `P` qua trục hoành và `Q(8045; -6936)`. Nhưng ta đang xét trong trường `Fp` với `p = 9739` nên điểm `Q` thực sự là `Q mod p` hay `Q(8045; 2803)`
### Flag
> ~~`crypto{8045,2803}`~~
---
## 3. Point Addition
### Description (*Translated*)
- Đối với quy tắc cộng điểm trong ECC, ta có hai cách để tìm "tổng". Cách 1 là dựa vào hình học, cách này phức tạp hơn nhiều so với cách 2. Cách 2 như sau:
```
If P = 0, P + Q = Q
If Q = 0, P + Q = P
Else P(x1; y1) and Q(x2; y2), then
If P = -Q then P + Q = 0
Else if P ≠ Q then λ = (y2 - y1) / (x2 - x1)
Else if P = Q: λ = (3x1^2 + a) / 2y1
x3 = λ^3 - x1 - x2
y3 = λ(x1 - x3) - y1
P + Q = (x3; y3)
```
:::info
Vì chúng ta đang xét trong trường hữu hạn `Fp`, tất cả các phép tính đều phải được `mod p`, chính vì thế, phép chia ở trên chính là phép nhân nghịch đảo. Ví dụ `1/5 ≡ 1*inverse(5, 11) ≡ 9 (mod 11)`
:::
- Xét `(E): Y^2 = X^3 + 496*X + 1768` trong trường `Fp`, `p = 9739`, cho điểm `P(493; 5564)`, `Q(1539; 4742)` và `R(4403; 5202)`, tìm điểm `S(x; y) = P + P + Q + R`
### Solution
- Trước tiên ta cần code để tính "tổng" hai điểm:
```python=
from Crypto.Util.number import inverse
def sum(P, Q, E):
O = (0, 0)
if P == O: return Q
elif Q == O: return P
else:
x1, y1 = P
x2, y2 = Q
if x1 == x2 and y1 == -y2: return O
Ea, Ep = E['a'], E['p']
if P != Q:
k = ((y2 - y1) * inverse(x2 - x1, Ep)) % Ep
else:
k = ((3*x1**2 + Ea) * inverse(2 * y1, Ep)) % Ep
x3 = (k**2 - x1 - x2) % Ep
y3 = (k*(x1 - x3) - y1) % Ep
return x3, y3
```
- Sau đó chỉ cần tính `S(x; y)` theo yêu cầu đề bài là xong.
### Flag
> ~~`crypto{4215,2162}`~~
---
## 4. Scalar Multiplication
### Description (*Translated*)
- Thuật ngữ "Scalar Multiplication" ở đây chính là phép nhân vô hướng, là việc lặp lại nhiều lần phép cộng, ví dụ `3P = P + P + P`.
- Trong một vài challs tiếp theo, chúng ta sẽ sử dụng tích vô hướng này để tạo ra một `shared secret` để gửi qua một kênh bảo mật kém tương tự như DH.
- Theo cuốn "An Introduction to Mathematical Cryptography" của *Jeffrey Hoffstein, Jill Pipher, Joseph H. Silverman*, thuật toán dưới đây được sử dụng để tính tích vô hướng khá hiệu quả trên elliptic.
```
Double and Add algorithm for the scalar multiplication of point P by n:
- Input: P thuộc E(Fp) và một số nguyên dương n
1. Lấy Q = P và R = 0
2. Lặp lại cho tới khi n âm:
3. Nếu n ≡ 1 (mod 2), gán R = R + Q
4. Gán Q = 2Q và n = ⌊n/2⌋
5. Trả về R = nP
```
:::info
:bulb: Đây không phải là thuật toán hiệu quả nhất nhưng khá ổn trong phần này
:::
- Cho `(E): Y^2 = X^3 + 497*X + 1768` trong `Fp` với `p = 9739`, sử dụng thuật toán trên để tính `Q = 7863P` biết `P(2339; 2213)`
### Solution
- Code để tính tích vô hướng theo thuật toán nói trên:
```python=
from Crypto.Util.number import inverse
def sum(P, Q, E):
O = (0, 0)
if P == O: return Q
elif Q == O: return P
else:
x1, y1 = P
x2, y2 = Q
if x1 == x2 and y1 == -y2: return O
Ea, Ep = E['a'], E['p']
if P != Q:
k = ((y2 - y1) * inverse(x2 - x1, Ep)) % Ep
else:
k = ((3*x1**2 + Ea) * inverse(2 * y1, Ep)) % Ep
x3 = (k**2 - x1 - x2) % Ep
y3 = (k*(x1 - x3) - y1) % Ep
return x3, y3
def mul(P, n, E):
O = (0, 0)
Q = P
R = O
while n>0:
if n%2 == 1: R = sum(R, Q, E)
Q = sum(Q, Q, E)
n //=2
return R
```
- Nhập `E` và `P`, `n` ta tìm được `Q(9467; 2742)`
### Flag
> ~~`crypto{9467,2742}`~~
---
## 5. Curves and Logs
### Description (*Translated*)
- Elliptic Curve Discrete Logarithm Problem (ECDLP) là bài toán tìm `n` thỏa `Q = nP`.
- Giống như bài toán tìm logarit rời rạc của DH trước đây, việc tìm `n` khi biết tích vô hướng của một điểm thuộc `E(Fp)` khá khó khăn để giải (thuật toán hiệu quả nhất phải chạy với thời gian `sqrt(p)`). Đây chính là hàm một chiều được sử dụng trong ECC.
- Đặt tình huống như sau: Alice và Bob cần trao đổi với nhau một `shared secret` nên cùng sử dụng elliptic curve `(E)` trong trường `Fp` và một điểm khởi tạo (điểm sinh) `G`.
:::info
Trong ECC, |G| hay cấp của `G` nên là một số nguyên tố.
:::
- Các quy trình như sau:
- Alice và Bob chọn hai số bí mật giả sử là `a` và `b` và tính `Q_A = aG`, `Q_B = bG`
- Alice gửi cho Bob `Q_A` và Bob gửi lại cho Alice `Q_B`. Sau đó cả hai cùng tính `aQ_B` và `bQ_A`, vì tính giao hoán của tích vô hướng, Alice và Bob đều thu được `S = abG = aQ_B = bQ_A` chính là `shared secret`.
- Xét `(E): Y^2 = X^3 + 497*X + 1768, p: 9739` và điểm sinh `G(1804, 5368)`
- Khôi phục lại `shared secret` biết `Q_A(815, 3190)` và `b = 1829` rồi băm hoành độ thành một `key` sử dụng SHA1.
### Solution
- Ta chỉ cần áp dụng tích vô hướng của bài trước :
```python=
from Crypto.Util.number import inverse
from hashlib import sha1
def sum(P, Q, E):
O = (0, 0)
if P == O: return Q
elif Q == O: return P
else:
x1, y1 = P
x2, y2 = Q
if x1 == x2 and y1 == -y2: return O
Ea, Ep = E['a'], E['p']
if P != Q:
k = ((y2 - y1) * inverse(x2 - x1, Ep)) % Ep
else:
k = ((3*x1**2 + Ea) * inverse(2 * y1, Ep)) % Ep
x3 = (k**2 - x1 - x2) % Ep
y3 = (k*(x1 - x3) - y1) % Ep
return x3, y3
def mul(P, n, E):
O = (0, 0)
Q = P
R = O
while n>0:
if n%2 == 1: R = sum(R, Q, E)
Q = sum(Q, Q, E)
n //=2
return R
E = {'a': 497, 'b': 1768, 'p': 9739}
G = (1804, 5368)
Q_A = (815, 3190)
b = 1829
key = mul(Q_A, b, E)[0]
key = sha1(str(key).encode()).hexdigest()
flag = 'crypto{?}'.replace('?', key)
print(flag)
```
### Flag
> ~~`crypto{80e5212754a824d3a4aed185ace4f9cac0f908bf}`~~
### Note
- Bài có thể giải mà không cần phải viết lại thuật toán tính tích vô hướng bằng cách dùng sage:
```python=
from hashlib import sha1
E = EllipticCurve(GF(9739),[497,1768])
P = E(815, 3190)
key = sha1(str((1829*P)[0]).encode()).hexdigest()
flag = 'crypto{?}'.replace('?', key)
print(flag)
```
---
## 6. Efficient Exchange
### Description (*Translated*)
- Alice và Bob nhận ra việc gửi cả hoành độ và tung độ của `Q_A` và `Q_B` đều không cần thiết. Trong chall này, Alice chỉ gửi `Q_Ax`. Xét chung một hệ như bài trước, ta cần tìm lại flag biết `q_x = 4726` và `b = 6534`.
- Bên cạnh đó còn có:
```python=
{'iv': 'cd9da9f1c60925922377ea952afc212c', 'encrypted_flag': 'febcbe3a3414a730b125931dccf912d2239f3e969c4334d95ed0ec86f6449ad8'}
```
và file `decrypt.py`:
```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 = ?
iv = ?
ciphertext = ?
print(decrypt_flag(shared_secret, iv, ciphertext))
```
### Solution
- Trước tiên ta cần tìm lại tung độ `q_y` ứng với `q_x`. Nhưng trong trường `Fp` này, thay `q_x` vào phương trình của `(E)` chỉ giúp tìm lại thặng dư bình phương của `q_y` theo `modulo p`. Chính vì thế ta cần code để tính thặng dư bậc hai, nói cách khác là tìm lại `q_y`:
```python=
E = {'a': 497, 'b': 1768, 'p': 9739}
G = (1804, 5368)
q_x = 4726
b = 6534
p = E['p']
left = lambda x : (x**3 + 497*x + 1768) % p
assert p % 4 == 3
q_y1, q_y2 = 0, 0
if pow(left(q_x), (p-1)//2, p) == 1:
q_y1 = pow(left(q_x), (p+1)//4, p)
q_y2 = p - q_y1
assert (q_y1)**2 % p == left(q_x)
assert (q_y2)**2 % p == left(q_x)
print(q_y1, q_y2)
```
- Có được hai tung độ `q_y1` và `q_y2` (thực ra hai tung độ này cho ra cùng một `shared secret`) ta sẽ khôi phục lại được flag:
```python=
from Crypto.Util.number import inverse
from Crypto.Cipher import AES
from Crypto.Util.Padding import 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')
def sum(P, Q, E):
O = (0, 0)
if P == O: return Q
elif Q == O: return P
else:
x1, y1 = P
x2, y2 = Q
if x1 == x2 and y1 == -y2: return O
Ea, Ep = E['a'], E['p']
if P != Q:
k = ((y2 - y1) * inverse(x2 - x1, Ep)) % Ep
else:
k = ((3*x1**2 + Ea) * inverse(2 * y1, Ep)) % Ep
x3 = (k**2 - x1 - x2) % Ep
y3 = (k*(x1 - x3) - y1) % Ep
return x3, y3
def mul(P, n, E):
O = (0, 0)
Q = P
R = O
while n>0:
if n%2 == 1: R = sum(R, Q, E)
Q = sum(Q, Q, E)
n //=2
return R
E = {'a': 497, 'b': 1768, 'p': 9739}
G = (1804, 5368)
q_x = 4726
b = 6534
p = E['p']
left = lambda x : (x**3 + 497*x + 1768) % p
assert p % 4 == 3
q_y1, q_y2 = 0, 0
if pow(left(q_x), (p-1)//2, p) == 1:
q_y1 = pow(left(q_x), (p+1)//4, p)
q_y2 = -q_y1 % p
assert (q_y1)**2 % p == left(q_x)
assert (q_y2)**2 % p == left(q_x)
Q1 = (q_x, q_y1)
Q2 = (q_x, q_y2)
shared_secret1 = int(mul(Q1, b, E)[0])
shared_secret2 = int(mul(Q2, b, E)[0])
assert shared_secret1 == shared_secret2
shared_secret = shared_secret1
iv = 'cd9da9f1c60925922377ea952afc212c'
ciphertext = 'febcbe3a3414a730b125931dccf912d2239f3e969c4334d95ed0ec86f6449ad8'
print(decrypt_flag(shared_secret, iv, ciphertext))
```
### Flag
> ~~`crypto{3ff1c1ent_k3y_3xch4ng3}`~~
### Note
- Do bài cho `p ≡ 3 (mod 4)` là dạng rất đơn giản của một số nguyên tố nên ta có thể sử dụng kiến thức liên quan đến [công thức Lagrange](https://en.wikipedia.org/wiki/Quadratic_residue#Prime_or_prime_power_modulus) để tính trực tiếp thặng dư bậc hai theo `modulo p`. Nếu không có dữ kiện trên thì ta phải dùng thuật toán khác là [Tonelli-Shanks](https://www.geeksforgeeks.org/find-square-root-modulo-p-set-2-shanks-tonelli-algorithm/)
- Code Tonelli (from Lactf :penguine:):
```python=
def legendre(a, p):
return pow(a, (p - 1) // 2, p)
def tonelli(a, p):
q = p - 1
s = 0
while q % 2 == 0:
q //= 2
s += 1
if s == 1:
return pow(a, (p + 1) // 4, p)
for z in range(2, p):
if p - 1 == legendre(z, p):
break
c = pow(z, q, p)
r = pow(a, (q + 1) // 2, p)
t = pow(a, q, p)
m = s
t2 = 0
while (t - 1) % p != 0:
t2 = (t * t) % p
for i in range(1, m):
if (t2 - 1) % p == 0:
break
t2 = (t2 * t2) % p
b = pow(c, 1 << (m - i - 1), p)
r = (r * b) % p
c = (b * b) % p
t = (t * c) % p
m = i
return r #Trả về r thỏa r^2 ≡ a (mod p)
```
---
# II. PARAMETER CHOICE
## 7. Smooth Criminal
### Description
- Spent my morning reading up on ECC and now I'm ready to start encrypting my messages. Sent a flag to Bob today, but you'll never read it.
- Challenge code:
```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
# 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)
```
- Challenge output:
```python=
Point(x=280810182131414898730378982766101210916, y=291506490768054478159835604632710368904)
{'iv': '07e2628b590095a5e332d397b8a59aa7', 'encrypted_flag': '8220b7c47b36777a737f5ef9caa2814cf20c1c1ef496ec21a9b4833da24a008d0870d3ac3a6ad80065c138a2ed6136af'}
```
### Solution
- Sau khi đọc source, mình biết được phương trình của `(E)`, trường `Fp`, điểm sinh `G` và giá trị `B` là khóa công khai của Bob. Điểm mình nhận được ở trong file `ouput.txt` chính là `Q = nG` với `n` random.
- Mình đã có trong tay `iv` và `encrypted_flag`, vậy còn thiếu `shared secret (ss)` mà ở đây `ss = nB`. Mình cần tìm lại `n`, nhưng theo đề bài là `Smooth Criminal` mình đoán là hint liên quan đến smooth prime `p`, khi đó thuật toán dlog sẽ chạy nhanh hơn.
- Code để tìm `n`:
```python=
p = 310717010502520989590157367261876774703
F = GF(p)
E = EllipticCurve(F, [2, 3])
g_x = 179210853392303317793440285562762725654
g_y = 105268671499942631758568591033409611165
G = E(g_x, g_y)
b_x = 272640099140026426377756188075937988094
b_y = 51062462309521034358726608268084433317
B = E(b_x, b_y)
public = E(280810182131414898730378982766101210916, 291506490768054478159835604632710368904)
n = discrete_log(public, G, operation='+')
```
- Tìm ra được `n = 47836431801801373761601790722388100620` và đem đi giải `ss` để lấy flag:
```python=
from Crypto.Util.number import inverse
from Crypto.Util.Padding import unpad
from Crypto.Cipher import AES
import hashlib
def sum(P, Q, E):
O = (0, 0)
if P == O: return Q
elif Q == O: return P
else:
x1, y1 = P
x2, y2 = Q
if x1 == x2 and y1 == -y2: return O
Ea, Ep = E['a'], E['p']
if P != Q:
k = ((y2 - y1) * inverse(x2 - x1, Ep)) % Ep
else:
k = ((3*x1**2 + Ea) * inverse(2 * y1, Ep)) % Ep
x3 = (k**2 - x1 - x2) % Ep
y3 = (k*(x1 - x3) - y1) % Ep
return x3, y3
def mul(P, n, E):
O = (0, 0)
Q = P
R = O
while n>0:
if n%2 == 1: R = sum(R, Q, E)
Q = sum(Q, Q, E)
n //=2
return R
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')
g_x = 179210853392303317793440285562762725654
g_y = 105268671499942631758568591033409611165
G = (g_x, g_y)
b_x = 272640099140026426377756188075937988094
b_y = 51062462309521034358726608268084433317
B = (b_x, b_y)
q_x = 280810182131414898730378982766101210916
q_y = 291506490768054478159835604632710368904
Q = (q_x, q_y)
p = 310717010502520989590157367261876774703
E = {
'a': 2,
'b': 3,
'p': p,
}
iv = '07e2628b590095a5e332d397b8a59aa7'
encrypted_flag = '8220b7c47b36777a737f5ef9caa2814cf20c1c1ef496ec21a9b4833da24a008d0870d3ac3a6ad80065c138a2ed6136af'
n = 47836431801801373761601790722388100620
assert mul(G, n, E) == Q
ss = mul(B, n, E)[0]
flag = decrypt_flag(ss, iv, encrypted_flag)
print(flag)
```
### Flag
> ~~`crypto{n07_4ll_curv3s_4r3_s4f3_curv3s}`~~
### Note
- Bên cạnh đó, thay vì tìm `n` mình có thể tìm `b` vì `B = bG`, code như sau:
```python=
p = 310717010502520989590157367261876774703
a = 2
b = 3
E = EllipticCurve(GF(p), [a,b])
# Generator point
G = E(179210853392303317793440285562762725654, 105268671499942631758568591033409611165)
# Bob's public key
B = E(272640099140026426377756188075937988094, 51062462309521034358726608268084433317)
# Our public key
A = E(280810182131414898730378982766101210916, 291506490768054478159835604632710368904)
# Compute Bob's private key
b = G.discrete_log(B)
shared_secret = (A * b).xy()[0]
```
nhận được
```python=
b = 23364484702955482300431942169743298535
ss = shared_secret = 171172176587165701252669133307091694084
```
và giải được flag như trên.
---
## 8. Exceptional Curves
### Description
- Learning from my mistakes... This time I've ensured my curve is of prime order. This flag will be safe forever.
- Challenge 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)
```
- Challenge output:
```python=
Generator: (3034712809375537908102988750113382444008758539448972750581525810900634243392172703684905257490982543775233630011707375189041302436945106395617312498769005 : 4986645098582616415690074082237817624424333339074969364527548107042876175480894132576399611027847402879885574130125050842710052291870268101817275410204850 : 1)
Public Key: (4748198372895404866752111766626421927481971519483471383813044005699388317650395315193922226704604937454742608233124831870493636003725200307683939875286865 : 2421873309002279841021791369884483308051497215798017509805302041102468310636822060707350789776065212606890489706597369526562336256272258544226688832663757 : 1)
{'iv': '719700b2470525781cc844db1febd994', 'encrypted_flag': '335470f413c225b705db2e930b9d460d3947b3836059fb890b044e46cbb343f0'}
```
### Solution
- Đối với bài này thì cấp của `E(Fp)` đúng bằng `p` nên mình có thuật toán [Smart's Attack](https://wstein.org/edu/2010/414/projects/novotney.pdf) để giải. Code trong [link này](https://github.com/victini-lover/CSAW-Quals-2021-Writeups/blob/main/ECC-Pop-Quiz/smarts_attack_solver.sage).
- Đề bài cho điểm sinh `G`, khóa công khai `B` của Bob và `A` của Alice, mình chỉ cần thay số vào giải là xong:
```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)
p = 0xa15c4fb663a578d8b2496d3151a946119ee42695e18e13e90600192b1d0abdbb6f787f90c8d102ff88e284dd4526f5f6b6c980bf88f1d0490714b67e8a2a2b77
a = 0x5e009506fcc7eff573bc960d88638fe25e76a9b6c7caeea072a27dcd1fa46abb15b7b6210cf90caba982893ee2779669bac06e267013486b22ff3e24abae2d42
b = 0x2ce7d1ca4493b0977f088f6d30d9241f8048fdea112cc385b793bce953998caae680864a7d3aa437ea3ffd1441ca3fb352b0b710bb3f053e980e503be9a7fece
E = EllipticCurve(GF(p), [a, b])
assert(E.order() == p)
G = E(3034712809375537908102988750113382444008758539448972750581525810900634243392172703684905257490982543775233630011707375189041302436945106395617312498769005, 4986645098582616415690074082237817624424333339074969364527548107042876175480894132576399611027847402879885574130125050842710052291870268101817275410204850)
A = E(4748198372895404866752111766626421927481971519483471383813044005699388317650395315193922226704604937454742608233124831870493636003725200307683939875286865, 2421873309002279841021791369884483308051497215798017509805302041102468310636822060707350789776065212606890489706597369526562336256272258544226688832663757)
a = SmartAttack(G, A, p)
print(a)
```
tìm được
```python!
a = 2200911270816846838022388357422161552282496835763864725672800875786994850585872907705630132325051034876291845289429009837283760741160188885749171857285407
```
và đem vào giải flag:
```python=
from Crypto.Util.number import inverse
from Crypto.Util.Padding import unpad
from Crypto.Cipher import AES
import hashlib
def sum(P, Q, E):
O = (0, 0)
if P == O: return Q
elif Q == O: return P
else:
x1, y1 = P
x2, y2 = Q
if x1 == x2 and y1 == -y2: return O
Ea, Ep = E['a'], E['p']
if P != Q:
k = ((y2 - y1) * inverse(x2 - x1, Ep)) % Ep
else:
k = ((3*x1**2 + Ea) * inverse(2 * y1, Ep)) % Ep
x3 = (k**2 - x1 - x2) % Ep
y3 = (k*(x1 - x3) - y1) % Ep
return x3, y3
def mul(P, n, E):
O = (0, 0)
Q = P
R = O
while n>0:
if n%2 == 1: R = sum(R, Q, E)
Q = sum(Q, Q, E)
n //=2
return R
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 = 310717010502520989590157367261876774703
E = {
'a': 0x5e009506fcc7eff573bc960d88638fe25e76a9b6c7caeea072a27dcd1fa46abb15b7b6210cf90caba982893ee2779669bac06e267013486b22ff3e24abae2d42,
'b': 0x2ce7d1ca4493b0977f088f6d30d9241f8048fdea112cc385b793bce953998caae680864a7d3aa437ea3ffd1441ca3fb352b0b710bb3f053e980e503be9a7fece,
'p': 0xa15c4fb663a578d8b2496d3151a946119ee42695e18e13e90600192b1d0abdbb6f787f90c8d102ff88e284dd4526f5f6b6c980bf88f1d0490714b67e8a2a2b77
}
b_x = 0x7f0489e4efe6905f039476db54f9b6eac654c780342169155344abc5ac90167adc6b8dabacec643cbe420abffe9760cbc3e8a2b508d24779461c19b20e242a38
b_y = 0xdd04134e747354e5b9618d8cb3f60e03a74a709d4956641b234daa8a65d43df34e18d00a59c070801178d198e8905ef670118c15b0906d3a00a662d3a2736bf
B = (b_x, b_y)
iv = '719700b2470525781cc844db1febd994'
encrypted_flag = '335470f413c225b705db2e930b9d460d3947b3836059fb890b044e46cbb343f0'
a = 2200911270816846838022388357422161552282496835763864725672800875786994850585872907705630132325051034876291845289429009837283760741160188885749171857285407
G = (3034712809375537908102988750113382444008758539448972750581525810900634243392172703684905257490982543775233630011707375189041302436945106395617312498769005, 4986645098582616415690074082237817624424333339074969364527548107042876175480894132576399611027847402879885574130125050842710052291870268101817275410204850)
A = (4748198372895404866752111766626421927481971519483471383813044005699388317650395315193922226704604937454742608233124831870493636003725200307683939875286865, 2421873309002279841021791369884483308051497215798017509805302041102468310636822060707350789776065212606890489706597369526562336256272258544226688832663757)
assert mul(G, a, E) == A
ss = mul(B, a, E)[0]
flag = decrypt_flag(ss, iv, encrypted_flag)
print(flag)
```
### Flag
> ~~`crypto{H3ns3l_lift3d_my_fl4g!}`~~
### Note
- Trình code python của mình hơi phèn nên không kết hợp hết vào cùng một script được :penguin:
---
## 9. Micro Transmissions
### Description
- Been fine tuning my bit lengths to ensure my data packages and calculation times are super efficient.
- Challenge 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}")
```
- Challenge output:
```python=
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'}
```
### Solution
- Trước tiên mình biết được số bits của hai khóa riêng tư `a` và `b` là khá nhỏ, 64 bits so với tiêu chuẩn là 256 bits. Điều này làm giảm tính bảo mật của ECC. Bằng một code sage đơn giản dưới đây, mình có thể tìm lại khóa riêng `a`:
```python=
p = 99061670249353652702595159229088680425828208953931838069069584252923270946291
a = 1
b = 4
E = EllipticCurve(GF(p), [a,b])
G = E(43190960452218023575787899214023014938926631792651638044680168600989609069200, 20971936269255296908588589778128791635639992476076894152303569022736123671173)
Ax = 87360200456784002948566700858113190957688355783112995047798140117594305287669
Bx = 6082896373499126624029343293750138460137531774473450341235217699497602895121
A = E.lift_x(Ax)
B = E.lift_x(Bx)
a = discrete_log(A, G, operation='+', bounds=(0, 2**64))
print(a)
```
hoặc code này (từ anh Quốc - thankiu anh :hearts:):
```python=
p = 99061670249353652702595159229088680425828208953931838069069584252923270946291
a = 1
b = 4
E = EllipticCurve(GF(p), [a,b])
G = E(43190960452218023575787899214023014938926631792651638044680168600989609069200, 20971936269255296908588589778128791635639992476076894152303569022736123671173)
P_A = E.lift_x(ZZ(87360200456784002948566700858113190957688355783112995047798140117594305287669))
P_B = E.lift_x(ZZ(6082896373499126624029343293750138460137531774473450341235217699497602895121))
primes = [p for p, _ in E.order().factor()][:-2]
dlogs = []
for fac in primes:
t = int(G.order()) // int(fac)
dlog = (t*G).discrete_log(t*P_A)
dlogs += [dlog]
a = crt(dlogs, primes)
print(a)
```
và nhận được
```python!
a = 15423694994465574149
```
vác đi giải flag là xong:
```python=
from Crypto.Util.number import inverse
from Crypto.Util.Padding import unpad
from Crypto.Cipher import AES
import hashlib
def sum(P, Q, E):
O = (0, 0)
if P == O: return Q
elif Q == O: return P
else:
x1, y1 = P
x2, y2 = Q
if x1 == x2 and y1 == -y2: return O
Ea, Ep = E['a'], E['p']
if P != Q:
k = ((y2 - y1) * inverse(x2 - x1, Ep)) % Ep
else:
k = ((3*x1**2 + Ea) * inverse(2 * y1, Ep)) % Ep
x3 = (k**2 - x1 - x2) % Ep
y3 = (k*(x1 - x3) - y1) % Ep
return x3, y3
def mul(P, n, E):
O = (0, 0)
Q = P
R = O
while n>0:
if n%2 == 1: R = sum(R, Q, E)
Q = sum(Q, Q, E)
n //=2
return R
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')
g_x = 43190960452218023575787899214023014938926631792651638044680168600989609069200
g_y = 20971936269255296908588589778128791635639992476076894152303569022736123671173
G = (g_x, g_y)
Ax = 87360200456784002948566700858113190957688355783112995047798140117594305287669
Bx = 6082896373499126624029343293750138460137531774473450341235217699497602895121
A = (87360200456784002948566700858113190957688355783112995047798140117594305287669, 59593466123013446762504853712989655201116629740011953821167160210569255093793)
B = (6082896373499126624029343293750138460137531774473450341235217699497602895121, 69060127841060897625121175491407587143129740583487721612423810293908788323020)
p = 99061670249353652702595159229088680425828208953931838069069584252923270946291
E = {
'a': 1,
'b': 4,
'p': p,
}
iv = 'ceb34a8c174d77136455971f08641cc5'
encrypted_flag = 'b503bf04df71cfbd3f464aec2083e9b79c825803a4d4a43697889ad29eb75453'
a = 15423694994465574149
assert mul(G, a, E) == A
ss = mul(B, a, E)[0]
flag = decrypt_flag(ss, iv, encrypted_flag)
print(flag)
```
### Flag
> ~~`crypto{d0nt_l3t_n_b3_t00_sm4ll}
`~~
### Note
- Do `key` là 64 bits, brute force ở đây cũng không phải ý tưởng tồi nên mình vẫn viết code brute ở trên
- Đối với code của anh Quốc chính là sử dụng Pohlig-Hellman. Vì `p` tương đối smooth, tương đối thôi vì ước lớn nhất của `p` cũng khá to nên ban đầu mình tưởng chạy sẽ lâu ngang với brute force, ai ngờ nhanh gấp 10 lần.
- Chi tiết về thuật toán trong bài ở [đây](https://hgarrereyn.gitbooks.io/th3g3ntl3man-ctf-writeups/content/2017/picoCTF_2017/problems/cryptography/ECC2/ECC2.html).
- Tài liệu chi tiết hơn nữa ở [đây](https://koclab.cs.ucsb.edu/teaching/ecc/project/2015Projects/Sommerseth+Hoeiland.pdf).
Sign in with Wallet
Connect another wallet