MỞ ĐẦU Bài toán logarit rời rạc trong Zp là đối tƣợng trong nhiều công trình nghiên cứu và đƣợc xem là bài toán khó nếu p đƣợc chọn cẩn thận. Bài toán này có nhiều ứng dụng sâu sắc trong nhiều hƣớng khác nhau của toán học, vật lý học,…đặc biệt bài toán logarit rời rạc là cơ sở để xây dựng hệ mã khóa công khai. Đây là dạng bài toán một chiều: bài toán lấy lũy thừa có thể tính toán hiệu quả theo thuật toán bình phƣơng và nhân, song bài toán ngƣợc tìm số mũ thì lại không dễ nhƣ vậy. Đề tài này nhằm nghiên cứu về bài toán logarit rời rạc và tìm hiểu ứng dụng của nó trong một vài hệ mã công khai: hệ mã RSA, hệ mã Elgamal, chữ kí Elgamal và hệ mã đƣờng cong Elliptic.
Luận văn đƣợc trình bày trong 2 chƣơng ngoài phần mởp đầu và kết luận. Chƣơng 1 gồm những kiến thức cơ sở để nhằm phục vụ cho chƣơng 2, bao gồm những kiến thức liên quan về về hệ mật mã, hệ mã công khai và bài toán logarit rời rạc. Chƣơng 2 tác giả trình bày những kiến thức cơ bản về hệ mã RSA, hệ mã Elgamal, chữ kí điện tử Ellgamal, hệ mã đƣờng cong Elliptic. Chƣơng này cũng trình bày một số ví dụ cụ thể để minh họa.
Mặc dù đã có nhiều cố gắng, song luận văn mới chỉ dừng ở mức trình bày hệ thống các kiến thức nhƣ trên và tính toán trên một số ví dụ cụ thể, phần ứng dụng thực tế còn hạn chế. Số hoá bởi Trung tâm Học liệu – ĐHTN http://www.vn 6 CHƢƠNG I : KIẾN THỨC CƠ SỞ Chƣơng 1 trình bày những kiến thức cơ sở khái quát về mật mã, khái niệm về hệ mật mã, hệ mã công khai, bài toán lôgarit rời rạc và một số thuật toán lôgarit rời rạc. Những kiến thức trình bày trong chƣơng này đƣợc trích dẫn ở tài liệu sau: Mã hoá thông tin: Cơ sở toán học và ứng dụng - Phạm Huy Điển, Hà Huy Khoái (2003) - NXB Đại Học Quốc Gia, Lý thuyết mật mã và an toàn thông tin - Phan Đình Diệu (2002) - NXB Đại Học Quốc Gia Hà Nội, Giáo trình an toàn dữ liệu – Khoa công nghệ thông tin - Trịnh Nhật Tiến - NXB Đại Học Quốc Gia Hà Nội. KHÁI QUÁT VỀ MẬT MÃ, MÃ CÔNG KHAI 1.
Khái quát về mật mã 1. Giới thiệu Mật mã đã đƣợc con ngƣời sử dụng từ lâu đời. Các hình thức mật mã sơ khai đã đƣợc tìm thấy từ khoảng bốn nghìn năm trƣớc trong nền văn minh Ai Cập cổ đại. Trải qua hàng nghìn năm lịch sử, mật mã đã đƣợc sử dụng rộng rãi ở khắp nơi trên thế giới từ Đông sang Tây để giữ bí mật cho việc giao lƣu thông tin trong nhiều lĩnh vực hoạt động giữa con ngƣời và các quốc gia, đặc biệt trong các lĩnh vực quân sự, chính trị, ngoại giao.
Mật mã trƣớc hết là một loại hoạt động thực tiễn, nội dung chính của nó là để giữ bí mật thông tin. Ví dụ muốn gửi một văn bản từ một ngƣời gửi A đến một ngƣời nhận B, A phải tạo cho văn bản đó một bản mã mật tƣơng ứng và thay vì gửi văn bản rõ thì A chỉ gửi cho B bản mã mật, B nhận đƣợc bản mã mật và khôi phục lại văn bản rõ để hiểu đƣợc thông tin mà A muốn gửi cho mình. Do văn bản gửi đi thƣờng đƣợc chuyển qua các con đƣờng công khai nên ngƣời ngoài có thể “lấy trộm” đƣợc, nhƣng vì đó là bản mật mã nên không đọc hiểu đƣợc. Còn A có thể tạo ra bản mã mật và B có thể giải bản mã mật thành bản rõ để hiểu Số hoá bởi Trung tâm Học liệu – ĐHTN http://www.vn 7 đƣợc là do hai ngƣời đã có một thoả thuận về một chìa khoá chung, chỉ với khoá chung này thì A mới tạo đƣợc bản mã mật từ bản rõ và B mới khôi phục đƣợc bản rõ từ bản mã mật.
Khoá chung đó đƣợc gọi là khoá mật mã. Để thực hiện đƣợc một phép mật mã, ta còn cần có một thuật toán biến bản rõ cùng với khoá mật mã thành bản mã mật và một thuật toán ngƣợc lại biến bản mật cùng với khoá mật mã thành bản rõ. Các thuật toán đó đƣợc gọi tƣơng ứng là thuật toán lập mã và thuật toán giải mã. Các thuật toán này thƣờng không nhất thiết phải giữ bí mật, mà cái luôn cần đƣợc giữ bí mật là khoá mật mã.
Trong thực tiễn, có những hoạt động ngƣợc lại với hoạt động bảo mật là khám phá bí mật từ các bản mã “lấy trộm” đƣợc, hoạt động này thƣờng đƣợc gọi là mã thám hay phá khoá. Các khái niệm cơ sở Mật mã là một lĩnh vực khoa học chuyên nghiên cứu về các phƣơng pháp và kỹ thuật đảm bảo an toàn và bảo mật trong truyền tin liên lạc với giả thiết sự tồn tại của các thế lực thù địch, những kẻ muốn ăn cắp thông tin để lợi dụng và phá hoại. Tên gọi trong tiếng Anh, Cryptology đƣợc dẫn giải nguồn gốc từ tiếng Hy lạp, trong đó kryptos nghĩa là “che dấu”, logos nghĩa là “từ ngữ”. Cụ thể hơn, các nhà nghiên cứu lĩnh vực này quan tâm xây dựng hoặc phân tích (để chỉ ra điểm yếu) các giao thức mật mã (cryptographic protocols), tức là các phƣơng thức giao dịch có đảm bảo mục tiêu an toàn cho các bên tham gia (với giả thiết môi trƣờng có kẻ đối địch, phá hoại).
Ngành Mật mã (cryptology) thƣờng đƣợc quan niệm nhƣ sự kết hợp của 2 lĩnh vực con: 1. Sinh, chế mã mật (cryptography): nghiên cứu các kỹ thuật toán học nhằm cung cấp các công cụ hay dịch vụ đảm bảo an toàn thông tin. Phá giải mã (cryptanalysis): nghiên cứu các kỹ thuật toán học phục vụ phân tích phá mật mã và hoặc tạo ra các đoạn mã giản nhằm đánh lừa bên Số hoá bởi Trung tâm Học liệu – ĐHTN http://www.vn 8 nhận tin. Hai lĩnh vực con này tồn tại nhƣ hai mặt đối lập, “đấu tranh để cùng phát triển” của một thể thống nhất là ngành khoa học mật mã (cryptology).
Tuy nhiên, do lĩnh vực thứ hai (cryptanalysis) ít đƣợc phổ biến quảng đại nên dần dần, cách hiểu chung hiện nay là đánh đồng hai thuật ngữ cryptography và cryptology. Theo thói quen chung này, hai thuật ngữ này có thể dùng thay thế nhau. Thậm chí cryptography là thuật ngữ ƣa dùng, phổ biến trong mọi sách vở phổ biến khoa học, còn cryptology thì xuất hiện trong một phạm vi hẹp của các nhà nghiên cứu học thuật thuần túy. Mặc dù trƣớc đây hầu nhƣ mật mã và ứng dụng của nó chỉ phổ biến trong giới hẹp, nhƣng với sự phát triển vũ bão của công nghệ thông tin và đặc biệt là sự phổ biến của mạng internet, các giao dịch có sử dụng mật mã đã trở nên rất phổ biến.
Chẳng hạn, ví dụ điển hình là các giao dịch ngân hàng trực tuyến hầu hết đều đƣợc thực hiện qua mật mã. Ngày nay, kiến thức ngành mật mã là cần thiết cho các cơ quan chính phủ, các khối doanh nghiệp và cả cho cá nhân. Một cách khái quát, ta có thể thấy mật mã có các ứng dụng nhƣ sau: - Với các chính phủ: bảo vệ truyền tin mật trong quân sự và ngoại giao, bảo vệ thông tin các lĩnh vực tầm cỡ lợi ích quốc gia. - Trong các hoạt động kinh tế: bảo vệ các thông tin nhạy cảm trong giao dịch nhƣ hồ sơ pháp lý hay y tế, các giao dịch tài chính hay các đánh giá tín dụng… - Với các cá nhân: bảo vệ các thông tin nhạy cảm, riêng tƣ trong liên lạc với thế giới qua các giao dịch sử dụng máy tính hoặc kết nối mạng.
Khái niệm hệ mật mã Hệ mật mã đƣợc định nghĩa là một bộ năm (P, C, K, E, D), trong đó: 1. P là tập hữu hạn các các bản rõ có thể. C 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ể.
Số hoá bởi Trung tâm Học liệu – ĐHTN http://www. E là tập các hàm lập mã. D là tập các hàm giải mã. Với mỗi k K, có một hàm lập mã ek E, ek : P → C và một hàm giải mã dk D, dk: C → P sao cho dk(ek(x)) = x , x P Hình 1.1: Quá trình mã hoá và giải mã - Một thông báo thƣờng đƣợc tổ chức dƣới dạng bản rõ.
- Ngƣời gửi sẽ làm nhiệm vụ mã hóa bản rõ, kết quả thu đƣợc gọi là bản mã. - Bản mã này đƣợc gửi đi trên một đƣờng truyền tới ngƣời nhận, sau khi nhận đƣợc bản mã ngƣời nhận giải mã nó để tìm hiểu nội dung. - Dễ dàng thấy đƣợc công việc trên khi sử dụng định nghĩa hệ mật mã: ek (P) = C và dk (C) = P. Những yêu cầu đối với hệ mật mã Một hệ mật mã phải cung cấp một mức cao về độ tin cậy, tính toàn vẹn, sự không từ chối và sự xác thực.
- Độ tin cậy: cung cấp sự bí mật cho các thông báo và dữ liệu đƣợc lƣu bằng việc che dấu thông tin sử dụng các kĩ thuật mã hóa. - Tính toàn vẹn: cung cấp sự bảo đảm với tất cả các bên rằng thông báo còn lại không thay đổi từ khi tạo ra đến khi ngƣời nhận mở nó ra. - Tính không từ chối: có thể cung cấp một cách xác nhận rằng tài liệu đã đến từ ai đó ngay cả khi họ cố gằng từ chối nó. - Tính xác thực: cung cấp hai dịch vụ: Số hoá bởi Trung tâm Học liệu – ĐHTN http://www.vn 10 + Đầu tiên là nhận dạng nguồn gốc của một thông báo và cung cấp một vài sự bảo đảm rằng nó là đúng sự thật.
+ Thứ hai là kiểm tra đặc tính của ngƣời đang trong một hê thống và sau đó tiếp tục kiểm tra đặc tính của họ trong trƣờng hợp ai đó cố gắng đột nhiên kết nối và giả dạng ngƣời sử dụng. Khái quát về hệ mã công khai 1. Mã đối xứng và mã công khai Mã đối xứng đƣợc dùng để chỉ các hệ mã mà trong đó khi biết khóa lập mã ta có thể tìm đƣợc khóa giải mã một cách đễ dàng. Đồng thời việc giải mã cũng đòi hỏi thời gian nhƣ việc lập mã.
Các hệ mã thuộc loại này có thời gian lập mã và giải mã tƣơng đối nhanh vì thế các hệ mã đối xứng thƣờng đƣợc sử dụng để mã hóa những dữ liệu lớn. Nhƣng các hệ mã đối xứng yêu cầu phải giữ bí mật hoàn toàn về khóa lập mã.