# RING, FIELD, ELIPTIC CURVE...
# Ring (Zmod)
## Định nghĩa
- Vành các số nguyên modulo $n$:
## Tính chất
- $n$ nguyên tố gồm $n - 1$ phần tử
- $n (!=) 0$ , mọi phần tử khác 0 + không có ước với $n$ thì khả nghịch
## Zmod() in Sage
Cú pháp:

R = Zmod(n) 

- R(a) chuyển số nguyên Python a thành phần tử trong vành
- R.cardinality() trả về $n$
- R.is_prime_field() kiểm tra xem $n$ có nguyên tố không
- R.extension(f) xây dựng mở rộng đại số của vành modulo đa thức f
-
# $Gf(p)$ Hay trường
## Định nghĩa
- Chỉ tồn tại <=> p là 1 số nguyên tố hoặc là 1 số nguyên tố được lũy thừa lên bậc dương.
- Nếu chỉ có p không được lũy thừa, trở thành 1 Ring.
- Nếu p được lũy thừa, $Gf(p^n)$ được xây dựng dưới dạng: $F_p[X]/P(X)$
## Tính chất
- Mỗi trường $Gf(p^n)$ có đúng $p^n$ phần tử và mọi phần tử khác 0 đều có nghịch đảo
- Phép Frobenius $x -> x^p$ là tự động cơ bản trong $Gf(p^n)$ và có thể truy cập qua phương thức conjugate() khi n = 2.

## Tạo trường mở rộng $Gf(p^n)$
### Cú pháp cơ bản

K = GF(p**n, 'a')  
# hoặc rõ hơn với đa thức mô-đun
x = polygen(GF(p), 'x')
K = GF(p**n, names='a', modulus=x^n + …)

- ký hiệu $a$ là phần tử sinh.
### Dùng phương thức extension
Khi đã có $p^m$ rồi, ta có thể mở rộng thêm:

F = GF(p)
R.<x> = F['x']                    # khai báo đa thức
E = F.extension(x^n + …, 'b')     # tạo GF(p^n) với sinh b
L = E.extension(y^m + …, 'c')     # tầng mở rộng tiếp

## Một số phương thức quan trọng
- Hàm khởi tạo và ép kiểu:

F(a)       # ép số nguyên a thành phần tử trong F

- Frobenius và nghịch đảo:

b = a.conjugate()   # cho GF(q^2)
a.inverse()         # nghịch đảo

- Toán tử liên quan đến đa thức:

R.polynomial_ring()    # lấy vành đa thức
I = R.ideal(f)         # lý tưởng
Q = R.quotient(I)      # trường thương

- Ví dụ:

F = GF(2)
R.<x> = F['x']                         # Tạo vành đa thức GF(2)[x]
E.<a> = GF(2^4, modulus=x^4 + x + 1)   # Tạo GF(2^4) với a là phần tử sinh

print(E)           # In ra trường GF(2^4)
print(a^5)         # Luỹ thừa phần tử sinh
print(a.frobenius())  # Frobenius: a ↦ a^2 vì trường cơ sở là GF(2)

# Zmod, Gf Example Challenges
## Farm - CryptoCTF 2021
Đề:

from sage.all import *
import string, base64, math
from flag import flag

ALPHABET = string.printable[:62] + '\\='

F = list(GF(64))

def keygen(l):
    key = [F[randint(1, 63)] for _ in range(l)] 
    key = math.prod(key) # Optimization the key length :D
    return key

def maptofarm(c):
    assert c in ALPHABET
    return F[ALPHABET.index(c)]

def encrypt(msg, key):
    m64 = base64.b64encode(msg)
    enc, pkey = '', key**5 + key**3 + key**2 + 1
    for m in m64:
        enc += ALPHABET[F.index(pkey * maptofarm(chr(m)))]
    return enc

# KEEP IT SECRET 
key = keygen(14) # I think 64**14 > 2**64 is not brute-forcible :P

enc = encrypt(flag, key)
print(f'enc = {enc}')

Output:

enc = "805c9GMYuD5RefTmabUNfS9N9YrkwbAbdZE0df91uCEytcoy9FDSbZ8Ay8jj"

### Phân tích
Key trong đề bài là tích random của 14 phần tử ngẫu nhiên trong GF(64). Sau đó được mod lại trở thành: $pkey = key^5 + key^3 + key^2 + 1$

Plaintext được mã hóa bằng cách:
- Chuyển plaintext thành base64
- Với mỗi phần tử của plaintext, tìm index chứa phần tử đó trong ALPHABET, sau đó thay thế phần tử đó = F[index].
- Sau khi thay thế, phần tử lúc này được nhân thêm với $pkey$. Lúc này vì phép nhân được thực hiện trong $Gf(64)$ nên bản chất nó vẫn nằm trong Trường này. Sau đó, trả về index của tích này trong F, rồi lại lấy phần tử của index đó trong ALPHABET làm 1 phần tử của Ciphertext hay $enc$.
### Solution
Ta thấy được rằng, key trong bài chỉ có thể nằm tring GF(64), nên là không gian key chỉ có 64 phần tử. Hiểu được điều này, ta sẽ tiến hành Brute Force key cho đến khi nào giải mã được Ciphertext được thôi

Và đồng thời, ta cũng sẽ cần phải đảo ngược lại các hàm function trong đề bài:
- Hàm farmtomap() sẽ được mod thành:

def farmtomap(f):
    assert f in F
    return ALPHABET[F.index(f)] 

Full script Sage:

import string 
import base64

F = list(GF(64))
ALPHABET = string.printable[:62] + '\\='
enc = "805c9GMYuD5RefTmabUNfS9N9YrkwbAbdZE0df91uCEytcoy9FDSbZ8Ay8jj"

def farmtomap(f):
    assert f in F
    return ALPHABET[F.index(f)] 
def decrypt(ciphertext, key):
    pkey = key**5 + key**3 + key**2 + 1
    m64 = ''
    for c in ciphertext:
        m64 += farmtomap(F[ALPHABET.index(c)] / pkey)
    return base64.b64decode(m64)

for f in F: 
    try:
        dec = decrypt(enc, f) 
        if b'CCTF' in dec: 
            print(dec)
    except: 
        continue

Flag: CCTF{EnCrYp7I0n_4nD_5u8STitUtIn9_iN_Fi3Ld!}

## Onlude - CryptoCTF
Đề:

from sage.all import *
from flag import flag

global p, alphabet
p = 71
alphabet = '=0123456789abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ$!?_{}<>'

flag = flag.lstrip('CCTF{').rstrip('}')
assert len(flag) == 24

def cross(m):
    return alphabet.index(m)

def prepare(msg):
    A = zero_matrix(GF(p), 11, 11)
    for k in range(len(msg)):
        i, j = 5*k // 11, 5*k % 11
        A[i, j] = cross(msg[k])
    return A

def keygen():
    R = random_matrix(GF(p), 11, 11)
    while True:
        S = random_matrix(GF(p), 11, 11)
        if S.rank() == 11:
            _, L, U = S.LU()
            return R, L, U

