# NHÓM VÀ CÁC KIẾN THỨC LIÊN QUAN

### Phép toán hai ngôi
Một phép toán hai ngôi trên X là một ánh xạ ký hiệu là ``*``.

``x*y`` không phải là ``x.y`` mà có thể là bất kỳ phép toán mà ta định nghĩa ví dụ như là ``x + 2y`` hoặc là ``x+y``.

Ví dụ: Phép trừ trong tập N không là một phép toán hai ngôi vì ``1 - 2 ∉ N``, nhưng mà là một phép toán hai ngôi trên tập Z.

### NHÓM
Nhóm là một trong những thành phần quan trọng trong cấu trúc đại số.

Cho G là 1 tập khác rỗng cùng với phép toán hai ngôi (*). Khi đó G được gọi là 1 nhóm nếu thỏa mãn các điều kiện sau:
- Phép toán hai ngôi (*) có tính chất kết hợp:
\begin{equation}
\forall x, y, z \in G, (x * y) * z = x * (y * z)
\end{equation}

- Phép toán hai ngôi (*) có phần tử trung lập e ∈ G:
\begin{equation}
\forall x \in G, x * e = e * x = x
\end{equation}

- Mọi x ∈ G có phần tử đối xứng (nghịch đảo) ∈ G:
\begin{equation}
\forall x \in G, x * x^{-1} = e
\end{equation}

Lưu ý:
- Nếu (*) chỉ thỏa mãn tính chất đầu tiên, thì G được gọi là nửa nhóm.
- Nếu (*) chỉ thỏa mãn tính chất thứ nhất và thứ hai, thì G được gọi là vị nhóm.
- Nếu (*) có thêm tính giao hoán thì G được gọi là nhóm Abel hay còn gọi là nhóm giao hoán.
\begin{equation}
\forall x, y \in G, x * y = y * x
\end{equation}

Ví dụ:
- Ví dụ 1:
- ($Z^{+}$) là tập $Z$ với phép toán hai ngôi là phép cộng là nhóm Abel. Tương tự với ($Q^{+}$), ($R^{+}$). Lấy $a, b, c \in \mathbb{Z}$ thì:
- (a + b) + c = a + (b + c)
- a + 0 = 0 + a = a (Phần tử trung lập là 0)
- a + (-a) = (-a) + a = 0 (Phần tử nghịch đảo là -a)
- Thêm tính chất giao hoán a + b = b + a
--> ($Z^{+}$) là nhóm Abel.

- Ví dụ 2:
- Gọi ($Z{n}$) là lớp thặng dư mod n $\{0, 1, 2, \dotsb, n-1\}$. ($Z^{+}_{n}$) cũng là một lớp giao hoán.

- Ví dụ 3:
- Gọi $a, b, c \in \mathbb{Q^{*}}$ (tập hợp không có số 0), ta thấy ($Q^{*}_{.}$) là nhóm nhân giao hoán bởi vì:
- (a . b) . c = a . (b . c)
- a . 1 = 1 . a = a
- $a \cdot \frac{1}{a} = \frac{1}{a} \cdot a = 1$
- Thế nhưng $Z^{*}$ lại không phải là nhóm vì không có phần tử đối xứng (5 ∈ $Z^{*}$ nhưng $\frac{1}{5}$ ∉ $Z^{*}$)

Định nghĩa: Cho G là một nhóm, số phần tử của G được gọi là cấp của G, ký hiệu là $|G|$.
- Nếu $|G|$ = ∞ --> G có vô cùng phần tử, gọi là nhóm vô hạn.
- Nếu $|G|$ = n --> G có n phần tử, gọi là nhóm hữu hạn.

Cấp của một phần tử a ∈ G là số nguyên dương n nhỏ nhất sao cho

<math xmlns="http://www.w3.org/1998/Math/MathML">
<munder>
<mrow data-mjx-texclass="OP">
<munder>
<mrow>
<mi>a</mi>
<mo>&#x2217;</mo>
<mo>.</mo>
<mo>.</mo>
<mo>.</mo>
<mo>&#x2217;</mo>
<mi>a</mi>
</mrow>
<mo>&#x23DF;</mo>
</munder>
</mrow>
<mrow data-mjx-texclass="ORD">
<mtext>n l&#x1EA7;n</mtext>
</mrow>
</munder>
<mo>=</mo>
<mi>e</mi>
</math>

Trong đó e là phần tử đơn vị của nhóm. Nếu không tồn tại n như vậy thì a được gọi là cấp vô hạn. Mọi phần tử của nhóm hữu hạn đều có cấp hữu hạn.
Ký hiệu của cấp của một phần tử a là $|a|$ hoặc là ord(a). Lưu ý là $|a|$ không phải là $|G|$ nha.
Ví dụ:
- 10 ∈ $Z^{+}_{25}$. Giờ ta sẽ tìm $|10|$ là bao nhiêu. Ta thấy rằng (10x5) = 50 mod 25 == 0 (phần tử đơn vị) --> |10| = 5
- 3 ∈ $Z^{+}_{6}$. Tương tự thế, (2x3) = 6 mod 6 = 0 --> |3| = 2.
- Ta có nhóm nhân $Z^{*}_{5}$ = {1, 2, 3, 4}. Ta thấy rằng ord(2) = 4 vì 16 mod 5 = 1 = e.

