Tài liệu Loogarit rời rạc và mật mã công khai

1 .. ĐẠI HỌC THÁI NGUYÊN TRƢỜNG ĐẠI HỌC KHOA HỌC VĂN THỊ THU THỊNH LÔGARIT RỜI RẠC VÀ MẬT MÃ CÔNG KHAI LUẬN VĂN THẠC SĨ TOÁN HỌC THÁI NGUYÊN – 2014 Số hoá bởi Trung tâm Học liệu – ĐHTN http://www.lrc.tnu.edu.vn 2 ĐẠI HỌC THÁI NGUYÊN TRƢỜNG ĐẠI HỌC KHOA HỌC VĂN THỊ THU THỊNH LÔGARIT RỜI RẠC VÀ MẬT MÃ CÔNG KHAI Chuyên ngành: TOÁN ỨNG DỤNG Mã số: 60.46.01.12 LUẬN VĂN THẠC SĨ TOÁN HỌC NGƢỜI HƢỚNG DẪN KHOA HỌC: TS. VŨ MẠNH XUÂN THÁI NGUYÊN – 2014 Số hoá bởi Trung tâm Học liệu – ĐHTN http://www.lrc.tnu.edu.vn 3 MỤC LỤC MỤC LỤC………………………………………….........................................1 LỜI CẢM ƠN…………………………………………………………….......2 MỞ ĐẦU………………………………………………………………….......3 CHƢƠNG I. KIẾN THỨC CƠ SỞ…………………………………………...4 1.1. Khái quát về mật mã, mã công khai…………………………...........4 1.2. Bài toán lôgarit rời rạc……………………………………………..11 CHƢƠNG II. ỨNG DỤNG LÔGARIT RỜI RẠC TRONG MỘT SỐ HỆ MÃ CÔNG KHAI………………………………………………………………...22 2.1. Hệ mã RSA………………………………………………………...22 2.2. Hệ mã Elgamal…………………………………………………….27 2.3. Sơ đồ chữ kí Elgamal………………………………………………37 2.4. Hệ mã đƣờng cong Eliptic…………………………………………43 KẾT LUẬN………………………………………………………………….56 TÀI LIỆU THAM KHẢO…………………………………………………...57 Số hoá bởi Trung tâm Học liệu – ĐHTN http://www.lrc.tnu.edu.vn 4 LỜI CẢM ƠN Sau một thời gian nghiên cứu tìm hiểu, em đã hoàn thành luận văn thạc sỹ toán học chuyên ngành toán ứng dụng với đề tài: “ Lôgarit rời rạc và mật mã công khai”. Lời đầu tiên em xin bày tỏ lòng biết ơn sâu sắc tới thầy giáo TS. Vũ Mạnh Xuân đã tận tình hƣớng dẫn em trong suốt quá trình nghiên cứu và thực hiện đề tài. Em cũng xin chân thành cảm ơn quý thầy cô khoa Toán – tin trƣờng Đại học Khoa học – Đại học Thái Nguyên, các đồng nghiệp và các bạn học trong lớp đã hƣớng dẫn, truyền đạt kiến thức, tạo mọi điều kiện giúp đỡ cho em trong suốt thời gian theo học và thực hiện luận văn này. Qua việc nghiên cứu và hoàn thành luận văn, em đã có thêm nhiều kiến thức bổ ích trong chuyên môn cũng nhƣ phƣơng pháp luận nghiên cứu khoa học. Trong khuôn khổ của một luận văn, chắc chắn chƣa đáp ứng đƣợc đầy đủ những vấn đề đặt ra. Vì điều kiện nghiên cứu còn hạn chế, nên mặc dù đã cố gắng rất nhiều nhƣng luận văn không tránh khỏi những thiếu sót. Em rất mong nhận đƣợc sự đóng góp ý kiến, phê bình quý báu của các nhà khoa học, các thầy cô và các bạn đồng nghiệp. Một lần nữa em xin chân thành cảm ơn ! Thái Nguyên, tháng 09 năm 2014 Học viên Văn Thị Thu Thịnh Số hoá bởi Trung tâm Học liệu – ĐHTN http://www.lrc.tnu.edu.vn 5 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.lrc.tnu.edu.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. 1.1. KHÁI QUÁT VỀ MẬT MÃ, MÃ CÔNG KHAI 1.1.1. Khái quát về mật mã 1.1.1.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.lrc.tnu.edu.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á. 1.1.1.2. 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. 2. 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.lrc.tnu.edu.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. 1.1.1.3. 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ể. 2. C tập hữu hạn các bản mã có thể. 3. 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.lrc.tnu.edu.vn 9 4. E là tập các hàm lập mã. 5. 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. 1.1.1.4. 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.lrc.tnu.edu.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. 1.1.2. Khái quát về hệ mã công khai 1.1.2.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ã. Để giải quyết vấn đề phân phối và thoả thuận khoá của mật mã khoá đối xứng, năm 1976 Diffie và Hellman đã đƣa ra khái niệm về hệ mật mã khoá công khai và một phƣơng pháp trao đổi công khai để tạo ra một khoá bí mật chung mà tính an toàn đƣợc bảo đảm bởi độ khó của một bài toán toán học cụ thể (là bài toán tính “lôgarit rời rạc”). Hệ mật mã khoá công khai hay còn đƣợc gọi là hệ mật mã phi đối xứng sử dụng một cặp khoá, khoá mã hoá còn gọi là khoá công khai (public key) và khoá giải mã đƣợc gọi là khoá bí mật hay khóa riêng (private key). Trong hệ mật này, khoá mã hoá khác với khoá giải mã. Về mặt toán học thì từ khoá công khai rất khó tính đƣợc khoá riêng. Biết đƣợc khoá này không dễ dàng tìm đƣợc khoá kia. Khoá giải mã đƣợc giữ bí mật trong khi khoá mã hoá đƣợc công bố công khai. Một ngƣời bất kỳ có thể sử dụng khoá công khai để mã hoá tin tức, nhƣng chỉ có ngƣời nào có đúng khoá giải mã mới có khả năng xem đƣợc bản rõ. Số hoá bởi Trung tâm Học liệu – ĐHTN http://www.lrc.tnu.edu.vn 11 Ngƣời gửi A sẽ mã hoá thông điệp bằng khóa công khai của ngƣời nhận B và ngƣời nhận B sẽ giải mã thông điệp với khoá riêng tƣơng ứng của mình. Quá trình này đƣợc mô tả trong hình 1.2 và 1.3. Hình 1.2: Mã hoá thông điệp sử dụng khoá công khai P Hình 1.3: Giải mã thông điệp sử dụng khoá riêng của ngƣời nhận Có nhiều hệ thống khoá công khai đƣợc triển khai rộng rãi nhƣ hệ RSA, hệ Elgamal sử dụng giao thức trao đổi khoá Diffie-Hellman và nổi lên trong những năm gần đây là hệ mã đƣờng cong Elliptic. Trong số các hệ mật mã trên thì hệ RSA là hệ đƣợc cộng đồng chuẩn quốc tế và công nghiệp chấp nhận rộng rãi trong việc thực thi mật mã khoá công khai. Việc phát minh ra phƣơng pháp mã công khai tạo ra một cuộc “cách mạng” trong công nghệ an toàn thông tin điện tử. Nhƣng thực tiễn triễn khai Số hoá bởi Trung tâm Học liệu – ĐHTN http://www.lrc.tnu.edu.vn 12 cho thấy tốc độ mã hoá khối dữ liệu lớn bằng các thuật toán mã hoá công khai chậm hơn rất nhiều so với hệ mã hoá đối xứng. Ví dụ, để đạt đƣợc độ an toàn nhƣ các hệ mã đối xứng mạnh cùng thời, RSA đòi hỏi thời gian cho việc mã hoá một văn bản lâu hơn gấp hàng ngàn lần. Do đó, thay bằng việc mã hoá văn bản có kích thƣớc lớn bằng lƣợc đồ khoá công khai thì văn bản này sẽ đƣợc mã hoá bằng một hệ mã đối xứng có tốc độ cao nhƣ DES, IDEA,…sau đó khoá đƣợc sử dụng trong hệ mã đối xứng sẽ đƣợc mã hoá sử dụng mật mã khoá công khai. Phƣơng pháp này rất khả thi trong việc mã và giải mã những văn bản có kích thƣớc lớn nhƣ đƣợc mô tả trong hình 1.5 và 1.6. Hình 1.4: Mã hoá thông điệp sử dụng khoá bí mật S để mã thông điệp và khoá công khai P để mã khoá bí mật S. Hình 1.5: Giải mã thông điệp sử dụng khoá bí mật S để giải mã thông điệp và khoá riêng P để giải mã khoá bí mật S. Số hoá bởi Trung tâm Học liệu – ĐHTN http://www.lrc.tnu.edu.vn 13 1.1.2.2. Ƣu và nhƣợc điểm của hệ mật mã khoá công khai Ƣu điểm rõ ràng nhất của hệ mật mã khóa công khai là bảo mật. Một văn bản đƣợc mã hóa bằng khóa công khai của một ngƣời sử dụng thì chỉ có thể giải mã với khóa bí mật của ngƣời đó. Hệ mật mã khoá công khai dựa vào các giả thiết liên quan đến các bài toán khó nên đa số các hệ mật mã này đều có tốc độ dịch mã không nhanh lắm. Chính nhƣợc điểm này làm cho các hệ mật mã khoá công khai khó đƣợc dùng một cách độc lập. Một vấn đề nữa nảy sinh khi sử dụng các hệ mật mã khóa công khai là việc xác thực mà trong mô hình hệ mật mã đối xứng không đặt ra. Do các khoá mã công khai đƣợc công bố một cách công khai trên mạng cho nên việc đảm bảo rằng “khoá đƣợc công bố có đúng là của đối tƣợng cần liên lạc hay không?” là một kẽ hở có thể bị lợi dụng. Vấn đề xác thực này đƣợc giải quyết cũng chính bằng các hệ mật mã khoá công khai. Nhiều thủ tục xác thực đã đƣợc nghiên cứu và sử dụng nhƣ Kerberos, X.509… Một ƣu điểm nữa của các hệ mật mã khoá công khai là các ứng dụng của nó trong lĩnh vực chữ ký số, cùng với các kết quả về hàm băm, thủ tục ký để bảo đảm tính toàn vẹn của một văn bản đƣợc giải quyết. 1.2. BÀI TOÁN LOGARIT RỜI RẠC Lôgarit rời rạc là sự tiếp nối của phép tính lôgarit trên trƣờng số thực vào các nhóm hữu hạn. Ta nhắc lại định nghĩa lôgarit: Với hai số thực x, y và cơ số a dƣơng, a khác 1, nếu ax = y thì x đƣợc gọi là lôgarit cơ số a của y, kí hiệu là x = logay. Lôgarit rời rạc có ứng dụng trong hệ mật mã khóa công khai, hệ mật mã Elgamal. Số hoá bởi Trung tâm Học liệu – ĐHTN http://www.lrc.tnu.edu.vn 14 1.2.1. Định nghĩa Tổng quát, giả sử G là một nhóm cyclic hữu hạn có n phần tử. Zn là vành các số nguyên modun n. Chúng ta kí hiệu phép toán của G theo lối nhân. Giả sử b là một phần tử sinh của G, khi đó mọi phần tử g của G có thể viết dƣới dạng g = bk với một số nguyên k nào đó. Hơn nữa, hai số nguyên có cùng tính chất đó với g là đồng dƣ theo modul n. Ta định nghĩa một ánh xạ: Logb : G → Zn g=bk  k Ánh xạ này là một đồng cấu nhóm, đƣợc gọi là lôgarit rời rạc theo cơ số b. Bài toán tìm ax mod p khi biết a, x, p là bài toán dễ. Nhƣng bài toán ngƣợc là bài toán tìm logarit rời rạc của một số modul p, tức là tìm số nguyên x sao cho: ax = b mod p là bài toán khó giải. Nếu a là căn nguyên tố của p và p là số nguyên tố, thì luôn luôn tồn tại lôgarit rời rạc, ngƣợc lại thì có thể không. Ví dụ: Cho a = 2, x = 4, n = 13 Ta có : 24 mod 13 = 3. Bài toán ngƣợc lại : tìm x để 2x = 3 mod 13 là bài toán lôgarit rời rạc. Ta có: 20 mod 13 = 1, 21 mod 13 = 2, 22 mod 13 = 4, 23 mod 13 = 8, 24 mod 13 = 3. Vậy x = log2 3 mod 13 = 4. Tuy nhiên nếu chon n là số lớn ví dụ tìm x để 2x = 3 mod 19797 thì việc tìm x là rất khó. Số hoá bởi Trung tâm Học liệu – ĐHTN http://www.lrc.tnu.edu.vn 15 Ta nhận thấy, trong khi bài toán lũy thừa là dễ dàng, thì bài toán logarit rời rạc là rất khó. Đây cũng là một cơ sở của mã công khai. 1.2.2. Ứng dụng trong mật mã Lôgarit rời rạc là bài toán khó (chƣa biết một thuật toán hiệu quả nào), trong khi bài toán tính luỹ thừa của một số lại không khó (có thể sử dụng thuật toán bình phƣơng và nhân). Tình trạng này giống nhƣ tình hình giữa bài toán thừa số nguyên và phép nhân các số nguyên. Chúng đều có thể dùng để xây dựng cấu trúc cho một hệ mật mã. Ngƣời ta thƣờng chọn nhóm G trong mật mã lôgarit rời rạc là nhóm cyclic (Zp)* chẳng hạn nhƣ mật mã Elgamal, trao đổi khóa Diffie – Hellman và chữ kí số Elgamal. Ngoài ra còn có mật mã sử dụng lôgarit rời rạc trong nhóm con cyclic của các đƣờng elliptic trên trƣờng hữu hạn gọi là mật mã đƣờng cong elliptic. 1.2.3. Một số thuật toán lôgarit rời rạc 1.2.3.1. Phƣơng pháp đơn định Cho G là nhóm cyclic, a, b  G . Bài toán tìm kiếm nghiệm của phƣơng trình ax = b gọi là bài toán lôgarit rời rạc trong nhóm G. Nghiệm x của phƣơng trình gọi là lôgarit rời rạc cơ số a của b, ký hiệu là logab, nếu nhƣ cơ số a cố định và nếu nhƣ nghiệm của phƣơng trình tồn tại thì loga b  Z G , nếu nhƣ |G|< ∞. Bài toán lôgarit rời rạc có vai trò rất lớn trong ứng dụng của mật mã. Đặc biệt quan trọng trong trƣờng hợp G = F(q)*, với q = pl, p là số nguyên tố, lN, tức là trong trƣờng Galoa, cũng nhƣ trong trƣờng hợp G là một nhóm điểm của đƣờng cong Elliptic trong trƣờng hữu hạn. Số hoá bởi Trung tâm Học liệu – ĐHTN http://www.lrc.tnu.edu.vn 16 Ta xét phƣơng trình ax ≡ b (mod p) (1) trong nhóm Z*p, với p là số nguyên tố. Ta giả sử rằng bậc của a (mod p) bằng p-1. Khi đó phƣơng trình giải đƣợc, và nghiệm x là một phần tử của Zp-1. Trong phần này ta mô tả phƣơng pháp đơn định để xác định nghiệm của (1). Nghiệm logab của phƣơng trình (1) có thể tìm theo công thức sau loga b   (1-a j )-1b j (mod p-1) , Thuật toán tƣơng hợp. Bƣớc 1. Gán H:= p1/2  +1. Bƣớc 2. Tìm c  a H (mod p) . Bƣớc 3. Lập bảng giá trị cu (modp), 1  u  H , sắp xếp nó. Bƣớc 4. Lập bảng giá trị b.a v (modp), 0  v  H , sắp xếp nó. Bƣớc 5. Tìm sự trùng nhau phần tử từ bảng thứ nhất và bảng thứ hai. Để làm điều này cu  b.a v (modp) , từ đây a Hu-v  b(mod p) . Bƣớc 6. Đƣa ra giá trị x  Hu-v(modp-1). Kết thúc thuật toán. 1.2.3.2. Thuật toán Pohlig-Hellman Input: cho số nguyên p Output: phân tích số nguyên p thành thừa số nguyên tố Bây giờ giả sử ta biết đƣợc sự phân tích thành nhân tử của p-1 ra thừa số s p-1= qiαi i=1 Thuật toán Pohlig-Hellman Số hoá bởi Trung tâm Học liệu – ĐHTN http://www.lrc.tnu.edu.vn 17 Bản chất của thuật toán nằm ở chổ, tìm số lƣợng đủ lớn phƣơng trình x theo modulo qi với tất cả i, sau đó tìm nghiệm của phƣơng trình ban đầu bằng i định lý phần dƣ trung hoa. Để tìm x theo một trong các modulo nhƣ thế, ta phải giải đồng dƣ thức (a p-1 α qi i )  (a p-1 α qi i )(modp) Bƣớc 1. Đối với từng số nguyên tố q,q|p-1 , ta lập bảng giá trị rq,j  a j(p-1)/q (modp) , j  0,..., q 1 . Bƣớc 2. Đối với từng số nguyên tố q, qα ||p-1 , ta tìm log a b(mod q α ) . Đặt x  loga b(modqα )  x0 +x1q+...+xα-1qα-1(modqα ) , với 0  xi  q-1. Lúc này từ (1) dẫn đến rằng b(p-1)/q  a x0 (p-1)/q (modp) . Với sự giúp đỡ của bảng trong bƣớc 1 ta tìm ra x0. Lúc này rõ ràng ta có 2 (ba -x0 )(p-1)/q  a x1(p-1)/q (modp) . Theo bảng trong bƣớc 1 ta tìm ra giá trị của x1 và tiếp tục nhƣ thế. Giá trị của xi đƣợc tìm thấy từ phƣơng trình i-1 i+1 (ba -x0 -x1q-...-xi-1q )(p-1)/q  a xi (p-1)/q (modp) . Bƣớc 3. Khi tìm loga b(mod qii ), i  1,..., s , ta tìm log a b(mod p 1) theo định lý phần dƣ trung hoa. Kết thúc thuật toán. 1.2.3.3. Phƣơng pháp ρ - Pollaid đối với logarit rời rạc Ta đã tìm hiểu phƣơng pháp ρ - Pollaid đối với nhân tử hóa số nguyên. Bây giờ ta tìm hiểu về bài toán lôgarit rời rạc theo modulo là số nguyên tố p. Ta muốn giải phƣơng trình a x  b(modp) . Để làm việc này ta xem 3 dãy số Số hoá bởi Trung tâm Học liệu – ĐHTN http://www.lrc.tnu.edu.vn 18 ui,vi,zi , i  0,1,2,..., đƣợc xác định nhƣ sau: u0 =v0 = 0 , z0  1 , ui+1  ui +1(mod p-1) , nếu nhƣ 0 0, L=e logploglogp , 0< ε <1 Hình thành tập hợp Số hoá bởi Trung tâm Học liệu – ĐHTN http://www.lrc.tnu.edu.vn 20 q|q - Xem thêm -