MAT3539 - Mật mã và an toàn dữ liệu

Giải bài trên lớp

Bài 1

Giải các phương trình sau:

• a. $3x \equiv 1 \pmod{13}$
• b. $x^2 \equiv 1 \pmod{17}$

Giải

a) $3x \equiv 1 \pmod{13}$

Ta cần $x$ sao cho $3x - 1$ chia hết cho $13$, tức $3x \equiv 1\pmod{13}$. Tìm nghịch đảo của $3$ modulo $13$:

Kiểm tra nhanh: $3\cdot 9 = 27 \equiv 1 \pmod{13}$ (vì $27-2\cdot13=1$). Vậy $3^{-1}\equiv 9\pmod{13}$.

Nhân hai vế với $3^{-1}$ ta có

\[x \equiv 3^{-1}\cdot 1 \equiv 9 \pmod{13}.\]

Kết luận: $x \equiv 9 \pmod{13}$ (ví dụ nghiệm nhỏ nhất $x=9$).

b) $x^2 \equiv 1 \pmod{17}$

Ta giải phương trình $x^2\equiv 1\pmod{17}$, tức

\[x^2-1\equiv 0\pmod{17}\quad\Longleftrightarrow\quad (x-1)(x+1)\equiv0\pmod{17}.\]

Vì $\mathbb{Z}_{17}$ là trường (17 nguyên tố) nên không có zero-divisor; do đó sản phẩm bằng $0$ khi và chỉ khi một trong các thừa số $\equiv 0$.

Suy ra

\[x\equiv 1\pmod{17}\quad\text{hoặc}\quad x\equiv -1\equiv 16\pmod{17}.\]

Kết luận: $x\equiv 1$ hoặc $x\equiv 16$ (mod 17).

Bài 2

(Định lý Wilson). Cho $p$ là một số nguyên tố, $X = {1, 2, …, p-1}$.

• a. CMR với mọi $a \in X$, tồn tại $b \in X$ sao cho $a \cdot b \equiv 1 \pmod{p}$.
• b. Tìm tất cả $x \in X$ sao cho $x^2 \equiv 1 \pmod{p}$.
• c. Từ 2 câu trên, hãy chỉ ra rằng $1 \cdot 2 \cdot … \cdot (p-1) \equiv 1 \pmod{p}$.
• d. Cho số tự nhiên $n \ge 2$ thỏa mãn $1 \cdot 2 \cdot … \cdot (n-1) \equiv -1 \pmod{n}$. CMR $n$ là số nguyên tố.

Giải

Cho $p$ là số nguyên tố, $X={1,2,\dots,p-1}$.

a) Với mọi $a\in X$, tồn tại $b\in X$ sao cho $a\cdot b \equiv 1\pmod{p}$.

Vì $p$ là số nguyên tố, nếu $a\in{1,\dots,p-1}$ thì $\gcd(a,p)=1$. Do đó $a$ có nghịch đảo modulo $p$ — tức tồn tại $b$ thỏa $ab\equiv1\pmod p$ (có thể tìm bằng Euclid mở rộng). (Đây nói rằng mọi phần tử trong $X$ là khả nghịch trong nhóm đơn vị modulo $p$.)

b) Tìm tất cả $x\in X$ sao cho $x^2\equiv1\pmod p$.

Giống Bài 1b, ta giải $(x-1)(x+1)\equiv0\pmod p$. Vì $\mathbb{Z}_p$ là trường, nên

\[x\equiv 1\quad\text{hoặc}\quad x\equiv -1\equiv p-1.\]

Kết luận: hai nghiệm trong $X$ là $1$ và $p-1$.

c) Từ 2 câu trên, chỉ ra $(p-1)! = 1\cdot 2\cdots (p-1)\equiv -1\pmod p$.

(Cảnh báo: đây chính là Định lý Wilson: $(p-1)!\equiv -1\pmod p$.)

Chứng minh (phủ định theo cặp nghịch đảo):

Mỗi $a\in X$ có một nghịch đảo $a^{-1}\in X$. Nếu $a\neq a^{-1}$ thì ta có thể ghép cặp $(a,a^{-1})$ và $a\cdot a^{-1}\equiv1$. Những phần tử không thể ghép cặp theo cách này là các $a$ thỏa $a=a^{-1}$, tức $a^2\equiv1$, mà theo câu (b) chỉ có $a=1$ và $a=p-1$.

