Tài liệu Nghiên cứu vấn đề chia sẻ bí mật và ứng dụng trong bỏ phiếu điện tử

i .. ĐẠI HỌC THÁI NGUYÊN TRƢỜNG ĐẠI HỌC CNTT&TT LÊ ĐÌNH QUYẾN NGHIÊN CỨU VẤN ĐỀ CHIA SẺ BÍ MẬT VÀ ỨNG DỤNG TRONG BỎ PHIẾU ĐIỆN TỬ Chuyên ngành: Khoa học máy tính Mã số chuyên ngành: 60.48.01 LUẬN VĂN THẠC SĨ KHOA HỌC MÁY TÍNH NGƢỜI HƢỚNG DẪN KHOA HỌC PGS.TS TRỊNH NHẬT TIẾN THÁI NGUYÊN, NĂM 2012 ii LỜI CAM ĐOAN Tôi xin cam đoan luận văn này của tự bản thân tôi tìm hiểu, nghiên cứu dƣới sự hƣớng dẫn của PGS.TS Trịnh Nhật Tiến. Các chƣơng trình thực nghiệm do chính bản thân tôi lập trình, các kết quả là hoàn toàn trung thực. Các tài liệu tham khảo đƣợc trích dẫn và chú thích đầy đủ. TÁC GIẢ LUẬN VĂN Lê Đình Quyến Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên http://www.lrc-tnu.edu.vn iii LỜI CẢM ƠN Trƣớc hết em xin trân trọng gửi lời cảm ơn đến toàn thể các thầy cô giáo Trƣờng Đại học Công nghệ – Đại học Quốc gia Hà Nội và Trƣờng Đại học Công nghệ thông tin và Truyền thông – Đại học Thái nguyên đã dạy dỗ chúng em trong suốt quá trình học tập chƣơng trình cao học tại trƣờng. Đặc biệt em xin bày tỏ lòng biết ơn sâu sắc tới thầy giáo PGS.TS Trịnh Nhật Tiến, Trƣờng Đại học Công nghệ – Đại học Quốc gia Hà Nội đã quan tâm, định hƣớng và đƣa ra những góp ý, gợi ý, chỉnh sửa quí báu cho em trong quá trình làm luận văn tốt nghiệp. Cuối cùng, em xin chân thành cảm ơn các bạn bè đồng nghiệp, gia đình và ngƣời thân đã quan tâm, giúp đỡ và chia sẻ với em trong suốt quá trình làm luận văn tốt nghiệp. Thái Nguyên, ngày 28 tháng 10 năm 2012 HỌC VIÊN Lê Đình Quyến Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên http://www.lrc-tnu.edu.vn iv MỤC LỤC LỜI CAM ĐOAN ....................................................................................................... I LỜI CẢM ƠN ...........................................................................................................III MỤC LỤC ................................................................................................................ IV DANH MỤC CÁC THUẬT NGỮ .......................................................................... VI DANH MỤC CÁC BẢNG...................................................................................... VII DANH MỤC CÁC HÌNH ...................................................................................... VIII MỞ ĐẦU .....................................................................................................................1 CHƢƠNG 1. CÁC KHÁI NIỆM VÀ THUẬT TOÁN CƠ BẢN ...............................3 1.1. LÝ THUYẾT TOÁN HỌC MODULO ...........................................................3 1.1.1. Hàm phi Euler ..........................................................................................3 1.1.2. Đồng dƣ thức ............................................................................................4 1.1.3. Không gian Zn ...........................................................................................5 1.1.4. Nhóm nhân Z*n ..........................................................................................6 1.1.5. Thặng dƣ ...................................................................................................7 1.1.6. Căn bậc modulo ........................................................................................7 1.1.7. Các thuật toán trong Zn ............................................................................8 1.1.8. Ký hiệu Legendre và ký hiệu Jacobi .......................................................10 1.2. VẤN ĐỀ MÃ HOÁ .......................................................................................13 1.2.1. Mã hoá khoá đối xứng ............................................................................15 1.2.2. Mã hoá khoá bất đối xứng ......................................................................16 1.3. VẤN ĐỀ KÍ ĐIỆN TỬ ..................................................................................18 1.4. CHỮ KÍ SỐ ...................................................................................................21 1.4.1. Giới thiệu về chữ kí số ............................................................................21 1.4.2. Sơ đồ chữ kí số ........................................................................................22 1.4.3. Chuẩn chữ kí số ......................................................................................25 1.5. VẤN ĐỀ QUẢN LÝ KHOÁ .........................................................................26 1.5.1. Khoá và một số khái niệm ......................................................................26 1.5.2. Các cách tạo khoá ..................................................................................28 1.5.3. Phân phối khoá .......................................................................................35 CHƢƠNG 2. SƠ ĐỒ CHIA SẺ BÍ MẬT .................................................................41 2.1. Khái niệm chia sẻ bí mật................................................................................41 2.2. Các sơ đồ chia sẻ bí mật ................................................................................43 2.2.1. Sơ đồ ngƣỡng của Sharmir .....................................................................43 2.2.2. Cấu trúc mạch đơn điệu .........................................................................47 2.2.3. Cấu trúc không gian vectơ Brickell ........................................................54 2.3. Tính chất mở rộng của các sơ đồ chia sẻ bí mật ............................................58 2.4. Ƣu điểm của sơ đồ ngƣỡng Shamir trong bài toán bỏ phiếu điện tử .............59 CHƢƠNG 3. ỨNG DỤNG TRONG BỎ PHIẾU ĐIỆN TỬ ....................................60 Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên http://www.lrc-tnu.edu.vn v 3.1. Một số bài toán về an toàn thông tin trong “Bỏ phiếu điện tử” .....................60 3.1.1. Bài toán xác thực cử tri ..........................................................................60 3.1.2. Bài toán ẩn danh lá phiếu ......................................................................61 3.1.3. Bài toán phòng tránh sự liên kết giữa thành viên ban bầu cử và cử tri .62 3.2. Giải quyết bài toán chia sẻ khóa kí phiếu bầu cử ..........................................63 3.2.1. Chia sẻ khóa ...........................................................................................63 3.2.2. Khôi phục khóa .......................................................................................63 3.3. Giải quyết bài toán chia sẻ nội dung phiếu bầu cử ........................................64 3.4. Chƣơng trình thử nghiệm ...............................................................................65 3.4.1. Chia sẻ khóa kí phiếu bầu cử .................................................................65 3.4.2. Chia sẻ nội dung phiếu bầu cử ...............................................................66 KẾT LUẬN ...............................................................................................................67 TÀI LIỆU THAM KHẢO .........................................................................................68 NHẬN XÉT CỦA GIÁO VIÊN HƢỚNG DẪN ......................................................69 NHẬN XÉT CỦA GIÁO VIÊN PHẢN BIỆN .........................................................70 Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên http://www.lrc-tnu.edu.vn vi DANH MỤC CÁC THUẬT NGỮ gcd greatest common divisor (ƣớc số chung lớn nhất) CRT Chinese Remainder Theorem (định lý phần dƣ Trung Hoa) DES Data Encryption Standard (Tiêu chuẩn mã hóa dữ liệu) RSA Rivest, Sharmir, Adleman SHA Secure Hash Algorithm (Thuật giải băm an toàn) PKI Public Key Infastructure (Hạ tầng khóa công khai) CA Certification Authority (Chứng thực chữ kí số) DSS Digital Signature Standard (Chuẩn chữ kí số) Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên http://www.lrc-tnu.edu.vn vii DANH MỤC CÁC BẢNG Bảng 1.1: Mô tả các bƣớc tính 5596 mod 1234 ............................................................9 Bảng 1.2: Độ phức tạp theo bit của các phép toán cơ bản trong Zn ..........................9 Bảng 2.1: Các cấu trúc truy nhập không đẳng cấu ..................................................56 Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên http://www.lrc-tnu.edu.vn viii DANH MỤC CÁC HÌNH Hình 1.1: Sơ đồ hoạt động của mã hóa khóa đối xứng.............................................15 Hình 1.2: Sơ đồ hoạt động của mã hóa khóa bất đối xứng ......................................16 Hình 1.3:Trao đổi khoá Diffie – Hellman .................................................................28 Hình 1.4: Kẻ xâm nhập giữa cuộc trong giao thức Diffie – Hellman.......................29 Hình 1.5: Giao thức trạm tới trạm ............................................................................30 Hình 1.6: Giao thức trạm tới trạm có sự xâm nhập giữa đƣờng ..............................30 Hình 1.7: Thỏa thuận khóa Girault ..........................................................................33 Hình 1.8: Thoả thuận khoá Girault có sự xâm nhập giữa đƣờng.............................34 Hình 2.1: Phân chia khóa dựa vào mạch đơn điệu...................................................48 Hình 2.2: Mạch đơn điệu thể hiện cấu trúc truy nhập ..............................................50 Hình 2.3: Cấu trúc mạch đơn điệu có tốc độ thông tin ρ = 1/3 ................................52 Hình 2.4: Cấu trúc mạch đơn điệu có tốc độ thông tin ρ = 1/2 ................................53 Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên http://www.lrc-tnu.edu.vn 1 MỞ ĐẦU Hiện nay Internet đã trở nên rất phổ biến trên toàn thế giới, thông qua mạng Internet mọi ngƣời có thể trao đổi thông tin với nhau một cách nhanh chóng và thuận tiện. Những tổ chức có các hoạt động trên môi trƣờng Internet/Intranet phải đối diện với vấn đề là làm thế nào để bảo vệ những dữ liệu quan trọng, ngăn chặn những hình thức tấn công, truy xuất dữ liệu bất hợp pháp từ bên trong (Intranet) lẫn bên ngoài (Internet). Khi một ngƣời muốn trao đổi thông tin với một ngƣời hay một tổ chức nào đó thông qua mạng máy tính thì yêu cầu quan trọng là làm sao để đảm bảo thông tin không bị sai lệch hoặc bị lộ do sự can thiệp của ngƣời thứ ba. Trƣớc các yêu cầu cần thiết đó, lý thuyết về mật mã thông tin đã ra đời nhằm đảm bảo tính an toàn dữ liệu tại nơi lƣu trữ cũng nhƣ khi dữ liệu đƣợc truyền trên mạng. Vấn đề chia sẻ bí mật đƣợc đã đƣợc nghiên cứu từ những năm 70 của thế kỷ trƣớc. Ý tƣởng chính của chia sẻ bí mật dựa trên nguyên tắc đơn giản là không tin vào bất cứ ai. Để đảm bảo an toàn một thông tin nào đó thì ta không thể trao nó cho một ngƣời nắm giữ mà phải chia nhỏ thành các mảnh và chỉ trao cho mỗi ngƣời một hoặc một số mảnh, sao cho một ngƣời với một số mảnh mình có thì không thể tìm ra thông tin bí mật. Việc phân chia các mảnh phải theo một sơ đồ chia sẻ bí mật nhất định, sau đó có thể khôi phục lại thông tin bí mật ban đầu. Đƣợc sự gợi ý của giáo viên hƣớng dẫn và nhận thấy tính thiết thực của vấn đề, em đã chọn đề tài: Nghiên cứu vấn đề chia sẻ bí mật và ứng dụng trong “Bỏ phiếu điện tử” để làm nội dung cho luận văn tốt nghiệp của mình. Luận văn này tập trung vào nghiên cứu cơ sở lý thuyết toán học và một số kỹ thuật mật mã để thực hiện chia sẻ thông tin mật, sau đó áp dụng giải quyết một số bài toán về an toàn thông tin trong “Bỏ phiếu điện tử”. 2 Nội dung chính của luận văn gồm ba chƣơng Chƣơng 1: Các khái niệm cơ bản Trong chƣơng này luận văn trình bày các kiến thức cơ bản về lý thuyết toán học Modulo, vấn đề mã hóa, kí điện tử, chữ kí số và vấn đề quản lý khóa. Chƣơng 2: Sơ đồ chia sẻ bí mật Nội dung chƣơng 2 trình bày khái niệm về chia sẻ bí mật, các sơ đồ chia sẻ bí mật và tính chất mở rộng của các sơ đồ chia sẻ bí mật, ƣu điểm của sơ đồ Shamir trong bài toán bỏ phiếu điện tử. Chƣơng 3: Ứng dụng trong bỏ phiếu điện tử. Chƣơng này đề cập tới một số bài toán về an toàn thông tin trong “Bỏ phiếu điện tử”, Giải quyết bài toán chia sẻ khóa ký phiếu bầu cử, Giải quyết bài toán chia sẻ nội dung phiếu bầu cử. Chƣơng trình thử nghiệm đƣợc viết bằng ngôn ngữ lập trình C# 2012. Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên http://www.lrc-tnu.edu.vn 3 Chương 1. CÁC KHÁI NIỆM VÀ THUẬT TOÁN CƠ BẢN Chƣơng này trình bày các vấn đề cơ bản mà bất kỳ bài toán an toàn thông tin nào cũng phải đề cập đến, đó là các vấn đề về lý thuyết toán học sử dụng trong bảo mật thông tin, mã hoá thông tin, chữ ký điện tử, khái niệm khoá, các cách tạo khoá, các phƣơng pháp phân phối khoá, vấn đề định danh. Qua đó, hình thành cơ sở lý thuyết cho an toàn truyền tin trên mạng máy tính. Các khái niệm và định nghĩa trong chƣơng này đƣợc tham khảo trong các tài liệu: Lý thuyết mật mã và an toàn thông tin; Contemporary Cryptography. 1.1. LÝ THUYẾT TOÁN HỌC MODULO 1.1.1. Hàm phi Euler 1/. Định nghĩa Cho n ≥1. Φ(n) đƣợc định nghĩa là số các số nguyên trong khoảng [1, n] nguyên tố cùng nhau với n. Hàm Φ đƣợc gọi là hàm phi Euler.[4 – tr79] 2/. Tính chất của hàm phi Euler  Nếu p là số nguyên tố thì Φ(n) = p – 1.  Tính nhân của hàm phi Euler: Nếu gcd(m, n) = 1 thì Φ(mn) = Φ(m)Φ(n) (trong đó gcd(m, n) là ký hiệu ƣớc số chung lớn nhất của m và n).  Nếu n  p1e p2e ... pke trong đó p1, p2, ..., pk là các thừa số nguyên tố của n thì: 1 (n)  n(1  2 k 1 1 1 )(1  )...(1  ) . p1 p2 pk Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên http://www.lrc-tnu.edu.vn 4 1.1.2. Đồng dƣ thức 1/. Định nghĩa Cho a và b là các số nguyên, a đƣợc gọi là đồng dƣ với b theo modulo n, ký hiệu là a  b (mod n) nếu n chia hết (a – b). Số nguyên n đƣợc gọi là modulus của đồng dƣ.[4 – tr81] 2/. Ví dụ: 13  7 (mod 3) bởi vì 13 – 7 = 2*3 –11  4 (mod 5) bởi vì –11 – 4 = – 3*5 3/. Tính chất của đồng dƣ Cho a, a1, b, b1, c  Z. Ta có các tính chất sau:  a  b (mod n) nếu và chỉ nếu a và b có cùng số dƣ khi chia cho n.  a  a (mod n) (Tính phản xạ).  Nếu a  b (mod n) thì b  a (mod n) (Tính đối xứng).  Nếu a  b (mod n) và b  c (mod n) thì a  c (mod n) (Tính bắc cầu).  Nếu a  a1 (mod n), b  b1 (mod n) thì a + b  a1 + b1 (mod n) và ab  a1b1 (mod n). Lớp tƣơng đƣơng [1 – tr24] của một số nguyên a là tập hợp các số nguyên đồng dƣ với a theo modul n. Từ các tính chất 2, 3 và 4 ta thấy: cho n cố định, các số đồng dƣ với n theo modulo n trong không gian Z đƣợc xếp vào một một lớp tƣơng đƣơng. Nếu a = qn + r, trong đó 0 ≤ r < n thì a  r (mod n). Vì vậy mỗi số nguyên a là đồng dƣ theo modul n với duy nhất một số nguyên trong khoảng từ 0 đến n – 1 và đƣợc gọi là thặng dƣ nhỏ nhất của a theo modul n. Cũng vì vậy, a và r cùng thuộc một lớp tƣơng đƣơng. Do đó r có thể đơn giản đƣợc sử dụng để thể hiện lớp tƣơng đƣơng. Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên http://www.lrc-tnu.edu.vn 5 1.1.3. Không gian Zn 1/. Các định nghĩa trong không gian Zn  Các số nguyên theo modul n ký hiệu Zn là một tập hợp các số nguyên {0,1,2,3,…,n–1}. Các phép toán cộng, trừ, nhân trong Zn đƣợc thực hiện theo modulo n.[1 – tr24] Ví dụ: Z25 = {0, 1, 2, …, 24}. Trong Z25 : 13 + 16 = 4, bởi vì: 13 + 16 = 29  4 (mod 25). Tƣơng tự, 13*16 = 8 trong Z25  Cho a  Zn. Nghịch đảo nhân của a theo modulo n là một số nguyên x  Zn sao cho a*x  1 (mod n). Nếu x tồn tại thì đó là giá trị duy nhất và a đƣợc gọi là khả nghịch, nghịch đảo của a ký hiệu là a-1.[1 – tr25]  Cho a, b  Zn . Phép chia của a cho b theo modulo n là tích của a và b-1 theo modulo n, và chỉ dƣợc xác định khi b có nghịch đảo theo modulo n.[1 – tr25] 2/. Các tính chất trong không gian Zn  Cho a  Zn , a có nghịch đảo khi và chỉ khi gcd(a, n) = 1. [4 – tr83] Ví dụ: Các phần tử khả nghịch trong Z9 là: 1, 2, 4, 5, 7 và 8. trong đó 4-1 = 7 vì 4 .7  1 (mod 9)  Giả sử d = gcd(a, n). Phƣơng trình đồng dƣ ax  b (mod n) có nghiệm x nếu và chỉ nếu d chia hết cho b [1 – tr25], trong trƣờng hợp các nghiệm d nằm trong khoảng 0 đến n – 1 thì các nghiệm đồng dƣ theo modulo n / d. 3/. Định lý phần dƣ Trung Hoa (CRT) Nếu các số nguyên n1, n2, …, nk là các số nguyên tố cùng nhau từng đôi một thì hệ phƣơng trình đồng dƣ: x  a1 (mod n1 ) x  a2 (mod n2 ) ….. x  ak (mod nk ) có nghiệm duy nhất theo modulo n = n1n2 … nk [1 – tr26] Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên http://www.lrc-tnu.edu.vn 6 4/. Thuật toán của Gausse Nghiệm x trong hệ phƣơng trình đồng dƣ trong định lý phần dƣ Trung Hoa đƣợc tính nhƣ sau: k x=  ai NiMi mod n, trong đó: Ni = n/ni, Mi = Ni-1 mod ni [1 – tr26] i 1 Ví dụ: Cặp đồng dƣ: x  3 (mod 7 ) và x  7 (mod 13) có nghiệm duy nhất x  59 (mod 91) Tính chất: Nếu gcd(n1, n2) = 1 thì cặp đồng dƣ x  a (mod n1) và x  a (mod n2) có nghiệm duy nhất x  a (mod n1n2). 1.1.4. Nhóm nhân Z*n 1/. Các định nghĩa trong nhóm nhân Z*n  Nhóm nhân của Zn ký hiệu là Z*n = {a  Zn | gcd (a, n) = 1}. Đặc biệt, nếu n là số nguyên tố thì Z*n = {a  Zn | 1 ≤ a ≤ n – 1}. [1 – tr27]  Cho a  Zn*. Bậc của a, ký hiệu là ord(a) là số nguyên dƣơng t nhỏ nhất sao cho at  1 (mod n). [1 – tr27] 2/. Các tính chất trong Zn*  Cho n ≥ 2 là số nguyên. [1 – tr27, tr28] o (Định lý Euler) Nếu a  Zn * thì aΦ(n)  1 (mod n). o Nếu n là tích của các số nguyên tố phân biệt và nếu r  s (mod Φ(n)) thì ar  as (mod n) với mọi số nguyên a.  Cho p là số nguyên tố. [1 – tr28] o (Định lý Fermat) Nếu gcd(a, p) = 1 thì ap-1  1 (mod p). o Nếu r  s (mod p – 1) thì ar  as (mod p) với mọi số nguyên a. o Đặc biệt ap  a (mod p) với mọi số nguyên a. Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên http://www.lrc-tnu.edu.vn 7 1.1.5. Thặng dƣ 1/. Định nghĩa thặng dƣ Cho a  Zn*, a đƣợc gọi là thặng dƣ bậc 2 theo modulo n hoặc bình phƣơng theo modulo n nếu tồn tại x  Zn* sao cho x2  a (mod n). Nếu không tồn tại x thì a đƣợc gọi là thặng dƣ không bậc 2 theo modulo n. Tập hợp các thặng dƣ bậc 2 theo modulo n ký hiệu là Qn và tập hợp các thặng dƣ không bậc 2 theo modulo n ký hiệu ___ là Q n. [1 – tr28] ___ Chú ý: Vì định nghĩa 0  Zn* nên 0  Qn và 0  Q n 2/. Ví dụ ___ Cho n = 21. Khi đó: Q21 = {1, 4, 16} và Q 21 = {2, 5, 8, 10, 11, 13, 17, 19, 20}. 1.1.6. Căn bậc modulo 1/. Định nghĩa Cho a  Qn. Nếu a  Zn* thoả mãn x2  a (mod n) thì x đƣợc gọi là căn bậc 2 của a theo modulo n. [4 – tr91] 2/. Tính chất (Số căn bậc 2)  Nếu p là một số nguyên tố lẻ, a  Qn thì a có chính xác 2 căn bậc 2 theo modulo p.  Tổng quát hơn: cho n  p1e p2e ... pke trong đó pi là các số nguyên tố lẻ phân biệt 1 2 k và ei ≥ 1. Nếu a  Qn thì a có chính xác 2k căn bậc 2 theo modulo n. 3/. Ví dụ Căn bậc 2 của 13 theo modulo 37 là 7 và 30. Căn bậc 2 của 121 modulo 315 là 11, 74, 101, 151, 164, 214, 241 và 304. Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên http://www.lrc-tnu.edu.vn 8 1.1.7. Các thuật toán trong Zn Cho n là số nguyên dƣơng, các phần tử trong Zn sẽ đƣợc thể hiện bởi các số nguyên {0, 1, 2,…, n–1}. Ta thấy rằng nếu a, b  Zn thì: nÕu a  b  n ab (a  b) mod n   a  b  n nÕu a  b  n Vì vậy, phép cộng modulo (và phép trừ modulo) có thể đƣợc thực hiện mà không cần thực hiện các phép chia. Phép nhân modulo của a và b có thể đƣợc thực hiện bằng phép nhân thông thƣờng a với b nhƣ các số nguyên bình thƣờng, sau đó lấy phần dƣ của kết quả sau khi chia cho n. Phép tính nghịch đảo trong Zn có thể đƣợc thực hiện nhờ sử dụng thuật toán Euclidean mở rộng nhƣ mô tả sau: 1/. Thuật toán tính nghịch đảo nhân trong Zn INPUT: a  Zn OUTPUT: a-1 mod n, nếu tồn tại.  Sử dụng thuật toán Euclidean mở rộng sau để tìm các số nguyên x và y sao cho: ax + ny = d với d = gcd(a, n).  Nếu d > 1 thì a-1 mod n không tồn tại. Ngƣợc lại, return (x). 2/. Thuật toán Euclidean mở rộng [4 – tr69] INPUT: 2 số nguyên dƣơng a và b với a ≥ b. OUTPUT: d = gcd(a, b) và các số nguyên x, y thoả mãn: ax + by = d  Nếu b == 0 thì đặt d = a; x = 1; y = 0; return (d, x, y);  x2 = 1; x1 = 0; y2 = 0; y1 = 1;  Khi b > 0 thực hiện: q = [a / b]; r = a – qb; x = x2 – qx1; y = y2 – qy1; a = b; r = b; x2 = x1; x1 = x; y2 = y1; y1 = y;  d = a; x = x2; y = y2; return (d, x, y); Số mũ modulo có thể đƣợc tính một các hiệu quả bằng thuật toán bình phƣơng và nhân liên tiếp, nó đƣợc sử dụng chủ yếu trong nhiều giao thức mã hoá. Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên http://www.lrc-tnu.edu.vn 9 3/. Thuật toán bình phƣơng liên tiếp để tính số mũ modulo trong Zn. [4 – tr85] INPUT: a  Zn và số nguyên dƣơng 0 ≤ k < n trong đó k có biểu diễn nhị phân là: k=  t ki 2i i 0 OUTPUT: ak mod n  b = 1; Nếu k == 0 return (b);  A = a; Nếu k0 == 1 thì đặt b = a;  For i = 1 to t do A = A2 mod n; Nếu ki == 1 thì b = A * b mod n;  Return (b); Ví dụ: (Tính số mũ modulo) i 0 1 2 3 4 5 6 7 8 9 ki 0 0 1 0 1 0 1 0 0 1 A 5 25 625 681 1011 369 421 779 947 925 b 1 1 625 625 67 67 1059 1059 1059 1013 Bảng 1.1: Mô tả các bƣớc tính 5596 mod 1234 Độ phức tạp theo bit của các phép toán cơ bản trong Zn nhƣ sau: Phép toán Cộng modulo (a + b) mod n Trừ modulo (a – b) mod n Độ phức tạp về bit O(lg n) O(lg n) Nhân modulo (a b) mod n O((lg n)2) Nghịch đảo theo modulo a-1 mod n O((lg n)2) Số mũ modulo ak mod n, k < n O((lg n)3) Bảng 1.2: Độ phức tạp theo bit của các phép toán cơ bản trong Zn Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên http://www.lrc-tnu.edu.vn 10 1.1.8. Ký hiệu Legendre và ký hiệu Jacobi 1/. Định nghĩa ký hiệu Legendre Cho p là số nguyên tố lẻ và một số nguyên a. Ký hiệu Legendre ( a ) đƣợc p định nghĩa là: [1 – tr29]  0 nÕu p | a a  ( )   1 nÕu a  Qp p  1 nÕu a  Q P 2/. Tính chất của ký hiệu Legendre Cho số nguyên tố lẻ p; a, b  Z. Ký hiệu Legendre có tính chất sau: [1 – tr29, tr30]  ( 1 1 a )  a (p-1)/2 (mod p). Trƣờng hợp đặc biệt: ( ) = 1 và ( ) = (–1)(p-1)/ 2 p p p ___ Bởi vậy nên: –1  Qp nếu p  1 (mod 4); và –1  Q n nếu p  3 (mod 4).  ( a2 ab a b ) = ( )( ) . Vì vậy nếu a Zp* thì ( ) = 1 p p p p  Nếu a  b (mod p) thì ( 2 p  ( )  (1) ( p 1) / 8  và ( 2 ( b a )=( ) p p 2 ) p = 1 nếu p  1 hoặc 7 (mod 8) 2 ) = –1 nếu p  3 hoặc 5 (mod 8) p  Nếu q là số nguyên tố lẻ khác p thì: ( Nói cách khác: ( Ngƣợc lại thì ( p q ) = ( ) (–1)(p-1)(q-1) / 4. q p p q ) = ( ) trừ khi cả p và q đều đồng dƣ với 3 theo modulo 4. q p p q )=–( ) q p Ký hiệu Jacobi là sự tổng quát hoá của ký hiệu Legendre cho các số nguyên n là lẻ mà không cần phải là nguyên tố. Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên http://www.lrc-tnu.edu.vn 11 3/. Định nghĩa ký hiệu Jacobi a n Cho n ≥ 3 là lẻ với các thừa số nguyên tố: n  p1e p2e ... pke . Ký hiệu Jacobi ( ) đƣợc 1 2 k a a a a định nghĩa là: ( )  ( )e1 ( )e2 ...( )ek [1 – tr29] n p1 p2 pk Rõ ràng, nếu n là số nguyên tố thì ký hiệu Jacobi là ký hiệu Legendre. 4/. Tính chất của ký hiệu Jacobi Cho m ≥ 3, n ≥ 3 là số nguyên lẻ và a, b Z. Ký hiệu Jacobi có các tính chất sau: a n a n  ( ) = 0, 1 hoặc –1, và ( ) = 0 khi và chỉ khi gcd(a, n) 1.  ( ab a b ) = ( )( ) . Vì vậy, nếu a  Zn* thì n n n  ( a a a ) = ( )( ). m n mn a n ( a2 )  1. n b n  Nếu a  b (mod n) thì ( ) = ( ). 1 n  ( ) = 1.  ( 1 ) n và ( = –(1) (n-1)/2 . Vì vậy ( 1 ) n = 1 nếu n  1 (mod 4) 1 ) = –1 nếu n  3 (mod 4). n 2 n 2 n  ( )  (1) ( n 1) / 8 . Vì vậy, ( ) = 1 nếu p  1 hoặc 7 (mod 8) 2 2 n và ( ) = –1 nếu p  3 hoặc 5 (mod 8).  ( m n ) = ( ) (–1)(m-1)(n-1) / 4. n m Ngoài ra, ( m n ) = ( ) trừ khi cả m và n đều đồng dƣ với 3 theo modulo 4. n m Ngƣợc lại thì ( m n ) = – ( ). n m Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên http://www.lrc-tnu.edu.vn 12 Bằng các tính chất Jacobi, ta suy ra rằng: nếu n lẻ và a = 2ea1 với a1 lẻ thì a 2e a1 2 n mod a1 ( )  ( )( )  ( ) e ( )(1) ( a1 1)( n1) / 4 n n n n a1 a n Từ đó có thuật toán tính ( ) mà không yêu cầu tính các thừa số nguyên tố của n. 5/. Thuật toán tính ký hiệu Jacobi (và ký hiệu Legendre) JACOBI(a, n) INPUT: số nguyên lẻ n ≥ 3 và một số nguyên a, 0 ≤ a < n a n OUTPUT: Ký hiệu Jacobi ( ) (và là ký hiệu Legendre khi n là số nguyên tố)  Nếu a == 0 thì return (0);  Nếu a == 1 thì return (1);  Viết a = 2e a1 với a1 lẻ  Nếu e chẵn thì đặt s = 1; Nếu không thì đặt s = 1 nếu n  1 hoặc 7 (mod 8) hoặc đặt s = –1 nếu n  3 hoặc 5 (mod 8).  Nếu n  3 (mod 4) và a1  3 (mod 4) thì đặt s = – s;  Đặt n1 = n mod a1;  Nếu a1 == 1 thì return (s); Ngƣợc lại thì return (s . JACOBI(a1, n1)); Thuật toán trên chạy trong thời gian O((lg n)2) phép tính bit. 6/. Ví dụ (Tính ký hiệu Jacobi) Cho a = 158 và và n = 235. Ký hiệu Jacobi ( ( 158 ) đƣợc tính nhƣ sau: 235 158 2 79 235 77 )=( )( ) = (–1) ( )(–1)78. 234 / 4 = ( ) 79 235 235 235 79 =( 79 2 )(–1)76 . 78 / 4 = ( ) = –1 77 77 Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên http://www.lrc-tnu.edu.vn