Tài liệu Kỹ thuật lập trình - Chương 8: Mật mã khóa công khai

Chương 8: Mật mã khóa công khai, người học sẽ tìm hiểu tổng quan về mật mã công khai, hệ mật RSA, hệ mật Elgama, hệ mật Rabin, hệ mật Merkle-hellman, hệ mật McEliece, hệ mật bất đối xứng trên cơ sỡ đường cong Elliptic.
Nội dung trích xuất từ tài liệu:
Tài liệu Kỹ thuật lập trình - Chương 8: Mật mã khóa công khai Chương 8 MẬT MÃ KHÓA CÔNG KHAI 8.1 Tổng quan về mật mã công khai Trong chương trước chúng ta đã tìm hiểu về mật mã đối xứng. Chúng ta rõ rằng cácbên tham gia cần có một khóa mật để mã hóa và giải mã. Điều này đồng nghĩa với việctrao đổi khóa mật qua kênh. Việc giữ bí mật khóa mật đồng nghĩa với việc giữ mậtthông tin. Nên việc trao đổi khóa chỉ diễn ra trên kênh mật thì mới đ ảm bảo đ ược, th ếnhưng việc trao đổi này cung không phải dễ để đảm bảo độ an toàn cao. Từ đây hìnhthành nên ý tưởng của mật mã công khai. Tức là không cần phải trao đổi khóa mật quakênh nữa. Ý tưởng của hệ mật công khai được Diffie và Hellman đưa ra năm 1976. Còn việcthực hiện hệ mật công khai thì do Rivest, Shamir và Adleman đưa ra đầu tiên năm 1977,họ đề xuất một hệ mật RSA nổi tiếng. Và kể từ đó có một số hệ mật khác được côngbố, độ mật của chúng dựa trên bài tính toán khác nhau, như dựa trên độ khó của bài toánphân tích thành nhân tử như hệ mật RSA, dựa vào độ khó logarithm rời rạc như hệ mậtElGamal, hay dựa trên đường cong Elliptíc. Chúng ta đi tìm hiểu cụ thể các hệ mật nàytrong các phần sau. Nhưng trước tiên chúng ta đi tìm hiểu sơ đồ và nguyên tắc mã vàgiải mã của hệ mật công khai. Sơ đồ của hệ mã công khai được cho ở hình 8.1. Hình 8.1. Sơ đồ mã hóa công khai Hệ mã công khai sử dụng hai khóa có quan hệ toán học với nhau, tức là một khóanày được hình thành từ khóa kia: Người muốn nhận bản mã (Alice) tạo ra một khóamật (private key) và từ khóa mật tính ra khóa công khai (public key) với một thủ tụckhông phức tạp, còn việc tìm khóa mật khi biết khóa công khai là bài toán khó gi ảiđược. Khóa công khai sẽ đưa đến cho người gởi bản tin (Bob) qua kênh công cộng. Vàbản tin được Bob mã hóa bằng khóa công cộng. Bản mã truyền đến Alice, và nó đ ượcgiải mã bằng khóa mật. 8.2 Hệ mật RSA Lịch sử hình thành Thuật toán được Ron Rivest, Adi Shamir và Len Adleman mô tả lần đầu tiên vàonăm 1977 tại Học viện Công nghệ Massachusetts (MIT). Tên của thuật toán lấy từ 3chữ cái đầu của tên 3 tác giả. Đây là thuật toán đầu tiên phù hợp với việc tạo ra chữ kýđiện tử đồng thời với việc mã hóa. Nó đánh dấu một sự tiến bộ vượt bậc của lĩnh vựcmật mã học trong việc sử dụng khóa công cộng. RSA đang được sử dụng phổ biếntrong thương mại điện tử và được cho là đảm bảo an toàn với điều kiện độ dài khóa đủlớn. Thuật toán RSA được MIT đăng ký bằng sáng chế tại Hoa Kỳ vào năm 1983 (Sốđăng ký 4,405,829). Bằng sáng chế này hết hạn vào ngày 21 tháng 9 năm 2000. Tuynhiên, do thuật toán đã được công bố trước khi có đăng ký bảo hộ nên s ự bảo h ộ h ầunhư không có giá trị bên ngoài Hoa Kỳ. Ngoài ra, nếu như công trình của Clifford Cocksđã được công bố trước đó thì bằng sáng chế RSA đã không thể được đăng ký. Thuật toán dựa trên độ khó của bài toán phân tích một số thành nhân tử. Quá trình tạo khóa cho hệ mật RSA. Giả sử Alice và Bob cần trao đổi thông tin bí mật thông qua một kênh không an toàn(ví dụ như Internet). Với thuật toán RSA, Alice đầu tiên cần tạo ra cho mình cặp khóagồm khóa công khai và khóa bí mật theo 6 bước sau: 1. Chọn 2 số nguyên tố lớn khác nhau p, q thỏa mãn điều kiện p ≈ q 2. Tính tích của nó n = p ⋅ q . 3. Tính giá trị hàm Phi Euler của n: ϕ( n ) = ( p − 1)( q − 1) . 4. Chọn số nguyên d, sao cho d < ϕ( n ) và gcd(d, ϕ (n) )=1. 5. Tính giá trị e thỏa mãn điều kiện: e ⋅ d = 1mod( ϕ( n ) ) . 6. Khóa công khai bao gồm: n và e. Khóa mật:d còn p,q và ϕ (n) thường là xóa saukhi tính toán khóa. Quá trình mã hóa: Giả sử Bob muốn gửi đoạn thông tin m Cuối cùng Bob gửi c cho Alice. Quá trình giải mã: Alice nhận c từ Bob và khóa bí mật d. Alice có thể tìm được m từ c theo công thứcsau: m = c d (mod n) Quá trình giải mã hoạt động vì ta có c d ≡ (m e ) d ≡ med (mod n) Do ed ≡ 1 (mod p-1) và ed ≡ 1 (mod q-1), theo Định lý Fermat nhỏ nên: med ≡ m(mod p ) med ≡ m(mod q ) Do p và q là hai số nguyên tố cùng nhau, áp dụng định lý phần dư trung hoa, chúng tacó: med ≡ m(mod pq ) Hay c d ≡ m(mod n) Ví dụ: p = 70793 q = 707933 n = p ⋅ q = 50116700869 ϕ( n ) = ( p − 1)( q − 1) = 50115922144 d = 30483041 e = 5851898625 m c = me (mod n) m = c d (mod n) 30483041 7523619714 30483041 7523619714 38101458113 7523619714 3487987 ...