def encrypt(A, key):
    R, L, U = key
    S = L * U
    X = A + R
    Y = S * X
    E = L.inverse() * Y
    return E

A = prepare(flag)
key = keygen()
R, L, U = key
S = L * U
E = encrypt(A, key)
print(f'E = \n{E}')
print(f'L * U * L = \n{L * U * L}')
print(f'L^(-1) * S^2 * L = \n{L.inverse() * S**2 * L}')
print(f'R^(-1) * S^8 = \n{R.inverse() * S**8}')

Output:

E = 
[25 55 61 28 11 46 19 50 37  5 21]
[20 57 39  9 25 37 63 31 70 15 47]
[56 31  1  1 50 67 38 14 42 46 14]
[42 54 38 22 19 55  7 18 45 53 39]
[55 26 42 15 48  6 24  4 17 60 64]
[ 1 38 50 10 19 57 26 48  6  4 14]
[13  4 38 54 23 34 54 42 15 56 29]
[26 66  8 48  6 70 44  8 67 68 65]
[56 67 49 61 18 34 53 21  7 48 32]
[15 70 10 34  1 57 70 27 12 33 46]
[25 29 20 21 30 55 63 49 11 36  7]
L * U * L = 
[50  8 21 16 13 33  2 12 35 20 14]
[36 55 36 34 27 28 23 21 62 17  8]
[56 26 49 39 43 30 35 46  0 58 43]
[11 25 25 35 29  0 22 38 53 51 58]
[34 14 69 68  5 32 27  4 27 62 15]
[46 49 36 42 26 12 28 60 54 66 23]
[69 55 30 65 56 13 14 36 26 46 48]
[25 48 16 20 34 57 64 62 61 25 62]
[68 39 11 40 25 11  7 40 24 43 65]
[54 20 40 59 52 60 37 14 32 44  4]
[45 20  7 26 45 45 50 17 41 59 50]
L^(-1) * S^2 * L = 
[34 12 70 21 36  2  2 43  7 14  2]
[ 1 54 59 12 64 35  9  7 49 11 49]
[69 14 10 19 16 27 11  9 26 10 45]
[70 17 41 13 35 58 19 29 70  5 30]
[68 69 67 37 63 69 15 64 66 28 26]
[18 29 64 38 63 67 15 27 64  6 26]
[ 0 12 40 41 48 30 46 52 39 48 58]
[22  3 28 35 55 30 15 17 22 49 55]
[50 55 55 61 45 23 24 32 10 59 69]
[27 21 68 56 67 49 64 53 42 46 14]
[42 66 16 29 42 42 23 49 43  3 23]
R^(-1) * S^8 = 
[51  9 22 61 63 14  2  4 18 18 23]
[33 53 31 31 62 21 66  7 66 68  7]
[59 19 32 21 13 34 16 43 49 25  7]
[44 37  4 29 70 50 46 39 55  4 65]
[29 63 29 43 47 28 40 33  0 62  8]
[45 62 36 68 10 66 26 48 10  6 61]
[43 30 25 18 23 38 61  0 52 46 35]
[ 3 40  6 45 20 55 35 67 25 14 63]
[15 30 61 66 25 33 14 20 60 50 50]
[29 15 53 22 55 64 69 56 44 40  8]
[28 40 69 60 28 41  9 14 29  4 29]

### Phân tích
- Flag có độ dài 24

Đề bài chuyển Flag thành ma trận A, và sẽ tiến hành encrypt nó như sau:
- $E = U(A + R)$
- $HINT1 = L.U.L$
- $HINT2 = L^{-1}.S^2.L$
- $HINT3 = R^{-1}.S^8$

Với đống hints này, ta dễ dàng khôi phục được $U, R$ để lấy được $A$ từ đó khôi phục lại Flag.

Bằng 1 số bước biến đổi, ta được:
- $U = HINT2/HINT1$
- 
### Solution

from sage.all import * 

E = Matrix(GF(71),[[25,55,61,28,11,46,19,50,37,5,21],
[20,57,39,9,25,37,63,31,70,15,47],
[56,31,1,1,50,67,38,14,42,46,14],
[42,54,38,22,19,55,7,18,45,53,39],
[55,26,42,15,48,6,24,4,17,60,64],
[1,38,50,10,19,57,26,48,6,4,14],
[13,4,38,54,23,34,54,42,15,56,29],
[26,66,8,48,6,70,44,8,67,68,65],
[56,67,49,61,18,34,53,21,7,48,32],
[15,70,10,34,1,57,70,27,12,33,46],
[25,29,20,21,30,55,63,49,11,36,7]])

hint1 = Matrix(GF(71),[[50,8,21,16,13,33,2,12,35,20,14],
[36,55,36,34,27,28,23,21,62,17,8],
[56,26,49,39,43,30,35,46,0,58,43],
[11,25,25,35,29,0,22,38,53,51,58],
[34,14,69,68,5,32,27,4,27,62,15],
[46,49,36,42,26,12,28,60,54,66,23],
[69,55,30,65,56,13,14,36,26,46,48],
[25,48,16,20,34,57,64,62,61,25,62],
[68,39,11,40,25,11,7,40,24,43,65],
[54,20,40,59,52,60,37,14,32,44,4],
[45,20,7,26,45,45,50,17,41,59,50]])

hint2=Matrix(GF(71),[[34,12,70,21,36,2,2,43,7,14,2],
[1,54,59,12,64,35,9,7,49,11,49],
[69,14,10,19,16,27,11,9,26,10,45],
[70,17,41,13,35,58,19,29,70,5,30],
[68,69,67,37,63,69,15,64,66,28,26],
[18,29,64,38,63,67,15,27,64,6,26],
[0,12,40,41,48,30,46,52,39,48,58],
[22,3,28,35,55,30,15,17,22,49,55],
[50,55,55,61,45,23,24,32,10,59,69],
[27,21,68,56,67,49,64,53,42,46,14],
[42,66,16,29,42,42,23,49,43,3,23]])

hint3=Matrix(GF(71),[[51,9,22,61,63,14,2,4,18,18,23],
[33,53,31,31,62,21,66,7,66,68,7],
[59,19,32,21,13,34,16,43,49,25,7],
[44,37,4,29,70,50,46,39,55,4,65],
[29,63,29,43,47,28,40,33,0,62,8],
[45,62,36,68,10,66,26,48,10,6,61],
[43,30,25,18,23,38,61,0,52,46,35],
[3,40,6,45,20,55,35,67,25,14,63],
[15,30,61,66,25,33,14,20,60,50,50],
[29,15,53,22,55,64,69,56,44,40,8],
[28,40,69,60,28,41,9,14,29,4,29]])
alphabet = '=0123456789abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ$!?_{}<>'
U = hint2 / hint1 
R_inverse = hint3/U/hint1/U/hint1/U/hint1/U/hint1
R = R_inverse.inverse() 
def recover_flag(A):
    flag_chars = ''
    for k in range(24):
        i, j = 5*k // 11, 5*k % 11
        idx = int(A[i, j])  # phần tử thuộc GF(p), cần cast về int
        flag_chars += (alphabet[idx])
    return 'CCTF{' + (flag_chars) + '}'

