Luận văn Thạc sĩ Khoa học máy tính: Nghiên cứu một số thuật toán hệ mật mã khoá công khai Elgamal và ứng dụng

Chia sẻ: _ _ | Ngày: | Loại File: PDF | Số trang:67

Thêm vào BST

Báo xấu

43
lượt xem 8
download

Download Vui lòng tải xuống để xem tài liệu đầy đủ

Mục tiêu nghiên cứu là thử nghiệm thuật toán mã hóa Elgamal và các cải tiến mới của các tác giả đã đưa ra, so sánh hiệu quả của chúng và kiểm định thuật toán này bằng một ứng dụng trong thực tiễn. Đây là bài toán lựa chọn các khả năng trong các giải pháp đã có bằng việc mã hóa và xác thực như bài toán bỏ phiếu điện tử do các cán bộ tiến hành hoặc bài toán thăm dò tín nhiệm lãnh đạo tại một đơn vị. Mời các bạn cùng tham khảo!

Chủ đề:

Bình luận(0) Đăng nhập để gửi bình luận!

Lưu

Nội dung Text: Luận văn Thạc sĩ Khoa học máy tính: Nghiên cứu một số thuật toán hệ mật mã khoá công khai Elgamal và ứng dụng

ĐẠI HỌC THÁI NGUYÊN TRƢỜNG ĐẠI HỌC CÔNG NGHỆ THÔNG TIN VÀ TRUYỀN THÔNG PHẠM THỊ TUYẾT NGHIÊN CỨU MỘT SỐ THUẬT TOÁN HỆ MẬT MÃ KHOÁ CÔNG KHAI ELGAMAL VÀ ỨNG DỤNG LUẬN VĂN THẠC SĨ KHOA HỌC MÁY TÍNH THÁI NGUYÊN - 2015 Số hóa bởi Trung tâm Học liệu – ĐHTN http://www.lrc.tnu.edu.vn
ĐẠI HỌC THÁI NGUYÊN TRƢỜNG ĐẠI HỌC CÔNG NGHỆ THÔNG TIN VÀ TRUYỀN THÔNG PHẠM THỊ TUYẾT NGHIÊN CỨU MỘT SỐ THUẬT TOÁN HỆ MẬT MÃ KHOÁ CÔNG KHAI ELGAMAL VÀ ỨNG DỤNG Chuyên ngành: Khoa học máy tính Mã số: 60 48 01 01 LUẬN VĂN THẠC SĨ KHOA HỌC MÁY TÍNH Ngƣời hƣớng dẫn khoa học: TS NGUYỄN NGỌC CƢƠNG THÁI NGUYÊN - 2015 Số hóa bởi Trung tâm Học liệu – ĐHTN http://www.lrc.tnu.edu.vn
i LỜI CAM ĐOAN Tôi xin cam đoan luận văn “ Nghiên cứu một số thuật toán hệ mật mã khoá công khai ElGamal và ứng dụng” là công trình nghiên cứu của cá nhân tôi tìm hiểu, nghiên cứu dƣới sự hƣớng dẫn của TS Nguyễn Ngọc Cƣơng. Các kết quả là hoàn toàn trung thực, toàn bộ nội dung nghiên cứu của luận văn, các vấn đề đƣợc trình bày đều là những tìm hiểu và nghiên cứu của chính cá nhân tôi hoặc là đƣợc trích dẫn từ các nguồn tài liệu đƣợc trích dẫn và chú thích đầy đủ. TÁC GIẢ LUẬN VĂN Phạm Thị Tuyết Số hóa bởi Trung tâm Học liệu – ĐHTN http://www.lrc.tnu.edu.vn
ii LỜI CẢM ƠN Học viên xin bày tỏ lời cảm ơn chân thành tới tập thể các thầy cô giáo Viện công nghệ thông tin, các thầy cô giáo Trƣờng Đại học Công nghệ thông tin và truyền thông - Đại học Thái Nguyên đã mang lại cho học viên kiến thức vô cùng quý giá và bổ ích trong suốt quá trình học tập chƣơng trình cao học tại trƣờng. Đặc biệt học viên xin bày tỏ lòng biết ơn sâu sắc tới thầy giáo TS Nguyễn Ngọc Cƣơng - Học viện an ninh đã định hƣớng khoa học và đƣa ra những góp ý, gợi ý, chỉnh sửa quý báu, quan tâm, tạo điều kiện thuận lợi trong quá trình nghiên cứu hoàn thành luận văn này. Cuối cùng, học viên 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 học viên trong suốt quá trình học tập. Do thời gian và kiến thức có hạn nên luận văn chắc không tránh khỏi những thiếu sót nhất định. Học viên rất mong nhận đƣợc những sự góp ý quý báu của thầy cô và các bạn. Thái Nguyên, ngày tháng năm 2015 HỌC VIÊN Phạm Thị Tuyết Số hóa bởi Trung tâm Học liệu – ĐHTN http://www.lrc.tnu.edu.vn
iii MỤC LỤC LỜI CAM ĐOAN ........................................................................................................ i LỜI CẢM ƠN ............................................................................................................ ii MỤC CÁC HÌNH VẼ, ĐỒ THỊ ................................................................................ vi MỞ ĐẦU .................................................................................................................... 1 CHƢƠNG 1 ............................................................................................................... 3 TỔNG QUAN VỀ CÁC HỆ MẬT MÃ ..................................................................... 3 1.1. Lý thuyết toán học ............................................................................................... 3 1.1.1. Số nguyên tố, UCLN, BCNN .......................................................................3 1.1.2. Nhóm, vành, trƣờng, trƣờng hữu hạn ...........................................................3 1.1.3 Số học Modulo (phép tính đồng dƣ) ..............................................................5 1.1.4. Không gian rời rạc của phép lấy Logarit ......................................................6 1.1.5. Định lí Fermat và định lí Euler......................................................................6 1.1.6. Hàm một phía và hàm một phía có cửa sập ..................................................6 1.1.7. Định lí Trung Quốc về phần dƣ: ...................................................................7 1.2. Mật mã ................................................................................................................ 7 1.2.1. Khái niệm ......................................................................................................7 1.2.2. Những yêu cầu đối với hệ mật mã ................................................................8 1.2.3. Hệ mã hóa RSA ............................................................................................8 1.2.4. Hệ mã hóa Paillier .........................................................................................9 1.2.5. Hệ mã hóa ElGamal ....................................................................................10 1.2.6 Hệ mật đƣờng cong Eliptic ...........................................................................10 1.3. Chữ ký điện tử ................................................................................................... 11 1.3.1. Sơ đồ chữ ký điện tử ...................................................................................11 1.3.2. Chữ ký mù RSA ..........................................................................................12 1.3.3. Chữ ký nhóm (Group Signature) ................................................................13 1.4. Khái niệm xác thực điện tử ............................................................................... 15 Số hóa bởi Trung tâm Học liệu – ĐHTN http://www.lrc.tnu.edu.vn
iv 1.5. Hàm băm (Hash Function) ................................................................................ 16 CHƢƠNG :HỆ MẬT MÃ ELGAMAL CẢI TIẾN VÀ MÃ HÓA ĐỒNG CẤU ... 17 2.1. Hệ mã hóa ElGamal cải tiến.............................................................................. 17 2.1.1. Thuật toán mật mã ElGamal cổ điển ..........................................................17 2.1.2. Một số thuật toán ElGamal cải tiến [3] .......................................................18 2.1.2.1 Thuật toán thứ nhất .............................................................................18 2.1.2.2 Thuật toán thứ hai ...............................................................................21 2.1.2.3 Thuật toán thứ ba .................................................................................23 2.2. Hệ mã hóa đồng cấu .......................................................................................... 26 2.2.1. Khái niệm mã hóa đồng cấu........................................................................26 2.2.2. Hệ mã hoá Elgamal có tính chất đồng cấu..................................................26 2.2.3. Mô hình hệ mã hóa đồng cấu ElGamal cho mô hình bỏ phiếu có/không ....27 2.3. Sơ đồ chia sẻ bí mật .......................................................................................... 29 2.3.1. Khái niệm chia sẻ bí mật .............................................................................29 2.3.2. Giao thức “Chia sẻ bí mật” Shamir.............................................................31 2.3.2.1. Khái niệm sơ đồ ngƣỡng A(t, m) ........................................................31 2.3.2.2. Chia sẻ khoá bí mật K .........................................................................32 2.3.2.3. Khôi phục khóa bí mật K từ t thành viên...........................................33 CHƢƠNG 3: ỨNG DỤNG HỆ MẬT MÃ ELGAMAL TRONG BÀI TOÁN BỎ PHIẾU THĂM DÒ TÍN NHIỆM ............................................................................. 37 3.1. Hệ thống bỏ phiếu điện tử [5] ........................................................................... 37 3.1.1. Khái niệm bỏ phiếu điện tử .........................................................................37 3.1.2. Yêu cầu của hệ thống bỏ phiếu điện tử .......................................................38 3.1.3. Những vấn đề cần giải quyết ......................................................................38 3.1.4.Các thành phần trong hệ thống bỏ phiếu điện tử .........................................39 3.1.5. Quy trình bài toán bỏ phiếu điện tử ............................................................39 3.2. Ứng dụng hệ mật ElGamal trong quá trình bỏ phiếu thăm dò tín nhiệm.......... 41 3.2.1. Thiết lập ......................................................................................................41 3.2.3. Mở phiếu bầu ..............................................................................................43 3.3. Xây dựng chƣơng trình thử nghiệm mô hình bỏ phiếu thăm dò tín nhiệm ...... 44 Số hóa bởi Trung tâm Học liệu – ĐHTN http://www.lrc.tnu.edu.vn
v 3.3.1. Môi trƣờng cài đặt và thử nghiệm ..............................................................44 3.3.2. Phát biểu bài toán ........................................................................................44 3.3.3 Các đối tƣợng của hệ thống ........................................................................45 3.3.4. Phân tích và thiết kế chƣơng trình bỏ phiếu: ..............................................45 3.3.5 Các chức năng chính ....................................................................................45 3.3.6. Thứ tự thực hiện chƣơng trình ....................................................................46 3.3.7. Kết quả thực nghiệm ...................................................................................47 3.4. Phân tích vấn đề bảo mật cần đạt đƣợc ............................................................. 56 3.5. Các tính chất đạt đƣợc ....................................................................................... 56 KẾT LUẬN VÀ HƢỚNG PHÁT TRIỂN ĐỀ TÀI ................................................. 57 TÀI LIỆU THAM KHẢO ........................................................................................ 58 Số hóa bởi Trung tâm Học liệu – ĐHTN http://www.lrc.tnu.edu.vn
vi MỤC CÁC HÌNH VẼ, ĐỒ THỊ Hình 1.1. Sơ đồ mã hóa và giải mã ............................................................................ 7 Hình 2.1. Sơ đồ bỏ phiếu đồng ý/ không đồng ý ....................................................... 28 Hình 2.2. Sơ đồ ngƣỡng Shamir.............................................................................. 32 Hình 3.1. Sơ đồ Quy trình bỏ phiếu điện tử ............................................................. 40 Hình 3.2. Sơ đồ mô tả bỏ phiếu thăm dò tín nhiệm ................................................. 41 Hình 3.3. Sơ đồ giai đoạn bỏ phiếu tín nhiệm ......................................................... 42 Hình 3.4. Giao diện chính của chƣơng trình ............................................................ 47 Hình 3.5. Ban tổ chức đăng nhập vào hệ thống ...................................................... 48 Hình 3.6. Thông báo tạo cơ sở dữ liệu cán bộ thành công....................................... 48 Hình 3.7. Bảng danh sách cán bộ sau khi đƣợc ban tổ chức tạo cơ sở dữ liệu ....... 49 Hình 3.8. Thông báo tạo cơ sở dữ liệu ban kiểm phiếu thành công. ....................... 49 Hình 3.9. Cán bộ đăng nhập vào hệ thống ............................................................... 49 Hình 3.10. Quá trình bỏ phiếu .................................................................................. 50 Hình 3.11. Cán bộ cập nhật thông tin ...................................................................... 50 Hình 3.12. Thông báo nhắc nhở lựa chọn của cán bộ .............................................. 51 Hình 3.13. Thông báo xác nhận lựa chọn của cán bộ .............................................. 51 Hình 3.14. Ban kiểm phiếu đăng nhập vào hệ thống ............................................... 52 Hình 3.14. Mảnh khóa của ban kiểm phiếu ............................................................. 52 Hình 3.15. Ban kiểm phiếu cập nhật thông tin......................................................... 53 Hình 3.16. Thông báo xác nhận quá trình gửi mảnh khóa ....................................... 53 Hình 3.17. Xác nhận tổng hợp đủ các mảnh khóa ................................................... 54 Hình 3.18. Thông báo ghép mảnh khóa thành công ................................................ 54 Hình 3.19. Kết quả bỏ phiếu .................................................................................... 55 Hình 3.20. Cơ sở dữ liệu trong mô hình bỏ phiếu tín nhiệm ................................... 56 Số hóa bởi Trung tâm Học liệu – ĐHTN http://www.lrc.tnu.edu.vn
1 MỞ ĐẦU 1. Tính khoa học và cấp thiết của đề tài Cùng với sự phát triển của công nghệ thông tin, hiện nay vấn đề an toàn thông tin trở nên hết sức cần thiết trên qui mô toàn cầu. Đảm bảo tính bảo mật, khả năng xác thực nguồn gốc gói tin trong quá trình truyền tải thông tin qua môi trƣờng không an toàn nhƣ Internet là một vấn đề nóng trong nghiên cứu và thực tiễn. Để đảm bảo tính bảo mật và xác thực ngƣời ta cần phải mã hoá, có một số thuật toán mã hoá công khai rất nổi tiếng: RSA, ElGamal, ... Tuy nhiên, các hệ mật mã này có nhƣợc điểm là không có cơ chế xác thực thông tin đƣợc bảo mật (nguồn gốc, tính toàn vẹn) do đó chúng không có khả năng chống lại một số dạng tấn công giả mạo trong thực tế. Chính vì vậy hiện nay, ngƣời ta [3] đã đề xuất một số cải tiến hệ mật mã ElGamal. Ƣu điểm của các thuật toán mới đề xuất này là ở chỗ cho phép bảo mật và xác thực thông tin một cách đồng thời mà mức độ an toàn của các thuật toán mới đề xuất không nhỏ hơn mức độ an toàn của thuật toán ElGamal xét theo khả năng chống thám mã khi tấn công trực tiếp vào các thủ tục mã hóa và giải mã. Để góp phần nâng cao hiệu năng của phƣơng pháp mã hóa ElGamal. Trong luận văn này, học viên đặt mục tiêu nghiên cứu, thử nghiệm thuật toán mã hóa Elgamal và các cải tiến mới của các tác giả đã đƣa ra, so sánh hiệu quả của chúng và kiểm định thuật toán này bằng một ứng dụng trong thực tiễn. Đây là bài toán lựa chọn các khả năng trong các giải pháp đã có bằng việc mã hóa và xác thực nhƣ bài toán bỏ phiếu điện tử do các cán bộ tiến hành hoặc bài toán thăm dò tín nhiệm lãnh đạo tại một đơn vị. Những bài toán này luôn đòi hỏi tính bí mật, ví dụ trong bỏ phiếu điện tử (e-voting), việc đảm bảo tính đúng đắn bảo mật ở đây có thể bao gồm cả việc không để lộ danh tính cử tri (ai bỏ phiếu cho ứng viên nào?), tính duy nhất (mỗi cử tri đảm bảo chỉ tối đa 1 lần bỏ phiếu)... 2. Đối tƣợng và phạm vi nghiên cứu - Đối tƣợng nghiên cứu: Hệ mật khóa công khai ElGamal và các cải tiến của hệ mật mã. Số hóa bởi Trung tâm Học liệu – ĐHTN http://www.lrc.tnu.edu.vn
2 - Phạm vi nghiên cứu: Nghiên cứu cải tiến dựa trên thuật toán đã có và xây dựng chƣơng trình ứng dụng trong bài toán thăm dò dƣ luận về mức độ tín nhiệm đối với một đơn vị (ở đây là tổng công ty xăng dầu Việt Nam). 3. Hƣớng nghiên cứu của đề tài - Nghiên cứu các đề xuất một số thuật toán mật mã khóa công khai đƣợc phát triển từ hệ mật ElGamal của các tác giả đã công bố để xây dựng chƣơng trình ứng dụng trong bài toán bỏ phiếu thăm dò dƣ luận về mức độ tín nhiệm. - Đánh giá ƣu điểm của các thuật toán mới do các tác giả đã đề xuất về mức độ bảo mật và xác thực thông tin một cách đồng thời. 4. Những nội dung nghiên cứu chính Luận văn đƣợc trình bày trong 3 chƣơng, có phần mở đầu, phần kết luận, phần mục lục, phần tài liệu tham khảo. Các nội dung cơ bản của luận văn đƣợc trình bày theo cấu trúc sau: Chương 1: TỔNG QUAN VỀ CÁC HỆ MẬT MÃ Trong chƣơng này tổng trình bày một số khái niệm cơ bản trong toán học mà các hệ mã hoá thƣờng sử dụng nhƣ: mod, số nguyên tố, vành Zn, các phép toán cộng, nhân, bài toán logarrit rời rạc trên không gian Zn.... Sau đó đƣa ra các khái niệm mật mã, các thuật toán mã hoá, chữ ký số phục vụ cho việc mã hoá thông tin. Chương 2: HỆ MẬT MÃ ELGAMAL CẢI TIẾN VÀ MÃ HÓA ĐỒNG CẤU Tập trung nghiên cứu một số thuật toán mật mã ElGamal cải tiến, tính chất đồng cấu của hệ mật ElGamal và sơ đồ chia sẻ bí mật theo ngƣỡng Shamir. Chương 3: ỨNG DỤNG HỆ MẬT MÃ ELGAMAL TRONG BÀI TOÁN BỎ PHIẾU THĂM DÒ TÍN NHIỆM Cài đặt thử nghiệm thuật toán hệ mật ElGamal cải tiến và kỹ thuật chia sẻ khóa bí mật Shamir. Số hóa bởi Trung tâm Học liệu – ĐHTN http://www.lrc.tnu.edu.vn
3 CHƢƠNG 1 TỔNG QUAN VỀ CÁC HỆ MẬT MÃ 1.1. Lý thuyết toán học 1.1.1. Số nguyên tố, UCLN, BCNN a), Số nguyên tố: là số nguyên dƣơng lớn hơn 1và chỉ có duy nhất 2 ƣớc là 1và chính nó. b), Ƣớc chung lớn nhất (ƢCLN): Cho hai số nguyên a và b, b  0. Nếu có một số nguyên q sao cho a = b*q, thì ta nói rằng a chia hết cho b(b\a). Khi đó b là ƣớc của a và a là bội của b. Số nguyên d đƣợc gọi là ƣớc chung của các số nguyên a1, a2, .., an nếu nó là ƣớc của tất cả các số đó. d đƣợc gọi là ƣớc chung lớn nhất của a1, a2, .., an nếu d > 0 và là số lớn nhất trong tập hợp các ƣớc chung của các số đó. Ký hiệu d = gcd ( a1, a2, .., an ) hay d = UCLN (a1, a2, .., an ). a) Bội chung nhỏ nhất (BCNN): Số nguyên m đƣợc gọi là bội chung của các số nguyên a1, a2, .., an nếu nó là bội của tất cả các số đó. m đƣợc gọi là bội chung nhỏ nhất của a1, a2, .., an nếu m > 0 và là số nhỏ nhất trong tập hợp các bội chung của các số đó. Kí hiệu m = lcm(a1, a2, .., an ) hay m = BCNN(a1, a2, .., an ). Hai số nguyên tố p và q đƣợc gọi là nguyên tố cùng nhau nếu ƣớc chung lớn nhất của chúng bằng 1. Kí hiệu: UCLN (m, n) = 1 1.1.2. Nhóm, vành, trƣờng, trƣờng hữu hạn a) Phép toán hai ngôi Cho G là một tập hơp. Phép toán hai ngôi (*) là một ánh xạ: (*): G  G  G ( x, y)  z  x * y  G,  x, y  G Ví dụ: G = Z. Phép toán (*) là phép (+) b) Nhóm Nhóm là bộ các phần tử (G, *) thỏa mãn các tính chất sau: Số hóa bởi Trung tâm Học liệu – ĐHTN http://www.lrc.tnu.edu.vn
4 - Tính chất kết hợp: ( x * y ) * z = x * ( y * z ), x, y, z  G - Tồn tại phần tử trung lập e  G: e * x = x * e = x, x  G - Tồn tại phần tử nghịch đảo x’  G: x’ * x = x * x’ = e 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 = a. Khi đó g là phần tử sinh hay phần tử nguyên thủy của nhóm G. Ví dụ: (Z+,*) gồm các số nguyên dƣơng là nhóm Cyclic có phần tử sinh là 1. Cấp của nhóm Cyclic: Cho (G,*) là nhóm Cyclic với phần tử sinh là 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, g, g1, g2,…, 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ô hạn. c, Vành Vành là một tập R với 2 toán tử + (cộng) và * (nhân) thỏa mãn các điều kiện sau: là nhóm Abel là nửa nhóm Phép nhân phân phối đối với phép cộng: với các phần tử tùy ý x, y, z  X ta có: x(y + z) = xy + z và (y + z) x = yx + zx Nếu phép nhân là giao hoán thì R đƣợc gọi là vành giao hoán d, Trƣờng Giả sử F là tập hợp khác rỗng, trên đó có hai phép toán đóng hai ngôi bất kỳ, chẳng hạn ký hiệu là + (cộng) và * (nhân). F là một trƣờng nếu và chỉ nếu: (F,+) là nhóm giao hoán với phần tử đơn vị là "0" (F\{0},*) là nhóm giao hoán với phần tử đơn vị là "1" Các phép toán cộng và nhân có tính chất phân phối: a(b+c) = ab + ac Số phần tử của một trƣờng đƣợc gọi là bậc của một trƣờng. Một trƣờng có số phần tử hữu hạn đƣợc gọi là trƣờng hữu hạn, một trƣờng có số phần tử vô hạn đƣợc gọi là trƣờng vô hạn. Số hóa bởi Trung tâm Học liệu – ĐHTN http://www.lrc.tnu.edu.vn
5 Trƣờng hữu hạn là trƣờng chứa hữu hạn các phần tử. Mọi trƣờng hữu hạn có một số nguyên tố là đặc số của trƣờng. Một trƣờng F có đặc số thì với mọi a  F, p pa  a  ...  a  0 e. Trƣờng hữu hạn Fp: Cho p là số nguyên tố. Trƣờng hữu hạn Fp bao gồm tập các số nguyên {0, 1, 2, .., p-1} cùng với các phép toán: Phép cộng: Nếu a, b  Fp , ta có a + b = r, với r là phần dƣ khi chia a + b cho p và 0  r  p  1 . Đây gọi là phép cộng modulo p. Phép nhân: Nếu a, b  Fp , ta có a.b = s, với s là phần dƣ khi chia a.b cho p và 0  s  p  1 . Đây gọi là phép nhân modulo p. Phép nghịch đảo: Nếu a  Fp (a  0), phép nghịch đảo của a modulo p, ký hiệu là a-1, nếu tồn tại duy nhất số nguyên c  Fp sao cho a.c = 1. Trƣờng hữu hạn F2m: Trƣờng F2m, kí hiệu F2m = {0,1, a1, a2, ..., a2m-2}, đƣợc gọi là trƣờng hữu hạn nhị phân. Khi đó tồn tại m phần từ  0,  1, ...,  m-1 trong F2m sao cho mỗi phẩn tử   F2m có thể viết duy nhất dƣới dạng: A = a0  0 + a1  1 + ... + am-1  m-1 với ai  0,1 Một bộ {  0,  1, ...,  m-1 } đƣợc gọi là cơ sở của F2m trên F2. Với mỗi cơ sở nhƣ vậy thì một phần tử  của trƣờng có thể biểu diễn dƣới dạng xâu bit ( a0a1 am-1). 1.1.3 Số học Modulo (phép tính đồng dƣ) Cho mỗi số nguyên dƣơng n và một số nguyên a bất kì nếu chúng ta chia a cho n đƣợc thƣơng là q và phần dƣ là r: a = q*n + r với 0 = < r < n và q = [a/n] Kí hiệu [x] là số nguyên lớn nhất nhỏ hơn hoặc bằng x. Nhƣ vậy, nếu a  Z và n  Z+ thì chúng ta định nghĩa a mod n phần dƣ của phép chia a cho n. Với ví dụ trên ta có: r = a mod n. Hai số nguyên a và b đƣợc gọi là đồng dƣ với nhau theo modul n nếu và chỉ nếu: a mod n = b mod n và kí hiệu là a  b mod (n) Số hóa bởi Trung tâm Học liệu – ĐHTN http://www.lrc.tnu.edu.vn
6 Chú ý: nếu a  0 mod (n) thì n|a Từ việc tính đồng dƣ theo mod n ta tách đƣợc số nguyên thành n lớp mỗi lớp chứa các số nguyên đồng dƣ với nhau theo (mod n) và tập các lớp này đƣợc kí hiệu là: Z/nZ và chứa đúng n phần tử thuộc đoạn [0, n-1]. 1.1.4. Không gian rời rạc của phép lấy Logarit Ta kí hiệu Fp là tập các lớp đồng dƣ theo Modul p hay Fp = Z/pZ = (0, 1, 2,…, p-1) Zp/Z* là những tập gồm các số nguyên tố cùng nhau với p hay tập các phần tử có nghịch đảo trong Z/pZ. Ta kí hiệu Fp* = Z/pZ* Với p là số nguyên tố thì Z/pZ = Z/pZ * = Fp = Fp* = (0, 1, 2, …, p-1). 1.1.5. Định lí Fermat và định lí Euler * Định lí Fermat: Nếu p là một số nguyên tố và a là một số nguyên thì ap  a (mod p). Nếu a không chia hết cho p tức là (a(mod p) ≠ 0) thì ap-1  1 (mod p). * Định lí Euler: Nếu gcd(a,m) = 1 thì aФ(m) = 1 mod m. Trong trƣờng hợp m là số nguyên tố thì Ф(m) = m-1 và ta có định lí Fermat. 1.1.6. Hàm một phía và hàm một phía có cửa sập a, Hàm một phía: Một hàm một phía là hàm mà dễ dàng tính toán ra quan hệ một chiều nhƣng rất khó để tính ngƣợc lại. Ví dụ: Biết giả thiết x thì có thể dễ dàng tính ra f(x), nhƣng nếu biết f(x) thì khó tính ra đƣợc x. Trong trƣờng hợp này “khó” có nghĩa là để tính ra đƣợc kết quả thì phải mất nhiều thời gian để tính toán. b, Hàm một phía có cửa sập: F(x) đƣợc gọi là hàm một phía có cửa sập nếu tính xuôi y = f(x) thì dễ tính ngƣợc x = f-1(y ) thì khó tuy nhiên nếu có “ cửa sập” thì vấn đề tính ngƣợc trở nên dễ dàng. Cửa sập ở đây là một điều kiện nào đó giúp chúng ta dễ dàng tính ngƣợc. Ví dụ: Hộp thƣ là một ví dụ khác về hàm một phía có cửa sập. Bất kỳ ai cũng có thể bỏ thƣ vào thùng. Bỏ thƣ vào thùng là một hành động công cộng. Mở thùng thƣ không phải hành động công cộng. Nó là khó khăn, bạn sẽ cần đến mỏ hàn để Số hóa bởi Trung tâm Học liệu – ĐHTN http://www.lrc.tnu.edu.vn
7 phá hoặc những công cụ khác. Tuy nhiên, nếu bạn có “ cửa sập” ( trong trƣờng hợp này là chìa khóa của hòm thƣ) thì công việc mở hòm thƣ thật dễ dàng. 1.1.7. Định lí Trung Quốc về phần dƣ: Giả sử m1, m2,…,mr là các số nguyên dƣơng nguyên tố cùng nhau từng đôi một và cho a1, a2,…,ar là các số nguyên. Khi đó, hệ r đồng dƣ thức: x= ai mod mi (1 ≤ i ≤ r) sẽ có một nghiệm duy nhất theo modul M= m1, m2,…, mr đƣợc tính theo công thức sau: r x   ai M i yi (mod M ) i 1 Trong đó Mi = M / mi và yi = Mi-1 mod mi với 1 ≤ i ≤ r 1.2. Mật mã 1.2.1. Khái niệm - Bản rõ (plaintext or cleartext): Chứa các xâu ký tự gốc, thông tin trong bản rõ là thông tin cần mã hoá để giữ bí mật. - Bản mã (ciphertext): Chứa các ký tự sau khi đã đƣợc mã hoá, mà nội dung đƣợc giữ bí mật. - Mật mã học (Crytography): Là khoa học để giữ thông tin đƣợc an toàn. - Sự mã hoá (Encryption): Quá trình che dấu thông tin bằng phƣơng pháp nào đó để làm ẩn nội dung bên trong gọi là sự mã hoá. - Sự giải mã (Decryption): Quá trình biến đổi trả lại bản mã thành bản rõ. Quá trình mã hoá và giải mã đƣợc thể hiện trong sơ đồ sau: Bản rõ Bản mã Bản rõ gốc mãmax Mã hóa max Giải mã Hình 1.1. Sơ đồ mã hóa và giải mã - Hệ mật mã: Là một hệ bao gồm 5 thành phần (P, C, K, E, D) thoả mãn các tính chất sau: P (Plaintext): Là tập hợp hữu hạn các bản rõ có thể. Số hóa bởi Trung tâm Học liệu – ĐHTN http://www.lrc.tnu.edu.vn
8 C (Ciphertext): Là tập hợp hữu hạn các bản mã có thể. K (Key): Là tập hợp các bản khoá có thể. E (Encrytion): Là tập hợp các qui tắc mã hoá có thể. D (Decrytion): Là tập hợp các qui tắc giải mã có thể. Với mỗi k có một hàm lập mã ek, ek:P, và một hàm giải mã dk, dk:C sao cho: dk (ek(x)) =x, với  x € P. . - Một thông báo thƣờng đƣợc tổ chức dƣới dạng bản rõ. Ngƣời gửi sẽ làm nhiệm vụ mã hoá bản rõ, kết quả thu đƣợc gọi là bản mã. Bản mã này đƣợc gửi đi trên một đƣờng truyền tới ngƣời nhận sau khi nhận đƣợc bản mã ngƣời nhận giải mã nó để tìm hiểu nội dung. Ek(P) = C và Dk (C) = P 1.2.2. Những yêu cầu đối với hệ mật mã Cung cấp một mức cao về tính bảo mật, tính toàn vẹn, tính chống chối bỏ và tính xác thực:  Tính bảo mật: Bảo đảm bí mật cho các thông báo và dữ liệu bằng việc che dấu thông tin nhờ các kỹ thuật mã hóa.  Tính toàn vẹn (integrity): Bảo đảm với các bên rằng bản tin không bị thay đổi trên đƣờng truyền tin.  Tính không thể chối bỏ (Non-repudiation): Có thể xác nhận rằng tài liệu đã đến từ ai đó, ngay cả khi họ cố gắng từ chối nó.  Tính xác thực (Authentication): Cung cấp hai dịch vụ: o Nhận dạng nguồn gốc của một thông báo và cung cấp một vài bảo đảm rằng nó là đúng sự thực. o Kiểm tra định danh của ngƣời đang đăng nhập một hệ thống, tiếp tục kiểm tra đặc điểm của họ trong trƣờng hợp ai đó cố gắng kết nối và giả danh là ngƣời sử dụng hợp pháp. 1.2.3. Hệ mã hóa RSA Sinh khóa: Giả sử A và B cần trao đổi thông tin bí mật thông qua một kênh không an toàn (ví dụ nhƣ Internet). Với thuật toán RSA, A đầu tiên cần tạo ra cho mình Số hóa bởi Trung tâm Học liệu – ĐHTN http://www.lrc.tnu.edu.vn
9 cặp khóa gồm khóa công khai và khóa bí mật theo các bƣớc sau: - Chọn 2 số nguyên tố lớn p và q với p  q - Tính: n = p.q - Tính giá trị hàm số Ơle  (n)  (p - 1).(q - 1) - Chọn một số tự nhiên e sao cho 1 < e <  (n) và là số nguyên tố cùng nhau với  (n) . - Tính d sao cho e.d  1 (mod( (n)) . Khóa công khai (n,e) Khóa bí mật (n, d) Mã hóa: Giả sử B muốn gửi đoạn thông tin M cho A. Đầu tiên B chuyển M thành một số m < n theo một hàm có thể đảo ngƣợc (từ m có thể xác định lại M) đƣợc thỏa thuận trƣớc. Lúc này B có m và biết n cũng nhƣ e do A gửi. B sẽ tính c là bản mã hóa của m theo công thức: c = me mod n Giải mã: A nhận c từ B và biết khóa bí mật d. A có thể tìm đƣợc m từ c theo công thức sau: m = cd mod n 1.2.4. Hệ mã hóa Paillier Hệ mã hóa Paillier đƣợc đặt theo tên và phát minh của Pascal Paillier năm 1999. Đây là thuật toán bất đối xứng cho hệ mật mã khóa công khai. Sinh khóa: - Chọn hai số nguyên tố lớn p và q - Tính n = p * q sao cho gcd(n, (p-1)(q-1)) = 1 - Chọn ngẫu nhiên g  Z*n thỏa mãn gcd( L( g  mod n 2 ), n)  1 với 2 u 1 L(u ) = và  = lcm(p-1, q-1) n Khóa công khai là (n, g); Khóa bí mật là: (p, q,  ) Số hóa bởi Trung tâm Học liệu – ĐHTN http://www.lrc.tnu.edu.vn
10 Mã hóa: Mã hóa thông điệp m 3 là số nguyên tố. Đƣờng cong Eliptic y2 = x3 + ax + b trên Zp là tập các nghiệm (x,y)  Zp x Zp của đồng dƣ thức y2 = x3 + ax + b(mod p) Trong đó a, b Zp là các hằng số thỏa mãn 4a3 + 27b2  0(mod p) (để đa thức x3 + ax + b không có nghiệm bội) cùng với điểm đặc biệt 0 đƣợc gọi là điểm vô hạn. - Định lý Hasse: Việc xây dựng các hệ mật mã trên dƣờng cong Eliptic bao gồm việc lựa chọn đƣờng cong E thích hợp và một điểm G trên E gọi là điểm cơ sở. Xét trƣờng K là Fq. N là số điểm của E trên Fq (trƣờng hữu hạn q phần tử). Khi đó: Số hóa bởi Trung tâm Học liệu – ĐHTN http://www.lrc.tnu.edu.vn
11 N  (q  1)  2 q . Từ định lý Hasse suy ra E(Fq) = q +1 – t trong dó t  2 q . - Hệ mật trên đƣờng cong Eliptic Hệ ElGamal làm việc với nhóm Cyclic hữu hạn. Năm 1978, Kobliz đã đƣa một hệ trên ECC dựa trên hệ ElGamal. Để xây dựng hệ mã hóa dựa trên đƣờng cong Eliptic ta chọn đƣờng cong E(a,b) và một điểm G trên đƣờng cong làm điểm cơ sở. Mỗi ngƣời dùng A một khóa bí mật nA là một số nguyên và sinh khóa công khai PA = nA *G. Khi đó hệ mã hóa đƣờng cong Eliptic đƣợc xây dựng tƣơng tự hệ mã hóa ElGamal, trong đó thuật toán mã hóa và giải mã đƣợc xác định nhƣ sau: Thuật toán mã hóa: Giả sử ngƣời dùng A muốn gửi thông điệp cần mã hóa Pm tới ngƣời dùng B, chọn một số ngẫu nhiên k và gửi thông điệp mã hóa Cm đƣợc tính nhƣ sau: Cm  k * G, Pm + k * PB  (PB là khóa công khai của B). Thuật toán giả mã: Để giải thông điệp Cm  k * G, Pm + k * PB  , ngƣời dùng B thực hiện tính nhƣ sau: Pm + k * PB - n B * k * G = Pm + k * PB - k * n B * G = Pm + k * PB - k * PB  Pm Chỉ B mới có thể giải mã vì B có nB (là khóa bí mật). 1.3. Chữ ký điện tử 1.3.1. Sơ đồ chữ ký điện tử Một sơ đồ chữ ký điện tử S là một bộ năm: S = (P, A, K, S, V) thỏa mãn các điều kiện dƣới đây: P: tập hữu hạn các thông báo có thể có. A: tập hữu hạn các chữ ký số có thể có. K: tập hữu hạn các khóa có thể. S: tập các thuật toán ký. V: tập các thuật toán kiểm thử. Mỗi khóa K’  K có hai thành phần K’ = (K1, K2), K1 là khóa bí mật dùng để ký, còn K2 là khóa công khai để xác thực chữ ký. Với mỗi K’ = (K1, K2), trong S có thuật toán kí: Số hóa bởi Trung tâm Học liệu – ĐHTN http://www.lrc.tnu.edu.vn
12 Sig K : P  A 1 x  P  y= Sigk(x) Và trong V có thuật toán kiểm thử: Nếu VerK : P  A  2 Đúng, Sai; Hai thuật toán thỏa mãn điều kiện sau với mọi x  P, y  A: Verk(x, y) = Đúng Nếu y = Sigk(x) Sai Nếu y  Sigk(x) 1.3.2. Chữ ký mù RSA a) Khái niệm Chữ ký mù đƣợc David Chaum đƣa ra vào năm 1983. Trong hệ chữ ký thông thƣờng, ngƣời ký phải đƣợc nắm rõ nội dung văn bản cần kỹ, có thể lƣu bản sao. Trong hệ chữ ký mù (blind signature), ngƣời ký sẽ không đƣợc thấy rõ nội dung mà mình ký, các thông điệp cần đƣợc kí bị “che” đi. Tuy nhiên hệ chữ ký cũng đảm bảo cho ngƣời ký có thể kiểm tra tính hợp lệ của thông tin cần ký. Chữ ký mù thƣờng đƣợc dùng trong các vấn đề đòi hỏi sự ẩn danh, nó dƣợc ứng dụng phổ biến trong tiền điện tử, bỏ phiếu điện tử… Nội dung M trƣớc khi ngƣời A đƣa cho ngƣời kí B sẽ bị làm mù thành M’. Ngƣời kí lúc này sẽ kí trên M’ chứ không phải trên M. Sau khi có đƣợc chữ kí trên M’, A xóa mù để có đƣợc chữ kí trên M. Nhƣ vậy ngƣời A vẫn có chữ kí hợp lệ của ngƣời B trên M mà B không biết thông tin gì về M. Ví dụ: A chuẩn bị một văn bản M, cho vào một phòng bì A4, có kèm một tờ giấy than, rồi dán lại và đƣa cho B. B chỉ có thể ký lên phía ngoài phong bì, nhƣng chữ ký sẽ đƣợc tạo ra trong văn bản bên trong thông qua tờ giấy than. Mặc dù B không thể biết đƣợc nội dung thật của văn bản này, nhƣng có thể đánh giá đƣợc tính trung thực của A (không tạo ra gì xấu cho B) mà một phép kiểm tra theo phƣơng pháp thách thức - đáp ứng. b) Sơ đồ chữ ký RSA - Chọn p, q nguyên tố lớn . Số hóa bởi Trung tâm Học liệu – ĐHTN http://www.lrc.tnu.edu.vn