**Lưu ý: (*) là phép toán hai ngôi chứ không phải là phép nhân.**

**Lưu ý: (*) là phép toán hai ngôi chứ không phải là phép nhân.**

**Lưu ý: (*) là phép toán hai ngôi chứ không phải là phép nhân.**

### Nhóm con
Cho G là một nhóm. Tập con $X \neq \emptyset$ của G là một nhóm con của G nếu X cùng với phép toán thu hẹp trên X làm thành một nhóm. Hiểu đơn giản là G sau khi giảm một số phần tử thì ra X.

Ví dụ: Ta biết ($Q^{+}$) là một nhóm. Bây giờ thu hẹp tập Q thành tập Z thì ($Z^{+}$) cũng là một nhóm. Khi đó, ta nói ($Z^{+}$) là một nhóm con của ($Q^{+}$). Còn ($Q^{+}$) được gọi là nhóm mẹ.

Điều kiện để tập con X là con của G là:
- X khác rỗng
- Với mọi a, b ∈ X, thì a*b ∈ X
- Nếu a ∈ X thì phần tử đối xứng $a^{-1} \in X$

### Nhóm Cyclic
Một nhóm G được gọi là nhóm Cyclic nếu trong G tồn tại phần tử g sao cho $G = \langle g \rangle$ = {g^n với mọi số nguyên n}.
Ví dụ:
- $\langle a \rangle = \{ \ldots, a^{-2}, a^{-1}, 1, a, a^2, \ldots \}$
- Với nhóm nhân, ta lấy a ∈ G, ta có $\langle a \rangle = \{ \ldots, a^{-2}, a^{-1}, 1, a, a^2, \ldots \}$. Nếu $G = \langle a \rangle$ thì G là Cyclic group.
- Với nhóm cộng, ta lấy a ∈ G, ta có $\langle a \rangle = \{ \ldots, -3a, -2a, -a, 0, a, 2a, 3a, \ldots \}$.

Cho (G,*) là một nhóm. Tồn tại 1 phần tử g sao cho ord(g) = |G| thì G được gọi là nhóm cyclic, phần tử g đó được gọi là phần tử sinh hoặc là phần tử nguyên thủy.

Ví dụ: Xét nhóm nhân $Z_7^* = \{1, 2, 3, 4, 5, 6\}$ và phần tử sinh g = 3, ta nhận thấy rằng ord(3) = 6 = |$Z_7^*$| và nhóm nhân sinh bởi 3 là $\{3, 9, 27, 81, 243, 729\} = \{3, 2, 6, 4, 5, 1\} = Z_7^*$.

### Vành và Trường
A được gọi là một vành nếu trong A được trang bị hai phép toán hai ngôi (+) và nhân (.) thỏa mãn các tiên đề sau:
- (A,+) lập thành một nhóm Abel có phần tử đơn vị là 0.
- (A, .) lập thành một nửa nhóm (tức là chỉ có tính chất kết hợp).
- Phép nhân trong A phân phối được với phép cộng của A, tức là
$(x + y) \cdot z = x \cdot z + y \cdot z$
$z \cdot (x + y) = z \cdot x + z \cdot y$

Vành A được gọi là **vành có đơn vị** nếu phép nhân A có phần tử đơn vị khác 0.
Vành A được gọi là **vành giao hoán** nếu phép nhân A có tính giao hoán.
A được gọi là trường nếu A là một vành giao hoán có đơn vị khác 0 và mọi phần tử khác 0 của A đều có tính khả nghịch với phép nhân.


Ví dụ: Xét tập số nguyên $Z$ với phép công và phép nhân thông thường.
- Tính kết hợp: $(x + y) + z = x + (y + z)$ $\forall x, y, z \in \mathbb{Z}$
- Phần tử đơn vị là 0.
- Phần tử đối xứng: $x + (-x) = 0$
- Tính giao hoán: $x+y = y + x,$ $\forall x,y \in \mathbb{Z}$
$(Z,.)$ là vị nhóm giao hoán, phần tử đơn vị là 1.
- Tính kết hợp: $(x.y).z = z.(y.z)$ $\forall x,y,z \in \mathbb{Z}$
- Phần tử đơn vị là 1.
- Tính giao hoán $x.y = y.x, \forall x,y \in \mathbb{Z}.$
- Phần tử $a\neq0$, $a \in \mathbb{Z}$ không tồn tại phần tử nghịch đảo $\frac{1}{a} \in \mathbb{Z}$
- Thỏa mãn tính phân phối $x.(y+z) = x.y + x.z, z.(x+y)= z.x + z.y$
--> $(\mathbb{Z,+,.})$ là **Vành giao hoán đơn vị là 1.**

Với $(\mathbb{Q,.})$ $(\mathbb{R,.})$ $(\mathbb{C,.})$ cũng như thế nhưng mà có phần tử nghịch đảo.
--> $(\mathbb{Q,+,.})$ $(\mathbb{R,+,.})$ $(\mathbb{C,+,.})$ là **Trường**