A = (U.inverse())*E - R 
recover_flag(A)

# Permutation Cipher
## Định nghĩa
Tái sắp xếp các ký tự của plaintext nhưng không thay đổi ký tự. Khi key chính là 1 permutation có kích thước là $e$, ta chia plaintext thành các khối có độ dài là $e$ rồi hoán vị theo theo key đó.
## Cách hoạt động
- Chia khối: Cho plaintext thành các khối có cùng độ dài bằng độ dài key, có thể thêm các ký tự null nếu không đủ.
- Hoán vị: Với mỗi khối, sắp xếp lại ký tự theo permutation key: ví dụ key “4312” nghĩa là ký tự thứ nhất của khối mới lấy từ vị trí 4 của khối cũ, v.v.
- Đọc kết quả
> Trong nhiều trường hợp, khi cách mã hóa này áp dụng trên 1 string cố định, thì nếu biết được cách mà nó mã hóa ta có thể áp dụng nhiều lần hàm mã hóa này lên Ciphertext thì đến 1 thời điểm nào đó nó sẽ quay trở lại thành Plaintext ban đầu. Đây là tính chất của Permutation Cipher.
# Permutation Cipher Example Challenges
## Transposed - Jordan & Tunisia National CTF
Đề:

import random

W = 7
perm = range(W)
random.shuffle(perm)

msg = open("flag.txt").read().strip()
while len(msg) % (2*W):
    msg += "."

for i in xrange(100):
    msg = msg[1:] + msg[:1]
    msg = msg[0::2] + msg[1::2]
    msg = msg[1:] + msg[:1]
    res = ""
    for j in xrange(0, len(msg), W):
        for k in xrange(W):
            res += msg[j:j+W][perm[k]]
    msg = res
print msg

### Phân tích

W = 7
perm = range(W)
random.shuffle(perm)

- Tạo bảng hoán vị cho toàn bộ mã hóa

msg = open("flag.txt").read().strip()
while len(msg) % (2*W):
    msg += "."

- Flag hay $msg$ sẽ được padd cho đủ 14 phần tử.

for i in xrange(100):
    msg = msg[1:] + msg[:1]
    msg = msg[0::2] + msg[1::2]
    msg = msg[1:] + msg[:1]
    res = ""
    for j in xrange(0, len(msg), W):
        for k in xrange(W):
            res += msg[j:j+W][perm[k]]
    msg = res

Trong mỗi vòng lặp:
- $msg$ bị xoay trái 1 đơn vị
- Sau đó, tách các phần tử chẵn và lẻ lần lượt rồi ghép chúng vào với nhau
- Xoay trái thêm 1 phát nữa
- Trong vòng lặp con:
- - Chia $msg$ thành các khối có 7 phần tử, sau đó tiến hành hoán vị các ký tự theo bảng hoán vị.
### Solution
Vì mọi hoán vị diễn ra trên 1 string cố định, nên với $d$ lần hoán vị tương đương string sẽ trở về trạng thái ban đầu. Ta đơn giản chỉ cân bruteforce Permutations_map rồi dùng nó hoán vị nhiều lần Ciphertext là được:

res, sol = [], []
def gen_permu(n): 
    if len(sol) == n: 
        res.append(sol.copy()) 
        return
    
    for i in range(n): 
        if i not in sol: 
            sol.append(i) 
            gen_permu(n) 
            sol.pop() 
gen_permu(7)  
permutations = res
W = 7 
msg_enc = "L{NTP#AGLCSF.#OAR4A#STOL11__}PYCCTO1N#RS.S"
for perm in permutations:
    msg = msg_enc
    for i in range(100):
        msg = msg[1:] + msg[:1]
        msg = msg[0::2] + msg[1::2]
        msg = msg[1:] + msg[:1]
        res = ""
        for j in range(0, len(msg), W):
            for k in range(W):
                res += msg[j:j+W][perm[k]]
        msg = res
        if "FLAG{" in msg: 
            print(res) 

