Tài liệu Tìm hiểu, nghiên cứu một số chữ ký đặc biệt dùng trong bỏ phiếu điện tử

ĐẠI HỌC QUỐC GIA HÀ NỘI TRƢỜNG ĐẠI HỌC CÔNG NGHỆ LẠI THỊ KIM CHINH TÌM HIỂU, NGHIÊN CỨU MỘT SỐ CHỮ KÝ ĐẶC BIỆT DÙNG TRONG BỎ PHIẾU ĐIỆN TỬ LUẬN VĂN THẠC SĨ Hà Nội - 2014 ĐẠI HỌC QUỐC GIA HÀ NỘI TRƢỜNG ĐẠI HỌC CÔNG NGHỆ LẠI THỊ KIM CHINH TÌM HIỂU, NGHIÊN CỨU MỘT SỐ CHỮ KÝ ĐẶC BIỆT DÙNG TRONG BỎ PHIẾU ĐIỆN TỬ Ngành: Công nghệ Thông tin Chuyên ngành: Hệ thống Thông tin Mã số : 60.48.01.04 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 - 2014 3 LỜI CAM ĐOAN Tôi xin cam đoan toàn bộ nội dung bản luận văn “Tìm hiểu, nghiên cứu một số chữ ký đặc biệt dùng trong bỏ phiếu điện tử” là do tôi tự sƣu tầm, tra cứu và tìm hiểu theo tài liệu tham khảo và làm theo hƣớng dẫn của ngƣời hƣớng dẫn khoa học. Nội dung bản luận văn chƣa từng đƣợc công bố hay xuất bản dƣới bất kỳ hình thức nào và cũng không đƣợc sao chép từ bất kỳ một công trình nghiên cứu nào. Các nguồn lấy từ tài liệu tham khảo đều đƣợc chú thích rõ ràng, đúng quy định. Nếu sai tôi xin hoàn toàn chịu trách nhiệm. Hà nội, tháng 07 năm 2014 Ngƣời cam đoan Lại Thị Kim Chinh 4 LỜI MỞ ĐẦU Luận văn tiến hành trình bày hai loại chữ ký số: chữ ký mù và chữ ký nhóm. Sau đó dựa vào kết quả nghiên cứu để áp dụng giải quyết một số vấn đề mất an toàn, an ninh trong quy trình bỏ phiếu điện tử. Các nội dung cơ bản của luận văn có cấu trúc nhƣ sau: Chương 1. Một số khái niệm cơ bản Trình bày một số khái niệm về số học, lý thuyết mật mã, và chữ ký số. Chương 2. Một số loại chữ ký đặc biệt Trình bày chi tiết về khái niệm, sơ đồ chữ ký số mù RSA, ví dụ minh họa và khái niệm, sơ đồ chữ ký của ba dạng chữ ký số nhóm, hiệu quả của mỗi loại chữ ký, vấn đề mở chữ ký nhóm, nhận xét về chữ ký nhóm. Chương 3. Ứng dụng một số loại chữ ký đặc biệt trong bỏ phiếu từ xa Trình bày khái quát về bỏ phiếu từ xa, quy trình bỏ phiếu từ xa, một số vấn đề mất an toàn, an ninh trong quy trình bỏ phiếu từ xa, cách giải quyết các vấn đề nêu trên. Chương 4. Thử nghiệm chữ ký mù RSA Trình bày bài toán lập trình để xây dựng hai chƣơng trình ký số mù RSA lên một số và lên một văn bản ngắn.Hƣớng dẫn sử dụng hai chƣơng trình. 5 BẢNG DIỄN GIẢI CÁC CHỮ VIẾT TẮT STT CHỮ VIẾT TẮT DIỄN GIẢI 1 BCNN Bội chung nhỏ nhất 2 UCNN Ƣớc chung nhỏ nhất 3 UCLN Ƣớc chung lớn nhất 4 RSA Ronald Rivest, Adi Shamir và Leonard Adleman. 5 DSS Digital Signature Standard 6 KB Ki lô byte 7 MB Mê ga byte 8 MD Message-Digest algorithm 9 MD4, MD5 Message-Digest algorithm 4, Message-Digest algorithm 5 10 SHA Secure Hash Algorithm 11 CT1, CT2, CT3 Cử tri 1, Cử tri 2, Cử tri 3 12 KP1, KP2, KP3 Kiểm phiếu 1, Kiểm phiếu 2, Kiểm phiếu 3 13 ĐH Điều hành 14 ĐK Đăng ký 15 KT Kiểm tra 16 KP Kiểm phiếu 17 CMT Chứng minh thƣ 18 TPD Trusted Public Directory 19 XMTT Xác minh trung thực 6 DANH MỤC HÌNH VẼ Hình 1.1. Sơ đồ khối một hệ truyền tin mật .........................................................19 Hình 2.1. Giao thức 2............................................................................................40 Hình 2.2. Giao thức 3............................................................................................41 Hình 3.1. Quy trình bỏ phiế u điê ̣n tƣ̉ ....................................................................50 Hình 3.2. Quy trình đăng ký bỏ phiếu ..................................................................51 Hình 3.3. Quy trình bỏ phiếu ................................................................................53 Hình 3.4. Quy trình kiểm phiếu ............................................................................55 Hình 3.5. Ví dụ minh họa chứng minh không tiết lộ thông tin ............................56 Hình 4.1. Hƣớng dẫn khởi động chƣơng trình ký mù RSA..................................64 Hình 4.2. Giao diện ký mù RSA trên một số ........................................................64 Hình 4.3. Tạo khóa ...............................................................................................65 Hình 4.4. Làm mù số cần ký .................................................................................66 Hình 4.5. Ký mù lên một số ..................................................................................67 Hình 4.6. Tách chữ ký xóa mù..............................................................................67 Hình 4.7. Giao diện của chức năng ký mù lên văn bản ........................................68 Hình 4.8. Giao diện chức năng tạo khóa ..............................................................68 Hình 4.9 Nội dung thông điệp cần làm mù ...........................................................69 Hình 4.10. Giao diện chức năng làm mù thông điệp ............................................70 Hình 4.11. Nội dung thông điệp mù .....................................................................70 Hình 4.12. Giao diện chức năng ký lên văn bản mù.............................................71 Hình 4.13. Thông điệp mù đã đƣợc ký .................................................................71 Hình 4.14. Giao diện chức năng tách chữ ký........................................................72 Hình 4.15. Thông điệp đã đƣợc tách chữ ký.........................................................72 Hình 4.16. Giao diện chức năng lấy lại bản rõ (xóa mù) ......................................73 Hình 4.17. Thông điệp đã đƣợc xóa mù ...............................................................73 7 DANH MỤC BẢNG BIỂU Bảng 1.1. Ví dụ sử dụng thuật toán Euclide mở rộngđể tìm phần tử nghịch đảo 17 Bảng 1.2. Thời gian chạy của các lớp thuật toán khác nhauError! Bookmark not defined. Bảng 3.1. Giao thức Cử tri chứng minh lá phiếu hợp lệ .......................................57 Bảng 3.2. Chứng minh lá phiếu đã làm mù hoặc mã hóa hợp lệ ..........................58 8 MỤC LỤC LỜI CAM ĐOAN ............................................................................................................ 1 LỜI MỞ ĐẦU ................................................................................................................. 4 MỤC LỤC ....................................................................................................................... 8 Chương 1. MỘT SỐ KHÁI NIỆM CƠ BẢN ................................................................ 11 1.1. CÁC KHÁI NIỆM CƠ SỞ ..................................................................................... 11 1.1.1. Một số khái niệm trong số học ........................................................................ 11 1.1.1.1. Số nguyên tố ........................................................................................11 1.1.1.2. Nguyên tố cùng nhau ...........................................................................11 1.1.1.3. Đồng dƣ Mô-đun (Modulo) .................................................................11 1.1.1.4. Ƣớc số - Bội số ....................................................................................11 1.1.2. Một số khái niệm trong đại số ......................................................................... 12 1.1.2.1.Cấu trúc nhóm ......................................................................................12 1.1.2.2. Nhóm hữu hạn .....................................................................................13 1.1.2.3. Nhóm chu kỳ (Cyclic ) ........................................................................13 1.1.2.4. Nhóm (𝒁𝒏 ∗ , phép nhân mod n) .........................................................14 1.2. HỆ MÃ HÓA .......................................................................................................... 18 1.2.1. Khái niệm mã hóa dữ liệu .............................................................................. 18 1.2.1.1. Hệ mã hóa ............................................................................................18 1.2.1.2. Mã hóa và giải mã ...............................................................................19 1.2.2. Phân loại hệ mã hóa........................................................................................ 19 1.2.2.1. Hệ mã hóa khóa đối xứng....................................................................20 1.2.2.2. Hệ mã hóa khóa công khai ..................................................................21 1.2.3. Một số hệ mã hóa cụ thể .................................................................................. 22 1.2.3.1. Hệ mã hóa RSA ...................................................................................22 1.2.3.2. Hệ mã hóa ElGamal ............................................................................22 1.2.3.3. Mã hóa đồng cấu .................................................................................24 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ố ........................................................................................ 26 1.3.2.1. Phân loại chữ ký theo đặc trƣng kiểm tra chữ ký ..............................26 1.3.2.2. Phân loại chữ ký theo mức an toàn .....................................................26 1.3.2.3. Phân loại chữ ký theo ứng dụng đặc trƣng ..........................................26 9 1.3.3. So sánh chữ ký thông thƣờng và chữ ký số.................................................... 27 1.3.4. Tạo đại diện tài liệu và hàm băm ................................................................... 28 1.3.4.1. Một số vấn đề với chữ ký số ...............................................................28 1.3.4.2. Cách giải quyết các vấn đề trên ...........................................................28 1.3.4.3. Tổng quan về hàm băm .......................................................................29 Chương 2. MỘT SỐ LOẠI CHỮ KÝ ĐẶC BIỆT ........................................................ 31 2.1. CHỮ KÝ MÙ RSA ................................................................................................ 31 2.1.1. Khái niệm chữ ký mù ..................................................................................... 31 2.1.2. Sơ đồ chữ ký RSA ........................................................................................... 31 2.1.3. Sơ đồ chữ ký mù RSA ..................................................................................... 32 2.2. CHỮ KÝ NHÓM ................................................................................................... 34 2.2.1. Khái niệm về chữ ký nhóm(Groups Signature) ............................................. 34 2.2.2. Những đặc điểm của chữ ký nhóm .................................................................. 34 2.2.2.1. Hiệu quả của chữ kýnhóm ...................................................................34 2.2.2.2. Việc đảm bảo an ninh đối với chữ ký nhóm. ......................................35 2.2.3. Các sơ đồ chữ ký nhóm ................................................................................... 35 2.2.3.1. Sơ đồ chữ ký nhóm thứ nhất ...............................................................35 2.2.3.2. Sơ đồ chữ ký nhóm thứ hai .................................................................38 2.2.3.3. Sơ đồ chữ ký nhóm thứ ba ..................................................................44 Chương 3. ỨNG DỤNG MỘT SỐ LOẠI CHỮ KÝ ĐẶC BIỆT TRONG HỆ THỐNG BỎ PHIẾU TỪ XA........................................................................................................ 47 3.1. VẤN ĐỀ BỎ PHIẾU TỪ XA ................................................................................ 47 3.1.1. Khái niệm bỏ phiếu từ xa ................................................................................ 47 3.1.2. Tổ chức bỏ phiếu từ xa .................................................................................... 47 3.1.2.1. Chuẩn bị hệ thống bỏ phiếu .................................................................47 3.1.2.2. Quy trình bỏ phiếu từ xa......................................................................48 3.2. BÀI TOÁN VỀ AN TOÀN THÔNG TIN TRONG BỎ PHIẾU TỪ XA .............. 49 3.2.1. Giai đoạn Đăng ký bỏ phiếu ............................................................................ 49 3.2.2. Giai đoạn bỏ phiếu .......................................................................................... 49 3.2.3. Giại đoạn kiểm phiếu ...................................................................................... 49 3.3. PHƢƠNG PHÁP GIẢI QUYẾT CÁC BÀI TOÁN VỀ THÔNG TIN TRONG BỎ PHIẾU TỪ XA .............................................................................................................. 50 3.3.1. Bài toán trong Giai đoạn đăng ký bỏ phiếu ..................................................... 50 3.3.2. Bài toán trong giai đoạn bỏ phiếu ................................................................... 52 3.3.3. Bài toán trong Giai đoạn Kiểm phiếu.............................................................. 54 10 3.3.4. Bài toán trong kiểm tra phiếu của ngƣời XMTT........................................... 55 3.3.5. Kỹ thuật trộn các lá phiếu (mixing the votes) ................................................. 58 Chương 4. THỬ NGHIỆM CHƢƠNG TRÌNH KÝ MÙ RSA ..................................... 63 4.1. BÀI TOÁN LẬP TRÌNH ....................................................................................... 63 4.2. CẤU HÌNH HỆ THỐNG ....................................................................................... 63 4.3. GIỚI THIỆU ........................................................................................................... 63 4.4. MÔ TẢ HOẠT ĐỘNG ........................................................................................... 65 4.4.1. Chức năng ký mù lên một số ........................................................................... 65 4.4.2. Chức năng ký mù lên một văn bản .................................................................. 68 KẾT LUẬN ................................................................................................................... 74 TÀI LIỆU THAM KHẢO ............................................................................................. 75 11 Chương 1. MỘT SỐ KHÁI NIỆM CƠ BẢN 1.1. CÁC KHÁI NIỆM CƠ SỞ 1.1.1. Một số khái niệm trong số học 1.1.1.1. Số nguyên tố 1/.Khái niệm: Số nguyên tố là số tự nhiên chỉ chia hết cho 1 và chính nó. Ngoài ra nókhông chia hết cho bất cứ số nào khác. Số 0 và1không đƣợc coi là số nguyên tố. 2/ Ví dụ: Các số nguyên tố từ 2 đến 100:2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 97 Số 2 là số nguyên tố nhỏ nhất, và 2 cũng là số nguyên tố chẵn duy nhất. 1.1.1.2. Nguyên tố cùng nhau 1/ Khái niệm: Trong toán học, các số nguyên a và b đƣợc gọi là nguyên tố cùng nhau nếu chúng có ƣớc số chung lớn nhất là 1. 2/ Ví dụ: Hai số 6 và 35 là nguyên tố cùng nhau vì chúng có ƣớc chung lớn nhất là 1 Hai số 6 và 27 không nguyên tố cùng nhau vì chúng có ƣớc số chung lớn nhất là 3 1.1.1.3. Đồng dưMô-đun (Modulo) 1/ Định nghĩa: Cho số nguyên dƣơng n và hai số nguyên a,b đƣợc gọi là đồng dƣ theo mô-đunn nếu chúng cho cùng số dƣ khi chia cho n (hay là a-b chia hết cho n). Kí hiệu là: a  b (mod n) 2/ Ví dụ: 11  5 (mod 3) Vì 11 và 5 chia cho 3 đều dƣ 2 1.1.1.4. Ước số - 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 + Ước số chung lớn nhất (UCLN): Là số lớn nhất mà a và b chia hết 12 Ký hiệu: c = gcd (a,b); (great common divisor) + Bội số chung nhỏ nhất (BCNN): d là BCNN của a và b nếu ∀c mà c|a, c|b → c|d Ký hiệu: d = lcm (a,b); (least common multiple) Tính chất: lcm (a,b) = a.b/gcd(a,b) Ví dụ:a = 6, b = 3, ta có 6 = 2*3, ký hiệu 3|6. Ở đây 3 là ƣớc của 6 và 6 là bội của 3. + Tập Z𝒏 và 𝒁𝒏∗ + Zn = {0, 1, 2, .. . , n-1} là tập các số nguyên không âm < n. + 𝒁∗𝒏 = {eZn , e là nguyên tố cùng nhau với n}. Tức là e ≠ 0. Ví du: 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 1.1.2. Một số khái niệm trong đại số 1.1.2.1.Cấu trúc nhóm 1/. Khái niệm nhóm - Nhóm là bộ đôi (G, ∗), trong đó G là tập ≠và ∗ là một phép toán hai ngôi trong G thỏa mãn ba tiên đề sau: + Phép toán nhóm kết hợp a * (b * c) = (a * b) * c ∀ a, b, c ∈G + Có một phần tử 0 ∈G đƣợc gọi là phần tử đơn vị thỏa mãn a*0=0*a ∀ a ∈G + Với mỗi a ∈G, tồn tại một phần tử a-1 ∈G đƣợc gọi là nghịch đảo a * a-1 = a-1 * a = 0 Nhóm đƣợc gọi là giao hoán (hay nhóm Abel) nếu:a * b = b * a ∀ a, b ∈G - Cấp của nhóm G đƣợc hiểu là số phần tử của nhóm, ký hiệu là |G|. Cấp của nhóm có thể là  nếu G có vô hạn phần tử. - Nhóm Abel là nhóm (G, *), trong đó phép toán hai ngôi * có tính giao hoán. Tính chất: Nếu a* b = a * c, thì b = c Nếu a * c = b * c, thì a = b 13 Ví dụ: - Tập hợp các số nguyên Z cùng với phép cộng (+) thông thƣờng là nhóm giao hoán, có phần tử đơn vị là số 0. Gọi là nhóm cộng các số nguyên. - Tập Q* cácsố hữu tỷ khác 0 (hay tập R* các số thực khác 0), cùng với phép nhân (*) thông thƣờng là nhóm giao hoán, gọi là nhóm nhân các số hữu tỷ (số thực) khác 0. - Tập các vectơ trong không gian với phép toán cộng vectơ là nhóm giao hoán. 2/. Nhóm con của nhóm (G, *) Nhóm con của G là tập S  G, S , và thỏa mãn các tính chất sau: - Phần tử trung lập e của G nằm trong S. - S khép kín đối với phép tính (*) trong G, tức là x*y  S (x, y S) - S khép kín đối với phép lấy nghịch đảo trong G, tức x−1 S (xS) 1.1.2.2. Nhóm hữu hạn Định nghĩa: Nhóm (G, ∗) hữu hạn nếu |G| là hữu hạn. Số các phần tử của nhóm G đƣợc gọi là cấp của nhóm. Ví dụ: Tập các số nguyên Z với phép cộng sẽ tạo nên một nhóm. Phần tử đơn vị của nhóm này đƣợc kí hiệu là 0, phần tử ngƣợc của một số nguyên a là số nguyên –a. 1.1.2.3. Nhóm chu kỳ (Cyclic ) 1/. Khái niệm nhóm Cyclic Nhóm (G, *) đƣợc gọi là nhóm Cyclic nếu nó đƣợc sinh ra bởi một trong các phần tử của nó. Tức là có phần tử g  G mà với mỗi a  G, đều tồn tại số n  N để gn= g * g * … * g = a. (Chú ý g * g * … * g là g * g với n lần). Khi đó g đƣợc gọi là phần tử sinh hay phần tử nguyên thuỷ của nhóm G. Nói cách khác: G đƣợc gọi là nhóm Cyclic nếu tồn tại g  G sao cho mọi phần tử trong G đều là một luỹ thừa nguyên nào đó của g. Ví dụ: Nhóm (𝑍𝑁∗ , *) gồm các số nguyên dƣơng là Cyclic với phần tử sinh g=1. 14 2/. Cấp của nhóm Cyclic Cho (G, *) là nhóm Cyclic với phần tử sinh g và phần tử trung lập e. - Nếu tồn tại số tự nhiên nhỏ nhất n mà gn = e, thì G sẽ chỉ gồm có n phần tử khác nhau: e, g1, g2, g3, . . . , gn - 1. Khi đó G đƣợc gọi là nhóm Cyclic hữu hạn cấp n. - Nếu không tồn tại số tự nhiên n để gn = e, thì G có cấp . Ví dụ: (Z +, +) gồm các số nguyên dƣơng là Cyclic với phần tử sinh g =1, e= 0. Đó là nhóm Cyclic vô hạn, vì không tồn tại số tự nhiên n để gn = e. 3/. Cấp của một phần tử trong nhóm Cyclic Phần tử α G đƣợc gọi là có cấp d nếu d là số nguyên dƣơng nhỏ nhất sao cho α = e, trong đó e là phần tử trung lập của G. d Nhƣ vậy phần tử α có cấp 1, nếu α = e. 1.1.2.4. Nhóm (𝒁𝒏∗ , phép nhân mod n) 1/. Khái niệm tập thặng dƣ thu gọn theo modulo - Kí hiệu Zn={0, 1, 2, .. . , n-1} là tập các số nguyên không âm< n. Zn và phép cộng (+) lập thành nhóm Cyclic có phần tử sinh là 1, phần tử trunglập e=0. (Zn, +) gọi là nhóm cộng, đó là nhóm hữu hạn có cấp n. - Kí hiệu 𝒁𝒏∗ = {x  Zn, x là nguyên tố cùng nhau với n} (tức là x phải  0). 𝒁𝒏∗ đƣợc gọi là Tập thặng dƣ thu gọn theo mod n, có số phần tử là (n). 𝒁𝒏∗ với phép nhân mod n lập thành một nhóm (hay còn gọi là nhóm nhân),phần tử trung lập e=1. - Tổng quát (𝒁∗𝒏 , phép nhân mod n) không phải là nhóm Cyclic. - Nhóm 𝒁𝒏∗ là Cyclic chỉ khi n có dạng:2, 4, pk, hay 2pk với p là nguyên tố lẻ. 2/. Một số kết quả đã đƣợc chứng minh - Định lý Lagrange:Nếu G là nhóm cấp n và α G, thì cấp của α là ƣớc của n. - Hệ quả: Giả sử α𝒁∗𝒏 có cấp m, thì m là ƣớc của (n). - Định lý:Nếu p là số nguyên tố thì𝒁∗𝒑 là nhóm Cyclic. Nếu b 𝒁𝒏∗ thì b(n) 1 (mod n). Nếu p là số nguyên tố thì(p) = p – 1. Do đó với b 𝒁𝒑∗ (b nguyên tố với p), thì b(p) 1 (mod n), hay bp -11 (mod n). Chú ý:Theo định nghĩa, phần tử α𝒁∗𝒏 có cấp d nếu d là số nguyên dƣơng nhỏ nhấtsao cho dα = e trong 𝒁∗𝒏 . Nhƣ vậy trong 𝒁𝒏∗ ta hiểu là αde (mod n). - Định lý: Nhóm con của một nhóm Cyclic là một nhóm Cyclic. 15 3/. Phần tử nghịch đảo đối với phép nhân - Định nghĩa: Cho a Zn, nếu tồn tại b  Zn sao cho a.b  1(mod n), ta nói blà phần tử nghịch đảo của a trong Zn và ký hiệu a-1. Một phần tử có phần tử nghịch đảo,gọi là khả nghịch. - Định lý: UCLN (a, n) = 1  Phần tử a  Zn có phần tử nghịch đảo. Chứng minh: Nếu a.a-1 ≡ 1 (mod n) thì a.a-1 = 1 + kn ↔ a.a-1– kn = 1→ (a, n) =1. Nếu (a, n) = 1, ta có a.a-1 + kn = 1 → a.a-1 = 1+kn, do đó a.a-1 ≡ 1 (mod n). - Hệ quả: Mọi phần tử trong 𝒁∗𝒏 đều có phần tử nghịch đảo. - Tìm phần tử nghịch đảo bằng Thuật toán Euclid mở rộng + Input: a Zn , n + Output: Phần tử nghịch đảo của a. Procedure Invert(a,n); begin g0:=n; g1:=a; u0:=1; u1:=0; v0:=0; v1:=1; i:=1; while gi 0 do begin y := gi-1 div gi; gi+1 := gi-1– y.gi; ui+1 := ui-1– y.ui; vi+1 := vi-1– y.vi; i:=i+1; end; t := vi-1; if t > 0 then a-1 := t elsea-1 := t + n; end; 16 Ví dụ: Tìm phần tử nghịch đảo của 3 trong Z7 Tức là phải giải phƣơng trình3.x ≡ 1(mod 7),x sẽ là phần tử nghịch đảo của 3).Xem chi tiết trong bảng 1.1. 17 Bảng 1.1. Ví dụ sử dụng thuật toán Euclide mở rộngđể tìm phần tử nghịch đảo I gi ui vi y 0 7 1 0 1 3 0 1 2 2 1 1 -2 3 3 0 Vì t = v2 = -2 < 0 do đó x = a-1 := t + n = -2 + 7 = 5. Vậy 5 là phần tử nghịch đảo của |3| trong Z7 Chú ý:- Định lý (Euler tổng quát): Nếu (a, n) = 1 thì α(n) mod n = 1 - Hệ quả: Nếu p là số nguyên tố và (a, p) = 1, thì ap−1 (mod p) = 1 4/. Khái niệm Lô-ga-rit rời rạc Cho p là số nguyên tố, g là phần tử nguyên thủy của𝒁𝒑∗ , 𝒁∗𝒑 “Logarit rời rạc” chính là việc giải phƣơng trình x = 𝑙𝑜𝑔𝑔 (mod p) với ẩn x. Hay phải tìm số x duy nhất sao cho: gx (mod p). 18 1.2. HỆ MÃ HÓA 1.2.1. Khái niệm mã hóa dữ liệu Để bảo đảm an toàn thông tin lƣu trữ trong máy tính (ví dụ: giữ gìn thông tin cố định) hay bảo đảm an toàn thông tin trên đƣờng truyền tin (ví dụ: trên mạng máy tính, điện thoại), ngƣời ta phải “che giấu” các thông tin này. - “Che” thông tin (dữ liệu) hay“mã hóa” thông tin là thay đổi hình dạng thông tin gốc, và ngƣời khác “khó” nhận ra. Nói cách khác “mã hóa” thông tin là “che” đi “ý nghĩa” của thông tin, và ngƣời khác “khó” hiểu đƣợc (“khó” đọc đƣợc) thông tin đã mã hoá. - “Giấu” thông tin (dữ liệu) là cất giấu thông tin trong bản tin khác, và ngƣời khác cũng “khó” nhận ra. Việc mã hoá phải theo quy tắc nhất định, quy tắc đó gọi là hệ mã hóa. 1.2.1.1. Hệ mã hóa Hệ mã hóa đƣợc định nghĩa là bộ năm (P, C, K, E, D), trong đó: P là tập hữu hạn các bản rõ có thể. C là tập hữu hạn các bản mã có thể. K là tập hữu hạn các khoá có thể. E là tập các hàm lập mã. D là tập các hàm giải mã. Với khóa lập mã ke  K, có hàm lập mã eke E, eke: P C, Với khóa giải mã kd K, có hàm giải mã dkd D, dkd: C P sao cho dkd (eke (T)) = T, T  P. Ở đây T đƣợc gọi là bản rõ, eke (T) đƣợc gọi là bản mã. 19 1.2.1.2. Mã hóa và giải mã Ngƣời gửi G muốn gửi bản tin T cho ngƣời nhận N. Để bảo đảm bí mật, G mã hoá bản tin bằng khóa lập mã ke, thu đƣợc bản mã eke(T), sau đó gửi cho N. Tin tặc có thể trộm bản mã eke(T), nhƣng cũng “khó” hiểu đƣợc bản tin gốc T nếu không có khoá giải mã kd. Ngƣời N nhận đƣợc bản mã, họ dùng khoá giải mã kd, để giải mã eke (T), sẽ nhận đƣợc bản tin gốc T = dkd (eke (T)). k e k d Hình 1.1.Sơ đồ khối một hệ truyền tin mật 1.2.2. Phân loại hệ mã hóa Hiện nay có hai loại hệ mã hóa chính: Hệ mã hóa khóa đối xứng và hệ mã hóa khóa bất đối xứng (hệ mã hóa khoá công khai). - Mã hóa khóa đối xứng: là hệ mã hóa có khóa lập mã và khóa giải mã “giống nhau”, theo nghĩa biết đƣợc khóa này thì “dễ” tính đƣợc khóa kia, vì vậy cần phải giữ bí mật cả 2 khóa. - Mã hóa khóa công khai: là hệ mã hóa có khóa lập mã khác khóa giải mã (kekd), biết đƣợc khóa này cũng “khó” tính đƣợc khóa kia. Vì thế khóa giải mã cần phải đƣợc giữ bí mật, khóa lập mã đƣợc công khai. 20 1.2.2.1. Hệ mã hóa khóa đối xứng Mã hóa khóa đối xứng là hệ mã hóa có khóa lập mã và khóa giải mã “giống nhau”, theo nghĩa biết đƣợc khóa này thì “dễ” tính đƣợc khóa kia. Đặc biệt một số hệ mã hóa loại này có khoá lập mã và khoá giải mã trùng nhau (ke = kd). Hệ mã hóa khóa đối xứng còn có tên gọi là Hệ mã hóa khoá bí mật, vì phải giữ bí mật cả hai khóa. Trƣớc khi dùng hệ mã hóa khóa đối xứng, ngƣời gửi và ngƣời nhận phải thoả thuận thuật toán mã hóa và một khoá chung (lập mã hay giải mã), khoá này phải đƣợc giữ bí mật. Độ an toàn của hệ mã hóa loại này phụ thuộc vào khoá [1][2]. Ví dụ: -Hệ mã hóa cổ điển:Dễ hiểu, dễ thực thi, nhƣng có độ an toàn không cao. Vì giới hạn tính toán chỉ trong phạm vi bảng chữ cái, sử dụng trong bản tin cần mã, ví dụ là Z26 nếu dùng các chữ cái tiếng Anh, là Z256 nếu dùng bảng mã ASCII... Với hệ mã hóa cổ điển, nếu biết khoá lập mã hay thuật toán lập mã, ngƣời ta có thể “dễ” xác định đƣợc bản rõ, vì “dễ” tìm đƣợc khoá giải mã. - Hệ mã hóa DES(1973):Là hệ mã hóa khóa đối xứng hiện đại, có độ an toàn cao. 1/. Các đặc điểm của hệ mã hóa khóa đối xứng - Ƣu điểm: Mã hóa khóa đối xứng mã hóa và giải mã nhanh hơn mã hóa khóa công khai. - Hạn chế: + Mã hóa khóa đối xứng chƣa thật an toàn vì: Ngƣời mã hoá và ngƣời giải mã phải có “chung” một khoá. Khóa phải đƣợc giữ bí mật tuyệt đối, vì “dễ” xác định khoá này nếu biết khoá kia. Khi hai ngƣời (lập mã, giải mã) cùng biết “chung” một bí mật, thì khó giữ đƣợc bí mật. + Vấn đề thỏa thuận khoá và quản lý khóa chung là khó khăn và phức tạp. Ngƣời gửi và ngƣời nhận phải luôn thống nhất với nhau về khoá.Việc thay đổi khoá là rất khó và dễ bị lộ. Khóa chung phải đƣợc gửi cho nhau trên kênh an toàn. + Không thể tạo ra chữ ký số. 2/. Phạm vi áp dụng hệ mã hóa đối xứng - Hệ mã hóa khóa đối xứng thƣờng đƣợc sử dụng trong môi trƣờng mà khoá chung có thể dễ dàng trao chuyển bí mật, chẳng hạn trong cùng một mạng nội bộ. - Hệ mã hóa khóa đối xứng dùng để mã hóa những bản tin lớn, vì tốc độ mã hóa và giải mã nhanh hơn hệ mã hóa khóa công khai.