›

Đồ án Tìm hiểu lược đồ chữ ký số chống chối bỏ - Hoàng Văn Hiệp

pdf 54 trang huongle 2490
Download
Bạn đang xem 20 trang mẫu của tài liệu "Đồ án Tìm hiểu lược đồ chữ ký số chống chối bỏ - Hoàng Văn Hiệp", để tải tài liệu gốc về máy bạn click vào nút DOWNLOAD ở trên

Tài liệu đính kèm:

  • pdfdo_an_tim_hieu_luoc_do_chu_ky_so_chong_choi_bo_hoang_van_hie.pdf

Nội dung text: Đồ án Tìm hiểu lược đồ chữ ký số chống chối bỏ - Hoàng Văn Hiệp

  1. BỘ GIÁO DỤC VÀ ĐÀO TẠO TRƢỜNG ĐẠI HỌC DÂN LẬP HẢI PHÒNG o0o TÌM HIỂU LƢỢC ĐỒ CHỮ KÝ SỐ CHỐNG CHỐI BỎ ĐỒ ÁN TỐT NGHIỆP ĐẠI HỌC HỆ CHÍNH QUY Ngành: Công nghệ Thông tin Sinh viên thực hiện: Hoàng Văn Hiệp Giáo viên hƣớng dẫn: TS. Hồ Văn Canh Mã số sinh viên: 1351010042 HẢI PHÒNG - 2013
  2. Đồ án tốt nghiệp Trƣờng ĐHDL Hải Phòng MỤC LỤC MỞ ĐẦU 3 CHƢƠNG 1: MẬT MÃ KHÓA CÔNG KHAI 5 1.1. Lịch sử phát triển 5 1.1.1. Giới thiệu. 5 1.1.2. Định nghĩa hệ mật 5 1.2. Một vài hệ mật đơn giản 7 1.2.1. Mã dịch chuyển 7 1.2.2. Mã thay thế. 8 1.2.3. Mã Affine 9 1.2.4. Mã Vigenere. 10 1.2.5. Mã hoán vị. 11 1.3. Mật mã khoá công khai. 12 1.3.1. Cơ sở của mật mã khóa công khai. 13 1.3.2. Một số hệ mật điển hình 15 CHƢƠNG 2: CHỮ KÝ SỐ 19 2.1. Giới thiệu 19 2.2. Định nghĩa lƣợc đồ chữ ký số: 20 2.3. Một số lƣợc đồ chữ ký số 20 2.3.1. Lược đồ chữ ký RSA 20 2.3.2. Lược đồ chữ ký Elgamal 22 CHƢƠNG 3: HÀM HASH 26 3.1. Chữ ký và hàm Hash 26 3.1.1. Đặt vấn đề 26 3.1.2. Định nghĩa hàm HASH 26 3.2. Một số hàm HASH sử dụng trong chữ ký số 28 3.2.1. Các hàm HASH đơn giản 28 3.2.2. Hàm HASH MD5: 29 CHƢƠNG 4: CHỮ KÝ CHỐNG CHỐI BỎ 39 4.1. Giới thiệu 39 4.2. Sơ đồ chữ ký chống chối bỏ. 40 4.2.1. Thuật toán ký: 40 4.2.2. Thuật toán xác minh: 40 4.2.3. Giao thức từ chối: 40 Hoàng Văn Hiệp - CT1301 1
  3. Đồ án tốt nghiệp Trƣờng ĐHDL Hải Phòng CHƢƠNG 5 : ÁP DỤNG CHỮ KÝ CHỐNG CHỐI BỎ VÀO QUẢN LÝ HÀNH CHÍNH CỦA TRƢỜNG ĐẠI HỌC DÂN LẬP HẢI PHÒNG 45 5.1. Đặt vấn đề. 45 5.2. Giải quyết vấn đề. 45 CHƢƠNG 6: CHƢƠNG TRÌNH 48 6.1. Giải thích chƣơng trình 48 6.2. Các phép toán hỗ trợ 48 6.3. Demo chƣơng trình. 52 KẾT LUẬN 54 TÀI LIỆU THAM KHẢO 55 Hoàng Văn Hiệp - CT1301 2
  4. Đồ án tốt nghiệp Trƣờng ĐHDL Hải Phòng MỞ ĐẦU Cùng với sự phát triển mạnh mẽ của công nghệ thông tin và sự giao lƣu thông tin ngày càng trở nên phổ biến trên các mạng truyền thông, thì vấn đề đảm bảo an toàn thông tin đã trở thành một yêu cầu chung của mọi hoạt động kinh tế, xã hội và giao tiếp của con ngƣời. Để thực hiện yêu cầu về bảo mật thông tin thì cách hay dùng nhất là mã hoá thông tin trƣớc khi gửi đi. Vì vậy mật mã đã đƣợc nghiên cứu và sử dụng từ rất lâu trong lịch sử loài ngƣời. Tuy nhiên chỉ vài ba chục năm gần đây, nó mới đƣợc nghiên cứu công khai và tìm đƣợc các lĩnh vực ứng dụng trong đời sống công cộng cũng với sự phát triền của kỹ thuật tính toán và viễn thông hiện đại. Và từ đó, ngành khoa học này đã phát triển rất mạnh mẽ, đạt đƣợc nhiều kết quả lý thuyết sâu sắc và tạo cơ sở cho việc phát triển các giải pháp bảo mật và an toàn thông tin trong mọi lĩnh vực hoạt động của con ngƣời trong thời đại mà công nghệ thông tin đƣợc ứng dụng rộng rãi. Các hệ thống mật mã đƣợc chia làm hai loại: mật mã bí mật và mật mã khoá công khai. Trong các hệ thống mật bí mật, hai ngƣời muốn truyền tin bí mật cho nhau phải thoả thuận một khóa mật mã chung K, K vừa là khóa để lập mã vừa là khóa để giải mã. Và khóa K phải giữ kín chỉ có hai ngƣời biết. Đề tài dựa trên cơ sở là các hệ thống mật mã khóa công khai. Ở đây, quan niệm về bí mật đƣợc gắn với độ phức tạp tính toán: ta xem một giải pháp là bí mật, nếu để biết đƣợc bí mật thì cần phải thực hiện một quá trình tính toán cực kỳ phức tạp, phức tạp đến mức mà ta coi là “không thể đƣợc” trên thực tế. Với quan niệm đó, ngƣời ta đã cải tiến và tạo mới nhiều giải pháp mật mã chỉ có thể thực hiện đƣợc bằng các công cụ tính toán hiện đại. Mật mã khóa công khai là cống hiến mới của lý thuyết mật mã hiện đại và có nhiều ứng dụng mà các hệ thống mật mã cổ điển không thể có đƣợc. Mật mã khóa công khai dựa trên ý tƣởng: có thể tách riêng khóa làm hai phần tƣơng ứng với hai quá trình lập mã và giải mã. Bí mật là dành cho ngƣời nhận tin, nên phần khóa giải mã phải đƣợc giữ bí mật cho ngƣời nhận tin, còn phần khóa dành cho việc lập mã để gửi đến một ngƣời A có thể công khai để mọi ngƣời có thể dùng để gửi thông tin mật cho A. Ý tƣởng đó đƣợc thực hiện nhờ vào các hàm cửa sập một phía. Tính ƣu việt của các hệ thống mật mà này thể hiện ở chỗ: trong một hệ truyền tin bảo mật không ai phải trao đổi khóa bí mật trƣớc với ai Hoàng Văn Hiệp - CT1301 3
  5. Đồ án tốt nghiệp Trƣờng ĐHDL Hải Phòng cả, mỗi ngƣời chỉ giữ cái bí mật riêng của mình mà vẫn truyền tin bảo mật với mọi ngƣời khác. Điều này rất quan trọng khi việc truyền tin đƣợc phát triển trên các mạng rộng với số ngƣời sử dụng gần nhƣ không hạn chế. Mật mã khóa công khai không chỉ có tác dụng bảo mật, mà còn có nhiều ứng dụng khác, một trong các ứng dụng đó là xác thực, chữ ký số. Trong cách giao thiệp truyền thống, một chữ ký viết tay của ngƣời gửi dƣới một văn bản không có tẩy, xoá là đủ xác nhận ngƣời gửi là ai, ngƣời gửi có trách nhiệm về văn bản và sự toàn vẹn của văn bản và cũng không thể chối bỏ trách nhiệm về chữ ký của mình. Nhƣng trong truyền tin điện từ, văn bản chỉ là một dãy bít, nên để đảm bảo đƣợc hiệu lực nhƣ truyền thống thì ngƣời ta phải dùng chữ ký số. Chữ ký số cũng có nhiệm vụ giống chữ ký tay nghĩa là nó dùng để thực hiện các chức năng xác nhận của một ngƣời gửi trên một văn bản. Nó phải làm sao vừa mang dấu vết không chối cãi đƣợc của ngƣời gửi, vừa phải gắn bó với từng bit của văn bản mà nếu thay đổi dù chỉ một bit của văn bản thì chữ ký cũng không còn đƣợc chấp nhận. May thay, những yêu cầu này có thể thực hiện đƣợc bằng phƣơng pháp mật mã khoá công khai. Nói chung các sơ đồ chữ ký số thì không cần đối thoại. Tuy nhiên, trong một số trƣờng hợp để tăng thêm trách nhiệm trong việc xác nhận, ngƣời ta dùng các giao thức có tính chất đối thoại (hay chất vấn )qua một vài lần hỏi đáp để chính thức xác nhận tính đúng đắn (hoặc không đúng đắn) của chữ ký, tính toàn vẹn của văn bản, hay để buộc chấp nhận (không thể thoái thác, chối bỏ) chữ ký của mình. Trên cơ sở đó, trong đề tài tốt nghiệp tôi tìm hiểu về lƣợc đồ chữ ký số chống chối bỏ và việc áp dụng nó trong quản lý hành chính trên mạng của trƣờng Đại học Dân Lập Hải Phòng. Hoàng Văn Hiệp - CT1301 4
  6. Đồ án tốt nghiệp Trƣờng ĐHDL Hải Phòng CHƢƠNG 1: MẬT MÃ KHÓA CÔNG KHAI 1.1. Lịch sử phát triển 1.1.1. Giới thiệu. Theo các nhà nghiên cứu lịch sử mật mã thì Hoàng đế Caesar là ngƣời đầu tiên sử dụng mật mã trong quân sự. Trong năm 1949, bài báo của Claude Shannon lần đầu tiên đã đƣợc công bố với tiêu đề “lý thuyết thông tin của các hệ thống mật" (Communication Theory of Secret Systems) trong The Bell Systems Technical Joumal. Bài báo này đã đặt nền móng khoa học cho mật mã, nó có ảnh hƣởng lớn đến việc nghiên cứu khoa học của mật mã. Ý tƣởng về một hệ mật khoá công khai đã đƣợc Diffie và Hellman đƣa ra vào 1976, còn việc hiện thực hoá đầu tiên hệ mật khoá công khai thì do Rivest, Shamir và Adleman đƣa ra vào năm 1977. Họ đã tạo nên hệ mật RSA nổi tiếng. Kể từ đó đã có nhiều hệ mật đƣợc công bố và đƣợc phân tích, tấn công. Mục tiêu cơ bản của mật mã là giúp hai ngƣời (Bob và Alice) thƣờng xuyên liên lạc với nhau qua một kênh không an toàn mà sao cho đối phƣơng (Oscar) không thể hiểu họ đang nói gì. Kênh này có thể là một đƣờng dây điện thoại hoặc mạng máy tính. Thông tin Alice muốn gửi cho Bob, mà chúng ta gọi là “thông báo rõ“, có thể là văn bản tiếng Anh, các dữ liệu bằng số, hoặc bất kỳ tài liệu nào có cấu trúc tuỳ ý.Alice mã thông báo bằng cách sử dụng một khoá đã đƣợc xác định trƣớc và gửi kết quả trên kênh. Oscar thu trộm mã trên kênh song không thể hiểu đƣợc thông báo rõ là gì, nhƣng với Bob ngƣời biết khoá mã của Alice có thể giải mã và thu đƣợc thông báo rõ. 1.1.2. Định nghĩa hệ mật Một hệ mật là một bộ 5 thành phần (P, C, K, E, D) thoả mãn các điểu kiện sau: 1. P: là 1 tập hữu hạn các bản rõ có thể. 2. C: là 1 tập hữu hạn các bản mã có thể. 3. K: (không gian khoá): tập hữu hạn các khóa có thể 4. Đối với mỗi k K có 1 quy tắc mã ek E và một quy tắc giải dk D tƣơng ứng, trong đó: Hoàng Văn Hiệp - CT1301 5
  7. Đồ án tốt nghiệp Trƣờng ĐHDL Hải Phòng Mỗi ek: P → C và dk: C→P là các hàm thoả mãn: dk (ek(x)) = x với mọi x P Tính chất quan trọng nhất là tính chất 4. Nội dung của nó là nếu một bản rõ x đƣợc mã hoá bằng ek và bản mã đƣợc giải mã bằng dk thì ta phải thu đƣợc bản rõ ban đầu x. Alice và Bob sẽ áp dụng thủ tục sau để dùng hệ mật khoá riêng. Đầu tiên họ chọn một khoá ngẫu nhiên k K. Điều này đƣợc thực hiện khi họ ở cũng một chỗ và không bị theo dõi bởi Oscar, hoặc khi họ có một kênh an toàn trong trƣờng hợp không cũng một chỗ. Sau đó Alice muốn gửi cho Bob một thông báo trên một kênh không an toàn, giả sử thông báo ấy là một chuỗi : x= x1 x2 xn (với số nguyên n ≥1, ở đây mỗi bản rõ đƣợc ký hiệu là xi P, 1 ≤ i ≤ n). Alice mã mỗi xi bằng quy tắc ek với khoá xác định trƣớc là k. Nghĩa là, Alice tính: yi = ek(xi), 1 ≤ i ≤n, và kết quả là một chuỗi: y = y1 y2 yn sẽ đƣợc gửi trên kênh. Khi Bob nhận đƣợc y1 y2 yn , anh ta sẽ giải nó bằng hàm dk và thu đƣợc thông bảo gốc x1 x2 xn. Ta có thể hình dung hệ thống liên lạc nhƣ sau: Oscar y y y Alice x Bộ mã Bộ giải x Bob k k Kênh an toàn k Nguồn khóa Rõ ràng trong trƣờng hợp này, hàm ek phải là hàm đơn ánh (ánh xạ 1-1) nếu không việc giải mã sẽ không thực hiện đƣợc một cách tƣờng minh. Ví dụ nếu: y = eK(x1) = e2(x2), trong đó x1 ≠ x2, thì Bob sẽ không biết giải mã thành x1 hay x2. Chú ý ràng nếu P=C thì mỗi hàm mã hoá sẽ là một phép hoán vị, tức là nếu tập các bản mã và tập các bản rõ đồng nhất thì mỗi một hàm mà sẽ là một hoán vị của các phần tử của tập này. Hoàng Văn Hiệp - CT1301 6
  8. Đồ án tốt nghiệp Trƣờng ĐHDL Hải Phòng 1.2. Một vài hệ mật đơn giản 1.2.1. Mã dịch chuyển Giả sử P = C = K = Z26 , với 0≤k ≤ 25, định nghĩa: eK(x) = x + k mod 26 và dK(x) = y - k mod 26; (x, y € Z26) Ví dụ: Cho k = 11 và bản rõ là: wewillmeetatmidnight Biến đối bản rõ thành dày các số nguyên tƣơng ứng và công với k theo modulo 26: 22 4 22 8 11 11 12 4 4 19 0 19 12 8 3 13 8 6 7 19 + K =11 7 15 7 19 22 22 23 15 15 4 11 4 23 19 14 24 19 17 18 4 Biến đổi dãy số nguyên này các ký tự ta đƣợc bản mã sau: hphtwwxppelextoytrse Để giải mã thì ta chuyển bản mã thành dãy số nguyên ,sau đó trừ đi K theo modulo 26: 7 15 7 19 22 22 23 15 15 4 11 4 23 19 14 24 19 17 18 4 - K =11 22 4 22 8 11 11 12 4 4 19 0 19 12 8 3 13 8 6 7 19 ta sẽ đƣợc bản rõ ban đầu là: wewillmeetatmidnight Nhận xét: Mã dịch chuyển là không an toàn vì nó có thể bị thám khóa bằng phƣơng pháp vét cạn( vì chỉ có 26 khóa). Về trung bình, sẽ tính đƣợc thông báo sau 26/2 = 13 lần thử. Hoàng Văn Hiệp - CT1301 7
  9. Đồ án tốt nghiệp Trƣờng ĐHDL Hải Phòng Một hệ mật muốn sử dụng đƣợc trong thực tế thì nó phải thỏa mãn một số tính chất nhất định. Sau đây sẽ nêu ra hai trong số đó: 1. Mỗi hàm mã hóa ek và mỗi hàm giải mã dk phải có khả năng tính toán đƣợc một cách hiệu quả. 2. Đối phƣơng dựa trên xâu bản mã phải không có khả năng xác định khóa k đã dùng hoặc không có khả năng xác định đƣợc xâu bản rõ x. 1.2.2. Mã thay thế. Định nghĩa hệ mật: Cho P = C = Z26. K chứa mọi hoán vị có thể của 26 ký hiệu 0, 1, 2, , 25. Với mỗi hoán vị K, ta xác định phép thế và với mỗi phép thế đó ta định nghĩa: eK (x) = (x) -1 và dK (y) = (y) Trong đó -1 là phép thế ngƣợc của , Ví dụ: K= defghijkolnmpqrswtuvyxbaze a b c d e i g h i j k 1 m n o p q r s t u v w x y z П = d e f g h i j k o l n m p q r s w t u v y x b a z c Hãy giải bản mã sau đây: qdbqj vpybd mdifk yzhhq lfydt utsbo iacza a b c d e f g h i j k l m n o p q r s t u v w x y z П-1 = . x w z a b c d e f g h j l k i m n p o r t s q v u y Để giải bản mã trên, áp dụng П-1 vào từng ký tự của bản mã, sau đó ghép lại ta sẽ đƣợc bản rõ tƣơng ứng. Cụ thể nhƣ sau: Hoàng Văn Hiệp - CT1301 8
  10. Đồ án tốt nghiệp Trƣờng ĐHDL Hải Phòng qdbqj => navvng => nắng vpybd=> smuvva => mƣa mdifk => lafch => là yzhhq => uyeen => chuyện lfydt => jcuar => của utsbo => trovvi => trời Nhận xét: Mỗi khoá của mật mã thay thế là một phép hoán vị của 26 ký tự. Số hoán vị là 26!, lớn hơn 4 x 1026 . Đó là một số rấl lớn. Bởi vậy, phép tìm khóa vét cạn không thể thực hiện đƣợc, thậm chí bằng máy tính. 1.2.3. Mã Affine Trong mã Affine, ta xét các hàm mã có dạng: e (x) = ax + b mod 26, (a, b Z26). Các hàm này đƣợc gọi là hàm Affine (khi a = 1 => ta có mã dịch chuyển). Để việc giải mã có thể thực hiện đƣợc, yêu cầu cần thiết là hàm Affine phải đơn ánh. Với bất kỳ y Z26, ta cần phƣơng trình: ax + b ≡ y (mod 26), phải có nghiệm duy nhất. Đồng dƣ thức này tƣơng đƣơng với : ax = y - b (mod 26). Vì y biến đổi trên Z26 nên (y - b) mod 26 cũng biến đối trên Z26 .Vì vậy, ta chỉ cần xét đồng dƣ thức: ax ≡ y (mod 26), y Z26 Ta biết rằng, phƣơng trình này có 1 nghiệm duy nhất đối với mỗi y khi và chỉ khi (a, 26) = 1. Trƣớc tiên, giả sử rằng (a, 26) = d > 1. Thế thì, ax≡0(mod 26) sẽ có ít nhất 2 nghiệm phân biệt trong Z26 là x = 0 và x =26/d. Khi đó, e(x) = ax + b mod 26 không phải hàm đơn ánh vì vậy nó không phải là một hàm mã hợp lệ. + Ta giả thiết (a, 26) = 1. Khi đó phƣơng trình ax = y (mod 26) có đúng một -1 nghiệm với mọi y Z26 là x = a y (mod 26). + Hệ mật: Cho p = c = Z26 và giả sử: K = { (a, b) Z26 x Z26 : (a, 26) = 1} Hoàng Văn Hiệp - CT1301 9
  11. Đồ án tốt nghiệp Trƣờng ĐHDL Hải Phòng với k = (a, b) K, ta định nghĩa: ek (x) = ax + b mod 26 -1 và dk (x) = a (y - b) mod 26. x, y Z26 +Ví dụ: k = (7, 3). Do ( 7, 26) = 1 nên có hàm mã là: ek (x) = 7x + 3 -1 và hàm giải mã: dk = 7 (y - 3) mod 26 = 15 (y - 3) = 15y - 19 Bản rõ: hot chuyền thành các số nguyên tƣơng ứng là 7, 14, 19. ek(h) = 7x7 + 3 mod 26 = 0 ek (o) = 7x14 + 3 mod 26 = 23 ek (t) =7x19+3 mod 26=6 Chuyền ba sổ 0, 23, 6 thành ký tự tƣơng ứng ta đƣợc bản mã là AXG. Giải ngƣợc lại: AXG => 0 23 6 dk (A) = 15x0-19 mod 26 = 7 => H dk (X) = 15x23- 19 mod 26 = 14 => O dk (G) =15x6-19 mod 26 = 19 => T 1.2.4. Mã Vigenere. Cho m là một số nguyên dƣơng cố định nào đó. Định nghĩa P = C = K = m (Z26) . Với khoá k = (k1, k2 , , km ) ta xác định: ek (x1, x2, , x m ) = (x1 + k1 , x2 + k2, , xm + km); và dk (y1, y2, ,ym) = (y1 – k1, y2 - k2, , , ym - km); trong đó tất cá các phép toán đƣợc thực hiện trong Z26. Ví dụ: m = 6. từ khoá k = CIPHER = (2, 8, 15, 7, 4, 17) Thông báo x: thiscryprosystemisnotsecure Chuyển từng khối 6 ký tự sang số: Hoàng Văn Hiệp - CT1301 10
  12. Đồ án tốt nghiệp Trƣờng ĐHDL Hải Phòng thiscr => 19 7 8 18 2 17 k 2 8 15 7 4 17 21 15 23 25 6 8=>VPXZGI yptosy => 24 15 19 14 18 24 k 2 8 15 7 4 17 0 23 8 21 22 15=>AXIVWP stemis => 18 19 4 12 8 18 k 2 8 15 7 4 17 20 1 19 19 12 9=> UBTTMJ notsec => 13 14 19 18 4 2 k 2 8 15 7 4 17 15 22 8 25 8 19 =>PWIZIT ure => 20 17 4 k 2 8 15 22 25 19 =>WZT 1.2.5. Mã hoán vị. Ý tƣởng của mật mã hoán vị là giữ các ký tự trên bản rõ không đổi nhƣng thay đổi vị trí của chúng bằng cách sắp xếp lại các ký tự này. m Cho m là một số nguyên dƣơng xác định nào đó. Cho P = C = (Z26) và K gồm tất cả các hoán vị của {1, , m} .Đối với một khoá K (tức là một hoán vị), ta xác định phép thế n tƣơng ứng và xác định: eK (x1, ,xm)=(xn(1),xn(m)) -1 -1 và dK (y1, ,ym) = (yn (1), ,yn (m)) Trong đó n-1 là hoán vị ngƣợc của n. Hoàng Văn Hiệp - CT1301 11
  13. Đồ án tốt nghiệp Trƣờng ĐHDL Hải Phòng Ví dụ: Cho m=6, K= 351642, khi đó ta có phép thế: 1 2 3 4 5 6 = 3 5 1 6 4 2 Hãy giải bản mã: wsstpa isorsw onugww difjad cdhajo laapan arjpih nfhsgo lmefax eklyxe iermen uojwwm suisaf wtnhma hlaafn jrautp wgwfno. Tìm: 1 2 3 4 5 6 -1= 3 6 1 5 2 4 Áp dụng - 1 vào bản mã ta đƣợc bản rõ nhƣ sau: wsstpa → sawpst eklyxe → leexky isorsw → owistr iermen → rnieem onugww → uwowng uojwwm → jmuwow difjad → fddaij suisaf → ifsaus cdhajo → hocjda wtnhma → nawmth laapan → anlaap hlaafn → anhfla arjpih → jhairp jrautp → apjtru nfhsgo → hongfs wgwfno → wowngf lmefax → exlamf Bản rõ thu lại đƣợc là: Sắp tới trƣờng Đại học dân lập Hải Phòng sẽ làm lễ kỷ niệm mƣời sáu năm thành lập trƣờng. 1.3. Mật mã khoá công khai. Trong mô hình mật mã cổ điển mà cho tới nay vẫn còn đang đƣợc nghiên cứu, Alice (ngƣời gửi) và Bob (ngƣời nhận) chọn k một cách bí mật .Sau đó dùng k để mã hóa và giải mã. Các hệ mật thuộc loại này còn đƣợc gọi là các hệ mật khóa bí mật vì việc để lộ k sẽ làm cho hệ thống mất an toàn. Nhƣợc điểm của hệ mật này là nó yêu cầu phải có thông tin về khoá k giữa Alice và Bob qua một kênh an toàn trƣớc khi gửi một bản mã bất kỳ. Trên thực tế, điều Hoàng Văn Hiệp - CT1301 12
  14. Đồ án tốt nghiệp Trƣờng ĐHDL Hải Phòng này rất khó đảm bảo, chẳng hạn khi Alice và Bob ở rất xa nhau và liên lạc với nhau bằng thƣ tín điện tử (Email), thì việc xây dựng một kênh an toàn là rất khó khăn. Ý tƣởng xây dựng một hệ mật khóa công khai là tìm một hệ mật không có khả năng tính toán để xác định dk nếu đã biết ek. Nếu thực hiện đƣợc nhƣ vậy thì quy tắc ek có thể đƣợc công khai bằng cách công bố nó. Ƣu điểm của hệ mật khóa công khai là ở chỗ Alice (hoặc bất kỳ ngƣời nào đó) có thể gửi một thông báo đã đƣợc mã hóa( mà không cần phải thông tin trƣớc về khóa bí mật) bằng quy tắc mã công khai ek. Bob sẽ là ngƣời duy nhất có thể giải đƣợc bản mã này bằng quy tắc giải mã bí mật dk của mình. Ta cũng có thể hình dung hệ mật nhƣ sau: Alice đặt một vật vào một hộp kim loại và rồi khóa nó bằng một khóa bấm do Bob để lại. Chỉ có Bob là ngƣời duy nhất có thể mở đƣợc hộp vì chỉ có anh ta mới có chìa mở đƣợc khóa của mình. 1.3.1. Cơ sở của mật mã khóa công khai. Hệ mật khóa công khai không bao giờ đảm bảo đƣợc độ mật tuyệt đối( an toàn vô điều kiện). Khi đối phƣơng nghiên cứu bản mã y, thì anh ta có thể mã lần lƣợt các bản rõ có thể bằng quy tắc mã công khai ek cho tới khi anh ta tìm đƣợc một bản rõ duy nhất x thỏa mãn y = ek (x). Bản rõ này chính là kết quả giải mã của y. Các hàm một chiều đóng vai trò rất quan trọng trong mật mã. Trong mật mã khóa công khai ngƣời ta muốn rằng thuật toán mã hóa nhờ khóa công khai ek của Bob là dễ tính toán song việc tính hàm ngƣợc( tức là giải mã) phải rất khó đối với bất kỳ ai không phải là Bob. Hàm f(x) đƣợc gọi là hàm 1 chiều, nếu tính y = f(x) là dễ nhƣng việc tính ngƣợc x = f-1(y) là rất khó. Có thể hiểu "dễ" là tính đƣợc trong thời gian đa thức( ví dụ đa thức bậc thấp) và "khó" theo nghĩa là không tính đƣợc trong thời gian đa thức. Cho đến nay, chƣa có hàm nào đƣợc chứng minh là một chiều nhƣng có một số hàm đƣợc tin là hàm một chiều. Thí dụ: Hàm f(x) = gx mod p (p: số nguyên tố; g: phần tử nguyên thủy mod p) đƣợc tin là hàm một chiều. Hàm f(x) = x2 mod n(n: là tích của 2 số nguyên tố lớn khác nhau n=p.q) cũng đƣợc ngƣời ta tin là hàm một chiều. Tuy nhiên, để xây dựng một hệ mật khoá công khai thì việc tìm đƣợc hàm một chiều vẫn chƣa đủ. Ta không muốn ek là hàm một chiều đối với Bob vì anh ta phải có khả năng giải mã các bản mã nhận dƣợc một cách có hiệu quả. Điều cần thiết là Bob cần phải có một cửa sập chứa thông tin bí mật cho phép dễ dàng tìm ngƣợc ek. Hoàng Văn Hiệp - CT1301 13
  15. Đồ án tốt nghiệp Trƣờng ĐHDL Hải Phòng Nhƣ vậy, Bob có thể giải mã 1 cách hữu hiệu vì anh ta biết cái cửa sập nằm trong bí mật của K. Bởi vậy, hàm f(x) đƣợc gọi là hàm cửa sập một chiều, nếu f là hàm một chiều nhƣng nếu biết cửa sập của nó thì việc tính f-1(y) là dễ. Thí dụ: cho n = p.q là tích của hai số nguyên tố lớn, a là số nguyên, hàm f(x) = xa (mod n) là hàm cửa sập một chiều, nếu chi biết n và a thì tính x=f-1(y) là rất khó, nhƣng nếu biết cửa sập, chẳng hạn hai thừa số của n thì sẽ tính đƣợc f-1(y) khá dễ. 1.3.2. Một số hệ mật điển hình a. Hệ mật RSA. Hệ mật RSA do Rives, Shamir và Adleman đề xuất năm 1977. Giá sử n là số nguyên, tích của hai số nguyên tố lớn khác nhau p và q, n = p.q. Ta chọn số a nguyên tố với ϕ(n) = (p - 1) (q -1) và tính b ≡a-1 mod ϕ; tức ab≡mod ϕ(n). Hệ RSA đƣợc mô tả nhƣ sau: Lấy n = p.q; p và q là hai số nguyên tố khác nhau: P = C = Zn K = {(n, p, q, b, a): ab ≡ 1 mod ϕ(n)} trong đó n, b: công khai; a, p, q: bí mật. Với k = (n, p, q, a, b) ta định nghĩa: b ek(x) = x mod n,V x P a ek(y) = y mod n, Vy C Ví dụ: Giá sử Bob chọn p = 101 và q = 113. Khi đó n = 11413 và ϕ(n)=100 x 112 =11200. Vì 11200 = 26.52.7, nên có thế dùng một số nguyên b nhƣ một số mũ mã hoá khi và chỉ khi b không chia hết cho 2, 5 hoặc 7. Giá sử Bob chọn b = 3533 (vì(ϕ(n), b)=l). Khi đó: a = b-1 mod <ϕ(n) = 3533-1 mod ϕ(n) = 6597 Bob sẽ công bố n = 11413 và b = 3533 trong thƣ mục công cộng. Bây giờ giá sử Alice muốn gửi bản rõ x = 9726 tới cho Bob. Cô ta sẽ tính: y = xb mod n = 9 7 2 6 3533 mod 11413 = 5761 Sau đó cô ta sẽ gửi bản mã 5761 trên kênh liên lạc. khi Bob nhận dƣợc bản mã Hoàng Văn Hiệp - CT1301 15
  16. Đồ án tốt nghiệp Trƣờng ĐHDL Hải Phòng 5761. anh ta sử dụng khoá bí mật a để tính: 5761 6597 mod 11413 = 9726. b Độ mật của RSA đƣợc dựa trên giả thiết là hàm mã ek(x) = x mod n là hàm một chiều. Bởi vậy, thám mã sẽ không có khả năng về mặt tính toán để giải một bản mã. Cửa sập cho phép Bob giải mã đƣợc chính là thông tin về phép phân tích thừa số n = p.q. Các thuật toán phân tích hiện thời có khả năng phân tích các số khoảng 130 chữ số thập phân, vì vậy để đảm bảo an toàn nên chọn số p và số q lớn, chẳng hạn có chừng 100 chữ số, khi đó n sẽ có 200 chữ số. Trong khoảng 20 năm, ngƣời ta đã đƣa ra nhiều sơ hở đề tấn công hệ mật RSA nhƣng không có cách nào hiệu quả tuyệt đối mà chi đƣa ra các sơ hở để ngƣời dùng hệ mật RSA tránh không mắc phải, do đó RSA vẫn là hệ mật an toàn. b. Hệ mật Elgamal + Hệ mật Elgamal đƣợc xây dựng dựa trên bài toán logarithm rời rạc. Bài toán logarithm rời rạc trong Zp đƣợc xem là bài toán khó nếu số p đƣợc chọn cẩn thận .Cụ thể là không có thuật toán nào giải bài toán logarithm rời rạc trong thời gian đa thức. Số p đƣợc lựa chọn phải có ít nhất 150 chữ số thập phân và (p - 1) phải có ít nhất 1 thừa số nguyên tố lớn. Lợi thế của bài toán logarithm rời rạc là khó tìm đƣợc các logarithm rời rạc, song bài toán ngƣợc lấy luỹ thừa lại có thể tính dễ dàng. Hay luỹ thừa theo modulo p là hàm 1 chiều với các số nguyên tố p thích hợp. + Mô tả bài toán logarithm rời rạc trong Zp. Cho I = (p, , ) trong đó p là số nguyên tố, α Zp là phần từ nguyên thuỷ, β Z*p. Bài toán đặt ra là: Hãy tìm 1 số nguyên duy nhất a, 0 ≤ a ≤ p - 2 sao cho: a α ≡β(mod p); ta sẽ kí hiệu a= logα . + Định nghĩa hệ mật: Cho p là số nguyên tố sao cho bài toán logarithm rời rạc trong Zp là khó giải. Và α Z*p là phần tử nguyên thuỷ. Giá sử P = Z*p, C=Z*pxZ*p .Ta định nghĩa: K = {(p, , a, β): β ≡ αa (mod p)} Các giá trị p, α,β đƣợc công khai, còn a là bí mật. Với k = (p, α, a, β) và một số ngẫu nhiên bí mật k’ Zp-1, ta xác định: ek(x, k) = (y1,y2); trong đó: k' y1 = α mod p Hoàng Văn Hiệp - CT1301 16
  17. Đồ án tốt nghiệp Trƣờng ĐHDL Hải Phòng k' y2 = xβ mod p. a -1 và với y1 , y2 Z*p, ta xác định: dk (y1, y2) = y2 (y 1) mod p + Ví dụ: Cho p = 2579, α = 2, a =765. Khi đó: β = 2765 mod 2579 =949 Bây giờ Alice muốn gừi thông báo x = 1299 tới Bob. Giả sử Alice chọn số ngẫu nhiên bí mật k’ = 853. Sau đó cô tính: 853 y1 = 2 mod 2579 = 435 853 y2 = 1299.949 mod 2579 =2396 Và cô gửi (435, 2396) trên kênh cho Bob. Khi Bob nhận đƣợc bản mã y = (435, 2396), anh ta tính: x = 2396 x (435765)-1 mod 2579 = 1299 Và đây là bản rõ mà Alice đã mã hoá trƣớc khi gửi cho Bob. Nhƣ vậy, đối với hệ mật này thì độ dài của bản mã gấp đôi độ dài của bản rõ, thành phần bản mã phụ thuộc vào việc chọn ngẫu nhiên số k, việc chọn này làm tăng độ bí mật, nhƣng lại không ảnh hƣởng gì đến quá trình giải mã, do vậy ứng với một bản rõ có thể có nhiều bản mã khác nhau, phụ thuộc vào k khác nhau. Ta cũng thấy ràng y1 không liên quan đến bản rõ vì toàn bộ thông tin liên quan đến bản rõ nằm trong y2 .Nhƣng y1 lại cho biết thông tin cần thiết về k và việc giữ bí mật số k là rất quan trọng vì biết k’ thì có thể tính đƣợc khoá bí mật a. Hoàng Văn Hiệp - CT1301 17
  18. Đồ án tốt nghiệp Trƣờng ĐHDL Hải Phòng CHƢƠNG 2: CHỮ KÝ SỐ 2.1. Giới thiệu Khái niệm về chữ ký đã khá quen thuộc trong đời sống hàng ngày .Chữ ký đƣợc sử dụng hàng ngày để viết thƣ, rút tiền ở nhà băng, ký hợp đồng, Chữ ký viết tay thông thƣờng trên tài liệu dùng để xác nhận một ngƣời ký nó. Lƣợc đồ chữ ký số là một phƣơng pháp ký một thông điệp lƣu dƣới dạng điện tử. Ví dụ nhƣ thông điệp đƣợc ký có thể truyền trên mạng máy tính. Giữa chữ ký tay và chữ ký số có một vài điều khác nhau cơ bản. Cụ thể nhƣ sau: Với chữ ký thông thƣờng, nó là một phần vật lý của tài liệu. Đối với chữ ký số thì không gắn theo kiểu vật lý vào tài liệu mà gắn theo kiểu logic với tài liệu. Về việc kiểm tra chữ ký: Với chữ ký thông thƣờng thì kiểm tra bằng cách so sánh nó với những chữ ký xác thực khác. Ví dụ, một ngƣời ký trên một tấm séc mua hàng, ngƣời bán phải so sánh chữ ký trên mảnh giấy với chữ ký nằm ở sau thẻ tín dụng để kiểm tra. Và ta có thể thấy đây không phải là phƣơng pháp an toàn. Mặt khác, lƣợc đồ chữ ký số có thể đƣợc kiểm tra bằng cách sử dụng thuật toán kiểm thử công khai. Vì vậy bất kỳ ai cũng có thể kiểm thử chữ ký số. Việc dùng một sơ đồ chữ ký số an toàn có thể ngăn chặn đƣợc khả năng giả mạo. Còn một sự khác nhau cơ bản giữa chữ ký số và chữ ký thông thƣờng là bản sao chép của chữ ký số đồng nhất với bản gốc. Còn của chữ ký thông thƣờng có thể khác xa so với bản gốc .Điều này có nghĩa là phải cẩn thận ngăn chặn một thông điệp chữ ký số khỏi bị dùng lại. Ví dụ, nếu Bob ký bức điện số xác nhận Alice rút 100$ từ nhà băng, anh ta chỉ muốn Alice có thể làm điều đó một lần. Vì vậy, cần nghiên cứu những phƣơng pháp để ngăn chặn việc chữ ký số bị dùng lại. Một lƣợc đồ chữ ký số bao gồm 2 phần: 1 thuật toán ký và 1 thuật toán kiểm thử. Bob có thể ký trên thông điệp x bằng một thuật toán ký an toàn. Kết quả của việc ký sig(x) có thể đƣợc kiểm thử bằng thuật toán công khai. Khi đƣa 1 cặp (x,y), thuật toán kiểm thử trả lại câu trả lời là "True" hoặc "False" phụ thuộc vào việc chữ ký số là xác thực hay không xác thực. Hoàng Văn Hiệp - CT1301 19
  19. Đồ án tốt nghiệp Trƣờng ĐHDL Hải Phòng 2.2. Định nghĩa lƣợc đồ chữ ký số: Một lƣợc đồ chữ ký số là một bộ năm phần tử (P, A, K, S, V) thoả mãn các điều kiện dƣới đây: K: không gian khoá, là tập hữu hạn các khoá có thể. Với mỗi k thuộc K, có một thuật toán ký sigk S và thuật toán kiểm thử tƣơng ứng verk V Mỗi sigk : P→ A và verk : P x A →{True, False} là những hàm sao cho mỗi bức điện x P và mỗi chữ ký y A thoả mãn ver(x,y) = True , nếu y = sig(x) False, nếu y ≠ sig(x) Với mỗi khoá k K. hàm sigk và verk là hàm có thời gian tính toán đa thức, verk sẽ là hàm công khai và sigk là hàm bí mật. Điều đó có nghĩa là với x cho trƣớc, chỉ có Bob mới tính đƣợc chữ ký y để ver(x,y) = True. Lƣợc đồ chữ ký số không thể an toàn mà không có điều kiện vì Oscar có thể kiểm tra tất cả chữ ký số y có thể trên thông điệp x bằng thuật toán công khai ver cho đến khi tìm đƣợc chữ ký đúng. Vì thế nếu có đủ thời gian, Oscar sẽ luôn luôn có thể giả mạo đƣợc chữ ký của Bob. Cũng giống nhƣ hệ thống mật mã công khai, mục đích của chúng ta là tìm các lƣợc đồ chữ ký an toàn về mặt tính toán. Chú ý rằng, ai đó có thể giả mạo chữ ký của Bob trên 1 bức điện ngẫu nhiên x bằng cách tính x = ek(y) với y nào đó; khi đó y = sigk(x). Một biện pháp xung quanh vấn đề khó khăn này là yêu cầu các thông điệp chứa đủ phần dƣ thừa để chữ ký giả mạo kiểu này không tƣơng ứng với bức điện đầy đủ x trừ một xác suất rất nhỏ. 2.3. Một số lƣợc đồ chữ ký số Trong phần này ta sẽ nghiên cứu một số lƣợc đồ chữ ký số tốt, đứng vững trƣớc các kiểu tấn công trong thời gian qua. 2.3.1. Lược đồ chữ ký RSA Lƣợc đồ chữ ký số RSA đƣợc định nghĩa nhƣ sau: Cho n = p.q, p và q là các số nguyên tố lớn khác nhau. Cho P = A = Zn và định nghĩa: K = { (n, p, q, a, b): ab ≡ l(mod ϕ(n)) } Các giá trị n, b là công khai; a, p, q là bí mật. Hoàng Văn Hiệp - CT1301 20
  20. Đồ án tốt nghiệp Trƣờng ĐHDL Hải Phòng Với k = (n, p, q, a, b), ta định nghĩa: a sigk(x) = x mod n b và verk(x,y) = True x ≡ y (mod n) ; x,y Zn Kết hợp chữ ký với mã hoá sẽ làm cho độ an toàn của chữ ký tăng thêm. Giả sử rằng, Alice sẽ tính chữ ký của cô ta là y = sigAlice(x), và sau đó mã hóa cả x và y bằng cách sử dụng mật mã công khai eBob của Bob, khi đó cô ta nhận đƣợc z = eBob(x,y). Bản mã z sẽ đƣợc truyền tới Bob. Khi Bob nhận đƣợc z, việc trƣớc tiên là anh ta giải mã bằng hàm dBob để nhận đƣợc (x,y). Sau đó anh ta sử dụng hàm kiểm thử công khai của Alice để kiểm tra xem liệu verAlice(x,y) = True hay không? Nếu Alice mã hoá x trƣớc rồi sau đó mới ký lên bản mã đã đƣợc mã hóa thì sao? Khi đó cô ta tính: y = sigAlice(eBob(x)) Alice sẽ truyền cặp (z,y) cho Bob. Bob sẽ giải mã z, nhận đƣợc x và kiểm tra chữ ký y trên z bằng cách sử dụng verAlice. Một vấn đề tiềm ẩn trong biện pháp này là nếu Oscar có đƣợc cặp (z,y) kiểu này, anh ta có thể thay thế chữ ký y của Alice bằng chữ ký của anh ta: ' y = sigOscar(eBob(x)) Chú ý rằng Oscar có thể ký bản mã eBob(x) ngay cả khi anh ta không biết bản rõ x. Khi đó, nếu Oscar truyền (z,y ) tới Bob, chữ ký của Oscar sẽ đƣợc kiểm thử vì Bob sử dụng verOscar và Bob có thể suy ra rằng bản rõ x xuất phát từ Oscar. Điều này cũng làm cho ngƣời sử dụng hiểu rằng nên ký trƣớc rồi sau đó mới tiến hành mã hoá. Ví dụ: Giá sử Bob dùng lƣợc đồ chữ ký số RSA với n = 143 (p = 1 1, q = 1 3); ϕ(n) =120. Khoá công khai của Bob là b=7 => a = 7-1 mod 120=103. Bob có thông báo là x = 110 khi đó Bob sẽ ký trên thông báo x: y = xa mod n = 110103 mod 143 = 33 Bod gửi y=33 và x=l10 cho Alice. Alice sẽ kiểm thử bằng cách sử dụng khoá công khai của Bob nhƣ sau: Hoàng Văn Hiệp - CT1301 21
  21. Đồ án tốt nghiệp Trƣờng ĐHDL Hải Phòng yb mod n = 337 mod 143 = 110 = X Và Alice chấp nhận y=33 là chữ ký hợp lệ. 2.3.2. Lược đồ chữ ký Elgamal Lƣợc đồ Elgamal đã đƣợc Viện tiêu chuẩn và Công nghệ quốc gia Mỹ sửa đổi thành chuẩn chữ ký số .Lƣợc đồ Elgamal không tất định cũng giống nhƣ hệ thống mã khoá công khai Elgamal. Điều này có nghĩa là, có nhiều chữ ký hợp lệ cho một thông điệp bất kỳ. Thuật toán kiểm thử phải có khả năng chấp nhận bất kỳ chữ ký hợp lệ nào khi xác minh. Lƣợc đồ Elgamal đƣợc định nghĩa nhƣ sau: + Cho p là số nguyên tố sao cho bài toán log rời rạc trên Zp là khó và giả sử a Zp là phân tử nguyên thuỷ. Cho P = Zp,A = Z*pxZp-1 và định nghĩa: K = { (p, , a, ): ≡ αa (mod p) } giá trị p, α, β là công khai; a là bí mật. + Với k= (p, α, a, β) và một số ngẫu nhiên bí mật k’ Z*p- 1,định nghĩa: k sigk(x,k’) = ( , ), trong đó: = α mod p = (x- a )k’-l mod (p - 1) + Với x, y Z*p và Z*p-1, là định nghĩa: ver(x, , ) = True khi và chỉ khi βy ≡αx (mod p) Chứng minh: Nếu chữ ký đƣợc thiết lập đúng thi kiểm tra sẽ thành công vì: β = aa ak (mod p) ≡ αx (mod p) (vì a + k = x (mod p - 1)) Bob tính chữ ký bằng cách dùng cả giá trị bí mật a (là một phần của khoá) lẫn số ngẫu nhiên bí mật k' (dùng để ký trên x). Việc kiểm thử có thể thực hiện duy nhất bằng thông tin công khai. Vídụ: Giá sử p = 467; = 2; a = 127 →β = αa mod p = 2127 mod 467 = 132 →Giá sử Bob có thông điệp x = 100, Bob chọn ngẫu nhiên k’=213 vì (213, 466) =1 và 213-1 mod 466 = 431 Hoàng Văn Hiệp - CT1301 22
  22. Đồ án tốt nghiệp Trƣờng ĐHDL Hải Phòng -» Bob ký trên x nhƣ sau: y = αk mod p = 2213 mod 467 = 29 và = (x - a )k’-1 mod (p - 1) = (100 - 127). 431 mod 4=51 Bất kỳ ngƣời nào đó cũng có thể kiểm tra chữ ký này bằng cách: 13229 2951 ≡ 189 (mod 467) 2100 ≡ 189 (mod 467) Do đó chữ ký là hợp lệ Xét độ an toàn của lƣợc đồ chữ ký Elgamal. Giá sử Oscar thử giá mạo chữ ký trên bức diện x cho trƣớc mà không biết a. Nếu Oscar chọn giá trị và thử tìm tƣơng ứng, anh ta phải tính log rời rạc của log αx β- . Mặt khác, nếu anh ta chọn trƣớc và sau đó thử tìm thì anh ta phải giải phƣơng trình β ≡αx (mod p), trong đó là ẩn số. Bài toán này chƣa có lời giải, tuy nhiên dƣờng nhƣ nó liên quan đến bài toán đã nghiên cứu. Vẫn còn có khả năng là tìm và đồng thời để ( , ) là chữ ký. Hiện thời không ai tìm đƣợc cách giải song cũng không ai khẳng định đƣợc là nó không có lời giải. Nếu Oscar chọn và và sau đó thử giải để tìm x, anh ta sẽ phải tính bài toán logarit rời rạc, tức phải tính log β . Vì thế Oscar không thể ký một thông điệp ngẫu nhiên bằng cách này .Tuy nhiên có một cách để Oscar ký lên thông điệp ngẫu nhiên bằng việc chọn , và x đồng thời: Giả thiết i và j là các số nguvên 0 ≤ i ≤ p - 2 ; 0 ≤ j ≤ p - 2 và (j, p -1) = 1 Khi đó thực hiện các phép tính: = αi βj mod p = - yj -1 mod (p - 1) x = i j-1 mod (p - 1) = i mod (p-1) trong đó j-1 đƣợc tính theo module (p - 1). Ta thấy rằng ( , ) là chữ ký hợp lệ của x. Điều này đƣợc chứng minh qua việc kiểm tra: βyy£ ≡β- (αiβj)- 1j-1 mod p = βyα-ij-1y β-y (mod p) = α- ij-1 (mod p) Hoàng Văn Hiệp - CT1301 23
  23. Đồ án tốt nghiệp Trƣờng ĐHDL Hải Phòng =αx (mod p) Ví dụ: p = 467; = 2; = 123. Giả sử Oscar chọn i = 99; j = 179, khi đó j-1mod (p - 1) = 151. Anh ta tính: = 299 132179 mod 467= 177 = -177 x 151 mod 466 = 41 x = 99 x 41 mod 466 = 331 Và (117, 41) là chữ ký trên x= 331 Kiểm thử: 132117 11741 ≡ 303 (mod 467) và 2331 ≡ 303 (mod 467) Do đó chữ ký là hợp lệ Oscar có thể giả mạo chữ ký theo kiểu khác là bắt đầu từ thông điệp x đã đƣợc Bob ký. Giả sử ( , ) là chữ ký hợp lệ trên x. Khi đó Oscar có khả năng ký lên nhiều thông điệp khác nhau. Giá sử i, j, h là các số nguyên; 0≤h; i; j ≤ p -2 và (h - j , p-1) = 1. Thực hiện các phép tính: = h i j mod p µ = (h - j ) mod(p- 1) x = (hx +i ) (h - j )-1 mod(p - 1) trong đó (h - j )-1 đƣợc tính theo module (p - 1) Kiểm thử: β µ ≡αx mod(p) ( ,µ) là chữ ký hợp lệ của x. Cả hai phƣơng pháp trên đều tạo các chữ ký giả mạo hợp lệ song không xuất hiện khả năng đối phƣơng giả mạo chữ ký trên thông điệp có lựa chọn của chính họ mà không phải giải bài toán logarit rời rạc. Vì thế không có gì nguy hiểm về độ an toàn của lƣợc đồ Elgamal. Một vài sơ xuất để phá lƣợc đồ Elgamal: 1) Lộ k’ giải phƣơng trình đồng dƣ tuvến tính: a=(x-k’ ) mod (p-1) để tìm a. Nghiệm nào thoả mãn β= a mod p thì đó là giá trị đúng. Khi biết a thì Oscar dễ dàng giả mạo chữ ký. Hoàng Văn Hiệp - CT1301 24
  24. Đồ án tốt nghiệp Trƣờng ĐHDL Hải Phòng 2) Dùng một k' để ký hai thông điệp khác nhau. Giá sử ( , 1) là chữ ký trên xl; ( , 2) là chữ ký trên x2 Khi đó: -1 1=(x1-a )k' mod (p-1) -1 2=(x2-a )k' mod (p-1) Từ đây nhận đƣợc phƣơng trình tìm k chƣa biết: k’( 1- 2)≡(x1-x2) mod (p-l) Phƣơng trình này có nghiệm vì thực sự đã có k , 1, 2, x1, x2 thoả mãn. Giải phƣơng trình đồng dƣ tuyến tính với k’ là ẩn số ta có thể tìm đƣợc d=( 1 - 2, p-1) nghiệm. Kiểm tra điều kiện ≡αk’ (mod p) để tìm 1 giá trị đúng duy nhất của k’. Sau khi có k’ ta trở về trƣờng hợp trƣớc để tìm a. Hoàng Văn Hiệp - CT1301 25
  25. Đồ án tốt nghiệp Trƣờng ĐHDL Hải Phòng CHƢƠNG 3: HÀM HASH 3.1. Chữ ký và hàm Hash 3.1.1. Đặt vấn đề Ta thấy rằng các cơ sở đồ chữ ký chỉ cho phép ký các thông báo nhỏ, thƣơng có đọ dài xấp xỉ bằng bản thân chữ ký. Trên thực tế ta cần ký các thông báo có đọ dài lớn hơn nhiều chẳng hạn nhƣ có thể là một vài Megabyte. Vậy làm thế nào có thể có đƣợc chữ ký ngắn trên một thông báo có độ dài tùy ý. Vì chữ ký điện tử phải "ký " trên từng bit của thông báo, nên muốn có chữ ký độ dài cố định trên thông báo có độ dài tùy ý thì phải rút ngắn thông báo. Trên thực tế, việc rút ngắn văn bản là không thể đƣợc. Vấn đề đặt ra là: chúng ta có thể có thể cắt thông báo x ra thành từng đoạn ký đƣợc có độ dài bằng nhau và cố định sau đó thực hiện ký trên từng đoạn và gửi từng đoạn đó đi. Nhƣng giải pháp này gặp nhiều khó khăn vì: Vì phải sử lý quá nhiều đoạn. Có thể ngƣời nhận sẽ không sắp xếp lại đƣợc thông báo theo đúng trật tự ban đầu. Có thể mất từng đoạn khi truyền. Giải pháp thứ 2 là dùng hàm HASH: Cho thông báo x có độ dài tùy ý và hàm HASH biến đổi thành thông báo thu gọn z=h(x) có độ dài cố định 128 bit hoặc 160 bit. Sau đó ta thực hiện ký trên trên thông báo thu gọn: Chữ ký y=sigk(z). Ta sẽ gửi cặp (x, y) nếu không cần bí mật. Còn nếu cần giữ bí mật thì ta sẽ mã hóa thông báo x thành x' và gửi (x', y). Nhƣ vậy hàm HASH đã làm nhiệm vụ biến một thông báo x có độ dài bất kỳ thành một thông báo thu gọn có độ dài cố định và từ đó thực hiện ký trên thông báo thu gọn một cách dễ dàng và vẫn đảm bảo tính xác thực thông tin. 3.1.2. Định nghĩa hàm HASH Hàm HASH là một hàm tính toán có hiệu quả khi ánh xạ các dòng nhị phân có độ dài tùy ý thành các dòng nhị phân có độ dài cố định nào đó. Hàm HASH yếu: Một hàm HASH đƣợc gọi là yếu nếu cho một thông báo x thì về mặt tính toán Hoàng Văn Hiệp - CT1301 26
  26. Đồ án tốt nghiệp Trƣờng ĐHDL Hải Phòng không tìm ra đƣợc thông báo x'≠ x và h(x') = h(x). Hàm HASH mạnh: Một hàm HASH đƣợc gọi là mạnh nếu về mặt tính toán không tìm ra đƣợc 2 thông báo x và x' sao cho x'≠ x và h(x') =h(x). Hàm HASH có tính chất một chiều: Hàm HASH có tính chất một chiều nếu cho trƣớc một thông báo rút gọn z thì về mặt tính toán không tìm ra đƣợc thông báo x sao cho h(x) = z. Nhƣ vậy hàm HASH có tính chất nhƣ sau: Có thể tác động lên một khối dữ liệu có kích thƣớc tùy ý và sản sinh một đầu ra có kích thƣớc cố định. Có thể dễ dàng sản sinh ra bản tóm tắt đối với một thông báo bất kỳ. Tƣơng đối dễ tính toán đối với một x bất kỳ khi thực hiện trên cả phần cứng cũng nhƣ phần mềm. Từ mã cho trƣớc không thể sản sinh ra thông báo tƣơng ứng với nó qua hàm HASH. Với một x đã cho không thể tính toán y khác x sao cho h(x)= h(y). Không tìm ra một cặp (x, y) sao cho h(y)= h(x). Giải thích các tính chất trên: Ba tính chất đầu là yêu cầu cần thiết cho một ứng dụng thực tế của hàm HASH trong việc xác thực thông báo. Tính chất thứ tƣ là tính chất của hàm một chiều: Nó rất dễ dàng sản sinh ra một mã đối với một thông báo cho trƣớc nhƣng không thể sản sinh một thông báo từ mã cho trƣớc. Tính chất này rất quan trọng. Tính chất thứ năm bảo đảm rằng khi đã cho một thông báo thì không thể tính toán để tìm ra thông báo khác có cùng bản tóm tắt và do đó làm cho chữ ký số trở nên tin cậy giống nhƣ toàn bộ chữ ký lên toàn bộ thông báo. Tính chất thứ sáu chống lại kẻ giả mạo tạo ra hai bản thông báo có nội dung khác nhau, sau đó thu nhận chữ ký hợp pháp cho một thông báo dễ đƣợc chấp nhận , rồi lấy nó giả mạo lấy nó làm chữ ký cho thông báo thứ hai. Hoàng Văn Hiệp - CT1301 27
  27. Đồ án tốt nghiệp Trƣờng ĐHDL Hải Phòng 3.2. Một số hàm HASH sử dụng trong chữ ký số 3.2.1. Các hàm HASH đơn giản Tất cả các hàm HASH thực hiện sử dụng nguyên tắc chung dƣới đây. Đầu vào (thông điệp, file ) đƣợc biểu diễn nhƣ m khối, mỗi khối n bit. Đầu vào sử lý mỗi khối tại một thời điểm trong một kiểu lặp đi lặp lại để xây dựng một hàm HASH n bit. Một hàm HASH đơn giản nhất trong các hàm là thực hiện phép toán XOR từng bit một của mỗi khối. Nó đƣợc biểu diễn nhƣ sau: Ci= bi1 bi2 bim Trong đó: Ci là bit thứ i của mã HASH, 1≤i≤n m= số các khối đầu vào bij = bit thứ i trong khối thứ j = phép cộng modulo Hàm HASH đơn giản sử dụng phép XOR các bit bit1 bit2 bit n Khối 1 b11 b21 bn1 b12 b21 bn2 Khối m b1m b2m bnm Mã HASH C1 C2 Cn Khi thực hiện phép cộng modulo, nó sản sinh ra một bit parity đơn giản cho mỗi vị trí của từng bit và nó đƣợc biết nhƣ một sự kiểm tra ngẫu nhiên dọc theo chiều dài. Nó có tác động một cách ngẫu nhiên đến dữ liệu nhƣ một sự kiểm tra tổng thể tính toàn vẹn của dữ liệu. Hoàng Văn Hiệp - CT1301 28
  28. Đồ án tốt nghiệp Trƣờng ĐHDL Hải Phòng 3.2.2. Hàm HASH MD5: MD5 là một phiên bản mạnh hơn MD4, có một sự khác biệt quan trọng đó là MD5 sử dụng 4 vòng với 4 hàm cơ bản chứ không phải là 3 vòng với 3 hàm cơ bản nhƣ MD4. a. Giới thiệu thuật toán: Thuật toán thực hiện đầu vào là một thông điệp có độ dài bất kỳ và xây dựng một đầu ra là một thông điệp 128 bit rút gọn. Đầu vào sử lý các khối bit có độ dài 512 bit. b. Quá trình xây dựng thông điệp rút gọn thuật toán thực hiện một số bƣớc sau: Bƣớc 1: Mở rộng và gắn thêm các bit Thông diệp đƣợc chèn thêm sao cho độ dài là một chuỗi các bit đồng dƣ với 448 modulo 512 (độ dài ≡448 mod 512). Các bit đƣợc thêm vào không làm thay đổi nội dung của thông điệp đó là các số 0. Bƣớc 2 : Mở rộng độ dài Một thông điệp nguyên thủy là một chuỗi các bit có đại diện 64 bit( trƣớc khi gắn vào ) thì sẽ đƣợc mở rộng sao cho nó phải phù hợp với kết quả của bƣớc 1. Nếu độ dài nguyên thủy lớn hơn 264 bit thấp sẽ đƣợc sử dụng. Kết quả đầu tiên của hai bƣớc đầu có hiệu quả cao ta đƣợc một thông điệp là một số nguyên nhân với 512 bit độ dài. Thông điệp mở rộng sẽ đƣa ra một chuỗi các khối 512 bit Y0, Y1, , YL-1 , vì vậy độ dài của thông điệp sẽ là L x 512 bit. Tƣơng tự, kết quả là tích của 16 từ có độ dài 32 bit. Trong đó M[ 0 N-1] biểu diễn các từ của kết quả thông điệp, với N là một số nguyên và N= L*16. Bƣớc 3: Giá trị ban đầu( khởi nguồn ) của bộ đệm MD Bộ đệm 128 bit đƣợc sử dụng để lƣu trữ trực tiếp và kết quả cuối cùng của hàm HASH. Bộ đệm đƣợc thể hiện là 4 thanh ghi 32 bit( A, B, C, D). Các thanh ghi này đƣợc nhận giá trị ban đầu là các giá trị thập lục phân dƣới đây: A=0x01234567 B=0x89abcdef C=0xfedcba98 D=0x76543210 Hoàng Văn Hiệp - CT1301 29
  29. Đồ án tốt nghiệp Trƣờng ĐHDL Hải Phòng Bƣớc 4: Xử lý thông điệp trong các khối 512 bit( 16 từ). Trái tim của thuật toán là module nó bao gồm 4 vòng" 4 rounds" của quá trình xử lý. Mỗi module đƣợc đặt một nhãn HMD5, chúng đƣợc thể hiện theo mô hình sau: Mô hình tổng quát thông điệp rút gọn sử dụng MD5. Bốn vòng có cấu trúc nhƣ nhau, nhƣng mỗi vòng sử dụng hàm logic nguyên thủy khác nhau, nhƣ các hàm F, G, H và I đƣợc mô tả chi tiết dƣới đây. Trong mô hình dƣới đây 4 vòng là các nhãn fF, fG, fH, fI, các nhãn này chỉ ra rằng mỗi vòng có chức năng cấu trúc tổng quát là nhƣ nhau, nhƣng f phụ thuộc vào các hàm nguyên thủy( F, G, H, I). Hoàng Văn Hiệp - CT1301 30
  30. Đồ án tốt nghiệp Trƣờng ĐHDL Hải Phòng Mô hình biểu diễn công việc sử lý các khối đơn 512 bit(HMD5): Chú ý mỗi vòng thực hiện nhƣ đầu vào một khối hiện tại 512 bit đƣợc sử lý (Yq) và bộ đệm 128 bit co giá trị ABCD và cập nhật nội dung của bộ đệm. Mỗi vòng tạo ra sử dụng 1/4 của bộ table 64 phần tử T[1 64] đƣợc xây dựng từ hàm sine. Phần tử thứ i của T là T[i] có giá trị bằng một phần của số nguyên 232x abs(sin(i)), trong đó i tính bằng radians. Khi abs(sin(i)) là một số nằm giữa 0 và 1, thì mỗi phần tử của T là một số nguyên có thể biểu diễn trong 32 bit. Trong bảng xây dựng một cách ngẫu nhiên một cặp các mẫu 32 bit, cái loại ra một số tính hợp thức trong dữ liệu vào. Hoàng Văn Hiệp - CT1301 31
  31. Đồ án tốt nghiệp Trƣờng ĐHDL Hải Phòng Bảng dƣới đây là giá trị của T. T[1]=D76AA478 T[17]=F61E5265 T[33]=FFFA3942 T[49]=F4292244 T[2]=E8C7B756 T[18]=C040B340 T[34]=8771F681 T[50]=432AFF97 T[3]=242070DB T[19]=265E5A51 T[35]=69D96122 T[51]=AB9423A7 T[4]=C1BDCEEE T[20]=E9B6C7AA T[36]=FDE5380C T[52]=FC93A039 T[5]=F57COFAF T[21]=D62F105D T[37]=A4BEEA44 T[53]=655B59C3 T[6]=4787C62A T[22]=02441453 T[38]=4ADFCFA9 T[54]=8F0CCC92 T[7]=A8304613 T[23]=D8A1E681 T[39]=F6BB4B60 T[55]=FFEFF47D T[8]=FD469501 T[24]=E7D3FBC8 T[40]=BEBFBC70 T[56]=85845DD1 T[9]=698098D8 T[25]=21E1CDE6 T[41]=28987EC6 T[57]=6FA87E4F T[10]=8B44F7AF T[26]=C33707D6 T[42]=EAA127FA T[58]=FE2CE6E0 T[11]=FFFF5BB1 T[27]=F4D50D87 T[43]=DAEF3085 T[59]=A3014314 T[12]=895CD7EB T[28]=455A14ED T[44]=04881D05 T[60]=AE0811A1 T[13]=6B901122 T[29]=A9E3E905 T[45]=D4D9D039 T[61]=F7537E82 T[14]=FD987193 T[30]=FCEFA3F8 T[46]=6EDB99E5 T[62]=BD3AF235 T[15]=A679438E T[31]=676F02D9 T[47]=1FA27CF8 T[63]=2AD7D2BB T[16]=49B40821 T[32]=8D2A4C8A T[48]=C4AC5665 T[64]=EB86D391 Bƣớc 5: Đầu ra Sau khi tất cả L khối 512 bit đã đƣợc sử lý, thì đầu ra từ tầng thứ L là thông điệp 128 bit rút gọn. Chúng ta nghiên cứu chi tiết hơn việc sử lý mức logic trong 4 vòng của mỗi khối 512 bit. Mỗi vòng bao gồm một chuỗi 16 bƣớc xử lý trên bộ đệm ABCD. Mỗi bƣớc là một nguyên mẫu thể hiện dƣới đây: a<- b+ CLSs (a+ g(b,c,d) + X[k] + T[i]) Hoàng Văn Hiệp - CT1301 32
  32. Đồ án tốt nghiệp Trƣờng ĐHDL Hải Phòng Trong đó: a,b,c,d = 4 từ của bộ đệm, đƣợc chỉ rõ trật tự qua mỗi bƣớc nhẩy. g = là một trong 4 hàm nguyên thủy F, G, H, I CLSs =quay vòng dịch trái của 32 bit argument bởi s bit. Round Primitive functions g G(b,c,d) fF F(b,c,d) (b.c) v ((~b).d) fG G(b,c,d) (b.d) v (c.(~d)) fH H(b,c,d) b c d fI I(b,c,d) c (b.(~d)) Các phép toán logic (AND, OR, NOT, XOR) đƣợc biểu diễn bằng các biểu tƣợng (., v, ~, ). Hàm F là hàm điều kiện: if b then c else d. Tƣơng tự, G có thể đƣợc xác định if d then b else c. Hàm H xây dựng bit kiểm tra chẵn lẻ. Bảng IIIa là bảng chân lý của 4 hàm. b c d F G H I 0 0 0 0 0 0 1 0 0 1 1 0 1 0 0 1 0 0 1 1 0 0 1 1 1 0 0 1 1 0 0 0 0 1 1 1 0 1 0 1 0 1 1 1 0 1 1 0 0 1 1 1 1 1 1 0 Hoàng Văn Hiệp - CT1301 33
  33. Đồ án tốt nghiệp Trƣờng ĐHDL Hải Phòng c. Thuật toán MD5 /* Process each 16 word( 512-bit) block*/ For q = 0 to (N/16) - 1 do /* Copy block i into X*/ For j=0 to 15 do Set X[j] to M[q*16+j] end/*of loop on*/ /* Save A as AA, B as BB, C as CC and D as DD*/ AA =A BB = B CC = C DD= D /* Round 1*/ /* Let [abcd k s i] denote the operation a=b+((a + F(b,c,d) + X[k] + T[i] <<<s) Do the following 16 operations.*/ [ABCD 0 7 1] [DABC 1 12 2] [CDAB 2 17 3] [BCDA 3 22 4] [ABCD 4 7 5] [DABC 5 12 6] [CDAB 6 17 7] [BCDA 7 22 8] [ABCD 8 7 9] [DABC 9 12 10] [CDAB 10 17 11] Hoàng Văn Hiệp - CT1301 34
  34. Đồ án tốt nghiệp Trƣờng ĐHDL Hải Phòng [BCDA 11 22 12] [ABCD 12 7 13] [DABC 13 12 14] [CDAB 14 17 15] [BCDA 15 22 16] /* Round 2*/ /* Let [abcd k s i] denote the operation a=b+((a + G(b,c,d) + X[k] + T[i] <<<s) Do the following 16 operations.*/ [ABCD 1 5 17] [DABC 6 9 18] [CDAB 11 14 19] [BCDA 0 20 20] [ABCD 5 5 21] [DABC 10 9 22] [CDAB 15 14 23] [BCDA 4 20 24] [ABCD 9 5 25] [DABC 14 9 26] [CDAB 3 14 27] [BCDA 8 20 28] [ABCD 13 5 29] [DABC 2 9 30] [CDAB 7 14 31] [BCDA 12 20 32] /* Round 3*/ Hoàng Văn Hiệp - CT1301 35
  35. Đồ án tốt nghiệp Trƣờng ĐHDL Hải Phòng /* Let [abcd k s i] denote the operation a=b+((a + H(b,c,d) + X[k] + T[i] <<<s) Do the following 16 operations.*/ [ABCD 5 4 33] [DABC 8 11 34] [CDAB 11 16 35] [BCDA 14 23 36] [ABCD 1 4 37] [DABC 4 11 38] [CDAB 7 16 39] [BCDA 10 23 40] [ABCD 13 4 41] [DABC 0 11 42] [CDAB 3 16 43] [BCDA 6 23 44] [ABCD 9 4 45] [DABC 12 11 46] [CDAB 15 16 47] [BCDA 2 23 48] /*Round 4*/ /* Let [abcd k s i] denote the operation a=b+((a + I(b,c,d) + X[k] + T[i] <<<s) Do the following 16 operations.*/ [ABCD 0 6 49] [DABC 7 10 50] [CDAB 14 15 51] [BCDA 5 21 52] Hoàng Văn Hiệp - CT1301 36
  36. Đồ án tốt nghiệp Trƣờng ĐHDL Hải Phòng [ABCD 12 6 53] [DABC 3 10 54] [CDAB 10 15 55] [BCDA 1 21 56] [ABCD 8 6 57] [DABC 15 10 58] [CDAB 6 15 59] [BCDA 13 21 60] [ABCD 4 6 61] [DABC 11 10 62] [CDAB 14 15 63] [BCDA 5 21 64] /* then increment it of four registers by the value it had before this block was started.*/ A = A + AA B= B + BB C = C + CC D = D + DD end./* of loop on q*/ d. Sức mạnh của MD5 Thuật toán MD5 có tính chất mỗi bit của mã hàm băm là một hàm của các bit đầu vào. Sự lặp lại phức tạp của 4 hàm cơ bản ( F, G, H, I) tạo ra kết quả có sự hòa lẫn rất mạnh, do vậy mà nó không dễ dàng có hai thông điệp lựa chọn ngẫu nhiên thậm chí chúng có cùng nội dung tổng quát mà có cùng một mã Hash nhƣ nhau. Theo Rivest phỏng đoán trong RFC thì MD5 rất mạnh trong 128 bit mã băm, rất khó khăn trong việc xây dựng hai thông điệp có cùng một thông điệp rút gọn trong trật tự của 264 toán hạng, bên cạnh đó cũng rất khó tìm ra một thông điệp với một điểm rút gọn trong trật tự 2128 toán hạng. Cho đến nay chƣa có một phân tích nào bác bỏ các nhận định trên. Tuy nhiên khi sử dụng các phân tích bí mật( cryptalalysis) khác nhau có thể trong thời điểm Hoàng Văn Hiệp - CT1301 37
  37. Đồ án tốt nghiệp Trƣờng ĐHDL Hải Phòng phù hợp sẽ tìm ra hai thông điệp mà cùng đƣa ra một rút gọn giống nhau trong một vòng đơn MD5. Hàm Hash MD5 là một trong các hàm Hash mạnh và chƣa thể tìm ra đƣợc trong thời điểm hiện nay. Hàm MD5 đã sử dụng một số hàm rất phức tạp trong 4 vòng và chƣa tìm ra đụng độ trên các hàm này. Tuy nhiên, hàm MD5 chạy chậm hơn MD4 khoảng 30%(0.9Mbytes / sec) nhƣng nó đƣợc coi là mạnh nhất hiện nay. MD5 đƣợc phát triển và kế thừa từ MD4 do vậy về cơ bản thì MD5 có nhiều nét đặc trƣng tƣơng tự nhƣ MD4. Hoàng Văn Hiệp - CT1301 38
  38. Đồ án tốt nghiệp Trƣờng ĐHDL Hải Phòng CHƢƠNG 4: CHỮ KÝ CHỐNG CHỐI BỎ 4.1. Giới thiệu Các chữ ký chống chối bỏ do Chaum và Antwerpen đƣa ra từ năm 1989. So với những chữ ký số khác chúng có một vài đặc điểm mới. Đặc điểm khác biệt nhất trong các chữ ký này là chữ ký không thể xác minh đƣợc nếu không có sự hợp tác của ngƣời ký là Bob. Nhƣ vậy, điều này sẽ bảo vệ đƣợc Bob trƣớc khả năng các tài liệu đƣợc anh ta ký bị nhân bản và đƣợc phân phối bằng phƣơng pháp điện tử mà không có sự đồng ý của anh ta. Tuy nhiên, liệu có cần sự hợp tác của Bob để xác minh chữ ký không? ( điều này nhằm ngăn chặn việc Bob từ chối nhận đã ký thông báo trƣớc đó). Bob có thể tuyên bố một chữ ký hợp lệ là giả mạo và từ chối xác minh nó, hoặc thực hiện giao thức theo cách để chữ ký không thể đƣợc xác minh. Để ngăn chặn tình huống này xảy ra, sơ đồ chữ ký chống chối bỏ đã kết hợp giao thức từ chối( theo giao thức này Bob có thể chứng minh chữ ký là giả mạo. Nhƣ vậy, Bob có khả năng chứng minh trƣớc tòa rằng chữ ký bị lừa dối trên thực tế là giả mạo.(Nếu anh ta không chấp nhận tham gia vào giao thức từ chối thì điều này đƣợc xem nhƣ là bằng chứng chứng tỏ chữ ký trên thực tế là thật và anh ta đang cố gắng từ chối chữ ký của mình). Nhƣ vậy sơ đồ chữ ký chống chối bỏ gồm 3 thành phần: thuật toán ký, giao thức xác minh và giao thức từ chối. Ta có thể xét hai ví dụ sau: Ví dụ 1: Một khách hàng A muốn truy nhập đến một miền bí mật đƣợc giám sát bởi khách hàng B, B yêu cầu A ký một lần vào văn bản trƣớc khi truy nhập. Nếu A sử dụng chữ ký không chối bỏ đƣợc thì B không thể chứng minh( sau đó) với mọi ngƣời là A đã sử dụng tài liệu này mà không có sự tham gia trực tiếp của B trong quá trình xác minh chữ ký. Ví dụ 2: Giả sử rằng một vài công ty lớn A nào đó tạo một sản phẩm phần mềm. A ký vào sản phẩm và bán cho B, ngƣời có ý định tạo ra một bản sao của sản phẩm này và bán lại cho C. C không thể xác minh tác giả của sản phẩm phần mềm đó mà không có sự hợp tác của A. Tất nhiên, điều này không ngăn chặn đƣợc B ký lại lên sản phẩm với chữ ký riêng nhƣng với sự hợp tác của A thì dễ dàng lần ra dấu vết hành động của B. Hoàng Văn Hiệp - CT1301 39
  39. Đồ án tốt nghiệp Trƣờng ĐHDL Hải Phòng 4.2. Sơ đồ chữ ký chống chối bỏ. 4.2.1. Thuật toán ký Cho p = 2q+1 là một số nguyên tố sao cho q là số nguyên tố và bài toán logarithm rời rạc trong Zp là không giải đƣợc. * a Giả sử Z p là phần tử bậc q. Cho 1≤a≤q-1 và định nghĩa = mod p. * Giả sử G biểu thị nhóm con nhân bậc q của Z p (G gồm các thặng dƣ bậc hai modulo p). Cho P=A=G và định nghĩa K={(p, ,a, ): = amod p} Trong đó: các giá trị p, , là công khai; a là bí mật. Với k=(p, ,a, ) và x ϵ G, định nghĩa: a y=sigk(x)= x mod p và y là chữ ký trên văn bản x; 4.2.2. Thuật toán xác minh: Với x,y ϵ G, việc xác minh đƣợc thực hiện nhƣ sau: * 1. Alice chọn ngẫu nhiên e1,e2 Z p 2. Alice tính c = ye1 e2 mod p và gửi nó cho Bob 3. Bob tính d = ca-1mod q mod p và gửi nó cho Alice. 4. Alice chấp nhận y là chữ ký hợp lệ khi và chỉ khi: d≡ xe1 e2 mod p 4.2.3. Giao thức từ chối: * 1. Alice chọn ngẫu nhiên e1, e2 Z p 2. Alice tính c= ye1 e2 mod p và gửi nó cho Bob 3. Bob tính d = ca-1 mod q mod p và gửi nó cho Alice. 4. Alice xác minh xem có d ≡ xe1 e2 mod p không * 5. Alice chọn ngẫu nhiên f1, f2 ϵ Z q 6. Alice tính C= yf1 f2 mod p và gửi nó cho Bob 7. Bob tính D = Ca-1 mod q mod p và gửi nó cho Alice. Hoàng Văn Hiệp - CT1301 40
  40. Đồ án tốt nghiệp Trƣờng ĐHDL Hải Phòng 8. Alice xác minh xem có D xf1 f2 mod p không 9. Alice kết luận rằng y là giả mạo khi và chỉ khi ( d -e2)f1 ≡ (D -f2)e1(mod p) * Ta xét vai trò của p và q trong sơ đồ này. Sơ đồ này tồn tại trong Z p; tuy vậy * cần có khả năng tính toán theo nhóm nhân con G của Z p có bậc nguyên tố. Đặc biệt ta cần có khả năng tính đƣợc các phần tử nghịch đảo modulo |G| - đây là lý do giải thích tại sao |G| phải là số nguyên tố. Để thuận lợi lấy p = 2q + 1, trong đó q là số nguyên tố. Trƣớc hết ta chứng minh rằng, Alice sẽ chấp nhận một chữ ký hợp lệ. Trong các tính toán sau đây, tất cả các số mũ đƣợc rút gọn theo modulo q. Đầu tiên nhận xét rằng: d≡ c -1 mod p ≡ye1a-1 e2a-1 mod p vì ≡ a mod p, ta có: a-1 ≡ (mod p) Tƣơng tự: y≡ xa mod p, ta có: ya-1≡ x(mod p) Vì thế d ≡ xe1 e2 mod p. Tiếp theo ta chứng minh rằng Bob không thể lừa Alice chấp nhận chữ ký giả mạo nhƣ một chữ ký hợp lệ ngoại trừ một xác suất rất bé. Kết quả này không phụ thuộc vào bất kỳ giả thiết tính toán nào, điều đó có nghĩa là độ an toàn là vô điều kiện. Định lý 1: nếu y xa mod p thì Alice sẽ nhận y là một chữ ký hợp lệ trên x với xác suất 1/q. Chứng minh: Trƣớc hết, nhận xét rằng mỗi yêu cầu c có thể tƣơng ứng chính xác với q cặp đƣợc sắp(e1,e2) ( đó là tại vì cả y và đều là các phần tử của nhóm nhân G có bậc nguyên tố q). Vì y= -1 mod p, = a mod p nên c = ye1 e2 = -1e1 ae2 mod p = -1e1+ae2 mod p, c cố định nên (-1e1+ae2 ) mod q = u cố định. Hoàng Văn Hiệp - CT1301 41
  41. Đồ án tốt nghiệp Trƣờng ĐHDL Hải Phòng -1 * e2 = a (u -1e1) mod q vi e1 Z q có q giá trị e1 có q cặp (e1, e2) cho cùng cùng 1 giá trị c. Bây giờ, khi Bob nhận đƣợc yêu cầu c, anh ta không có cách biết cặp đƣợc sắp (e1,e2) nào trong q cặp co thể mà Alice đã dùng để xây dựng c. Ta khẳng định, nếu y xa mod p thì đáp ứng d G mà Bob có thể tạo ra là tƣơng ứng với chính xác một trong q cặp đƣợc sắp( e1,e2). Vì sinh ra G nên ta có thể viết một phần tử bất kỳ thuộc G nhƣ một số mũ của , trong đó số mũ đƣợc xác định duy nhất theo modulo q. Vì thế có thể viết c= i j k -1 , d= , x= và y= ; với i,j,k,l Zq và mọi phép tính số học theo modulo q. Xét hai đồng dƣ thức sau: c≡ ye1 e2mod p) d≡xe1 e2(mod p) Hệ này tƣơng đƣơng với hệ đồng dƣ thức sau: i≡-le1 +ae2(mod )q j≡ke1 +e2(mod)q Bây giờ giả thiết rằng: y xa (mod p) thì ta rút ra : 1 a k(mod q). Vì thế, ma trận hệ số của hệ các đồng dƣ thức theo modulo q này có định thức khác 0 và nhƣ vậy tồn tại nghiệm duy nhất cho hệ thống. Nghĩa là, mỗi d G là một đáp ứng đúng với một trong q cặp (e1,e2) đƣợc sắp có thể. Hệ quả là xác suất để Bob đƣa cho Alice một đáp ứng d sẽ đƣợc xác minh đúng là 1/q. Bây giờ ta chứng minh hai vấn đề: 1. Bob có thể thuyết phục Alice rằng chữ ký không hợp lệ là giả mạo 2. Bob không thể làm Alice tin rằng một chữ ký tin cậy là giả mạo trừ một xác suất rất bé. Định lý 2: Nếu y xa mod p và cả Alice và Bob thực hiện theo giao thức từ chối thì(d -e2)f1 ≡ (D -f2)e1 mod p Chứng minh: Do cả Alice và Bob đều thực hiện giao thức nên ta có thể sử dụng các yếu tố: d≡ca-1 mod p Hoàng Văn Hiệp - CT1301 42
  42. Đồ án tốt nghiệp Trƣờng ĐHDL Hải Phòng c≡ye1 e2 mod p và ≡ a mod p Ta có: (d -e2)f1 ≡((ye1 e2)a-1 e-2)f1(mod p) ≡(ye1f1a-1 e2a-1f1 -e2f1(mod p)) ≡ye1f1a-1 e2f1 -e2f1 mod p ≡ye1f1a-1 mod p Tƣơng tự, dùng các yếu tố D≡Ca-1 mod p , C≡yf1 f2 mod p và ≡ a mod p, ta có: (D -f2)e1 ≡ ye1f1a-1 mod p vì thế phép kiểm tra tính phù hợp trong bƣớc 9 thành công. Bây giờ xét xác suất để Bob có thể từ chối một chữ ký hợp lệ. Trƣờng hợp này không giả thiết Bob thực hiện theo thủ tục. Nghĩa là Bob có thể không xây dựng D và d nhƣ trong giao thức. Vì thế trong định lý tiếp theo chi giả thiết rằng, Bob có thể tạo ra các D và d thỏa mãn điều kiện trong các bƣớc 4,8,9 của giao thức chối bỏ. Định lý 3: Giả sử y≡ xa mod p và Alice thực hiện theo giao thức từ chối. Nếu d xe1 e2mod p và D xf1 f2(mod p) thì xác suất để (d -e2)f1 (D -f2)e1 (mod p) là 1- 1/q. Chứng minh: Giả sử rằng các đồng dƣ thức sau đƣợc thỏa mãn y≡xa(mod p) d xe1 e2(mod p) D xf1 f2(mod p) (d -e2)f1≡ (D -f2)e1(mod p) ta sẽ đƣa đƣợc ra mâu thuẫn nhƣ sau: Trong giao thức chối bỏ, bƣớc 9 có thể viết lại nhƣ sau: f1 f2 D≡ d0 (mod p) 1/e1 -e2/e1 trong đó, d0 = d mod p là giá trị chỉ phụ thuộc vào các bƣớc từ 1-4 trong giao thức. Áp định lý 1, ta kết luận y là chữ ký hợp lệ đối với d0 với xác suất 1-1/q. a a Song ta đang giả thiết y là chữ ký hợp lệ đối với x, nghĩa là ta có x ≡d0 (mod p) với Hoàng Văn Hiệp - CT1301 43
  43. Đồ án tốt nghiệp Trƣờng ĐHDL Hải Phòng xác suất cao, điều này kéo theo là x = d0. Tuy nhiên do d xe1 e2(mod p) có nghĩa là x≡ d1/e1 -e2/e1(mod p) 1/e1 -e2/e1 Và từ biểu thức d0≡d (mod p), suy ra x≠d0 ta nhận đƣợc mâu thuẫn. Nhƣ vậy Bob co thể lừa dối Alice theo cách này với xác suất là 1/q. Ví dụ: Giả sử lấy p=467, vi 2 là phần tử nguyên thủy nên 22 = 4 là phần tử sinh của G, gồm các thặng dƣ bậc hai modulo 467. Vì thế ta có thể lấy =4. Giả thiết a = 101, Khi đó: = a mod 467=449 Bob sẽ ký thông báo x=119 với chữ ký: y =119101 mod 467 = 129 Bây giờ giả sử Alice muốn xác minh chữ ký y, cô ta chọn các số ngẫu nhiên chẳng hạn e1=38, e2=397. Cô tính c= 13 và ngay lúc đó Bob sẽ trả lời với d= 9. Alice kiểm tra câu trả lời bằng việc xác minh rằng: 119384397=9mod 467. Vì thế mà Alice chấp nhận y là chữ ký hợp lệ. Ví dụ: Giả sử p= 467, =4, a=101 và =449. Giả sử thông báo x=286 đƣợc ký với chữ ký y = 83 và Bob muốn thuyết phục Alice rằng chữ ký này không hợp lệ. Giả sử Alice bắt đầu bằng việc chọn các giá trị ngẫu nhiên e1=45, e2=237. Alice tính c=305 và Bob trả lời với d=109. Sau đó Alice tính: 246454237 mod 467=149 vì 149≠109 nên Alice thực hiện bƣớc tiếp theo là chọn các giá trị ngẫu nhiên f1=125, f2=9. Alice tính C=270 và Bob trả lời với D=68. Alice tính: 28612549mod 467=25 Vì 25≠ 68 nên Alice thực hiện bƣớc cuối cùng là kiểm tra tính phù hợp. Bƣớc kiểm tra này thành công vì: (109 x 4-237)125 ≡ 188(mod 467) và: (68 x 4-9)45 ≡ 188(mod 467) Vì thế Alice tin rằng chữ ký y trên x là không hợp lệ. Hoàng Văn Hiệp - CT1301 44
  44. Đồ án tốt nghiệp Trƣờng ĐHDL Hải Phòng CHƢƠNG 5 : ÁP DỤNG CHỮ KÝ CHỐNG CHỐI BỎ VÀO QUẢN LÝ HÀNH CHÍNH CỦA TRƢỜNG ĐẠI HỌC DÂN LẬP HẢI PHÒNG 5.1. Đặt vấn đề. Với bất kỳ một cơ quan tổ chức nào thì hệ thống quản lý hành chính đóng vai trò rất quan trọng. Trƣờng Đại Học Dân Lập Hải Phòng có cơ sở 1 tại số 36- Đƣờng dân lập-Dƣ Hàng Kênh- Lê Chân- Hải Phòng, cơ sở 2( đang xây dựng) Tại Xã Minh Tân- Kiến Thụy- Hải Phòng và khu Khách Sạn Sinh Viên. Do khoảng cách đia lý nên việc quản lý hành chính khá phức tạp và khó khăn. Trƣờng Đại Học Dân Lập Hải Phòng gồm các phòng ban, các khoa, các trung tâm nên việc ban hành các quyết định, văn bản từ Nhà trƣờng tới các phòng ban đều do bộ phận văn thƣ đảm nhiệm nên rất khó khăn và mất thời gian. Mặt khác, những yêu cầu, kiến nghị của các khoa, trung tâm muốn lấy ý kiến, chỉ thị của lãnh đạo nhà trƣờng cũng rất phức tạp. 5.2. Giải quyết vấn đề. Ngày nay với sự phát triển mạnh mẽ của công nghệ cao, công nghệ internet không còn mới mẻ đối với mọi ngƣời, việc trao đổi thông tin trên mạng trở nên phổ biến hơn. Vì vậy, giải pháp thuận lợi nhất là chuyển các quyết định, văn bản qua mạng. Tuy nhiên việc trao đổi tài liệu qua mạng không phải không có khó khăn: ví dụ trên đƣờng truyền văn bản, nghị quyết bị sửa đổi, điều này rất nguy hiểm vì đây không phải là những tài liệu thông thƣờng mà là các nghị quyết, văn bản quy chế của Nhà trƣờng. Cũng có những vấn đề khác cần giải đáp, ví dụ nhƣ văn bản đó có đáng tin không? văn bản đó có chính xác không? Chúng ta biết rằng, trong các nghị quyết, văn bản, thông thƣờng trên giấy thì bao giờ cũng kết thúc bằng chữ ký ngƣời quyết định. Đó là bằng chứng để chứng minh hiệu lực của văn bản. Nếu chữ ký bị tẩy xóa thì ta co thể nghi ngờ tài liệu đã bị sửa đổi, hoặc chữ ký là giả mạo. Nhƣng khi đã trao đổi trên mạng thì chữ ký viết tay không thể thực hiện đƣợc nhƣ trên văn bản thông thƣờng. Hiện nay có rất nhiều chữ ký điện tử đã đƣợc đem vào sử dụng trong thực tiễn. Do tính chất và đặc điểm của việc quản lý hành chính, tôi chọn chữ ký chống chối bỏ để áp dụng. Chữ ký chống chối bỏ là một chữ ký với ba giao thức: giao thức ký, giao thức kiểm thử và giao thức chối bỏ, do đó phù hợp với việc trao đổi trên mạng, hơn nữa nếu tất cả cùng áp dụng các giao thức chữ ký chống chối bỏ thì việc Hoàng Văn Hiệp - CT1301 45
  45. Đồ án tốt nghiệp Trƣờng ĐHDL Hải Phòng ban hành các quyết định có chữ ký của Nhà trƣờng hoàn toàn đáng tin cậy. Ngƣời ký muốn phủ nhận chữ ký của mình cũng không đƣợc. Hơn nữa, một ngƣời có thể chối bỏ chữ ký nếu nó không phải chữ ký của mình. Đặc biệt chữ ký chống chối bỏ cũng không thể nhân bản đƣợc. Khi sử dụng chữ ký chống chối bỏ, tất cả những ngƣời tham gia trong mạng sẽ có một số nguyên tố p, phần tử nguyên thủy và khóa trên thƣ mục công khai chung của Trƣờng và một khóa bí mật a cho riêng mình, trong đó là phần tử có * a bậc q trong Z p, p=2q + 1 (q là số nguyên tố) và = mod p. Ví dụ: Khoa Công Nghệ Thông Tin muốn gửi danh sách những sinh viên đủ điều kiện bảo vệ đồ án tốt nghiệp cho Hiệu trƣởng duyệt. Trƣớc khi gửi danh sách cho Hiệu trƣởng thì Trƣởng khoa Công Nghệ Thông Tin sẽ tiến hành việc ký nhƣ sau: 1. Ông sẽ lấy số nguyên tố p trên thƣ mục công khai và một khóa bí mật a chỉ dùng cho riêng mình. 2. Tiến hành ký trên văn bản: y=xa mod p(Ở đây x là văn bản thu đƣợc sau hai phép biến đổi thông báo cần ký là: Hash và đƣa về nhóm con G). 3. Gửi văn bản kèm theo chữ ký trên mạng. Về phía mình, Hiệu trƣởng sẽ kiểm tra lại chữ ký có đúng là của Trƣởng khoa Công Nghệ Thông Tin hay không?. Ông ta sẽ tiến hành giao thức kiểm thử cùng với sự hợp tác của Trƣởng khoa Công Nghệ Thông Tin nhƣ sau: e1 e2 1. Hiệu trƣởng lấy ngẫu nhiên hai số e1, e2 và tính c=y mod p rồi gửi lại cho Trƣởng khoa Công Nghệ Thông Tin. 2. Trƣởng khoa Công Nghệ Thông Tin sẽ tính d =a-1mod qmod p rồi gửi lại cho Hiệu trƣởng. 3. Hiệu trƣởng kiểm tra nếu d≡xe1 e2 mod p thì chấp nhận là chữ ký hợp lệ. Sau khi kiểm tra chữ ký, Hiệu trƣởng sẽ ra quyết định cho các sinh viên mà khoa Công Nghệ Thông Tin đã gửi đƣợc bảo vệ đồ án tốt nghiệp và ký vào quyết định trƣớc khi gửi cho khoa Công Nghệ Thông Tin. Khoa Công Nghệ Thông Tin cũng sẽ kiểm tra chữ ký của Hiệu trƣởng nhƣ cách thức trên. Nếu cả hai bên không có vấn đề gì thì thời gian tiến hành bảo vệ do khoa Công Nghệ Thông Tin ấn định. Nếu trong bản danh sách có sai sót gì thì ngƣời chịu trách nhiệm là Trƣởng khoa Công Nghệ Thông Tin vì danh sách đã có chữ ký của Trƣởng khoa. Tuy nhiên, Trƣởng khoa có thể tuyên bố chữ ký đó là giả mạo và từ chối xác minh nó, hoặc thực hiện giao thức theo cách để chữ ký không thể xác minh. Để ngăn chặn tình Hoàng Văn Hiệp - CT1301 46
  46. Đồ án tốt nghiệp Trƣờng ĐHDL Hải Phòng huống này, Hiệu trƣởng sẽ thực hiên giao thức từ chối. Nếu Trƣởng khoa Công Nghệ Thông Tin không chấp nhận tham gia vào giao thức từ chối thì điều này xem nhƣ chữ ký trên thực tế là thật và ông ta đang cố gắng từ chối chữ ký cua mình. Nếu Trƣởng khoa tuân thủ các bƣớc của giao thức và kết quả là việc Hiệu trƣởng kết luận chữ ký giả mạo thi ông sẽ có quyền chối bỏ chữ ký kia một cách thuyết phục. Giao thức từ chối đƣợc tiến hành nhƣ sau: * 1. Hiệu trƣởng chọn ngẫu nhiên e1, e2 Z q. 2. Hiệu trƣởng tính c = ye1 e2 mod p và gửi nó cho Trƣởng khoa CNTT. 3. Trƣởng khoa CNTT tính d= ca-1 mod q mod p và gửi nó cho Hiệu trƣởng. 4. Hiệu trƣởng xác minh xem có d xe1 e2 mod p không? * 5. Hiệu trƣởng chọn ngẫu nhiên f1, f2 Z q 6. Hiệu trƣởng tính C= yf1 f2 mod p và gửi nó cho Trƣởng khoa CNTT. 7. Trƣởng khoa CNTT tính D = Ca-1 mod q mod p và gửi nó cho Hiệu trƣởng. 8. Hiệu trƣởng xác minh xem có D xf1 f2 mod p không? 9. Hiệu trƣởng kết luận rằng y là giả mạo khi và chỉ khi (d -e2)f1 ≡(D -f2)e1 (mod p). Nhƣ vậy bằng cách sử dụng chữ ký số chống chối bỏ thì việc trao đổi các quyết định, giấy tờ rất nhanh và chính xác. Hơn nữa, tất cả các chữ ký và văn bản đều đƣợc lƣu giữ lại do đó có thể kiểm thử lại bất cứ lúc nào thấy cần thiết. Tuy nhiên, khi cài đặt lƣợc đồ chữ ký vào mạng thông tin máy tính của trƣờng tôi thấy cần nghiên cứu thêm ba vấn đề nữa: 1. Có thể Hiệu trƣởng hoặc Trƣởng khoa Công Nghệ Thông Tin bận, nếu cần ủy quyền cho ngƣời khác tham gia vào giao thức hỏi đáp, thì phải thực hiện nhƣ thế nào? 2. Cũng có trƣờng hợp, bên nhận thấy văn bản gửi cho mình có nội dung mà mình chƣa muốn thực hiện nên không tiến hành kiểm tra chữ ký và lờ đi. Vậy làm thế nào để ngăn chặn sự cố này? 3. Nghiên cứu việc lƣu trữ trên máy tính các văn bản và các chứng cứ tƣơng ứng nhƣ thế nào cho an toàn thuận tiện. Hoàng Văn Hiệp - CT1301 47
  47. Đồ án tốt nghiệp Trƣờng ĐHDL Hải Phòng CHƢƠNG 6: CHƢƠNG TRÌNH 6.1. Giải thích chƣơng trình Để cài đặt đƣợc sơ đồ chữ ký chông chối bỏ, tôi sử dụng ngôn ngữ C++ và để an toàn tôi thực trên các số cỡ lớn hệ cơ số 256. Mỗi số cỡ lớn đƣợc cài đặt nhƣ sau: độ dài các số cỡ lớn đƣợc lƣu vào một biến unsigned int và giá trị của nó lƣu trong một mảng unsigned char. Để mô phỏng chữ ký chống chối bỏ, tôi chọn số p có độ dài 19 byte và các giá trị nhƣ sau: 56 29 43 85 112 151 142 150 211 7 90 78 106 77 226 71 208 21 191. Khóa đƣợc tạo theo thủ tục sau: * 2 1. Chọn ngẫu nhiên một phần tử e Z p và tính = e mod p 2. Nếu = 1, quay lại bƣớc 1. Điều kiện để thực hiện chữ ký chống chối bỏ là x, y G.Để ký đƣợc trên các văn bản bất kỳ, tôi thực hiện nhƣ sau: 1. Tiến hành Hash văn bản gốc( giả sử là x1) theo thuật toán MD5 thành một văn bản gồm 16 byte (giả sử là m) 2. Tính x = m mod p. Và giao thức ký đƣợc tiến hành trên x để thu đƣợc chữ ký là y và y đƣợc xem nhƣ là chữ ký trên văn bản gốc. Điều này đảm bảo x, y G. Chƣơng trình đƣợc chia làm hai modun sau: 1. Tạo danh sách những ngƣời sử dụng trên mạng trong một cơ sở dữ liệu: Modun này cho phép đăng ký tham ra bằng cách nhập user name và password. 2. Tạo khóa bí mật: Trƣớc tiên, ngƣời sử dụng phải đăng nhập mạng bằng cách nhập user name và password(dạng mã hóa) của mình. Sau khi đã đăng nhập mạng thành công thì có thể tiến hành thủ tục tạo khóa với số p cho trƣớc. Khóa , sẽ đƣợc đƣa vào thƣ mục công khai, còn khóa bí mật a thì ngƣời sử dụng giữ cho riêng mình. 3. Cuối cùng là modun chứa các giao thức ký, kiểm thử và từ chối. 6.2. Các phép toán hỗ trợ a. Thuật toán cộng Input: x,y là số nguyên, mỗi số gồm n+1 chữ số hệ 256 Output: x+y = (wn+1wn w1w0) hệ 256. 1. c 0( c là số nhớ) Hoàng Văn Hiệp - CT1301 48
  48. Đồ án tốt nghiệp Trƣờng ĐHDL Hải Phòng 2. For i=0 to n do 2.1 wi (xi +yi+c) mod 256 2.2 if(xi +yi +c<256) then c 0 3. else c 1. 4. wn+1 c 5. Return (wn+1wn w1w0) b. Thuật toán trừ Input: x, y là số nguyên, mỗi số gồm n+1 chữ số hệ 256; và x≥y Output: x-y =(wn+1wn w1w0) hệ 256. 1. c 0 ( c là số nhớ) 2. For i=0 to n do a. wi (xi- yi +c) mod 256 b. if(xi -yi +c ≥0) then c 0 else c -1 3. Return (wn+1wn w1w0) c. Thuật toán nhân Input: x, y là số nguyên gồm n+1 và t+1 chữ số hệ 256; Output: x*y =(wn+1wn w1w0) 1. For i=0 to (n+t+1) do wi 0 2. For i =0 to t do 2.1. c 0 2.2. For j =0 to n do Tính (uv)256 =wi+j+ xj * yi +c; Đặt wi+j v; c u; 2.3. wi+n+1 u. 3. Return (wn+t+1 w1w0) d. Thuật toán chia Input: x=(xn x1x0)256, y= (yt y1y0) với n≥ t ≥ 1; yt ≠ 0 Output: thƣơng q= ( qn-t q1q0)256; số dƣ r = (rt r1r0)256; sao cho x = q.y +r; 0 r y. Hoàng Văn Hiệp - CT1301 49
  49. Đồ án tốt nghiệp Trƣờng ĐHDL Hải Phòng 1. For j=0 to (n-1) do qj 0 n-t n-t 2. While(x≥y.256 ) do qn-t +1; x x-y.256 3. For i=n downto (t+1) do 3.1. if xi = yt then qi-t-1 256-1 else qi-t-1 (xi.256 +xi-1)/yt 2 3.2. While (qi-t-1 (yt256+yt-1) xi256 +xi-1256+xn-2) do qi-t-1 qi-t-1-1 i-t-1 x x-qi-t-1y256 . i-t-1 3.3. While x 0 do x x+y256 ; qi-t-1 qi-t-1-1. 4. r x 5. Return (q, r) e. Thuật toán tính AB mod M Input: A,B,M là ba số nguyên hệ 256; A, B <M; Output: P= AB mod M 1. Đổi B (BnBn-1 B1B0)2; H là số chứ số của B ở hệ nhị phân 2. T H-1; D M-A 3. While (B(T) =0) do T T-1 4. P A 5. For i=T-1 downto 0 do 5.1 if(P<M) then P 2*P else P 2(P-M) 5.2 if (B(i)=1) then if (P<M) then P P+A else P P-D 6. if (P≥ M) P P-M 7. Return P. f. Thuật toán nhị phân yn mod N Input: y,n,N là ba số nguyên hệ 256; Output: b=yn mod N 1. a n ; b 1; c y; 2. if (a chẵn) then d 1; else d 0; a [a/2]; 3. if d=1 then goto 6 4. b b*c mod N 5. if (a=0) then return 0 6. c c*c mod N; goto 2; Hoàng Văn Hiệp - CT1301 50
  50. Đồ án tốt nghiệp Trƣờng ĐHDL Hải Phòng 7. Return (b); g. Thuật toán tính phần tử nghịch đảo: n-1 mod m Input: m, n là hai số nguyên hệ 256; (a1, a2, a3); (b1, b2, b3); (c1, c2, c3) là ba tập vector hệ 256. Output: y= n-1 mod m 1. (a1, a2, a3) (1, 0, m); (b1, b2, b3) (0, 1, n); 2. if(b3=0) then y=a2 ; return 0; 3. q [a3/b3] và (c1,c2, c3) (a1, a2, a3) -q(b1, b2, b3) (a1, a2, a3) (b1,b2, b3) (b1, b2, b3) (c1, c2, c3) goto 2; 4. Return (y); Hoàng Văn Hiệp - CT1301 51
  51. Đồ án tốt nghiệp Trƣờng ĐHDL Hải Phòng 6.3. Demo chƣơng trình. a. Khởi động chƣơng trình: b. Giao thức ký: Hoàng Văn Hiệp - CT1301 52
  52. Đồ án tốt nghiệp Trƣờng ĐHDL Hải Phòng c. Giao thức kiểm thử: d. Giao thức chối bỏ: Hoàng Văn Hiệp - CT1301 53
  53. Đồ án tốt nghiệp Trƣờng ĐHDL Hải Phòng KẾT LUẬN Ngày nay cùng với sự phát triển của khoa học kỹ thuật hiện đại, công nghệ thông tin đã giúp nhiều trong các lĩnh vực đời sống của con ngƣời. Mạng Internet với tốc độ nhanh, lƣợng thông tin trao đổi có thể rất lớn và đặc biệt không hạn chế ngƣời sử dụng, giúp cho con ngƣời có thể trao đổi với nhau nhanh hơn, chính xác hơn và hiệu quả hơn. Trong đồ án này em đã đi sâu tìm hiểu về lƣợc đồ chữ ký số chống chối bỏ, lƣợc đồ chữ ký ngƣời xác nhận đƣợc chỉ định và lƣợc đồ chữ ký ngƣời xác nhận không thể chối bỏ. Với lƣợc đồ chữ ký số chống chối bỏ đã giải quyết đƣợc yêu cầu của chữ ký số đó là chống sao chép không hợp pháp. Vì chữ ký số chống chối bỏ chỉ có thể kiểm tra khi có sự hợp tác của ngƣời ký thông qua giao thức hỏi- đáp. Tuy nhiên đó cũng là nhƣợc điểm của chữ ký số chống chối bỏ vì nếu trƣờng hợp ngƣời ký không hợp tác hoặc ngƣời ký cố tình không thực hiện đúng giao thức thì khả năng kiểm tra là không thể và có thể chối bỏ chữ ký đó. Tuy vậy, chữ ký số chống chối bỏ cũng là một sự lựa chọn rất hợp lý trong truyền tải dữ liệu số yêu cầu bảo mật và tính xác thực và một số ứng dụng khác. Để hoàn thành đƣợc đồ án này, tôi đã nhận đƣợc sự chỉ bảo, hƣớng dẫn tận tình của thầy giáo TS. Hồ Văn Canh. Tuy nhiên, đồ án không tránh khỏi thiếu xót, rất mong sự góp ý của các Thầy, Cô giáo. Hoàng Văn Hiệp - CT1301 54
  54. Đồ án tốt nghiệp Trƣờng ĐHDL Hải Phòng TÀI LIỆU THAM KHẢO [1] Phan Đình Diệu(2002): Lý thuyết mật mã và an toàn thông tin. NXB Đại học Quốc gia Hà Nội, 2002. [2]Nguyễn Đ. Cƣơng(2007) : Mật mã và an toàn thông tin( sách điện tử). [3]Hồ Văn Canh : Vai trò của chữ ký số chống chối bỏ trong thƣơng mại điện tử(2011). [4]Alfred J. Menezes, Paul C. van Oorschot, Scott A. Vanstone : Handboof of Applied Cryptography CRC press : Boca Raton, New York, London, Tokyo(1997). Hoàng Văn Hiệp - CT1301 55