Tập hợp lớp thặng dư $(\mathbb{Z}_n)$ modulo n với hai phép cộng thông thường:
- $(Z_n,+)$ là nhóm Abel, phần tử trung hòa là $\overline{0}$
- Tính kết hợp $(\overline{a} + \overline{b}) + \overline{c} = \overline{a} + (\overline{b} + \overline{c}) = \overline{a + b + c},\ \forall a,b,c \in \mathbb{Z}$
- Phần tử đơn vị là $\overline{0}$
- Phần tử đối xứng là $\overline{-a}$
- Tính giao hoán: $\overline{a} + \overline{b} = \overline{b} + \overline{a} = \overline{a + b} = \overline{b + a}$

### Vành đa thức hữu hạn biến
Cho A là một vành giao hoán có đơn vị là 1.
Với một ký hiệu $X$, gọi $A[X]$ là một tập các biểu thức có dạng:
$f(X)= a_0 + a_1X + a_2X^2+ ... + a_nX^n$. Trong đó $a_i \in A$ với mọi $0 \leq i \leq n, n \in \mathbb{N}$

Giả sử $f(X) = a_0 + a_1X +...+ a_nX^n$, $g(X) = b_0 + b_1X + ... + b_mX^m \in A[X]$

Trong $A[X]$ phép cộng như sau:
$f(X) + g(X) = \sum_{i=0}^{n}(a_i + b_i)X^i$

Phép nhân như sau:
$f(X) \cdot g(X) = \prod_{i=0}^{n+m}\left(\sum_{j=0}^{i}a_{(i-j)} \cdot b_j\right) \cdot X^i$

# DIFFIE HELLMAN
### Tóm tắt thuật toán
Alice và Bob sử dụng nhóm nhân số nguyên tố modulo p, trong đó p là số nguyên tố, và g là phần tử sinh. p và g sẽ là khóa công khai.
Alice sẽ chọn 1 số bí mật a. Sau đó sẽ tính giá trị A = pow(g, a, p).
Bob cũng thế, sẽ tìm 1 giá trị bí mật b và B = pow(g, b, p).

Giờ 2 người sẽ trao đổi A và B cho nhau.

Khi đó thì Alice sẽ thu được 1 giá trị ``s = pow(B, a, p)`` và Bob cũng thế, cũng sẽ thu được giá trị ``s = pow(A, b, p)`` vì $(g^a)^b \equiv (g^b)^a \pmod{p}$


### Diffie-Hellman Starter 1


from Crypto.Util.number import*

print(inverse(209,991))

**Flag: 569**

### Diffie-Hellman Starter 2


Chall bắt ta tìm phần tử sinh g nhỏ nhất trong trường Fp với p = 28151.

Ta dùng sage để giải challenge này.


**Flag: 7**

### Diffie-Hellman Starter 3


Chall này đơn giản thui, giờ tính ``pow(g,a,p)``.


**Flag: 1806857697840726523322586721820911358489420128129248078673933653533930681676181753849411715714173604352323556558783759252661061186320274214883104886050164368129191719707402291577330485499513522368289395359523901406138025022522412429238971591272160519144672389532393673832265070057319485399793101182682177465364396277424717543434017666343807276970864475830391776403957550678362368319776566025118492062196941451265638054400177248572271342548616103967411990437357924**

### Diffie-Hellman Starter 4


Như lý thuyết ở trên, ``s = pow(A,b,p)``. Giờ dùng python để tìm lại thui.

g = 2
p = 2410312426921032588552076022197566074856950548502459942654116941958108831682612228890093858261341614673227141477904012196503648957050582631942730706805009223062734745341073406696246014589361659774041027169249453200378729434170325843778659198143763193776859869524088940195577346119843545301547043747207749969763750084308926339295559968882457872412993810129130294592999947926365264059284647209730384947211681434464714438488520940127459844288859336526896320919633919
A = 70249943217595468278554541264975482909289174351516133994495821400710625291840101960595720462672604202133493023241393916394629829526272643847352371534839862030410331485087487331809285533195024369287293217083414424096866925845838641840923193480821332056735592483730921055532222505605661664236182285229504265881752580410194731633895345823963910901731715743835775619780738974844840425579683385344491015955892106904647602049559477279345982530488299847663103078045601
b = 12019233252903990344598522535774963020395770409445296724034378433497976840167805970589960962221948290951873387728102115996831454482299243226839490999713763440412177965861508773420532266484619126710566414914227560103715336696193210379850575047730388378348266180934946139100479831339835896583443691529372703954589071507717917136906770122077739814262298488662138085608736103418601750861698417340264213867753834679359191427098195887112064503104510489610448294420720
B = 518386956790041579928056815914221837599234551655144585133414727838977145777213383018096662516814302583841858901021822273505120728451788412967971809038854090670743265187138208169355155411883063541881209288967735684152473260687799664130956969450297407027926009182761627800181901721840557870828019840218548188487260441829333603432714023447029942863076979487889569452186257333512355724725941390498966546682790608125613166744820307691068563387354936732643569654017172

