Chương 1. CÁC KHÁI NIỆM CƠ BẢN 1. MỘT SỐ KHÁI NIỆM TOÁN HỌC. Số nguyên tố và số nguyên tố cùng nhau.
Số nguyên tố là số tự nhiên lớn hơn 1, chỉ chia hết cho 1 và chính nó. Hai số nguyên a và b được gọi là nguyên tố cùng nhau nếu chúng có ước số chung lớn nhất bằng 1 (viết: gcd(a, b) = 1). Hai số nguyên tố cùng nhau a, b được ký hiệu: a b. 2, 3, 5, 7, 11… là những số nguyên tố.
14 và 17 là hai số nguyên tố cùng nhau. 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 lần lượt chia a và b cho m, ta nhận được cùng một số dư. 17 ≡ 23 (mod 3) vì: 17 = 5*3 + 2 23 = 7*3 + 2 Vậy 17 và 23 đồng dư với nhau theo modulo 3.
Nhận xét: Các mệnh đề sau đây là tương đương. 1) a ≡ b (mod m) 2) m \ (a - b) 3) Tồn tại số nguyên t sao cho a = b + mt (LUAN.tinh TIEU LUAN MOI download : skknchat@gmail. Các tính chất của quan hệ “đồng dƣ”. Với mọi số nguyên dương m ta có: a ≡ a (mod m) với mọi a Z; (tính chất phản xạ) a ≡ b (mod m) thì b ≡ a (mod m); (tính chất đối xứng) a ≡ b (mod m) và b ≡ c (mod m) thì a ≡ c (mod m); (tính chất bắc cầu) Tổng hay hiệu các đồng dư: (a+b) (mod n) ≡ [(a mod n) + (b mod n)] (mod n) (a-b) (mod n) ≡ [(a mod n) - (b mod n)] (mod n) Tích các đồng dư: (a*b) (mod n) ≡ [(a mod n) * (b mod n)] (mod n) 4/.
Quan hệ “đồng dư” theo modulo m 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 Z 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 chia cho m. Mỗi lớp tương đương đại diện bởi một số trong tập Z m = {0, 1,…, 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 Như 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. 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.tinh TIEU LUAN MOI download : skknchat@gmail.
Phần tử nghịch đảo. Cho a Zn , nếu tồn tại b Zn sao cho a*b 1 (mod n), ta nói b là phần tử nghịch đảo của a trong Zn, ký hiệu b = a -1. Khi một phần tử có phần tử nghịch đảo của nó, phần tử đó được gọi là khả nghịch (có nghịch đảo). ƯCLN (a, n) = 1 Phần tử a Zn có phần tử nghịch đảo.
Cho a, b Zn, 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ỉ được xác định khi b có nghịch đảo theo modulo n. Tức là: a / b (mod n) = a * b-1 (mod n) Ví dụ: Xét phần tử a = 4 Z9, ta có gcd(4,9) = 1 nên phần tử a là khả nghịch trong Z9. Ta sẽ tìm phần tử nghịch đảo b này. b = 7 là phần tử nghịch đảo của 4 trong Z9 vì thỏa mãn: 4 * 7 mod 9 = 1 hay 4 * 7 1 (mod 9) Phần tử a Zn là phần tử khả nghịch trong Zn khi và chỉ khi gcd(a,n) = 1 (LUAN.tinh TIEU LUAN MOI download : skknchat@gmail.
Khái niệm về mã hóa dữ liệu. Bảo mật thông tin là một nhu cầu thiết yếu trong quá trình trao đổi thông tin dưới cả hình thức cổ xưa hay hiện đại (internet) như ngày hôm nay. Việc bảo mật thông tin thông thường được thực hiện bằng cách mã hóa thông tin, việc mã hóa thông tin để đảm bảo sao cho chỉ người nào có khóa giải mã thì mới có thể nhận được đúng thông tin gốc ban đầu. b ) thông tin “khó” b ).
ngược lại: thao tác b b để có thể nhận được đúng thông tin gốc ban đầu. óa hay thuật toán việc. không gian khóa. mã hóa thông tin như để giải mã bản mã.
Dựa trên tiêu chí đặc trưng đối xứng của khóa để phân loại, ta có 2 loại hệ mã hóa: + Hệ mã hóa khóa bí mật (hay còn gọi là hệ mã hóa khóa đối xứng). Hệ mật mã khóa bí mật yêu cầu người gửi và người nhận phải thỏa thuận một khóa trước khi tin tức được gửi đi, khóa này phải được cất giữ bí mật. Quá trình mã hóa và giải mã đều sử dụng chung một khóa (nên nó phải được giữ bí mật ở cả hai phía, vậy nó còn có tính đối xứng).tinh TIEU LUAN MOI download : skknchat@gmail.tinh 12 Mô hình mã hóa khóa bí mật (đối xứng) gồm hai quá trình mã hóa và giải mã, như sau: Bản Bản rõ mã hóa Bản mã giải mã rõ Hình 1.1: Mô hình mã hóa khóa bí mật (đối xứng) Người gửi tạo bản mã từ bản rõ thông qua Private Key, bản mã này được truyền đi đến người nhận. Tại đây, người nhận sử dụng Private Key để giải mã bản mã này, thu được bản rõ là thông tin gốc ban đầu.
* Ưu điểm - Tốc độ mã hoá và giải mã nhanh. - Đơn giản, tiện dụng khi dùng một khoá cho cả hai quá trình mã hoá và giải mã. * Nhược điểm - Không an toàn vì độ phức tạp tính toán phụ thuộc vào khoá. - Vì bên nhận và bên gửi đều sử dụng một khoá nên khoá cần phải được truyền trên kênh an toàn.
Điều này làm phức tạp thêm cho hệ thống cài đặt hệ mã hóa khoá đối xứng. * Một số thuật toán mã hoá đối xứng - DES: 56 bit, không an toàn. Có thể bị bẻ khoá trong khoảng vài phút. - Triple DES, RDES: mở rộng độ dài khoá trong hệ DES lên tới 168 bit.
- IDEA (International Data Encryption Algorithm): 128 bit, thuật toán này thường được dùng trong các chương trình email.tinh TIEU LUAN MOI download : skknchat@gmail.tinh 13 + Hệ mã hóa khóa công khai (hay còn gọi là hệ mã hóa khóa phi đối xứng). Tại phía người gửi, sử dụng một khóa để mã hóa, được gọi là khoá công khai (Public Key) tạo ra bản mã và gửi lên đường truyền. Tại phía người nhận, sử dụng một khoá để giải mã, được gọi là khoá riêng (Private Key) để giải mã bản mã này, thu được bản rõ là thông tin gốc ban đầu. Trong hệ mã hóa khóa công khai, khóa mã hóa khác với khóa giải mã, biết được khóa công khai “khó” thể tìm được khóa bí mật.
Bản Bản rõ mã hóa Bản mã giải mã rõ Hình 1.2: Hệ mã hóa khóa phi đối xứng * Ưu điểm - Kẻ tấn công biết được thuật toán mã hóa và khóa mã hóa (Public Key) cũng “khó” có thể tính được khóa riêng (Private Key). Chức năng này đạt được trên nguyên tắc sử dụng các hàm một chiều khi tính hàm y = f(x) là dễ nhưng ngược lại việc tính giá trị x khi đã biết y là khó. - Không đòi hỏi kênh truyền bí mật vì khoá mã hoá được truyền công khai trên đường truyền cho tất cả mọi người. * Nhược điểm - Tốc độ mã hóa chậm hơn so với mã hóa khóa đối xứng.
* Một số thuật toán mã hóa khóa công khai - RSA: độ dài khóa 512 đến 1024 bit, được dùng nhiều nhất cho web và chương trình email. - ElGamal: độ dài khóa từ 512 đến 1024 bit.tinh TIEU LUAN MOI download : skknchat@gmail. Hệ mã hóa được định nghĩa là bộ năm (P, C, K, E, D), trong đó: P là tập hữu hạn các bản rõ có thể, là dữ liệu cần mã hóa. C là tập hữu hạn các bản mã có thể, là dữ liệu đã được mã hóa.
K là tập hữu hạn các khóa có thể, gồm khóa mã hóa (ke) và khóa giải mã (kd). E là tập các hàm (thuật toán) mã hóa (E(ke, P) = C). D là tập các hàm (thuật toán) giải mã (D(kd, C) = P). Với khóa lập mã ke K, có hàm mã hóa eke E, eke: P C Với khóa giải mã kd K, có hàm giải mã dkd D, dkd: C P sao cho dkd (eke (x)) = x, x P.
Ở đây x được gọi là bản rõ, eke (x) được gọi là bản mã. Như vậy, có thể tóm lược sơ đồ quá trình mã hóa và giải mã như hình dưới. Chú ý rằng trong quá trình bản mã được truyền đi trên đường truyền, đây là thời điểm để tin tặc có thể trộm bản mã: Người gửi G: x eke(x) Người nhận N: (dùng khóa lập mã ke) (dùng khóa giải mã kd) Tin tặc có thể trộm bản mã eke(x) trên đường truyền (LUAN.tinh TIEU LUAN MOI download : skknchat@gmail.tinh 15 * Hệ mã hóa khóa công khai RSA. Sơ đồ (do Rivest, Shamir, Adleman đề xuất năm 1977) - Tạo cặp khóa (bí mật, công khai) (a, b): Chọn bí mật số nguyên tố lớn p, q, tính n = p * q, công khai n.
Chọn khóa công khai b < (n), nguyên tố cùng nhau với (n). Khóa bí mật a là phần tử nghịch đảo của b theo mod (n): a*b 1 mod (n). Tập cặp khóa (bí mật, công khai) K = (a, b)/ a, b Zn , a*b 1 mod (n). Với Bản rõ x P và Bản mã y C, định nghĩa: Hàm Mã hoá: y = ek (x) = x b mod n Hàm Giải mã: x = dk (y) = y a mod n 2/.
Giả sử bảng các chữ cái viết hoa tiếng Anh từ A đến Z được cho tương ứng với các số nguyên từ 1 => 26: A B C D E F G H I J K L MN O P Q R S T U V WX Y Z A 1 2 3 4 5 6 7 8 9 1 1 1 1 1 1 1 1 1 1 2 2 2 2 2 2 2 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 Ta sử dụng hệ mã hóa RSA để mã hóa bản rõ chữ sau: Bản rõ chữ: HAPPINESS *Sinh khóa: Chọn bí mật số nguyên tố p = 5, q = 7, tính n = p * q = 35, công khai n. Đặt P = C = Zn , tính bí mật (n) = (p-1)*(q-1) = 4 * 6 = 24.