Chương 1 : CÁC KHÁI NIỆM VÀ THUẬT TOÁN CƠ BẢN Chƣơng này trình bày các vấn đề cơ bản trong toán học đƣợc ứng dụng nhiều trong các bài toán an toàn thông tin. Đó là các vấn đề về lý thuyết toán học sử dụng trong bảo mật và mã hóa thông tin nhƣ : Mã hóa đồng cấu, chữ ký mù, chia sẻ bí mật ngƣỡng Shamir và mã hóa Elgamal. Thông qua đó hình thành cơ sở lý thuyết cho an toàn truyền tin trên mạng máy tính.1 Hàm phi Euler 1/ Định nghĩa Cho n >= 1, Φ(n) đƣợc định nghĩa là số các số nguyên trong khoảng từ [1, n] nguyên tố cùng nhau với n. Hàm Φ (n) đƣợc gọi là hàm Euler phi.
2/ Tính chất của hàm Euler Nếu p là số nguyên tố thì Φ (n) = p – 1. Hàm phi Euler là hàm có tính nhân : Nếu gcd(m, n) = 1 thì Φ(mn) = Φ(m) Φ(n) (trong đó gcd(m, n) là ký hiệu ƣớc số chung lớn nhất của m và n) Nếu n = p1e1p2e2…pkek trong đó p1, p2, ., pk là các thừa số nguyên tố của n thì: 1 1 1 Φ(n) = n(1 - )(1 - )… (1 - ) p1 p2 pk 1.2 Đồng dƣ thức 1/ Định nghĩa Cho a và b là các số nguyên, a đƣợc gọi là đồng dƣ với b theo modulo n, ký hiệu: a b (mod n) nếu (a – b) chia hết cho n. Số nguyên n đƣợc gọi là modulus đồng dƣ. 2/ Ví dụ 10 3 (mod 7) vì 10 – 3 = 7 chia hết cho 7 7 -4 (mod 11) vì 7 – (-4) = 11 chia hết cho 11 2.
3/ Tính chất của đồng dư Cho a, a1, b, b1, c Z. Ta có các tính chất sau: a b (mod n) nếu và chỉ nếu a và b cùng có số dƣ khi chia cho n a a (mod n) – Tính phản xạ a b (mod n) thì b a (mod n) – Tính đối xứng a b (mod n) và b c (mod n) thì a c (mod n) – Tính bắc cầu nếu a a1 (mod n) và b b1 (mod n) thì : a + b a1 + b1 (mod n) a.b1 (mod n) Quan hệ “đồng dƣ” theo modulo n trên tập Z (tập các số nguyên) là một quan hệ tƣơng đƣơng (vì có tính chất phản xạ, đối xứng, bắc cầu), do đó nó tạo ra trên tập một phân hoạch gồm các lớp tƣơng đƣơng : hai số nguyên thuộc cùng một lớp tƣơng đƣơng khi và chỉ khi chúng có cùng một số dƣ khi chi cho n. Mỗi lớp tƣơng đƣơng đại diện bởi một số duy nhất trong tập Zn = {0, 1, 2, … , n-1} là số dƣ khi chia các số trong lớp cho n, ký hiệu một lớp đƣợc đại diện bởi số a là [a] n: Nhƣ vậy : [a] n = [b]n tƣơng đƣơng với a b (mod n) Vì vậy ta có thể đồng nhất Zn với tập các lớp tƣơng đƣơng theo modulo n. Zn = {0, 1, 2, … , n-1} đƣợc gọi là tập các “thặng dƣ đầy đủ” theo modulo n.
Mọi số nguyên bất kỳ đều có thể tìm đƣợc trong Zn một số đồng dƣ với mình theo modulo n.3 Không gian Zn 1/ Các định nghĩa trong không gian Zn Các số nguyên theo modul n ký hiệu Zn là tập hợp các số nguyên {0,1,2,…, n-1}. Các phép toán cộng, trừ, nhân trong Zn đƣợc thực hiện theo modulo n. Tƣơng tự, 13*16 = 8 trong Z25 - Cho a Zn. Nghịch đảo nhân của a theo modulo n là một số nguyên x Zn sao cho a*x 1 (mod n).
Nếu x tồn tại thì đó là giá trị duy nhất và a đƣợc gọi là khả nghịch, nghịch đảo của a ký hiệu là a-1. Phép chia của a cho b theo modulo n là tích của a và b-1 theo modulo n, và chỉ dƣợc xác định khi b có nghịch đảo theo modulo n. 3/ Các tính chất trong không gian Zn - Cho a Zn , a có nghịch đảo khi và chỉ khi gcd(a, n) = 1 trong đó : gcd(a, n) (greatest common divisor) là ký hiệu ƣớc số chung lớn nhất của a và n Ví dụ: Các phần tử khả nghịch trong Z9 là: 1, 2, 4, 5, 7 và 8.7 1 (mod 9) Tiếp theo là sự tổng quát hoá của tính chất 1.6 - Giả sử d = gcd(a, n). Phƣơng trình đồng dƣ ax b (mod n) có nghiệm x nếu và chỉ nếu d chia hết cho b, trong trƣờng hợp các nghiệm d nằm trong khoảng 0 đến n-1 thì các nghiệm đồng dƣ theo modulo n/d.
4/ Định lý phần dư Trung Hoa CRT Nếu các số nguyên n1, n2, …, nk là các số nguyên tố cùng nhau từng đôi một thì hệ phƣơng trình đồng dƣ : x a1 (mod n1 ) x a2 (mod n2 ) …. x ak (mod nk ) có nghiệm duy nhất theo modulo n = n1n2 … nk 5/ Thuật toán của Gausse Nghiệm x trong hệ phƣơng trình đồng dƣ (định lý phần dƣ Trung Hoa) đƣợc tính nhƣ sau : k x = ai NiMi mod n i 1 -1 trong đó: Ni = n/ni, Mi = Ni mod ni 4. Ví dụ: Cặp đồng dƣ: x 3 (mod 7) và x 7 (mod 13) có nghiệm duy nhất x 59 (mod 91) Tính chất : Nếu gcd(n1, n2) = 1 thì cặp đồng dƣ x a (mod n1) và x a (mod n2) có nghiệm duy nhất x a (mod n1n2) 1.4 Nhóm nhân Zn* 1/ Các định nghĩa trong nhóm nhân Z*n Nhóm nhân của Zn ký hiệu là Z*n = {a Zn | gcd (a, n) = 1}. Đặc biệt, nếu n là số nguyên tố thì Z*n = {aZn | 1 ≤ a ≤ n-1} Cho aZn*.
Bậc của a, ký hiệu là ord(a) là số nguyên dƣơng t nhỏ nhất sao cho at 1 (mod n). 2/ Các tính chất trong Zn* - Cho n ≥ 2 là số nguyên : (Định lý Euler) Nếu a Zn* thì aΦ(n) 1 (mod n). Nếu n là tích của các số nguyên tố phân biệt và nếu r s (mod Φ(n)) ar as (mod n) với mọi số nguyên a. Nói cách khác, làm việc với các số theo modulo nguyên tố p thì số mũ có thể giảm theo modulo Φ(n) - Cho p là số nguyên tố : (Định lý Fermat) Nếu gcd(a, p) = 1 thì ap-1 1 (mod p).
Nếu r s (mod p-1) thì ar as (mod p) với mọi số nguyên a. Nói cách khác, làm việc với các số theo modulo nguyên tố p thì số mũ có thể giảm theo modulo p-1 Đặc biệt ap a (mod p) với mọi số nguyên a.5 Thặng dƣ 1/ Định nghĩa thặng dư Cho a Zn*. a đƣợc gọi là thặng dƣ bậc 2 theo modulo n hoặc bình phƣơng theo modulo n nếu tồn tại xZn* sao cho x2 a (mod n). Nếu không tồn tại x thì a đƣợc gọi là thặng dƣ không bậc 2 theo modulo n.
Tập hợp các thặng dƣ bậc 2 theo modulo n ký ___ hiệu là Qn và tập hợp các thặng dƣ không bậc 2 theo modulo n ký hiệu là Q n. ___ Chú ý vì định nghĩa 0 Zn* nên 0 Qn và 0 Q n 2/ Tính chất của thặng dư Cho n là tích của 2 số nguyên tố p và q. Khi đó a Zn* là một thặng dƣ bậc 2 theo ___ modulo n khi và chỉ khi a Qn và a Q n. Ta có, |Qn| = |Qp|.|Qq| = (p-1)(q-1)/4 và ___ | Q n| = 3(p-1)(q-1)/4 3/ Ví dụ ___ Cho n = 21.6 Căn bậc Modulo 1/ Định nghĩa Cho a Qn.
Nếu a Zn* thoả mãn x2 a (mod n) thì x đƣợc gọi là căn bậc 2 của a theo modulo n. 2/ Tính chất (Số căn bậc 2) Nếu p là một số nguyên tố lẻ thì a Qn thì a có chính xác 2 căn bậc 2 theo modulo p Tổng quát hơn: cho n = p1e1p2 e2…pk ek trong đó pi là các số nguyên tố lẻ phân biệt và ei ≥1. Nếu a Qn thì a có chính xác 2k căn bậc 2 theo modulo n. 3/ Ví dụ Căn bậc 2 của 13 theo modulo 37 là 7 và 30.
căn bậc 2 của 121 modulo 315 là 11, 74, 101, 151, 164, 214, 241 và 304.7 Các thuật thoán trong Zn* 1/ Định nghĩa Cho n là số nguyên dƣơng. Nhƣ đã nói ở trƣớc, các phần tử trong Zn sẽ đƣợc thể hiện bởi các số nguyên {0, 1, 2,…, n-1}. Ta thấy rằng: nếu a, b Zn thì: a + b nếu a + b < n (a + b) mod n= a + b – n nếu a + b ≥ n Vì vậy, phép cộng modulo (và phép trừ modulo) có thể đƣợc thực hiện mà không cần thực hiện các phép chia. Phép nhân modulo của a và b có thể đƣợc thực hiện bằng phép nhân thông thƣờng a với b nhƣ các số nguyên bình thƣờng, sau đó lấy phần dƣ của kết quả sau khi chia cho n.
Phép tính nghịch đảo trong Zn có thể đƣợc thực hiện nhờ sử dụng thuật toán Euclidean mở rộng nhƣ mô tả sau: 2/Thuật toán tính nghịch đảo nhân trong Zn INPUT: a Zn OUTPUT: a-1 mod n nếu tồn tại. Sử dụng thuật toán Euclidean mở rộng sau để tìm các số nguyên x và y sao cho: ax + ny = d với d = gcd(a, n). Nếu d > 1 thì a-1 mod n không tồn tại. Ngƣợc lại, return (x).
3/ Thuật toán Euclidean mở rộng: INPUT: 2 số nguyên dƣơng a và b với a ≥ b. OUTPUT: d = gcd(a, b) và các số nguyên x, y thoả mãn: ax + by = d 1. Nếu b = 0 thì đặt d a, x 1, y 0 và return (d, x, y) 2. Khi b > 0 thực hiện: 3.
q [a/b], r = a – qb, x x2 – qx1, y y2 – qy1 3. Đặt d a, x x2, y y2 và return (d, x, y) 7. Số mũ modulo có thể đƣợc tính một các hiệu quả bằng thuật toán bình phƣơng và nhân liên tiếp, nó đƣợc sử dụng chủ yếu trong nhiều giao thức mã hoá. Một phiên bản t của thuật toán này nhƣ sau: Giả sử biểu diễn nhị phân của k là i 0 ki2i với ki {0,1}.
4/ Thuật toán bình phương liên tiếp để tính số mũ modulo trong Zn. INPUT: a Zn và số nguyên dƣơng 0 ≤ k < n trong đó k có biểu diễn nhị phân t là: k = i 0 ki 2i OUTPUT: ak mod n 1. Nếu k0 = 1 thì đặt b a.