print(pow(A,b,p))

**Flag: 1174130740413820656533832746034841985877302086316388380165984436672307692443711310285014138545204369495478725102882673427892104539120952393788961051992901649694063179853598311473820341215879965343136351436410522850717408445802043003164658348006577408558693502220285700893404674592567626297571222027902631157072143330043118418467094237965591198440803970726604537807146703763571606861448354607502654664700390453794493176794678917352634029713320615865940720837909466**
### Diffie-Hellman Starter 5


Chall đưa cho ta 2 source code, 1 code là encrypt, 1 code là decrypt, ta thấy là mã hóa CBC, với Key sẽ là bí mật chung giữa Alice và Bob hash dạng sha256 và lấy 16 byte đầu.

Giờ code giải sẽ như sau

from Crypto.Cipher import AES
from Crypto.Util.Padding import pad, unpad
import hashlib
import os

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

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]
    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 = 2
p = 2410312426921032588552076022197566074856950548502459942654116941958108831682612228890093858261341614673227141477904012196503648957050582631942730706805009223062734745341073406696246014589361659774041027169249453200378729434170325843778659198143763193776859869524088940195577346119843545301547043747207749969763750084308926339295559968882457872412993810129130294592999947926365264059284647209730384947211681434464714438488520940127459844288859336526896320919633919
A = 112218739139542908880564359534373424013016249772931962692237907571990334483528877513809272625610512061159061737608547288558662879685086684299624481742865016924065000555267977830144740364467977206555914781236397216033805882207640219686011643468275165718132888489024688846101943642459655423609111976363316080620471928236879737944217503462265615774774318986375878440978819238346077908864116156831874695817477772477121232820827728424890845769152726027520772901423784
B = 1241972460522075344783337556660700537760331108332735677863862813666578639518899293226399921252049655031563612905395145236854443334774555982204857895716383215705498970395379526698761468932147200650513626028263449605755661189525521343142979265044068409405667549241125597387173006460145379759986272191990675988873894208956851773331039747840312455221354589910726982819203421992729738296452820365553759182547255998984882158393688119629609067647494762616719047466973581
b = 197395083814907028991785772714920885908249341925650951555219049411298436217190605190824934787336279228785809783531814507661385111220639329358048196339626065676869119737979175531770768861808581110311903548567424039264485661330995221907803300824165469977099494284722831845653985392791480264712091293580274947132480402319812110462641143884577706335859190668240694680261160210609506891842793868297672619625924001403035676872189455767944077542198064499486164431451944

iv = bytes.fromhex("737561146ff8194f45290f5766ed6aba")
encrypt_flag = bytes.fromhex("39c99bf2f0c14678d6a5416faef954b5893c316fc3c48622ba1fd6a9fe85f3dc72a29c394cf4bc8aff6a7b21cae8e12c")
print(decrypt_flag(pow(A,b,p),iv,encrypt_flag))

**Flag: crypto{sh4r1ng_s3cret5_w1th_fr13nd5}**

### Parameter Injection


Chall này sẽ cho mình là người ở giữa, mình sẽ được can thiệp vào cuộc trò chuyện giữa hai người. Mình có thể thay đổi nội dung của Alice dành cho Bob và ngược lại.

Giờ mình chỉ cần nói rằng khóa công khai của Bob là ``B = 0x01``. Từ đó ``s = pow(1, a, p) = 1``. Từ đó ta sẽ có được bí mật chung của 2 người.

from Crypto.Util.number import*
from Crypto.Cipher import AES
import hashlib
from json import loads
from pwn import*

io = remote("socket.cryptohack.org", 13371)

io.recvuntil(b'Intercepted from Alice: ')
data1 = io.recvuntil(b'\n', drop=True)
io.recvuntil(b'Send to Bob: ')
print(data1)
io.sendline(data1)
io.recvuntil(b'Send to Alice: ')
io.sendline(b'{"B": "0x01"}')
io.recvuntil(b'Intercepted from Alice: ')
output = io.recvuntil(b'\n', drop=True)
Alice = loads(output)

s = 1
sha1 = hashlib.sha1()
sha1.update(str(s).encode('ascii'))
key = sha1.digest()[:16]

iv = bytes.fromhex(Alice['iv'])
ciphertext = bytes.fromhex(Alice['encrypted_flag'])
cipher = AES.new(key,AES.MODE_CBC,iv)

print(cipher.decrypt(ciphertext))

**Flag: crypto{n1c3_0n3_m4ll0ry!!!!!!!!}**

### EXPORT_GRADE

Chall đưa ta 1 source encrypt như sau:

from Crypto.Cipher import AES
from Crypto.Util.Padding import pad, unpad
import hashlib
import os
from secret import shared_secret

FLAG = b'crypto{????????????????????????????}'


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


print(encrypt_flag(shared_secret))

Ta thấy rằng khi kết nối với server, thì ta được như sau:

Intercepted from Alice: {"supported": ["DH1536", "DH1024", "DH512", "DH256", "DH128", "DH64"]}

Thấy được rằng, Alice hỗ trợ các loại Diffie Hellman từ 64 đến 1536 bits
Giờ ta gửi cho Bob loại Diffie Hellman loại 64bits để lấy được khóa dài 64bits

