Đã đăng vào thg 7 24, 2:00 SA 5 phút đọc

[Cryptography p4] Những kiến thức toán học cơ bản cần thiết trong mật mã học

Bài viết được lấy từ https://truongphuoc.wordpress.com/2023/03/07/blockchain-17-nhung-kien-thuc-toan-hoc-can-thiet-trong-rsa-va-elliptic-curve-cryptography/

Hi, xin 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. Trong bài viết này đáng lẽ mình sẽ viết về thuật toán mã hóa RSA, một thuật toán thuộc hệ bất đối xứng, bài viết sau là về Elliptic curve cryptography. Nhưng thấy rằng để hiểu rõ hai thuật toán bất đối xứng phổ biến này, chúng ta phải biết một chút về các kiến thức toán học liên quan đến nó.

Những kiến thức toán học liên quan tới RSA và Elliptic curve cryptography cũng không khó lắm, các bạn đã được học ở cấp 2 và cấp 3 rồi, mình chỉ ôn lại một chút cho các bạn nhớ lại thôi.

Note: những kiến thức toán học này không quá khó, các bạn đừng bỏ qua bài này mà sang luôn bài RSA và Elliptic curve nha.

Số nguyên tố

Nhắc đến số nguyên tố thì chắc hẳn ai cũng biết rồi. Số nguyên tố là số tự nhiên lớn hơn 1, có tính chất là chỉ chia hết cho 1 và chính nó. Ví dụ số 5 là số nguyên tố vì 5 chỉ chia hết cho 1 và 5. Số 6 không phải là số nguyên tố và ngoài chia hết cho 1 và 6 ra, 6 còn chia hết cho 2 và 3.

Ví dụ dãy các số nguyên tố: 3, 5, 7, 11, 13, ...

Ước chung lớn nhất

Ước chung lớn nhất của hai hay nhiều số nguyên là số lớn nhất trong các ước số chung của các số đó. Ví dụ ước chung lớn nhất của 6 và 15 là 3 vì $\frac{6}{3} = 2$ và $\frac{15}{3}=5$ . Ta ký hiệu $gcd(6, 15) = 3$ . Để tìm ước chung lớn nhất của hai số ta có thể sử dụng thuật toán Euclide.

Thuật toán Euclide

Thuật toán Euclide dựa trên định lý sau: Cho hai số nguyên $a >= 0$ và $b > 0$ , ta có:

$gcd(a, b) = gcd(a, b - a)$ . Ví dụ muốn tìm ước chúng lớn nhất của 45 và 110

  gcd(45, 110) = gcd(45, 110 - 45)  // trừ 45 lần 1
= gcd(45, 65)  = gcd(45, 65 - 45)   // trừ 45 lần 2
= gcd(45, 20)  = gcd(45 - 20, 20)   // trừ 20 lần 1
= gcd(25, 20)  = gcd(25 - 20, 20)   // trừ 20 lần 2
= gcd(5, 20)   = gcd(5, 20 - 5)     // trừ 5 lần 1
= gcd(5, 15)   = gcd(5, 15 - 5)     // trừ 5 lần 2
= gcd(5, 10)   = gcd(5, 10 - 5)     // trừ 5 lần 3
= gcd(5, 5)    = gcd(5, 5 - 5)      // trừ 5 lần 4
= 5

Vậy $gcd(45, 110) = 5$ . Làm như trên có vẻ hơi dài đúng không, ta trừ 45 là 2 lần, trừ 20 là 2 lần và trừ 5 là 4 lần. Thay vì trừ từng phép toán nhứ thế ta có thể trừ một lúc luôn (trừ 245, 220 và 4*5). Ta có thể viết ngắn gọn như sau

  gcd(45, 110) = gcd(45, 110 - 45*2)  // 45 * 2 = 90 < 110, 45 * 3 = 135 > 110 nên không thể chọn 3
= gcd(45, 20)  = gcd(45 - 20*2, 20)   // 20*2 = 40
= gcd(5, 20)   = gcd(5, 20 - 5*4)     // 5*4 = 20
= gcd(5,0)
= 5

Hay có thể làm nhanh hơn (Không cần quan tâm đến các số 2, 2, 4 để nhân như trên)
  gcd(45, 110) = gcd(45, 110 mod 45)
= gcd(45, 20)  = gcd(45 mod 20, 20)
= gcd(5, 20)   = gcd(5, 20 mod 5)
= gcd(5, 0)
= 5
Phép mod chúng ta nghiên cứu bên dưới nhé.

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à hai số nguyên tố cùng nhau, vì $gcd(5, 7) = 1$ . 6 và 27 không phải là nguyên tố cùng nhau, vì ước chung lớn nhất của 6 và 27 là 3.

Các bạn chú ý tên có vẻ gây hiểu lầm: Nguyên tố cùng nhau không nhất thiết hai số phải là số nguyên tố nhé.

Phép $div$ và $mod$

Cho a là số nguyên và n là số nguyên dương, khi đó tồn tại q và r duy nhất sao cho $a = nq + r$ với $0 <= r < n$ .

Phép chia này thì đơn giản rồi, ví dụ $a = 10$ và $q = 5$ thì $10 = 2*5 + 0, a = 12$ và $q = 5$ thì $12 = 2*5 + 2$ .

