Tài liệu Tìm hiểu chữ ký số và ứng dụng của nó

ĐẠI HỌC QUỐC GIA HÀ NỘI TRƯỜNG ĐẠI HỌC CÔNG NGHỆ NGUYỄN VĂN LIỆU TÌM HIỂU CHỮ KÝ SỐ VÀ ỨNG DỤNG CỦA NÓ LUẬN VĂN THẠC SĨ HÀ NỘI - 2009 ĐẠI HỌC QUỐC GIA HÀ NỘI TRƯỜNG ĐẠI HỌC CÔNG NGHỆ NGUYỄN VĂN LIỆU TÌM HIỂU CHỮ KÝ SỐ VÀ ỨNG DỤNG CỦA NÓ Ngành: Công nghệ thông tin Chuyên ngành: Truyền dữ liệu và Mạng máy tính Mã số: 60 48 15 LUẬN VĂN THẠC SĨ NGƢỜI HƢỚNG DẪN KHOA HỌC TS. HỒ VĂN CANH HÀ NỘI - 2009 MỤC LỤC LỜI CAM ĐOAN .............................................................................................................................. LỜI CẢM ƠN.................................................................................................................................... MỤC LỤC ...................................................................................................................................... iii DANH MỤC CÁC KÝ HIỆU, CÁC CHỮ VIẾT TẮT .................................................................. v DANH MỤC CÁC HÌNH VẼ, ĐỒ THỊ ....................................................................................... vii MỞ ĐẦU ......................................................................................................................................... 1 CHƢƠNG 1: CÁC KHÁI NIỆM TOÁN HỌC CƠ BẢN ............................................................... 2 1. 1 CÁC CẤU TRÚC ĐẠI SỐ................................................................................................... 2 1.1.1 Nhóm .............................................................................................................................. 2 1.1.2 Vành ............................................................................................................................... 2 1.1.3 Trƣờng ............................................................................................................................ 2 1.2 SỐ HỌC TRÊN MODULO ................................................................................................... 3 1.2.1 Định nghĩa Modulo ......................................................................................................... 3 1.2.2 Các phép toán số học trên Modulo ................................................................................. 3 1.2.3 Tính chia hết của các số nguyên - Thuật toán Euclide ................................................... 3 1.3 TRƢỜNG GALOA ............................................................................................................... 4 1.3.1 Trƣờng Galoa.................................................................................................................. 5 1.3.2 Tìm số nghịch đảo .......................................................................................................... 5 1.3.3 Số học đa thức ................................................................................................................ 5 1.3.4 Phép toán đa thức với Modulo đa thức ........................................................................... 6 1.4 LÝ THUYẾT SỐ ................................................................................................................... 7 1.4.1 Các số nguyên tố ............................................................................................................ 7 1.4.2 Phân tích ra thừa số nguyên tố........................................................................................ 7 1.4.3 Các số nguyên tố cùng nhau và GCD ............................................................................. 7 1.4.4 Định lý Ferma (Định lý Ferma nhỏ) ............................................................................... 7 1.4.5 Hàm Ole.......................................................................................................................... 8 1.4.6 Định lý Ole ..................................................................................................................... 8 1.4.7 Kiểm tra tính nguyên tố .................................................................................................. 8 1.4.8 Định lý phần dƣ Trung Hoa ............................................................................................ 9 1.4.9 Căn nguyên tố ............................................................................................................... 10 1.4.10 Logarit rời rạc ............................................................................................................. 10 CHƢƠNG 2: MẬT MÃ, HÀM BĂM ........................................................................................... 10 2.1 HỆ MẬT MÃ KHOÁ CÔNG KHAI................................................................................... 10 2.1.1 Giới thiệu ...................................................................................................................... 10 2.1.2 Hệ mật mã RSA [3] ...................................................................................................... 11 2.1.3 Hệ mật mã Elgamal [3]................................................................................................. 12 2.1.4 Hệ mật mã Rabin [3] .................................................................................................... 15 2.1.5 Các hệ mật mã dựa trên các bài toán NP-đầy đủ [3] .................................................... 16 2.1.6 Các Hệ mật mã xác suất [3] .......................................................................................... 18 2.2 HỆ MẬT TRÊN ĐƢỜNG CONG ELLIPTIC .................................................................... 21 2.2.1 Cơ bản về đƣờng cong Elliptic ..................................................................................... 21 2.2.2 Các hệ mật dựa trên đƣờng cong Elliptic [4] ............................................................... 23 2.2.3 Đánh giá hệ mật ECC ................................................................................................... 25 2.3 HỆ MẬT TRÊN KHÔNG GIAN KHÔNG GIAO HOÁN ................................................. 26 2.3.1 Giới thiệu chung ........................................................................................................... 26 2.3.2 Hệ mã hoá khoá công khai trên nhóm Bện [6] ............................................................. 27 2.4 HÀM BĂM .......................................................................................................................... 29 2.4.1 Đặt vấn đề ..................................................................................................................... 29 2.4.2 Hàm băm MD5 ............................................................................................................. 30 2.4.4 Hàm băm Davies – Mayer và ứng dụng của TT Rijndael vào hàm băm ..................... 33 2.4.5 Các hàm băm sử dụng thuật toán Rijndael ................................................................... 34 CHƢƠNG 3: CÁC MÔ HÌNH CHỮ KÝ SỐ ............................................................................... 35 3.1 TỔNG QUAN VỀ CHỮ KÝ SỐ......................................................................................... 35 3.1.1 Giới thiệu về chữ ký số ................................................................................................. 35 3.1.2 Định nghĩa lƣợc đồ chữ ký số ....................................................................................... 35 3.1.3 Phân loại chữ ký số ....................................................................................................... 36 3.1.4 Tầm quan trọng và ý nghĩa thực tiễn của chữ ký số ..................................................... 39 3.2 CÁC LƢỢC ĐỒ CHỮ KÝ SỐ CƠ BẢN ........................................................................... 43 3.2.1 Lƣợc đồ RSA [3] .......................................................................................................... 43 3.2.2 Lƣợc đồ Elgamal [3] ..................................................................................................... 43 3.2.3 Lƣợc đồ chữ ký số chuẩn DSS [3]................................................................................ 44 3.3 LƢỢC ĐỒ CHỮ KÝ SỐ TRÊN EC ................................................................................... 45 3.3.1 Lƣợc đồ chữ ký ECDSA [4] ......................................................................................... 45 3.3.2 Lƣợc đồ ký mù Harn trên EC [4].................................................................................. 46 3.3.3 Lƣợc đồ chữ ký Nyberg – Rueppel trên EC ................................................................. 47 3.4 LƢỢC ĐỒ CHỮ KÝ SỐ TRÊN KHÔNG GIAN KHÔNG GIAO HOÁN ........................ 48 3.4.1 Giao thức trao đổi khoá mật trên không gian không giao hoán ................................... 48 3.4.2 Lƣợc đồ chữ ký số trên không gian không giao hoán .................................................. 49 3.5 MỘT SỐ LƢỢC ĐỒ CHỮ KÝ SỐ KHÁC ........................................................................ 50 3.5.1 Lƣợc đồ chữ ký số Rabin [3] ........................................................................................ 50 3.5.2 Lƣợc đồ chữ ký số Schnorr [3] ..................................................................................... 51 3.5.3 Lƣợc đồ chữ ký số một lần [5] ..................................................................................... 51 3.5.4 Lƣợc đồ chữ ký số Fail – Stop...................................................................................... 53 3.5.5 Lƣợc đồ chữ ký uỷ nhiệm ............................................................................................. 55 CHƢƠNG 4: CHỮ KÝ CHỐNG CHỐI BỎ VÀ ỨNG DỤNG.................................................... 56 4.1 ĐẶT VẤN ĐỀ ..................................................................................................................... 57 4.2 LỊCH SỬ PHÁT TRIỂN CỦA CHỮ KÝ CHỐNG CHỐI BỎ [32] ................................... 57 4.3 LƢỢC ĐỒ CHỮ KÝ CHỐNG CHỐI BỎ .......................................................................... 60 4.3.1 Lƣợc đồ chữ ký Chaum-van Antverpen [3] ................................................................. 60 4.3.2 Tính hợp thức của các giao thức ................................................................................... 60 4.3.3 Tính an toàn của Lƣợc đồ chữ ký Chaum-van Antverpen ........................................... 62 4.4 MỘT SỐ BIẾN THỂ CỦA LƢỢC ĐỒ CHỮ KÝ CHỐNG CHỐI BỎ .............................. 63 4.4.1 Chữ ký chống chối bỏ Zero-Knowledge ...................................................................... 63 4.4.2 Chữ ký chống chối bỏ có thể chuyển đổi ..................................................................... 66 4.4.3 Chữ ký chống chối bỏ với ngƣời chứng minh phân tán ............................................... 67 4.4.4 Chữ ký chống chối bỏ trên EC ..................................................................................... 70 4.4.5 Chữ ký với ngƣời thẩm định đƣợc chỉ định.................................................................. 72 4.5 ỨNG DỤNG CỦA LƢỢC ĐỒ CHỮ KÝ CHỐNG CHỐI BỎ .......................................... 76 4.5.1 Nhận xét chung ............................................................................................................. 76 4.5.2 Một số ứng dụng chung ................................................................................................ 77 KẾT LUẬN ................................................................................................................................... 83 1. CÁC VẤN ĐỀ ĐƢỢC TÌM HIỂU TRONG LUẬN VĂN ................................................... 83 2. HƢỚNG NGHIÊN CỨU TIẾP THEO ................................................................................. 84 TÀI LIỆU THAM KHẢO ............................................................................................................. 85 DANH MỤC CÁC KÝ HIỆU, CÁC CHỮ VIẾT TẮT CHỮ VIẾT TẮT TỪ GỐC NGHĨA TIẾNG VIỆT 3-DES Triple Data Encrytion Standard Áp dụng giải thuật DES 3 lần cho mỗi khối dữ liệu AES Advanced Encryption Standard Hệ mật mã tiên tiến CDP Conjugacy Decision Problem Vấn đề phân xử liên hợp CDP Conjugacy Decomposition Problem Vấn đề phân tích liên hợp CSP Conjugacy Search Problem Vấn đề tìm kiếm liên hợp DES Data Encryption Standard Hệ mật mã chuẩn DLP Discrete Logarithm Problem Vấn đề Logarit rời rạc DSS Digital Signature Standard Chuẩn chữ ký số DVS Designated Verifier Signature Chữ ký ngƣời thẩm định đƣợc chỉ định ECC Elliptic curve cryptography Hệ mã hóa đƣờng con Elliptic ECDSA Elliptic Curve Digital Signature Algorithm Elliptic Discrete Logarithm Thuật toán ký trên EC EDLP Vấn đề Logarith rời rạc trên EC Problem GCD Greatest Common Divisor GCSP Generalized Conjugacy Search Problem Ƣớc số chung lớn nhất Vấn đề tìm kiếm liên hợp suy rộng IFP Integer Factorization Problem Vấn đề phân tích thừa số nguyên LCM Least Common Multiple Bội số chung nhỏ nhất LHS Left Hand Side Phía bên trái MUO M. Mambo, K. Usuda, E. Okamoto Lƣợc đồ ký uỷ nhiệm đƣợc đề xuất bởi M. Mambo, K. Usuda và E. Okamoto RHS Right Hand Side Phía bên phải RSA Ron Rivest, Adi Shamir, Len Adleman Thuật toán mã hóa khóa công khai do 3 tác giả Ron Rivest, Adi Shamir, Len Adleman đề xuất SDVS Strong Designated Verifier Signature Chữ ký ngƣời thẩm định đƣợc chỉ định mạnh SHA Secure Hash Algorithm Thuật toán hàm băm an toàn TTP Trusted Third Party Thành phần thứ ba tin cậy DANH MỤC CÁC HÌNH VẼ, ĐỒ THỊ Hình 2.1 So sánh kích thƣớc khóa RSA và ECC với cùng mức độ an toàn .................................. 25 Hình 2.2 So sánh mức độ bảo mật giữa ECC với RSA / DSA ...................................................... 26 Hình 2.3 Biểu diễn hình học một số bện ....................................................................................... 27 Hình 2.4 Biểu diễn hình học của bện kết hợp, bện nghịch đảo, bện tƣơng đƣơng ........................ 28 Hình 3.1 Lƣợc đồ chữ ký số với phần đính kèm ........................................................................... 38 Hình 3.2 Lƣợc đồ chữ ký số khôi phục thông điệp ....................................................................... 38 Hình 3.3 Sự trao đổi khóa k giữa Bob và Alice............................................................................. 48 Hình 3.4. Sự trao đổi khóa f giữa Bob và Alice. ........................................................................... 49 Hình 3.5 Sơ đồ xác nhận chữ ký số giữa Bob và Alice. ................................................................ 49 Hình 3.6 Cách thứ hai để xác nhận chữ ký số. .............................................................................. 50 Hình 4.1 Mô hình để P1,2 chứng tỏ với P3 quyền đƣợc thẩm định chữ ký .................................... 82 MỞ ĐẦU Trong các hoạt động thƣơng mại điện tử cũng nhƣ việc xây dựng một nền hành chính điện tử, không thể không tính đến mức độ chính xác, an toàn của các bản thông báo điện tử đƣợc gửi đi và đến cũng nhƣ việc xác thực đối tƣợng gửi bản thông báo đó. Điều này nói lên sự cần thiết của việc xác thực và chữ ký số. Hiện nay, Bộ Thƣơng mại và Ngân hàng Nhà nƣớc Việt Nam đã đƣợc Chính phủ cho phép triển khai chữ ký số và xác thực trong thanh toán điện tử từ năm 2006. Hiện nay, Hàn Quốc cũng đang giúp ta triển khai hạ tầng cơ sở khoá công khai PKI trong chính phủ điện tử. Tất cả kết quả trên chủ yếu là đƣợc chuyển giao từ bên ngoài. Xét về lĩnh vực an ninh quốc gia, chúng ta sẽ đặt câu hỏi: mức độ an toàn của chữ ký số và tính xác thực của văn bản có đảm bảo yêu cầu của chúng ta không khi mà chúng ta phải nhập ngoại hoàn toàn dây chuyền công nghệ ? Để giúp các nhà an ninh an toàn mạng có đƣợc cơ sở đánh giá mức độ an toàn của hệ thống đó, em chọn đề tài: “Tìm hiểu chữ ký số và ứng dụng của nó” làm đối tƣợng để nghiên cứu phục vụ cho luận văn của mình. Bố cục của luận văn gồm 4 chƣơng: Chƣơng 1. Các khái niệm toán học cơ bản Chƣơng 2. Mật mã, hàm băm Chƣơng 3. Các mô hình chữ ký số Chƣơng 4. Chữ ký chống chối bỏ và ứng dụng Trong đó, Chƣơng 4 là trọng tâm của luận văn này. Ở chƣơng này, luận văn đi sâu tìm hiểu mô hình chữ ký số chống chối bỏ, một số biến thể của mô hình này cũng nhƣ đƣa ra một số trƣờng hợp có thể áp dụng mô hình chữ ký này trong cuộc sống. Trong chƣơng này em cũng đƣa ra chƣơng trình demo bằng ngôn ngữ C# để có thể hình dung rõ hơn về mô hình chữ ký có thể đƣợc áp dụng. Do khả năng còn hạn chế, đặc biệt là khả năng toán học cho nên mặc dù em đã có nhiều cố gắng nhằm hoàn thành tốt nhất nhiệm vụ của mình nhƣng không khỏi còn có nhiều thiếu sót. Em rất mong đƣợc sự chỉ bảo, đóng góp của các thầy cô giáo để luận văn này đƣợc hoàn thiện hơn. Em xin chân thành cảm ơn./. CHƢƠNG 1: CÁC KHÁI NIỆM TOÁN HỌC CƠ BẢN 1. 1 CÁC CẤU TRÚC ĐẠI SỐ 1.1.1 Nhóm Cho một tập các phần tử hoặc “số” và một phép toán hai ngôi, mà kết quả cũng là một phần tử của tập hợp đó. Tức là ứng với mỗi cặp phần tử trên tập đó, kết quả của phép toán cũng là một phần tử xác định của tập đã cho. Tính chất này ta gọi là tính đóng của phép toán trên tập đang xét, ta có định nghĩa sau đây về nhóm. Định nghĩa nhóm. Tập hợp G cùng với phép toán „.’ đóng kín trên G đƣợc gọi là nhóm, nếu nó thỏa mãn các tính chất sau với mọi phần tử a, b, c thuộc G: - Tính kết hợp (a.b).c = a.(b.c) - Có đơn vị e: e.a = a.e = a - Có nghịch đảo a-1: a.a-1 = e Nếu có thêm tính giao hoán a.b = b.a, thì gọi là nhóm Aben. Định nghĩa nhóm Cyclic. Giả sử cho trƣớc một nhóm hữu hạn (G, .) (tức G là một tập hợp khác rỗng và gồm một số hữu hạn phần tử). Khi đó, một phần tử a Є G đƣợc gọi là phần tử sinh của G nếu: ak = a.a.a .....a = e (k lần a) và không tồn tại số nguyên dƣơng h < k mà ah = e , trong đó số k là số phần tử của tập hợp G. Một nhóm (G, .) có ít nhất một phần tử sinh thì đƣợc gọi là nhóm cyclic. 1.1.2 Vành Cho một tập R các “số” với hai phép toán là cộng và nhân. Tập với hai phép toán trên đƣợc gọi là vành, nếu hai phép toán thoả mãn các tính chất sau: - Với phép cộng, R là nhóm Aben - Với phép nhân, có: tính đóng ; tính kết hợp; tính phân phối đối với phép cộng a(b+c) = ab + ac . Nếu phép nhân có tính giao hoán thì tạo thành vành giao hoán. Nếu phép nhân có nghịch đảo và không có thƣơng 0, thì nó tạo thành miền nguyên 1.1.3 Trƣờng Trường là một tập hợp F với hai phép toán cộng và nhân, thoả mãn: - Với phép cộng F là nhóm Aben - Với phép nhân F trừ phần tử 0 là nhóm Aben. - a(b+c) = ab + ac (với mọi a, b, c Є ) 1.2 SỐ HỌC TRÊN MODULO 1.2.1 Định nghĩa Modulo Cho số tự nhiên n và số nguyên a. Định nghĩa: a mod n là phần dƣ dƣơng khi chia a cho n. 1.2.2 Các phép toán số học trên Modulo Cho số n. Ta muốn thực hiện các phép toán theo Modulo của n. Ta có thể thực hiện các phép toán trên các số nguyên nhƣ các phép cộng, nhân các số nguyên thông thƣờng sau đó rút gọn lại bằng phép lấy Modulo hoặc cũng có thể vừa tính toán, kết hợp với rút gọn tại bất cứ thời điểm nào: (a+b) mod n = [a mod n + b mod n] mod n (*) (a.b) mod n = [a mod n . b mod n] mod n (**) Nhƣ vậy khi thực hiện các phép toán ta có thể thay các số bằng các số tƣơng đƣơng theo Modulo n đó hoặc đơn giản hơn có thể thực hiện các phép toán trên các đại diện của nó: Zn = { 0, 1, 2, 3, …, n-1 }. - Zn với các phép toán theo Modulo n tạo thành vành giao hoán có đơn vị. Thực vậy tính đóng của các phép cộng và nhân dựa trên hai công thức (*) và (**). Các tính chất kết hợp, giao hoán và nghịch đảo đƣợc suy ra từ các tính chất tƣơng ứng của các số nguyên. - Các chú ý về tính chất rút gọn: + Nếu (a+b) ≡ (a+c) mod n, thì b ≡ c mod n + Nhƣng (ab) ≡ (ac) mod n, thì b ≡ c mod n chỉ khi nếu a là nguyên tố cùng nhau với n 1.2.3 Tính chia hết của các số nguyên - Thuật toán Euclide Tập hợp Z là đóng kín đối với các phép cộng, trừ và nhân, nhƣng không đóng kín đối với phép chia. Cho hai số nguyên bất kỳ a và b, b  1. Thực hiện phép chia a cho b ta sẽ đƣợc hai số q và r sao cho a = b.q + r , 0  r  b . Số q đƣợc gọi là số thương của phép chia a cho b, ký hiệu a div b, và số r đƣợc gọi là số dư của phép chia a cho b, ký hiệu a mod b. Một số nguyên d đƣợc gọi là ước số chung của hai số nguyên a và b nếu da và db. Số nguyên d đƣợc gọi là ước số chung lớn nhất của a và b nếu d  0, d là ƣớc số chung của a và b, và mọi ƣớc số chung của a và b đều là ƣớc số của d . Ta ký hiệu ƣớc số chung lớn nhất của a và b là gcd(a,b). Hai số a và b đƣợc gọi là nguyên tố với nhau, nếu chúng không có ƣớc số chung nào khác 1, tức là nếu gcd(a,b) = 1. Một số nguyên n > 1 bất kỳ đều có thể viết dƣới dạng: n = p1a1 . p2a 2 ... pka k trong đó p1 , p2 ,..., pk là các số nguyên tố khác nhau, 1 , 2 ,..., k là các số mũ nguyên dƣơng. Nếu không kể thứ tự các thừa số nguyên tố, thì dạng biểu diễn đó là duy nhất, ta gọi đó là dạng khai triển chính tắc của n . Định lý 1.1 Nếu b  0 và b a thì gcd(a ,b) = b. Nếu a = bq + r thì gcd(a,b) = gcd(b,r). Một số nguyên m đƣợc gọi là bội số chung của a và b nếu am và bm. Số m đƣợc gọi là bội số chung bé nhất của a và b , và đƣợc ký hiệu là lcm(a ,b), nếu m  0, m là bội số chung của a và b , và mọi bội số chung của a và b đều là bội của m . Với hai số nguyên dƣơng a và b ta có quan hệ lcm(a,b).gcd(a,b) = a.b Thuật toán sau đây thực hiện tìm USCLN của hai số nguyên bất kỳ: Thuật toán Euclide tìm ƣớc số chung lớn nhất INPUT: hai số nguyên không âm a và b , với a b . OUTPUT: ƣớc số chung lớn nhất của a và b. 1. Trong khi còn b  0, thực hiện: 1.1. đặt r a modb , a b , b  r. 2. Cho ra kết quả (a). Ta biết rằng nếu gcd(a,b) = d, thì phƣơng trình bất định a.x + b.y = d có nghiệm nguyên (x,y), và một nghiệm nguyên (x,y) nhƣ vậy có thể tìm đƣợc bởi thuật toán Euclide mở rộng nhƣ sau: Thuật toán Euclide mở rộng : INPUT: hai số nguyên không âm a và b với a b. OUTPUT: d = gcd(a,b) và hai số x,y sao cho a.x + b.y = d. 1. Nếu b = 0 thì đặt d a , x 1, y  0, và cho ra (d,x,y). 2. Đặt x2  1, x1  0 , y2  0 , y1  1. 3. Trong khi còn b  0, thực hiện: 3.1. qa divb, r  a modb , x  x2  qx1 , y  y2  qy1. a b, b r , x2  x1 , x1 x , y2 y1 và y1y. 4. Đặt d  a, x x2 , y  y2 , và cho ra kết quả (d,x,y). 1.3 TRƢỜNG GALOA Ta muốn đi tìm một trƣờng số có hữu hạn các phần tử, tức là một tập hữu hạn các phần tử mà ở đó có thể cộng trừ, nhân, chia mà không vƣợt ra ngoài phạm vi tập hữu hạn các phần tử đó. Trƣờng Galoa thuộc lọai đó và đóng vai trò quan trọng trong lý thuyết mã. Có thể chứng minh đƣợc rằng số các phần tử của trƣờng hữu hạn bất kỳ bằng lũy thừa của pm của số nguyên tố p nào đó, ta ký hiệu trƣờng Galoa đó là GL(pm). Thông thƣờng ta sử dụng các trƣờng: GL(p) và GL(2m). 1.3.1 Trƣờng Galoa Trƣờng Galoa GL(p), với p là số nguyên tố. - GL(p) gồm tập {0,1, … , p-1} - Với các phép toán cộng và nhân Modulo, nhƣ đã biết GL(p) tạo thành một vành giao hoán. Vì p là số nguyên tố nên mọi số khác 0 nhỏ hơn p đều nguyên tố cùng nhau với p, do đó GL(p) tạo thành trƣờng vì mọi a thuộc {1, … , p-1} đều có phần tử nghịch đảo a-1: a . a-1 = 1. Nhƣ vậy trên GL(p) ta có thể thực hiện các phép toán cộng, trừ, nhân, chia theo Modulo p. 1.3.2 Tìm số nghịch đảo Xét bài toán: nếu GCD(m, b) = 1, tìm nghịch đảo của b theo Modulo m. Ta mở rộng thuật toán Euclide vừa tìm ƣớc chung lớn nhất của m và b, vừa tính nghịch đảo trong trƣờng hợp GCD(m, b) = 1. Thuật toán Euclide mở rộng: EXTENDED EUCLID(m, b) 1.(A1, A2, A3)=(1, 0, m); (B1, B2, B3)=(0, 1, b) 2. if B3 = 0 return A3 = gcd(m, b); no inverse 3. if B3 = 1 return B3 = gcd(m, b); B2 = b–1 mod m 4. Q = A3 div B3 5. (T1,T2,T3)=(A1 – Q*B1,A2 – Q*B2, A3 – Q*B3) 6. (A1, A2, A3)=(B1, B2, B3) 7. (B1, B2, B3)=(T1, T2, T3) 8. goto 2 1.3.3 Số học đa thức Xét tập các đa thức Pn có bậc nhỏ hơn hoặc bằng n: Trên tập các đa thức đó có thể có một số cách khác nhau thực hiện các phép toán cộng và nhân đa thức: - Có thể thực hiện các phép toán thông thƣờng trên đa thức - Các phép toán trên đa thức với các hệ số trên Modulo p - Các phép toán trên đa thức với các hệ số trên Modulo p và sau đó lấy Modulo theo đa thức m(x). Sau đây ta xét riêng trƣờng hợp khi các phép toán cộng, nhân đa thức đƣợc thực hiện với phép lấy Modulo theo một đa thức nào đó. 1.3.4 Phép toán đa thức với Modulo đa thức Cho đa thức g(x) bậc n và các hệ số của các đa thức xét trong mục này lấy trong trƣờng Galoa GF(p) với p là số nguyên tố. Viết đa thức f(x) dƣới dạng: f(x) = q(x) g(x) + r(x) trong đó r(x) là phần dƣ khi chia f(x) cho g(x). Rõ ràng bậc của r(x) sẽ nhỏ hơn bậc của g(x). Ta viết r(x) = f(x) mod g(x) Nếu không có phần dƣ, tức là r(x) = 0, ta nói g(x) là ƣớc của f(x) hay g(x) chia hết f(x) hay f(x) chia hết cho g(x). Trong trƣờng hợp g(x) không có ƣớc ngoài 1 và chính nó, thì ta nói g(x) là đa thức nguyên tố hoặc không rút gọn đƣợc. Việc tìm ƣớc chung lớn nhất của hai đa thức đƣợc trình bày trong thuật toán tƣơng tự nhƣ Euclide nhƣ sau: Tìm đa thức ƣớc chung lớn nhất GCD(a(x), b(x)) - c(x) = GCD(a(x), b(x)) nếu c(x) là đa thức bậc lớn nhất mà chia hết cả a(x),b(x) - Có thể điều chỉnh thuật toán Euclid‟s Algorithm để tìm nó: EUCLID[a(x), b(x)] 1. A(x) = a(x); B(x) = b(x) 2. if B(x) = 0 return A(x) = gcd[a(x), b(x)] 3. R(x) = A(x) mod B(x) 4. A(x) ¨ B(x) 5. B(x) ¨ R(x) 6. goto 2 Thuật toán tìm nghịch đảo của một đa thức theo một đa thức nguyên tố cùng nhau với nó, đƣợc trình bày tƣơng tự nhƣ Ơcolit mở rộng. Phép toán đa thức với Modulo đa thức Cho g(x) là đa thức nguyên tố bậc n. Khi đó tập các đa thức bậc nhỏ hơn bằng n với các phép toán cộng và nhân đa thức theo Modulo của đa thức nguyên tố g(x) tạo thành trƣờng hữu hạn, gọi là trƣờng Galoa và ký hiệu là GL(pn). Trƣờng Galoa GL(2n) gồm 2n phần tử. Muốn trƣờng Galoa có số phần tử lớn tuỳ ý, ta chỉ việc tăng và lấy n thích hợp. Đặc biệt việc tính toán các phép toán cộng trừ, nhân, chia trên đó rất nhanh và hiệu quả trên các thao tác của các thiết bị phần cứng. 1.4 LÝ THUYẾT SỐ 1.4.1 Các số nguyên tố Số nguyên tố là các số nguyên dƣơng chỉ có ƣớc số là 1 và chính nó. Các số nguyên tố là trung tâm của lý thuyết số. Số các số nguyên tố là vô hạn. 1.4.2 Phân tích ra thừa số nguyên tố Một trong những bài toán cơ bản của số học là phân tích ra thừa số nguyên tố số a, tức là viết nó dƣới dạng tích của các số nguyên tố. Lƣu ý rằng phân tích là bài toán khó hơn rất nhiều so với bài toán nhân các số để nhận đƣợc tích. Ta có kết luận, mọi số nguyên dƣơng đều có thể phân tích duy nhất thành tích các lũy thừa của các số nguyên tố: . Ví dụ: 91=7×13; 3600=24×32×52 Thông thƣờng để tìm phân tích trên, ta phải kiểm tra tính chia hết cho các số nguyên tố từ nhỏ đến lớn và thực hiện phép chia liên tiếp cho các số nguyên tố, rồi gộp thành lũy thừa của các số nguyên tố. 1.4.3 Các số nguyên tố cùng nhau và GCD Hai số nguyên dƣơng a và b không có ƣớc chung nào ngoài 1, đƣợc gọi là nguyên tố cùng nhau. Ngƣợc lại có thể xác định ƣớc chung lớn nhất bằng cách trong các phân tích ra thừa số của chúng, tìm các thừa số nguyên tố chung và lấy bậc lũy thừa nhỏ nhất trong hai phân tích của hai số đó. 1.4.4 Định lý Ferma (Định lý Ferma nhỏ) ap-1 mod p = 1 trong đó p là số nguyên tố và a là số nguyên bất kỳ khác bội của p: GCD(a,p) = 1. Hay với mọi số nguyên tố p và số nguyên a không là bội của p, ta luôn có ap = a mod p. Công thức trên luôn đúng, nếu p là số nguyên tố, còn a là số nguyên dƣơng nhỏ hơn p. 1.4.5 Hàm Ole Cho n là một số nguyên dƣơng. Khi thực hiện phép tính đồng dƣ n của mọi số nguyên khác ta nhận đƣợc tập đầy đủ các phần dƣ có thể có là: 0, 1, 2,…, n-1 Từ tập trên ta tìm tập rút gọn bao gồm các số nguyên tố cùng nhau với n và quan tâm đến số lƣợng các phần tử nhƣ vậy đối với số nguyên dƣơng n cho trƣớc. Ví dụ. Với n = 10: - Tập đầy đủ các phần dƣ là {0,1,2,3,4,5,6,7,8,9} - Tập rút gọn các phần dƣ nguyên tố với 10 là {1,3,7,9} - Số các phần tử của tập rút gọn trên là giá trị của hàm Ole Ф(n). Nhƣ vậy, Ф(10) = 4. Muốn tính Ф(n) việc đếm số các số ngƣyên tố cùng nhau với n và nhỏ hơn n đƣợc loại bỏ vì đây là bài toán tốn nhiều công sức. Nói chung có thể tính hàm Ơle của một số dựa trên biểu thức phân tích ra thừa số của số đó. - Dễ dàng thấy, nếu p là số nguyên tố Ф(p) = p-1 - Nếu p và q là hai số nguyên tố khác nhau, thì có thể chứng minh đƣợc rằng: Ф(p.q) = (p-1)(q-1) - Nếu s và t là hai số nguyên tố cùng nhau, thì Ф(s.t) = Ф(s).Ф(t) 1.4.6 Định lý Ole Định lý Ole là tổng quát hoá của Định lý Ferma aФ(n)mod n = 1 với mọi cặp số nguyên dƣơng nguyên tố cùng nhau a và n: gcd(a,n)=1. 1.4.7 Kiểm tra tính nguyên tố Giả sử cần tìm một số nguyên tố rất lớn. Lấy ngẫu nhiên một số đủ lớn, ta sẽ kiểm tra xem số đó có phải là số nguyên tố không. Phƣơng pháp truyền thống là thử bằng phép chia. Tuy nhiên phƣơng pháp này chỉ hiệu quả khi xét các số nhỏ. Có phƣơng pháp khác, mà ta sẽ xét ở đây, sử dụng các phép kiểm tra tính nguyên tố thống kê dựa trên các tính chất: - Mọi số nguyên tố phải thỏa mãn - Nhƣng có một số số không nguyên tố, gọi là giả nguyên tố cũng thoả mãn tính chất đó. Cụ thể là phép kiểm tra dựa trên Định lý Ferma nhƣ sau: nếu số n cần kiểm tra tính nguyên tố là số nguyên tố, thì nó sẽ thoã mãn định lý Ferma đối với mọi số a nhỏ hơn nó an-1 mod n = 1. Nhƣ vậy, lấy ngẫu nhiên số a và kiểm tra xem nó có tính chất trên không. Nếu có thì n có thể là số nguyên tố, nếu cần độ tin cậy lớn hơn, thì ta kiểm tra liên tiếp nhiều lần nhƣ vậy với các số ngẫu nhiên a đƣợc chọn. Sau mỗi lần qua đƣợc phép thử, xác suất để n là số nguyên tố lại tăng lên. Chú ý: - nếu bi mod n = 1, thì b2i mod n = (1)2 mod n = 1 và - nếu bi mod n = n–1, thì b2i mod n = (n-1)2 mod n = (n2 –2n +1) mod n = 1 Kiểm tra số n có là số nguyên tố không, ta chỉ cần xét n là lẻ, khi đó n-1 là chẵn và biểu diễn nó dạng (n–1)= 2k.q Khi đó để tính an-1, ta tính aq, sau đó bình phƣơng liên tiếp k lần. Thuật toán Miller - Rabin TEST (n) is: 1. Find integers k, q, k > 0, q odd, so that (n–1)= 2k.q 2. Select a random integer a, 1 - Xem thêm -