Flag = FLAG{##CL4SS1CAL_CRYPTO_TRANSPOS1T1ON##}
## Permutation[452] - Grey Cat The Flag 2022
Đề:

from secrets import randbits
from hashlib import shake_256
import random
import perm

FLAG = <REDACTED>

def encrypt(key : str) -> str:
    otp = shake_256(key.encode()).digest(len(FLAG))
    return xor(otp, FLAG).hex()

def xor(a : bytes, b : bytes) -> bytes:
    return bytes([ x ^ y for x, y in zip(a, b)])

n = 5000
h = 2048

arr = [i for i in range(n)]
random.shuffle(arr)

g = perm.Perm(arr)
a = randbits(h); b = randbits(h)
A = g ** a; B = g ** b
S = A ** b
key = str(S)

print(f"g = [{g}]"); print(f"A = [{A}]"); print(f"B = [{B}]"); 

print(f"c = {encrypt(key)}")

File perm:

class Perm():
    def __init__(self, arr):
        assert self.valid(arr)
        self.internal = arr
        self.n = len(arr)

    def valid(self, arr):
        x = sorted(arr)
        n = len(arr)
        for i in range(n):
            if (x[i] != i):
                return False
        return True

    def __str__(self):
        return ",".join(map(str, self.internal))

    def __mul__(self, other):
        assert other.n == self.n
        res = []
        for i in other.internal:
            res.append(self.internal[i])
        return Perm(res)

    def __pow__(self, a):
        res = Perm([i for i in range(self.n)])
        g = Perm(self.internal)
        while (a > 0):
            if (a & 1): res = res * g
            g = g * g
            a //= 2
        return res

Output:

g = ... 
A = ... 
B = ...
c = 9f8a883d7e045010619a7aba5c0cdeb33ee0482626e2c5e718b3ef955ad9b4986d4406b6a1f53e78e506c7dcf806f964090a1e44fe2737b883

### Phân tích

# Afffine Cipher
## Định nghĩa
Sử dụng hàm tuyến tính trên tập giá trị số của ký tự:
$E(x) = a.x + b \mod m$
- m là kịch thước của bảng chữ cái.
- $a, b$ là khóa.
- $GCD(a, m) = 1$ để có thể giải mã
## Cách hoạt động
1. Chuẩn hóa: Gán giá trị số cho ký tự: ví dụ A=0, B=1,…, Z=25.
2. Mã hóa: Vỡi mối giá trị của x, có $y = (ã + b) \mod m$.
3. Ghép lại
## A Fine Cipher - RITSEC CTF 2023
ĐỀ: 
### Phaân tích:
Ta lấy 1 câu đơn giản làm mẫu trước. Khi gặp những đề bài thế này + gợi ý cách encrypt thì ta sẽ dùng `dcode` để mò thôi
### Solution
FLAG: RS{IFYOUAREINTERESTEDCHECKOUTMORECRYTPOCTFSATCRYPTOHACK}

## zakukozh_DONE
ĐỀ:
Đề bài cho ta 1 file nhị phân bị mã hóa Cipher:
`zakukozh.bin`
Nhiệm vụ của ta là giải mã nó.
### Phân tích
Ta biết rằng mỗi phần tử của Affine Cipher được mã hóa theo công thức:
$E(x) = a.x + b \mod m$

- Đây là file nhị phân, ta đoán rằng $m = 256$
- $a, b$ sẽ thử bruteforce trong khoảng $m$
- Đồng thời, nếu đây là file ảnh `jpg`, 2 bytes đầu sẽ là `255, 216`, nếu là png sẽ là `137, 80`.
- Với mỗi $a, b$ lụm được, ta thử giải mã toàn bộ file để lấy ảnh và chọn ảnh có flag.
### Solution
- Bruteforce $a, b$:

from math import gcd 

data  = bytearray(open('zakukozh.bin', 'rb').read()) 
m = 256 

def affine(x, a , b): 
    return (a*x + b) % m 

for a in range(m): 
    if gcd(a, m) != 1: 
        continue 
    for b in range(m): 
        new = [affine(data[0], a ,b), affine(data[1],a, b)] 
        if new == [255, 216]: 
            print("jpg", a, b) 
        elif new == [137, 80]: 
            print("png", a, b)  

- Output:

jpg 177 159
png 239 233

- Final check:

jpg = bytearray([affine(x, 177, 159) for x in list(data)]) 
png = bytearray([affine(x, 239, 233) for x in list(data)]) 
open("possible_jpg.jpg", "wb").write(jpg)
open("possible_png.png", "wb").write(png)

Flag: 

# Eliptic Curve Cryptography -CryptoHack
# Background Reading
> ECC không tự nhiên mà đến, mà mày phải là người tìm nó

Khi nghĩ đến ECC, ta tưởng tượng 1 đường cong Ellip. Ta sẽ nghiên cứu phương trình `Weierstrass`: $E:y^2 = x^3 + a.x + b$
- Đặc biệt: $4.a^3 + 27.b^2 != 0$

Elliptic Curve là tập hợp các điểm thỏa mãn phương trình trên trong 1 trường hữu hạn

`Point addition`: Cho 2 điểm P và Q đều nằm trên Elliptic Curve, ta định nghĩa 1 điểm thứ 3 là R = P + Q cũng nằm trên đường cong đó(Phép công này tuân theo cấu trúc Abel):

Khi nhân 1 điểm với 1 số nguyên(Hay scaling), ta có thể lấy 1 VD:
$Q = [2].P = P + P$
Điểm mấu chốt ở đây là: Khi cho $Q, P$ và bắt tìm scalar $n$ thì rất khó vì đây chính là bẫy 1 chiều Trapdoor của hệ thống Crypto này. Toàn bộ hệ thống sẽ dựa vào độ khó của việc tìm $n$, hay n thực chất sẽ chính là ẩn số hay $private$ mà kẻ tấn công cần tìm.

`Understanding Point Addition`:
- Chọn 2 điểm $P, Q$ trên Elliptic Curve.
- Nối 2 đểm này thành 1 đường thẳng và điểm thứ 3 $R$ chính là giao điểm của đường $PQ$ với Elliptic Curve.
- Lấy $R'$ là nghịch đảo $y$ của $R$, ta được $R' = (x_R, -y_R)$.
- $P + Q = R'$ -> Đây chính là cách ta hiểu về `point addition`

`VẬY CÒN NẾU TA CỘNG 1 ĐIỂM VỚI CHÍNH NÓ THÌ SAO?`
- Gỉa sử ta cộng $P + P$, vậy ta không thể vẽ đường thẳng qua 2 điểm khác nhau được.
- Nên thay vào đó, lấy tiếp tuyến với Elliptic Curve tại chính điểm $P$ đó.
- Và cứ thế theo logic cũ, đường tiếp tuyến này rồi sẽ giao với Elliptic Curve tại 1 điểm là $R$. Ta được: $P + P = R'$

`VẬY NẾU PQ HAY PP KHÔNG CẮT ELLIPTIC CURVE TẠI ĐIỂM NÀO THÌ SAO?`
(VD: P & Q đối xứng qua trục hoành)
- Lúc này ta lấy điểm thứ 3 chính là điểm vô cực $O$ - hay điểm đơn vị.
- Phần tử $O$ được định nghĩa: $P + (-P) = O$


Flag: Cờ của đề bài là tên nhóm có tính chất giao hoán, vậy thì sẽ là: `crypto{Aelian}`
# Starter
## Point Negation
Đoạn này cơ bản giống phần Background, nhấn mạnh 1 chút rằng ta đang nghiên cứu ECC nên các định nghĩa đều phải để trong $Fp$.

Bài tập ở phần này là tìm $Q$ sao cho với P cho trước thỏa mãn $P + Q = O$ -> Tức là $Q = -P$

Ta đơn giản chỉ cần: Lấy nghịch đảo của $P$ đơn giản là là $P' = P(x, -y)$

Vậy với $P(8045,6936)$ ta được Flag là: `crypto{8045,2803}
`

## Point Addition
Để tính tổng 2 điểm trong Elliptic Curve. Ta có thể sử dụng 1 trong 2 cách:

- Đầu tiên là sử dụng Hàm tự xây dựng:

def modinv(a, p):
    # Nghịch đảo modulo dùng extended Euclidean algorithm
    return pow(a, -1, p)

def ec_add(P, Q, a, p):
    # Nếu một trong hai điểm là điểm "vô cực", trả lại điểm kia
    if P is None:
        return Q
    if Q is None:
        return P
    
    x1, y1 = P
    x2, y2 = Q

    # Trường hợp P = -Q → kết quả là điểm vô cực
    if x1 == x2 and (y1 + y2) % p == 0:
        return None

    if P != Q:
        # Slope λ = (y2 - y1) / (x2 - x1)
        numerator = (y2 - y1) % p
        denominator = (x2 - x1) % p
        lam = (numerator * modinv(denominator, p)) % p
    else:
        # P == Q → dùng công thức tiếp tuyến
        numerator = (3 * x1 * x1 + a) % p
        denominator = (2 * y1) % p
        lam = (numerator * modinv(denominator, p)) % p

    # Tính x3, y3
    x3 = (lam * lam - x1 - x2) % p
    y3 = (lam * (x1 - x3) - y1) % p

    return (x3, y3)

- Sử dụng Sagemath: VD câu này lun:

from sage.all import * 

p = 9739 
F = FiniteField(p) 

E = EllipticCurve(F, [497, 1768]) 
P = E(493,5564) 
Q = E(1539,4742) 
R = E(4403,5202) 
S = P + P + Q + R
print(S)

Flag: crypto{4215,2162}
## Scalar Multiplication
Hàm giả được cung cấp để tính Scaling, but we gonna use Sage instead:


Solution:

from sage.all import * 

a = 497 
b = 1768 
p = 9739 

E = EllipticCurve(GF(p), [a, b]) 
P = E(2339,2213) 
print(7863*P)

Flag: crypto{9467,2742}
## Curves and Logs
Bài toán logarit rời nhạc trong Elliptic Curve: `The Elliptic Curve Discrete Logarithm Problem (ECDLP)` là bài toán tìm $n$ trong $Q = n.P trong ECC.

`Thuật toán DFH`:
Cả 2 bên sẽ đồng ý các tham số sau:
- Elliptic Curve: $E$
- Prime: $p$
- 1 Hàm sinh $G \in E$ với bậc (order) là số nguyên tố $q$ => $H = <G>$ là nhóm con được sinh ra bởi $G$, gồm tất cả $nG$ với $n \in Zq$

Lúc này, cả 2 bên sẽ chọn cho mình các $n$, lúc này logic encrypt và decrypt sẽ khá giống `DFH`:

- Alice chọn $n_A$, tính $Q_A = n_A.G$ rồi gửi cho Bob.
- Bob cũng tương tự, Alice sẽ nhận được $Q_B = n_B.G$
- Lúc này thì mỗi người nhân Gía trị mà mình nhận được với khóa riêng là đã có thể đều nhìn thấy được cùng 1 Giá trị.

Đề bài phần này yêu cầu ta tính toán tạo độ $x$ của $S$ với điều kiện biết trước EC và $G \& n$.

from sage.all import * 
from hashlib import sha1
a = 497 
b = 1768 
p = 9739 

E = EllipticCurve(GF(p), [a, b]) 
Qa = E(815,3190) 
nb = 1829 
flag = int((Qa*nb)[0]) 
flag = sha1((str(flag).encode())).hexdigest() 
print(flag)

Flag: crypto{80e5212754a824d3a4aed185ace4f9cac0f908bf}

## Efficient Exchange

Với tất cả giá trị $x$ mà Alice và Bob nhận được, chỉ có thể có 2 giá trị của $y$ ứng với nó.

Đề bài cho ta giá trị: $x_A$ của $Q_A$ và $n_B$. Nhiệm vụ của ta là phải tìm lại Plaintext ban đầu với việc được cho trước hàm decrypt và các dữ liệu liên quan.

from sage.all import * 
from hashlib import sha1
a = 497 
b = 1768 
p = 9739 
F = FiniteField(p)
E = EllipticCurve(GF(p), [a, b]) 
x = F(4726) 
n_b = F(6534) 
ysqrt = x**3 + a*x + b 
y = (ysqrt.sqrt(all = True))[0] 
S = E(x,y)*n_b 
print(S)

Đây là hàm tính giá trị của y, từ đó có được Shared để nhét vào file `decrypt`:

Final:

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)

