Khóa luận Nghiên cứu một số chữ ký số đặc biệt và ứng dụng

ĐẠI HỌC QUỐC GIA HÀ NỘI TRƢỜNG ĐẠI HỌC CÔNG NGHỆ Phạm Thị Vân Anh NGHIÊN CỨU MỘT SỐ CHỮ KÝ SỐ ĐẶC BIỆT VÀ ỨNG DỤNG KHOÁ LUẬN TỐT NGHIỆP ĐẠI HỌC HỆ CHÍNH QUY Ngành: Công nghệ thông tin HÀ NỘI - 2010 ĐẠI HỌC QUỐC GIA HÀ NỘI TRƢỜNG ĐẠI HỌC CÔNG NGHỆ Phạm Thị Vân Anh NGHIÊN CỨU MỘT SỐ CHỮ KÝ SỐ ĐẶC BIỆT VÀ ỨNG DỤNG KHOÁ LUẬN TỐT NGHIỆP ĐẠI HỌC HỆ CHÍNH QUY Ngành: Công nghệ thông tin Cán bộ hƣớng dẫn: PGS.TS. Trịnh Nhật Tiến HÀ NỘI - 2010 LỜI CẢM ƠN Trƣớc hết, em xin gửi lời cảm ơn sâu sắc tới PGS.TS. Trịnh Nhật Tiến đã hƣớng dẫn em phát triển khóa luận đi từ lý thuyết đến ứng dụng. Sự hƣớng dẫn của thầy trong suốt thời gian qua đã giúp em tiếp cận tới một hƣớng nghiên cứu khoa học mới: đó là nghiên cứu trong lĩnh vực an toàn thông tin. Qua đó, những lý thuyết về an toàn thông tin đã lôi cuốn em và sẽ trở thành hƣớng nghiên cứu tiếp của em sau khi tốt nghiệp. Em xin bày tỏ lòng biết ơn đến các thầy cô trong trƣờng Đại học Công nghệ đã giảng dạy và cho em những kiến thức quý báu, làm nền tảng để em hoàn thành khóa luận cũng nhƣ thành công trong nghiên cứu, làm việc trong tƣơng lai. Cuối cùng, cho em gửi lời cảm ơn sâu sắc tới gia đình, bạn bè đã động viên kịp thời để em học tập tốt và hoàn thành đƣợc khóa luận. Em xin chân thành cảm ơn! Hà Nội, tháng 5 năm 2010 Sinh viên Phạm Thị Vân Anh TÓM TẮT KHÓA LUẬN Những năm gần đây, nhu cầu trao đổi thông tin từ xa của con ngƣời ngày càng lớn, các ứng dụng trao đổi thông tin qua mạng diễn ra ngày càng nhiều. Tuy nhiên, mỗi loại ứng dụng có những đòi hỏi riêng khác nhau, ví dụ nhƣ ứng dụng bầu cử từ xa cần phải che dấu đƣợc thông tin ngƣời bỏ phiếu, hoặc những văn bản đã đƣợc ký nhƣng không muốn ai cũng có thể xác thực chữ ký khi chƣa đƣợc sự đồng ý của ngƣời ký. Chữ ký mù và chữ ký không thể chối bỏ đã ra đời để giải quyết vấn đề nêu trên. Ý tƣởng chính của ký mù là ngƣời ký không biết mình đang ký trên nội dung gì. Ý tƣởng chính của chữ ký không thể chối bỏ là chữ ký mà ngƣời ký tham gia trực tiếp vào quá trình xác thực chữ ký. Khóa luận tốt nghiệp này đề cập về mặt lý thuyết của hai loại chữ ký trên, xây dựng ứng dụng minh họa tƣơng ứng với từng loại chữ ký; đồng thời xây dựng một ứng dụng thực hiện ký số RSA trên file văn bản tiếng Việt sử dụng thƣ viện mã nguồn mở OpenSSL. MỤC LỤC LỜI MỞ ĐẦU .............................................................................................. 1 Chương 1. CÁC KHÁI NIỆM CƠ BẢN .............................................. 3 1.1. CÁC KHÁI NIỆM TRONG TOÁN HỌC ........................................ 3 1.1.1. Một số khái niệm trong số học .......................................................... 3 1.1.2. Một số khái niệm trong đại số ......................................................... 13 1.1.3. Khái niệm độ phức tạp của thuật toán ............................................. 17 1.2. MÃ HÓA ........................................................................................ 21 1.2.1. Khái niệm mã hóa dữ liệu ............................................................... 21 1.2.2. Phân loại hệ mã hóa ........................................................................ 22 1.3. KÝ SỐ ............................................................................................. 25 1.3.1. Khái niệm chữ ký số ........................................................................ 25 1.3.2. Phân loại chữ ký số. ........................................................................ 25 1.3.3. So sánh chữ ký thông thƣờng và chữ ký số .................................... 26 1.3.4. Tạo đại diện tài liệu và hàm băm .................................................... 27 Chương 2. CHỮ KÝ MÙ RSA ............................................................ 30 2.1. KHÁI NIỆM CHỮ KÝ MÙ ........................................................... 30 2.1.1. Sơ đồ chữ ký RSA ........................................................................... 30 2.1.2. Sơ đồ chữ ký mù RSA ..................................................................... 31 2.1.3. Ví dụ minh họa ................................................................................ 32 2.2. ỨNG DỤNG CHỮ KÝ MÙ ........................................................... 33 2.2.1. Ứng dụng trong tiền điện tử ............................................................ 33 2.2.2. Ứng dụng trong bỏ phiếu trực tuyến. .............................................. 34 Chương 3. CHỮ KÝ KHÔNG THỂ CHỐI BỎ ................................ 36 3.1. KHÁI NIỆM CHỮ KÝ KHÔNG THỂ CHỐI BỎ ......................... 36 3.1.1. Sơ đồ chữ ký không thể chối bỏ Chaum – Van Antwerpen ............ 36 3.1.2. Ví dụ minh họa ................................................................................ 38 3.1.3. Một số đánh giá về sơ đồ ................................................................. 39 3.2. HÌNH THỨC TẤN CÔNG CHỮ KÝ KHÔNG THỂ CHỐI BỎ .. 43 3.2.1. Tống tiền ngƣời ký .......................................................................... 43 3.2.2. Nhiều ngƣời cùng xác thực chữ ký mà ngƣời ký không biết .......... 43 3.3. ỨNG DỤNG CHỮ KÝ KHÔNG THỂ CHỐI BỎ ......................... 45 3.3.1. Ứng dụng trong thẻ chứng minh thƣ điện tử. .................................. 45 3.3.2. Ứng dụng trong ký hợp đồng qua điện thoại .................................. 45 Chương 4. THỬ NGHIỆM CÁC CHƢƠNG TRÌNH ...................... 46 4.1. THỬ NGHIỆM ỨNG DỤNG CHỮ KÝ SỐ .................................. 46 4.1.1. Giới thiệu ......................................................................................... 46 4.1.2. Mô tả hoạt động chƣơng trình ......................................................... 47 4.2. THỬ NGHIỆM CHƢƠNG TRÌNH KÝ MÙ RSA ........................ 53 4.2.1. Giới thiệu ......................................................................................... 53 4.2.2. Mô tả hoạt động chƣơng trình ......................................................... 53 4.3. THỬ NGHIỆM CHỮ KÝ KHÔNG THỂ CHỐI BỎ ..................... 55 4.3.1. Giới thiệu ......................................................................................... 55 4.3.2. Mô tả hoạt động chƣơng trình ......................................................... 56 KẾT LUẬN ................................................................................................ 60 DANH SÁCH BẢNG Bảng 1: Ví dụ sử dụng thuật toán Euclide tìm ước chung lớn nhất .......................5 Bảng 2: Ví dụ sử dụng thuật toán Euclide mở rộng để tìm phần tử nghịch đảo ..16 Bảng 3: Thời gian chạy của các lớp thuật toán khác nhau ..................................19 DANH SÁCH HÌNH VẼ Hình 1: Giao diện chương trình ký số RSA ..........................................................46 Hình 2: Giao diện chức năng “Ký”RSA ...............................................................47 Hình 3: Giao diện chức năng xác thực chữ ký số RSA .........................................49 Hình 4: Giao diện chức năng mã hóa DES file văn bản và chữ ký ......................50 Hình 5: Giao diện chức năng giải mã DES ..........................................................51 Hình 6: Giao diện chức năng ký mù .....................................................................53 Hình 7: Giao diện chức năng xóa mù chữ ký .......................................................54 Hình 8: Giao diện của người ký chữ ký không thể chối bỏ ..................................55 Hình 9: Giao diện của người xác thực chữ ký không thể chối bỏ ........................55 Hình 10: Thông báo khi chữ ký không thể chối bỏ được xác thực là đúng ..........57 Hình 11: Thông báo khi điều kiện 𝒅 ≡ 𝒙𝒆𝟏𝒈𝒆𝟐𝒎𝒐𝒅 𝒑 không được thỏa mãn ...58 Hình 12: Thông báo khi chữ ký đúng là giả mạo .................................................58 Hình 13: Thông báo khi phát hiện người ký cố tình chối bỏ chữ ký của mình .....59 1 LỜI MỞ ĐẦU Trong những năm gần đây, sự bùng nổ của cách mạng thông tin đang diễn ra nhanh chóng trên phạm vi toàn thế giới. Sự phổ biến rộng rãi của Internet đã kết nối mọi ngƣời trên toàn thế giới lại với nhau, trở thành công cụ không thể thiếu, làm tăng hiệu quả làm việc, tăng sự hiểu biết, trao đổi, cập nhật các thông tin một cách nhanh chóng và tiện lợi. Tuy nhiên Internet là một mạng mở, nó cũng chứa đựng nhiều hiểm họa đe dọa hệ thống mạng, hệ thống máy tính, tài nguyên thông tin của các tổ chức, cá nhân. Ví dụ những tin tức quan trọng nằm ở kho dữ liệu hay đang trên đƣờng truyền có thể bị trộm cắp, bị làm cho sai lệch hoặc có thể bị làm giả mạo. Vì thế, nảy sinh yêu cầu phải làm thế nào để văn bản khi đƣợc gửi sẽ không đƣợc nhìn thấy hay khó có thể giả mạo dù cho có thể xâm nhập vào văn bản. Với sự ra đời của công nghệ mã hóa và chữ ký số đã trợ giúp cho con ngƣời trong việc giải quyết các bài toán nan giải về an toàn thông tin. Một tình huống nảy sinh khi trao đổi thông tin trên mạng, đó là khi ngƣời ta nhận đƣợc một văn bản truyền trên mạng thì làm sao để có thể đảm bảo rằng đó là của đối tác gửi cho mình. Tƣơng tự, ngƣời nhận nhận đƣợc tờ tiền điện tử thì có cách nào để xác nhận rằng đó là của đối tác đã thanh toán cho họ. Ngoài ra còn có rất nhiều các hoạt động kinh tế, xã hội từ xa nhƣ đàm phán, thanh toán, gửi tiền từ xa,... Do đó chữ ký số đƣợc sử dụng ở rất nhiều lĩnh vực: trong kinh tế với việc trao đổi các hợp đồng của các đối tác kinh doanh, trong xã hội là các cuộc bỏ phiếu điện tử hay thăm dò thông tin từ xa,… Tuy nhiên, yêu cầu về chữ ký đặt ra với các ứng dụng là khác nhau. Có những ứng dụng đòi hỏi sự nặc danh của tài liệu đƣợc ký nhƣ ứng dụng bỏ phiếu điện tử, tiền điện tử. Một số ứng dụng khác lại yêu cầu sự tham gia của ngƣời ký vào quá trình xác thực chữ ký. Chữ ký mù (ra đời năm 1983) và chữ ký không thể chối bỏ ( ra đời năm 1989 ) đã giải quyết hai vấn đề nêu ra ở trên. Trong khóa luận này, em chú trọng vào tìm hiểu cơ sở lý thuyết của chữ ký mù và chữ ký không thể chối bỏ kèm theo ứng dụng minh họa với từng loại. Đồng thời xây dựng một ứng dụng thử nghiệm chữ ký số RSA trên file text tiếng Việt. Khóa luận bao gồm các phần cụ thể sau: Chƣơng 1: Các khái niệm cơ bản: nêu lên những lý thuyết toán học cơ bản mà bất kỳ bài toán an toàn thông tin nào cũng cần tới, các khái niệm cơ bản về mã hóa và ký số. 2 Chƣơng 2: Chữ ký mù RSA: trình bày về sơ đồ chữ ký mù RSA, ví dụ minh họa và ứng dụng chữ ký mù. Chƣơng 3: Chữ ký không thể chối bỏ: trình bày về sơ đồ chữ ký không thể chối bỏ Chaum van Antwerpen, ví dụ minh họa, các hình thức tấn công chữ ký không thể chối bỏ và ứng dụng của của chữ ký này. Chƣơng 4: Thử nghiệm các chƣơng trình: thử nghiệm chƣơng trình chữ ký số RSA, chƣơng trình chữ ký mù RSA và chƣơng trình chữ ký không thể chối bỏ. Kết luận. 3 Chương 1. CÁC KHÁI NIỆM CƠ BẢN 1.1. CÁC KHÁI NIỆM TRONG TOÁN HỌC 1.1.1. Một số khái niệm trong số học 1.1.1.1. Ước chung lớn nhất, bội chung nhỏ nhất 1/. Khái niệm - Ước số và bội số + Cho hai số nguyên a và b, b ≠ 0. Nếu có một số nguyên q sao cho a = b*q, ta nói rằng a chia hết cho b, kí hiệu b\a. Ta nói b là ước của a, và a là bội của b. Ví dụ: a = 6, b = 2, ta có 6 = 2*3, ký hiệu 2\6. Ở đây 2 là ƣớc của 6 và 6 là bội của 2 + Cho các số nguyên a, b ≠ 0, tồn tại cặp số nguyên (q, r) (0  r < /b/) duy nhất sao cho a = b * q + r. Khi đó q gọi là thương nguyên, r gọi là số dư của phép chia a cho b. Nếu r = 0 thì ta có phép chia hết. Ví dụ: Cho a = 13, b = 5, ta có 13 = 5*2 + 3. Ở đây thƣơng là q = 2, số dƣ là r = 3. - Ước chung lớn nhất, bội chung nhỏ nhất + Số nguyên d đƣợc gọi là ƣớc chung của các số nguyên 𝑎1, 𝑎2, …, 𝑎𝑛 , nếu nó là ƣớc của tất cả các số đó. + Số nguyên m đƣợc gọi là bội chung của các số nguyên 𝑎1, 𝑎2, …, 𝑎𝑛 , nếu nó là bội của tất cả các số đó. + Một ƣớc chung d > 0 của các số nguyên 𝑎1, 𝑎2, …, 𝑎𝑛 , trong đó mọi ƣớc chung của 𝑎1, 𝑎2, …, 𝑎𝑛 đều là ƣớc của d, thì d đƣợc gọi là ƣớc chung lớn nhất (UCLN) của 𝑎1, 𝑎2, …, 𝑎𝑛 . Ký hiệu d = gcd (𝑎1, 𝑎2, …, 𝑎𝑛 ) hay d = UCLN(𝑎1, 𝑎2, …, 𝑎𝑛 ). Nếu gcd(𝑎1, 𝑎2, …, 𝑎𝑛 ) = 1, thì các số 𝑎1, 𝑎2, …, 𝑎𝑛 đƣợc gọi là nguyên tố cùng nhau. + Một bội chung m > 0 của các số nguyên 𝑎1, 𝑎2, …, 𝑎𝑛 , trong đó mọi bội chung của 𝑎1, 𝑎2, …, 𝑎𝑛 đều là bội của m, thì m đƣợc gọi là bội chung nhỏ nhất (BCNN) của 𝑎1, 𝑎2, …, 𝑎𝑛 . Ký hiệu m = lcm(𝑎1, 𝑎2, …, 𝑎𝑛 ) hay m = BCNN(𝑎1, 𝑎2, …, 𝑎𝑛 ). 4 Ví dụ: Cho a =12, b =15, gcd(12, 15) = 3, lcm(12, 15) = 60. Hai số 8 và 13 là nguyên tố cùng nhau, vì gcd(8, 13) = 1. - Tập 𝒁𝒏 và 𝒁𝒏 ∗ + 𝑍𝑛 = 0, 1, 2, .. . , n-1 là tập các số nguyên không âm < n. + 𝑍𝑛 ∗= e  𝑍𝑛 , e là nguyên tố cùng nhau với n. Tức là e ≠ 0. Ví dụ: Z7 = {0, 1, 2, 3, 4, 5, 6}. Khi đó số phần tử của Z7 là |Z7 | = 7. 𝑍7 ∗ = {1, 2, 3, 4, 5, 6}. Khi đó số phần tử của 𝑍7 ∗ là |𝑍7 ∗| = 6. 2/. Tính chất - d = gcd(𝑎1, 𝑎2, …, 𝑎𝑛 )  tồn tại các số x1, x2,…, xn sao cho: d = a1x1 + a2x2 + … + anxn Đặc biệt: a1, a2, …, an nguyên tố cùng nhau  tồn tại các số x1, x2,…, xn sao cho: 1 = a1x1 + a2x2 + … + anxn - d = gcd(𝑎1, 𝑎2, …, 𝑎𝑛 )  gcd(𝑎1/𝑑, 𝑎2/𝑑, …, 𝑎𝑛/𝑑) =1. - m = lcm(𝑎1, 𝑎2, …, 𝑎𝑛 )  gcd(𝑚/𝑎1, 𝑚/𝑎2, …, 𝑚/𝑎𝑛 ) =1. - gcd(𝑚𝑎1, m𝑎2, …, m𝑎𝑛 ) = m * gcd(𝑎1, 𝑎2, …, 𝑎𝑛 ) (với m ≠ 0). - Nếu gcd(a, b) =1 thì lcm(a, b) = a * b - Nếu b > 0, a = bq + r thì gcd(a, b) = gcd(b, r) 3/. Thuật toán Euclide tìm ƣớc chung lớn nhất - Bài toán + Dữ liệu vào: Cho hai số nguyên không âm a, b, a ≥ b. + Kết quả: gcd(a,b). - Thuật toán (Mô phỏng bằng ngôn ngữ Pascal): Readln(a, b); While b>0 do begin r := a mod b; a := b; b := r; end; Writeln(a); 5 Ví dụ: a=30, b=18; gcd(30,18) = gcd(18,12) = gcd(12,6) = gcd(6,0) = 6 Bảng 1: Ví dụ sử dụng thuật toán Euclide tìm ước chung lớn nhất a b r a = b.q + r 30 18 12 30 = 18 * 1+12 18 12 6 18 = 12 * 1+6 12 6 0 12 = 6 * 2 + 0 4/. Thuật toán Euclide mở rộng - Bài toán: + Dữ liệu vào: Cho hai số nguyên không âm a, b, a ≥ b. + Kết quả: d = gcd (a,b) và hai số x, y sao cho: a.x + b.y = d. - Thuật toán (Mô phỏng bằng ngôn ngữ Pascal): Readln(a, b); IF b=0 THEN Begin d := a; x := 1; y := 0; writeln(d, x, y); End ELSE Begin x2 := 1; x1 := 0; y2 := 0; y1 := 1; While b>0 Do begin q := a div b; r := a mod b;x := x2 – q * x1; y := y2 – q * y1; a := b; b := r; x2 := x1; x1 := x; y2 := y1; y1 := y; end; d := a; x := x2; y := y2; writeln(d, x1, x2); End; 6 1.1.1.2. Quan hệ “Đồng dư” 1/. Khái niệm - Cho các số nguyên a, b, m (m > 0). Ta nói rằng a và b “đồng dư” với nhau theo modulo m nếu chia a và b cho m ta nhận đƣợc cùng một số dƣ. Ký hiệu: a ≡ b (mod m). Ví dụ: 17 ≡ 5 (mod 3) vì chia 17 và 5 cho 3, đƣợc cùng số dƣ là 2. - Nhận xét: Các mệnh đề sau đây là tƣơng đƣơng: + a ≡ b (mod m) (1) + m \ (a – b) (2) + Tồn tại số nguyên t sao cho a = b + m.t (3) Chứng minh: + (1)  (2): Nếu có (1), thì theo định nghĩa: a, b chia cho m, phải có cùng số dƣ, do đó: a = mqa + r; b = mqb + r; Suy ra (a – b) = m.(qa - qb), tức là m \ (a - b). + (2)  (3): Nếu có (2), tức là m\(a – b). Nghĩa là có t ∈ Z sao cho a - b = mt hay a = b + mt + (3)  (1): Nếu có (3), tức là tồn tại số nguyên t sao cho a = b + m.t. Lấy a chia cho m, giả sử thƣơng là qa và dƣ r, hay a = mqa + r (0 ≤ r < m), do đó: b + m.t = a = mqa + r hay b = m(qa - t) + r (0 ≤ r < m). Điều đó chứng tỏ khi chia a và b cho m đƣợc cùng số dƣ r, hay a ≡ b (mod m). 2/. Các tính chất của quan hệ “đồng dƣ” - Quan hệ “đồng dư” là quan hệ tương đương trong Z Với mọi số nguyên dƣơng m ta có: + a ≡ a (mod m) với mọi a ∈ Z (tính chất phản xạ) + a ≡ b (mod m) thì b ≡ a (mod m) (tính chất đối xứng) + a ≡ b (mod m) và b ≡ c (mod m) thì a ≡ c (mod m) (tính chất bắc cầu) 7 - Tổng hay hiệu các “đồng dư” + (a+b) (mod n)  [(a mod n) + (b mod n)] (mod n) + (a- b) (mod n)  [(a mod n) - (b mod n)] (mod n) Tổng quát: Có thể cộng hoặc trừ từng vế nhiều đồng dƣ thức theo cùng một modulo m, ta đƣợc một đồng dƣ thức theo cùng modulo m, tức là: Nếu ai ≡ bi (mod m), i = 1...k, thì: 𝑡𝑖𝑎𝑖 ≡ 𝑡𝑖𝑏𝑖(𝑚𝑜𝑑 𝑚) 𝑘 𝑖=1 𝑣ớ𝑖 𝑡𝑖 = ± 1 𝑘 𝑖=1 - Tích các “đồng dƣ”: (a * b) (mod n)  [(a mod n) * (b mod n)] (mod n) Tổng quát: Có thể nhân từng vế nhiều đồng dƣ thức theo cùng một modulo m, ta đƣợc một đồng dƣ thức theo cùng modulo m, tức là: Nếu ai ≡ bi (mod m) với i = 1...k, thì ta có: 𝑎𝑖 ≡ 𝑏𝑖 𝑘 𝑖=1 (𝑚𝑜𝑑 𝑚) 𝑘 𝑖=1 - Hệ quả: + Có thể cộng hoặc trừ cùng một số vào hai vế của một đồng dƣ thức. + Có thể chuyển vế các số hạng của đồng dƣ thức bằng cách đổi dấu các số hạng đó. + Có thể cộng vào một vế của đồng dƣ thức một bội của modulo: a ≡ b (mod m)  a + km ≡ b (mod m) với mọi k  Z + Có thể nhân hai vế của một đồng dƣ thức với cùng một số: a ≡ b (mod m)  ac ≡ bc (mod m) với mọi c  Z + Có thể nâng lên lũy thừa bậc nguyên không âm cho 2 vế của một đồng dƣ thức: a ≡ b (mod m)  an ≡ bn (mod m) với mọi n  Z+ + Có thể chia 2 vế đồng dƣ thức cho một ƣớc chung nguyên tố với modulo: c\a, c\b, (c,m) = 1, a ≡ b (mod m)  a/c ≡ b/c (mod m) 8 + Có thể nhân 2 vế đồng dƣ thức và modulo với cùng một số nguyên dƣơng: Nếu a ≡ b (mod m), c > 0  ac ≡ bc (mod mc) + Có thể chia 2 vế đồng dƣ thức và modulo cho cùng một số nguyên dƣơng là ƣớc chung của chúng: Nếu c \ (a, b, m)  a/c ≡ b/c (mod m/c) + a ≡ b (mod m)  a ≡ b (mod k) với k \ m + a ≡ b (mod m)  gcd(a, m) = gcd(b, m) 3/. Các lớp thặng dƣ - Quan hệ “đồng dƣ” theo modulo m trên tập Z (tập các số nguyên) là một quan hệ tƣơng đƣơng (vì có tính chất phản xạ, đối xứng, bắc cầu), do đó nó tạo ra trên tập Z một phân hoạch gồm các lớp tƣơng đƣơng: hai số nguyên thuộc cùng một lớp tƣơng đƣơng khi và chỉ khi chúng có cùng một số dƣ khi chia cho m. - Mỗi lớp tƣơng đƣơng đại diện bởi một số duy nhất trong Zm = {0, 1, 2,…, m-1} là số dƣ khi chia các số trong lớp cho m, ký hiệu một lớp đƣợc đại diện bởi số a là [a]m .Nhƣ vậy [a]m = [b]m  a ≡ b (mod m) Vì vậy ta có thể đồng nhất Zm với tập các lớp tƣơng đƣơng theo modulo m. - Zm ={0, 1, 2,…, m-1} đƣợc gọi là tập các “thặng dư đầy đủ” theo modulo m. Mọi số nguyên bất kỳ đều có thể tìm đƣợc trong Zm một số đồng dƣ với mình theo modulo m. 1.1.1.3. Số nguyên tố 1/. Khái niệm Số nguyên tố là số tự nhiên lớn hơn 1 và chỉ có hai ƣớc là 1 và chính nó. Ví dụ: Các số 2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37 là số nguyên tố. 2/. Một số định lý về số nguyên tố - Định lý: về số nguyên dương > 1 Mọi số nguyên dƣơng n > 1 đều có thể biểu diễn đƣợc duy nhất dƣới dạng: 1 2 kn n n 1 2 k . ...=P P Pn trong đó: k, ni (i =1,2,..,k) là các số tự nhiên, Pi là các số nguyên tố, từng đôi một khác nhau. 9 - Định lý: Mersenne Cho p = 2 k -1, nếu p là số nguyên tố thì k phải là số nguyên tố. Chứng minh Bằng phản chứng, giả sử k không là nguyên tố. Khi đó k = a.b với 1 < a, b < k. Nhƣ vậy p = 2k -1 = 2ab -1 = (2a)b -1= (2a -1).E (Trong đó E là một biểu thức nguyên - áp dụng công thức nhị thức Newton). Điều này mâu thuẫn giả thiết p là nguyên tố. Vậy giả sử là sai, hay k là số nguyên tố. - Hàm Euler Cho số nguyên dƣơng n, số lƣợng các số nguyên dƣơng bé hơn n và nguyên tố cùng nhau với n đƣợc ký hiệu (𝒏) và gọi là hàm Euler. + Nhận xét: Nếu p là số nguyên tố, thì  𝒑 = 𝒑 − 𝟏 Ví dụ: Tập các số nguyên không âm nhỏ hơn 7 là Z7 = {0, 1, 2, 3, 4, 5, 6}. Do 7 là số nguyên tố, nên tập các số nguyên dƣơng nhỏ hơn 7 và nguyên tố cùng nhau với 7 là Z7 * = {1, 2, 3, 4, 5, 6}. Khi đó |Z| = (p) = p - 1 = 7 - 1 = 6 + Định lý về hàm Euler Nếu n là tích của hai số nguyên tố p, q thì  𝑛 =  𝑝 . 𝑞 = 𝑝 − 1 . 𝑞 − 1 3/. Một