Tài liệu Nghiên cứu phương pháp bảo vệ thông tin dùng trên thiết bị cầm tay

ĐẠI HỌC QUỐC GIA HÀ NỘI TRƯỜNG ĐẠI HỌC CÔNG NGHỆ LÊ THỊ THU NGHIÊN CỨU PHƯƠNG PHÁP BẢO VỆ THÔNG TIN DÙNG TRÊN THIẾT BỊ CẦM TAY LUẬN VĂN THẠC SĨ Hà Nội – 2011 ĐẠI HỌC QUỐC GIA HÀ NỘI TRƯỜNG ĐẠI HỌC CÔNG NGHỆ LÊ THỊ THU NGHIÊN CỨU PHƯƠNG PHÁP BẢO VỆ THÔNG TIN DÙNG TRÊN THIẾT BỊ CẦM TAY Ngành: Công nghệ thông tin Chuyên ngành: Hệ thống thông tin Mã số: 604805 LUẬN VĂN THẠC SĨ Người hướng dẫn khoa học: PGS TS TRỊNH NHẬT TIẾN Hà Nội – 2011 MỤC LỤC BẢNG DANH MỤC CÁC TỪ VIẾT TẮT .....................................................................5 DANH MỤC CÁC HÌNH VẼ ..........................................................................................6 LỜI MỞ ĐẦU ..................................................................................................................7 Chƣơng 1. CÁC KHÁI NIỆM CƠ BẢN ........................................................................8 1.1. MỘT SỐ KHÁI NIỆM TRONG SỐ HỌC ..............................................................8 1.1.1. Số nguyên tố .......................................................................................................8 1.1.1.1. Khái niệm số nguyên tố ..............................................................................8 1.1.1.2. Phƣơng pháp kiểm tra số nguyên tố ...........................................................9 1.1.2 Các tính toán trong Zn * ......................................................................................18 1.1.2.1 Tập hợp Zn và Zn * .................................................................................18 1.1.2.2 Tính phần tử nghịch đảo trong Zn * ..........................................................19 1.1.2.3 Tính luỹ thừa trong Zn .............................................................................20 1.2. MỘT SỐ KHÁI NIỆM TRONG ĐẠI SỐ ..............................................................22 1.2.1. Khái niệm: Nhóm, Vành, Trƣờng .....................................................................22 1.2.1.1 Nhóm ........................................................................................................22 1.2.1.2 Vành .........................................................................................................23 1.2.1.3 Trƣờng ......................................................................................................23 1.2.2. Không gian Vector ............................................................................................25 1.2.3. Không gian chiếu ..............................................................................................26 1.3. MỘT SỐ KHÁI NIỆM VỀ ĐỘ PHỨC TẠP CỦA THUẬT TOÁN ....................27 1.3.1. Khái niệm thuật toán ........................................................................................27 1.3.2. Độ phức tạp của thuật toán ..............................................................................27 1.3.3. Một số lớp bài toán ..........................................................................................30 1.4. MỘT SỐ KHÁI NIỆM TRONG MẬT MÃ ..........................................................32 1.4.1. Mã hóa ..............................................................................................................32 1.4.1.1 Khái niệm hệ mã hóa .................................................................................32 1.4.1.2 Phân loại mã hóa .......................................................................................33 1.4.2. Chữ ký số ..........................................................................................................36 1.4.2.1 Sơ đồ chữ ký số .........................................................................................36 1.4.2.2 Chữ ký số RSA ..........................................................................................36 1.4.2.3 Chữ kỹ số Elgamal ....................................................................................37 Chƣơng 2. HỆ MẬT MÃ TRÊN ĐƢỜNG CONG ELLIPTIC...................................39 2.1. ĐƢỜNG CONG ELLIPTIC ...................................................................................39 2.1.1. Khái niệm đƣờng cong Elliptic .........................................................................39 2.1.1.1 Đƣờng cong Elliptic theo công thức Weierstrass ......................................39 2.1.1.2. Đƣờng cong Elliptic trên trƣờng Galois ...................................................40 2.1.1.3. Đƣờng cong Elliptic trên trƣờng hữu hạn ................................................42 2.1.2. Các phép toán trên đƣờng cong ELLIPTIC ......................................................44 2.1.2.1 Phép cộng .................................................................................................44 2.1.2.2 Phép nhân .................................................................................................47 2.1.2.3. Số điểm trên đƣờng cong ELLIPTIC với trƣờng FQ ..............................50 2.1.4. Chọn đƣờng cong ELLIPTIC phù hợp ............................................................51 2.1.4.1. Trƣờng K ..................................................................................................51 2.1.4.2. Dạng của đƣờng cong elliptic ..................................................................51 2.1.4.3. Phƣơng pháp lựa chọn ..............................................................................52 2.1.4.4. Bài toán LOGARIT rời rạc trên đƣờng cong ELLIPTIC .........................53 2.2 MỘT SỐ HỆ MẬT TRÊN ĐƢỜNG CONG ELLIPTIC .......................................54 2.2.1. Hệ mã hoá ........................................................................................................54 2.2.1.1. Nhúng bản rõ vào đƣờng cong Elliptic ....................................................54 2.2.1.2. Hệ mã hóa “tựa” Ellgamal .......................................................................55 2.2.1.3. Hệ mã tƣơng tự mã mũ (Dạng tƣơng tự của Massey –Omura)................56 2.2.1.4. Hệ mã hóa trên đƣờng cong Elliptic của Menezes – Vanstore ................58 2.2.1.5. Kết hợp ECES với thuật toán Rijndael và các thuật toán mở rộng .........59 2.2.1.6. Một số chuẩn sử dụng hệ mật ECC ..........................................................59 2.2.1.7. So sánh RSA và ECC ...............................................................................62 2.2.2. Chữ ký số ..........................................................................................................65 2.2.2.1. Sơ đồ chữ ký ECDSA .............................................................................65 2.2.2.2 Sơ đồ chữ ký Nyberg – Rueppel ...............................................................66 2.2.2.3 Sơ đồ chữ ký mù Harn trên EC .................................................................67 2.2.2.4 Sơ đồ đa chữ ký mù Harn trên EC ............................................................70 2.2.3. Phƣơng pháp thoả thuận khoá..........................................................................72 2.2.3.1. Phƣơng pháp thỏa thuận khóa Diffie - Hellman .....................................72 2.2.3.2. Phƣơng pháp thỏa thuận khóa Elliptic Curve Diffie – Hellman .............73 2.3 ĐỘ AN TOÀN CỦA HỆ MẬT TRÊN ĐƢỜNG CONG ELLIPTIC ......................74 2.4. KHẢ NĂNG TẤN CÔNG HỆ MẬT TRÊN THIẾT BỊ CẦM TAY ......................75 2.4.1. Phƣơng pháp tấn công “baby-step giant - step” ...............................................75 2.4.2. Phƣơng pháp tấn công MOV ............................................................................76 2.4.3. Các thuật toán tấn công khác ............................................................................78 Chƣơng 3. SỬ DỤNG MỘT SỐ HỆ MẬT MÃ KHÁC TRÊN THIẾT BỊ CẦM TAY 79 3.1 Hệ mã mật RC4 (40 bit/ 128 bit) ..............................................................................79 3.1.1.Mô tả hệ mật RC4 ..............................................................................................79 3.1.2.Khởi tạo khối S ..................................................................................................80 3.1.3.Mã hóa và Giải mã .............................................................................................80 3.1.4.Những ƣu điểm chính của hệ mã hoá RC4 ........................................................81 3.2 Hệ mã mật DES (56 bit) ...........................................................................................81 3.2.1 Các thành phần của DES ...................................................................................81 3.2.2 Giải thuật mã hóa DES ......................................................................................83 3.2.3 Giải thuật giải mã DES ......................................................................................86 3.3 Hệ mã mật 3DES (112bit/ 168 bit) ...........................................................................87 3.3.1. Tổng quan mã hóa 3DES ..................................................................................87 3.3.2. Chuẩn mã hóa dữ liệu 3DES.............................................................................88 Chƣơng 4: THỬ NGHIỆM CHƢƠNG TRÌNH ............................................................91 4.1 GIỚI THIỆU CHƢƠNG TRÌNH .............................................................................91 4.2. CÀI ĐẶT CHƢƠNG TRÌNH VÀ HƢỚNG DẪN SỬ DỤNG .............................95 KẾT LUẬN ....................................................................................................................97 TÀI LIỆU THAM KHẢO ..............................................................................................98 BẢNG DANH MỤC CÁC TỪ VIẾT TẮT Từ viết tắt Từ gốc Nghĩa tiếng Việt Tìm ƣớc chung lớn nhất GCD Greatest Common Divisor MOV Menezes, Okamoto, và Vanstone EDLP Elliptic Curve Discrete Logarithm Vấn đề logarit rời rạc trên Problem đƣờng cong Elliptic DLP Discrete Logarithm Problem Vấn đề logarit rời rạc ECC Elliptic Curve Cryptography Hệ mật trên đƣờng cong Elliptic ECDSA Elliptic Curve Digital Signature Algorithm Thuật toán ký trên đƣờng cong Elliptic ECKA Elliptic Curve Key Agreement Thỏa thuận khóa trên đƣờng Elliptic FSTC Financial Services Technology Consortium Hệ thống thanh toán điện tử và các dịch vụ tài chính IETF Internet Engineering Task Force Giao thức thỏa thuận khóa NIST National Institue of Standards Viện nghiên cứu chuẩn quốc tế SET Secure Electronic Transaction WAP Wireless Application Protocol ECDLP Elliptic Curve Discrete Logarithm Problem ECDH Elliptic curve Diffie-Hellman DANH MỤC CÁC HÌNH VẼ Hình vẽ Tên hình vẽ Hình 2.1 Một ví dụ về đƣờng cong Elliptic Hình 2.2 Điểm ở vô cực Hình 2.3 Phép nhân đôi trên đƣờng cong Elliptic Hình 3.1 Sơ đồ tạo chuỗi gama trong hệ mật RC4 Hình 3.2 Một vòng của DES Hình 3.3 Mô hình hàm f(A,J) của DES Hình 3.4 Mô hình sinh khóa con của DES Hình 4.1 Sơ đồ quá trình tạo khóa mã hóa ECC Hình 4.2 Kiến trúc tổng thể phần mềm mã hóa tin nhắn Chức năng bảo mật tin nhắn Hình 4.3 Hình 4.5 Chức năng quản lý tin nhắn Chức năng quản lý danh bạ Hình 4.6 Quá trình bảo mật SMS Hình 4.7 Hình 4.8 Giao diện chính của chƣơng trình Giao diện chức năng quản lý tin nhắn SMS Hình 4.9 Giao diện chức năng quản lý danh bạ Hình 4.4 LỜI MỞ ĐẦU Hiện nay cùng với sự phát triển mạnh mẽ của các thiết bị cầm tay với ƣu điểm tiện lợi, linh hoạt thì nhu cầu xây dựng những ứng dụng trên các thiết bị này ngày càng lớn đặc biệt là các ứng dụng thƣơng mại điện tử. Do đó nhu cầu bảo mật thông tin trong các giao dịch sử dụng thiết bị cầm tay càng lớn. Một trong những đặc điểm của các thiết bị cầm tay là bộ nhớ nhỏ với tốc độ tính toán thấp. Xuất phát từ thực tế đó, các thuật toán mã hóa trên đƣờng cong Elliptic với ƣu điểm là tốc độ xử lý nhanh, không cần nhiều tài nguyên đã ra đời và rất thích hợp với các thiết bị cầm tay này vì nó vừa đảm bảo độ an toàn và không yêu cầu nhiều tài nguyên. Chính vì vậy em đã chọn đề tài:"Nghiên cứu phƣơng pháp bảo vệ thông tin dùng trên thiết bị cầm tay" làm đề tài luận văn thạc sỹ của mình. Nội dung của đề tài: Chương 1: Các khái niệm cơ bản Nêu lên một số khái niệm cơ bản về đại số, số học, các khái niệm về mã hóa, chữ ký số cũng nhƣ độ phức tạp thuật toán. Chương 2: Hệ mật mã trên đường cong Elliptic Tìm hiểu về đƣờng cong Elliptic, một số hệ mật trên đƣờng cong Elliptic và các tình huống xuất hiện khi sử dụng các hệ mật trên. Chương 3: Sử dụng một số hệ mật mã khác trên thiết bị cầm tay Nghiên cứu một số hệ mã khác dùng trên thiết bị cầm tay nhƣ: RC4, DES, 3DES. Chương 4: Thử nghiệm chương trình: Thử nghiệm chƣơng trình bảo mật tin nhắn trên điện thoại di động. Em xin chân thành cảm ơn PGS. TS Trịnh Nhật Tiến đã tận tình giúp đỡ em trong suốt quá trình viết luận văn này. Chương 1. CÁC KHÁI NIỆM CƠ BẢN 1.1. MỘT SỐ KHÁI NIỆM TRONG SỐ HỌC 1.1.1. Số nguyên tố 1.1.1.1. Khái niệm số nguyên tố Định nghĩa 1.1 Số nguyên tố là số nguyên lớn hơn 1, chỉ chia hết cho 1 và chính nó. Số nguyên lớn hơn 1 không phải là số nguyên tố gọi là hợp số. Định lý 1.1 (Định lý cơ bản của số học) Mọi số nguyên lớn hơn 1 đều phân tích được một cách duy nhất thành tích các số nguyên tố, trong đó các thừa số được viết với thứ tự không giảm. n=p1m1. p2m2…pkmk Chứng minh Xét tập F gồm tất cả các số nguyên lớn hơn 1 không biểu diễn đƣợc thành tích một số hữu hạn thừa số nguyên tố. Ta chỉ cần chỉ ra F=  . Thật vậy, giả sử F   . Khi đó có số nguyên dƣơng nhỏ nhất m thuộc F. Vì m  F nên m phải là hợp số. Khi đó có hai số nguyên dƣơng q1, q2 >1 để m = q1q2. Vì q1,q2 < m nên q1,q2  F. Nhƣ vậy ta có phân tích: q1 = t1t2 ... th và q2 = u1u2 ... uk Ở đó các ti, ui, đều là các số nguyên tố. Khi đó: m = q1q2 = t1t2 ... th u1u2 ... uk . Điều này mâu thuẫn với giả thiết m  F. Nhƣ vậy F phải là tập rỗng. Do đó mọi số tự nhiên lớn hơn 1 đều phân tích thành tích của hữu hạn thừa số nguyên tố. Bây giờ giả sử một số đƣợc phân tích thành hai tích dạng A và B các thừa số nguyên tố. Khi đó A = B. Bằng cách lƣợc bỏ tất cả các thừa số nguyên tố xuất hiện trong cả A và B, ta nhận đƣợc đẳng thức tƣơng đƣơng C=D. Ta cần phải chứng minh C=D=1. Giả sử trái lại, C = D  1. Gọi p là thừa số nguyên tố xuất hiện trong C. Khi đó p không thể là thừa số xuất hiện trong biểu thức tích của D. Có nghĩa là D không phải là bội của p, và do đó C cũng không là bội của p (mâu thuẫn!). Vậy C = D = 1. Điều này chứng tỏ rằng sự phân tích ra các thừa số nguyên tố của một số nguyên >1 là duy nhất nếu không kể đến thứ tự các thừa số. Định lý 1.2 Mọi hợp số n đều có ước nguyên tố nhỏ hơn n Chứng minh Vì n là một hợp số nên ta có thể viết n = ab, trong đó a và b là các số nguyên với 11hoặc a(n-1)/2    mod n, thì a là bằng chứng Euler (Euler witness) và n là hợp số. a n Mặt khác, nếu gcd(a, n) =1 và a(n-1)/2 =   mod n, thì a là giả mạo Euler (Euler liar) của n. Sau đây là thuật toán xác định a là bằng chứng Euler(Euler witness) của n là hợp số: Bƣớc đầu tiên của thuật toán là tính r = a(n-1)/2 mod n, giống nhƣ với thuật toán Fermat. Nếu r =  1 mod n, thì r2 = an-1 =1mod n, nên n là hợp số bằng thuật toán a Fermat. Bƣớc tiếp theo là tính Jacobi   và so sánh với r. Nếu không bằng nhau thì n n là một hợp số theo tiêu chuẩn Euler. Ngƣợc lại, thì n là số nguyên tố với xác suất nào đó. a n Chú ý có một vấn đề xuất hiện ở đây là việc tính Jacobi   . Giống nhƣ thuật toán Fermat, thuật toán Solovay-Strassen kiểm tra một số nguyên n là hợp số bằng cách thực hiện thuật toán euler-witness với vài giá trị ngẫu nhiên của a. Nếu có k giá trị a cho trả lời đúng thì n là hợp số. Ngƣợc lại thì k là số nguyên tố với xác suất nào đó, thuật toán đƣợc trình bày nhƣ sau: Nó không hiệu quả để kiểm tra tất cả các giá trị có thể của a, nên chúng ta muốn biết sự giống nhau giữa cách chọn lựa của a nhƣ thế nào, nếu n là hợp số, một giá trị a ngẫu nhiên là bằng chứng Euler (Euler witness) cho n là hợp số. Trong kiểm tra Fermat, chúng ta tìm thấy một tập chắc chắn các số là số Carmichael, có rất ít bằng chứng. Định lý dƣới đây sẽ đảm bảo rằng tiêu chuẩn Euler không giống số Carmichael. Định lý sử dụng phi hàm Euler: Định lý 1.5 Nếu n là hợp số nguyên lẻ, thì có nhiều nhất  (n)/2 giả mạo Euler (Euler liar) cho n trong đoạn [2, n-1]. Chúng ta biết rằng  (n)1 là số nguyên lẻ và với a, b là số nguyên bất kỳ. Thì ký hiệu Jacobi có các tính chất sau: a n a n (i)   =0, 1, hoặc -1. Hơn nữa,   =0 nếu và chỉ nếu gcd(a, n)  1  ab   a   b  =     n  n n (ii)   a   a  a =      mn   m   n  (iii)  a b n n (iv) Nếu a=b mod n thì   =   1 n (v)   =1  1  1 if n  1mod 4 (vi)    (1)( n1)/2    n  1if n  3mod 4 2 1 if n  1mod8 (vii)    (1)( n 1)/8   n 1if n  3mod8 m 2 n (viii)    (1)( m1)( n 1)/4 n m n  m if m  n  3mod 4    n  if m  1mod 4 or n  1mod 4   m  Các tính chất này cho phép chúng ta định nghĩa đệ quy ký hiệu Jacobi. Nếu n là số lẻ, và a=2ka1, và a1 cũng là số lẻ, thì: k a 2   n  n   a1   2k   n mod a1   a1 1 n 1 /4   1      a1   n   n   Định nghĩa đệ quy này đƣợc diễn giải bởi thuật toán sau, thuật toán hiệu quả để a n tính   mà không cần phải phân tích n thành thừa số nguyên tố: Thời gian chạy của thuật toán tính Jacobi là O(log2 n). Thuật toán Euler-witness a n thực hiện với hai phép tính chính: a(n-1)/2 mod n và   . Sử dụng phƣơng pháp bình phƣơng liên tiếp, phép tính thứ nhất thực hiện trong thời gian O(log n), và phép tính thứ hai đƣợc xác định thực hiện trong thời gian là O(log2 n). Các toán tử so sánh có thời gian chạy coi nhƣ không đáng kể, vì vậy độ phức tạp thời gian của thuật toán euler-witness là O(log2 n). Kiểm tra Solovay-Strassen thực hiện thuật toán k lần nên có thời gian thực hiện là O(k. log2 n). Với thuật toán Solovay-Strassen, chúng ta có (1/2)k khả năng phân loại sai cho thời gian thực hiện O(k. log2 n). Nhƣ vậy là chậm hơn thuật toán Fermat O(k.log n), nhƣng thuật toán Fermat không đƣa ra một giá trị cụ thể nào đảm bảo sự chặc chắn của mình kể cả sự tồn tại của số Carmichael. 3/. Thuật toán Miller-Rabin Thuật toán Miller Rabin là phiên bản sửa đổi của thuật toán Fermat sử dụng ý tƣởng đơn giản trình bày dƣới đây để tạo ra kiểm tra thiên về hợp số rất mạnh. Nó thay thế thuật toán Solovay-Strassen nhƣ là một chọn lựa đầu tiên để kiểm tra xác suất vì hiệu quả cao hơn và xác suất chính xác cũng cao hơn. Định lý 1.8: Nếu x2 = 1 mod n có nghiệm không tầm thường, thì n là hợp số. Giống nhƣ giả nguyên tố, thuật toán kiểm tra an-1 = 1 mod n và phân loại là số giả nguyên tố nếu đƣợc. Cũng nhƣ vậy, tuy nhiên, nó cũng kiểm tra bất thặng dƣ bậc hai (nontrivial square root) của 1 mod n bằng cách tính an-1 theo một cách riêng. Đầu tiên, nó biểu diễn n-1 = u.2t, u là số lẻ. Sau đó viết an-1 = au.2t = (au)2t đƣợc tính bằng cách bình phƣơng liên tiến au tổng cộng t lần. Thuật toán đầu tiên tính au sử dụng bình phƣơng liên tiếp (ordinary binary exponentiation), sau đó bình phƣơng nó t lần, giữ lại giá trị hiện tại(cur) và giá trị cuối cùng (last) ở mỗi bƣớc. Nếu cur = 1, thì last là thặng dƣ bậc hai (square root) của 1 mod n. Nếu last khác 1, hoặc -1, thì nó là bất thặng dƣ bậc hai (nontrivial square root) của 1 mod n, và do đó n là hợp số. Nếu mr-witness(a, n) trả về đúng (true), thì a là cơ sở cho n là hợp số. Kiểm tra Miller-Rabin chỉ đơn giản chạy thuật toán mr-witness với k lần ngẫu nhiên chọn gia trị a. Nếu bất kỳ giá trị nào chứng tỏ n là hợp số thì n là hợp số, ngƣợc lại n là số nguyên tố với xác suất nào đó: Thuật toán thể hiện mạnh hơn kiểm tra Fermat, bởi vì nó sử dụng định lý ở trên để tăng cƣờng kiểm tra hợp số. Định lý tiếp theo trình bày bằng chứng là những thay đổi tạo ra dấu hiệu cho thấy kiểm tra xác suất số nguyên tố tốt hơn. Định lý 1.9: Nếu n là hợp số lẻ, thì số bằng chứng chứng tỏ n là hợp số ít nhất bằng 3/4 (n-1) Theo định lý này nều n là hợp số thì ít nhất 75% khẳ năng chứng tỏ là hợp số với bất kỳ giá trị ngẫu nhiên của cơ sở. Kiểm tra Miller – Rabin sẽ chỉ có lỗi nếu nó chọn k cở sở kiểm tra từ tập hợp bằng chứng sai. Xác suất sai đƣợc phát biểu bởi hệ quả của định lý dƣới đây: Hệ quả: Nếu thuật toán Miller – Rabin với tham số n và k phân loại n là nguyên tố, thì xác suất sai nhiều nhất là (1/4)k. Cũng nhƣ thuật toán Solovay–Strassen, xác suất sai độc lập với n. Ví dụ, nếu chọn k = 25, thì Miller – Rabin rất có khả nẳng tìm ra một bằng chứng cho n là hợp số, dù chỉ là một. Nếu nó không tìm đƣợc bằng chứng, thì xác suất n là nguyên tố với xác suất sai là (1/4)25 = 10-15. Thuât toán mr-witness thực hiện với độ phức tạp thời gian O(log n), về bản chất nó tính an-1 mod n bằng phƣơng pháp bình phƣơng liên tiếp. Nghĩa là độ phức tạp của nó tƣơng đƣơng với thuật toán giả nguyên tố của kiểm tra Fermat, nhƣng kiêm tra thiên về hợp số mạnh hơn. Thuật toán Miller–Rabin thực hiện mr-witness k lần, nên độ phƣc tạp thời gian là O(k . logn). Kiểm tra Miller–Rabin cho khả năng phân loại sai là (1/4)k với độ phức tạp O(k. log n). Vì đây là thuật toán xác suất tìm số nguyên tố tốt nhất hiện này, nên trong luận văn này xin trình bày một số ví dụ mình hoạ Ví dụ 1: Lấy n = 91 = 7.13, n-1=90=21.45, nên s=1. Chú ý 91 là hợp số (a). Chọn ngẫu nhiên cơ sở a=10. Bắt đầu với b=1045 mod 91 = 90. Do đó thuật toán kết luận là số nguyên tố. Tuy nhiên , chúng ta biết rằng 91 không phải là số nguyên tố, vậy 10 là một cơ sở cho kết luận sai. (b). Chọn ngẫu nhiên cơ sở a=29. Bắt đầu với b=2945 mod 91 = 1. Do đó thuật toán lại trả về kết quả đúng (true), và 29 cũng là một cơ sở cho kết luận sai. (c). Cuối cùng, chọn a=2 bắt đầu với b=245 mod 91 = 57. Ở đây thuật toán không thể vào vòng lặp ( bởi vì s-1=0), thuật toán đến dòng 14, và từ đây cho kết quả sai (false). Vậy 91 đƣợc xác định là hợp số. Ví dụ 2: Lấy n=101, n-1=100=22.25, nên s=2. Chú ý 101 là số nguyên tố (a). Giả sử a=17, có b=100, và thuật toán kết luận là số nguyên tố. (b). Giả sử a=19, có b=1, và thuật toán kết luận là số nguyên tố. (c). Giả sử a=29. Có b=91, nên vào vòng lặp. Tính b=912 mod 101, kết quả là 100, thuật toán kết luận là số nguyên tố. (d). Giả sử a=3. Có b=10, nên vào vòng lặp. Tính b=102 mod 101, kết quả là 100, thuật toán kết luận là số nguyên tố. Ở đây, 4 lần kiểm tra đều cho kết quả là số nguyên tố (với xác suất nào đó). Xác suất sai cho cho kết quả là <= 1/44 = 1/256. Vậy theo thuật toán thì 101 là số nguyên tố với xác suất là 1-1/256 = 0.9961. 1.1.2 Các tính toán trong Zn * 1.1.2.1 Tập hợp Zn và Zn * Định nghĩa 1.7 (Khái niệm đồng dư) Nếu a và b là các số nguyên thì a đƣợc gọi là đồng dƣ với b theo modulo (ký hiệu là a  b mod n ) nếu n a  b  . Số nguyên n đƣợc gọi là modulo đồng dƣ. Ví dụ: 24  9 mod 5 vì 24  9  3.5  11  17 mod 7 vì  11  17  4.7 Các tính chất: Đối với a, a1 , b, b1 , c   ta có: (1) a  bmod n  nếu và chỉ nếu a và b cũng có phần dƣ khi chia cho n. (2) Tính phản xạ : a  a mod n  . (3) Tính đối xứng : Nếu a  bmod n  thì b  a mod n  (4) Tính bắc cầu : Nếu a  bmod n  và b  cmod n  thì a  cmod n  (5) Nếu a  a1 mod n  và b  b1 mod n  thì a  b  a1  b1 mod n  và a.b  a1.b1 mod n  Lớp tƣơng đƣơng của một số nguyên a là tập các số nguyên đồng dƣ với a modulo n. Từ các tính chất (2), (3) và (5) ở trên ta có thể thấy rằng đối với n cố định, quan hệ đồng dƣ theo modulo n sẽ phân hoạch Z thành các lớp tƣơng đƣơng. Nếu a  qn  r với 0  r  n thì a  rmod n  . Bởi vậy mỗi số nguyên a là đồng dƣ theo modulo n với một số nguyên duy nhất nằm trong khoảng từ 0 tới n  1, số này đƣợc gọi là thặng dƣ tối thiểu của a mod n . Nhƣ vậy a và r có thể đƣợc dùng để biểu thị cho lớp tƣơng đƣơng này. Định nghĩa 1.8 Không gian Zn (các số nguyên theo modulo n) là tập hợp các số nguyên {0,1,2,…,n-1}. Các phép toán trong Zn nhƣ cộng, trừ, nhân, chia đều đƣợc thực hiện theo module n. Ví dụ: Z11 = {0,1,2,3,…,10} Trong Z11: 6 + 7 = 2, bởi vì 6 + 7 = 13 2 (mod 11).