Flag: crypto{3ff1c1ent_k3y_3xch4ng3}

# Parameter Choice
## Smooth Criminal

Đề bài này cho ta thông tin về Public của Bob, Public của Alice, G, Elliptic Curve và các thông tin râu ria để Decrypt Ciphertext

Mục tiêu chính của ta lần này đó chính là làm thế nào để tìm lại được private $n$ của Alice, biết G và Public.

`Bài toán logarit rời rạc trong ECC - ECDLP`

Điều kiện triển khai:
- Các điểm phải nằm trên Elliptic Curve Fp cho trước
- G sinh ra 1 nhóm con và Public phải thuộc nhóm đó
- Xác định được order - bậc của G:
- Nhỏ: bruteforce
- Smooth: Pohlig-Hellman
- Prime to vừa: BigstepGiantstep

-> Nma thật ra ta có thể thử giải bằng Sagemath và tùy vào thời gian chờ đợi kết quả hay việc có ra được kết quả hay không sẽ cho ta biết độ khó hay độ khả thi của Bài toán này.

from sage.all import * 
from hashlib import sha1
from Crypto.Cipher import AES
from Crypto.Util.Padding import unpad
import hashlib

def decrypt_flag(shared_secret: int, iv_hex: str, ciphertext_hex: str):
    # Tạo AES key từ shared_secret (giống y trong encrypt_flag)
    sha1 = hashlib.sha1()
    sha1.update(str(shared_secret).encode('ascii'))
    key = sha1.digest()[:16]

    # Giải mã AES
    iv = bytes.fromhex(iv_hex)
    ciphertext = bytes.fromhex(ciphertext_hex)

    cipher = AES.new(key, AES.MODE_CBC, iv)
    plaintext_padded = cipher.decrypt(ciphertext)
    
    try:
        plaintext = unpad(plaintext_padded, 16)
    except ValueError as e:
        raise ValueError("Sai shared secret hoặc ciphertext bị lỗi padding!") from e

    return plaintext

p = 310717010502520989590157367261876774703
a = 2
b = 3
F = FiniteField(p)
E = EllipticCurve(GF(p), [a, b]) 
g_x = 179210853392303317793440285562762725654
g_y = 105268671499942631758568591033409611165
G = E(g_x, g_y) 
order  = G.order() 
public = E(280810182131414898730378982766101210916, 291506490768054478159835604632710368904) 
n = G.discrete_log(public)
b_x = 272640099140026426377756188075937988094
b_y = 51062462309521034358726608268084433317
Bob_public = E(b_x, b_y) 
iv = '07e2628b590095a5e332d397b8a59aa7'
encrypted_flag = '8220b7c47b36777a737f5ef9caa2814cf20c1c1ef496ec21a9b4833da24a008d0870d3ac3a6ad80065c138a2ed6136af'
print(decrypt_flag((Bob_public*n)[0], iv, encrypted_flag))

Flag: crypto{n07_4ll_curv3s_4r3_s4f3_curv3s}

## Exceptional Curves

Câu này em ăn gian 1 xíu, hẹ hẹ Sagemath no.1:

from sage.all import * 
from Crypto.Cipher import AES
from Crypto.Util.Padding import unpad
import hashlib
from binascii import unhexlify

def decrypt_flag(b_x, b_y, iv_hex, ciphertext_hex, nA, E):
    # Reconstruct Bob's public key
    B = E(b_x, b_y)
    
    # Compute shared secret
    S = B * nA
    x_shared = S.xy()[0]

    # Derive AES key
    sha1 = hashlib.sha1()
    sha1.update(str(x_shared).encode('ascii'))
    key = sha1.digest()[:16]

    # Convert IV and ciphertext
    iv = unhexlify(iv_hex)
    ciphertext = unhexlify(ciphertext_hex)

    # AES decryption
    cipher = AES.new(key, AES.MODE_CBC, iv)
    plaintext = unpad(cipher.decrypt(ciphertext), 16)
    return plaintext

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