Trong phép chia số nguyên $a = nq + r$ ở trên, $div$ và $mod$ là các ký hiệu để biểu diễn cho $q$ và $r$ .

a div n = q
a mod n = r

Ví dụ

Nhắc lại công thức: a = nq + r

Tìm 11 div 3 và 11 mod 3
11 = 3*3 + 2
=>  11 div 3 = 3
=>  11 mod 3 = 2

Tìm -11 div 3 và 11 mod 3
-11 = 4*(-3) + 1
=> -11 div 3 = -3
=> -11 div 3 = 1

Tại sao không phân tích -11 = 3*(-3) + (-2)?
Tại vì nếu sử dụng cách trên thì r = -2, trong khi theo định nghĩa phép chia số nguyên 0<= r < n, nên r = -2 không đúng.

Ta có thể tính -11 mod 3 nhanh như sau: -11 mod 3 = 3 - (11 mod 3) = 3 - 2 = 1

Đồng dư

Cho n là một số nguyên, $n > 1$ . Hai số $a$ và $b$ được gọi là đồng dư $modulo\; n$ nếu $a$ và $b$ có cùng số dư khi chia $n$ . Tức là $a\; mod\; n = b\; mod \;n$ . Ta ký hiệu như sau: $a ≡ b (mod\; n)$ - Đọc là a đồng dư với b modulo n.

Ví dụ $6 ≡ 9 (mod\; 3)$ vì 6 chia 3 dư 0, và 9 chia 3 cũng dư 0.

Phép mod với phân số

Ta đã tính được phép mod với số nguyên rồi, còn với phân số thì sao $\frac{a}{b}\; mod\; n = ?$ Ví dụ muốn tính $\frac{2}{7} \;mod\; 19$ thì làm cách nào?

2/7 mod 19 = ?
Ta đặt 2/7 mod 19 = x
=> 7x ≡ 2(mod 19)   // Nhân 2 vế với 7
Vì 2 mod 19 = 2 nên ta cần tìm x sao cho 7x mod 19 = 2 (1)
x từ 0 đến 18
Để tìm x ta thay từng phần từ vào (1):
x = 0 => 7*0 mod 19 = 0     != 2 (!= là không bằng)
x = 1 => 7*1 mod 19 = 7     != 2
x = 2 => 7*2 mod 19 = 14    != 2
x = 3 => 7*3 mod 19 = 2      = 2 => là giá trị cần tìm
Do đó 2/7 mod 19 = 3

Chú ý: a/b mod n có thể không có nghiệm nhé.

Bài toán logarit rời rạc

Logarit rời rạc được định nghĩa là số nguyên 𝑥 thỏa mãn phương trình: $𝑎^𝑥 ≡ 𝑏 \;(mod\; 𝑚)$ với $𝑎, 𝑏, 𝑚$ cho trước.

Ví dụ: Biết $3^x ≡ 13 \;(mod \;17)$ hãy tìm x.

Logarit rời rạc không phải lúc nào cũng tồn tại. Ví dụ: không tồn tại $𝑥$ sao cho:
$2^𝑥 ≡ 3\; (mod\; 7)$ và cũng không có điều kiện cụ thể để xác định xem $𝑥$ tồn tại không.

Cách giải: Bài toán logarit rời rạc là một bài toán khó, hiện chưa có cách giải hiệu quả, nó được áp dụng cho mật mã học (đọc tiếp RSA và DH để biết thêm).

Căn nguyên thủy

Cho một số nguyên tố $p$ và một số nguyên $g$ , $g$ là căn nguyên thủy của $p$ nếu:

$\{g^1\;mod \;p, g^2\;mod\; p,...,g^{p-1}\;mod\; p\}$

tạo thành một tập hợp chứa tất cả các số từ $1$ đến $p-1$ (không lặp lại).

Cũng dễ hiểu phải không nào, lấy ví dụ nhé: ví dụ $p = 7$ là một số nguyên tố, cũng xem $g =3$ có phải là căn nguyên thủy của $7$ không

$3^1\; mod\; 7 = 3$
$3^2\; mod\; 7 = 9 \;mod\; 7 = 2$
$3^3\; mod \;7 = 27 \;mod\; 7 = 6$
$3^4\; mod\; 7 = 81\; mod\; 7 = 4$
$3^5\; mod\; 7 = 243\; mod\; 7 = 5$
$3^6 mod\; 7 = 729\; mod \;7 = 1$

Kết quả các lũy thừa của $3\; modulo\; 7$ là: $3,2,6,4,5,1$ .

Tập hợp các kết quả này bao gồm tất cả các số từ $1$ đến $6$ mà không có số nào lặp lại, do đó $3$ là căn nguyên thủy của $7$ .

Phù thế là xong phần kiến thức cơ bản rồi, cũng không khó lắm phải không mọi người. Trong phần tiếp theo mình sẽ trình bày về một thuật toán mã hóa rất nổi tiếng: RSA.

Link bài viết gốc: https://truongphuoc.wordpress.com/2023/03/07/blockchain-17-nhung-kien-thuc-toan-hoc-can-thiet-trong-rsa-va-elliptic-curve-cryptography/