Sau đó ta tiếp tục gửi cho Alice ```{"chosen": "DH64"}``` để Alice lấy 
khóa dài 64bits

![image](https://hackmd.io/_uploads/Sk4GPBr9p.png)


Từ đó ta thu được các khóa công khai, iv và encrypted_flag

Trong thư viện sage, ta thấy có 1 hàm ``discrete_log(a, b)``. Hàm ``discrete_log(a, b)`` (còn được gọi là logarithm rời rạc) là một hàm toán học được sử dụng trong lý thuyết số và mã hóa mật mã. Hàm này tính toán giá trị x sao cho ``a^x ≡ b (mod n)``, trong đó a, b, và n là các số nguyên dương đã biết và a và n phải là các số nguyên tố cùng nhau.

Ý nghĩa của hàm ``discrete_log(a, b)`` là tìm giá trị x mà khi a được nhân với chính nó lặp đi lặp lại x lần và lấy phần dư khi chia cho n, ta sẽ thu được giá trị b. Đây là một bài toán khá phức tạp khi n có giá trị lớn.

Từ đó ta sẽ thu được ``a = discrete_log(A, g)`` (Với A và g thuộc ``F(p)``)

Source solution sage như sau:

from Crypto.Cipher import AES
from Crypto.Cipher import*
from Crypto.Util.number import*
import hashlib

p = 0xde26ab651b92a129
g = Mod(0x2,p)
A = Mod(0x78ab0eb17a55cdcb,p)
B = 0x6ec23355b1a51fb4
iv = "9dcd838ee8f0d1c191933ad1371cc1d0"
encrypted_flag = "c89bbd8eaa0771cbf0d9ac623cf8582182eee62355ff46d82f93f72c95357699"
a = discrete_log(A, g)
s = pow(B,a,p)
sha1 = hashlib.sha1()
sha1.update(str(s).encode('ascii'))
key = sha1.digest()[:16]
iv = bytes.fromhex(iv)
ciphertext = bytes.fromhex(encrypted_flag)
cipher = AES.new(key,AES.MODE_CBC,iv)
print(cipher.decrypt(ciphertext))

Flag: **crypto{d0wn6r4d35_4r3_d4n63r0u5}**

### Static Client

Chall này khi ta kết nối, ta có thể trở thành Alice giả mạo để gửi g, p, A cho Bob, khi đó Bob sẽ gửi khóa B cho mình, từ đó ta có thể thu được khóa bí mật

Ta thấy rằng khi ta gửi cho Bob khóa g, thì Bob sẽ gửi lại cho ta ``B = pow(b,g,p)``, thế giờ ta thay thế giữa g và A của Alice thì ``B = pow(b,A,p) = shared_secret``  

Khi thu được shared_secret thì làm như bình thường thuii

Source solution như sau:

from pwn import*
import json
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')

io = remote('socket.cryptohack.org', 13373)

io.recvuntil(b'Intercepted from Alice: ')
Alice = json.loads(io.recvuntil(b'\n',drop=True).decode())
io.recvuntil(b'Intercepted from Bob: ')
Bob = json.loads(io.recvuntil(b'\n',drop=True).decode())
io.recvuntil(b'Intercepted from Alice: ')
encrypted = json.loads(io.recvuntil(b'\n',drop=True).decode())

p = Alice['p']
A = Alice['A']
g = Alice['g']
B = Bob['B']
iv = (encrypted['iv'])
ciphertext = (encrypted['encrypted'])

io.recvuntil(b'Bob connects to you, send him some parameters: ')
to_send = {
"p": p,
"g": A,
"A": g
}
to_send = json.dumps(to_send)
io.sendline((to_send).encode())
io.recvuntil(b'Bob says to you: ')
secret = json.loads(io.recvuntil(b'\n',drop=True).decode())
share_key = int(secret["B"],16)

print(decrypt_flag(share_key,iv,ciphertext))

Flag: **crypto{n07_3ph3m3r4l_3n0u6h}**



### Additive

Ta thấy đề miêu tả như sau:

Alice and Bob decided to do their DHKE in an additive group rather than a multiplicative group. What could go wrong?

Có nghĩa là thay vì ``A = pow(g,a,p)`` và ``B = pow(g,b,p)`` thì ``A = pow(g*a,1,p)`` và ``B = pow(g*b,1,p)``

Ta có ``A*inverse(g,p) = a*g*inverse(g,p) mod p`` <=> ``A*inverse(g,p) = a mod p`` --> Ta có được a

Khi có a rồi thì ``s = B*a mod p``

Đoạn code sẽ như sau:

from Crypto.Util.number import*
from Crypto.Cipher import AES
import hashlib
from Crypto.Util.Padding import pad, unpad

p = 0xffffffffffffffffc90fdaa22168c234c4c6628b80dc1cd129024e088a67cc74020bbea63b139b22514a08798e3404ddef9519b3cd3a431b302b0a6df25f14374fe1356d6d51c245e485b576625e7ec6f44c42e9a637ed6b0bff5cb6f406b7edee386bfb5a899fa5ae9f24117c4b1fe649286651ece45b3dc2007cb8a163bf0598da48361c55d39a69163fa8fd24cf5f83655d23dca3ad961c62f356208552bb9ed529077096966d670c354e4abc9804f1746c08ca237327ffffffffffffffff
g = 0x02
A = 0x7c552dc34d83ef5c448cd6e752fcfef27429a700014550c6844d23e65601953ff4574ce3dc7d07b6bd3357b1e9aaffc497025f4b29fac72d651b0c42f11151dd6ade6254b92337a9524ada2f20b4f221899aed5bd548467ff57a29668527679deab87263f6950bde6194ae717b888d14c7ade8a52e83e671de1d4f5b8b5e489235f3da8bd3b5bc32c328aa65d472a144aa35a3897514bcd05c76be3632b331d3f5d0dcb4e2ccd2eeacac5991c6fea3f586e0c5c7dea0e91cb85bbeee9da8211e
B = 0x1eb2a3a6264d04bc9ec838aa38bb074232382263bb8c44a4c81f342d629747fa08086c8021fbc941b9a8288887a88082841d2280050b990cb4d12bd4095b9add4f7333f9ae04b2a6d5fe169319a843500abd7bb4e6e18a0d49e04d408bd065665af2d8cc3de598e6aec20c840dff017a5230a7f22e6ea340b9ca75e408c5dc59fcae177ddac8324d5330b30bb5f5fbb0807ddba65a0eee229aeb97ccc2fab1458bbd9d3d10b5544cc24d3ae2a4fe3c8d9cb2836e597efc495ccb6f8dd508e5ed
iv = "b3b2567219b5540c3ff280f5eb28cc4f"
encrypted_flag = "be1fcf223e9aa01047caf18191f6e21639a950bf8e1056c2a481ae03f3faef21982e95ad6112b6adb0e0d56f97692218"

A = 0x7c552dc34d83ef5c448cd6e752fcfef27429a700014550c6844d23e65601953ff4574ce3dc7d07b6bd3357b1e9aaffc497025f4b29fac72d651b0c42f11151dd6ade6254b92337a9524ada2f20b4f221899aed5bd548467ff57a29668527679deab87263f6950bde6194ae717b888d14c7ade8a52e83e671de1d4f5b8b5e489235f3da8bd3b5bc32c328aa65d472a144aa35a3897514bcd05c76be3632b331d3f5d0dcb4e2ccd2eeacac5991c6fea3f586e0c5c7dea0e91cb85bbeee9da8211e
a = (inverse(g, p) * A) % p
s = int((a * B) % p)
sha1 = hashlib.sha1()
sha1.update(str(s).encode('ascii'))
key = sha1.digest()[:16]
iv = bytes.fromhex(iv)
ciphertext = bytes.fromhex(encrypted_flag)
cipher = AES.new(key,AES.MODE_CBC,iv)
print(unpad(cipher.decrypt(ciphertext),16))

Flag: **crypto{cycl1c_6r0up_und3r_4dd1710n?}**

### Static Client 2
Chall này cũng như Static Client trước thui, thế nhưng không còn dùng cách cũ như ban nãy được nữa, thế nên mình phải dùng cách mới huhuhuuhu :crying_cat_face: 

Sau một thời gian tìm hiểu thì bài này thuộc dạng $Pohlig-hellman attack$ trong tường số nguyên tố p. Thế nhưng, số nguyên tố p này không phải là bình thường mà khi $p-1$ thì sẽ là [``smooth_number``](https://en.wikipedia.org/wiki/Smooth_number).

Vì $p-1$ là smooth prime thế nên rất dễ factor, khi đó ta có thể sử dụng nó để tấn công như trên [**video**](https://www.youtube.com/watch?v=BXFNYVmdtJU) này.

Giờ ta vẫn sẽ gửi cho Bob g và A như bình thường, nhưng mà sẽ gửi 1 số nguyên tố p với $p-1$ là smooth number.

from pwn import remote
from json import loads, dumps
from Crypto.Cipher import AES
from Crypto.Util.Padding import unpad
from Crypto.Util.number import *
import hashlib
from sympy.ntheory.residue_ntheory import discrete_log
from gmpy2 import *

def getParams():
Alice = loads(io.recvline().split(b":", 1)[1])
Bob = loads(io.recvline().split(b":", 1)[1])
cipher = loads(io.recvline().split(b":",1)[1])
iv = cipher['iv']
encrypted = cipher['encrypted']
return Alice,Bob,iv,encrypted

def getSmoothP(p,digits):
pSmooth = 2
primes = []
while (pSmooth.bit_length() < p.bit_length()):
prime = getPrime(digits)
if prime not in primes:
pSmooth *= prime
primes.append(prime)
pSmooth += 1
return pSmooth

io = remote("socket.cryptohack.org", 13378)
Alice,Bob,iv,encrypted = getParams()

p = int(Alice["p"], 16)
pSmooth = 0
while not is_prime(pSmooth):
pSmooth = getSmoothP(p,32)

print(pSmooth)

io.sendline(dumps({"p": hex(pSmooth), "g": Alice["g"], "A": Alice["A"]}).encode())
reply = loads(io.recvline().split(b":", 2)[2])
B = int(reply["B"], 16)

b = discrete_log(pSmooth, B, 2)

print(b)

shared_secret = pow(int(Alice['A'],16), b, p)
sha1 = hashlib.sha1()
sha1.update(str(shared_secret).encode('ascii'))
key = sha1.digest()[:16]
iv = bytes.fromhex(iv)
ciphertext = bytes.fromhex(encrypted)
cipher = AES.new(key,AES.MODE_CBC,iv)
print(unpad(cipher.decrypt(ciphertext),16))

**Flag: crypto{uns4f3_pr1m3_sm4ll_oRd3r}**



### Script Kiddie

Ta được source như sau:

from Crypto.Cipher import AES
import hashlib
import secrets

def header():
print(""" _____ _ __ __ _
| __ \(_)/ _|/ _(_)
| | | |_| |_| |_ _ ___
| | | | | _| _| |/ _ \
| |__| | | | | | | | __/
|_____/|_|_| |_| |_|\___|
| | | | | | |
| |__| | ___| | |_ __ ___ __ _ _ __
| __ |/ _ \ | | '_ ` _ \ / _` | '_ \
| | | | __/ | | | | | | | (_| | | | |
|_| |_|\___|_|_|_| |_| |_|\__,_|_| |_|

""")

def is_pkcs7_padded(message):
padding = message[-message[-1]:]
return all(padding[i] == len(padding) for i in range(0, len(padding)))

def pkcs7_unpad(message, block_size=16):
if len(message) == 0:
raise Exception("The input data must contain at least one byte")
if not is_pkcs7_padded(message):
return message
padding_len = message[-1]
return message[:-padding_len]

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)
return pkcs7_unpad(plaintext).decode('ascii')

def generate_public_int(g, a, p):
return g ^ a % p

def generate_shared_secret(A, b, p):
return A ^ b % p

def goodbye():
print('Goodbye!')

def main():
header()
print('[-] Collecting data from Alice')
p = int(input('> p: '))
q = (p - 1) // 2
g = int(input('> g: '))
A = int(input('> A: '))
print('[+] All data collected from Alice')

print('[+] Generating public integer for alice')
b = secrets.randbelow(q)
B = generate_public_int(g, b, p)
print(f'[+] Please send the public integer to Alice: {B}')
print('')
input('[+] Press any key to continue')
print('')

print('[+] Generating shared secret')
shared_secret = generate_shared_secret(A, b, p)

query = input('Would you like to decrypt a message? (y/n)\n')
if query == 'y':
iv = input('[-] Please enter iv (hex string)\n')
ciphertext = input('[-] Please enter ciphertext (hex string)\n')
flag = decrypt_flag(shared_secret, iv, ciphertext)
print(f'[+] Flag recovered: {flag}')
goodbye()
else:
goodbye()

if __name__ == '__main__':
main()

Nhìn kỹ code thì ta thấy rằng có 1 lỗ hỏng ở đây là:

def generate_public_int(g, a, p):
return g ^ a % p

def generate_shared_secret(A, b, p):
return A ^ b % p

Thay vì là hàm mũ thì đây là xor, thì có nghĩa là ``B = (g xor b) mod p`` và ``s = (A xor b) mod p``

Suy ra: ``s = B xor g xor A``

Thu được s rùi thì decrypt thuiii

Source solution như sau:

import hashlib
from Crypto.Cipher import AES

def pkcs7_unpad(message, block_size=16):
if len(message) == 0:
raise Exception("The input data must contain at least one byte")
if not is_pkcs7_padded(message):
return message
padding_len = message[-1]
return message[:-padding_len]
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)
return pkcs7_unpad(plaintext).decode('ascii')

p = 2410312426921032588552076022197566074856950548502459942654116941958108831682612228890093858261341614673227141477904012196503648957050582631942730706805009223062734745341073406696246014589361659774041027169249453200378729434170325843778659198143763193776859869524088940195577346119843545301547043747207749969763750084308926339295559968882457872412993810129130294592999947926365264059284647209730384947211681434464714438488520940127459844288859336526896320919633919
g = 2
A = 539556019868756019035615487062583764545019803793635712947528463889304486869497162061335997527971977050049337464152478479265992127749780103259420400564906895897077512359628760656227084039215210033374611483959802841868892445902197049235745933150328311259162433075155095844532813412268773066318780724878693701177217733659861396010057464019948199892231790191103752209797118863201066964703008895947360077614198735382678809731252084194135812256359294228383696551949882
B = 652888676809466256406904653886313023288609075262748718135045355786028783611182379919130347165201199876762400523413029908630805888567578414109983228590188758171259420566830374793540891937904402387134765200478072915215871011267065310188328883039327167068295517693269989835771255162641401501080811953709743259493453369152994501213224841052509818015422338794357540968552645357127943400146625902468838113443484208599332251406190345653880206706388377388164982846343351
iv = 'c044059ae57b61821a9090fbdefc63c5'
encrypted_flag = 'f60522a95bde87a9ff00dc2c3d99177019f625f3364188c1058183004506bf96541cf241dad1c0e92535564e537322d7'

s = B^A^g
print(decrypt_flag(s,iv,encrypted_flag))

Flag: **crypto{b3_c4r3ful_w1th_y0ur_n0tati0n}**


### The Matrix

``source.sage``

import random

P = 2
N = 50
E = 31337

FLAG = b'crypto{??????????????????????????}'

def bytes_to_binary(s):
bin_str = ''.join(format(b, '08b') for b in s)
bits = [int(c) for c in bin_str]
return bits

def generate_mat():
while True:
msg = bytes_to_binary(FLAG)
msg += [random.randint(0, 1) for _ in range(N*N - len(msg))]

rows = [msg[i::N] for i in range(N)]
mat = Matrix(GF(2), rows)

if mat.determinant() != 0 and mat.multiplicative_order() > 10^12:
return mat

def load_matrix(fname):
data = open(fname, 'r').read().strip()
rows = [list(map(int, row)) for row in data.splitlines()]
return Matrix(GF(P), rows)

def save_matrix(M, fname):
open(fname, 'w').write('\n'.join(''.join(str(x) for x in row) for row in M))

mat = generate_mat()

ciphertext = mat^E
save_matrix(ciphertext, 'flag.enc')

``flag.enc``

00000001111101100001101010010001001011000110001001
10111010010100110001011011111110011000001001000001
01011101000110110101010100100100111110110110011111
11101100011011010001111011011000100010110001001010
11111111101001010101001011111101010010011010101001
10010011101000000010000110100101111011110011101110
00011100010011010110000000001011000111010101001011
01001111000110100111110011000101011110010111111110
01111001110011000100000110010101011111010000000011
11001101010111111011110110101010001101001001111101
01100111000100010101000001011011001101001110101000
00010001001011101111100010101101011000101100010111
01101100101101011101101000110001011111111010000100
00001110111111000111111100011110000101100100000011
10001001111111011000111011111010110111111111000110
01111101100011110110111000011110000100111001110100
11111100110101111001111000110100011010111011110001
00100011011100101010111011111100000010000101111111
01111001110100011111011100100011011010010011111000
01011011101011111111101011011011000111110011111010
00010100110111110011111100111101100000001101110111
10011011011101110101100110110000011101000010101011
01111000001111011011111000100010010010010111101001
00100000010001110000001101111100011111110011011000
10010101101011011111101111101000111010010011111001
10011011000111000001010111011000000000100111100011
11001001010001111111000011011011101001101010001000
00100100000101110010001001011001111011001110100001
00000101000101100111010111101010001101111110011001
00101000011010100110100111111110000101011001011110
11011001001111111010000001100111011101101100110110
00111000011011011111111011110001001101001101101100
11110010101001100110000110110000100000101010101011
00101001000011001110110111100010010011100101001000
11000100010010111110110010100110110110101000110110
01101011000111001111011110000110001011111000011100
11010011001111111110100101100011000000000011110001
10000011000101100011000110111111011010110111101000
11000011000100010001001011010011010000001101100011
11011001111001010100010101001100001010101100010010
10110101010111111010110001111111100100110001001100
11101001100110001001001100000011100101001010011010
10000011100110001101010110010010100001010011011101
10001110111111100110011000010000011011011111011001
00011100011111110101011100111000110010100011000010
00111111010010111100100101100001001011110101111100
10000100101101000011011010100100011111100101101111
00011101110001001010111001111011111110110011011001
11111100110101111100110001011001000001111100110011
00110010110110011001001111110110000011001111010110

Trong RSA, ta biết được rằng $C = M^e \mod N$ và để decrypt lại thì ta có $M = C^d \mod N$ với $d = e^{-1} \mod\ φ(N)$

Và $φ(N)$ là trong trường số nguyên, trong challenge này thì lại trong $GF(50, GF(2))$, giờ ta cần tìm lại khóa d trong trường ma trận này.

lên wiki thì ta có được công thức sau đây

![image](https://hackmd.io/_uploads/SJN1HZiV0.png)

Từ đó ta có thể tìm lại được khóa d và flag.

import random
from Crypto.Util.number import *

P = 2
N = 50
E = 31337

FLAG = b'crypto{??????????????????????????}'

def load_matrix(fname):
data = open(fname, 'r').read().strip()
rows = [list(map(int, row)) for row in data.splitlines()]
return Matrix(GF(P), rows)

def bin_to_bytes(s):
all_bytes = [s[i:i+8] for i in range(0, len(s), 8)]
return b''.join(long_to_bytes(int(byte, 2)) for byte in all_bytes)

def find_order():
order = 1
for k in range(N):
order *= (P**N - P**k)

return order

ciphertext = load_matrix('flag.enc')

phi = ZZ(find_order())

d = inverse_mod(E, phi) # either phi or ciphertext.multiplicative_order()

M = ciphertext^d

bin_flag = ""
for i in range(N):
for j in range(N):
bin_flag += str(M[j,i])
print(bin_to_bytes(bin_flag[:len(FLAG)*8]))

**Flag: crypto{there_is_no_spoon_66eff188}**