Giới thiệu
Chào các bạn, trong bài viết trước, mình đã giới thiệu về hệ mật bất đối xứng. Tiếp theo, mình sẽ đi sâu vào hai thuật toán mã hóa nổi tiếng: RSA và Elliptic Curve Cryptography. Tuy nhiên, để hiểu rõ hơn về hai thuật toán này, chúng ta cần bắt đầu từ những kiến thức toán học cơ bản.
Lưu ý: Những kiến thức toán học này đã được học trong chương trình cấp 2 và cấp 3, vì vậy hãy cố gắng nhớ lại và không bỏ qua nhé!
1. Số Nguyên Tố
Số nguyên tố là những số tự nhiên lớn hơn 1, chỉ chia hết cho 1 và chính nó. Ví dụ, số 5 là số nguyên tố vì chỉ chia hết cho 1 và 5, trong khi số 6 không phải là số nguyên tố vì ngoài 1 và 6, nó còn chia hết cho 2 và 3. Dưới đây là một số số nguyên tố: 3, 5, 7, 11, 13.
2. Ước Chung Lớn Nhất (GCD)
Ước chung lớn nhất của hai số nguyên là số lớn nhất trong các ước số chung của chúng. Ví dụ, ước chung lớn nhất của 6 và 15 là 3, ký hiệu là gcd(6, 15) = 3. Chúng ta có thể tìm gcd bằng thuật toán Euclide.
3. Thuật Toán Euclide
Thuật toán Euclide được dựa trên định lý sau:
gcd(a, b) = gcd(a, b - a).
Chúng ta có thể sử dụng thuật toán này để tìm ước chung lớn nhất của hai số.
Ví dụ: Tìm gcd(45, 110):
gcd(45, 110) = gcd(45, 110 - 45)
= gcd(45, 65)
= gcd(45, 65 - 45)
= gcd(45, 20)
= gcd(45 - 20, 20)
= gcd(25, 20)
= gcd(25 - 20, 20)
= gcd(5, 20)
= gcd(5, 20 - 5)
= gcd(5, 15)
= gcd(5, 15 - 5)
= gcd(5, 10)
= gcd(5, 10 - 5)
= gcd(5, 5)
= gcd(5, 5 - 5)
= 5Vậy nên
gcd(45, 110) = 5.
4. Số Nguyên Tố Cùng Nhau
Hai số được gọi là nguyên tố cùng nhau nếu ước chung lớn nhất của chúng bằng 1. Ví dụ, 5 và 7 là số nguyên tố cùng nhau vì gcd(5, 7) = 1. Ngược lại, 6 và 27 không phải là nguyên tố cùng nhau vì gcd(6, 27) = 3.
5. Phép Chia và Phép Mod
Cho a là số nguyên và n là số nguyên dương, chúng ta có thể biểu diễn phép chia như sau:
a = nq + r với 0 <= r < n.
Ví dụ:
Nếu a = 10 thì:
- 10 div 3 = 3 và 10 mod 3 = 1
- -11 div 3 = -4 và -11 mod 3 = 1
6. Đồng Dư
Hai số a và b được gọi là đồng dư modulo n nếu a mod n = b mod n. Chúng ta ký hiệu: a ≡ b (mod n).
Ví dụ: 6 ≡ 9 (mod 3) vì cả hai đều chia được cho 3 dư 0.
7. Phép Mod Với Phân Số
Để tính a/b mod n, chúng ta có thể biến đổi thành 7x ≡ 2 (mod 19). Thực hiện thử các giá trị x sẽ giúp tìm ra nghiệm.
8. Bài Toán Logarit Rời Rạc
Logarit rời rạc là số nguyên x thỏa mãn phương trình: a^x ≡ b (mod m). Đây là một bài toán khó không dễ giải và rất quan trọng trong mật mã học.
9. Căn Nguyên Thủy
Nếu p là số nguyên tố và g là căn nguyên thủy của p, thì tập hợp {g^1 mod p, g^2 mod p, ..., g^{p-1} mod p} sẽ chứa tất cả các số từ 1 đến p-1 mà không lặp lại.
Kết Luận
Trên đây là những kiến thức toán học cơ bản cần thiết để hiểu rõ hơn về mật mã học, đặc biệt là các thuật toán RSA và Elliptic Curve. Trong phần tiếp theo, mình sẽ đi sâu vào thuật toán mã hóa nổi tiếng RSA.
Xem thêm bài viết gốc tại đây.
source: viblo