# Define curve
E = EllipticCurve(GF(p), [a, b])
PublicKey = E(4748198372895404866752111766626421927481971519483471383813044005699388317650395315193922226704604937454742608233124831870493636003725200307683939875286865 , 2421873309002279841021791369884483308051497215798017509805302041102468310636822060707350789776065212606890489706597369526562336256272258544226688832663757)
G = E(3034712809375537908102988750113382444008758539448972750581525810900634243392172703684905257490982543775233630011707375189041302436945106395617312498769005, 4986645098582616415690074082237817624424333339074969364527548107042876175480894132576399611027847402879885574130125050842710052291870268101817275410204850) 
b_x = 0x7f0489e4efe6905f039476db54f9b6eac654c780342169155344abc5ac90167adc6b8dabacec643cbe420abffe9760cbc3e8a2b508d24779461c19b20e242a38
b_y = 0xdd04134e747354e5b9618d8cb3f60e03a74a709d4956641b234daa8a65d43df34e18d00a59c070801178d198e8905ef670118c15b0906d3a00a662d3a2736bf 
na = G.discrete_log(PublicKey) 
iv = '719700b2470525781cc844db1febd994'
encrypted_flag = '335470f413c225b705db2e930b9d460d3947b3836059fb890b044e46cbb343f0' 
print(decrypt_flag(b_x, b_y, iv, encrypted_flag, na, E))

Flag: crypto{H3ns3l_lift3d_my_fl4g!}

## Micro Transmissions

Câu này hướng tới việc sử dụng thuật toán Pohlig Hellman

Thuật toán Pohlig Hellman dành cho điều kiện private key $n$ yếu:

order =  G.order()
print(order) 
print(factor(order))
max_value_n = 2**64 

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 = int(crt(results, factors))
print(n_a)

Full script:

from sage.all import * 
from Crypto.Cipher import AES
from Crypto.Util.Padding import unpad
import hashlib

def decrypt_flag(iv_hex: str, ciphertext_hex: str, shared_secret: int) -> bytes:
    """
    Giải mã AES-CBC của flag từ IV, ciphertext (cả hai ở dạng hex) và shared secret (int).
    Trả về plaintext (FLAG) ở dạng bytes.
    """
    # Derive AES key từ shared_secret
    sha1 = hashlib.sha1()
    sha1.update(str(shared_secret).encode('ascii'))
    key = sha1.digest()[:16]

    # Chuyển IV và ciphertext từ hex về bytes
    iv = bytes.fromhex(iv_hex)
    ciphertext = bytes.fromhex(ciphertext_hex)

    # Giải mã và bỏ padding
    cipher = AES.new(key, AES.MODE_CBC, iv)
    plaintext = (cipher.decrypt(ciphertext), AES.block_size)
    return plaintext

# Curve params
p = 99061670249353652702595159229088680425828208953931838069069584252923270946291
a = 1
b = 4
F = FiniteField(p)
# Define curve
E = EllipticCurve(GF(p), [a, b])
x = F(87360200456784002948566700858113190957688355783112995047798140117594305287669)
ysqrt = x**3 + a*x + b 
y1 = (ysqrt.sqrt(all = True))[0] 
y2 = (ysqrt.sqrt(all = True))[1]
G = E(43190960452218023575787899214023014938926631792651638044680168600989609069200 , 20971936269255296908588589778128791635639992476076894152303569022736123671173) 
A = E(87360200456784002948566700858113190957688355783112995047798140117594305287669, y2)
xb = F(6082896373499126624029343293750138460137531774473450341235217699497602895121)
ybsqrt = xb**3 + a*xb + b  
B = E(xb, ybsqrt.sqrt(all = True)[0]) 

order =  G.order()
print(order) 
print(factor(order))
max_value_n = 2**64 

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 = int(crt(results, factors))
print(n_a)
def gen_shared_secret(P, n):
	S = n*P
	return S.xy()[0]
iv = 'ceb34a8c174d77136455971f08641cc5'
encrypted_flag = 'b503bf04df71cfbd3f464aec2083e9b79c825803a4d4a43697889ad29eb75453' 
shared = gen_shared_secret(B, n_a) 
print(decrypt_flag(iv, encrypted_flag, shared))

Flag: crypto{d0nt_l3t_n_b3_t00_sm4ll}

## Elliptic Nodes
Phân này yêu cầu ta phải giải 2 bài toán:
- Tìm lại $a, b$ của EC cho trước biết Public và $G$
- Với a, b tìm được, Ta giải bài toán logarit rời nhạc với EC dạng `Singular`

### Bài toán tìm $a, b$

Khá dễ, chỉ cần giải phương trình modulo là xong.

### Bài toán tính Logarit rời rạc với EC dạng Singular

Ý tưởng: Chuyển bài toán từ `ECDLP` sang bài toán logarit rời rạc trong $F(p, *)$ ->Sagemath có thể giải bài toán này dễ hơn nhiều:
- Ta sẽ phải shift EC của ta thành conic: $y^2 = x'^2(x' + C)$.
- Nhóm này rất đặc biệt, nó tham số hóa toàn bộ các điểm nằm trên đó bằng 1 phân tử trong $Fp^*$.
- Nói cách khác: Nó chuyển tử nhóm cộng EC sang nhóm nhân $Fp$
- Đặt $w = \frac{y}{x'}$, ta có thể biến đổi được thành: $z = \frac{y - t.x'}{y + t.x'}$ với ($t = \sqrt{C}$) . Đây là ánh xạ `Mobius` - Mỗi 1 cặp $(y, x')$ ánh xạ thành 1 giá trị $z \in F_p^*$.
- Ánh xạ $G, Q_A$ sang $F_p^*$, giải logarit rời rạc để lụm $d$

Vậy thì $x' = x + s$ thì ta nên chọn $s$ là bao nhiêu?

Quay trở lại với phương trình EC ban đầu, ta có:
$y^2 = x^3 + a.x + b$, ta thử thay $x = x' + s$ vào nó:
Ta được:
- $x^3 + a.x + b = (x' + s)^3 + a.(x' + s) + b$
- $x^3 + a.x + b = x'^3 + 3.s.x'^2 + (3s^2 + a).x' + (s^3 + a.s + b)$
- Để có thể chuyển về dạng đường `conic` thì buộc: $3s^2 + a$ và $s^3 + a.s + b$ phải $= 0$ trong $Fp$
- Vậy đồng nghĩa với việc $s$ hay hệ số shift $x$ phải là nghiệm của: $s^3 + a.s + b$
- Khi tìm được $s$, ta được đường `conic` là: $x'^2(x' + 3s)$
- Nhiệm vụ cuối cùng của ta lúc này là ánh xạ $Q_A$ và $G$ để lấy loga thôi.

### Solution

from sage.all import * 
from Crypto.Util.number import long_to_bytes

xq = 2582928974243465355371953056699793745022552378548418288211138499777818633265
yq = 2421683573446497972507172385881793260176370025964652384676141384239699096612
p = 4368590184733545720227961182704359358435747188309319510520316493183539079703

xg = 8742397231329873984594235438374590234800923467289367269837473862487362482
yg = 225987949353410341392975247044711665782695329311463646299187580326445253608 

