Hàm số Euler
Trong các hàm số số học, hàm số Euler được định nghĩa sau đây, có vai trò rất quan trọng trong toán học và tin học.
Hàm số Euler ϕ(n) được định nghĩa cho một số tự nhiên n khác không, và nó thể hiện số lượng các số tự nhiên dương không vượt quá n và nguyên tố cùng nhau với n Cụ thể, ϕ(n) = X.
Từ định nghĩa trên đây, ta có ngay hệ quả: i) ϕ(1) = 1 ii) Số tự nhiên p > 1 là số nguyên tố khi và chỉ khi ϕ(p) = p−1
1.1.2 Định nghĩa Hệ thặng dư đầy đủ modn là một tập hợp gồm n số nguyên đôi một không đồng dư với nhau theo modn.
1.1.3 Bổ đề Cho m, n là hai số nguyên dương, nguyên tố cùng nhau Khi đó, mỗi hàng trong bảng số sau đây là một hệ thặng dư đầy đủ modn:
Chứng minh Ta xét hàng thứ r tổng quát Với 0 ≤ x, y ≤ n−1, giả sử xm+r ≡ym+r ( modn) Khi đó từ giả thiếtm vàn nguyên tố cùng nhau, ta suy ra x ≡ y (modn)
Mỗi hàng trong bảng số trên bao gồm n số nguyên phân biệt, không đồng dư với nhau theo modulo n, tạo thành một hệ thặng dư đầy đủ modulo n.
1.1.4 Định lí Hàm số Euler ϕ(n) là hàm có tính chất nhân, nghĩa là với m và n là hai số nguyên dương nguyên tố cùng nhau, ta có: ϕ(mn) ϕ(m)ϕ(n).
Để chứng minh, ta sắp xếp tất cả các số nguyên dương không vượt quá tích mn thành bảng số Giả sử r là số nguyên dương không vượt quá m và (m, r) = d > 1, thì trong hàng thứ r không có số nào nguyên tố cùng nhau với mn Do đó, để tính giá trị ϕ(mn), ta chỉ cần xét các số trong hàng thứ r với (m, r) = 1, và tất cả các số này đều nguyên tố cùng nhau với m Theo Bổ đề 1.1.3, các số trong hàng này tạo thành một hệ thặng dư đầy đủ mod n, tức là có đúng ϕ(n) số nguyên tố cùng nhau với n Như vậy, trong mỗi hàng có ϕ(n) số nguyên tố cùng nhau với mn, và có ϕ(m) hàng như vậy Do đó, tổng số nguyên tố cùng nhau với mn trong bảng số là ϕ(m)ϕ(n), hay ϕ(mn) = ϕ(m)ϕ(n).
1.1.5 Bổ đề Nếu p là số nguyên tố và k là số nguyên dương thì ta có: ϕ p k = p k −p k−1 = p k
Chứng minh Theo định nghĩa hàm Euler ϕ(n), ta có ϕ(p k ) = P
Ta thấy rằng, các số nguyên dương không vượt quá p k và chia hết cho p phải có dạng sp, p ≤s ≤ p k−1 Do đó, có đúng p k−1 số như vậy Vì vậy, ta có ϕ p k = p k −p k−1 = p k
1.1.6 Công thức tính giá trị của hàm số Euler Giả sử số tự nhiên n >1 cú dạng phõn tớch tiờu chuẩn là n= p α 1 1 p α 2 2 ã ã ãp α k k Khi đú, ta cú cụng thức: ϕ(n) =n
Chứng minh Do hàm Euler có tính chất nhân, nên áp dụng Bổ đề 1.1.5, ta có ϕ(n) =ϕ(p α 1 1 p α 2 2 ã ã ãp α k k ) =ϕ(p α 1 1 )ϕ(p α 2 2 )ã ã ãϕ(p α k k )
Ta có công thức cần chứng minh.
Định lý Gauss cho số nguyên dương n phát biểu rằng n có thể được biểu diễn bằng công thức n = P d|n ϕ(d), trong đó tổng được tính cho mọi ước số tự nhiên d của n.
Chứng minh Thật vậy, nếu n= 1 thì công thức đúng Nếu n > 1 có dạng phân tích tiêu chuẩn n = p α 1 1 p α 2 2 p α k k , thì áp dụng tính chất nhân của hàm số Euler ta được
Hệ thức Gauss được chứng minh.
Ta xét các minh hoạ hệ thức Gauss bằng số cụ thể sau:
Định lý Euler và Định lý Fermat bé
Hệ thặng dư thu gọn mod n là tập hợp các số nguyên khác nhau, không đồng dư với nhau theo modulo n, và đồng thời có tính chất nguyên tố cùng nhau với n, với số lượng là ϕ(n).
Giả sử a là số nguyên và a cùng n là hai số nguyên tố cùng nhau Khi đó, nếu r1, , rϕ(n) là một hệ thặng dư thu gọn modulo n, thì các giá trị ar1, , arϕ(n) cũng tạo thành một hệ thặng dư thu gọn modulo n.
Chứng minh rằng với 1 ≤ i ≠ j ≤ n, nếu ar_i ≡ ar_j (mod n) và a, n nguyên tố cùng nhau, thì r_i ≡ r_j (mod n) dẫn đến mâu thuẫn với giả thiết rằng r_1, , r_ϕ(n) là hệ thặng dư thu gọn Do đó, mỗi số nguyên trong hệ ar_1, , ar_ϕ(n) đều không đồng dư với nhau theo mod n Bên cạnh đó, từ giả thiết a và n nguyên tố cùng nhau, ta cũng suy ra rằng (ar_i, n) = (r_i, n) = 1, điều này khẳng định rằng hệ ar_1, , ar_ϕ(n) là hệ thặng dư thu gọn mod n.
Kết quả sau đây là Định lý Euler [4,6].
1.2.3 Định lí Euler Giả sử a là một số nguyên và n là một số tự nhiên lớn hơn 1 Khi đó, nếu a và n nguyên tố cùng nhau thì a ϕ(n) ≡ 1 (modn).
Giả sử r1, , rϕ(n) là một hệ thặng dư thu gọn mod n, theo Định lý 1.2.2, hệ ar1, , arϕ(n) cũng là hệ thặng dư thu gọn mod n Mỗi thặng dư của hệ này đồng dư với một và chỉ một thặng dư của hệ kia theo mod n.
(ar1) (ar2)ã ã ã(arn) =r1r2ã ã ãrn(modn)
Do đó a ϕ(n) r 1 r 2 ã ã ãr n = r 1 r 2 ã ã ãr n (modn)
Vì mỗi thặng dư r i nguyên tố cùng nhau với n, nên giản ước hai vế cho r i ta có: a ϕ(n) ≡ 1 (modn)
Kết quả sau đây là Định lý Fermat bé [4,6].
1.2.4 Định lí Fermat bé Nếu p là số nguyên tố và a là số nguyên không chia hết cho p thì ta có a p−1 ≡ 1(modp).
Chứng minh Vìa không chia hết chopvà plà số nguyên tố nên(a, p) = 1. Áp dụng Định lí Euler ta có a ϕ(p) ≡1(modp)
Mặt khác, ta biết rằng ϕ(p) =p−1 , do đó a p−1 ≡1(modp)
Ta thu được điều cần chứng minh
Kết quả sau đây là một dạng phát biểu khác của Định lý Fermat.
1.2.5 Định lí Cho p là một số nguyên tố Khi đó, với mọi số nguyên a, ta có đồng dư thức a p ≡ a(modp).
Nếu a là bội của p, thì a ≡ 0(modp), dẫn đến a p ≡ 0(modp) Theo quan hệ bắc cầu, ta có a p ≡ a(modp) Ngược lại, nếu a không chia hết cho p, theo Định lý 1.2.4, ta có a p−1 ≡ 1(modp), từ đó, nhân hai vế của đồng dư thức này với a, ta suy ra a p ≡ a(modp).
Để xác định nghiệm của phương trình đồng dư bậc nhất ax ≡ b (mod m) với điều kiện a và m là nguyên tố cùng nhau và 1 < a < m, ta có thể vận dụng Định lý Euler Theo Định lý Euler, ta có a ϕ(m) ≡ 1 (mod m), từ đó giúp tìm ra nghiệm của phương trình.
Từ đó ta được a ϕ(m) b ≡ b(modm) hay a a ϕ(m)−1 b
Do đó x ≡a ϕ(m)−1 b(modm) là nghiệm của phương trình đồng dư đã cho.
Tính nghịch đảo của số nguyên a theo mod m liên quan đến phương trình đồng dư bậc nhất đặc biệt ax ≡ 1 (mod m), trong đó a và m là hai số nguyên tố cùng nhau và 1 < a < m Theo quy tắc, phương trình này có nghiệm duy nhất, được biểu diễn là x ≡ a ϕ(m)−1 (mod m) Do đó, nghịch đảo của số nguyên a theo mod m được xác định là a ϕ(m)−1.
Sử dụng Định lý Euler, ta có thể chứng minh Định lý phần dư Trung Hoa Định lý này khẳng định rằng, với các số nguyên dương m1, m2, , mn là các số nguyên tố cùng nhau, hệ phương trình đồng dư bậc nhất một ẩn sẽ có nghiệm duy nhất modulo tích của các số này.
x ≡ b n (modm n ) cú nghiệm duy nhất theo mụđun M = m1m2ã ã ãmn là x ≡b 1 M 1 y 1 + b 2 M 2 y 2 +ã ã ã+b n M n y n (modM) trong đó M 1 = m M
Chứng minh Để chứng minh định lý này, ta sẽ chỉ ra một nghiệm cụ thể.
Vì các số nguyên m 1 , m 2 , , m n nguyên tố cùng nhau từng đôi một nên bội chung nhỏ nhất của chúng là M = m 1 m 2 m n Đặt M 1 = m M
2,ã ã ã , M n = m M n rồi xác định các số nguyên y 1 , y 2 , , y n sao cho y 1 M 1 ≡ 1 (modm 1 ), y 2 M 2 ≡ 1 (modm 2 ), , y n M n ≡1 (modm n ).
Theo Định lý Euler, nếu (m1, M1) = (m2, M2) = = (mn, Mn) = 1, thì các số nguyên y1, y2, , yn được xác định duy nhất, khác nhau một bội của m1, m2, , mn tương ứng Từ đó, ta có Miyibi ≡ bi (mod mi) với i = 1, , n Đặt x0 = b1M1y1 + b2M2y2 + + bnMny n, ta có x0 ≡ bi (mod mi) cho mọi i từ 1 đến n.
Như vậy, hệ phương trình đồng dư
x ≡ b n (modm n ) có nghiệm duy nhất x ≡ b 1 M 1 y 1 +b 2 M 2 y 2 +ã ã ã+b n M n y n (modM). Định lý được chứng minh.
Trong Định lý phần dư Trung Hoa, các điều kiện yêu cầu m1, m2, , mn phải là các số nguyên dương và đôi một nguyên tố cùng nhau Tuy nhiên, nếu các số này không thỏa mãn điều kiện đôi một nguyên tố cùng nhau, thì kết quả của định lý sẽ bị ảnh hưởng như thế nào?
Kết quả sau là Định lý phần dư Trung Hoa mở rộng [4,6].
1.2.9 Định lớ Cho n số nguyờn dương m 1 , m 2 ,ã ã ã , m n và a 1 , a 2 , , a n là các số nguyên dương bất kì Khi đó hệ phương trình đồng dư tuyến tính
Phương trình x ≡ a n (mod m n ) có nghiệm nếu và chỉ nếu a i ≡ a j (mod(m i , m j )) với mọi i, j thỏa mãn 1 ≤ i < j ≤ n Định lý phần dư Trung Hoa có nhiều ứng dụng quan trọng trong các bài toán liên quan đến số nguyên lớn, đặc biệt trong hệ mã RSA.
1.2.10 Bổ đề Cho p >1 là một số nguyên tuỳ ý Khi đó, p là số nguyên tố khi và chỉ khi C p k ≡ 0 (modp),∀k = 1, , p−1.
Chứng minh Giả sử p > 1 là một số nguyên tố Khi đó
C p k = p(p−1)ã ã ã(p−k + 1) k! ,∀k = 1, , p−1 là một số nguyờn Do đú tử số p(p−1)ã ã ã(p−k + 1) là bội của mẫu sốk!
Vì p là số nguyên tố và với các giá trị nhận được của k ta có p và k! nguyên tố cựng nhau, do đú (p−1)ã ã ã(p−k+ 1) là bội của k! hay
(p−1)ã ã ã(p−k + 1) k! ,∀k = 1, , p−1 là số nguyên, hay C p k ≡ 0 (modp),∀k = 1, , p−1.
Nếu C_p_k ≡ 0 (mod p) với mọi k từ 1 đến p−1 và p là hợp số, thì p có ít nhất một ước nguyên tố q thỏa mãn 1 < q < p Khi đặt k = q, theo giả thiết chiều ngược lại của định lý, ta có C_p_q ≡ 0 (mod p).
Từ đồng dư thức, ta suy ra rằng (p−1)ããã(p−q+1) là bội của q!, và do đó (p−1)ããã(p−q+1) cũng là bội của q Vì q là số nguyên tố, nên tồn tại một thừa số (p−i), với 1 < i < q, là bội của q Tuy nhiên, vì q là ước của p, nên q cũng là ước của i, dẫn đến mâu thuẫn với điều kiện 1 < i < q.
1.2.11 Định lí Các Định lý Euler và Định lí Fermat bé là tương đương với nhau.
Chứng minh Trước hết ta chứng minh nhận xét sau:
Nhận xét Với mọi số nguyên tố p, nếu a ≡ b(modp k ) thì a p ≡ b p (mod p k+1 ) Thật vậy, từ a ≡ b(modp k ) ta có a = b+p k t, t∈ Z , từ đó a p = b+p k t p = b p + p−1
Lại do plà số nguyên tố cho nên theo Bổ đề 1.2.10 ta cóC p i là bội củapvới
∀i = 1, , p−1 Từ đó suy ra tổng p−1
C p i b i p k t i là một bội của p k+1, và p k t p = p kp t p cũng là một bội của p k+1, do đó a p ≡ b p (modp k+1) Từ Định lý Fermat bé, chúng ta có thể suy ra Định lý Euler Giả sử a ∈ Z và m ∈ N với (a, m) = 1, ta có thể viết m = p α 1 1 p α 2 2 p α k k dưới dạng phân tích tiêu chuẩn Theo Định lý Euler, ta có a p i −1 ≡ 1 (modp i ) cho mọi i = 1, 2, , k.
Do đó, theo nhận xét trên bằng cách luỹ thừa mũ p i liên tiếp hai vế của đồng dư thức này ta có a p i −1 p i ≡ 1 modp 2 i ,∀i = 1,2, , k a p i −1 p
Từ đồng dư thức cuối cùng ta thu được a p αi
Sử dụng công thức ϕ(p α i i ) = p α i i (pi −1),∀i = 1, , k , ta suy ra a ϕ ( p αi i ) ≡1 (modp α i i ),∀i = 1,2, , k (∗)
Vì hàm Euler có tính chất nhân, nên ϕ(m) =ϕ(p α 1 1 p α 2 2 p α k k ) =ϕ(p α 1 1 )ϕ(p α 2 2 ) ϕ(p α k k ), hay ϕ(m) là bội của ϕ(p α 1 1 ) Do đó, luỹ thừa hai vế đồng dư thức (∗) với số mũ ϕ(p α 1 1 ) ϕ p α i−1 i−1 ϕ p α i+1 i+1 ϕ(p α k k ) , ta có a ϕ ( p α 1 1 ) ϕ ( p α 2 2 ) ϕ ( p αk k ) = a ϕ(m) ≡1 (modp α i i ),∀i = 1, , k.
Theo tính chất của đồng dư thức ta thu được a ϕ(m) ≡ 1 (mod [p α i i , p α 2 2 , , p α k k ]).
Vì m = p α 1 1 p α 2 2 p α k k = [p α 1 1 , p α 2 2 , , p α k k ] là bội chung nhỏ nhất của các số nguyên p α i i , i = 1, , k , nên a ϕ(m) ≡ 1 (modm),∀i = 1, , k.
Tính toán đồng dư của những lũy thừa lớn
Định lý Euler cho phép tính số dư của luỹ thừa các số nguyên lớn trong các phép chia cụ thể.
Bài toán đặt ra là tính a^n theo mod m, trong đó n là một số nguyên lớn Để giải quyết, ta cần tìm số dư của a^n khi chia cho m Giả sử m = p_1^α1 * p_2^α2 * * p_k^αk, theo Định lý Euler, ta có a^ϕ(p_i^αi) ≡ 1 (mod p_i^αi) Nếu N là bội chung nhỏ nhất của các ϕ(p_i^αi), thì a^N ≡ 1 (mod m) Do đó, nếu n được viết dưới dạng n = Nq + r với r < N, ta có a^n ≡ a^r (mod m) Như vậy, bài toán tính a^n theo mod m được chuyển thành bài toán tính a^r theo mod m.
Ví dụ 1 Tìm số dư trong phép chia 2 1000000 cho 77.
Ta có ϕ(7) = 6; ϕ(11) = 10 ; 2 6 ≡1(mod7); 2 10 ≡ 1(mod11) Do đó,
Ví dụ 2 Tìm chữ số tận cùng của số 2 999 Ta có 2 999 ≡ 2 3 (mod2) Mặt khác, do (2,5) = 1 nên theo Định lý Euler ta có 2 ϕ(5) ≡ 1(mod5), hay
2 4 ≡1(mod5) Do đó 2 996 ≡ 1(mod5) và 2 999 ≡ 2 3 (mod5)
Từ đó 2 999 ≡ 2 3 (mod10) , hay số 2 999 có chữ số tận cùng là 2 3 = 8
Ví dụ 3 Tìm số dư trong phép chia 2002 2003 chia cho 19.
Ta có (7,19) = 1 , áp dụng Định lý Fermat với số nguyên tố p = 19 ta được 7 18 ≡1(mod19).
Ta có 7 3 = 343 ≡ 1(mod19) nên 7 5 ≡ 49(mod19) hay 7 5 ≡ 11(mod19).
Vậy số dư trong phép chia cho 2002 2003 chia cho 19 là 11.
1.3.2 Tính toán giá trị của hàm Euler bằng Maple Giá trị của hàm Euler tại số tự nhiên khác không n được tính bằng lệnh sau:
Ngược lại, ta cũng có thể tìm được những số tự nhiên n nhận một số a cho trước làm giá trị hàm Euler của nó, bằng lệnh
Công việc tính toán hàm Euler là rất phức tạp, khiến cho ngay cả máy tính cũng khó có thể xác định giá trị của hàm khi a đủ lớn trong khoảng thời gian chấp nhận được Hơn nữa, hàm Euler không phải là một hàm "toàn ánh", do đó không phải mọi giá trị a đều đảm bảo rằng hàm invphi() sẽ cho ra một tập hợp số xác định.
Để tính toán nghịch đảo của một số nguyên a theo mod n trong Maple, cần lưu ý rằng a và n phải là các số nguyên tố cùng nhau Theo Định lý Euler, quá trình tìm nghịch đảo này có thể thực hiện một cách hiệu quả.
Trước tiên ta kiểm tra tính nguyên tố cùng nhau của hai số a và n bằng lệnh tính ước chung lớn nhất của chúng:
Nếu chúng không nguyên tố cùng nhau (kết quả lệnh trên khác 1) thì ta kết luận không tồn tại nghịch đảo.
Ngược lại, ta tính nghịch đảo của a theo modn bằng việc tính a ϕ(n)−1 , thông qua lệnh:
Ví dụ Tính nghịch đảo của số 56341 theo modulo 13713471 qua các lệnh sau:
Số giả nguyên tố cơ sở 2
Một cách độc lập với Định lý bé Fermat, các nhà toán học Trung Quốc đã đưa ra một giả thuyết sau, thường gọi là Giả thuyết Trung Quốc.
1.4.1 Giả thuyết Trung Quốc Số nguyên p > 1 là một số nguyên tố khi và chỉ khi 2 p ≡ 2(modp)
Quả là, nếu p là số nguyên tố, thì 2 p ≡ 2( modp) vì đây là trường hợp đặc biệt của Định lý Fermat bé.
Song mệnh đề ngược lại nói rằng: Nếu 2 p ≡ 2(modp) thì p là số nguyên tố hay Giả thuyết Trung Quốc là sai Chẳng hạn,2 341 ≡ 2( mod 341), nhưng
341 = 11 × 31 là hợp số hay một ví dụ khác 2 561 ≡ 2(mod561) nhưng
Như vậy, mệnh đề ngược lại của Định lí Fermat bé không đúng.
Theo Định lý Fermat bé, nếu n là số nguyên tố và a là số nguyên tùy ý,thì a n ≡ a(modn)
Nếu n là một số tự nhiên lớn hơn 1 và tồn tại một số nguyên a sao cho đồng dư thức không xảy ra, thì n là hợp số Ngược lại, nếu đồng dư thức xảy ra, ta chưa thể xác định tính nguyên tố của n Tuy nhiên, nhiều thống kê cho thấy rằng nếu một số nguyên thỏa mãn kết luận của Định lý Fermat bé, thì khả năng nó là số nguyên tố là rất cao.
Từ đó, dẫn xuất đến khái niệm sau.
Số giả nguyên tố cơ sở 2 là một khái niệm trong lý thuyết số, được định nghĩa cho các số nguyên n lớn hơn 1 Nếu n là một hợp số và thỏa mãn điều kiện 2^n ≡ 2 (mod n), thì n được coi là số giả nguyên tố cơ sở 2.
Trong trường hợp gcd (2, n) = 1 hay n là số lẻ, ta dùng điều kiện tương đương sau: 2 n−1 ≡ 1(modn)
Ví dụ Số nguyên 561 là số giả nguyên tố cơ sở 2.
Thật vậy, ta có 561 = 3×11×17 là một hợp số và gcd (2,561) = 1 Vì gcd(3,561) = gcd(11,561) = gcd(17,561) = 1, nên áp dụng Định lý Euler, ta có
Luỹ thừa hai vế ba đồng dư thức trên ta thu được
Từ đó suy ra, 2 560 ≡ 1(mod3 × 11× 17), hay 2 560 ≡ 1(mod561) Vì vậy,
Số 561 là một số giả nguyên tố cơ sở 2, và tổng số giả nguyên tố thường ít hơn nhiều so với số nguyên tố Ví dụ, trong khoảng dưới 10^10, có 455052512 số nguyên tố nhưng chỉ có 14884 số giả nguyên tố cơ sở 2 Cụ thể, có 5 số nguyên tố nhỏ hơn 12 là 2, 3, 5, 7, 11, nhưng không có số giả nguyên tố cơ sở 2 nào trong khoảng này.
Sự kiện này chỉ ra rằng các số thỏa mãn Định lý Fermat bé có khả năng cao là số nguyên tố Tuy nhiên, đối với bất kỳ cơ sở nào, số lượng các số giả nguyên tố là vô hạn, và điều này có thể được chứng minh với cơ sở 2.
Nếu n là số giả nguyên tố cơ sở 2, thì m = 2^n - 1 cũng sẽ là số giả nguyên tố cơ sở 2 Điều này dẫn đến kết luận rằng có vô hạn số giả nguyên tố cơ sở 2.
Chứng minh rằng số 561 là một số giả nguyên tố cơ sở 2 Giả sử n là một số giả nguyên tố cơ sở 2, ta sẽ chỉ ra rằng số nguyên m = 2n - 1 lớn hơn n cũng là một số giả nguyên tố cơ sở 2.
Thật vậy, theo giả thiết, ta có nlà hợp số, chẳng hạn n = dt,1 < d, t < n.
Từ đó, ta có thể kết luận rằng m là một hợp số Bởi vì n là số giả nguyên tố cơ sở 2, nên ta có 2^n ≡ 2 (mod n), điều này có nghĩa là tồn tại một số tự nhiên k khác không sao cho 2^n - 2 = kn.
2 m−1 −1 = 2 kn −1 = (2 n ) k −1 = (2 n −1) (2 n ) k−1 + (2 n ) k−2 +ã ã ã+ 1 chia hết cho m = 2 n −1 , tức 2 m−1 ≡1(modm).
Vậy m là số giả nguyên tố cơ sở 2 Từ đó suy ra có vô hạn số giả nguyên tố cơ sở 2.
CHƯƠNG 2 ỨNG DỤNG CỦA HÀM SỐ EULER TRONG ĐẢM
BẢO AN TOÀN CỦA MẬT MÃ
2.1 Sơ lược về lý thuyết mật mã
Lý thuyết mật mã gắn liền với quá trình mã hóa, chuyển đổi thông tin từ dạng có thể đọc thành dạng không thể đọc mà không có khoá bí mật Mã hóa chủ yếu được sử dụng để bảo vệ tính bí mật của thông tin quan trọng trong lĩnh vực tình báo, quân sự, ngoại giao, cũng như trong kinh tế và thương mại Gần đây, mật mã đã được ứng dụng rộng rãi trong chữ ký số, bầu cử điện tử và tiền điện tử, trở thành công cụ quan trọng trong an ninh máy tính và mạng.
Mật mã học là một lĩnh vực liên ngành, phát triển từ nhiều lĩnh vực khác nhau Các hình thức mã hóa cổ xưa chủ yếu liên quan đến mẫu ngôn ngữ Gần đây, với sự thay đổi trong tầm quan trọng, mã hóa ngày càng gắn liền với toán học, đặc biệt là toán học rời rạc, bao gồm lý thuyết số, lý thuyết thông tin, độ phức tạp tính toán, thống kê và tổ hợp.
Mật mã hóa là quá trình chuyển đổi thông tin thông thường, như văn bản rõ, thành dạng không thể đọc trực tiếp, được gọi là văn bản mã hóa Sơ đồ khái quát về hệ thống mật mã giúp minh họa rõ ràng cách thức hoạt động của quá trình này.
Giải mã là quá trình phục hồi văn bản thường từ văn bản mã, trong khi mật mã là thuật toán dùng để mã hóa và giải mã Hoạt động của mật mã phụ thuộc vào các khóa - thông tin bí mật cho phép tạo ra văn bản mã Các giao thức mật mã quy định chi tiết về cách thức mã hóa và các nền tảng khác được sử dụng để thực hiện các nhiệm vụ cụ thể Hệ thống mật mã bao gồm một bộ giao thức, thuật toán, quản lý khóa và các hành động do người sử dụng quy định Trong ngôn ngữ thông thường, "mã" thường được hiểu là "mật mã", nhưng trong mật mã học, nó có nghĩa kỹ thuật đặc biệt, liên quan đến việc thay thế các đơn vị văn bản lớn hơn như từ hoặc câu.
Hình 2.1: Sơ đồ khái quát về một hệ thống mật mã
Như vậy trong một hệ thống mật mã khái quát sẽ có các thành phần sau:
- Văn bản trơn (plaintext), tức là thông điệp nguyên gốc chưa được mã hóa.
- Văn bản mã hóa (ciphertext), tức là thông điệp đã được mã hóa.
- Thuật toán mã hóa (enciphering algorithm) là các giao thức hoặc hướng dẫn có tác dụng chuyển đổi văn bản trơn thành văn bản mã hóa.
Khóa mã hóa, hay còn gọi là enciphering key, là một hoặc nhiều đối tượng, thường là các con số hoặc hướng dẫn quan trọng, được sử dụng để mã hóa văn bản trơn.
Thuật toán giải mã là các quy trình chuyển đổi văn bản mã hóa thành văn bản gốc, giúp đảm bảo tính bảo mật thông tin Chỉ những người nhận thông điệp mới có quyền truy cập vào thuật toán này, nhằm bảo vệ nội dung khỏi sự xâm nhập trái phép.
2.1.3 Hệ thống mã hóa Một hệ thống mã hóa (hệ mật mã) bao gồm 5 thành phần (P, C, K, D, E):
1 Các thông tin trước khi mã hóa, kí hiệu là P (Plaintext),
2 Các thông tin sau khi mã hóa, kí hiệu là C (Ciphertext),
3 Các chìa khóa, kí hiệu là K (Key);
4 Các quy tắc mã hóa, ký hiệu là E (Encrytion),
Các quy tắc giải mã, ký hiệu là D (Giải mã), cần thỏa mãn điều kiện rằng với mỗi k ∈ K, tồn tại một quy tắc mã hóa e k : P → C và một quy tắc giải mã tương ứng d k : C → P Điều này đảm bảo rằng d k (e k (x)) = x cho mọi x thuộc P Hình 2.2 minh họa các thành phần của mật mã.
Hình 2.2: Các thành phần của mật mã
Quá trình mã hóa diễn ra khi áp dụng hàm toán học E lên dữ liệu P, được biểu diễn dưới dạng số, để tạo ra thông tin đã mã hóa C.
Quá trình giải mã được tiến hành ngược lại: Áp dụng hàm D lên thông tin C để được thông tin đã giải mã P.
Sử dụng các ký hiệu của hệ mật mã, các công việc trên được toán học hoá bởi các công thức sau: E K (P) = C; D K (C) =P.
Mật mã khoá công khai
Có hai hình thức mã hoá được sử dụng phổ biến là mã hoá đối xứng (sym- metric key crytograpy) và mã hoá bất đối xứng (asymmetric cryptography).
Mã hoá đối xứng, hay còn gọi là mã hoá không công khai, là phương thức mà cả người gửi và người nhận sử dụng chung một khoá để mã hoá và giải mã thông điệp Trong trường hợp khác, người gửi và người nhận có thể sử dụng các khoá khác nhau, nhưng mối liên hệ giữa chúng có thể dễ dàng tính toán.
Mã hóa bất đối xứng, hay còn gọi là mã hóa công khai, sử dụng hai khóa khác nhau cho quá trình mã hóa và giải mã Trong kỹ thuật này, một khóa công khai (PU) được phổ biến để mã hóa, trong khi khóa riêng (PR) được giữ bí mật để giải mã Việc này cho phép các bên tham gia trao đổi thông tin mà không cần chia sẻ khóa mật qua kênh, giúp tăng cường tính bảo mật Mặc dù việc giữ bí mật khóa là rất quan trọng, nhưng việc trao đổi khóa qua kênh an toàn vẫn là một thách thức lớn Mã hóa công khai ra đời nhằm giải quyết vấn đề này, cho phép bảo mật thông tin mà không cần phải trao đổi khóa mật.
Mã hóa khóa công khai là một hệ mật mã bao gồm các phép biến đổi mã hóa {E e} và giải mã {D d}, được gọi là mật mã khóa công khai hoặc mật mã bất đối xứng Trong đó, khóa mã hóa e là khóa công khai, dễ dàng được chia sẻ, trong khi khóa giải mã d là khóa riêng, cần được bảo mật Hệ mật mã này phải đảm bảo an toàn, không cho phép tính toán được khóa riêng từ khóa công khai Ý tưởng về hệ mật công khai được giới thiệu bởi Diffie và Hellman vào năm 1976.
Hình 2.3: Sơ đồ của hệ mã công khai
Hệ mã công khai sử dụng hai khóa có mối quan hệ toán học, trong đó một khóa được tạo ra từ khóa kia Cụ thể, người nhận bản mã, gọi là Alice, sẽ tạo ra một khóa mật (private key) và từ khóa mật này, cô ấy sẽ tính toán ra khóa công khai.
Khóa công khai cho phép người gửi tin nhắn (Bob) mã hóa thông tin qua kênh công cộng, trong khi việc tìm ra khóa mật từ khóa công khai là một bài toán khó Bản mã được Bob gửi đến Alice và chỉ có thể được giải mã bằng khóa mật.
2.2.3 Nguyên tắc hoạt động Một hệ thống mật mã khóa công khai bao gồm:
+ Mỗi thực thể thông tin (user) tạo ra một cặp khóa để dùng cho việc mã hóa và giải mã.
Mỗi người dùng chia sẻ một trong hai khóa của mình, gọi là khóa công khai, trong khi khóa còn lại được giữ bí mật (khóa riêng) Khi người dùng A muốn gửi thông tin cho người dùng B, A sẽ mã hóa thông tin bằng khóa công khai của B.
Khi user B nhận thông tin mã hóa từ user A, họ sử dụng khóa riêng của mình để giải mã Vì khóa riêng không được công khai, chỉ user B mới có khả năng thực hiện việc giải mã này.
Người gửi A mã hóa thông điệp bằng khóa công khai của người nhận B, và sau đó, người nhận B sẽ giải mã thông điệp bằng khóa riêng tương ứng của mình Quá trình này được minh họa trong hình 2.4 và hình 2.5.
Hình 2.4: Mã hoá thông điệp sử dụng khoá công khai P
Hình 2.5: Giải mã thông điệp sử dụng khóa riêng của người nhận
2.2.4 Ứng dụng của mật mã khóa công khai Mật mã khoá công khai được sử dụng cho các mục đích sau đây:
- Bảo mật thông tin (message cofidentiality).
- Xác thực nguồn thông tin bằng chữ ký số (digital signature).
- Trao đổi khóa trong các thuật toán mã đối xứng (key exchange).
Độ an toàn của khóa công khai phụ thuộc vào các thuật toán mật mã hóa bất đối xứng, tương tự như các thuật toán mã hóa khóa đối xứng Một số thuật toán được sử dụng phổ biến, trong khi những thuật toán khác chủ yếu tồn tại trên lý thuyết Mặc dù có những thuật toán vẫn được coi là an toàn, cũng có những thuật toán đã bị phá vỡ Cần lưu ý rằng, không phải tất cả các thuật toán phổ biến đều đảm bảo an toàn tuyệt đối.
Một số thuật toán mã hóa đã được chứng minh về độ an toàn theo các tiêu chuẩn khác nhau, liên kết việc phá vỡ chúng với những bài toán nổi tiếng chưa có lời giải trong thời gian đa thức Tuy nhiên, chưa có thuật toán nào được khẳng định là an toàn tuyệt đối, như hệ thống mật mã sử dụng một lần Do đó, các thuật toán mã hóa khóa công khai cần được sử dụng một cách thận trọng.
Hệ mật mã khoá công khai giải quyết được những vấn đề tồn đọng của hệ mật mã khoá đối xứng, nhờ vào ưu điểm này, nhiều nghiên cứu đã được thực hiện để phát triển và đánh giá các hệ mật mã công khai Tuy nhiên, do phụ thuộc vào các giả thiết liên quan đến những bài toán khó, tốc độ mã hóa của các hệ thống này thường không nhanh, khiến chúng khó được sử dụng độc lập Một trong những nhược điểm lớn là khả năng một người có thể tìm ra khóa bí mật, và chưa có thuật toán mã hóa khóa bất đối xứng nào được chứng minh an toàn trước các tấn công dựa trên bản chất toán học của thuật toán Khả năng tồn tại mối quan hệ giữa hai khóa hoặc điểm yếu trong thuật toán có thể dẫn đến việc giải mã mà không cần khóa hoặc chỉ cần khóa mã hóa vẫn chưa được loại trừ An toàn của các thuật toán này phụ thuộc vào ước lượng khối lượng tính toán cần thiết để giải quyết các bài toán liên quan, nhưng những ước lượng này có thể thay đổi theo sự phát triển của công nghệ máy tính và các phát hiện toán học mới.
Mặc dù các thuật toán mã hóa khóa công khai có độ an toàn tương đối cao, nhưng vẫn tồn tại những điểm yếu Nếu thời gian phá mã ước tính lên đến 1000 năm, thì chúng vẫn có thể được sử dụng an toàn cho thông tin thẻ tín dụng, vì thời gian tồn tại của thẻ thường chỉ từ hai đến ba năm Tuy nhiên, nhiều thuật toán mã hóa bất đối xứng, như thuật toán đóng gói ba lô, đã từng bị phát hiện những lỗ hổng an ninh khi có các tấn công không lường trước Gần đây, các phương pháp tấn công mới đã được phát hiện, cho phép tìm khóa giải mã thông qua việc đo thời gian thực hiện mã hóa của hệ thống phần cứng Do đó, mã hóa khóa bất đối xứng không thể đảm bảo an toàn tuyệt đối, và lĩnh vực này vẫn đang được nghiên cứu để phát hiện các dạng tấn công mới.
Một điểm yếu của khóa bất đối xứng là nguy cơ bị tấn công kiểu kẻ tấn công đứng giữa, trong đó kẻ tấn công lợi dụng việc phân phối khóa công khai để giả mạo khóa Sau khi chiếm đoạt khóa công khai, kẻ tấn công có thể nhận và giải mã các gói tin trước khi mã hóa lại bằng khóa đúng và gửi đến người nhận, nhằm tránh bị phát hiện Để phòng ngừa loại tấn công này, cần áp dụng các phương pháp trao đổi khóa an toàn để đảm bảo tính xác thực của người gửi và toàn vẹn thông tin Cần lưu ý rằng, các chính phủ có thể thuyết phục hoặc ép buộc nhà cung cấp chứng thực số xác nhận khóa giả mạo, từ đó có khả năng đọc thông tin mã hóa.
Cơ sở số học của hệ mã RSA
Thuật toán RSA được Ron Rivest, Adi Shamir và Len Adleman mô tả lần đầu tiên vào năm 1977 tại Học viện Công nghệ Massachusetts (MIT), Hoa
Thuật toán RSA, được đặt theo ba chữ cái đầu của tên ba tác giả, là một phương pháp mã hóa khóa công khai trong mật mã học Đây là thuật toán đầu tiên cho phép tạo ra chữ ký điện tử cùng với việc mã hóa, đánh dấu bước tiến quan trọng trong lĩnh vực này RSA hiện đang được áp dụng rộng rãi trong thương mại điện tử và được coi là an toàn, miễn là độ dài khóa đủ lớn.
Thuật toán RSA sử dụng hai loại khóa: khóa công khai và khóa bí mật Khóa công khai được phát tán rộng rãi để mã hóa thông tin, trong khi khóa bí mật chỉ được người sở hữu biết để giải mã Điều này có nghĩa là bất kỳ ai cũng có thể mã hóa dữ liệu, nhưng chỉ người nắm giữ khóa bí mật mới có khả năng giải mã thông tin đó Hệ thống mã hóa này thể hiện rõ tính bảo mật và tiện lợi của việc sử dụng khóa công khai.
B muốn gửi cho A một thông tin mật mà chỉ A có thể đọc Để thực hiện điều này, A đã gửi cho B một chiếc hộp đã mở khóa sẵn và giữ lại chìa khóa B nhận hộp, cho vào đó một tờ giấy viết thư và khóa lại, khiến cho ngay cả B cũng không thể mở lại để sửa thông tin Sau đó, B gửi hộp lại cho A, người sau đó mở hộp bằng chìa khóa của mình và đọc thông tin Trong trường hợp này, chiếc hộp với khóa mở tượng trưng cho khóa công khai, trong khi chìa khóa là khóa bí mật.
Hệ mật mã RSA được mô tả chủ yếu như sau:
Cho n = pq , với p, q là những số nguyên tố phân biệt đủ lớn. Đặt P = C = Z n Chọn e nguyên tố cùng nhau với ϕ(n).
Theo công thức tính giá trị của hàm số số học Euler, ta có ϕ(n) = ϕ(pq) = (p−1) (q −1).
K = {(n, e, d) : de ≡1(modϕ(n))}, trong đó (n, e) là khoá công khai, còn d là khoá bí mật Định nghĩa:
Phương pháp mã công khai đã tạo ra một cuộc cách mạng trong công nghệ an toàn thông tin điện tử Tuy nhiên, thực tế cho thấy rằng tốc độ mã hóa khối lượng dữ liệu lớn bằng các thuật toán mã hóa công khai chậm hơn nhiều so với hệ thống mã hóa đối xứng.
Để trao đổi thông tin bí mật qua kênh không an toàn, A và B sử dụng thuật toán RSA Bên A cần tạo một cặp khóa bao gồm khóa công khai và khóa bí mật bằng cách thực hiện các bước cụ thể.
1 Chọn n= pq , vớip, q là những số nguyên tố phân biệt đủ lớn (lựa chọn ngẫu nhiên và độc lập).
3 Tính giá trị của hàm số Euler: ϕ(n) = (p−1)(q −1).
4 Chọn ngẫu nhiên một số tự nhiên e sao cho 1 < e < ϕ(n) và e nguyên tố cùng nhau với ϕ(n)
5 Tính số nguyên d duy nhất sao cho 1< d < ϕ(n) vàde ≡ 1 (modϕ(n))
- Cặp khoá công khai của hệ mã RSA là (n, e) ;
- Khoá bí mật của hệ mã RSA là d
- Số nguyên eđược tạo ra trong thuật toán trên được gọi là số mũ mã hoá của hệ mã RSA.
- Số nguyên d được tạo ra trong thuật toán trên được gọi là số mũ giải mã của hệ mã RSA.
Số nguyên n được gọi là môđun của hệ mã RSA.
Quá trình mã hóa RSA bắt đầu khi A muốn gửi thông điệp M cho B, người sẽ giải mã thông điệp đó Để thực hiện mã hóa bằng RSA, A cần tuân theo một số bước cụ thể để đảm bảo thông điệp được bảo mật và chỉ B có thể giải mã thành công.
1 Xác thực khoá công khai (n, e)
2 Biểu diễn thông điệp M thành một số nguyên m trong đoạn [0, n−1]
3 Tính c ≡ m e (modn) (bằng cách sử dụng thuật toán bình phương và nhân liên tiếp để tính luỹ thừa modn).
4 Gửi bản mã hoá c tới B.
A chuyển M thành một số m nhỏ hơn n thông qua một hàm đảo ngược đã được thỏa thuận Khi đó, B có m và biết n cũng như e do A gửi B sẽ tính c, bản mã hóa của m, theo công thức c ≡ m^e (mod n).
Quá trình giải mã RSA yêu cầu người B sử dụng khóa bí mật d để khôi phục bản rõ M từ bản mã hóa c mà người A đã gửi Cụ thể, người B thực hiện phép toán m ≡ c^d (mod n) để lấy lại thông tin ban đầu.
Nói chi tiết hơn: B nhận bản mã hoá c từ A và biết khóa bí mật d Do đó, B có thể tìm được m từ c theo công thức sau: c ≡ m e (modn)
Biết m, B tìm lại M theo phương pháp đã thỏa thuận trước.
Quá trình giải mã RSA nói trên là khả thi bởi vì ta có c d ≡ (m e ) d (modn) hay c d ≡ m ed (modn)
Vì de≡ 1 (modϕ(n)) và ϕ(n) = (p−1)(q −1) nên ta suy ra ed≡ 1 (mod (p−1)) ;ed≡ 1 (mod (q −1))
Từ đó, sử dụng Định lý Fermat bé, ta có m ed ≡ m(modp) và m ed ≡ m(modq)
Do p và q là hai số nguyên tố cùng nhau và n = pq , theo Định lý số dư Trung Hoa, ta có: m ed ≡ m(modn) hay c d ≡ m(modn).
Dưới đây là một ví dụ cụ thể với các số liệu nhỏ để dễ dàng tính toán Tuy nhiên, trong thực tế, chúng ta cần sử dụng các số có giá trị lớn hơn để đạt được kết quả chính xác hơn.
Trong phần này, chúng ta sẽ xem xét ví dụ về mã hoá và giải mã thông điệp RSA bằng số Giả sử A gửi cho B một thông điệp là một số, và giữa A và B có một phương pháp chuyển đổi giữa văn bản và số Các bước thực hiện mã hoá và giải mã sẽ được trình bày cụ thể trong bài viết này.
1 B chọn ra hai số nguyên tố p = 23, q = 41
2 B tính ra tích pq = 23∗41 = 943 Giá trị này sẽ được B chuyển tới A.
3 B chọn một số nguyên e sao cho
Chẳng hạn, có thể chọn e = 7 là một thành phần khoá công khai.
A nhận được khoá công khai (n, e) = (943, 7) từ B A sẽ sử dụng cặp khoá này để mã hoá thông tin M trước khi gửi cho B Giả sử thông điệp được chuyển đổi thành m = 35.
5 A tính giá trị c sao cho c ≡ m e (modn) Tính toán cụ thể cho ta c = 545 Giá trị 545 là bản mã và được A gửi tới cho B.
6 B muốn giả mã thông điệp 545 thì B phải tự xác định số nguyên d thoả mãn ed ≡ 1 (mod (p−1) (q −1)).
Trong trường hợp này là 7d ≡1 (mod880) hay d = 503
7 Sau khi có số mũ giải mã d , người B cần tính c d theo modn.
Trong trường hợp cụ thể này là 545 503 (mod943).
Sử dụng thuật toán bình phương và nhân liên tiếp (suy từ Định lý Euler),
B sẽ giải mã thông điệp là m = 35.
Trong ví dụ này, số nguyên tố thứ nhất p = 61 và số nguyên tố thứ hai q = 53 cần được giữ bí mật hoặc hủy sau khi tạo khóa Môđun n được tính bằng tích của p và q, cụ thể là n = pq = 3233, và đây là thông tin công bố công khai Số mũ công khai e được xác định là 17, trong khi số mũ bí mật d được tính là 2753.
Khóa công khai là cặp (e, n) Khóa bí mật là d Hàm mã hóa là:
E(m) = m e mod n = m 17 mod 3233, với m là văn bản rõ Hàm giải mã là:
D(c) = c d mod n= c 2753 mod 3233, với c là văn bản mã. Để mã hóa văn bản có giá trị 123, ta thực hiện phép tính:
E(123) = 123 17 mod 3233 = 855 Để giải mã văn bản có giá trị 855, ta thực hiện phép tính:
2.3.6 Thực hành bằng Maple để lập mã RSA .
> vbgoc := "em xin chuc cac thay co manh khoe";
> dectohex := [seq(convert(str[i], hex, decimal), i = 1 nops(str))];
> hextostr := cat(seq(dectohex[i], i = 1 nops(dectohex)));
> number := convert(hextostr, decimal, hex);
> hexstr := convert(vbmaso, hex, decimal):
> hexlist := [seq(substring(hexstr, 2*i-1 2*i), i = 1 (1/2)*length(hexstr))]:
> declist := [seq(convert(hexlist[i], decimal, hex), i = 1 nops(hexlist))]:
> vbgiaima := convert(convert(convert(declist, list), bytes), name); vbgiaima:= em xin chuc cac thay co manh khoe
2.3.7 Về độ an toàn của hệ thống RSA Độ an toàn của hệ thống RSA dựa trên hai bài toán số học sau:
1 Bài toán phân tích ra thừa số nguyên tố các số nguyên, gọi tắt là bài toán IFP (The Integer Factorization Problem);
Bài toán RSA yêu cầu tìm số nguyên m sao cho m^e ≡ c (mod n), với n = pq là tích của hai số nguyên tố p và q, và e là số nguyên thỏa mãn điều kiện (e, ϕ(n)) = 1.
Phân tích n ra thừa số nguyên tố hiện nay là phương pháp triển vọng nhất để giải bài toán mã hóa Nếu kẻ tấn công thành công tìm được hai số nguyên tố p và q sao cho n = pq, họ có thể dễ dàng tính toán giá trị (p−1)(q−1) và xác định số mũ bí mật d từ khóa công khai e Mặc dù chưa có phương pháp nào được phát triển để giải bài toán này trong thời gian đa thức, nhưng cũng chưa có chứng minh nào khẳng định sự không tồn tại của thuật toán.
Việc hiểu rõ về khoá lập mã (e, n) không đồng nghĩa với việc có thể dễ dàng xác định khoá giải mã (d, n) Để tìm ra nghịch đảo d của e mod ϕ(n), trước tiên cần xác định ϕ(n), một nhiệm vụ không đơn giản hơn việc phân tích n Khi đã biết ϕ(n) và n, ta có thể phân tích n thành tích của hai số nguyên tố p và q Cụ thể, ta có mối quan hệ giữa p, q và ϕ(n) với công thức p + q = n - ϕ(n) + 1 và p - q = √((p + q)² - 4pq).
Từ các công thức đó tìm được các số nguyên tố p, q