Chương 1. CÁC KIẾN THỨC CƠ SỞ Lý thuyết mật mã là một ngành khoa học đƣợc xây dựng dựa trên cơ sở toán học, đặc biệt là lý thuyết số học. Chƣơng này tổng hợp một số kiến thức toán học liên quan đƣợc sử dụng trong lý thuyết mật mã cũng nhƣ trong lĩnh vực chữ ký số [2, 3, 5, 7, 33]. LÝ THUYẾT SỐ HỌC 1.
Phép chia hết và chia có dƣ 1.1 1) Cho hai số nguyên a và b (b ≠ 0). Nếu có một số nguyên q sao cho a = b.q thì ta nói rằng a chia hết cho b, kí hiệu b\a. Khi đó ta nói b là ƣớc của a hay a là bội của b.4 do đó 2 là ƣớc của 8 và ký hiệu 2\8. 2) Cho các số nguyên a, b (b ≠ 0), tồn tại cặp số nguyên (q, r) duy nhất sao cho a = b.q + r, 0 r < b , khi đó q gọi là thƣơng nguyên, r gọi là số dƣ của phép chia a cho b.
Nếu r = 0 thì ta có phép chia hết. Một số tính chất Với a, b, c là các số nguyên ta có: 1) ±1\a, với mọi a; a\0, a\a, với mọi a ≠ 0. 2) Nếu a\b và b\c thì a\c, với mọi a ≠ 0, b ≠ 0. 4) Nếu a\b và a\c thì a\(b+c) và a\(b-c), với mọi a ≠ 0.
5) Nếu a\b và c\d thì a. LUAN VAN CHAT LUONG download : add luanvanchat@agmail. Ƣớc chung lớn nhất, bội chung nhỏ nhất 1.2 1) Một số nguyên d đƣợc gọi là ƣớc chung của các số nguyên a 1, a2, …, an nếu nó là ƣớc của tất cả các số đó. 2) Một số nguyên m đƣợc gọi là bội chung của các số nguyên a1, a2, …, an nếu nó là bội của tất cả các số đó.
3) Một ƣớc chung d>0 của các số nguyên a1, a2, …, an sao cho mọi ƣớc chung của a1, a2, …, an đều là ƣớc của d, thì d đƣợc goi là ƣớc chung lớn nhất của a1, a2, …, an và ký hiệu là d = gcd(a1, a2, …, an). Để cho gọn trong trình bày ta có thể ký hiệu là d = (a1, a2, …, an). 4) Nếu gcd(a1, a2, …, an) = 1 thì các số a1, a2, …, an đƣợc gọi là nguyên tố cùng nhau. 5) Một bội chung m>0 của các số nguyên a1, a2, …, an sao cho mọi bội chung của a1, a2, …, an đều là bội của m, thì m đƣợc goi là bội chung nhỏ nhất của a1, a2, …, an và ký hiệu là m = lcm(a1, a2, …, an).
Ví dụ: gcd(12,18) = 6; lcm(12,18) = 36; gcd(8,9) = 1 do đó 8 và 9 là hai số nguyên tố cùng nhau. Tính chất 1) d = gcd(a1, a2, …, an) khi và chỉ khi tồn tại các số x1, x2,…, xn sao cho: d = a1x1+a2x2+…+an. 3) Nếu d là một ƣớc chung của a1, a2, …, an thì: d = gcd(a1, a2, …, an) khi và chỉ khi gcd(a1/d, a2/d,…, an/d) =1. 4) Nếu gcd(a,b) = 1 và b\ac thì b\c.
LUAN VAN CHAT LUONG download : add luanvanchat@agmail.com 8 5) Nếu gcd(a,b) = 1 thì gcd(ac,b) = gcd(c,b). 6) Nếu gcd(a, b) =1 thì lcm(a, b) = ab. 7) Nếu b > 0, a = bq+r thì gcd(a,b) = gcd(b,r). Thuật toán Euclide tìm ước chung lớn nhất 1) Bài toán Dữ liệu vào: Cho hai số nguyên không âm a, b, a ≥ b.
Kết quả: gcd(a,b).2 + 0 LUAN VAN CHAT LUONG download : add luanvanchat@agmail. Thuật toán Euclide mở rộng 1) Bài toán Dữ liệu vào: Cho hai số nguyên không âm a, b, a ≥ b. Kết quả: d = gcd(a,b) và hai số x, y sao cho: ax + by = d. 2) Thuật toán: (mô phỏng bằng ngôn ngữ Pascal) Readln(a, b); If b = 0 then Begin d := a; x := 1; y := 0; writeln(d, x, y); End Else Begin x2 := 1; x1 := 0; y2 := 0; y1 := 1; While b>0 do Begin q := a div b; r := a mod b; x := x2-q*x1; y := y2-q*y1; a := b; b := r; x2 := x1; x1 := x; y2 := y1; y1 := y; End; d := a; x := x2; y := y2; writeln(d, x, y); End; LUAN VAN CHAT LUONG download : add luanvanchat@agmail.
Số nguyên tố 1.3 Số nguyên tố là số tự nhiên lớn hơn 1, chỉ có hai ƣớc là 1 và chính nó. Ví dụ: Các số 2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37 là số nguyên tố. Số nguyên tố có vai trò và ý nghĩa to lớn trong số học và lý thuyết mật mã. Bài toán kiểm tra tính nguyên tố của một số nguyên dƣơng N và phân tích một số N ra thừa số nguyên tố là các bài toán rất đƣợc quan tâm và có nhiều công trình nghiên cứu và đã đạt đƣợc các kết quả to lớn.
Hiện nay bài toán kiểm tra tính nguyên tố đƣợc xếp vào lớp bài toán P. Có một số phƣơng pháp kiểm tra tính nguyên tố của một số nguyên bằng xác xuất nhƣ: Solovay-Strassen, Lehmann-Peralta, Miller-Rabin [5]. Ví dụ: 10 số nguyên tố đƣợc tìm thấy [33]. Thứ Số nguyên tố Số chữ số Tác Thời Tham khảo hạng giả gian 1 232582657-1 9808358 G9 2006 Mersenne 44 2 230402457-1 9152052 G9 2005 Mersenne 43 3 225964951-1 7816230 G8 2005 Mersenne 42 4 224036583-1 7235733 G7 2004 Mersenne 41 5 220996011-1 6320430 G6 2003 Mersenne 40 6 213466917-1 4053946 G5 2001 Mersenne 39 7 19249·213018586+1 3918990 SB10 2007 8 27653·29167433+1 2759677 SB8 2005 9 28433·27830457+1 2357207 SB7 2004 10 33661·27031232+1 2116617 SB11 2007 LUAN VAN CHAT LUONG download : add luanvanchat@agmail.
Một số định lý 1) Định lý 1.1 (Định lý cơ bản) Mọi số nguyên dƣơng n > 1 đều có thể biểu diễn duy nhất đƣợc dƣới dạng n P1n1 .Pknk với k, ni là các số tự nhiên, Pi là các số nguyên tố đôi một khác nhau (i = 1, 2,.2 (Định lý Mersenne) Cho p = 2k -1, nếu p là số nguyên tố thì k là số nguyên tố. Chứng minh Giả sử k không là số nguyên tố.b với 1 < a, b < k, do đó p = 2k -1 = 2ab -1 = (2a)b -1 = (2a -1).E (E là một biểu thức nguyên) mâu thuẫn giả thiết p là nguyên tố. Vậy giả sử là sai, hay k là số nguyên tố.3 (Hàm Euler) ▪ Hàm Euler Cho số nguyên dƣơng n, số lƣợng các số nguyên dƣơng bé hơn n và nguyên tố cùng nhau với n đƣợc ký hiệu (n) và gọi là hàm Euler. ▪ Nhận xét Nếu p là số nguyên tố thì (p) = p-1.
▪ Định lý Nếu n là tích của hai số nguyên tố n = p. LUAN VAN CHAT LUONG download : add luanvanchat@agmail.4 Cho các số nguyên a, b, m (m>0). Ta nói rằng a và b đồng dư với nhau theo modulo m nếu trong phép chia a và b cho m ta được cùng một số dư, ký hiệu: a ≡ b (mod m) [33]. Ví dụ: 19 ≡ 7 (mod 3) vì 19 và 7 chia cho 3 có cùng số dƣ là 1.
Các mệnh đề sau đây là tương đương: 1) a ≡ b (mod m). 3) Tồn tại một số nguyên t sao cho a = b + mt. Chứng minh 1)→2) : Theo định nghĩa a, b chia cho m có cùng số dƣ do đó : a = mqa + r; b = mqb + r; suy ra a - b = m(qa - qb) chứng tỏ m \ a-b; 2)→3) : m\a-b nên có t Z sao cho a - b = mt hay a = b + mt 3)→1) : Lấy a chia cho m giả sử thƣơng là qa và dƣ r: a = mqa + r (0 ≤ r <m), do đó: b + mt = a = mqa + r hay b = m(qa - t) + r (0 ≤ r < m). Điều đó chứng tỏ khi chia a và b cho m đƣợc cùng số dƣ r hay a ≡ b(mod m) 1.
Các tính chất 1) Quan hệ đồng dƣ theo modulo m là một quan hệ tƣơng đƣơng trong Z: (1) a ≡ a (mod m) với mọi a Z ( phản xạ). LUAN VAN CHAT LUONG download : add luanvanchat@agmail.com 13 2) Có thể cộng hoặc trừ từng vế nhiều đồng dƣ thức theo cùng một modulo m với nhau, ta đƣợc một đồng dƣ thức theo cùng modulo m tức là: k k Nếu ai ≡ bi (mod m) , i = 1.k thì: ti ai tibi (mod m) với ti = ±1. i 1 i 1 3) Có thể nhân từng vế các đồng dƣ thức theo cùng một modulo m với nhau, ta đƣợc một đồng dƣ thức theo cùng modulo m: k k Nếu ai ≡ bi (mod m), i=1.k thì ta có: ai bi (mod m). LUAN VAN CHAT LUONG download : add luanvanchat@agmail.
Các lớp thặng dư Quan hệ đồng dƣ theo modulo m trên tập Z 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 một phân hoạch trên tập các số nguyên Z thành ra 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 chia cho m. Mỗi lớp tƣơng đƣợc đại diện bởi một số duy nhất trong tập hợp Zm = {0, 1, 2,…, m-1} là số dƣ khi chia các số trong lớp cho m, ký hiệu một lớp đƣợc đại diện bởi số a là [a]m hay với m mặc định nào đó ta viết tắt là [a], vậy: [a]m = [b]m ↔ a ≡ b (mod m). Vì vậy ta có thể đồng nhất Zm với tập các lớp tƣơng đƣơng theo modulo m. Tập Zm = {0, 1, 2,…, m-1} đƣợc gọi là tập các thặng dƣ đầy đủ theo modulo m.
Mọi số nguyên bất kỳ đều có thể tìm đƣợc trong Zm một số đồng dƣ với mình theo modulo m [3, 33]. Nếu p không chia hết a thì ap-1 ≡ 1 (mod p). Trƣờng họp m là số nguyên tố ta có định lý Ferma. LUAN VAN CHAT LUONG download : add luanvanchat@agmail.com 15 Hệ quả 1: Nếu gcd(c, m) = 1 và a ≡ b (mod (m)) với a, b là các số tự nhiên thì ca ≡ cb (mod m) và suy ra: ca mod m = ca mod (m) mod m.
Nhận xét: Hệ quả trên giúp ta giảm nhẹ việc tính toán đồng dƣ của lũy thừa bậc cao một cách đáng kể. Ví dụ muốn tính 21004 (mod 15): Ta thấy (15) = (5). Hệ quả 2: Nếu e, d là các các số nguyên thỏa mãn e. Nhận xét: Với a = ed và b = 1, từ hệ quả 1 ta có hệ quả 2.
Hệ quả này đóng vai trò then chốt trong việc thiết lập các hệ mã mũ sau này (nhƣ RSA).