a = ((-(yg**2 - yq**2) - (xq**3 - xg**3) % p)*pow(xq - xg, -1, p)) % p  
b = (yg**2 - xg**3 - a*xg) % p
R = PolynomialRing(GF(p), 'x')
x = R.gen()
f = x**3 + a*x + b 
s = f.roots() 
s1 = s[0][0] 
s2 = s[1][0]
shift = 0
if GF(p)(s1*3).is_square(): 
    shift = s1
if GF(p)(s2*3).is_square(): 
    shift = s2 
newf = f.subs(x = x + shift) 
t = GF(p)(3*shift).square_root() 
zxq = (xq - shift) 
zxg = (xg - shift) 
zQ = (yq - t*zxq)/(yq + t*zxq) % p 
zG = (yg - t*zxg)/(yg + t*zxg) % p
d = discrete_log(zQ, zG)
print(long_to_bytes(d)) 

Flag: crypto{s1ngul4r_s1mplif1c4t1on}

## Moving Problems
Với cái đề bài như thế này gợi ý luôn cho ta rằng Ta cần ứng dụng `MOV - Menezes–Okamoto–Vanstone` Attack để giải.

### MOV Attack
Dạng tấn công này xuất hiện không nhiều, chủ yếu đánh vào các curve có embedding level nhỏ:
$$
r | p^k - 1
$$

- Câu này ta tính được $k = 2$, vậy thì ta hoàn toàn có thể áp dụng được thuật toán MOV để tấn công.

Thuật toán:

#               Đây là Thuật Toán MOV 
# Find embedding degree k
Gn = G.order()
k = 1
while p^k % Gn != 1:
    k += 1
print("Found k:", k)

# Select private key, and calculate public key Q
Q = E(1110072782478160369250829345256, 800079550745409318906383650948)

# Define new curve mod p^k and the points on it
Ek = EllipticCurve(GF(p ^ k), [a, b])
Gk = Ek(G)
Qk = Ek(Q)
Rk = Ek.random_point()

