# Các công cụ hỗ trợ
## SageMath
### Zmod() (Integer Modulo Ring)
Hàm Zmod(n) dùng để tạo ra một vành số dư $\mathbb{Z} / n\mathbb{Z}$.
* Nó đại diện cho tập hợp các số dư từ $0$ đến $n-1$.
* Mọi phép toán trên vành này đều được thực hiện theo modulo $n$.
* Các tham số:
* order (hoặc n): Đây là giá trị modulo. Ví dụ Zmod(10) sẽ tạo ra tập $\{0, 1, 2, ..., 9\}$.
* is_field (boolean, mặc định là False): Nếu đặt is_field=True, $n$ là số nguyên tố
Ví dụ: Tạo vành $Z_{11}$
```sage=
R = Zmod(11)
a = R(7)
b = R(5)
print(a + b) # Kết quả: 1 (vì 12 mod 11 = 1)
print(a * b) # Kết quả: 2 (vì 35 mod 11 = 2)
print(a / b) # Kết quả: 8 (vì 7 / 5 = 7 * 5^-1 = 63 mod 11 = 8)
```
### GF() (Galois Field)
Hàm GF(order, ...) trả về một trường hữu hạn có kích thước là `order`
* `order` là lũy thừa của số nguyên tố $(p^n)$
* Có thể dùng GF() hoặc FiniteField() thay thế cho nhau.
* Các tham số:
* order (bắt buộc): Kích thước của trường ($q = p^n$).
* name (tùy chọn): Tên của biến đại diện cho phần tử sinh (generator) của trường.
* modulus (tùy chọn): Đa thức bất khả quy dùng để định nghĩa trường. Nếu muốn phần tử sinh là phần tử nguyên thủy (primitive element), thì dùng modulus="primitive".
* impl (tùy chọn): Chọn thư viện tính toán
* proof (True, False): mặc định là True, nếu là True, Sage sẽ dùng provable
primality test (Sử dụng các thuật toán toán như ECPP hoặc Pocklington để chứng minh rằng số đó là số nguyên tố), False thì sẽ dùng pseudoprimality test (Sử dụng các thuật toán xác suất như Miller-Rabin, kiểm tra xem số đó có thỏa mãn một số tính chất của số nguyên tố hay không)
Ví dụ:
```python=
# Tạo trường hữu hạn có 8 phần tử, biến là 'a'
k.<a> = GF(8) # 8=2^3
print(k) # Kết quả: Finite Field in a of size 2^3
```
hoặc
```python=
# Tự định nghĩa đa thức tạo trường
K.<a> = GF(5**5, name='a', modulus=x^5 - x + 1)
x = a^2 + 1
y = a + 1
print(x+y) #Kết quả: a^2 + a + 2
```
### QQ() (Rational Field)
QQ() là trường số hữu tỉ, là tập hợp các số có thể được viết dưới dạng phân số
* QQ() Có thể được dùng để khởi tạo phân số theo nhiều cách khác nhau
Ví dụ:
```python=
# Từ chuỗi văn bản
sage: QQ('-930482/9320842317')
-930482/9320842317
# Từ một tuple (tử số, mẫu số)
sage: QQ((-930482, 9320842317))
-930482/9320842317
# Từ số nguyên cực lớn (Số nguyên lớn không giới hạn trong Sage được gọi là ZZ)
sage: a = 901824309821093821093812093810928309183091832091
sage: QQ(a)
901824309821093821093812093810928309183091832091
```
* QQ() có thể chuyển một số từ dạng thập phân sang phân số
Ví dụ:
```python=
QQ(23.2) # Kết quả: 116/5
```
### ZZ() (Integer Ring)
ZZ() là vành số nguyên, bao gồm tất cả số nguyên âm, số nguyên dương và số 0
* Đặc số của vành số nguyên là 0
* SageMath hỗ trợ tạo số nguyên từ một danh sách các chữ số theo quy tắc: Phần tử đầu tiên là hàng đơn vị, phần tử tiếp theo là hàng cao hơn.
* Công thức tổng quát: Z([d0, d1, d2], base=b) $= d_0 \cdot b^0 + d_1 \cdot b^1 + d_2 \cdot b^2$
* Ví dụ: Z([4, 1, 7], base=10) $\rightarrow 4 \cdot 1 + 1 \cdot 10 + 7 \cdot 100 = 714$
```python=
sage: Z([4, 1, 7], base=10)
714
```
### RealField() (hay RR())
RealField() còn được gọi là trường số thực, dùng để tính toán với các số thập phân. RealField lưu giá trị xấp xỉ.
Các tham số:
* prec(interger): Mặc định là 53, dùng để lưu phần định trị(mantisa) của một số dấu phẩy động
* sci_not(True, False): Mặc định là False. Nếu là False thì sẽ hiển thị số như bình thường(VD: 123.45) và chỉ hiển thị dạng `e` với số quá lớn hoặc quá nhỏ. Nếu là True thì sẽ hiển thị tất cả mọi số ở dạng `e` (1.23000000000000e2 với số 123)
* rnd: Chế độ làm tròn
Ví dụ:
```sage=
R = RR(100)
print(R(pi)) # Kết quả: 3.1415926535897932384626433833
```
### Phương thức để xem order của một vành/trường hữu hạn
Có hai phương thức chính thường dùng nhất là `.order()` và `.cardinality()`. Cả hai phương thức đều trả về cùng một kết quả
* Với GF()
```sage=
F.<a> = GF(3^2)
print(F.order()) # Kết quả: 9
print(F.cardinality()) # Kết quả: 9
```
* Với Vành số dư Zmod()
```sage=
R = Zmod(10)
print(R.order()) # Kết quả: 10
```
### Phương thức để tìm phần tử sinh của một vành/trường hữu hạn.
* Với GF()
* `.primitive_element()`: Phương thức này trả về phần tử $a$ sao cho tất cả các phần tử khác $0$ thuộc trường đều được biểu diễn dưới dạng $a^k$
* `.multiplicative_generator()`: tương tự `.primitive_element()`
* Với Zmod():
* `.multiplicative_generator()`: Trả về phần tử sinh của nhóm nhân nếu nhóm đó là xyclic.
* `.unit_gens()`: Trả về một tập hợp các phần tử sinh ra nhóm các đơn vị (units) của vành. Phương thức này hoạt động ngay cả khi nhóm nhân không xiclic.
Ví dụ:
```sage
sage: GF(65537).primitive_element()
3
sage: GF(65537).multiplicative_generator()
3
sage: Zmod(65537).multiplicative_generator()
3
sage: Zmod(65536).multiplicative_generator()
# Sage báo lỗi vì 65536 không nguyên tố
sage: Zmod(65536).unit_gens()
(65535, 5)
```
### Cách kiểm tra Quadratic Residue của một giá trị.
* Sử dụng ký hiệu Legendre (legendre_symbol(a, p)) khi $p$ là số nguyên tố lẻ
* $(\frac{a}{p}) = 1$: $a$ là $Q_p$
* $(\frac{a}{p}) = -1$: $a$ là $\overline{Q}_p$
* $(\frac{a}{p}) = 0$: $a$ là $Q_p$
Ví dụ:
```sage=
sage: p = 13
....: a = 3
....: print(legendre_symbol(a, p)) # Kết quả: 1
```
* Sử dụng ký hiệu Jacobi (jacobi_symbol(a, n)) với $n$ là hợp số và cả số nguyên tố
* $(\frac{a}{p}) = -1$: $a$ là $\overline{Q}_p$
* $(\frac{a}{p}) = 0$: $a$ là $Q_p$
* $(\frac{a}{p}) = 1$ sẽ có 2 trường hợp.
* Ví dụ với $n=p \times q$ thì $\left(\frac{a}{n}\right) = \left(\frac{a}{p}\right) \times \left(\frac{a}{q}\right)$
* Vậy $\left(\frac{a}{n}\right)$ có thể là $1 \times 1$ hoặc $-1 \times -1$
* Nên không thể chắc chắn rằng $(\frac{a}{n}) = 1$ thì $a$ là $Q_n$
Ví dụ:
```sage=
sage: n=15
sage: a=2
sage: jacobi_symbol(a,n)
1
```
nhưng
```sage=
sage: n=5
sage: a=2
sage: print(legendre_symbol(a,n))
-1
```
nên 2 không là Quadratic Residue
### Cách dùng .continued_fraction() và .convergent()
Hàm **continued_fraction(x)** trong SageMath là một công cụ dùng để biến đổi một số thành liên phân số.
Input: x là một số hoặc một list các thương của liên phân số
Với số hữu tỉ, continued_fraction() sẽ trả về một list hữu hạn các thương số riêng
Ví dụ:
```sage=
sage: continued_fraction(12/571)
[0; 47, 1, 1, 2, 2]
```
Với số vô tỉ, continued_fraction() trả về list vô hạn các phần tử
Ví dụ:
```sage=
sage: continued_fraction(pi)
[3; 7, 15, 1, 292, 1, 1, 1, 2, 1, 3, 1, 14, 2, 1, 1, 2, 2, 2, 2, ...]
```
Hàm **.convergent(i)** là hàm dùng để tính giản phân thứ `i` của liên phân số.
Ví dụ:
```sage=
sage: c = continued_fraction(17993/90581)
sage: c
[0; 5, 29, 4, 1, 3, 2, 4, 3]
sage: c.convergent(0)
0
sage: c.convergent(1)
1/5
sage: c.convergent(2)
29/146
sage: c.convergent(3)
```
Ta có:
* Với $i=0$, giản phân thứ $0$ là $0$.
* Với $i=1$, giản phân thứ $1$ là $\frac{1}{5}$
* Với $i=2$, giản phân thứ $2$ là $\frac{1}{5 + \frac{1}{29}} = \frac{29}{146}$
* Với $i=k$, giản phân thứ $k$ là $$\frac{1}{5+\frac{1}{29+\frac{1}{4+\frac{1}{...}}}}$$
### Cách dùng .from_integer() và .to_integer().
Mỗi phần tử trong trường $GF(p^n)$ với phần tử sinh là $a$ có thể được viết dưới dạng đa thức:$$c_{n-1}a^{n-1} + c_{n-2}a^{n-2} + \dots + c_1a + c_0$$
Hàm **.from_integer(n)** phân tích n thành dạng đa thức như trên với điều kiện n phải nhỏ hơn lượng phần tử trong $GF(p^n)$ hay nhỏ hơn $p^n$.
Ví dụ:
```sage=
sage: k.<a> = GF(2^48)
sage: k.from_integer(2)
a
sage: k.from_integer(2^50)
#Sage báo lỗi vì n>self.order()
sage: k.from_integer(2^20+2^3+1)
a^20 + a^3 + 1
```
Ngược lại **(a).to_integer()** lấy các hệ số $c_i$ và coi chúng như là các chữ số trong hệ cơ số $p$ để tính ra một số nguyên duy nhất
Ví dụ:
```sage=
sage: k.<a> = GF(3^70)
sage: (a^2 + 2*a + 1).to_integer()
16
sage: k.<a> = GF(7^5)
sage: (a^2 + 2*a + 1).to_integer()
64
sage: 5.to_integer()
# Sage báo lỗi
sage: k(5).to_integer()
5
```
### Cách dùng rational_reconstruction().
Hàm rational_reconstruction(a,n) là hàm tìm $x, y$ sao cho $\frac{x}{y} \equiv a \pmod n$. Là hàm thực hiện bài toán ngược lại với phép chia modulo n.
Điều kiện: $x, y$ phải nhỏ hơn $\sqrt{\frac{n}{2}}$. Nếu $x, y$ quá lớn, Sage sẽ báo lỗi
Ví dụ:
```sage=
sage: n=100000
sage: (119*inverse_mod(53,n))%n
11323
sage: rational_reconstruction(11323,n)
119/53
sage: rational_reconstruction(400,1000)
# Sage báo lỗi
```
### Cách dùng discrete_log() và .log()
Trong SageMath, cả discrete_log() và .log() đều dùng để giải bài toán Logarithm rời rạc. Có $g$, $a$, và $x$ sao cho:$$g^x \equiv a \bmod n \space \space(A)$$
Hàm **discrete_log()** là hàm tìm $x$ trong bài toán trên.
Các tham số:
* a: Kết quả (a)
* base: Cơ số (g)
* ord: bậc của base trong DLP
* bounds: giới hạn của nghiệm tìm được
* operation: $\times , +$ hoặc các toán tử khác
* identity: phần tử đơn vị, là 1 với phép nhân, là 0 với phép +
Ví dụ:
```sage=
sage: b = Mod(2,37); a = b^20
sage: discrete_log(a,b)
20
sage: discrete_log(a,b, bounds=(10,10000))
20
```
Hàm **.log()** cũng được dùng để tìm x trong $(A)$
Ví dụ:
```sage=
sage: b=125
sage: a=b^17
sage: a.log(b)
17
```
Hoặc có thể sử dụng trong môi trường GF()
```sage=
sage: k.<a> = GF(2^8)
sage: b=a^10
sage: b.log(a)
10
sage: b=a^10+a+1
sage: b.log(a)
43
sage: b
a^6 + a^5 + a^4 + a^2 + a + 1
sage: b-a^43
0
```
### Cách dùng .nth_root()
`self.nth_root()` là một hàm tìm căn bậc n của `self` rất mạnh trong sagemath.
Các tham số:
* n: số nguyên $(n\geq1)$
* all(boolean): mặc định là False. Khi đặt `all=True`, sage sẽ trả về toàn bộ căn bậc n thỏa mãn thay vì chỉ 1 kết quả
* algorithm: mặc định là None, đây là tham số sử dụng trong trường hợp modulo nguyên tố.
Ví dụ:
```sage=
sage: k=GF(31)
sage: k(22).nth_root(7)
13
sage: k(25).nth_root(5)
5
sage: k(25).nth_root(5,all=True)
[5, 18, 9, 20, 10]
```
Hoặc tính trong môi trường Zmod()
```sage=
sage: k=Zmod(3^7)
sage: k(25).nth_root(5,all=True)
[112]
```
### Cách factor một số nguyên, truyền tham số limit thì có tác dụng gì?
Trong sagemath, có nhiều cách để factor một số nguyên.
* Hàm `factor(n)` phân tích n ra thừa số nguyên tố
* Truyền limit trong hàm này có nghĩa là giới hàm số thừa số nguyên tố được phân tích
Ví dụ:
```sage=
sage: factor(114411)
3 * 11 * 3467
sage: factor(-20)
-1 * 2^2 * 5
sage: factor(114411, limit=2)
3 * 38137
```
Có thể biểu diễn factor dưới dạng danh sách
```sage=
sage: f=factor(-20)
sage: list(f)
[(2, 2), (5, 1)]
```
Dùng ecm.factor() sage sẽ trả về kết quả dạng list trong python
```sage=
sage: ecm.factor(114411)
[3, 11, 3467]
```
### Hàm crt của sagemath có gì đặc biệt so với Textbook crt?
Mình đã được học thuật toán CRT bằng công thức
$$x = \sum_{i=1}^{n} a_i M_i y_i \pmod M$$
Với các $m_i,m_j$ là những số nguyên tố cùng nhau hay $gcd(m_i, m_j)=1$. Nhưng `crt()` trong sagemath không yêu cầu như thế, crt() trong sagemath chỉ cần có nghiệm thì sẽ tính được kết quả.
Ví dụ:
```sage=
sage: n = [11,21,26]
....: a = [10,19,20]
sage: crt(a,n)
670
sage: CRT_list(a,n)
670
```
Hoặc có thể tính crt chỉ với 2 phương trình
```sage=
sage: crt(2,1,3,5)
11
sage: crt(13,20,100,301)
28013
sage: crt([13,20],[100,301])
28013
```
## Pwntools
### Học cách sử dụng thư viện Pwntools để kết nối tới Server
* `io = remote(HOST, PORT)` dùng để kết nối server với `HOST` là địa chỉ IP máy chủ và `PORT` là cổng cần truy cập
Ví dụ:
```python=
from pwn import *
io = remote("socket.cryptohack.org", 13377)
```
Kết quả:
```
[x] Opening connection to socket.cryptohack.org on port 13377
[x] Opening connection to socket.cryptohack.org on port 13377: Trying 134.122.111.232
[+] Opening connection to socket.cryptohack.org on port 13377: Done
[*] Closed connection to socket.cryptohack.org port 13377
```
Các lệnh nhận từ server
- `p.recvline()`: Nhận một dòng, giá trị trả về bao gồm cả ký tự xuống dòng
- `p.recvuntil()`: Nhận dữ liệu cho đến khi gặp một chuỗi nhất định, mặc định là giữ luôn chỗi text ấy, có thể thêm `drop=True` để bỏ.
- `p.recv(num_bytes)`: Nhận một số lượng byte cụ thể
Các lệnh gửi dữ liệu đến server
- `p.sendlineafter(promt, data)`: Gửi dòng dữ liệu sau một prompt cụ thể
- `p.sendafter(promt, data)`: Gửi dữ liệu sau một prompt cụ thể (không thêm ký tự xuống dòng)
- `p.sendline(data)`: Gửi dòng dữ liệu (có ký tự xuống dòng)
- `p.send(data)`: Gửi dữ liệu không thêm ký tự xuống dòng
`io = process(["python3", "<name_file>.py"])` dùng để kết nối trên local, là file cụ thể trên máy
### Áp dụng các lệnh pwntool giải challange
#### Chall 1
File source code như sau:
```python=
from Crypto.Util.number import bytes_to_long, long_to_bytes, getPrime
import sys, random
sys.set_int_max_str_digits(65537)
"""
CẢNH BÁO: Hãy bắt đầu từ đây!
Chuyện là anh Quanda đã cất giữ một số tiền lớn trong két sắt, trong két sắt, trong két sắt, cái gì quan trọng nhắc lại 3 lần.
Nhưng chẳng may, ảnh đã quên mật khẩu két sắt là gì rồi, chìa khóa thì bị hỏng. Anh ấy đã thử liên hệ với Kỳ Anh Thợ Khóa nhờ mở hộ.
Một lúc sau, Kỳ Anh Thợ Khóa lại nói rằng: "Kèo này hơi khê. Hãy đi tìm một bạn chơi CTF Crypto để khôi phục lại chìa khóa đã bị hỏng!".
két sắt của anh Quanda có cấu trúc như sau: KETSAT{???????????}. Với '???????????' bằng chính xác số tiền trong két sắt đang có.
Đây là cách mà hệ thống khóa của két sắt vận hành:
n = ...
e = 65537
m = bytes_to_long(b'KETSAT{???????????}')
ct = pow(m, e, n)
Hãy mở két an toàn và đưa số tiền này cho anh Quanda để xem xét nhé! (～￣▽￣)～
"""
n = 51054783597903480370518037084862755962893361152837124224471196590900076010209422848871101747394816882205821272912478563189177707321960718546463070665588575784720225550542837211135285473235059594676108743604057152970603764890692156345079366557303229525311273062217297903768046472939864346852138270493897446371
ct = 44449089060212966082311570514329998372754125354315165898608095718924104722504868307010635333977789437483321200892479777123682417029481931530922677365354863283877764613680158127573831895280544206073621760507514977853611001386433124667546055170871923384047365836397452345594238884161353975635123699188467659386
print("Giua~ CTF va` 2 ty?, em chon ca'i na`o:")
option = input('> ')
if option == 'CTF':
"""Cảnh này thật quen thuộc... Ta đã từng thấy nó ở đâu rồi (")>"""
try:
a, b, c, d = [int(input(f"{x} = ")) for x in "abcd"]
assert a > 0
assert 487 * a == c
assert 1529 * a == 1447 * b
assert d ** 2 == a + b
if a.bit_length() < 23:
u = 5797160311492700660410984002908468368420318968124328414575094385135089938987093573586006596396203452808458680292350711713618849469477258878282003909391
p = d * 10 ** 151 + u
assert n % p == 0
print(f"{p = }")
else:
print("(👉ﾟヮﾟ)👉 Nhu muo'i bo? bie?n")
except:
print("Nhu muo'i bo? bie?n")
elif option == '2 ty':
print("HDPE thi` ngon luo^n...")
else:
"_"
```
Đặt các giá trị
* `k1 = 487`
* `k2 = 1529`
* `k3 = 1447`
Theo đề, ta có
* $c = k1 \times a$
* $k2 \times a = k3 \times b$ hay $\frac{k2}{k3} = \frac{b}{a}$ (2)
* $d^2 = a + b$ (3)
Từ (2), ta có $$a=k \times k3$$ $$b = k \times k2$$
Từ (3) có thể thấy, $a+b \space$ phải là một số chính phương, vậy nên, k sẽ được tính bằng cách nhân cho các thừa số nguyên tố có mũ lẻ của tổng a+b.
Có k, ta suy ngược ra a,b,c và tính d.
Code như sau:
```python=
from sympy.ntheory import factorint
from Crypto.Util.number import bytes_to_long, long_to_bytes, getPrime, inverse, isPrime
from gmpy2 import iroot
n = 51054783597903480370518037084862755962893361152837124224471196590900076010209422848871101747394816882205821272912478563189177707321960718546463070665588575784720225550542837211135285473235059594676108743604057152970603764890692156345079366557303229525311273062217297903768046472939864346852138270493897446371
ct = 44449089060212966082311570514329998372754125354315165898608095718924104722504868307010635333977789437483321200892479777123682417029481931530922677365354863283877764613680158127573831895280544206073621760507514977853611001386433124667546055170871923384047365836397452345594238884161353975635123699188467659386
e = 65537
k1 = 487
k2 = 1529
k3 = 1447
k=1
s = k3+k2
for p, cnt in factorint(s).items():
if cnt%2!=0: k*=p
a = k*k3
b = k*k2
can, ex = iroot(a+b, 2)
c = 487 * a
d = can
print(a)
print(b)
print(c)
print(d)
```
Sau đó tiến hành gửi a,b,c,d đến local
```python=
from pwn import *
from Crypto.Util.number import bytes_to_long, long_to_bytes, getPrime, inverse, isPrime
io = process(["python3", "chall1.py"])
io.sendline(b'CTF')
io.sendlineafter(b'a = ', b'269142')
io.sendlineafter(b'b = ', b'284394')
io.sendlineafter(b'c = ', b'131072154')
io.sendlineafter(b'd = ', b'744')
io.recvuntil(b'p = ')
p = int(io.recvline())
n = 51054783597903480370518037084862755962893361152837124224471196590900076010209422848871101747394816882205821272912478563189177707321960718546463070665588575784720225550542837211135285473235059594676108743604057152970603764890692156345079366557303229525311273062217297903768046472939864346852138270493897446371
ct = 44449089060212966082311570514329998372754125354315165898608095718924104722504868307010635333977789437483321200892479777123682417029481931530922677365354863283877764613680158127573831895280544206073621760507514977853611001386433124667546055170871923384047365836397452345594238884161353975635123699188467659386
e = 65537
d = pow(e, -1, p-1)
print(long_to_bytes(pow(ct, d, p)).decode())
io.interactive()
```
Được kết quả như sau:
# Diffie-Hellman
## Đại số trừu tượng (Nhóm - Vành - Trường).
### Nhóm
* Định nghĩa: Cho $G$ là một tập khác rỗng, cùng với phép toán 2 ngôi $(*)$. Khi đó $G$ được gọi là 1 nhóm nếu:
* $(*)$ trên $G$ có tính chất kết hợp
* $(*)$ trên $G$ có phần tử đơn vị
* Mọi $x \in G$ có phần tử nghịch đảo
Nếu $(*)$ trên $G$ có thêm tính chất giao hoán, thì $G$ được gọi là **nhóm giao hoán** hay **nhóm Abel**
* **Ví dụ:** $\mathbb{Z}_n= \{ \bar{0}, \bar{1}, \bar{2}, \dots, \overline{n-1} \}$ là tập các số nguyên modulo n.
Xét phép (+) được xác định như sau:
* $\overline{a} + \overline{b} = \overline{a+b}$ là một phép toán 2 ngôi trên $\mathbb{Z}_n$
* Có tính chất kết hợp $(\overline{a} + \overline{b}) + \overline{c}
= \overline{a+b} + \overline{c} = \overline{a+(b+c)} = \overline{a} + (\overline{b} + \overline{c})$
* Có phần tử trung lập là $\overline{0}$ do $\overline{a} + \overline{0} = \overline{a}$
* Với mọi $\overline{a} \in \mathbb{Z}_n$, có phần tử đối xứng là $-\overline{a}= \overline{n-a}$
* Có tính chất giao hoán $\overline{a} + \overline{b} = \overline{b} + \overline{a}$
### Vành
**Định nghĩa:** Cho một tập R khác rỗng và phép toán 2 ngôi $(\times, +)$ được gọi là một vành nếu thỏa mãn các điều kiện sau:
* **Về Phép Cộng (+):**
* $(R, +)$ là một nhóm Abel (có tính đóng, kết hợp, giao hoán, có phần tử đơn vị, phần tử nghịch đảo).
* **Về Phép Nhân ($\times$):**
* $(R, \times)$ có tính đóng, tính kết hợp.
* Nghĩa là: $a \times b \in R$ thì $(a \times b) \times c = a \times (b \times c) = a \times b \times c$.
* **Tính phân phối phép nhân với phép cộng**
* $a \times (b + c) = (a \times b) + (a \times c)$
* $(a + b) \times c = (a \times c) + (b \times c)$
* Nếu phép nhân có tính giao hoán thì tạo thành **vành giao hoán**
* Nếu phép nhân có tính nghịch đảo và không có thương 0 (tức là không có hai phần khác 0 mà tích của chúng lại bằng 0), thì nó tạo thành **miền nguyên**
Ký hiệu: $(\text{R}, +, \times)$
* **Ví dụ:**
* Tập hợp số nguyên $(\mathbb{Z}, +, \times)$ là ví dụ cơ bản nhất của một vành giao hoán có đơn vị và là miền nguyên.
* Xét trên nhóm $\mathbb{Z}_6 =\{ 0,1,2,3,4,5\}$ tồn tại 2 và 3, mà $2 \times 3 = 0 \bmod 6$, nên đây không phải là miền nguyên
* Vành ma trận 3x3 không phải là một vành giao hoán
$$A = \begin{pmatrix}
1 &2 &3 \\
0 &1 &0 \\
2 &0 &1 \\
\end{pmatrix},
B = \begin{pmatrix}
1 &0 &0 \\
0 &1 &0 \\
0 &0 &1 \\
\end{pmatrix}$$
Vì $A \times B \neq B \times A$
### Trường
* Định nghĩa: Trường là một tập hợp F với hai phép toán cộng và nhân, thỏa mãn tính chất sau:
* $(F, +)$ là một nhóm Abel có phần tử đơn vị là $0$
* $(F \setminus \{0\}, \times)$ là một nhóm Abel có phần tử đơn vị là $1$
* Có thể nói là có các phép toán cộng trừ, nhân, chia số khác 0. Phép trừ được coi là phép cộng đối với số đối của phép cộng và phép chia là nhân với số đối của phép nhân:
* $a - b = a + (-b)$
* $\frac{a}{b} = a*b^{-1}$
* **Ví dụ:** Xét $(\mathbb{Z}_5 , +, \times)$
* $(\mathbb{Z}_5, +)$ là nhóm Abel có phần tử đơn vị là $0$ (đã chứng minh ở ví dụ trước)
* $(\mathbb{Z}_5 \setminus\{0\}, \times)$
* Do 5 là số nguyên tố, nên $a\times b \not\equiv 0 \bmod 5$, suy ra $a \times b= \overline{ab} \in \mathbb{Z}_5 \setminus\{0\}$ $\rightarrow$ Tính đóng
* Có tính kết hợp
* Có phần tử đơn vị là 1
* Có phần tử nghịch đảo (1x1=1, 2x3=1 mod 5, 4x4=1 mod 5)
* Phép nhân trong $\mathbb{Z}$ có tính giao hoán
Suy ra $(\mathbb{Z}_5 \setminus\{0\}, \times)$ là nhóm Abel
Vậy $(\mathbb{Z}_5 , +, \times)$ là một trường
## Diffie-Hellman
**Diffie-Hellman** là một giao thức mật mã cho phép hai bên (Alice và Bob) trao đổi khóa một cách an toàn qua một kênh không an toàn được Whitfield Diffie và Martin Hellman giới thiệu vào năm 1976, đây là một trong những phương pháp đầu tiên cho phép chia sẻ khóa bí mật mà không cần phải trao đổi trực tiếp hoặc thông qua một kênh an toàn nào.
### Thuật toán
* Alice và Bob sẽ thỏa thuận trước một số nguyên tố lớn $p$ và chọn $g$ là phần tử sinh của $Z_p^*$. Hai số $p$ và $g$ là khóa chung và được gửi công khai.
* Alice chọn một khóa bí mật $a$, sau đó gửi $C_A$ cho Bob bằng công thức $C_{A} \equiv g^{a} \pmod p$ (khóa công khai)
* Bob cũng sẽ chọn một khóa bí mật $b$, sau đó gửi $C_B$ cho Bob bằng công thức $C_{B} \equiv g^{b} \pmod p$ (khóa công khai)
* Sau khi cả hai nhận được khóa công khai của nhau, sẽ tiến hành tạo khóa bí mật bằng cách lấy khóa công khai của đối phương mũ số bí mật của mình rồi lấy modulo p:
* $K_{A} \equiv {C_{B}}^{a} \pmod p \equiv {[g^{b} \pmod p]}^{a} \equiv g^{a\times b} \pmod p$
* $K_{B} \equiv {C_{A}}^{b} \pmod p \equiv {[g^{a} \pmod p]}^{b} \equiv g^{a\times b} \pmod p$
* Khi đó, khóa bí mật của cả hai sẽ giống nhau, từ đó có thể suy ra khóa bí mật riêng của từng người.
Ví dụ: Chọn $p=7, g=3$. Alice chọn $a=6$ và Bob chọn $b=7$
* $C_A = g^a \bmod p \equiv 1 \mod p$
* $C_B = g^b \bmod p \equiv 3 \mod p$
* $K_A = C_B^a \mod p \equiv 1 \bmod p$
* $K_B = C_A^b \mod p \equiv 1 \bmod p$
Vậy khóa chung ở ví dụ này là $2$
Diffie-Hellman được minh họa như trong hình sau
## Discrete Logarithm Problem (DLP)
Bài toán DLP là phiên bản số nguyên của bài toán logarit thông thường trong môi trường số học Modulo. Phương trình của DLP có dạng:
$$g^x \equiv h \mod p$$
* Với $g$ là phần tử sinh của một nhóm xyclic $(G)$
* $h$ là một phần tử thuộc $G$
* p là một số nguyên tố lớn
Ví dụ:
Giả sử chọn số nguyên tố $p = 17$ và cơ số $g = 3$. Ta cần tìm $y$ sao cho:
$$3^x \equiv 13 \pmod{17}$$Để giải, chúng ta có thể thử brute-force các giá trị của $x$:
* $x = 1: 3^1 = 3$
* $x = 2: 3^2 = 9$
* $x = 3: 3^3 = 27 \equiv 10 \pmod{17}$
* $x = 4: 3^4 = 81 \equiv 13 \pmod{17}$
Vậy đáp án là $y = 4$.
Nhưng khi $p$ là một số cực kỳ lớn, việc tìm lại $x$ từ phương trình ban đầu sẽ là bài toán có độ phức tạp cực cao, chưa có thuật toán nào có thể tính được trong thời gian hợp lý. Vì vậy nên DLP có tính ứng dụng cao trong mật mã học.
### Một số kỹ thuật tấn công
#### Baby-step giant-step
Thuật toán Baby-step Giant-step (BSGS) là một phương pháp thông minh giúp giải bài toán Logarithm Rời rạc (DLP) nhanh hơn nhiều so với việc thử từng số một (brute-force).
Thuật toán:
* Tính $m = \sqrt{ord(G)}$
* For(j,0,m) tính $a^j$ và lưu pair($j, a^j$) vào mảng
* Tính $a^{-m}$
* Đặt $y=h$
* For(i,0,m)
* Check xem $y$ có phải là bất kì $a^j$ trong mảng lúc nãy không
* Nếu có thì return $i \times m + j$
* Nếu không, đặt $y = y \times a^{-m}$
Ví dụ tìm $x$ với $17^x \equiv 15 \mod 97$
```python=
from math import isqrt
def baby(a, b, n):
m = isqrt(n)
map = {}
for j in range(m):
map[pow(a,j,n)]=j
y = b
ainv = pow(a,-m,n)
for i in range(m):
if y in map:
j=map[y]
return i*m+j
else: y=y*ainv%n
return None
print(baby(17,15,97))
```
Được kết quả là 31
#### Pohlig–Hellman
**Pohlig-Hellman** là thuật toán chuyên dùng để giải bài toán DLP trong một nhóm abel hữu hạn. Thay vì giải trực tiếp bài toán trên một nhóm lớn, thuật toán này chia nhỏ bài toán thành các bài toán con trên các nhóm con có bậc là lũy thừa số nguyên tố, sau đó kết hợp các kết quả lại.
* Điều kiện áp dụng:
* n = ord(g)
* n phải có cấu trúc là tích của các số nguyên tố nhỏ.
* g là phần tử sinh của $Z_p$
* Cơ chế hoạt động: Do n là tích của các thừa số nguyên tố nhỏ, ta sẽ tách bài toán modulo p về các bài toán trên modulo nhỏ hơn, sau đó gộp crt để giải (vì các thừa số nguyên tố đôi một nguyên tố cùng nhau)
* Thuật toán:
* Tách $n = q_1^{e_1}.q_2^{e_2}....q_k^{e_k}.$
* Đưa bài toán từ $g^x \equiv h \mod p$ về $x \equiv a_i \mod q_i^{e_i}$ hay $x = a_i + k.q_i^{e_i}$ với $0 \leq a_i < q_i^{e_i}$
* Với mỗi i, đặt $m_i = \frac{n}{q_i^{e_i}}$. Nâng lũy thừa hai vế của phương trình $g^x \equiv h$ lên $m_i$: $$g^{(a_i + k \cdot q_i^{e_i}) \cdot m_i} \equiv h^{m_i} \pmod p$$ $$g^{a_i \cdot m_i} \cdot g^{(k \cdot q_i^{e_i}) \cdot \frac{n}{q_i^{e_i}}} \equiv h^{m_i} \pmod p$$ $$g^{a_i \cdot m_i} \cdot (g^n)^k \equiv h^{m_i} \pmod p$$
* Mà $n$ là bậc của $g$, nên $g^n \equiv 1 \bmod p$, vậy: $$(g^{m_i})^{a_i} \equiv h^{m_i} \pmod p$$
* Từ đây, có thể dùng CRT để ghép các $a_i$ để tìm ra $x$
Ví dụ giải bài toán $3^x \equiv 13 \bmod 31$
```python=
from sympy import factor
from sage.all import *
def facto(p):
res = []
for i in range(2,p):
if(p%i==0): res.append(i)
while(p%i==0): p=p//i
return res
def pohlig_hellman_sage(g, h, p):
res = []
K = GF(p)
n = euler_phi(p)
factors=facto(n)
# print(factors)
for q in factors:
mi = n//q
gi = pow(g, mi, p)
hi = pow(h, mi, p)
ai = discrete_log(K(hi),K(gi), ord = q)
res.append(ai)
return crt(res, factors)
print(pohlig_hellman_sage(3,13,31))
```
Được kết quả là 11.
# Challange Cryptohack
## Starter
### Working with Fields
Bài này đề yêu cầu tìm $d$ sao cho $d \equiv g^-1 \bmod p$.
Code:
```python
print(pow(g,-1,p))
```
flag: `569`
### Generators of Groups
Challenge giới thiệu phần tử sinh của một nhóm con và yêu cầu tìm phần tử sinh của $F_p$ với $p= 28151$
Code:
```sage=
sage: p = 28151
sage: F=GF(p)
sage: F.primitive_element()
```
flag: `7`
### Computing Public Values
Đề bài giới thiệu cơ chế bảo mật của Diffie-Hellman và cách chọn tham số cho an toàn. Cụ thể, cần chọn Số nguyên tố an toàn dạng $p = 2q + 1$ (với $q$ cũng là số nguyên tố lớn) để đảm bảo $p-1$ có các ước số lớn. Điều này làm cho thuật toán Pohlig-Hellman trở nên vô dụng, vì Pohlig-Hellman chỉ hiệu quả khi $p-1$ là số smooth.
Đề bài cho 3 số nguyên $a,g, p$ và yêu cầu tính $g^a \bmod p$
code:
```sage=
sage: g = 2
....: p = 241031242692103258855207602219756607485695054850245994265411694195
....: 8108831682612228890093858261341614673227141477904012196503648957050582
....: 6319427307068050092230627347453410734066962460145893616597740410271692
....: 4945320037872943417032584377865919814376319377685986952408894019557734
....: 6119843545301547043747207749969763750084308926339295559968882457872412
....: 9938101291302945929999479263652640592846472097303849472116814344647144
....: 38488520940127459844288859336526896320919633919
....: a = 97210744383703379624586431620045824684690459848898160585676589047
....: 8853088246897345487328491037710219222038930943365848626194109830309179
....: 3930182167633275721201247601400180386739998376433775904344138666111324
....: 0397954715065905389735559339449258697840004437546565729602759294834958
....: 9216415363722668361328689588996541370097559090335137676411595949335857
....: 3417971489261516942995759702928098053144314470434694474859576699499890
....: 90202320234337890323293401862304986599884732815
....: print(pow(g,a,p))
```
flag:
`1806857697840726523322586721820911358489420128129248078673933653533930681676181753849411715714173604352323556558783759252661061186320274214883104886050164368129191719707402291577330485499513522368289395359523901406138025022522412429238971591272160519144672389532393673832265070057319485399793101182682177465364396277424717543434017666343807276970864475830391776403957550678362368319776566025118492062196941451265638054400177248572271342548616103967411990437357924`
### Computing Shared Secrets
Đề bài cho sẵn các dữ kiện $g,p,A,B,b$ và yêu cầu tính khóa bí mật chung của hai người Bob và Alice dựa theo công thức của Diffie-Hellman.
Ta có, khóa bí mật chung được tính bằng công thức $g^{a \times b} \bmod p = A^b \mod p$
Code:
```sage=
sage: g = 2
....: p = 241031242692103258855207602219756607485695054850245994265411694195
....: 8108831682612228890093858261341614673227141477904012196503648957050582
....: 6319427307068050092230627347453410734066962460145893616597740410271692
....: 4945320037872943417032584377865919814376319377685986952408894019557734
....: 6119843545301547043747207749969763750084308926339295559968882457872412
....: 9938101291302945929999479263652640592846472097303849472116814344647144
....: 38488520940127459844288859336526896320919633919
....: A = 702499432175954682785545412649754829092891743515161339944958214007
....: 1062529184010196059572046267260420213349302324139391639462982952627264
....: 3847352371534839862030410331485087487331809285533195024369287293217083
....: 4144240968669258458386418409231934808213320567355924837309210555322225
....: 0560566166423618228522950426588175258041019473163389534582396391090173
....: 1715743835775619780738974844840425579683385344491015955892106904647602
....: 049559477279345982530488299847663103078045601
....: b = 120192332529039903445985225357749630203957704094452967240343784334
....: 9797684016780597058996096222194829095187338772810211599683145448229924
....: 3226839490999713763440412177965861508773420532266484619126710566414914
....: 2275601037153366961932103798505750477303883783482661809349461391004798
....: 3133983589658344369152937270395458907150771791713690677012207773981426
....: 2298488662138085608736103418601750861698417340264213867753834679359191
....: 427098195887112064503104510489610448294420720
....: B = 518386956790041579928056815914221837599234551655144585133414727838
....: 9771457772133830180966625168143025838418589010218222735051207284517884
....: 1296797180903885409067074326518713820816935515541188306354188120928896
....: 7735684152473260687799664130956969450297407027926009182761627800181901
....: 7218405578708280198402185481884872604418293336034327140234470299428630
....: 7697948788956945218625733351235572472594139049896654668279060812561316
....: 6744820307691068563387354936732643569654017172
....: print(pow(A,b,p))
```
flag: `1174130740413820656533832746034841985877302086316388380165984436672307692443711310285014138545204369495478725102882673427892104539120952393788961051992901649694063179853598311473820341215879965343136351436410522850717408445802043003164658348006577408558693502220285700893404674592567626297571222027902631157072143330043118418467094237965591198440803970726604537807146703763571606861448354607502654664700390453794493176794678917352634029713320615865940720837909466`
### Deriving Symmetric Keys
Đề cho file source:
```python=
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))
```
và file decrypt:
```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))
```
Dùng những dữ liệu đề bài cho để tìm shared_secret:
```sage=
sage: g = 2
....: p = 241031242692103258855207602219756607485695054850245994265411694195
....: 8108831682612228890093858261341614673227141477904012196503648957050582
....: 6319427307068050092230627347453410734066962460145893616597740410271692
....: 4945320037872943417032584377865919814376319377685986952408894019557734
....: 6119843545301547043747207749969763750084308926339295559968882457872412
....: 9938101291302945929999479263652640592846472097303849472116814344647144
....: 38488520940127459844288859336526896320919633919
....: b = 197395083814907028991785772714920885908249341925650951555219049411
....: 2984362171906051908249347873362792287858097835318145076613851112206393
....: 2935804819633962606567686911973797917553177076886180858111031190354856
....: 7424039264485661330995221907803300824165469977099494284722831845653985
....: 3927914802647120912935802749471324804023198121104626411438845777063358
....: 5919066824069468026116021060950689184279386829767261962592400140303567
....: 6872189455767944077542198064499486164431451944
....: A = 112218739139542908880564359534373424013016249772931962692237907571
....: 9903344835288775138092726256105120611590617376085472885586628796850866
....: 8429962448174286501692406500055526797783014474036446797720655591478123
....: 6397216033805882207640219686011643468275165718132888489024688846101943
....: 6424596554236091119763633160806204719282368797379442175034622656157747
....: 7431898637587844097881923834607790886411615683187469581747777247712123
....: 2820827728424890845769152726027520772901423784
....: B = 124197246052207534478333755666070053776033110833273567786386281366
....: 6578639518899293226399921252049655031563612905395145236854443334774555
....: 9822048578957163832157054989703953795266987614689321472006505136260282
....: 6344960575566118952552134314297926504406840940566754924112559738717300
....: 6460145379759986272191990675988873894208956851773331039747840312455221
....: 3545899107269828192034219927297382964528203655537591825472559989848821
....: 58393688119629609067647494762616719047466973581
....: pow(A,b,p)
```
có shared_secret là `1547922466740669851136899009270554812141325611574971428561894811681012510829813498961168330963719034921137405736161582760628870855358912091728546731744381382987669929718448423076919613463237884695314172139247244360699127770351428964026451292014069829877638774839374984158095336977179683450837507011404610904412301992397725594661037513152497857482717626617522302677408930050472100106931529654955968569601928777990379536458959945351084885704041496571582522945310187`
Thay shared_secret và iv, encrypted_flag đề cho vào code decrypt thì được flag:
`crypto{sh4r1ng_s3cret5_w1th_fr13nd5}`
## Man In The Middle
### Parameter Injection
Đề bài cho server `socket.cryptohack.org 13371`. Khi connect thì nhận được nội dung sau:
```
Intercepted from Alice: {"p": "0xffffffffffffffffc90fdaa22168c234c4c6628b80dc1cd129024e088a67cc74020bbea63b139b22514a08798e3404ddef9519b3cd3a431b302b0a6df25f14374fe1356d6d51c245e485b576625e7ec6f44c42e9a637ed6b0bff5cb6f406b7edee386bfb5a899fa5ae9f24117c4b1fe649286651ece45b3dc2007cb8a163bf0598da48361c55d39a69163fa8fd24cf5f83655d23dca3ad961c62f356208552bb9ed529077096966d670c354e4abc9804f1746c08ca237327ffffffffffffffff", "g": "0x02", "A": "0x446aee21ae370dbf2898e12f1596ae908f0146d54582c2858d346737d57ad65005809e60e78a8798c6ad2b46e67c36e23b67ad603e52c49648d10ae6e98437592263ac5335425eeb665f517c9b30ddce3c0352d4d27e34bee51fa9a64e9cd62feac158b24457add8b6db3ef8c87e27b52b1a42f39f2df9d5aa741adf4b3b16c43d5cc3c32ce0737d1bbc97ee005efad5852d50b5bfd72b79c430785497ece6e55064dbdbc41cf6287f763e121d6598e3817b0667acb9f2bc86af31ed331d43e6"}
```
Gửi tiếp JSON từ Alice cho Bob thì nhận được:
```
Intercepted from Bob: {"B": "0x5183c9693a862f4b5e7434541eb9cc45488b1fe1d1233690b70aa91d576caebd87063a4d9f88b77f5790566d8bfc91ae7f1ab1979c944ad4e62cbcd61a216067db20e43ee580412e4a04aebe089b8b678e6eecd2680d05dfd7022441b278b67f2018e4375ed4bef4255f94942d60dff7d1f7fb4146ed2150ba36243cdcab95f8a9f9c5afea532c9c47c06f6affd7ef03b892942b13cb7db5cb628eb38275becb9f50f1a1c650ef72a26c834819146838d4b13578e1ff60851ffaa8a223f76fcb"}
```
Sau đó tiếp tục gửi JSON này cho Alice, nhận được:
```
Intercepted from Alice: {"iv": "1c07e7d78af3912d022959bcfb44e2fc", "encrypted_flag": "686eb0b1d952404c5603dd403506f6dc2f0348414d0f142a1f0bc5027c60a033"}
```
Chúng ta đã có được các thông tin:
* iv
* encrypted_flag
* p,g,A,B
Vậy, đây là dạng bài người đứng giữa chặn thông tin của Alice và Bob. Mình cần thay đổi thông tin giữa họ để tìm ra được shared secret.
Ở thông tin đầu tiên, Alice gửi đi p,g,A. Nhận thấy `1` là ước của mọi số nguyên, hay mọi số mod 1 đều bằng 0, nên mình sẽ sửa p thành 1 và gửi lại cho Bob.
Sau đó Bob gửi lại B và B chắc chắn sẽ bằng 0, lúc này shared flag cũng chắc chắn bằng 0.
Tiếp tục gửi B cho Alice, ta nhận lại được iv và encrypted_flag. Dùng iv và encrypted_flag nhận được và shared secret = 0 vào script của bài `Deriving Symmetric Keys`, được flag là `crypto{n1c3_0n3_m4ll0ry!!!!!!!!}`
Code:
```python=
import json
from pwn import *
io = remote("socket.cryptohack.org", 13371)
io.recvuntil("Intercepted from Alice: ")
alice = json.loads(io.recvline())
alice['p'] = "1"
io.recvuntil("Send to Bob: ")
io.sendline(json.dumps(alice))
io.recvuntil("Intercepted from Bob: ")
io.sendline(io.recvline())
io.recvuntil("Intercepted from Alice: ")
res = json.loads(io.recvline())
print(res["iv"])
print(res["encrypted_flag"])
io.interactive()
```
### Export-grade
Đề cho server `socket.cryptohack.org 13379` và nói là Alice và Bob đang cần thương lượng các tham số mà cả hai đều hỗ trợ.
Khi connect tới server thì mình nhận được một list các dạng DH của Alice: `Intercepted from Alice: {"supported": ["DH1536", "DH1024", "DH512", "DH256", "DH128", "DH64"]}`
Do DH64 là dạng có lượng byte nhỏ nhất, dễ tìm ra số mũ a nhất nên mình sẽ sửa tin nhắn của Alice lại như sau: `{"supported": ["DH64"]}` và gửi cho Bob.
Lúc này Bob chỉ có một lựa chọn là DH64, và ta sẽ nhận được các thông tin sau
```
Intercepted from Alice: {"p": "0xde26ab651b92a129", "g": "0x2", "A": "0x89cdd23a85d2cf1f"}
Intercepted from Bob: {"B": "0x74b3df712a15942f"}
Intercepted from Alice: {"iv": "9676a853cb09063f6f1e0b6b38ce8dd6", "encrypted_flag": "fa33d66df5a39b7c73ff18e5d7abfbd67882f47537138ae800b83a102fbd94d6"}
```
Code:
```python=
from pwn import *
import json
io = remote("socket.cryptohack.org", 13379)
io.recvuntil("Intercepted from Alice: ")
alice = json.loads(io.recvline())
alice['supported'] = ["DH64"]
io.recvuntil("Send to Bob: ")
io.sendline(json.dumps(alice))
io.recvuntil("Intercepted from Bob: ")
io.sendline(io.recvline())
io.recvuntil("Intercepted from Alice: ")
res = json.loads(io.recvline())
io.recvuntil("Intercepted from Bob: ")
b = json.loads(io.recvline())
io.recvuntil("Intercepted from Alice: ")
iv = json.loads(io.recvline())
print(res['p'])
print(res['g'])
print(res['A'])
print(b['B'])
print(iv['iv'])
print(iv['encrypted_flag'])
```
Do p và A nhỏ nên có thể dùng discrete_log trong sage để giải và tìm được a của Alice, sau đó tìm $B^a \bmod p$ là ra được shared secret
```sage=
sage: p = 0xde26ab651b92a129
sage: F=GF(p)
sage: a = discrete_log(F(A), F(g))
sage: B = 0x74b3df712a15942f
sage: pow(B,a,p)
# 2927496042998365034
```
Dùng script bài `Deriving Symmetric Keys`, ta được flag là: `crypto{d0wn6r4d35_4r3_d4n63r0u5}`
### Static Client
Khi connect tới server đề cho, ta nhận được thông tin như sau:
```
Intercepted from Alice: {"p": "0xffffffffffffffffc90fdaa22168c234c4c6628b80dc1cd129024e088a67cc74020bbea63b139b22514a08798e3404ddef9519b3cd3a431b302b0a6df25f14374fe1356d6d51c245e485b576625e7ec6f44c42e9a637ed6b0bff5cb6f406b7edee386bfb5a899fa5ae9f24117c4b1fe649286651ece45b3dc2007cb8a163bf0598da48361c55d39a69163fa8fd24cf5f83655d23dca3ad961c62f356208552bb9ed529077096966d670c354e4abc9804f1746c08ca237327ffffffffffffffff", "g": "0x02", "A": "0x4b782de3b459d0cff3c6c59aa4ba4392d23fd75c50b29c4d2eed34653de019613e49abc5e0cbdbea721a1e94ba9f1de23739fe2a1eea6bb45ecaab9765af9413afa0ba5f5c532b995ad1a9fe1c42a50a663fa51d8ee2706f05c9ee685728a6434b2f13918a77582dc52e8191ffcd8ab332a2e7ca9fce65593f1bea0dee49813a73509f0ff12ed0093ae572cc2e5e6d9700153e915c34f8acbaa8c83f6ebd6f20e6c3761e6e60daf71456428203edd4cfc56092de1abbe1301178b3f0b538d3b6"}
Intercepted from Bob: {"B": "0x8d79b69390f639501d81bdce911ec9defb0e93d421c02958c8c8dd4e245e61ae861ef9d32aa85dfec628d4046c403199297d6e17f0c9555137b5e8555eb941e8dcfd2fe5e68eecffeb66c6b0de91eb8cf2fd0c0f3f47e0c89779276fa7138e138793020c6b8f834be20a16237900c108f23f872a5f693ca3f93c3fd5a853dfd69518eb4bab9ac2a004d3a11fb21307149e8f2e1d8e1d7c85d604aa0bee335eade60f191f74ee165cd4baa067b96385aa89cbc7722e7426522381fc94ebfa8ef0"}
Intercepted from Alice: {"iv": "083a8b56a2a1846780d9e45ccd09a45c", "encrypted": "d95a003d1293f606d04bf1c8da0e815f5a1fbb6dab64c7ea03043da4a1fd08ed"}
Bob connects to you, send him some parameters:
```
Vậy, cần gửi cho Bob một tin nhắn để nhận về B, ta đã biết $B = g^b \bmod p$, mà $s = g^{a \times b} \bmod p$. Nếu ta tráo giá trị của A và g trong tin nhắn của Alice, giá trị B của Bob sẽ là $A^b \bmod p = g^{a \times b} \bmod p$ hay ta sẽ nhận được shared secret từ Bob qua B. Code:
```python=
from pwn import *
import json
io = remote("socket.cryptohack.org", 13373)
io.recvuntil("Intercepted from Alice: ")
first = json.loads(io.recvline())
io.recvline("Intercepted from Bob: ")
io.recvuntil("Intercepted from Alice: ")
print(first['g'])
print(first['A'])
goc = json.loads(io.recvline())
first['g'],first['A']=first['A'],first['g']
io.sendline(json.dumps(first))
io.recvuntil("Bob says to you: ")
B = json.loads(io.recvline())
print(B)
```
Lúc này chỉ cần lấy giá trị iv và encrypted gốc và giá trị B vừa tìm được, dùng script trong bài `Deriving Symmetric Keys`, ta sẽ tìm được flag: `crypto{n07_3ph3m3r4l_3n0u6h}`
## Group Theory
### Additive
Ở bài này, thay vì sử dụng nhóm nhân, Alice và Bob đã sử dụng nhóm cộng, vậy nên bài toán trở nên đơn giản hơn rất nhiều.
Connect server đề cho:
```python=
from pwn import *
import json
io = remote("socket.cryptohack.org", 13380)
io.recvuntil(b"Intercepted from Alice: ")
alice1 = json.loads(io.recvline().decode())
io.recvuntil(b"Intercepted from Bob: ")
Bob = json.loads(io.recvline().decode())
io.recvuntil(b"Intercepted from Alice: ")
alice2 = json.loads(io.recvline().decode())
io.interactive()
```
Ta được thông tin sau:
```
Intercepted from Alice: {"p": "0xffffffffffffffffc90fdaa22168c234c4c6628b80dc1cd129024e088a67cc74020bbea63b139b22514a08798e3404ddef9519b3cd3a431b302b0a6df25f14374fe1356d6d51c245e485b576625e7ec6f44c42e9a637ed6b0bff5cb6f406b7edee386bfb5a899fa5ae9f24117c4b1fe649286651ece45b3dc2007cb8a163bf0598da48361c55d39a69163fa8fd24cf5f83655d23dca3ad961c62f356208552bb9ed529077096966d670c354e4abc9804f1746c08ca237327ffffffffffffffff", "g": "0x02", "A": "0x598d0d3b1aca9e2f321e496d96d07a8e4825c2f9b66f18ce24fac297e07a26e1ff566c183a2db633842add1efd23e404d8e6a40f98b17b21556c95a694aa853d63bc92411278ecb9a7a6581f18650229ec0102c5e0c8fe51487c1a567847c6f45e57c204b07769bb972769f6936f7da534a0df5e9535ceaa6f6d52428c516f9d7bcb1a0c42de740ea4f7d022b7193a5b78bfce37e29513fbafd6942835b3fb052c2f7652a2a21abdd0b2b2d60403f7b00bd7f7757b459498e3890a4412edfa01"}
Intercepted from Bob: {"B": "0x973a794315c76cc9fc4206772f03cae436449fc63820dc28a599a04e42ba52b2834c4af841978cc52e57c5e1367c7fcdfeb2e075f37796afaa59efc8746089499ab126cc648a867eb693f7c18cfe1888b1cab3ecf8a1f6b75de5f9b12329d41816311c3d733cd649eec911e92643fe46f148b993f451ce1d154c79bb164c0a93313f59c72192cb9ba3049883275f6c7d81a77245c9c1e0105d0298251c8e9d44ec9c84d8b07f767b3b5b3e2c536da0054a2d5049475d6c5a5bbf373887551234"}
Intercepted from Alice: {"iv": "c2f922f9c8cab5fad81e11edc32e01c5", "encrypted": "5acfcbf2d01149aeeb31b9869f07474157bc97ae67bf4e871bb443948bccc4ab6d0761ae3b6f252bfc0d38b1372133b9"}
```
Ta cần tìm s sao cho $s=g^{a \times b} \bmod p$ trong nhóm cộng thì $s=g \times{a \times b} \bmod p$
Mà ta đã có được p,g, A, B, nên chỉ cần lấy $$A \times B \times g^{-1} \mod p$$ $$\rightarrow g \times a \times g \times b \times g^{-1} \bmod p$$ $$\rightarrow g \times{a \times b} \bmod p$$
```sage=
sage: A=0x35644e4ec883f7ca29fbeba50e1e6fe636b846a27800af32a3b1b650aeacb8d40db3a4640ef74a751510d632c6fecfa22a11dcec4159d4c9cd8ee51d33628a43a312399aab8c9e27f6
....: 95b2f989a9942bd57f0bc6a460bec45684cd4a2872fd22630331d6ed994e83db981c4c70e45b4c94e01f5aeefd4b2630dc9962ef4934ced63c68398112399b70ae3aabca1404245e83609a
....: dac97404f143712be0089dcfd15a569ec16b0d78cf7f5a44d636e38bb6d3f0c840f52f0c1d523b062bbd7042
sage: B=0x2f04a9813609e34c9a4cc01f7d9a700a3ffbeb7410d2f90fe51abbd9c45d7253e54fa23eca98c1f7bade73b79fd0e2303e6cdd82cddacd0940b2544160396db361ff0a1032b687bb36
....: 08a4ca844ff73b655782fd0174450cdc2fd30c2110e23fe245c6571106bad2c0e9a8ac0f573738b2788a4d97dd6b9665a237d207459ac99258d6fc0a59ab2cc185f3e188acf3a8f16234b3
....: 1b6241900dd21406d8b3d836a48d7f8d8043bdb787227a36b105ec35cc31b5e1e70260ea9035a4a060e5824e
sage: g=0x02
sage: p=0xffffffffffffffffc90fdaa22168c234c4c6628b80dc1cd129024e088a67cc74020bbea63b139b22514a08798e3404ddef9519b3cd3a431b302b0a6df25f14374fe1356d6d51c245e4
....: 85b576625e7ec6f44c42e9a637ed6b0bff5cb6f406b7edee386bfb5a899fa5ae9f24117c4b1fe649286651ece45b3dc2007cb8a163bf0598da48361c55d39a69163fa8fd24cf5f83655d23
....: dca3ad961c62f356208552bb9ed529077096966d670c354e4abc9804f1746c08ca237327ffffffffffffffff
sage: A*B*pow(g,-1,p)%p
```
được shared secret là `1584383325800671150096769717564524871389951059969919946933160464729626387476679708513189460736498610764141915778611278510000545164004259232718518824542270376844944386199382076274120398605983358450579924688006761674683779938645554668104266239070848978925931749850843683946119737337296523100912550830711553636231349549349305067628600634109997205901615395257700282212675357677456308972184413286002712504980069635049961948561524186962700435880577974562104383433111336`
đưa vào file decrypt ta được flag: `crypto{cycl1c_6r0up_und3r_4dd1710n?}`
### Static Client 2
Khi connect với server `socket.cryptohack.org 13378` đề cho, nhận được thông tin sau:
```
Intercepted from Alice: {"p": "0xffffffffffffffffc90fdaa22168c234c4c6628b80dc1cd129024e088a67cc74020bbea63b139b22514a08798e3404ddef9519b3cd3a431b302b0a6df25f14374fe1356d6d51c245e485b576625e7ec6f44c42e9a637ed6b0bff5cb6f406b7edee386bfb5a899fa5ae9f24117c4b1fe649286651ece45b3dc2007cb8a163bf0598da48361c55d39a69163fa8fd24cf5f83655d23dca3ad961c62f356208552bb9ed529077096966d670c354e4abc9804f1746c08ca237327ffffffffffffffff", "g": "0x02", "A": "0xca233eb58bc3f13d0b62ac9e9fda8ae06d112f9129d74c87ae175314e0c6bb9223ebb336f4ed9fde17fa4e7bee32f21b995109970dd9a4bc6e55f2a0ded658b85af4abd00934b359345b8c0288216bda70f812b6de023d2b679a62d6fa91368eb08f360b0405b85023787ead23de78a7b859ab63d7e0ef53ac7f2283b1051312b58d00d41ebe6068ccc5a4485154c9eebcbfe89fbf04cbeb03ae7c2882b21f1f63e3a824f2d29954160e8f9032b9b4bfbd3068b123640597b7e36e632f1cbbeb"}
Intercepted from Bob: {"B": "0xd0d69585c6586c3b1a23e04245826be6db4aed1c9bc70f7110a30165ca878d31434aa357c2bd26d3c398284a17319504e1aeead141234afeb57dfef11417fdec44b21cea83920f300f4e0c3fb573a895371b24652c5e6ea0539b7719f0f966ac7adb9a292cc49f4d8b39560e02fa82aab3c273cc7df512a80e2de6f0e8840c00554f09460eaa2e221173a9ca13182d4e1342b1e54965e16ca5fc23b1aae80aedc7fb80e1aa9be8b0274812676e8e570e1abf65eea0c49f18794a5afba975c7c7"}
Intercepted from Alice: {"iv": "d1a3e1aa1c9c5261224952affb328d52", "encrypted": "f27b2080af7ec541ebfe596dd9f78bddf8fda3017377369eb887d956d8a039238310530754dba6c4dfb25dfa89ce07aa"}
Bob connects to you, send him some parameters:
```
Thử làm giống challenge trước, đổi g và A lại sau đó gửi đi, thì nhận được:
`Bob says to you: {"error": "That g value looks mighty suspicious"}`
Khi thử cho $p=1$ :
`Bob says to you: {"error": "Doesn't look like a legit public value"}`
Mục tiêu của bài này vẫn là tìm shared secret từ những thông tin có sẵn, mình sẽ tiến hành sinh một p khác sao cho p-1 là một số smooth rồi đổi với p của Alice và gửi đi.
Code sinh p ngẫu nhiên:
```python=
from Crypto.Util.number import getPrime , isPrime
def get_prime(factor_bits, nbits):
while True:
p = 2
while p.bit_length() + factor_bits < nbits:
p *= getPrime(factor_bits)
current_len = p.bit_length()
needed_bits = nbits - current_len
if needed_bits < 2:
continue
try:
last_prime = getPrime(needed_bits)
except ValueError:
continue
p = p * last_prime + 1
if p.bit_length() == nbits and isPrime(p):
return p
p = get_prime(16, 2048)
print(hex(p))
```
Giá trị p smooth:
`0x855a429bea546be316f9632a7304de26fe1a7379ee02516a3c1c87c3262d2aa262d9e0090b3d294ef89abf4d9a6a5076721fe93d966ae7021f7bd5f3dd4851d0635beed63a8ce18858c839800547edaaf735c84f7ca9f9111db69f1e3b5e36d59b09a97d735f55ac337bbea0a241cc82cf55eeafb927c1d83eb7f7e7be0b37287cdbc327a099623c5dc302cf1e5d151eea4580b3621198c375f7dcd864cd32939af857a4aee047e9946183880c3f75bc68ed2ecb788996a64767fcb658becb54ddba8b30968968b7b30c10e7956222954477ca04dd8e3caad8f248c203023c74380d8624a7d49e05c5b41b03508af465a08eadc8e6fc686485492a59f76c77df`
Thay p gốc bằng p smooth rồi gửi cho Bob:
```python=
from pwn import *
import json
io = remote("socket.cryptohack.org", 13378)
io.recvuntil(b"Intercepted from Alice: ")
first = json.loads(io.recvline())
io.recvuntil(b"Intercepted from Alice: ")
dataa = json.loads(io.recvline())
p2 = "0x855a429bea546be316f9632a7304de26fe1a7379ee02516a3c1c87c3262d2aa262d9e0090b3d294ef89abf4d9a6a5076721fe93d966ae7021f7bd5f3dd4851d0635beed63a8ce18858c839800547edaaf735c84f7ca9f9111db69f1e3b5e36d59b09a97d735f55ac337bbea0a241cc82cf55eeafb927c1d83eb7f7e7be0b37287cdbc327a099623c5dc302cf1e5d151eea4580b3621198c375f7dcd864cd32939af857a4aee047e9946183880c3f75bc68ed2ecb788996a64767fcb658becb54ddba8b30968968b7b30c10e7956222954477ca04dd8e3caad8f248c203023c74380d8624a7d49e05c5b41b03508af465a08eadc8e6fc686485492a59f76c77df"
p1 = first['p']
first['p'] = p2
print(p1)
io.sendlineafter("Bob connects to you, send him some parameters: ", json.dumps(first))
io.recvuntil("Bob says to you: ")
B = json.loads(io.recvline())
io.interactive()
```
Sau khi tìm được p, gửi cho Bob và nhận được B' và iv, encrypted fake.
Ta có: p1 là p ban đầu, p2 là p mà mình vừa mới sinh.
* Đầu tiên, có: $A = g^a \bmod p_1$, $B_1 = g^b \bmod p_1$
* Sau khi gửi p2: $B_2 = g^b \bmod p_2$
Do p2 smooth nên có thể dễ dàng tìm ra b từ discrete_log của sage, sau đó thế giá trị vừa tìm được vào phương trình ban đầu để tìm shared secret.
```sage=
p2 = 0x855a429bea546be316f9632a7304de26fe1a7379ee02516a3c1c87c3262d2aa262d9e0090b3d294ef89abf4d9a6a5076721fe93d966ae7021f7bd5f3dd4851d0635beed63a8ce18858c839800547edaaf735c84f7ca9f9111db69f1e3b5e36d59b09a97d735f55ac337bbea0a241cc82cf55eeafb927c1d83eb7f7e7be0b37287cdbc327a099623c5dc302cf1e5d151eea4580b3621198c375f7dcd864cd32939af857a4aee047e9946183880c3f75bc68ed2ecb788996a64767fcb658becb54ddba8b30968968b7b30c10e7956222954477ca04dd8e3caad8f248c203023c74380d8624a7d49e05c5b41b03508af465a08eadc8e6fc686485492a59f76c77df
p1 = 0xffffffffffffffffc90fdaa22168c234c4c6628b80dc1cd129024e088a67cc74020bbea63b139b22514a08798e3404ddef9519b3cd3a431b302b0a6df25f14374fe1356d6d51c245e485b576625e7ec6f44c42e9a637ed6b0bff5cb6f406b7edee386bfb5a899fa5ae9f24117c4b1fe649286651ece45b3dc2007cb8a163bf0598da48361c55d39a69163fa8fd24cf5f83655d23dca3ad961c62f356208552bb9ed529077096966d670c354e4abc9804f1746c08ca237327ffffffffffffffff
g = 0x02
A = 0x6e04662590d4e35870cc79d25b44377b2a8f3cc86d6a5335a3e2741232421b62cb971eaae0082f5aa20283c425ad1a19409673f276dd8e06c12f83ce0d352e019b3369d005a3cf6cbe4b6612c5be68512d6ed0231f8e49b156f850023e8337847072ffcae0073d1838fc4723d652b9553e0c90f33e4ec8339d4ed89e07dd6f99b5cc6fdbbda70e68ac4311fc888d834757a9f6c3abe081b85b7fd2c4e1382d7743902f851d8353e01fb7fb8ce1d7e7ad591f3a05dba618d568a2a1d3097f8054
B2 = 0x6ea8e1d3832d26b30798ae0b96c81fb6f8a157c4a462b3e4ec46f9058cc3dea5bdeea7b5ce54f9300aa1b23da1308240ccd95936351843da1fe73aa8671c48a3a419f55abc27ecc1998aa07c915abbc02f3b62cc30561c828872810b5038a1141aa8cd603ee09055df482caa1bb6450e0e9e9fa09f6b3b7d2680b1864d93f392706366ca5936b06b3c9ae6d909cf5d2f2e1396df98c3194eb73d62f1af6ca0edd362daee3d08869f72ceb83a216bb48cf12b611cde00c79b9862b2498f2cfb5a19da225062994fb0b010a2c154108984311be637c4d58fdf464e848e0dcd11a8a819b9948b7ccbf7abf192816dea9e8ead504fd4eacf6ac19e70dde8969bb237
F = GF(p2)
b = discrete_log(F(B2), F(g))
pow(A,b,p1)
```
Thay shared secret vào file decrypt, ta được flag: `crypto{uns4f3_pr1m3_sm4ll_oRd3r}`
## Misc
### Script Kiddie
Đề bài cho file script:
```python=
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()
```
và file output:
```
p: 2410312426921032588552076022197566074856950548502459942654116941958108831682612228890093858261341614673227141477904012196503648957050582631942730706805009223062734745341073406696246014589361659774041027169249453200378729434170325843778659198143763193776859869524088940195577346119843545301547043747207749969763750084308926339295559968882457872412993810129130294592999947926365264059284647209730384947211681434464714438488520940127459844288859336526896320919633919
g: 2
A: 539556019868756019035615487062583764545019803793635712947528463889304486869497162061335997527971977050049337464152478479265992127749780103259420400564906895897077512359628760656227084039215210033374611483959802841868892445902197049235745933150328311259162433075155095844532813412268773066318780724878693701177217733659861396010057464019948199892231790191103752209797118863201066964703008895947360077614198735382678809731252084194135812256359294228383696551949882
B: 652888676809466256406904653886313023288609075262748718135045355786028783611182379919130347165201199876762400523413029908630805888567578414109983228590188758171259420566830374793540891937904402387134765200478072915215871011267065310188328883039327167068295517693269989835771255162641401501080811953709743259493453369152994501213224841052509818015422338794357540968552645357127943400146625902468838113443484208599332251406190345653880206706388377388164982846343351
iv: 'c044059ae57b61821a9090fbdefc63c5'
encrypted_flag: 'f60522a95bde87a9ff00dc2c3d99177019f625f3364188c1058183004506bf96541cf241dad1c0e92535564e537322d7'
```
Trong file script của đề cho, mình đang ở vị trí của Bob, nhận p, g, A từ Alice, chọn b và tính B, gửi lại cho Alice và tính shared secret. Nhưng vấn đề nằm ở chỗ này:)
```python=
def generate_public_int(g, a, p):
return g ^ a % p
def generate_shared_secret(A, b, p):
return A ^ b % p
```
B được tạo từ hàm `generate_public_int`, thay vì dùng pow(g,a,p) thì hàm này lại dùng phép xor, thành ra chỉ cần xor ngược lại B cho g sẽ tìm được b, từ đó tìm được shared secret.
Code:
```python=
p= 2410312426921032588552076022197566074856950548502459942654116941958108831682612228890093858261341614673227141477904012196503648957050582631942730706805009223062734745341073406696246014589361659774041027169249453200378729434170325843778659198143763193776859869524088940195577346119843545301547043747207749969763750084308926339295559968882457872412993810129130294592999947926365264059284647209730384947211681434464714438488520940127459844288859336526896320919633919
g= 2
A= 539556019868756019035615487062583764545019803793635712947528463889304486869497162061335997527971977050049337464152478479265992127749780103259420400564906895897077512359628760656227084039215210033374611483959802841868892445902197049235745933150328311259162433075155095844532813412268773066318780724878693701177217733659861396010057464019948199892231790191103752209797118863201066964703008895947360077614198735382678809731252084194135812256359294228383696551949882
B= 652888676809466256406904653886313023288609075262748718135045355786028783611182379919130347165201199876762400523413029908630805888567578414109983228590188758171259420566830374793540891937904402387134765200478072915215871011267065310188328883039327167068295517693269989835771255162641401501080811953709743259493453369152994501213224841052509818015422338794357540968552645357127943400146625902468838113443484208599332251406190345653880206706388377388164982846343351
b = B ^ g % p
print(A ^ b % p)
```
Sau khi có shared secret, dùng lại script decrypt, ta được flag:
`crypto{b3_c4r3ful_w1th_y0ur_n0tati0n}`
Sign in with Wallet
Connect another wallet