Luận văn Thạc sĩ Công nghệ thông tin: Tìm hiểu chữ ký không thể phủ nhận và ứng dụng trong quản lý hoạt động của doanh nghiệp

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

Thêm vào BST

Báo xấu

15
lượt xem 2
download

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

Nội dung chính của luận văn này được chia làm 3 chương: Chương 1: Các khái niệm cơ bản. Chương 2: Chữ ký không thể phủ nhận. Chương 3: Ứng dụng chữ ký không thể phủ nhận trong hoạt động của doanh nghiệp.

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ĩ Công nghệ thông tin: Tìm hiểu chữ ký không thể phủ nhận và ứng dụng trong quản lý hoạt động của doanh nghiệp

ĐẠI HỌC QUỐC GIA HÀ NỘI TRƢỜNG ĐẠI HỌC CÔNG NGHỆ NGUYỄN VIẾT MINH TÌM HIỂU CHỮ KÝ KHÔNG THỂ PHỦ NHẬN VÀ ỨNG DỤNG TRONG QUẢN LÝ HOẠT ĐỘNG CỦA DOANH NGHIỆP LUẬN VĂN THẠC SĨ CÔNG NGHỆ THÔNG TIN HÀ NỘI - 2014
ĐẠI HỌC QUỐC GIA HÀ NỘI TRƢỜNG ĐẠI HỌC CÔNG NGHỆ NGUYỄN VIẾT MINH TÌM HIỂU CHỮ KÝ KHÔNG THỂ PHỦ NHẬN VÀ ỨNG DỤNG TRONG QUẢN LÝ HOẠT ĐỘNG CỦA DOANH NGHIỆP Ngành: Công nghệ thông tin Chuyên ngành: Hệ thống thông tin Mã số: 60480104 LUẬN VĂN THẠC SĨ CÔNG NGHỆ THÔNG TIN NGƢỜI HƢỚNG DẪN KHOA HỌC: TS. Hồ Văn Canh HÀ NỘI - 2014
i LỜI CAM ĐOAN Tôi xin cam đoan rằng luận văn của tôi là công trình nghiên cứu của bản thân. Luận văn hoàn toàn không phải là bản sao chép công trình nghiên cứu của một ngƣời khác, nó mang tính độc lập nhất định với tất cả các công trình nghiên cứu trƣớc đây. Tất cả các tài liệu tham khảo đều có xuất xứ rõ ràng và đƣợc trích dẫn hợp pháp. Nếu có vi phạm gì, tôi xin hoàn toàn chịu trách nhiệm. Hà Nội, ngày 30 tháng 11 năm 2014 Học viên Nguyễn Viết Minh
ii LỜI CẢM ƠN Đầu tiên, tôi xin gửi lời cảm ơn sâu sắc đến cán bộ hƣớng dẫn khoa học TS. Hồ Văn Canh, ngƣời đã tận tình hƣớng dẫn cho tôi từ những buổi đầu tiên khi tiếp cận với đề tài luận văn tốt nghiệp. TS. Hồ Văn Canh đã hƣớng dẫn, chỉ bảo cho tôi về phƣơng pháp nghiên cứu khoa học, cách làm việc khoa học trong suốt thời gian qua. Tôi xin bày tỏ lòng cảm ơn chân thành đến toàn thể các thầy cô giáo trƣờng Đại học Công nghệ - Đại học Quốc Gia Hà Nội đã tận tình giảng dạy và tạo điều kiện cho tôi học tập, nghiên cứu và hoàn thành đề tài luận văn này. Tôi xin chân thành cảm ơn các bạn học viên cao học K19, chuyên ngành Hệ thống thông tin đã giúp đỡ tôi trong quá trình học tập, nghiên cứu. Cuối cùng, tôi xin gửi lời cảm ơn sâu sắc đến gia đình, bạn bè, đồng nghiệp của tôi, những ngƣời đã động viên, tạo điều kiện tốt nhất cho tôi học tập và lao động trong suốt thời gian qua. Hà Nội, ngày 30 tháng 11 năm 2014 Học viên Nguyễn Viết Minh
iii MỤC LỤC LỜI CAM ĐOAN .............................................................................................................i LỜI CẢM ƠN ................................................................................................................. ii DANH MỤC CÁC KÝ HIỆU, CÁC CHỮ VIẾT TẮT ................................................ iii DANH MỤC CÁC HÌNH VẼ, ĐỒ THỊ ........................................................................vi MỞ ĐẦU ...................................................................................................................... vii Chƣơng 1: CÁC KHÁI NIỆM CƠ BẢN.........................................................................1 1.1. Một số kiến thức toán học liên quan ..................................................................1 1.1.1. Ƣớc số, bội số ..........................................................................................1 1.1.2. Số nguyên tố ............................................................................................1 1.1.3. Hàm  Euler ...........................................................................................1 1.1.4. Đồng dƣ thức ...........................................................................................1 1.1.5. Không gian Zn và Z*n ...............................................................................2 1.1.6. Khái niệm nhóm.......................................................................................2 1.1.7. Cấp của một phần tử ................................................................................3 1.1.8. Phần tử nguyên thủy ................................................................................3 1.1.9. Một số thuật toán .....................................................................................4 1.2. Chữ ký số ...........................................................................................................6 1.2.1. Khái niệm chữ ký số ................................................................................6 1.2.1.1. Ƣu điểm và hạn chế của chữ ký số ......................................................7 1.2.1.2. Phân loại lƣợc đồ chữ ký số .................................................................8 1.2.2. Tính pháp lý của chữ ký số ......................................................................9 1.2.3. Lƣợc đồ một số chữ ký số điển hình......................................................10 1.2.3.1. Lƣợc đồ chữ ký RSA .........................................................................10 1.2.3.2. Lƣợc đồ chữ ký ElGamal ...................................................................11 1.2.3.3. Lƣợc đồ chuẩn chữ ký số DSS ...........................................................13 1.3. Hàm băm ..........................................................................................................13 1.3.1. Khái niệm ............................................................................................... 13 1.3.2. Ứng dụng của hàm băm .........................................................................14 1.3.2.1. Một số ứng dụng ................................................................................14 1.3.2.2. Ứng dụng của hàm băm trong chữ ký số ...........................................14 1.3.3. Một số hàm băm sử dụng trong chữ ký số.............................................15 1.3.3.1. Hàm băm MD5 ...................................................................................15 1.3.3.2. Hàm băm SHA-1 ................................................................................17 Chƣơng 2: CHỮ KÝ KHÔNG THỂ PHỦ NHẬN ........................................................20 2.1. Khái niệm .........................................................................................................20
iv 2.2. Ứng dụng của chữ ký không thể phủ nhận ......................................................20 2.3. Lƣợc đồ chữ ký không thể phủ nhận Chaum-van Antwerpen (CVA) .............21 2.3.1. Thuật toán ký .........................................................................................21 2.3.2. Thuật toán kiểm tra ................................................................................21 2.3.3. Giao thức chối bỏ ...................................................................................22 2.3.4. Ví dụ ......................................................................................................22 2.3.5. Các định lý về tính đúng đắn của lƣợc đồ .............................................23 2.4. Một số lƣợc đồ cải tiến của chữ ký không thể phủ nhận .................................25 2.4.1. Chữ ký không thể phủ nhận có thể chuyển đổi .....................................25 2.4.1.1. Sự tồn tại lƣợc đồ chữ ký không thể phủ nhận có thể chuyển đổi .....26 2.4.1.2. Chữ ký không thể phủ nhận có thể chuyển đổi dựa trên chữ ký ElGamal ............................................................................................................27 2.4.1.3. Các chữ ký chuyển đổi toàn bộ ..........................................................31 2.4.1.4. Các chữ ký chuyển đổi có chọn lọc ...................................................31 2.4.1.5. Ví dụ ...................................................................................................32 2.4.1.6. Tính an toàn .......................................................................................32 2.4.2. Chữ ký ngƣời xác minh đƣợc chỉ định ..................................................33 2.4.2.1. Một số định nghĩa ..............................................................................33 2.4.2.2. Chữ ký ngƣời xác minh đƣợc chỉ định tƣơng tác .............................. 34 2.4.2.3. Chữ ký ngƣời xác minh đƣợc chỉ định không tƣơng tác. ..................35 2.4.2.4. Chữ ký nhóm ngƣời xác minh đƣợc chỉ định ....................................35 2.4.3. Chữ ký không thể phủ nhận dựa trên chữ ký RSA ................................ 36 2.4.3.1. Chuẩn bị ............................................................................................. 36 2.4.3.2. Lƣợc đồ .............................................................................................. 37 2.4.3.3. Phân tích mức độ an toàn ...................................................................39 2.4.4. Nhận xét .................................................................................................41 Chƣơng 3: ỨNG DỤNG CHỮ KÝ KHÔNG THỂ PHỦ NHẬN TRONG HOẠT ĐỘNG CỦA DOANH NGHIỆP ...................................................................................42 3.1. Các hoạt động liên quan đến chữ ký không thể phủ nhận ............................... 42 3.2. Chƣơng trình ứng dụng ....................................................................................44 3.3. Kết luận và hƣớng phát triển............................................................................51 TÀI LIỆU THAM KHẢO ............................................................................................. 53
v DANH MỤC CÁC KÝ HIỆU, CÁC CHỮ VIẾT TẮT STT Từ viết tắt Từ gốc Nghĩa Tiếng Việt Lƣợc đồ ký số của David 1 CVA Chaum, van Antwerpen Chaum và Hans van Antwerpen 2 DL Discrete Logarithm Logarit rời rạc 3 DSS Digital Signature Standard Chuẩn chữ ký số Chữ ký ngƣời xác minh đƣợc 4 DVS Designated Verifier Signature chỉ định 5 GCD Greatest Common Divisor Ƣớc số chung lớn nhất 6 LCM Least Common Multiple Bội số chung nhỏ nhất 7 MD5 Message-Digest algorithm 5 Thuật toán băm MD5 8 ORD Order Cấp của nhóm hoặc của phần tử 9 P Prover Ngƣời chứng minh chữ ký số Chữ ký số dựa trên lƣợc đồ mã 10 RSA Rivest-Shamir-Adleman hóa khóa công khai RSA 11 S Signer Ngƣời ký số 12 SHA Secure Hash Algorithm Thuật toán hàm băm an toàn 13 V Verifer Ngƣời xác minh chữ ký số
vi DANH MỤC CÁC HÌNH VẼ, ĐỒ THỊ Hình 1.1: Sơ đồ quy trình tạo và thẩm định chữ ký số ....................................................6 Hình 1.2: Phân loại chữ ký số theo chiến lược ký ...........................................................9 Hình 1.3: Ảnh minh họa làm việc của một hàm băm ....................................................14 Hình 1.4: Ghép thêm dữ liệu hàm băm MD5 ................................................................ 15 Hình 1.5: Khối dữ liệu sau khi thêm độ dài của hàm băm MD5...................................15 Hình 1.6: Xử lý hàm băm MD5 .....................................................................................17 Hình 1.7: Ghép thêm dữ liệu hàm băm SHA-1 .............................................................. 17 Hình 1.8: Các khối dữ liệu sau khi thêm độ dài của hàm băm SHA-1..........................18 Hình 2.9: Chứng minh rằng DL(u,  ) ≠ DL(v, w) . Người chứng minh P biết z  DL(u,  ) ................................................................................................................... 30 Hình 3.1: iao diện đăng nh p chương trình chữ ký kh ng th phủ nh n. ..................46 Hình 3.2: Chọn văn bản đ băm và ký. .........................................................................46 Hình 3.3: Giao diện giao thức ký của chương trình chữ ký kh ng th phủ nh n. ........47 Hình 3.4: Người xác minh tính c và gửi cho người ký. .................................................47 Hình 3.5: Người ký tính d và gửi cho người xác minh. .................................................48 Hình 3.6: Người xác minh ki m tra chữ ký. ..................................................................48 Hình 3.7: Giao thức chối bỏ: người xác minh tính c’ và gửi cho người ký...................49 Hình 3.8: Người xác minh chọn e1’ và e2’ rồi tính c’ và gửi cho người ký. ...................49 Hình 3.9: Người ký tính d’và gửi cho người xác minh. .................................................50 Hình 3.10: Người ký chối bỏ thành công. .....................................................................50
vii MỞ ĐẦU Trong những năm gần đây, cùng với sự phát triển mạnh mẽ của công nghệ thông tin, nhu cầu trao đổi thông tin qua mạng truyền thông ngày càng phổ biến. Sự phổ biến rộng rãi của mạng Internet đã kết nối mọi ngƣời trên toàn thế giới, trở thành công cụ không thể thiếu giúp tăng hiệu quả công việc, nâng cao sự hiểu biết, cập nhật, trao đổi thông tin nhanh chóng, thuận tiện. Vấn đề đặt ra là làm sao đảm bảo đƣợc sự an toàn cho thông tin trong quá trình trao đổi này, đặc biệt là với những thông tin quan trọng. Trong giao dịch truyền thống, chữ ký viết tay của một ngƣời phía dƣới một văn bản giấy không có tẩy xóa là đủ để xác nhận đƣợc danh tính ngƣời ký, ngƣời ký sẽ phải chịu trách nhiệm pháp lý về nội dung văn bản. Tuy nhiên, trong truyền tin điện tử thì văn bản chỉ là dãy bit, ta không ký tay lên dãy bit đó đƣợc mà phải sử dụng loại chữ ký khác gọi là chữ ký số. Chữ ký số cũng có nhiệm vụ giống với chữ ký tay trên văn bản giấy có con dấu xác thực màu đỏ. Sự ra đời của công nghệ mã hóa và chữ ký số đã trợ giúp con ngƣời trong việc giải quyết các bài toán về an toàn thông tin. Ở Việt Nam, từ năm 2006, Bộ Thƣơng mại và Ngân hàng Nhà nƣớc đã đƣợc Chính phủ cho phép triển khai chữ ký số và xác thực trong thanh toán điện tử. Tuy nhiên, chữ ký số trong một số trƣờng hợp tiềm ẩn nhiều nguy cơ sao chép, sử dụng lại nhiều lần. Vậy làm thế nào để ngăn chặn nguy cơ đó và làm thế nào để ngăn cản đƣợc ngƣời ký chối bỏ chữ ký của mình. Trƣớc những yêu cầu đó, đòi hỏi phải có lƣợc đồ chữ ký số có thể khắc phục đƣợc những nhƣợc điểm trên của chữ ký số, nâng cao tính an toàn, nâng cao trách nhiệm của ngƣời ký và ngƣời kiểm tra. Đó là lý do trong luận văn này tôi tìm hiểu về lƣợc đồ chữ ký không thể phủ nhận và ứng dụng nó trong quản lý hoạt động của doanh nghiệp. Nội dung chính của luận văn này đƣợc chia làm 3 chƣơng: Chƣơng 1: Các khái niệm cơ bản. Chƣơng 2: Chữ ký không thể phủ nhận. Chƣơng 3: Ứng dụng chữ ký không thể phủ nhận trong hoạt động của doanh nghiệp. Cụ thể, trƣớc khi đi vào tìm hiểu chữ ký không thể phủ nhận, trong chƣơng 1, ta tìm hiểu chung về một số kiến thức toán học cơ bản áp dụng trong chữ ký số, các kiến thức tổng quan về chữ ký số và hàm băm. Hai chƣơng sau cũng là hai chƣơng trọng tâm của luận văn này. Ở chƣơng 2, luận văn đi sâu tìm hiểu lƣợc đồ chữ ký số không thể phủ nhận cùng với một số tính năng nâng cao, biến thể của lƣợc đồ này cùng với những ứng dụng của các lƣợc đồ trong thực tế. Chƣơng thứ 3 tôi tiến hành ứng dụng lƣợc đồ chữ ký không thể phủ nhận trong quản lý hoạt động của doanh nghiệp với
viii chƣơng trình minh họa viết bằng ngôn ngữ Objective C để có thể hình dung rõ hơn về mô hình chữ ký không thể phủ nhận.
1 Chƣơng 1: CÁC KHÁI NIỆM CƠ BẢN 1.1. Một số kiến thức toán học liên quan 1.1.1. Ƣớc số, bội số Cho a, b là các số nguyên, ƣớc số chung (ƣớc chung) của a và b là c nếu a và b cùng chia hết cho c. Ví dụ: uớc chung của 20 và 12 là các số: 1, 2, 4. - Ước chung lớn nhất (great common divisor) của a và b là số lớn nhất mà a và b cùng chia hết. Ta ký hiệu ƣớc chung lớn nhất của a và b là gcd(a,b). Ví dụ: ƣớc chung lớn nhất của 20 và 12 là 4. - Bội chung nhỏ nhất (least common multiple) của a và b là số nguyên dƣơng nhỏ nhất có thể chia hết cho cả a và b. Nếu a hoặc b là 0 thì không tồn tại số nguyên dƣơng chia hết cho a và b, khi đó ta quy ƣớc bội chung nhỏ nhất của a và b là 0. Ký hiệu bội chung nhỏ nhất của a và b là lcm(a,b). Ví dụ: bội chung nhỏ nhất của 20 và 12 là 60. - Ta có: lcm(a,b) = (a.b)/gcd(a,b), nghĩa là: bội chung nhỏ nhất của a và b bằng tích của a, b chia cho ƣớc chung lớn nhất của hai số đó. 1.1.2. Số nguyên tố - Số nguyên tố là số chỉ chia hết cho 1 và chính nó. Ví dụ: 1, 2, 3, 5… là các số nguyên tố. - Hai số a, b gọi là nguyên tố cùng nhau khi ƣớc chung lớn nhất của chúng bằng 1 (hay gcd(a,b) = 1). Ví dụ: 5 và 7 là hai số nguyên tố cùng nhau. 1.1.3. Hàm  Euler Với n là một số nguyên dƣơng, ta định nghĩa hàm  Euler của n (ký hiệu  (n)) là số các số nguyên tố cùng nhau với n nằm trong khoảng [1, n]. Hàm  (n) có rất nhiều ứng dụng vì nó là kích thƣớc của nhóm nhân các số nguyên modulo (mô đun) n. Hàm  Euler có các tính chất sau: - Nếu p là số nguyên tố →   p   p  1 . - Nếu gcd(a, p)=1 và p là số nguyên tố → a   p   1 mod p (Định lý Fermat) Tổng quát: cho a, m: gcd(a, m)=1 → a  m   1 mod m (Định lý Euler) - Nếu p=m.n, gcd(m,n)=1 →   p    m. n - Nếu n  p1e . p2e . p3e ... →  n  n.1  1/ p1  1 2 3 . 1  1/ p2  . 1  1/ p3 ... 1.1.4. Đồng dƣ thức Cho n là số nguyên dƣơng, ta nói hai số nguyên a và b là đồng dƣ với nhau theo modulo n nếu (a-b) chia hết cho n. Ta ký hiệu: a  bmod n . Một số tính chất của đồng dƣ thức: a  amod n . a  bmod n  b  amod n . a  bmod n , b  cmod n → a  cmod n .
2 a  a1 mod n , b  b1 mod n → a  b  a1  b1 mod n ; a.b  a1 .b1 mod n . 1.1.5. Không gian Zn và Z*n  Zn: gồm tập hợp các số nguyên {0, 1, 2, …, n-1} và các phép toán cộng, trừ, nhân trong Zn đƣợc thực hiện theo modulo n. Ví dụ: Z21 = {0, 1, 2, …, 20}. Trong Z21 thì: 10+16=5 vì 10  16  26  5mod 21 10 *16  13 vì 10 * 16  160  13mod 21  Z n: là tập hợp các số nguyên trong Zn (hay còn gọi là nhóm nhân của Zn) sao * cho ƣớc chung lớn nhất của những số đó với n bằng 1. Hoặc có thể viết: Z n*  p  Z n | gcd n, p   1. Với n là số nguyên tố thì Z n*  p  Z n | 1  p  n  1  Z n /0. Ví dụ: Z3 = {0, 1, 2} Z*3 = {1, 2} vì gcd (1,3)=1; gcd (2,3)=1. 1.1.6. Khái niệm nhóm  Nhóm Nhóm là bộ các phần tử (G, *) với G là một tập hợp G    và “*” là một phép toán hai ngôi (thƣờng là phép cộng hoặc nhân) thỏa mãn các tính chất sau: - Tính chất đóng: x, y  G thì x  y  G . - Tính chất kết hợp: x  y   z  x   y  z  với x, y, z  G . - Tồn tại phần tử trung hòa 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 với x  G . Ví dụ: tập hợp G = {các số nguyên chẵn}, phép toán “*” là phép “+”. - Tính chất đóng: x, y  G  x, y chẵn, x  y chẵn. x chẵn => x = 2a; y chẵn => y = 2b với a, b nguyên. x+y = 2a+2b = 2(a+b) là một số nguyên chẵn. Vì thế 2a  b G . - Tính chất kết hợp: với x, y, z  G , phép toán “*” là phép “+” thì: (x + y) + z = x + y + z = x + (y+z) (thỏa mãn tính chất kết hợp). - Tồn tại phần tử trung hòa: tồn tại e=0∈G là phần tử trung hòa vì: Với e=0, x  G thì x+0 = 0+x = x. - Tồn tại phần tử nghịch đảo x' G : Với x chẵn bất kỳ, x = 2a, lấy x’ = -2a thì: x' G và x+x’ = x’+x = 2a+ (-2a) = 0 = e  G .  Nhóm con Nhóm con của nhóm (G, *) là bộ các phần tử (S, *) thỏa mãn các tính chất: S là một tập con của G ( S  G ), phần tử trung hòa e S và với x, y  S ta luôn có x yS .
3  Nhóm nhân Nhóm nhân của Z n ký hiệu là Z n* ,* là tập hợp các phần tử p thuộc Z n sao cho gcd(p,n)=1 và phép toán “*” trong Z n* thực hiện theo quy tắc a.b  c và c  a.b(mod n) . - Cấp của nhóm nhân Z n* : là số phần tử của Z n* , kí hiệu là Z n* , Z n*   n  . Z n* là lực lƣợng của Z n* .  Nhóm Cyclic Cho   Z n* nếu cấp của  là  n  khi đó  gọi là phần tử sinh hay phần tử nguyên thuỷ của Z n* , và nếu Z n* tồn tại một phần tử sinh thì đƣợc gọi là Cyclic. Nhóm Cylic có các tính chất sau: - Nếu  là phần tử sinh của Z n* thì Zn*   i mod n | 0  i   n. -  là phần tử sinh của tập Z n* khi đó b   i mod n cũng là phần tử sinh của Z n* khi và chỉ khi gcd(i,  n  )=1. - Nếu p là số nguyên tố thì Z *p chắc chắn có phần tử sinh. 1.1.7. Cấp của một phần tử Cho a là một số nguyên và n là một số nguyên dƣơng cố định. Nếu tồn tại số h nguyên dƣơng nhỏ nhất sao cho a h  1 mod n thì h đƣợc gọi là cấp của phần tử a theo modulo n và viết là h  ordn (a) . 1.1.8. Phần tử nguyên thủy Trong định nghĩa cấp của phần tử a, nếu h   (n) thì a đƣợc gọi là phần tử nguyên thủy (hay còn gọi là phần tử sinh). Các định lý: - Định lý 1.1: Xét nhóm nhân Z n* = {x: 1≤ x
4 - Định lý 1.3: Giả sử  là một phần tử nguyên thủy trong Z *p (với p là số nguyên tố lẻ). Khi đó với x  Z *p sao cho x   j mod p với j mà gcd(j,p-1)=1 thì x là phần tử nguyên thủy. Ví dụ: p=7, ta có p-1 = 6 = 2.3; j = 1, 5. Áp dụng định lý 1.3, ta có 35 mod 7  5 là phần tử nguyên thủy. Vậy trong Z*7 có 2 phần tử nguyên thủy là 3, 5. - Định lý 1.4: Giả sử gcd(a, p)=1, p là số nguyên tố, khi đó a là phần tử nguyên p 1 thủy khi và chỉ khi a q  1 mod p với mọi số nguyên tố q là ƣớc của p-1. Ví dụ: p=7, p-1=6=2.3 12  1 mod 7 ; 13  1 mod 7 ; 2 2  1mod 7 ; 23  1 mod 7 ; 3 2  1 mod 7 ; 33  1 mod 7 ; 42  1 mod 7 ; 43  1 mod 7 ; 52  1 mod 7 ; 53  1 mod 7 ; 62  1 mod 7 ; 63  1 mod 7 ;  3 và 5 là các phần tử nguyên thủy trong Z 7* . 1.1.9. Một số thuật toán  Thuật toán Euclid: thuật toán tìm ƣớc số chung lớn nhất của 2 số nguyên dƣơng. Cho 2 số nguyên dƣơng a, b với a ≥ b. Ta kí hiệu ƣớc số chung lớn nhất của 2 số a, b là gcd(a,b). Trƣớc hết ta có bổ đề sau: - Bổ đề 1.5: Nếu a = bq+r, với b>0 thì ƣớc số chung bất kỳ của a và b cũng là ƣớc chung của b và r; 0 ≤ r ≤ a ≤ b. Với r  0 thì gcd(a, b)= gcd(b, r). Do 0 ≤ r ≤ b nên có thể tìm gcd(a,b) sau một số hữu hạn bƣớc nhƣ sau: a  bq1  r1 0  r1  b b  r1 q 2  r2 0  r2  r1 r1  r2 q3  r3 0  r3  r2 … rk 1  rk 2 q k  rk 0  rk  rk 1 Cho đến khi rk 1  0 thì thuật toán dừng và gcd a, b  =gcd b,r1  =…=gcd rk 1 , rk  = rk . Từ bổ đề trên, ta có thuật toán tìm gcd(a,b): + Bƣớc 1: r  a  a / b* n , a  b , b  r (với [a/b] là phần nguyên của a chia cho b, tức là số nguyên lớn nhất nhƣng không lớn hơn a chia cho b). + Bƣớc 2: Nếu n≠0, quay lại bƣớc 1, ngƣợc lại thì dừng, a là đáp số. - Bổ đề 1.6: Số các phép chia trong thuật toán Euclid không vƣợt quá 2 log 2 b .
5 - Bổ đề 1.7: Nếu gcd(a,b)=k thì tồn tại các số nguyên x và y sao cho: ax +by=k. Từ đó, ta có thuật toán mở rộng đề xác định số x, y, k khi cho trƣớc a, b (giả thiết a>b).  Thuật toán Euclid mở rộng: Thuật toán sử dụng đầu vào là 2 số nguyên dƣơng a, b với a > b>0. Kết quả thu đƣợc ở đầu ra là k=gcd(a, b) và các số nguyên x, y thỏa mãn ax+by=k. Cho m1 , m2 , m3  , n1 , n2 , n3  , e1 , e2 , e3  là ba vector. + Bƣớc 1: m1 , m2 , m3  ← (1, 0, a); n1 , n2 , n3  ← (0, 1, b); + Bƣớc 2: Nếu n3 =0 thì thuật toán dừng và đáp số là m1 , m2 , m3 . + Bƣớc 3: Đặt q  m3 / n3 , (với m3 / n3  là phần nguyên của m3 / n3  ); và: e1 , e2 , e3  ← m1 , m2 , m3  - q n1 , n2 , n3  ; m1 , m2 , m3  ← n1 , n2 , n3  ; n1 , n2 , n3  ← e1 , e2 , e3  ; Và trở lại bƣớc 2. Kết quả đầu ra: m1  x , m2  y , m3  k . Ví dụ: a=42, b=4. Quá trình tính toán đƣợc cho trong bảng sau: q m1 m2 m3 n1 n2 n3 e1 e2 e3 10 1 0 42 0 1 4 1 -10 2 2 0 1 4 1 -10 2 -2 21 0 1 -10 2 -2 21 0 Vậy x = 1, y = -10, k = (42, 4) = 2. Thử lại: 42*1-10*4 = 2  Thuật toán nghịch đảo nhân trong Z n Thuật toán nghịch đảo nhân trong Z n với đầu vào là số a  Z n , đầu ra là a 1 mod n (nếu tồn tại). Ta sử dụng thuật toán Euclid mở rộng để tìm các số nguyên x và y sao cho ax  ny  k ; với k= gcd(a,n). Nếu k>1 thì a 1 mod n không tồn tại. Ngƣợc lại, trả về x.  Thuật toán tính số mũ modulo trong Z n Thuật toán tính số mũ modulo trong Z n có đầu vào là số a  Z n , và số nguyên k t với 0  k  n . Biểu diễn nhị phân của k gồm t bit có dạng: k   ki 2i , k i  0,1 , khi đó i 0 ak  a2  a  ...a  . Đầu ra của thuật toán là a 0 k0 1 2 k1 2t kt k mod n . Bƣớc 1: Đặt b  1 . Nếu k=0 thì trả về b. Bƣớc 2: Đặt A  a . Bƣớc 3: Nếu k 0  1 thì đặt b  a .
6 Bƣớc 4: Với i chạy từ 1 tới t. Ta đặt A  A2 mod n . Nếu k i  1 thì b  A.b mod n . Bƣớc 5: Trả về giá trị b. 1.2. Chữ ký số 1.2.1. Khái niệm chữ ký số Một chữ ký số là một lƣợc đồ toán học đƣợc sử dụng để xác thực ngƣời gửi tài liệu điện tử. Nó đảm bảo rằng tài liệu gửi đi thực sự đƣợc gửi từ đúng ngƣời này mà không phải từ bất kỳ ai khác, đồng thời đảm bảo rằng tài liệu nhận đƣợc từ ngƣời gửi không bị thay đổi. Chữ ký số đƣợc xem là hiệu quả cho các văn bản ràng buộc pháp lý vì chúng khó giả mạo và có thể đƣợc lƣu vết thời gian. Ngƣời ký Khóa bí mật Thông điệp Thông điệp Băm Ký số Chữ ký số rút gọn ban đầu Tách Thông điệp Chữ ký số ban đầu Khóa công Băm Xác thực khai Thông điệp Thông điệp rút gọn rút gọn khác nhau So sánh Chữ ký không hợp lệ giống nhau Chữ ký hợp lệ Ngƣời nhận Hình 1.1: Sơ đồ quy trình tạo và thẩm định chữ ký số
7 Chữ ký số là một dạng chữ ký điện tử dựa trên công nghệ mã hoá bất đối xứng. Để sử dụng chữ ký số thì ngƣời sử dụng phải có một cặp khoá gồm: khoá công khai (public key) và khoá bí m t (private key). Khoá bí mật dùng để tạo chữ ký số, khoá công khai dùng để thẩm định chữ ký số hay xác thực ngƣời tạo ra chữ ký số đó. Việc sử dụng chữ ký số thƣờng gồm hai quá trình đƣợc thực hiện bởi ngƣời ký số và ngƣời nhận chữ ký số (xem hình 1.1): Quá trình tạo chữ ký số sử dụng một kết quả băm lấy từ tài liệu đã đƣợc ký và một khóa bí mật. Xác minh chữ ký số là quá trình ngƣời nhận kiểm tra chữ ký số bằng cách xem xét tài liệu ban đầu và khóa công khai, từ đó xác định xem chữ ký số đã đƣợc tạo từ cùng tài liệu sử dụng khóa bí mật tƣơng ứng với khóa công khai đã nói đến. 1.2.1.1. Ƣu điểm và hạn chế của chữ ký số  Ƣu điểm: chữ ký số có một số ƣu điểm chính sau: - Không cần dấu xác thực: Chữ ký số không cần dấu xác thực nhƣ chữ ký thông thƣờng. - Tăng tốc độ: Các doanh nghiệp không cần phải chờ đợi các văn bản giấy để chuyển phát nhanh. Có thể hoàn thành hợp đồng với đầy đủ chữ ký của các bên liên quan trong một thời gian ngắn và không giới hạn về mặt địa lý. - Giảm chi phí: Sử dụng dịch vụ bƣu chính, chuyển phát nhanh hay chuyển trực tiếp các văn bản giấy tốn kém hơn so với sử dụng chữ ký số trên các tài liệu điện tử. - An toàn: Việc sử dụng chữ ký số và văn bản điện tử giảm thiểu nguy cơ văn bản bị hủy hoặc thay đổi trong quá trình truyền. - Tính xác thực: Một tài liệu điện tử đã ký số đƣợc đảm bảo pháp lý trong tòa án nhƣ bất kỳ tài liệu giấy nào đƣợc ký kết. - Theo dõi, lần vết: Văn bản ký số có thể đƣợc theo vết và xác định vị trí trong khoảng thời gian ngắn. - Dễ ki m tra: Dễ dàng kiểm tra xem chữ ký có phải là chữ ký thật của ngƣời ký hay không. - Không th phủ nh n: Việc ký một văn bản số xác định rằng bạn là ngƣời ký và bạn không thể phủ nhận điều đó. - Phòng ngừa mạo danh: Khó có thể giả mạo chữ ký số hoặc gửi một văn bản điện tử giả chữ ký của một ngƣời nào đó. - Đánh dấu thời gian: Có thể biết rõ đƣợc thời điểm tài liệu đƣợc ký.  Hạn chế: Bên cạnh rất nhiều ƣu điểm thì chữ ký số có một số hạn chế nhƣ các sản phẩm điện tử khác. - Hạn sử dụng: Chữ ký số dựa trên công nghệ, trong khi công nghệ tiến bộ rất nhanh chóng nên nhiều sản phẩm công nghệ có tuổi thọ ngắn. - Chứng nh n: Để sử dụng chữ ký số, cả ngƣời gửi và ngƣời nhận có thể cần tốn chi phí mua chứng thƣ số của các cơ quan cung cấp đáng tin cậy.
8 - Phần mềm: Để làm việc với chứng thƣ số, ngƣời gửi cần mua phần mềm kiểm tra. - Bản sao: Bản sao của thông điệp đã đƣợc ký đồng nhất với bản gốc, do đó phải cẩn thận để ngăn chặn một thông điệp đã ký bị sử dụng nhiều lần. Tuy có một số hạn chế nhƣ trên, nhƣng hầu hết các doanh nghiệp ngày nay đang đi theo ý tƣởng của các văn phòng ít giấy hơn. Để làm đƣợc điều đó, họ đã chọn cho mình một chữ ký số và xác định đƣợc những lợi thế khi sử dụng chúng. Nhiều doanh nghiệp, tổ chức đã sử dụng chữ ký số để xác thực các tài liệu quan trọng và ký kết các thỏa thuận ràng buộc về mặt pháp lý. 1.2.1.2. Phân loại lƣợc đồ chữ ký số Có nhiều tiêu chí khác nhau giúp phân loại chữ ký số. Tuy nhiên, trong luận văn này, ta chỉ xét một số tiêu chí phân loại sau [14]:  Phân loại theo mức an toàn - Chữ ký “một lần”: Để đảm bảo an toàn thì khóa ký chỉ đƣợc dùng một lần trên một tài liệu. Một số chữ ký thuộc loại này nhƣ: Chữ ký Fail-Stop, chữ ký một lần Lamport. - Chữ ký không th phủ nh n: Là loại chữ ký mà ngƣời ký tham gia trực tiếp vào việc kiểm tra chữ ký. Chữ ký không thể phủ nhận Chaum-van Antwerpen sẽ đƣợc trình bày cụ thể trong chƣơng 2 của luận văn. - Chữ ký số mù, chữ ký số mù nhóm: Là loại chữ ký mà ngƣời ký không thể biết nội dung văn bản mà mình ký.  Ph n loại theo các th nh phần tham gia - Chữ ký số trực tiếp: Là chữ ký số chỉ liên quan đến bên gửi và bên nhận. Chữ ký số trực tiếp cài đặt với mật mã khóa công khai và chỉ có tác dụng khi khóa riêng của bên gửi đƣợc đảm bảo an ninh. - Chữ ký số gián tiếp: Là chữ ký số có sự tham gia của một bên trọng tài. Bên trọng tài sẽ nhận thông điệp có chữ ký số từ bên gửi, kiểm tra tính hợp lệ của nó và bổ sung thông tin thời gian, sau đó gửi đến bên nhận. Với loại chữ ký này thì an ninh phụ thuộc chủ yếu vào bên trọng tài. Bên trọng tài có thể đƣợc phép nhìn thấy hoặc không nhìn thấy nội dung thông điệp. Chữ ký số gián tiếp có thể cài đặt với mã hóa đối xứng hoặc mã hóa công khai.  Phân loại theo chiến lƣợc chữ ký Chúng ta có thể chia chữ ký số ra 2 loại dựa vào chiến lƣợc chữ ký: Kỹ thuật ký đính kèm vào thông điệp mà chữ ký số là một phần đính vào thông điệp gửi đi và loại chữ ký mà từ nó có thể phục hồi lại thông điệp ban đầu trƣớc khi ký [5]. - Lược đồ chữ ký đính kèm th ng điệp: trong lƣợc đồ này, chữ ký số là một phần đính vào thông điệp gửi đi, cả chữ ký và thông điệp đều là đầu vào cho quá trình xác minh tính đúng đắn của chữ ký. Kỹ thuật ký này đƣợc sử dụng phổ biến trong thực tế,
9 dựa trên hàm băm và thƣờng ít bị tấn công giả mạo. Ví dụ một số lƣợc đồ thuộc loại này nhƣ: DSS, ElGamal, Schnorr. - Lược đồ chữ ký khôi phục th ng điệp: trong lƣợc đồ này, thông điệp đã ký có thể đƣợc khôi phục từ chữ ký của chính nó, nghĩa là thông điệp ban đầu này không phải là đầu vào cho quá trình xác minh chữ ký. Một số lƣợc đồ chữ ký số tiêu biểu thuộc loại này nhƣ: RSA, Rabin. Trong thực tế, hầu hết các lƣợc đồ chữ ký số khôi phục thông điệp chỉ sử dụng cho các thông điệp đính kèm thông điệp ngắn, có chiều dài cố định. Trong khi đó, lƣợc đồ chữ ký số đính kèm thông điệp sử dụng cho các thông điệp có độ dài tùy ý. Chiến lƣợc chữ ký Chữ ký khôi Chữ đính phục thông điệp kèm vào thông điệp Hình 1.2: Phân loại chữ ký số theo chiến lược ký 1.2.2. Tính pháp lý của chữ ký số Dựa trên những khái niệm và nguyên tắc cơ bản của bộ luật mẫu về Thƣơng mại điện tử của Ủy Ban Pháp luật thƣơng mại quốc tế - Liên Hợp Quốc, nhiều nƣớc trên thế giới đã xây dựng khung pháp lý riêng của mình về vấn đề sử dụng chữ ký số. Tuy còn một số khó khăn, trở ngại do các quy định pháp lý khác nhau ở từng quốc gia, nhƣng bộ luật mẫu này cung cấp các nguyên tắc chung mang tính quốc tế, giải quyết phần nào những rắc rối cho việc kết nối giữa các quốc gia, góp phần tạo ra môi trƣờng pháp lý an toàn cho hoạt động thƣơng mại điện tử. Ở Việt Nam, luật về giao dịch điện tử cũng đã đƣợc Quốc hội thông qua ngày 29 tháng 11 năm 2005 [23] và chính thức có hiệu lực từ ngày 01 tháng 03 năm 2006, theo luật này, văn bản điện tử đƣợc ký bằng chữ ký số có giá trị pháp lý tƣơng đƣơng văn bản giấy đƣợc ký và đóng dấu. Cho đến nay, luật cũng đã có những điều chỉnh, bổ sung cho phù hợp với sự phát triển của thƣơng mại điện tử trong nƣớc cũng nhƣ trên thế giới. Những sửa đổi bổ sung gần đây nhất về điều kiện sử dụng chứng thƣ số nƣớc ngoài đƣợc chấp nhận tại Việt Nam đƣợc quy định trong Nghị định số 170/2013/NĐ- CP, ngày 13 tháng 11 năm 2013, chính thức có hiệu lực ngày 01 tháng 01 năm 2014 [24].
10 1.2.3. Lƣợc đồ một số chữ ký số điển hình. Một lƣợc đồ chữ ký số thƣờng bao gồm hai thành phần chủ chốt là thu t toán ký và thu t toán xác minh. Một lƣợc đồ chữ ký số là một bộ 5 (P, A, K, S, V) thỏa mãn các điều kiện sau [3] [10]: - P là tập hợp hữu hạn các thông điệp có thể. - A là tập hữu hạn các chữ ký có thể. - K là tập hữu hạn các khóa. - S là tập các thuật toán ký (ứng với các khóa riêng k  K ). - V là tập các thuật toán xác minh (ứng với các khóa công cộng k  K ). Với mỗi k thuộc K, tồn tại một thuật toán ký sigk thuộc S và một thuật toán xác minh verk thuộc V, trong đó sigk và verk là các ánh xạ: sigk là một ánh xạ từ P sang A và verk là một ánh xạ từ P  A sang tập {True, False} thỏa mãn với mọi x thuộc P, y thuộc A, ver (x,y)= true nếu y= sigk(x) và verk (x,y) = false nếu y khác sigk(x). Với mỗi k thuộc K, hàm sigk và verk là các hàm thời gian đa thức, verk là hàm công khai còn sigk là hàm mật. Ý nghĩa của lược đồ: Khi một ngƣời muốn ký lên một thông điệp x thì ngƣời đó dùng thuật toán an toàn để tạo ra chữ ký y =sig(x) nhận đƣợc và gửi cho ngƣời nhận. Ngƣời nhận nhận đƣợc chữ ký sig(x) thì dùng thuật toán xác minh ver(x,y) để xác định tính đúng đắn của chữ ký số (trả về true hoặc false). Có thể viết:  true, khi y  sig k x  Verk x, y    .  false, khi y  sig k x  1.2.3.1. Lƣợc đồ chữ ký RSA Không gian thông điệp và bản mã của lƣợc đồ mã hóa khóa công khai RSA là Zn={0, 1, 2,…, n-1} với n=p.q là kết quả của việc chọn ngẫu nhiên các số nguyên tố khác nhau. Lƣợc đồ chữ ký RSA [5] [12] là lƣợc đồ chữ ký khôi phục thông điệp. Không gian chữ ký A và không gian ký S là Z n . Một hàm rút gọn R : P  Z n đƣợc chọn và đƣợc công khai.  Thuật toán sinh hóa cho lƣợc đồ chữ ký RSA: Mỗi thực thể B tạo một khóa công khai RSA và khóa bí mật tƣơng ứng. Với mỗi thực thể B, ta làm nhƣ sau: - Sinh hai số nguyên tố lớn ngẫu nhiên là p và q, với p và q có cùng kích thƣớc. - Tính n=p.q và   ( p  1)(q  1) . - Chọn một số nguyên ngẫu nhiên e, 1  e   , chọn gcd(e,  ) =1. - Sử dụng thuật toán Euclid mở rộng để tính số nguyên duy nhất d, 1  d   , ed  1mod   . - Khóa công khai của thực thể là (n,e), khóa bí mật là d.  Thuật toán sinh chữ ký và xác thực: B ký một thông điệp m P . C bất kỳ có thể xác thực chữ ký của B và khôi phục thông điệp m từ chữ ký. - Sinh chữ ký: B làm theo các bƣớc sau:  Tính m ~  Rm , một số nguyên trong khoảng [0, n-1]. R : P  Z . n