Khi nhân tất cả các phần tử trong $X$ lại, mọi cặp khác nhau góp tích $1$, chỉ còn nhân thêm $1$ và $p-1$:

\[1\cdot 2\cdots(p-1) \equiv 1\cdot (p-1) \equiv p-1 \equiv -1 \pmod p.\]

Vậy $(p-1)! \equiv -1\pmod p$. (Đây là phát biểu chuẩn của Định lý Wilson.)

d) Cho số tự nhiên $n\ge2$ thỏa $(n-1)! \equiv -1\pmod n$. Chứng minh $n$ là số nguyên tố.

Chứng minh theo phản chứng (hoặc lấy phản ngược của Wilson):

Giả sử $n$ hợp số. Ta tách hai trường hợp.

Trường hợp 1: $n=4$. Thử trực tiếp $(n-1)! = 3! = 6 \equiv 2\pmod 4 \ne -1 \equiv 3\pmod4$. Vậy $n=4$ không thỏa $(n-1)!\equiv -1$.

Trường hợp 2: $n$ hợp số và $n\ge 6$. Lấy một ước tố $d$ của $n$ thỏa $1<d<n$. Gọi $e=n/d$. Vì $n$ hợp số và $n\ge6$ nên ta có thể chọn $d\le e$ và $e\le n-1$. Nếu $d\ne e$ thì cả $d$ và $e$ xuất hiện trong tích $(n-1)!$, và vì $de=n$ nên $(n-1)!$ chứa một nhân tử bằng $n$, suy ra $(n-1)!\equiv 0\pmod n\ne -1$. Nếu $d=e$ (tức $n$ là bình phương hoàn chỉnh $d^2$), thì $d^2=n$ với $1<d<n$. Khi đó vì $d\le n-1$ thì $d$ xuất hiện trong $(n-1)!$ nhưng xuất hiện chỉ một lần; tuy nhiên vì $n\ge6$ sẽ luôn tồn tại một ước khác hoặc một cách chứng minh bổ sung cho thấy $(n-1)!\not\equiv -1$ (như xét ước tố tối thiểu $p\le \sqrt n$ và đối số tương tự). (Một cách ngắn gọn: đối với mọi $n$ hợp số $\ge 6$ tồn tại hai ước dương $a,b$ khác 1 và nhỏ hơn $n$ sao cho $ab\equiv0\pmod n$; do đó factorial chứa đủ yếu tố để bị chia hết cho $n$.)

Tóm lại, với mọi $n$ hợp số ta có $(n-1)!\not\equiv -1\pmod n$. Do đó nếu $(n-1)!\equiv -1\pmod n$ thì $n$ không thể hợp số ⇒ $n$ là số nguyên tố.

(Ý chính: đây là chiều ngược lại của Định lý Wilson.)

Bài 3

Cho đoạn mã sau:

KHOORZHDUHKXVHUV

Biết rằng bản rõ được viết bằng TA (Tiếng Anh) và đoạn mã trên được tạo bởi mã Caesar. Hãy tìm bản rõ.

Giải

Brute-force giải ra:

\[\text{`HELLO WE ARE HUSERS'}\]

Là shift +23 (-3), manh mối lớn nhất là KHOOR tương ứng với HELLO

Bài 4

Cho \(M = \begin{pmatrix} 1 & 2 \\ 3 & 4 \end{pmatrix}\) được dùng để mã hóa cho mã Hill.

• a. Tính $|M|$. Có tồn tại $M^{-1} \pmod{26}$ không?
• b. Tìm 2 bản rõ có cùng bản mã khi mã hóa với M.

Giải

a) Tính $\det(M)$. Có tồn tại $M^{-1}\pmod{26}$ không?

Tính định thức:

\[\det(M)=1\cdot4-2\cdot3=4-6=-2.\]

Dưới modulo $26$ ta có $-2\equiv 24\pmod{26}$. Tính $\gcd(24,26)=2\ne1$. Do đó $\det(M)$ không có nghịch đảo modulo $26$ ⇒ $M$ không khả nghịch modulo $26$, nên không tồn tại $M^{-1}\pmod{26}$.

b) Tìm 2 bản rõ khác nhau mà cho cùng bản mã khi mã hóa bằng $M$.

Khi $M$ không khả nghịch mod 26, tồn tại vectơ không tầm $v\neq 0$ sao cho $Mv\equiv 0\pmod{26}$ (kernel không chỉ có vectơ 0). Nếu $P_1$ và $P_2$ là hai bản rõ khác nhau với $P_1-P_2=v$, thì $M P_1 \equiv M P_2$.

Tìm kernel: giải

\[M\begin{pmatrix}x \\ y\end{pmatrix} \equiv \begin{pmatrix}0 \\ 0\end{pmatrix} \pmod{26}\]

tức hệ

\[\begin{cases} x+2y\equiv0\pmod{26}, \\[4pt] 3x+4y\equiv0\pmod{26}. \end{cases}\]

Từ phương trình 1: $x\equiv -2y\equiv 24y\pmod{26}$. Thay vào 2:

\[3(24y)+4y = 76y \equiv 24y \equiv 0\pmod{26}.\]

Rút gọn: $24y\equiv 0\pmod{26}$ ⇒ $12y\equiv0\pmod{13}$ ⇒ $y\equiv0\pmod{13}$. Vậy $y=0$ hoặc $13$ (mod 26).

Nếu $y=13$ thì $x\equiv 24\cdot13\equiv 0\pmod{26}$. Do đó vectơ không tầm ta lấy được là

\[v=\begin{pmatrix}0 \\ 13\end{pmatrix}.\]

Chọn ví dụ hai bản rõ khác nhau:

• $P_1=(0,0)$ tương ứng “AA”,
• $P_2=(0,13)$ tương ứng “AN”.

Ta kiểm tra:

\[M P_2 = \begin{pmatrix}1&2 \\ 3&4\end{pmatrix}\begin{pmatrix}0 \\ 13\end{pmatrix} =\begin{pmatrix}26 \\ 52\end{pmatrix}\equiv\begin{pmatrix}0 \\ 0\end{pmatrix}\pmod{26},\]

vậy $M P_1 \equiv M P_2$.

Kết luận: “AA” và “AN” là hai bản rõ khác nhau nhưng cho cùng bản mã.

Bài 5

Cho \(M = \begin{pmatrix} 11 & 13 \\ 2 & 3 \end{pmatrix}\).

• a. Tìm $M^{-1} \pmod{26}$.
• b. Một bản rõ sau khi được mã hóa bởi M được bản mã YGFI. Tìm bản rõ đó.

Giải

a) Tìm $M^{-1}\pmod{26}$.

Tính định thức:

\[\det(M)=11\cdot3 - 13\cdot2 = 33 - 26 = 7.\]

Ta có $\gcd(7,26)=1$, nên ma trận khả nghịch modulo 26.

Tìm nghịch đảo của $\det(M)$ modulo 26: cần $d$ sao cho $7d\equiv1\pmod{26}$. Ta thấy $7\cdot15=105\equiv1\pmod{26}$ (vì $105-4\cdot26=1$). Vậy $7^{-1}\equiv15\pmod{26}$.

Ma trận phụ hợp (adjugate) của ma trận $2\times2$ là

\[\operatorname{adj}(M)=\begin{pmatrix}d & -b\\ -c & a\end{pmatrix} =\begin{pmatrix}3 & -13\\ -2 & 11\end{pmatrix}.\]

Chuyển sang modulo 26 (thay các số âm bằng đại diện trong $0,\dots,25$):

\[\operatorname{adj}(M)\equiv\begin{pmatrix}3 & 13\\ 24 & 11\end{pmatrix}\pmod{26}.\]

Vậy

\[M^{-1} \equiv 7^{-1}\cdot \operatorname{adj}(M) \equiv 15\cdot \begin{pmatrix}3 & 13\\ 24 & 11\end{pmatrix}\pmod{26}.\]

Nhân từng phần tử (mod 26):

\[\begin{aligned} 15\cdot3 &\equiv 45 \equiv 19\pmod{26},\\ 15\cdot13&\equiv 195\equiv 13\pmod{26},\\ 15\cdot24&\equiv 360\equiv 22\pmod{26},\\ 15\cdot11&\equiv 165\equiv 9\pmod{26}. \end{aligned}\]

Do đó

\[\boxed{M^{-1}\equiv\begin{pmatrix}19 & 13 \\[4pt] 22 & 9\end{pmatrix}\pmod{26} }.\]

(Thử kiểm tra: $M^{-1}M\equiv I\pmod{26}$ — bạn có thể nhân kiểm tra để xác nhận.)

b) Giải mã bản mã YGFI

Chia YGFI thành hai khối 2 ký tự: YG và FI.

Bảng A=0, B=1, …, Z=25:

• Y → $24$, G → $6$,
• F → $5$, I → $8$.

Ta giải từng khối với $P = M^{-1} C \pmod{26}$.

Khối 1: $C_1=\begin{pmatrix}24\6\end{pmatrix}$.

\[P_1 \equiv \begin{pmatrix}19&13 \\ 22&9\end{pmatrix}\begin{pmatrix}24 \\ 6\end{pmatrix} = \begin{pmatrix}19\cdot24+13\cdot6[4pt]22\cdot24+9\cdot6\end{pmatrix} = \begin{pmatrix}534\\ 582\end{pmatrix}.\]

Lấy modulo 26:

\[534\bmod26=14,\qquad 582\bmod26=10.\]

Vậy $P_1=(14,10)$ → ký tự $14\mapsto O$, $10\mapsto K$ ⇒ khối 1 = OK.

Khối 2: $C_2=\begin{pmatrix}5\8\end{pmatrix}$.

\[P_2 \equiv \begin{pmatrix}19&13 \\ 22&9\end{pmatrix}\begin{pmatrix}5 \\ 8\end{pmatrix} = \begin{pmatrix}199 \\ 182\end{pmatrix}.\]

Lấy modulo 26:

\[199\bmod26=17,\qquad 182\bmod26=0.\]

Vậy $P_2=(17,0)$ → ký tự $17\mapsto R$, $0\mapsto A$ ⇒ khối 2 = RA.

Kết luận: ghép hai khối lại, bản rõ là OKRA.

Lý thuyết chung

Cơ bản về phương trình đồng dư

🔸 1. Khái niệm cơ bản

Định nghĩa: Hai số nguyên $( a, b )$ được gọi là đồng dư modulo $( n )$ nếu chúng chia cho $( n )$ cùng dư.

Ký hiệu:

\[a \equiv b \pmod{n}\]

hay nói bằng lời: “$a$ đồng dư $b$ theo mod $n$”.

↪️ Nghĩa là $( n )$ chia hết cho $( a - b )$.

\[a \equiv b \pmod{n} \iff n \mid (a - b)\]

Ví dụ:

• $ ( 17 \equiv 2 \pmod{5} ) $ vì $ ( 17 - 2 = 15 ) $ chia hết cho 5.
• $ ( -8 \equiv 4 \pmod{12} ) $ vì $ ( -8 - 4 = -12 ) $ chia hết cho 12.

💡 Một số có thể có nhiều đại diện đồng dư: Ví dụ với mod 7, các số ( …, -4, 3, 10, 17, … ) đều ≡ 3 (mod 7).

🔸 2. Tính chất cơ bản

Nếu $( a \equiv b \pmod{n} )$ và $( c \equiv d \pmod{n} )$ thì:

• Cộng: $( a + c \equiv b + d \pmod{n} )$
• Trừ: $( a - c \equiv b - d \pmod{n} )$
• Nhân: $( a \cdot c \equiv b \cdot d \pmod{n} )$

Ngoài ra:

• Nếu $( a \equiv b \pmod{n} )$ thì $( a^k \equiv b^k \pmod{n} )$ với mọi $( k \in \mathbb{N} )$.

🔸 3. Nghịch đảo modulo

Định nghĩa:

Một số $( a )$ có nghịch đảo modulo $n$ nếu tồn tại $( a^{-1} )$ sao cho:

\[a \cdot a^{-1} \equiv 1 \pmod{n}\]

Điều kiện tồn tại:

Nghịch đảo của $( a )$ modulo $( n )$ chỉ tồn tại khi $( \gcd(a, n) = 1 )$

(nói cách khác: $a$ và $n$ nguyên tố cùng nhau).

Ví dụ:

• $( 3 \cdot 5 = 15 \equiv 1 \pmod{7} )$ ⟹ $( 5 )$ là nghịch đảo của 3 mod 7.
• $( 4 \cdot 2 = 8 \equiv 1 \pmod{7} )$ ⟹ $( 2 )$ là nghịch đảo của 4 mod 7.
• $( 6 )$ không có nghịch đảo mod 9 vì $( \gcd(6, 9) = 3 \ne 1 )$.

🔸 4. Phương trình đồng dư bậc nhất

Phương trình dạng:

\[a x \equiv b \pmod{n}\]

Cách giải (đơn giản nhất):

1. Nếu $( \gcd(a, n) = 1 )$, nhân hai vế với nghịch đảo của $( a )$:

   \[x \equiv a^{-1} \cdot b \pmod{n}\]

2. Nếu $( \gcd(a, n) = d > 1 )$:

   • Chỉ có nghiệm nếu $( d \mid b )$.
   • Khi đó chia cả hai vế cho $( d )$ rồi giải tiếp.

Ví dụ:

\[3x \equiv 1 \pmod{7} \Rightarrow x \equiv 5\]

vì $( 3 \cdot 5 = 15 \equiv 1 \pmod{7} )$.

🔸 5. Phương trình đồng dư bậc hai (dạng cơ bản)

Phương trình dạng:

\[x^2 \equiv a \pmod{n}\]

Hiện tại, ta chỉ cần biết cách thử nghiệm:

Ví dụ:

Tìm $( x )$ sao cho $( x^2 \equiv 4 \pmod{7} )$

Thử tất cả giá trị từ 0 đến 6:

\[\begin{aligned} 0^2 &\equiv 0 \\ 1^2 &\equiv 1 \\ 2^2 &\equiv 4 \\ 3^2 &\equiv 2 \\ 4^2 &\equiv 2 \\ 5^2 &\equiv 4 \\ 6^2 &\equiv 1 \end{aligned}\]

⟹ $( x \equiv 2 )$ hoặc $( x \equiv 5 )$ (mod 7).

🔸 6. Ghi nhớ nhanh

Phương pháp Euclid

🔸 1. Mục đích

Dùng để tìm:

• Ước chung lớn nhất (gcd) của hai số nguyên $(a, b)$.
• Nghịch đảo modulo, khi $(\gcd(a, n) = 1)$.

🔸 2. Thuật toán Euclid cơ bản

Nguyên lý:

Nếu chia $a$ cho $b$ được thương $q$ và dư $r$, thì:

\[a = bq + r\]

và ta có:

\[\gcd(a, b) = \gcd(b, r)\]

Lặp lại cho đến khi $r = 0$. Khi đó, ước chung lớn nhất chính là số chia cuối cùng khác 0.

Ví dụ:

\[\begin{aligned} 30 &= 2 \times 12 + 6 \\ 12 &= 2 \times 6 + 0 \end{aligned}\]

⟹ $\gcd(30, 12) = 6$

🔸 3. Thuật toán Euclid mở rộng

Mục tiêu: Tìm các hệ số $(x, y)$ thỏa mãn:

\[a x + b y = \gcd(a, b)\]

Khi $\gcd(a, b) = 1$, ta có thể tìm được nghịch đảo của $a$ theo mod $b$ (hoặc ngược lại).

🔸 4. Cách làm (phiên bản tay cơ bản)

1. Dùng Euclid thường để tìm các phép chia:

   \[a = q_1 b + r_1 \\ b = q_2 r_1 + r_2 \\ r_1 = q_3 r_2 + r_3 \dots\]

2. Dừng khi $r_k = 0$. Khi đó, $\gcd(a, b) = r_{k-1}$.

3. Thay ngược lại từ các dòng trên để biểu diễn $\gcd(a, b)$ theo $a$ và $b$.

🔸 5. Ví dụ minh họa

Tìm $\gcd(43, 17)$ và nghịch đảo của $17$ theo mod $43$.

Bước 1 – Euclid thường:

\[\begin{aligned} 43 &= 2 \times 17 + 9 \\ 17 &= 1 \times 9 + 8 \\ 9 &= 1 \times 8 + 1 \\ 8 &= 8 \times 1 + 0 \end{aligned}\]

⟹ $\gcd(43,17) = 1$

Bước 2 – Đi ngược lại:

\[\begin{aligned} 1 &= 9 - 1\times8 \\ &= 9 - 1\times(17 - 1\times9) = 2\times9 - 1\times17 \\ &= 2\times(43 - 2\times17) - 1\times17 \\ &= 2\times43 - 5\times17 \end{aligned}\]

⟹ $1 = 2(43) - 5(17)$ ⟹ $(-5)$ là nghịch đảo của $17$ mod $43$ ⟹ $17^{-1} \equiv 38 \pmod{43}$

Kiểm tra:

\[17 \times 38 = 646 \equiv 1 \pmod{43}\]

✅ Đúng!

🔸 6. Ghi nhớ nhanh

Số nguyên tố – Phi Euler – Lũy thừa mod – Định lý Fermat & Euler

🔸 1. Số nguyên tố

Định nghĩa:

Một số nguyên $( p > 1 )$ được gọi là nguyên tố nếu nó chỉ có hai ước dương là $( 1 )$ và $( p )$ chính nó.

Ví dụ: $( 2, 3, 5, 7, 11, 13, 17, 19, \dots )$

Ngược lại, các số như $( 4, 6, 8, 9, 10 )$ là hợp số (composite), vì có thêm ước khác $( 1 )$ và chính nó.

Tính chất quan trọng:

Khi $( p )$ là số nguyên tố, mọi số $( a )$ với $( 1 \le a < p )$ đều nguyên tố cùng nhau với $( p )$ (vì $( \gcd(a, p) = 1 )$).

💡 Hệ quả:

Trong modulo nguyên tố $( p )$, mọi phần tử $( a \in {1, 2, \dots, p-1} )$ đều có nghịch đảo modulo $( p )$.

🔸 2. Hàm Phi Euler

Định nghĩa:

Hàm $( \varphi(n) )$ đếm số lượng các số nguyên dương ≤ n mà nguyên tố cùng nhau với $( n )$.

\[\varphi(n) = |{1 \le a \le n \mid \gcd(a, n) = 1}|\]

Ví dụ:

Một số công thức cơ bản:

• Nếu (p) là nguyên tố:

  \[\varphi(p) = p - 1\]

• Nếu $(n = p^k)$:

  \[\varphi(p^k) = p^k - p^{k-1} = p^k(1 - \tfrac{1}{p})\]

• Nếu $(n = p_1^{a_1} p_2^{a_2} \dots p_r^{a_r})$:

  \[\varphi(n) = n\left(1 - \tfrac{1}{p_1}\right)\left(1 - \tfrac{1}{p_2}\right)\dots\left(1 - \tfrac{1}{p_r}\right)\]

Liên hệ:

$(\varphi(n))$ chính là số lượng phần tử có nghịch đảo modulo $(n)$.

🔸 3. Lũy thừa modulo

Định nghĩa:

\[a^b \pmod{n}\]

là phần dư khi chia $(a^b)$ cho $(n)$.

Để tránh số quá lớn, ta luôn rút gọn từng bước:

Ví dụ:

\[3^5 \pmod{7} \\ 3^2 = 9 \equiv 2 \pmod{7} \\ 3^4 = (3^2)^2 \equiv 2^2 = 4 \pmod{7} \\ 3^5 = 3^4 \cdot 3 \equiv 4 \cdot 3 = 12 \equiv 5 \pmod{7}\]

⟹ $( 3^5 \equiv 5 \pmod{7} )$

🔸 4. Định lý Fermat nhỏ

Nếu $(p)$ là số nguyên tố, và $(a)$ không chia hết cho $(p)$, thì:

\[a^{p-1} \equiv 1 \pmod{p}\]

Ví dụ:

\[p = 7,\ a = 3 \Rightarrow 3^6 = 729 \equiv 1 \pmod{7}\]

🔸 5. Định lý Euler (phiên bản tổng quát)

Nếu $( \gcd(a, n) = 1 )$, thì:

\[a^{\varphi(n)} \equiv 1 \pmod{n}\]

Đây là mở rộng của Fermat nhỏ, vì khi $(n = p)$ nguyên tố, ta có $(\varphi(p) = p-1)$.

Ví dụ:

\[n = 10,\ \varphi(10) = 4,\ a = 3 3^4 = 81 \equiv 1 \pmod{10}\]

🔸 6. Ứng dụng thực tế

• Dùng để rút gọn lũy thừa cực lớn trong RSA, Diffie–Hellman, chữ ký số.
• Ví dụ:

  \[7^{222} \pmod{13}\]

  Vì $(13)$ là nguyên tố, nên $(7^{12} \equiv 1 \pmod{13})$.

  Viết lại:

  \[7^{222} = 7^{12\cdot18 + 6} = (7^{12})^{18} \cdot 7^6 \equiv 1^{18} \cdot 7^6 \equiv 7^6 \pmod{13}\]

  Ta chỉ cần tính $(7^6 \pmod{13})$.

🔸 7. Ghi nhớ nhanh

Logarit rời rạc

🔸 1. Mục đích

Dùng để giải phương trình dạng mũ trong modulo, tức là tìm số mũ $x$ thỏa:

\[a^x \equiv b \pmod{n}\]

Nếu phép nhân mod n tạo thành “nhóm kín” (ví dụ mod nguyên tố), thì luôn có thể tìm (ít nhất lý thuyết là vậy) một $x$ như thế.

🔸 2. Ý tưởng

Trong số học thông thường (với số thực), logarit là phép “ngược lại” của lũy thừa:

$a^x = b \Rightarrow x = \log_a b$

Nhưng trong modulo, ta không thể chia hay lấy log như bình thường — vì phép nhân mod n không còn tuyến tính nữa.

Ta gọi $x$ thỏa $a^x \equiv b \pmod{n}$ là logarit rời rạc của b theo cơ số a modulo n.

🔸 3. Ví dụ cơ bản

Tìm $x$ sao cho:

$3^x \equiv 4 \pmod{7}$

Ta thử từng giá trị nhỏ của x:

⟹ $x = 4$ là nghiệm. Ta nói “log cơ số 3 của 4 mod 7 bằng 4” ⟹ $\log_3 4 \equiv 4 \pmod{6}$.

🔸 4. Tính chất quan trọng

Nếu $a$ là phần tử sinh của modulo (tức là sinh ra mọi phần dư khác 0), thì với mọi $b$, tồn tại duy nhất một $x$ thỏa mãn $a^x \equiv b \pmod{p}$.

Điều này chỉ đúng khi:

• $p$ là số nguyên tố, và
• $a$ là phần tử sinh (primitive root) mod p.

🔸 5. Ứng dụng

Rất quan trọng trong:

• Diffie–Hellman key exchange
• ElGamal encryption
• DSA, ECDSA (phiên bản elliptic curve)

→ Bảo mật dựa trên giả định:

“khó tính logarit rời rạc hơn là tính lũy thừa modulo”.

Tức là: Dễ để tính $a^x \bmod p$, nhưng cực khó để ngược lại tìm $x$.

🔸 6. Ghi nhớ nhanh

Mã Caesar

🔸 1. Ý tưởng

Là mã thay thế đơn giản nhất, mỗi ký tự trong bản rõ được dịch đi k vị trí trong bảng chữ cái.

\[C = (P + k) \bmod 26\]

Ngược lại, giải mã bằng:

\[P = (C - k) \bmod 26\]

🔸 2. Ví dụ

Giả sử $k = 3$ Bản rõ: ATTACK

Chuyển đổi sang số (A=0, B=1, …, Z=25):

$P = [0, 19, 19, 0, 2, 10]$

Mã hóa:

$C = (P + 3) \bmod 26 = [3, 22, 22, 3, 5, 13]$

⟹ Bản mã: DWWDFN

🔸 3. Nhận xét

• Cực kỳ dễ phá bằng phân tích tần suất.
• Có đúng 25 khóa khả dĩ.

Mã Vigenère

🔸 1. Ý tưởng

Là mở rộng của Caesar, dùng một từ khóa lặp lại để dịch từng ký tự khác nhau.

\[C_i = (P_i + K_i) \bmod 26\]

Với $K_i$ là giá trị của ký tự khóa tương ứng.

🔸 2. Ví dụ

Bản rõ: HELLO

Khóa: KEY (lặp thành KEYKE)

⟹ Bản mã: RIJVS

🔸 3. Nhận xét

• Mạnh hơn Caesar, nhưng vẫn dễ bị phá bằng Kasiski test khi biết độ dài khóa.

Mã khối (Block Cipher)

🔸 1. Ý tưởng

Mã hóa theo từng khối cố định (ví dụ 64 hoặc 128 bit), mỗi khối được biến đổi bằng nhiều vòng hoán vị và thay thế.

Công thức tổng quát:

\[C = E_K(P)\]

\[P = D_K(C)\]

Với $E_K$ là hàm mã hóa, $D_K$ là giải mã cùng khóa $K$.

🔸 2. Ví dụ minh họa (giả lập)

Giả sử ta có khối 4-bit, và khóa là phép XOR với $K = 1010$:

$P = 1100$

$C = P \oplus K = 0110$

⟹ Giải mã ngược lại cũng dùng XOR:

$P = C \oplus K = 1100$

🔸 3. Ứng dụng

Các thuật toán phổ biến:

• DES, AES
• Là nền tảng cho hầu hết hệ mã hiện đại (VPN, TLS, Disk encryption)

Mã Hill

🔸 1. Ý tưởng

Dùng đại số tuyến tính trên modulo 26. Mỗi nhóm ký tự được xem như một vector, nhân với ma trận khóa để mã hóa.

\[C = K \cdot P \bmod 26\]

\[P = K^{-1} \cdot C \bmod 26\]

🔸 2. Ví dụ

Chọn ma trận khóa \(K = \begin{bmatrix} 3 & 3 \\ 2 & 5 \end{bmatrix}\)

và bản rõ “HI” → $P = [7, 8]^T$

Tính:

\[C = \begin{bmatrix} 3 & 3 \\ 2 & 5 \end{bmatrix} \cdot \begin{bmatrix} 7 \\ 8 \end{bmatrix} \bmod 26\]

\[\begin{bmatrix} 45 \\ 54 \end{bmatrix} \bmod 26 = \begin{bmatrix} 19 \\ 2 \end{bmatrix}\]

⟹ Bản mã: TC

🔸 3. Lưu ý

• Ma trận khóa phải khả nghịch mod 26 (determinant và 26 phải nguyên tố cùng nhau).

Mã RSA

🔸 1. Ý tưởng

Dựa trên khó khăn của việc phân tích thừa số của số lớn. Sử dụng hai khóa khác nhau: công khai $(e, n)$ và bí mật $(d, n)$.

\[C = P^e \bmod n\]

\[P = C^d \bmod n\]

🔸 2. Ví dụ

Chọn $p=3$, $q=11$ ⟹ $n = 33$, $\varphi(n) = 20$

Chọn $e = 3$, tìm $d$ sao cho $3d \equiv 1 \pmod{20}$ ⟹ $d = 7$

Mã hóa $P = 4$:

$C = 4^3 \bmod 33 = 64 \bmod 33 = 31$

Giải mã:

$P = 31^7 \bmod 33 = 4$

⟹ Khớp lại.

🔸 3. Ghi nhớ

• $n = pq$, hai số nguyên tố lớn
• $e$ công khai, $d$ bí mật
• An toàn dựa trên khó phân tích n thành p, q

Mã Diffie–Hellman

🔸 1. Ý tưởng

Là giao thức trao đổi khóa: hai bên có thể cùng tạo ra khóa chung mà không truyền trực tiếp khóa đó.

Công thức:

\[A = g^a \bmod p\]

\[B = g^b \bmod p\]

\[K = B^a \equiv A^b \equiv g^{ab} \pmod{p}\]

🔸 2. Ví dụ

Chọn $p = 23$, $g = 5$ Alice chọn $a = 6$ ⟹ $A = 5^6 \bmod 23 = 8$ Bob chọn $b = 15$ ⟹ $B = 5^{15} \bmod 23 = 19$

Khóa chung:

$K = B^a \bmod 23 = 19^6 \bmod 23 = 2$

$K = A^b \bmod 23 = 8^{15} \bmod 23 = 2$

⟹ Khớp.

🔸 3. Bảo mật

Dựa trên vấn đề logarit rời rạc khó tính.

Mã ElGamal

🔸 1. Ý tưởng

Là hệ mã khóa công khai dựa trên Diffie–Hellman. Khóa công khai gồm $(p, g, y=g^x \bmod p)$, khóa bí mật là $x$.

Mã hóa:

\(C_1 = g^k \bmod p\) \(C_2 = M \cdot y^k \bmod p\)

Giải mã:

\[M = C_2 \cdot (C_1^x)^{-1} \bmod p\]

🔸 2. Ví dụ

Chọn $p = 23$, $g = 5$, $x = 6$ ⟹ $y = 5^6 \bmod 23 = 8$

Mã hóa $M = 10$, chọn $k = 15$:

$C_1 = 5^{15} \bmod 23 = 19$

$C_2 = 10 \cdot 8^{15} \bmod 23 = 10 \cdot 2 \bmod 23 = 20$

⟹ Bản mã $(19, 20)$

Giải mã:

$M = 20 \cdot (19^6)^{-1} \bmod 23$

Tính $19^6 \bmod 23 = 2$ ⟹ nghịch đảo của 2 mod 23 là 12

$M = 20 \cdot 12 \bmod 23 = 240 \bmod 23 = 10$

⟹ Khôi phục thành công.

🔸 3. Ghi nhớ

• Dựa trên cùng nguyên lý Diffie–Hellman.
• Dạng mã hóa ngẫu nhiên — cùng bản rõ, khóa khác → bản mã khác nhau.