MỞ ĐẦU Hệ mật mã RSA được phát minh bởi Ron Rivest, Adi Shamin và Leonard Adleman là hệ mật mã khóa công khai được biết đến và sử dụng rộng rãi nhất trên thế giới hiện nay. RSA được sử dụng hàng triệu lần mỗi ngày trên internet. Nó được sử dụng trên web servers và trên Browers nhằm đảm bảo an ninh đường truyền, được sử dụng trong việc tạo khóa và xác thực của mail, trong truy cập từ xa,.RSA là một hệ mật mã công khai được sử dụng trong giao thức SSL (Transport Layer Secure Sockets Layer) và giao thức TLS (Transport Layer Security). Ngày nay, RSA đã được phát triển và ứng dụng rộng rãi trong thương mại điện tử.
Đặc biệt, nó là hạt nhân của hệ thống thanh toán điện tử. Hơn 30 năm sau lần đầu tiên công bố công khai, RSA nó vẫn là một lĩnh vực nghiên cứu tích cực trong mật mã học. Trong thực tế, đã có nhiều nghiên cứu trực tiếp liên quan đến hệ mật mã RSA. Điển hình như nghiên cứu của May, Ritzenhofen và Aono được trình bày tại PKC năm 2009; nghiên cứu của Aggarwal và Maurer đã được trình bày tại EUROCRYPT năm 2009.
Các RSA bản gốc, theo SiteSeer, đã được trích dẫn hơn 2100 lần. Ngay từ khi công bố lần đầu tiên, RSA đã được phân tích hệ số an toàn bởi nhiều nhà nghiên cứu. Cho đến nay, các nhà nghiên cứu đã tìm ra một số phương pháp tấn công RSA và chỉ ra được những mối nguy hiểm tiềm ẩn của RSA, mà khi sử dụng RSA người dùng cần cải thiện. Thực tế, vấn đề thám mã đối với hệ mật mã RSA hiện tại vẫn đang được các nhà nghiên cứu tập trung khai thác các sở hở của RSA, các cuộc tấn công có tính chất toán học khai thác cấu trúc của RSA như: tấn công khi số mũ công khai nhỏ, tấn công khi số mũ bí mật nhỏ, tấn công khi biết một số thông tin về khóa,.
Trong những năm gần đây, các biến thể của RSA cũng rất được quan tâm. Đây là những hệ mật mã cơ bản dựa trên RSA nhưng, nói chung, có hiệu quả hơn so với RSA về một mặt nào đó. Một số biến thể nổi tiếng của RSA như: CRT-RSA, Multi-Prime RSA, Multi-power RSA, Common prime RSA, và Dual RSA,. Ba biến thể CRT-RSA, Multi-Prime RSA, Multi-power RSA của RSA, được thiết kế để giảm thiểu chi phí giải mã.
Common prime RSA là một biến thể được thiết kế để chống lại các cuộc tấn công khi mũ bí mật nhỏ và Dual RSA là một phiên bản được thiết kế để giảm bớt các yêu cầu bộ nhớ của RSA Hệ mật RSA là hệ mật khóa công khai đang được sử dụng rộng rãi hiện nay, việc phân tích, đánh giá RSA và các biến thể của nó, đặc biệt là việc nghiên Nguyễn Thị Ngọc Anh – K16 – HTTT1 LUAN VAN CHAT LUONG download : add luanvanchat@agmail.com -7- cứu các các phương pháp tấn công để tìm ra các điểm yếu của hệ mật RSA và các biến thể của RSA, từ đó tìm cách khắc phục là vấn đề thời sự về mặt lý thuyết và thực tiễn. Vì vậy, em đã chọn đề tài “ Phân tích hệ mật mã RSA và các biến thể của nó” làm luận văn tốt nghiệp. Nội dung của luận văn trình bày một số vấn đề chính sau: Chƣơng I: Cơ sở lý thuyết và toán học của hệ mật mã RSA Chương này sẽ giới thiệu sơ lược về một số khái niệm trong mật mã như: hệ mật mã, hệ mật mã khóa bí mật, hệ mật mã khóa công khai,. và một số kiến thức toán học như: các khái niệm về: số nguyên tố, số nguyên tố cùng nhau, tập Zn và Z n* , hàm Phi - EULER, quan hệ “Đồng dư”, phân số liên tục,.; các định lý: định lý Fermat, định lý Euler, định lý số dư Trung Hoa và một số thuật toán.
Qua chương này, sẽ cho ta các kiến thức nền tảng để hiểu rõ về RSA và các biến thể của nó. Chƣơng II: Phân tích tổng quan hệ mật mã RSA và các biến thể của RSA Chương này sẽ phân tích tổng quan RSA và một số các biến thể của RSA như: CRT-RSA, Multi-Prime RSA, Multi-Power RSA về các mặt như: đặc điểm, sơ đồ, an toàn. Chƣơng III: Tấn công RSA và biến thể của RSA Chương này sẽ trình bày một số cuộc tấn công có tính chất toán học, khai thác cấu trúc của RSA và các biến thể của nó, qua đây có thể cho ta một cái nhìn tổng quát về các cuộc tấn công thuộc loại này. Đầu tiên, luận văn sẽ trình bày một số cuộc tấn công được biết đến sớm nhất vào RSA như: tấn công khi modulus phổ biến, tấn công Hastad's Broadcats, tấn công lặp.
Sau đó, luận văn trình bày một số cuộc tấn công điển hình trong một số trường hợp như: tấn công khi số mũ công khai nhỏ, tấn công khi số mũ bí mật nhỏ, tấn công khi biết một số thông tin về khóa. Cuối cùng, luận văn trình bày một số tấn công vào các biến thể của RSA. Chƣơng IV: Đánh giá và so sánh hệ mật mã RSA với các biến thể của nó Chương này sẽ thực hiện đánh giá và so sánh về tốc độ và không gian nhớ sử dụng trong các thuật toán của RSA và các biến thể: CRT-RSA, Multi-Prime RSA, Multi-Power RSA Nguyễn Thị Ngọc Anh – K16 – HTTT1 LUAN VAN CHAT LUONG download : add luanvanchat@agmail.com -8- CHƢƠNG 1: CƠ SỞ LÝ THUYẾT VÀ TOÁN HỌC CỦA HỆ MẬT MÃ RSA Chương này trình bày một số khái niệm cơ bản về mã hóa thông tin, các thành phần cơ bản của một hệ mật mã, hệ mật mã khóa đối xứng, hệ mật mã khóa bất đối xứng và một số khái niệm, định lý toán học làm cơ sở để hiểu được hệ mật mã RSA. Giới thiệu chung về mật mã * Khái niệm mật mã [11]: M ) hiệu quả.
* Lịch sử của mật mã: Có thể nói, mật mã đã có khoảng 4000 năm lịch sử, điều này được minh chứng bởi các cổ vật mà các nhà khảo cổ thời cổ đại tìm được. Những người Ai Cập đã khắc những mã bằng hình vẽ lên các ngôi mộ để tỏ lòng tôn kính những người đã chết, chữ tượng hình này như một dạng mã hóa đơn giản nhất. Khoảng 400 năm trước công nguyên, người Spactơ đã sử dụng một hệ thống mã hóa thông tin bằng cách viết thông điệp lên một chiếc gậy quyền trượng có băng giấy cói quấn quanh. Thông điệp được viết theo cách thức thông thường từ trái sang phải và từ trên xuống dưới.
Khi băng giấy được tháo ra khỏi chiếc quyền trượng, thông điệp trở thành một dãy các kí tự ngẫu nhiên. Người Hi Lạp cổ đại đã sử dụng cách trên để trao đổi thông tin quân sự. Khi nhận được mã, những đội quân Hi Lạp sẽ quấn mảnh giấy lên các quyền trượng có đường kính và chiều dài phù hợp và dãy kí tự ngẫu nhiên sẽ biến thành thông điệp có thể hiểu được. Người ta cho rằng, người đầu tiên áp dụng mật mã một cách có hệ thống để đảm bảo bí mật thông tin quân sự là nhà quân sự thiên tài của La Mã cổ đại, Hoàng đế Julirs Caesar.
Caesar đã từng sử dụng phép mã thay thế trong quân sự, trong đó mỗi ký tự được thay thế bởi ký tự đứng sau nó 3 vị trí trong bảng chữ cái alphabet. Người xưa thường che dấu thông tin mã hiệu dưới 2 dạng, hoặc bằng phương pháp nào đó che dấu thông tin mà đối phương không phát hiện được, hoặc bằng cách biến đổi mã hiệu thành một dạng công khai nào đó nhưng khó nhận biết được nội dung. Nguyễn Thị Ngọc Anh – K16 – HTTT1 LUAN VAN CHAT LUONG download : add luanvanchat@agmail.com -9- Mã khối được xem là xuất hiện vào những năm đầu thế kỷ XX, với sự ra đời của hệ mã British Playfair vào năm 1954, trong đó mỗi khối là một cặp 2 chữ. Hệ mã tích hợp (Product cipher) được sử dụng sớm nhất là của quân đội Đức trong Đại chiến thế giới lần thứ I, mang tên ADFGVX.
Trong Đại chiến Thế giới lần thứ II, người ta thấy rằng hệ mã tích hợp là rất an toàn. Tuy nhiên, hệ mã ADFGVX có những điểm yếu. Chính vì vậy, một hệ mã tích hợp khác, phức tạp hơn, đã được sử dụng trong Đại chiến thứ II, đó là ENIGMA. Sự ra đời của hệ mã Lucifer(1974) và sau đó được cải tiến thành hệ chuẩn mã dữ liệu DES (1975).
Tiếp sau đó, sự ra đời của hệ mã với khóa công khai vào cuối những năm 70 của thế kỷ vừa qua. Một số thuật ngữ đƣợc sử dụng trong hệ mật mã (1) Bản rõ (plaintext) Chứa các xâu ký tự gốc có thể đọc được, thông tin trong bản rõ là thông tin cần mã hoá để giữ bí mật. (3) Mật mã học (Crytography) Là nghệ thuật và khoa học để giữ thông tin được an toàn. (5) Giải mã (Decryption) Quá trình biến đổi bản mã thành bản rõ gọi là giải mã.
Trong phần này có tham khảo tài liệu [2], [3] 1. Hệ mật mã Việc mã hoá phải theo quy tắc nhất định, quy tắc đó gọi là Hệ mật mã. Nguyễn Thị Ngọc Anh – K16 – HTTT1 LUAN VAN CHAT LUONG download : add luanvanchat@agmail.com -10- Hệ mật mã đượ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ể. - C: là tập hữu hạn các bản mã có thể.
- K: là tập hữu hạn các khoá có thể. - E: là tập các hàm lập mã. - D: là tập các hàm giải mã. Với khóa lập mã ke K, có hàm lập mã ek e E, eke : P C Với khóa giải mã kd K, có hàm giải mã d k d D, d kde : C P , sao cho: d k d (eke ( x)) x, x P Vai trò của hệ mật mã: Hệ mật mã phải thực hiện được các vai trò sau: - Hệ mật mã phải che dấu được nội dung của văn bản rõ để đảm bảo sao cho chỉ người chủ hợp pháp của thông tin mới có quyền truy cập thông tin, hay nói cách khác là chống truy nhập không đúng quyền hạn.
- Tạo các yếu tố xác thực thông tin, đảm bảo thông tin lưu hành trong hệ thống đến người nhận hợp pháp là xác thực. - Tổ chức các sơ đồ chữ ký điện tử, đảm bảo không có hiện tượng giả mạo, mạo danh để gửi thông tin trên mạng. Ưu điểm lớn nhất của bất kỳ hệ mật mã nào đó là: có thể đánh giá được độ phức tạp tính toán mà “kẻ địch” phải giải quyết bài toán để có thể lấy được thông tin của dữ liệu đã được mã hoá.