# Find a point T with order d such that d divides G's order
m = Rk.order()
d = gcd(m, Gn)
Tk = (m // d) * Rk
assert Tk.order() == d
assert (Gn*Tk).is_zero() # Point INFINITY

# Using T, pair G and Q to integers g and q such that q=g^n (mod p^k)
g = Gk.weil_pairing(Tk, Gn)
q = Qk.weil_pairing(Tk, Gn)
# Alternatively:
#g = Gk.tate_pairing(Tk, Gn, k)
#q = Qk.tate_pairing(Tk, Gn, k)

print("Calculating private key...")
found_key = q.log(g)
print((found_key)) 

> Lưu ý nên chạy trong môi trường Sage chứ chạy file Python import Sage đéo chạy được
### Solution

from sage.all import * 
from Crypto.Cipher import AES
from Crypto.Util.Padding import unpad
import hashlib

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

def decrypt_flag(iv_hex: str, ciphertext_hex: str, shared_secret: int) -> bytes:
    """
    Giải mã AES-CBC của flag từ IV, ciphertext (cả hai ở dạng hex) và shared secret (int).
    Trả về plaintext (FLAG) ở dạng bytes.
    """
    # Derive AES key từ shared_secret
    sha1 = hashlib.sha1()
    sha1.update(str(shared_secret).encode('ascii'))
    key = sha1.digest()[:16]

    # Chuyển IV và ciphertext từ hex về bytes
    iv = bytes.fromhex(iv_hex)
    ciphertext = bytes.fromhex(ciphertext_hex)

    # Giải mã và bỏ padding
    cipher = AES.new(key, AES.MODE_CBC, iv)
    plaintext = (cipher.decrypt(ciphertext), AES.block_size)
    return plaintext

p = 1331169830894825846283645180581
a = -35
b = 98
E = EllipticCurve(GF(p), [a, b])
G = E(479691812266187139164535778017, 568535594075310466177352868412) 

#---------------------------------------------------------------------------------------------------
#               Đây là Thuật Toán MOV 
# Find embedding degree k
Gn = G.order()
k = 1
while p^k % Gn != 1:
    k += 1
print("Found k:", k)

# Select private key, and calculate public key Q
Q = E(1110072782478160369250829345256, 800079550745409318906383650948)

# Define new curve mod p^k and the points on it
Ek = EllipticCurve(GF(p ^ k), [a, b])
Gk = Ek(G)
Qk = Ek(Q)
Rk = Ek.random_point()

# Find a point T with order d such that d divides G's order
m = Rk.order()
d = gcd(m, Gn)
Tk = (m // d) * Rk
assert Tk.order() == d
assert (Gn*Tk).is_zero() # Point INFINITY

# Using T, pair G and Q to integers g and q such that q=g^n (mod p^k)
g = Gk.weil_pairing(Tk, Gn)
q = Qk.weil_pairing(Tk, Gn)
# Alternatively:
#g = Gk.tate_pairing(Tk, Gn, k)
#q = Qk.tate_pairing(Tk, Gn, k)

print("Calculating private key...")
found_key = q.log(g)
print((found_key)) 

#---------------------------------------------------------------------------------------------------

Qa = E(1110072782478160369250829345256 , 800079550745409318906383650948 )
Qb = E(1290982289093010194550717223760 , 762857612860564354370535420319 )
iv = 'eac58c26203c04f68d63dc2c58d79aca'
encrypted_flag = 'bb9ecbd3662d0671fd222ccb07e27b5500f304e3621a6f8e9c815bc8e4e6ee6ebc718ce9ca115cb4e41acb90dbcabb0d'

shared = gen_shared_secret(Qb, found_key) 
print(decrypt_flag(iv, encrypted_flag, shared))

Flag: crypto{MOV_attack_on_non_supersingular_curves}

# Signature

Trong ECC cũng có hệ thống chữ ký giống RSA. Nó là 1 giá trị số đặc biệt giúp xác minh thông tin tin nhắn.
## Gen Signature
Một Signature có cấu trúc $(r, s)$.

Để tạo 1 Signature như vậy, ta có những bước như sau:
- Tính toán 1 số ngẫu nhiên $k$, sau đó nhân nó với điểm sinh $G$ được 1 điểm $R = (x_R, y_R)$
- $n$ là bậc của đường Cong, $r = x_R \mod n$ chính là $r$ trong cấu trúc Signature.
- Với $d_A$ là private key của người ký, ta sẽ tiến hành tính giá trị của $s$ theo công thức:
$s = (e + r.d_A).k^{-1} \mod n$ với $e$ là giá trị hash của tin nhắn.
## Digestive

Đề bài này muốn ta khai thác lỗ hổng của thuật toán ký `NIST192p` và hàm `băm không băm`.

- `NIST192p`: Chỉ ký vào 24 bytes đầu tiên.
- Hàm băm của code không hề băm tí nào :v.
=> Nắm được điều này, ta chỉ cần dùng 1 username rất dài, khi `kí` và khi `verify`, ta chỉ làm việc với 24 byte đầu.
=> Đồng thời, ta cũng đè thêm vào cuối file JSON gửi đi `admin : true`, khi hệ thống xác minh thông tin của trường `admin` nó sẽ lấy cái ở sau cùng.
### Solution

import requests
import json

# URL cơ sở của server CTF
BASE_URL = "https://web.cryptohack.org/digestive/" # Thay thế bằng URL thực tế của bài CTF nếu khác

def sign(username): 
    return requests.get(BASE_URL + '/sign/' + username).json()
def verify(msg, signature): 
    return requests.get(BASE_URL + '/verify/' + msg + '/' + signature).text

username = 'mosumsue'*100
sending = '{"admin": false, "username": "' + username + '", "admin": true }'
output = sign(username) 
print(output)
sig = (output["signature"])
flag = verify(sending, sig)
print(flag)

Flag: crypto{thanx_for_ctf_inspiration_https://mastodon.social/@filippo/109360453402691894}
## Curveball

Mấu chốt của bài tập này là muốn ta đưa vào sever 1 điểm sinh $G$ và 1 khóa riêng $d$ sao cho khi tính Public Key trùng với Public Key của `bing`.

Để làm được thì cũng đơn giản thôi, ta chỉ cần lấy Public Key của `bing` rồi chia cho $d$ được ta chọn sẵn trong trường $n$ với $n$ là bậc của $G$. Sau đó ta lấy kết quả làm 1 điểm sinh rồi chỉ cần đưa nó cùng với $d$ lên sever là xong
### Solution

from sage.all import *
import socket
import json
p = 0xFFFFFFFF00000001000000000000000000000000FFFFFFFFFFFFFFFFFFFFFFFF
a = -3
b = 0x5AC635D8AA3A93E7B3EBBD55769886BC651D06B0CC53B0F63BCE3C3E27D2604B
n = 0xFFFFFFFF00000000FFFFFFFFFFFFFFFFBCE6FAADA7179E84F3B9CAC2FC632551
Fp = GF(p)
E = EllipticCurve(Fp, [a, b])

q_bing_x = 0x3B827FF5E8EA151E6E51F8D0ABF08D90F571914A595891F9998A5BD49DFA3531
q_bing_y = 0xAB61705C502CA0F7AA127DEC096B2BBDC9BD3B4281808B3740C320810888592A

q_bing = E(q_bing_x, q_bing_y)
d = pow(2,-1,n) 
g = q_bing*d 
g_x, g_y = g.xy()


# 1. Điền thông tin
HOST = 'socket.cryptohack.org'  
PORT = 13382
# 2. Chuẩn bị payload
payload = {
    "private_key": 2,
    "host": "any",
    "curve": "secp256r1",
    "generator": [int(g_x), int(g_y)]
}

# 3. Gửi và nhận kết quả
try:
    with socket.socket(socket.AF_INET, socket.SOCK_STREAM) as s:
        s.connect((HOST, PORT))
        s.recv(1024)  # Đọc và bỏ qua tin nhắn chào mừng
        
        # Gửi payload đã được mã hóa sang JSON và bytes
        s.sendall(json.dumps(payload).encode() + b'\n')
        
        # Đọc và in phản hồi
        response = s.recv(4096).decode()
        print(response.strip())

except Exception as e:
    print(f"Lỗi: {e}")

Flag: crypto{Curveballing_Microsoft_CVE-2020-0601}
## Montgomery's Ladder

Khi sử dụng ECC bình thường có thể ta sẽ gặp khả năng gặp phải những kiểu tấn công tinh vi như `timing` hay `LadderLeak` khiến cho hệ thống ECC HOÀN TOÀN SỤP ĐỔ.

Thay vào đó, ta có thể triển khai ECC trên 1 đường cong khác đó là: 

Các thuật toán:
- 
- 

Đề bài này đơn giản bắt ta tìm k.Q trong đường cong Montgomery. Ta biết được tọa độ x của Q, ta chỉ cần tìm y rồi sau đó nhân Q với k theo công thức là xong:

# Bước 1: Thiết lập các hằng số và trường hữu hạn
# --------------------------------------------------
# p = 2^255 - 19
p = 2^255 - 19
F = GF(p)  # Tạo trường hữu hạn GF(p)

# Các hằng số của đường cong y^2 = x^3 + Ax^2 + x
A = 486662
B = 1 # Không cần thiết trong định nghĩa này nhưng có trong công thức tổng quát

# Bước 2: Định nghĩa đường cong Elliptic
# --------------------------------------------------
# Sage sử dụng dạng Weierstrass tổng quát: y^2 + a1*x*y + a3*y = x^3 + a2*x^2 + a4*x + a6
# So sánh với y^2 = x^3 + Ax^2 + x, ta có:
# a1=0, a3=0, a2=A, a4=1, a6=0
E = EllipticCurve(F, [0, A, 0, 1, 0])
print("Đã định nghĩa đường cong:", E)

# Bước 3: Định nghĩa điểm gốc P và khóa k
# --------------------------------------------------
x_p = F(9) # Tọa độ x của điểm P

# Tìm y_p bằng cách giải phương trình đường cong
# y_p^2 = x_p^3 + A*x_p^2 + x_p
y_p_squared = x_p^3 + A*x_p^2 + x_p
y_p = y_p_squared.sqrt() # Sage sẽ tự tìm căn bậc hai modulo p

# Tạo đối tượng điểm P
P = E(x_p, y_p)
print("Điểm gốc P:", P.xy())

# Khóa bí mật (vô hướng)
k = 0x1337c0decafe
print("Khóa k (thập phân):", k)

# Bước 4: Triển khai thuật toán Thang Montgomery
# --------------------------------------------------
# Chuyển k sang dạng nhị phân
k_bin = bin(k)[2:] # Lấy chuỗi nhị phân, bỏ đi tiền tố '0b'

# Khởi tạo R0, R1 theo thuật toán
R0 = P
R1 = 2*P  # Sage cho phép nhân đôi điểm dễ dàng như thế này!
print("Khởi tạo R0, R1 xong.")

# Lặp qua các bit của k, bắt đầu từ bit thứ hai (từ trái qua)
for i in range(1, len(k_bin)):
    bit = int(k_bin[i])
    
    if bit == 0:
        # R0' = 2*R0
        # R1' = R0 + R1
        R1 = R0 + R1 # Sage cho phép cộng điểm bằng toán tử '+'
        R0 = 2*R0
    else: # bit == 1
        # R0' = R0 + R1
        # R1' = 2*R1
        R0 = R0 + R1
        R1 = 2*R1

# Bước 5: Lấy kết quả
# --------------------------------------------------
# Sau vòng lặp, kết quả Q = [k]P chính là R0
Q = R0
x_q = Q.xy()[0] # Lấy tọa độ x của điểm Q

print("\n--- KẾT QUẢ ---")
print("Điểm Q = [k]P là:", Q.xy())
print("Tọa độ x của Q (dạng số của trường hữu hạn):", x_q)
print("Tọa độ x của Q (dạng số nguyên thập phân):")
print(int(x_q)) # In ra số nguyên để nộp đáp án

Flag: crypto{49231350462786016064336756977412654793383964726771892982507420921563002378152}