# Nhập môn crypto
---
## Thuật toán
### Euclide
a\*x(k)+b\*y(k) = r(k)
r0 = r1.q1 + r2
( x0, y0, r0 ) = (1,0,a)
( x1, y1, r1 ) = (0,1,b)
( x2, y2, r2) = ( x0-x1.q1, y0 - y1.q1, r0 - r1.q1)
### GCD (ước chung lớn nhất)
gcd(a,b)=(a,b)
a=bq+r --> (a,b) = (b,r)
(r = a%b trong code)
(a,b)=1 => a,b nguyên tố cùng nhau
(a,b)=d => tồn tại m,n thuộc Z thỏa am+bn=d
(i) Nếu a chẵn b chẵn => gcd(a,b) = 2^(min(a2,b2)) gcd(a1,b1)
Tức là rút 2^n của đứa chứa ít 2 hơn.
(ii) Nếu a chẵn b lẻ => gcd(a,b) = gcd(a/2,b)
(iii) Nếu a lẻ b lẻ => gcd(a,b) = gcd(min(a,b),|a-b|)
### Phi hàm Euler φ(n)
φ(n) là các số tự nhiên nhỏ hơn n và nguyên tố cùng nhau với n trong khoảng [1,n](tính cả giá trị 0)(tức là n và k không có ước chung)
Vd: φ(8)=4, φ(10)=4
nguyên tố cùng nhau của 6 là {1,5}
**φ(p^α)= p^α - p^(α-1)** #trong đó p là prime.
**Định lý 2**: **Nếu (a,b)=1 thì φ(ab)=φ(a).φ(b)**
p1,p2,... là ước của n
### Định lý Fermat (nhỏ)
Nếu p là prime và (a,p)=1 => **a^(p-1) 三 1 (mod p)**
### Nghịch đảo
Xét {x1,x2,..x(φ(n)) } = B
Các số nghịch đảo luôn nằm cùng trong tập B.
x(i)x(j) 三 1 (mod n)
vd:φ(7)={1,2,3,4,5,6,7}
1.1, 2.4, 3.5, 4.2, 5.3, 6.6
Ta có thể thấy nó có tính chất hoán vị cho nhau.
### Đồng dư
1----------------------------Tổng các số % n (3 và 9)
abc % 3 = 0 khi
Với abc = a\*100 + b\*10 + c
a\*100 % 3 = a\*1 % 3
b*10 % 3 = b\*1 % 3
c % 3 = c % 3
=> a+b+c % 3 => abc % 3 = 0
2-----------------------------------------------------------
a 三 b (mod n), b 三 c (mod n) => a 三 c (mod n)
a 三 b (mod n) thì b 三 a (mod n)
{a 三 b (mod n), c 三 d (mod n)}
=> a +- c 三 b +- d (mod n)
=> a.c 三 b.d (mod n)
=> a^n 三 b^n (mod n)
**3**-----------------------------------------------------------
**VD1**: 4x 三 6 (mod 5)
Z(5)={0,1,2,3,4} Thay lần lượt 0,1,2,3,4 vào chắc chắn ra 4x 三 6 (mod 5).
Khi x=4 thỏa => x=5k+4 (với 4 là nghiệm, 5 là n(số cần mod)).
**VD2:**
3x 三 8 (mod 20)
7.3.x 三 7.8 (mod 20)
1.x 三 56 (mod 20)
x 三 16 (mod 20)
3x 三 1 (mod 20) => x 三 7 (mod 20) hay 3^-1 = 7 (mod 20)
4------------------------------------------------------------
Nếu (a,n)=1 => tồn tại b sao cho a.b 三 1 (mod n)
Chứng minh (a,n)=1 => tồn tại b,y thuộc Z: ab+ny=1
ny ⋮ n
ny = 1-ab
=>1-ab ⋮ n => ab 三 1 (mod n) (dễ hiểu hơn là -(ab-1) ⋮ n)
### Đồng dư trung hoa (CRT)
m(1).m(3)...m(k) là các số nguyên tố khác nhau.
x 三 a1 (mod m1)
x 三 a2 (mod m2)
...
x 三 a(k) (mod m(k))
Đặt N=m(1).m(2)...m(k)
M1 = N/m1 = m(2).m(3)...m(k)
(M1,m1)=1 => tồn tại y1 sao cho M1.y1 三 1 (mod m1)
Tương tự M(k).y(k) 三 1 (mod m(k))
Đặt **x(0)=a1.M1.y1 + ... +a(k).M(k).y(k)**
Chứng minh:
x(0)三 a1.M1.y1 + 0 (mod m1) (Vì các M(k) của các cụm còn lại đều chứa m1)
Dựa vào M(k).y(k) 三 1 (mod m(k)) ở trên:
=>x(0) 三 a1 (mod m1)
Tương tự => x(0) 三 a(k) (mod m(k))
### Nhóm cyclic
Cho số n, các phần tử nào trong [1,n-1] mod n tạo thành vòng tuần hoàn thì là **phần tử sinh** (Căn nguyên thủy modulo n).
Vd:
```
Z(5)={1,2,3,4} có phần tử sinh là 2 và 3
{
2^1%5=2
2^2 %5=4
2^3 %5=3
2^4 %5=1
}
```
#### Cấp của một phần tử ------------------------------
Nhóm Z(7), khi đó:
```
1 có cấp là 1
2 có cấp là 3 (2^3 % 7 = 1)
3 có cấp là 6 (3^6 % 7 = 1)
... 6 có cấp là 2
```
Cấp của G là một số nguyên tố thì G là một nhóm cyclic (tại vì số nguyên tố chỉ chia hết cho chính nó)
### Vành
(G,+,•) là một vành nếu
* (G,+) là 1 nhóm giao hoán
* (G,•) là phép toán nhân có tính chất kết hợp:
(x•y)z=x•(y•z)=x•y•z
* Tính chất phân phối giữa + và *
x•(y+z)=x•y+x•z
(y+z)•x=y•x+z•x
Vd: C/m (Z(n),+,•) là một vành
- (Z,+) là một nhóm giao hoán
- phép nhân có tính chất kết hợp
- x(y+z) =xy+xz
(y+z)x=yx+zx
### Prime
Thuật toán Miller–Rabin.
https://en.wikipedia.org/wiki/Miller%E2%80%93Rabin_primality_test
Giả sử n = x^2 - 1 = (x-1)(x+1)
Nếu một số chia n dư 1 hoặc -1 thì số đó khi ^2 lên sẽ luôn chia acho n dư 1.
Vậy x sẽ dư 1 hoặc -1 khi chia n. hoặc nói theo cách chuyên ngành là x đồng dư 1 hoặc −1 modulo n.
n là số nguyên tố thì nó luôn lẻ (trừ số nguyên tố: 2), vậy n-1 chẵn và nó luôn chia hết cho 2.
Theo định lý nhỏ Fermat: 
Nói đơn giản thì khi nào  chia n dư n-1, thì khả năng n là số nguyên tố.
Ví dụ: với a = 174
## Mã hóa
### Phương pháp mã hóa
* Thay thế – **substitution** . Mỗi ký hiệu của bản rõ được thay thế bằng một hoặc nhiều ký hiểu để tạo ra bản mã
* Chuyển vị – **transposition**. Các ký tự trong bản rõ được sắp xếp lại để tạo thành bản mã
* Thay thế đơn điệu – **Monoalphabetic**. Mã thay thế trong đó một ký hiệu của bản rõ luôn được thay thế bằng cùng một ký hiệu.
* Thay thế đa chiều – **polyalphabetic**. Mã thay thế về cơ bản sử dụng nhiều ánh xạ thay thế dùng một bảng chữ cái.
* Tuần hoàn – **periodic**. Mã thay thế đa chiều trong đó sơ đồ thay thế được lặp lại.
* Không-tuần hoàn – **non-periodic**.
* Mã khối – **block cipher**. Mã hóa diễn theo từng khối ký hiệu.
* Mã Luồng – **stream cipher**. Mã hoạt động trên luồng dữ liệu có độ dài không xác định, thường kết hợp phản hồi.
### Game
#### Luật chơi 1: Giấu thuật E giải lẫn khóa k.
1. 
luật chơi ở đây là giấu cả cách mã (algorithm) lẫn khóa (key).
2. Thay vị trí chữ này bằng vị trí chữ khác.
Đổi vị trí 10 số => 10!
Chỉ cần giữ bí mật khóa.
#### Luật chơi 2: công bố thuật giải E và giữ bí mật khóa k.(RSA)
### Một hệ mật an toàn phải có những tính chất sau:
* **Tính bảo mật** – confidentiality. Chi phí để Eve khôi phục lại thông điệp m từ bản mã c sẽ cao hơn giá trị của thông điệp m.
* **Xác thực** – authentication. Bob có thể dễ dàng xác minh là chính Alice đã gửi thông điệp m.
* **Tính toàn vẹn** – integrity. Bob có thể xác minh rằng thông điệp m không bị giả mạo hay thay đổi gì.
* **Không từ chối** – non-repudiation. Alice không thể từ chối là mình không gửi thông điệp m.
*
Các hệ mã tốt nhất giả định rằng Eve và Mallory ngay cả biết hàm mã E, hàm giải mã D, bản mã c và biết khóa công khai nếu hệ là mã công khai. Hầu hết các hệ thống mật mã **không dựa vào tính bí mật của thuật toán**, vì những lý do sau:
* Nếu thuật toán bí mật của bạn bị xâm phạm, sẽ phải thay thuật toán mới, khó hơn nhiều việc chỉ thay một khóa!
* Công khai thuật toán có thể nhận được sự hỗ trợ của hàng nghìn chuyên gia tìm kiếm lỗi.
#### Shannon's Maxim
Nguyên lý Maxim Shannon giả thiết rằng kẻ thù biết hệ thống! Thuật toán bảo mật phải bền vững *trong ngữ cảnh kẻ thù biết mọi thứ về hệ thống ngoại trừ khóa*.
Nghiên cứu về mã hóa (cryptography) học bao gồm thiết kế các loại mật mã khác nhau, trao đổi khóa, khóa xác thực, hàm băm mật mã, chữ ký số và các vấn đề xã hội (pháp lý, chính trị, v.v.). Tuy vậy, ta cũng sẽ học một số phương pháp phân thám mã (tấn công) để đảm bảo hệ mã xây dựng hay đang sử dụng là an toàn-bảo mật.
### RSA
#### (I) Sinh khóa – KeyGen(λ)
Allice trước hết, chọn ngẫu nhiên 2 số nguyên tố λ/2 bit và tính:
(1) p,q ← Prime(λ)
(2) n ← pq, φ ← (p-1)(q-1)
(3) e.d mod φ=1. (e d thuộc Z)
(4) Allice công bố khóa (e, n) và giữ bí mật d.
#### (II) Mã hóa – Encryption(e,n,m)
c←m^e mod n.
**Giải mã nhanh RSA**
Xét phép tính cd (mod n), với n = pq là tích của 2 số nguyên tố phân biệt p và q.
Đặt
d1 = d mod (p – 1)
d2 = d mod (q – 1).
Có các số k1 và k2 sao cho:
d = k1(p – 1) + d1 = k2(q – 1) + d2 .
c^d ≡(c^(d1 ) mod p)(c^(p-1) mod p)^(k1 ) ≡c^(d1 ) (mod p)
c^d ≡(c^(d2 ) mod q)(c^(q-1) mod q)^(k2 ) ≡c^(d2 ) (mod q)
Theo CRT, hệ trên có duy nhất nghiệm trong n = pq.
Thuật giải giả mã nhanh RSA
```
fastDecryption(c,p,q):
d1 = d mod (p – 1)
d2 = d mod (q – 1)
a1 = powerMod(c, d1, p)
a2 = powerMod(c, d2, q)
m = CRT(a1, a2, p, q)
```
#### (III) Giải mã – Decryption(d,n,c)
m←c^d mod n
Các bài giải mã tại đây: https://hackmd.io/@LightSheng/H1GnE2yMa
## Coding
Ta sẽ xử lý dưới dạng binary.
### a mod 2
Check a[-1] (bit cuối bên phải): 0 là chẵn, 1 là lẻ
### a/b
Idea:
1. Với phép chia ta đếm số binary a và b lệch nhau(gọi là n).
2. Ta thêm số 0 vào b cho bằng độ dài a. (là tăng b lên b^(2 ^ n) lần) (vì mỗi lần thêm 0 là dịch trái sẽ tăng dần 2,4,8...) (Thay vì trừ từng cái b nhỏ sẽ phải trừ rất nhiều lần).
3. Ta bỏ vô vòng lặp a > b. Thì chạy (1),(2) và thêm biến đếm kết quả.
### a^b % c
Idea: Ta tách b ra và * dần vô a, rồi lấy a mod c rồi lấy kết quả đó làm a mới.
a.b mod c <=> (a mod c) * (b mod c) mod c (cách sau này đưa vào code sẽ thực thi nhanh hơn).
```
result = "1"
a = a % c
Vòng lặp ( b > 0 ){
Nếu ( b % 2 == 1 ) (Tức là b lẻ){
result = (result * a) % n
}
a = (a*a) mod n
b = b dịch phải #(b/2)
}
```
## Attack vector
### Many time pad Attack
https://drx.home.blog/2019/03/26/ctf_write-up-securinets-prequals-2k19-23-3-2019/
https://crypto.stackexchange.com/questions/33673/many-time-pad-attack-xor
Tool: https://github.com/Jwomers/many-time-pad-attack/blob/master/attack.py
Ta có thể thấy rằng khi 2 đoạn đã mã hóa cùng xor với nhau thì key sẽ bị triệt tiêu.
Vd:
48 và 0A là 2 kí tự đã được xor với key.
Đồng thời:
0x62 xor 0x20 = 0x42 (vậy 2 kí tự là 0x62 và 0x20)
Ta sẽ tìm ngược lại key bằng công thức: 
(message(0x20) và cipher(48 hoặc 0A).)
Vậy ta chỉ cần thử kí tự thay vì 256 kí tự.
### Flipping attack
https://silk.one/blog/2023/11/05/tsgctf-2023-dance-writeup/
Thay đổi ciphertext dẫn đến thay đổi plaintext (bản rõ)
xor(ciphertext, xor(b'guest', b'admin'))
### AES
https://hackmd.io/@phgvee/BkZEbnzSj
## Detect
### Base 45
Chỉ chữ viết và số và phép tính.
Luyện tập:
https://hackmd.io/@phgvee/rJE8TcANj
## Tham khảo
https://hackmd.io/@phgvee/BJM3Wd8No
Sign in with Wallet
Connect another wallet