Đăng ký Đăng nhập
Trang chủ Bài toán logarithm rời rạc và hệ mật elgamal có sửa đổi...

Tài liệu Bài toán logarithm rời rạc và hệ mật elgamal có sửa đổi

.PDF
80
366
121

Mô tả:

BỘ GIÁO DỤC VÀ ĐÀO TẠO LÊ THANH PHÚC VIỆN ĐẠI HỌC MỞ HÀ NỘI LUẬN VĂN THẠC SỸ CÔNG NGHỆ THÔNG TIN CHUYÊN NGÀNH CÔNG NGHỆ THÔNG TIN BÀI TOÁN LOGARITHM RỜI RẠC VÀ HỆ MẬT ELGAMAL CÓ SỬA ĐỔI LÊ THANH PHÚC 2015-2017 HÀ NỘI - 2017 BỘ GIÁO DỤC VÀ ĐÀO TẠO VIỆN ĐẠI HỌC MỞ HÀ NỘI LUẬN VĂN THẠC SỸ BÀI TOÁN LOGARITHM RỜI RẠC VÀ HỆ MẬT ELGAMAL CÓ SỬA ĐỔI LÊ THANH PHÚC CHUYÊN NGÀNH: CÔNG NGHỆ THÔNG TIN MÃ SỐ: 60.48.02.018 NGƯỜI HƯỚNG DẪN KHOA HỌC: GS.TS. NGUYỄN BÌNH HÀ NỘI - 2017 LỜI CAM ĐOAN Luận văn thạc sĩ đánh dấu cho những thành quả, kiến thức tôi đã tiếp thu đƣợc trong suốt quá trình rèn luyện, học tập tại trƣờng. Tôi xin cam đoan luận văn “Bài toán Logarithm rời rạc & Hệ mật ElGamal có sửa đổi” đã đƣợc hoàn thành bằng quá trình học tập và nghiên cứu của tôi dƣới sự hƣớng dẫn, góp ý và chỉnh sửa của GS. TS. Nguyễn Bình. Trong toàn bộ nội dung nghiên cứu của luận văn, các vấn đề đƣợc trình bày là những tìm hiểu và nghiên cứu của cá nhân tôi hoặc là trích dẫn các nguồn tài liệu và một số trang web hợp pháp đƣợc đƣa ra ở phần Tài liệu tham khảo. Tôi xin cam đoan những lời trên là sự thật và chịu mọi trách nhiệm trƣớc thầy cô và hội đồng bảo vệ luận văn thạc sĩ. Hà Nội, ngày 12 tháng 12 năm 2017 HỌCVIÊN Lê Thanh Phúc i LỜI CẢM ƠN Học viên xin bày tỏ lời cảm ơn chân thành tới tập thể các thầy cô giáo Viện Đại học Mở Hà Nội và Viện công nghệ thông tin đã mang lại cho học viên kiến thức vô cùng quý giá và bổ ích trong suốt quá trình học tập chƣơng trình cao học tại trƣờng. Đặc biệt học viên xin bày tỏ lòng biết ơn sâu sắc tới thầy giáo GS.TS Nguyễn Bình- Học viện Bƣu chính viễn thông đã định hƣớng khoa học và đƣa ra những góp ý, gợi ý, chỉnh sửa quý báu, quan tâm, tạo điều kiện thuận lợi trong suốt quá trình nghiên cứu hoàn thành luận văn này. Cuối cùng, học viên xin chân thành cảm ơn các bạn bè đồng nghiệp, các bạn học Viên lớp CNTT khóa 2015 - 2017, những ngƣời đồng hành trong suốt khóa học và có nhiều góp ý bổ ích cho tôi. Cảm ơn gia đình và ngƣời thân đã quan tâm, giúp đỡ và chia sẻ với học viên trong suốt quá trình học tập. Do thời gian và kiến thức có hạn nên luận văn chắc không tránh khỏi những thiếu sót nhất định. Học viên rất mong nhận đƣợc những sự góp ý quý báu của thầy cô và các bạn. Một lần nữa học viên xin đƣợc gửi lời cảm ơn chân thành và sâu sắc. Hà Nội, ngày 12 tháng 12 năm 2017 HỌCVIÊN Lê Thanh Phúc ii MỤC LỤC LỜI CAM ĐOAN ....................................................................................................... i LỜI CẢM ƠN ............................................................................................................ ii DANH MỤC CÁC THUẬT NGỮ, CHỮ VIẾT TẮT ................................................v DANH MỤC CÁC BẢNG BIỂU ............................................................................. vi DANH MỤC CÁC HÌNH VẼ.................................................................................. vii MỞ ĐẦU .....................................................................................................................1 CHƢƠNG 1. TỔNG QUAN VỀ BÀI TOÁN LOGARITHM RỜI RẠC VÀ CÁC HỆ MẬT MÃ ..............................................................................................................4 1.1. Tổng quan về bài toán logarithm rời rạc [1] ....................................................4 1.1.1. Bài toán Logarithm trên trƣờng số thực R .................................................4 1.1.2. Bài toán Logarithm trên trƣờng hữu hạn....................................................5 1.1.3. Thuật toán logarithm rời rạc.......................................................................8 1.1.3.1. Phƣơng pháp đơn định .....................................................................8 1.1.3.2. Thuật toán Adleman .......................................................................10 1.1.3.3. Thuật toán vét cạn ..........................................................................11 1.1.3.5. Thuật toán Shank ...........................................................................11 1.1.3.6. Thuật toán tính logarithm rời rạc đối với nhóm cyclic ..................13 1.1.3.7. Tính chỉ số trên GF(p) ....................................................................14 1.1.3.8. Tính chỉ số trên GF(2n) ..................................................................15 1.2. Tổng quan mật mã học [4, Tr.11] ...................................................................17 1.3. Vấn đề về mã hóa [4, Tr.12-15] ......................................................................18 1.3.1. Khái niệm mật mã ....................................................................................18 1.3.2. Khái niệm về mã hóa................................................................................19 1.3.3. Phân loại mã hóa [4, Tr.20-97] ................................................................20 1.3.3.1. Hệ mã hóa khóa đối xứng ..............................................................20 1.3.3.2. Hệ mã hóa khóa bất đối xứng ........................................................24 Hệ mật đƣờng cong Eliptic ...............................................................................30 Hệ mã hóa RSA [4, tr.74-79]............................................................................31 Hệ mã hóa Paillier ............................................................................................32 iii 1.4. Lý thuyết độ phức tạp của thuật toán [1] ........................................................33 1.5. Kết luận chƣơng 1 ...........................................................................................36 CHƢƠNG 2. XÂY DỰNG HỆ MẬT ELGAMAL CÓ SỬA ĐỔI ..........................38 2.1. Hệ mật mã Elgamal [2, tr.5]............................................................................38 2.1.1. Thuật toán mật mã ElGamal cổ điển ..........................................................38 2.2. Hệ mã hóa ElGamal sửa đổi ...........................................................................43 2.2.1. Thuật toán thứ nhất [5] ...............................................................................43 2.2.2. Thuật toán thứ hai [3, tr.17-20]...................................................................45 2.3. Chƣơng trình thực nghiệm hệ mã hóa công khai Elgamal sửa đổi .................49 2.4. Kết luận chƣơng 2 ...........................................................................................51 CHƢƠNG 3. PHÂN TÍCH HIỆU NĂNG AN TOÀN CỦA HỆ MẬT ELGAMAL CÓ SỬA ĐỔI & ỨNG DỤNG TRONG KỸ THUẬT MÃ HÓA PGP ĐỂ BẢO MẬT EMAIL ............................................................................................................52 3.1 Đánh giá Hệ mật ElGamal [5] ........................................................................52 3.2 Hệ mật ElGamal sửa đổi: ................................................................................53 3.3 Tìm hiểu kỹ thuật mã hóa PGP sử dụng hệ mã hóa khóa công khai Elgamal, RSA trong mã hóa Email [13] ...................................................................................55 3.3.1. Giới thiệu về hệ mã hóa PGP ...................................................................55 3.3.2. Các thuật toán sử dụng trong PGP ...........................................................55 3.4 Tổng kết chƣơng 3 ..........................................................................................69 KẾT LUẬN VÀ HƢỚNG NGHIÊN CỨU TIẾP THEO .........................................70 1. Hạn chế:....................................................................................................70 2. Hƣớng phát triển ......................................................................................70 TÀI LIỆU THAM KHẢO .........................................................................................71 Tiếng Việt .............................................................................................................71 Tiếng nƣớc ngoài ..................................................................................................71 Internet ..................................................................................................................71 iv DANH MỤC CÁC THUẬT NGỮ, CHỮ VIẾT TẮT STT Từ viết tắt Tiếng Anh Tiếng Việt 1 CA Certificate Authority Cơ quan chứng thực chữ ký số 2 DS Digital Signatures Chữ ký số 3 DSA Digital Signature Algorithm Giải thuật chữ ký điện tử 4 DES Data Encryption Standard Chuẩn mã hóa dữ liệu 5 EMAIL Electronic Mail Thƣ điện tử 6 ID 7 RSA Rivest, Shamir and Adleman 8 PGP Pretty Good Privacy 9 PKI Public Key Infrastructure Cơ sở hạ tầng khóa công khai 10 SHA Secure Hash Algorithm Giải thuật băn an toàn 11 SSL Secure Socket Layer Giao thức an ninh thông tin 12 UCLN Gcd Ƣớc chung lớn nhất 13 XCB 14 NSA Chỉ danh ngƣời dùng trên mạng Giải thuật mã hóa công khai Phần mềm mã hóa dữ liệu và xác thực Xyclic cục bộ National Security Agency v Cơ quan An ninh Quốc gia Mỹ DANH MỤC CÁC BẢNG BIỂU Trang Bảng 1.1. Các giá trị của y = 2x mod 19 trên Z*19 .................................................... 05 Bảng 1.2. Các giá trị log2x(mod 19) trên Z*19 ......................................................... 06 Bảng 1.3. Bài toán logarithm rời rạc trên Z*19......................................................... 07 Bảng 1.4. Bảng chi phí thời gian phân tích sốnguyên n ra thừa số nguyên tố ......... 34 Bảng 3.1. Bảng so sánh tốc độ mã hóa .................................................................... 53 Bảng 3.2. Bảng so sánh tốc độ giải mã .................................................................... 53 Bảng 3.3. Bảng kết quả so sánh thời gian mã hóa của hệ mật trƣớc và sau sửa đổi 54 vi DANH MỤC CÁC HÌNH VẼ Trang Hình 1.1. Đồ thị hàm số y=ax và y = logax ............................................................. 05 Hình 1.2. Quá trình mã hoá và giải mã .................................................................... 20 Hình 1.3. Sơ đồ hoạt động của mã hóa khóa đối xứng ............................................ 21 Hình 1.4. Sơ đồ hoạt động của mã hóa khóa bất đối xứng ...................................... 25 Hình 1.5. Mã hoá thông điệp sử dụng khoá công khai ............................................ 26 Hình 1.6. Giải mã thông điệp sử dụng khoá riêng của ngƣời nhận ......................... 26 Hình 1.7. Hệ mật Omura- Massey xây dựng trên bài toán lôgarith rời rạc ............. 29 Hình 1.8. Quá trình truyền tin sử dụng hệ mật Omura – Massey ............................ 29 Hinh 2.1. Hệ mã Emlgamal ...................................................................................... 40 Hình 2.2. Sơ đồ chứng nhận khóa công khai ........................................................... 42 Hình 2.3. Giao diện sinh khóa .................................................................................. 49 Hình 2.4. Kết quả sinh khóa ..................................................................................... 50 Hình 2.6. Mã hóa và giải mã .................................................................................... 50 Hình 3.1. Quá trình mã hóa một thông điệp trong PGP ........................................... 56 Hình 3.2. Quá trình giải mã một thông điệp trong PGP........................................... 58 vii MỞ ĐẦU 1. Tính cấp thiết của đề tài Cùng với sự phát triển của công nghệ thông tin và truyền thông, mạng máy tính đang trở thành một phƣơng tiện điều hành thiết yếu trong mọi lĩnh vực hoạt động của xã hội. Việc trao đổi thông tin và dữ liệu trong môi trƣờng mạng ngày càng trở nên phổ biến và đang dần thay thế các phƣơng thức truyền tin trực tiếp. Khi ngày càng nhiều thông tin đƣợc trao đổi thì nhu cầu về bảo mật thông tin là một vấn đề đặt ra cho nhiều ngành, lĩnh vực và nhiều quốc gia...Để bảo vệ các thông tin khỏi sự truy cập trái phép cần phải kiểm soát đƣợc những vấn đề nhƣ: thông tin đƣợc tạo ra, lƣu trữ và truy nhập nhƣ thế nào, ở đâu, bởi ai và vào thời điểm nào. Giải quyết các vấn đề trên, kỹ thuật mật mã hiện đại phải đảm bảo các dịch vụ an toàn cơ bản: (1) bí mật (Confidential); (2) xác thực (Authentication); (3) đảm bảo tính toàn vẹn (Integrity). Hệ mật mã ra đời nhằm đảm bảo các dịch vụ an toàn cơ bản trên nhƣ: hệ mật mã với khóa sở hữu riêng (Private Key Cryptosystems), hệ mã với khóa bí mật (Secret Key Cryptosystems), hệ mã truyền thống (Conventional Cryptosystems) đều là những hệ mật mã sử dụng mã khóa đối xứng. Hệ mật mã với khóa công khai cho phép ngƣời sử dụng trao đổi các thông tin mật mà không cần phải trao đổi các khóa chung bí mật trƣớc đó; mật mã hóa khóa công khai đƣợc thiết kế sao cho khóa sử dụng trong quá trình mã hóa khác biệt với khóa sử dụng trong quá trình giải mã; khóa sử dụng dùng để mã hóa và ngƣợc lại, tức là hai khóa này có quan hệ với nhau về mặt toán học nhƣng không thể suy diễn đƣợc ra nhau. Một trong những thuật toán mã khóa công khai đƣợc phát triển dựa trên Hệ mật mã ElGamal cho phép giải quyết tốt các yêu cầu bảo mật thông tin thực hiện đồng thời việc xác thực về nguồn gốc và tính toàn vẹn của thông tin. Luận văn sẽ trình bày về hệ mật mã ElGamal và xem xét các biến thể của nó. 2. Mục tiêu, đối tƣợng, phạm vi và phƣơng pháp nghiên cứu Mục tiêu nghiên cứu: Tìm hiểu hoạt động của hệ mật mã khóa công khai và các biến thể thuật toán ElGamal để đƣa ra sửa đổi đối với hệ mật. Đánh giá tính bảo 1 mật thông tin, xác thực về nguồn gốc thông tin, xác thực về tính toàn vẹn của thông tin của hệ thống. Đối tượng nghiên cứu: Hệ mật mã ElGamal là đối tƣợng chính nghiên cứu của đề tài nhằm phát hiện các phƣơng pháp tấn công qua đó tìm hiểu các ứng dụng thử nghiệm đánh giá mã hóa với thuật toán ElGamal. Phạm vi nghiên cứu: Đề tài nghiên cứu và đánh giá hiệu quả tính an toàn của hệ mật ElGamal sửa đổi. Xây dựng hoặc tìm hiểu các thuật toán thử nghiệm trên chữ ký số giúp tăng tính an toàn cho chữ ký số Elgamal/ RSA. Phương pháp nghiên cứu * Phương pháp lý thuyết - Tìm hiểu nghiên cứu về mật mã, cơ sở toán học của hệ mật mã - Tìm hiểu bài toán logarithm rời rạc và hệ mật ElGamal; thủ tục trao đổi khóa Diffie- Hellman; các phƣơng pháp che giấu dữ liệu và các điều kiện lũy đẳng và giao hoán của các hệ mật. - Lý thuyết chung về hệ mật khóa công khai từ đó đƣa ra những sửa đổi của hệ mật ElGamal. * Phương pháp thực nghiệm - Sửa đổi hệ mật bằng cách giữ nguyên cấu trúc trao đổi khóa Diffie-Hellman, sửa đổi kiểu che giấu dữ liệu. - Đánh giá hiệu quả và tính an toàn của Hệ mật ElGamal. 3. Cấu trúc luận văn Luận văn đƣợc tác giả trình bày trong 3 chƣơng, có phần mở đầu, danh mục hình vẽ, danh mục từ viết tắt, danh mục bảng, phần kết luận, phần mục lục, phần tài liệu tham khảo. Các nội dung cơ bản của luận văn đƣợc trình bày theo cấu trúc sau: Chƣơng 1: Tổng quan về bài toán Logarithm rời rạc và các hệ mật mã Trong chƣơng này, luận văn trình bày một số khái niệm cơ bản trong toán học mà các hệ mã hoá thƣờng sử dụng nhƣ: modulo, số nguyên tố, vành Zn, các phép toán cộng, nhân, bài toán logarithm rời rạc trên không gian Zn, Zn*,...Sau đó đƣa ra các khái niệm mật mã, các thuật toán mã hoá, chữ ký số phục vụ cho việc mã hoá và giải mã thông tin. 2 Chƣơng 2: Xây dựng hệ mật Elgamal có sửa đổi Tập trung nghiên cứu hệ mật mã Elgamal cổ điển và đƣa ra những đánh giá về ƣu nhƣợc điểm từ đó đƣa ra những sửa đổi đối với thuật toán hệ mật mã khóa công khai ElGamal, tính chất đồng cấu của hệ mật mã ElGamal và sơ đồ chia sẻ bí mật theo ngƣỡng Shamir. Chƣơng 3: Phân tích hiệu năng an toàn của hệ mật Elgamal có sửa đổi và tìm hiểu các ứng dụng có sử dụng thuật toán mã hóa khóa công khai Cài đặt thử nghiệm chƣơng trình mô phỏng thuật toán hệ mật mã khóa công khai ElGamal sửa đổi và kỹ thuật chia sẻ khóa bí mật. Demo ứng dụng mã hóa và giải mã trong việc gửi nhận thƣ điện tử. 3 CHƢƠNG 1. TỔNG QUAN VỀ BÀI TOÁN LOGARITHM RỜI RẠC VÀ CÁC HỆ MẬT MÃ 1.1. Tổng quan về bài toán logarithm rời rạc [1] Bài toán Logarithm rời rạc là sự kết nối của phép tính logarithm trên trƣờng số thực vào các nhóm hữu hạn. Với hai số thực x,y và cơ số a>0, a 1, nếu ax - y =0 thì x đƣợc gọi là logarithm cơ số a của y, ký hiệu x = logay. Bài toán logarithm rời rạc là bài toán khó. Trong khi bài toán ngƣợc lũy thừa rời rạc lại không khó (có thể sử dụng thuật toán bình phƣơng và nhân). 1.1.1. Bài toán Logarithm trên trường số thực R Bài toán thuận: Hàm số y =ax với a,x R việc tính toán hàm mũ này có thể đƣợc thực hiện dễ dàng bằng thuật toán nhân và bình phƣơng. Ví dụ 1: Cho p là một số nguyên tố, xét nhóm nhân các số nguyên modulo p: Zp* = { 1,2….,p } với phép nhân modulo p. Nếu ta tính lũy thừa bậc k của một số trong nhóm rồi rút gọn theo modulo p thì ta đƣợc một số trong nhóm đó. Quá trình này đƣợc gọi là lũy thừa rời rạc modulo p. Chẳng hạn với p = 17, lấy a = 3, k = 4 ta có: 34 = 81 = 13 mod 17. Logarithm rời rạc là phép tính ngƣợc lại : Biết: 3k = 13 (mod 17) hãy tìm k?  Thực hiện tƣơng tự nhƣ thuật toán Shank → k=4. Tuy nhiên đây là một bài toán tƣơng đối khó. Trong trƣờng hợp p lớn (có ít nhất 150 chữ số) thì bài toán trở thành bất khả thi → an toàn. Bài toán ngƣợc: Phép tính ngƣợc của hàm mũ chính là hàm logarithm y= logax, việc tính toán hàm ngƣợc logarithm này khó khăn hơn nhiều so với hàm thuận. Tuy nhiên, cả hai phép mũ và logarithm đều là các hàm đồng biến cho nên có thể xác định giá trị tƣơng đối của hàm logarithm nhƣ hình dƣới đây 4 Hình 1.1: Đồ thị hàm số y=ax và y = logax Một số tính chất của hàm logarithm.  y =logabc =logab +logac  y = loga = logab - logac  loga1 = 0  y = logax -1 = - logax. Bài toán Logarithm trên trường hữu hạn 1.1.2. Xét với vành đa thức Zp* với p là số nguyên tố thì theo định lý nếu p là nguyên tố thì Zp là một trƣờng (Zp = GF(2)). Tập tất cả các phần tử khác không của trƣờng sẽ tạo nên một nhóm nhân xyclic Z*p. Z*p= Zp/{0}={1,2,...,p -1}  Bài toán thuận: y = ax mod p, (a,x Z*p) Ví dụ 2: Xét p = 19, a = 2 ta có các giá trị y = ax nhƣ trong bảng dƣới đây: x 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 2x 2 4 8 16 13 7 14 9 18 17 15 11 3 6 12 5 10 1 Bảng 1.1: Các giá trị của y = 2x mod 19 trên Z*19 Chú ý: + Nếu a là một phần tử nguyên thủy thì ax sẽ đi qua tất cả các phần tử của nhóm. 5 + Nếu a là phần tử nguyên thủy thì ai cũng là nguyên thủy với (i,p-1)= 1(p là số nguyên tố). Trong ví dụ trên các giá trị của i thỏa mãn (i, 18)=1 là i = (1,5,7,11,13,17). Số lƣợng các giá trị của i bằng giá trị hàm (p-1). Ni = (p-1) = (18)=6 Cách tính hàm Phi-Euler nhƣ sau: (1)= 1, và (n) = (p-1)pk-1 với n là lũy thừa bậc k của số nguyên tố p; nếu m và n là hai số nguyên tố cùng nhau thì (mn)= (m). (n) Nếu n = P1k1 ............. prkr trong đó các Pjlà các số nguyên tố phân biệt thì (n) = (p1- 1)p1k1-1 .............. (P1- 1)prkr-1 (n) = n ∏ p|n Nhƣ vậy trong nhóm Z*19 có 6 phần tử nguyên thủy: 2 = 2i ; 13 = 25; 14 = 27; 15 = 211; 3 = 213; 10 = 217 Các phần tử nguyên thủy này tạo thành các cặp nghịch đảo nhƣ sau: (2,10) 2 = 10-1 (13,3) 13 = 3-1 14 = 15-1 (14,15)  Bài toán ngƣợc: y = logax, (a,x Z*p) Từ bảng trên ta tính đƣợc giá trị hàm log2x nhƣ sau: x 1 2 3 4 5 6 7 8 2x 2 4 8 16 13 7 14 9 18 17 15 11 3 6 12 5 10 1 log2x 18 1 13 2 16 14 6 5 7 11 4 10 9 3 9 8 10 11 12 13 14 15 16 17 18 17 12 15 Bảng 1.2: Các giá trị log2x(mod 19) trên Z*19 Vì 218 = 1 nên log21 = 18 Một số tính chất của hàm logarit rời rạc a-1 + y = logabc = (logab + logac)modp- 1 + y = loga = (logab - logac)modp-1 + loga-1x = - logax = p - 1 - loga + loga1 = 0 = p - 1( coi 0 = p - 1) Nhận xét: Từ hai bảng trên ta thấy hai hàm thuận và ngƣợc đều không phải là 6 hàm đồng biến, khi biết bài toán thuận thì mới tìm đƣợc bài toán ngƣợc. Do đó việc giải bài toán ngƣợc giống bài toán vét cạn, phải thử lần lƣợt các trƣờng hợp. Việc xác định logarithm của một phần tử bất kỳ trong trƣờng hợp là bài toán khó giải. Bài toán thuận: Cho Z*pvới plà số nguyên tố, a là một phần tử nguyên thủy a Z*p. Yêu cầu tìm y = logax với a, x Z*p. Nhận xét: x Z*p thì: - Bài toán có nghiệm khi α là phần tử nguyên thủy - Bài toán có thể không có nghiệm khi α là phần tử bất kỳ Ví dụ: Với trƣờng hợp p = 19 ta đã tính đƣợc 6 phần tử nguyên thủy nhƣ trong bảng 1.1. Ta sẽ đi tìm bài toán logarithm rời rạc với cơ số 6 phần tử nguyên thủy này. Tuy nhiên ta có thể áp dụng tính chất của hàm logarithm rời rạc để tính logarithm với cơ số là các cặp số nghịch đảo. loga-1x= - logax = p - 1 - logax, hayloga-1x+ logax = p - 1 Tức là (2,10) là cặp số nghịch đảo, khi đó log10x = p - 1 - log2x = 18 - log2x Tƣơng tự (13,3) và (14,15)là các cặp nghịch đảo nênlog3x = 18 - log13x và log15x = 18 - log14x Với quy tắc nhƣ thế có thể tính đƣợc các giá trị logarithm nhƣ trong bảng dƣới đây: x 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 2 x 2 4 8 16 13 7 14 9 18 17 15 11 3 6 12 5 10 1 log2x 18 1 13 2 16 14 6 3 8 17 12 15 5 7 11 4 10 9 log10x 18 17 5 16 2 4 12 15 10 1 6 3 13 11 7 14 8 9 13x 13 17 12 4 14 11 10 16 18 6 2 7 15 5 8 9 3 1 log13x 18 11 17 4 14 10 12 15 16 7 6 3 1 5 13 8 2 9 log3x 18 7 1 14 4 8 6 3 2 11 12 15 17 13 5 10 16 9 14x 14 6 8 17 10 7 3 4 18 5 13 11 2 9 12 16 15 1 log14x 18 13 7 8 10 2 6 3 14 5 12 15 11 1 17 16 4 9 log15x 18 5 11 10 8 16 12 15 4 13 6 3 7 17 1 2 14 9 * Bảng 1.3. Bài toán logarithm rời rạc trên Z 7 19 Có thể tính 13x thông qua 2x, ta thấy 13 = 25 do đó 13x= 25x, tƣơng tự nhƣ thế có thể tính 14x= 27x Phương pháp – Pollaid đối với bài toán logarithm rời rạc Bài toán logarithm rời rạc theo modulo là số nguyên tố p. Chúng ta muốn giải phƣơng trình ax b(modp). Để làm việc này chúng ta xem 3 dãy số:{ui}, {vi}, {zi}, i = 0,1,2,...,Đƣợc xác định nhƣ sau: u0=v0=0, z0=1 ui+1 ui + 1(modp-1), nếu nhƣ 0 p. Từ đây dẫn đến sự đúng đắn của thuật toán. Đánh giá độ phức tạp của thuật toán cũng rõ ràng đúng, bởi vì tập từ N phần tử có thể sắp xếp cần O(N log N) lệnh số học. 1.1.3.2. Thuật toán Adleman Trong phần này chúng ta xem thuật toán giải phƣơng trình ax ≡ b(modp) (3.2) ở đây p là số nguyên tố. Thuật toán này có độ phức tạp là Lp[ ;c]với một số giá trị của hằng số c. Chúng ta cho rằng a(mod p) có bậc là p-1. Thuật toán Tầng 1. Hình thành cơ sở nhân tử, bao gồm tất cả các số nguyên tố q, √ Q≤B= Tầng 2. Bằng cách chọn lựa chúng ta tìm số tự nhiên risao cho ari≡  q aiq (mod p) ,q là số nguyên tố qB Từ đây dẫn đến (3.3), q là số nguyên tố Tầng 3. Chọn số lƣợng đủ lớn biểu thức (3.3), giải hệ phƣơng trình tuyến tính thu đƣợc ứng với các ẩn logaq -logarithmh rời rạc của phần tử của cơ sở nhân tử. Tầng 4. Bằng cách lựa chọn chúng ta tìm ra một giá trị của r, sao cho ar.b ≡ q q . p1... pk (modp) q B ở đây p1,.., pk - là các số nguyên tố với độ lớn “trung bình”, có nghĩa B < pi< B1, với B = √ Tầng 5. Bằng cách tính toán tƣơng tự nhƣ tầng 2 và 3 của thuật toán, tìm ra logarithm rời rạc logapi đối với các số nguyên tố p1,...,pk ở tầng 4. Tầng 6. Xác định giá trị cần tìm logab: 10 Kết thúc thuật toán. 1.1.3.3. Thuật toán vét cạn Đây là thuật toán tự nhiên nhất và kém hiệu quả nhất để tính logarithmth rời rạc. Ngƣời ta cứ thử tính 0, 1, 2, … cho đến khi nào đạt đƣợc β thì thôi. Phƣơng pháp này đòi hỏi O(n) phép toán nhân với n là cấp của α và do đó không hiệu quả khi n lớn và rõ ràng là hàm mũ thực sự theo logn. 1.1.3.4. Thuật toán bƣớc đi lớn bƣớc đi nhỏ (Baby-step giant-step) Giả sử m = [√ ] với n là cấp của α. Thuật toán bƣớc đi lớn bƣớc đi nhỏ là sự thoả hiệp giữa thời gian và bộ nhớ của phƣơng pháp vét cạn và dựa trên quan sát sau là nếu β = αx thì chúng có thể viết: x = im + j với 0  i,j < m. Từ đó x= im j hay ( -m)i = j. Vậy nên ngƣời ta có thể lập bảng (j, j) với 0  j < m. Sau đó lần lƣợt tính β( -m)-i với i lần lƣợt chạy từ 0 đến (m – 1) và tra trong bảng (j, j) chừng nào có đƣợc đẳng thức β( -m)i = αj thì dừng lại. Thuật toán này đòi hỏi không gian lƣu trữ là O(√ ) phần tử nhóm và đòi hỏi O(√ ) phép nhân để xây dựng và O(√ logn) phép so sánh để sắp xếp. Ngoài ra nó cũng cần O(√ ) phép toán nhân và O(√ ) phép toán tra bảng. Tựu chung là nó có thời gian chạy O(√ ) phép toán nhóm. 1.1.3.5. Thuật toán Shank Thuật toán này có tên gọi khác là thuật toán thời gian và bộ nhớ. Tƣ tƣởng của thuật toán là nếu ta có đủ bộ nhớ thì có thể sử dụng bộ nhớ đó để giảm thời gian thực hiện của thuật toán. Input: Số nguyên tố p, phần tử nguyên thủy a cua Z*p, số nguyên y. Output: Cần tìm a sao cho beta =alphaa mod p Thuật toán : Gọim = [(p-1)1/2](lấy phần nguyên).  Bƣớc 1: Tính alphamj mod p với 0 ≤ j ≤ m-1. 11
- Xem thêm -

Tài liệu liên quan