›

Đồ án Tìm hiểu chuẩn mật mã dữ liệu (des) và ứng dụng vào thi tuyển đại học

pdf 74 trang huongle 1550
Download
Bạn đang xem 20 trang mẫu của tài liệu "Đồ án Tìm hiểu chuẩn mật mã dữ liệu (des) và ứng dụng vào thi tuyển đại học", để 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_chuan_mat_ma_du_lieu_des_va_ung_dung_vao_thi.pdf

Nội dung text: Đồ án Tìm hiểu chuẩn mật mã dữ liệu (des) và ứng dụng vào thi tuyển đại học

  1. BỘ GIÁO DỤC VÀ ĐÀO TẠO TRƢỜNG ĐẠI HỌC DÂN LẬP HẢI PHÒNG o0o ĐỒ ÁN TỐT NGHIỆP NGÀNH CÔNG NGHỆ THÔNG TIN HẢI PHÒNG 2013
  2. 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 CHUẨN MẬT MÃ DỮ LIỆU (DES) VÀ ỨNG DỤNG VÀO THI TUYỂN ĐẠI HỌC ĐỒ ÁN TỐT NGHIỆP ĐẠI HỌC HỆ CHÍNH QUY Ngành: Công nghệ Thông tin HẢI PHÒNG - 2013
  3. 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 CHUẨN MẬT MÃ DỮ LIỆU (DES) VÀ ỨNG DỤNG VÀO THI TUYỂN ĐẠI HỌC ĐỒ Á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: Đỗ Thị Phƣơng Giáo viên hƣớng dẫn: TS. Hồ Văn Canh Mã số sinh viên: 1351010046 HẢI PHÒNG - 2013
  4. BỘ GIÁO DỤC VÀ ĐÀO TẠO CỘNG HÒA XA HỘI CHỦ NGHĨA VIỆT NAM TRƢỜNG ĐẠI HỌC DÂN LẬP HẢI PHÒNG Độc lập - Tự do - Hạnh phúc o0o NHIỆM VỤ THIẾT KẾ TỐT NGHIỆP Sinh viên: Đỗ Thị Phƣơng Mã SV: 1351010046 Lớp: CT 1301 Ngành: Công nghệ Thông tin Tên đề tài: Tìm hiểu chuẩn mật mã dữ liệu (DES) và ứng dụng vào thi tuyển đại học.
  5. NHIỆM VỤ ĐỀ TÀI 1. Nội dung và các yêu cầu cần giải quyết trong nhiệm vụ đề tài tốt nghiệp a. Nội dung 1. Tìm hiểu mật mã DES. 2. Nghiên cứu bài toán chia sẻ bí mật của Lagrange. 3. Ứng dụng lƣợc đồ chia sẻ bí mật của Lagrange để phân phối khóa. 4. Demo chƣơng trình b. Các yêu cầu cần giải quyết 1. Đọc tài liệu và hiểu đƣợc vấn đề đặt ra, nắm đƣợc các phƣơng pháp mã dịch DES một cách thành thạo (cả tiếng việt và tiếng anh). 2. Hiểu đƣợc lƣợc đồ chia sẻ bí mật Lagrange. 3. Đọc hiểu đƣợc một số tài liệu chuyên môn bằng tiếng Anh 4. Nắm vững một ngôn ngữ lập trình cơ bản (Vb, C#, C++) và giải đƣợc bài toán có tính ứng dụng vào thực tiễn.
  6. Đồ án tốt nghiệp Trƣờng DHDL Hải Phòng CÁN BỘ HƢỚNG DẪN ĐỀ TÀI TỐT NGHIỆP Ngƣời hƣớng dẫn thứ nhất: Họ và tên: Hồ Thị Hƣơng Thơm Học hàm, học vị: Tiến Sĩ Cơ quan công tác: Trƣờng Đại Học Dân Lập Hải Phòng Nội dung hƣớng dẫn: Ngƣời hƣớng dẫn thứ hai: Họ và tên: . Học hàm, học vị: . Cơ quan công tác: Nội dung hƣớng dẫn: Đề tài tốt nghiệp đƣợc giao ngày tháng năm 2013 Yêu cầu phải hoàn thành trƣớc ngày tháng năm 2013 Đã nhận nhiệm vụ: Đ.T.T.N Đã nhận nhiệm vụ: Đ.T.T.N Sinh viên Cán bộ hƣớng dẫn Đ.T.T.N TS. Hồ Thị Hƣơng Thơm Hải Phòng, ngày tháng năm 2013 HIỆU TRƢỞNG GS.TS.NGƯT Trần Hữu Nghị Đỗ Thị Phƣơng- CT1301 Page 6
  7. Đồ án tốt nghiệp Trƣờng DHDL Hải Phòng PHẦN NHẬN XÉT TÓM TẮT CỦA CÁN BỘ HƢỚNG DẪN 1. Tinh thần thái độ của sinh viên trong quá trình làm đề tài tốt nghiệp: 2. Đánh giá chất lƣợng của đề tài tốt nghiệp (so với nội dung yêu cầu đã đề ra trong nhiệm vụ đề tài tốt nghiệp) 3. Cho điểm của cán bộ hƣớng dẫn: ( Điểm ghi bằng số và chữ ) Đỗ Thị Phƣơng- CT1301 Page 7
  8. Đồ án tốt nghiệp Trƣờng DHDL Hải Phòng Ngày tháng năm 2013 Cán bộ hƣớng dẫn chính ( Ký, ghi rõ họ tên ) Đỗ Thị Phƣơng- CT1301 Page 8
  9. Đồ án tốt nghiệp Trƣờng DHDL Hải Phòng PHẦN NHẬN XÉT ĐÁNH GIÁ CỦA CÁN BỘ CHẤM PHẢN BIỆN ĐỀ TÀI TỐT NGHIỆP 1. Đánh giá chất lƣợng đề tài tốt nghiệp (về các mặt nhƣ cơ sở lý luận, thuyết minh chƣơng trình, giá trị thực tế, ) 2. Cho điểm của cán bộ phản biện ( Điểm ghi bằng số và chữ ) Ngày tháng năm 2013 Cán bộ chấm phản biện ( Ký, ghi rõ họ tên ) Đỗ Thị Phƣơng- CT1301 Page 9
  10. Đồ án tốt nghiệp Trƣờng DHDL Hải Phòng MỤC LỤC LỜI NÓI ĐẦU 12 CHƢƠNG 1: MẬT MÃ CỔ ĐIỂN 14 1.1 KHÁI NIỆM VÀ ĐỊNH NGHĨA VỀ MẬT MÃ 14 1.1.1 Khái niệm 14 1.1.2 Định nghĩa 14 1.2 MỘT SỐ MÃ HÓA ĐƠN GIẢN 15 CHƢƠNG 2: CHUẨN MÃ DỮ LIỆU (DES) 16 2.1 Mô tả DES ( Data Encryption Standard) 16 2.2 Các bƣớc thực hiện: 17 2.2.1 Cách tính biến x0: 17 2.2.2 Cách tính LiRi: 18 2.2.2.1 Các biến trong hàm f: 18 2.2.2.2 Cách tính hàm f: 20 2.2.3 Xác định bản mã y: 25 2.3 Giải mã DES 33 2.3.1 Thuật toán 33 2.3.2 Chứng minh thuật toán 33 2.4 Các vấn đề xung quanh DES 35 2.4.1 Những ý kiến phản hồi 35 2.4.2 DES trong thực tế 36 2.4.3 Một vài kết luận về mã DES 37 CHƢƠNG 3. CÁC SƠ ĐỒ CHIA SẺ BÍ MẬT 38 3.1 Khái niệm về chia sẻ bí mật 38 3.2 Sơ đồ chia sẻ bí mật 39 3.2.1 Khái niệm “ sơ đồ chia sẻ bí mật”: 39 3.2.2 Định nghĩa: 39 3.3 Cấu trúc truy nhập và sơ đồ chia sẻ bí mật 43 3.3.1 Định nghĩa sơ đồ chia sẻ bí mật hoàn thiện 43 3.3.2 Định nghĩa tập hợp thức tối thiểu 44 Đỗ Thị Phƣơng- CT1301 Page 10
  11. Đồ án tốt nghiệp Trƣờng DHDL Hải Phòng 3.4 Mạch đơn điệu 44 3.4.1 Định nghĩa mạch đơn điệu 44 3.4.2 Chia sẻ khóa bí mật dựa vào “mạch đơn điệu” 45 CHƢƠNG 4. ỨNG DỤNG THUẬT TOÁN DES VÀ LƢỢC ĐỒ CHIA SẺ BÍ MẬT VÀO THI TUYỂN SINH 48 4.1 Các ứng dụng 48 4.2 Quy trình thực hiện giải bài toán 48 4.2.1 Sơ đồ 48 4.2.2 Các bƣớc thực hiện 49 4.2.3 Mô phỏng lƣợc đồ chia sẻ bỉ mật bằng ngôn ngữ C: 49 4.2.3.1 Chia sẻ khóa bí mật theo giao thức “chia sẻ bí mật” Shamir. 50 4.2.3.2 Khôi phục khóa bí mật bằng phƣơng pháp giải hệ phƣơng trình tuyến tính 52 4.2.3.3 Khôi phục khóa bí mật bằng phƣơng pháp dùng công thức nội suy Lagrange 58 4.2.3.4 Chia sẻ khóa bí mật theo phƣơng pháp bằng mạch đơn điệu 60 4.2.3.5 Khôi phục khóa bí mật theo phƣơng pháp mạch đơn điệu 61 4.3 Mã nguồn mở của chƣơng trình 62 KẾT LUẬN 73 1. Tìm hiểu lí thuyết về mật mã 73 2. Phần ứng dụng 73 TÀI LIỆU THAM KHẢO 74 Đỗ Thị Phƣơng- CT1301 Page 11
  12. Đồ án tốt nghiệp Trƣờng DHDL Hải Phòng LỜI NÓI ĐẦU Ngày nay, mạng máy tính ngày càng trở lên phổ biến. Mỗi quốc gia đều có mạng riêng với rất nhiều mạng mang tính bộ phận. trên phạm vi toàn cầu, ngƣời ta đã dùng mạng Internet một cách thông dụng. Nhiều dịch vụ điện tử nhƣ: thƣ điện tử, chuyển tiền, thƣơng mại điện tử, chính phủ điện tử đã đƣợc áp dụng rộng rãi. Các ứng dụng trên mạng máy ngày càng trở lên phổ biến, thuận lợi và quan trọng thì yêu cầu về an toàn mạng, về an ninh dữ liệu càng trở lên cấp bách và cần thiết. Trên thế giới có rất nhiều quốc gia, nhiều nhà khoa học ngiên cứu về vấn đề bảo mật, đƣa ra nhiểu thuật toán với mục đích thông tin truyền đi không bị lấy cắp hoặc nếu bị lấy cắp thì cũng không sử dụng đƣợc. Trong đề tài của em đƣa ra một thuật toán đó là thuật toán DES(Data encryption standar) đây là thuật toán chuẩn của Mỹ, đƣợc Mỹ và nhiều nƣớc trên thế giới sử dụng, thuật toán này đã đƣợc đƣa vào sử dụng nhiều năm nhƣng vẫn giữ đƣợc tính bảo mật của nó. Tuy nhiên với công nghệ phát triển nhƣ hiện nay thì thuật toán DES trở lên không đƣợc an toàn tuyệt đối nữa, ngƣời ta đã đƣa ra thuật toán 3DES dựa trên nền tảng của thuật toán DES nhƣng số bít đƣợc mã hóa tăng lên. Mã hóa và các lƣợc đồ chia sẻ bí mật có thể đƣợc ứng dụng trong rất nhiều lĩnh vực ví dụ: phát hành thẻ ATM trong ngân hang, đấu tầu từ xa, trong thi tuyển sinh, trong lĩnh vực quân sự Trong đề tài của em đề cập tới một lĩnh vực đó là ứng dụng trong thi tuyển sinh đại học. Vấn đề thi tuyển sinh đại học ở nƣớc ta trở thành gánh nặng cho ngành Giáo Dục và các ban ngành khác liên quan. Nó làm tổn hại về kinh tế và công sức không chỉ đối với các ban ngành tham gia tổ chức kỳ thi mà ngay cả đối với các thí sinh dự thi, nhƣng đó là điều bắt buộc phải đƣợc tổ chức hàng năm. Do vậy làm sao để giảm thiểu các khâu trong thi tuyển sinh mà vẫn đảm bảo tính công bằng và chính xác là điều cần thiết, theo tôi để làm đƣợc điều đó ta nên ứng dụng công nghệ thông tin vào việc thi tuyển sinh đại học, một trong những ứng dụng đó là ứng dụng lƣợc đồ chia sẻ bí mật vì nó đảm bảo đƣợc tính bí mật và chính xác mà trong thi tuyển sinh hai điều đó là quan trọng nhất. Phạm vi luận văn đề cập đến mật mã, thuật toán DES, lƣợc đồ chia sẻ bí mật và ứng dụng của chúng trong thi tuyển sinh. Đỗ Thị Phƣơng- CT1301 Page 12
  13. Đồ án tốt nghiệp Trƣờng DHDL Hải Phòng Luận văn gồm 4 chƣơng: Chƣơng 1: Mật mã cổ điển: chƣơng này giới thiệu về khái niệm và định nghĩa mật mã, một số mã cổ diển. Chƣơng 2: thuật toán DES: chƣơng này nói về mã hóa và giải mã trong thuật toán DES, các vấn đề xung quanh DES. Chƣơng 3: Chia sẻ bí mật: chƣơng này nói về khái niệm chia sẻ bí mật, phƣơng thức chia sẻ và khôi phục khóa bí mật. Chƣơng 4: Ứng dụng thuật toán DES và lƣợc đồ chia sẻ bí mật vào thi tuyển sinh: Chƣơng này nói vè phần ứng dụng và mô phỏng lƣợc đồ chia sẻ bí mật bằng ngôn ngữ C. Để hoàn thành luận văn này, trƣớc hết em xin chân thành cảm ơn TS Hồ Văn Canh - ngƣời đã trực tiếp hƣớng dẫn, cung cấp tài liệu và đóng góp nhiều ý kiến cho luận văn. Em cũng xin chân thành cảm ơn các thầy cô giáo, các cán bộ khoa công nghệ thông tin trƣờng đại học Dân Lập Hải Phòng đã tận tình giảng dạy, giúp đỡ em trong suốt khóa học. Đỗ Thị Phƣơng- CT1301 Page 13
  14. Đồ án tốt nghiệp Trƣờng DHDL Hải Phòng CHƢƠNG 1: MẬT MÃ CỔ ĐIỂN 1.1 KHÁI NIỆM VÀ ĐỊNH NGHĨA VỀ MẬT MÃ 1.1.1 Khái niệm - Chức năng cơ bản của mật mã là tạo ra khả năng liên lạc trên một kênh không mật cho hai ngƣời sử dụng ( tạm gọi là A và B ) sao cho đối phƣơng C không thể hiểu đƣợc thông tin truyền đi. - Kênh liên lạc có thể là một đƣờng dây điện thoại hoặc một mạng máy tính. Thông tin mà A muốn gửi cho B bản rõ có thể là một văn bản tiếng Anh, các dữ liệu bằng số hoặc bất cứ tài liệu nào có cấu trúc tùy ý. - A sẽ mã hóa bản rõ bằng một khóa đã đƣợc xác định trƣớc và gửi bản mã kết quả trên kênh. C có bản mã thu trộm đƣợc trên kênh xong không thể xác định nội dung của bản rõ, nhƣng B (ngƣời biết khóa mã) có thể giải mã và thu đƣợc bản rõ. Ta sẽ mô tả hình thức nội dung bằng cách dùng khái niệm toán học nhƣ sau: 1.1.2 Định nghĩa Một hệ mật mã là một bộ 5 ( P, C, K, E,D ) thỏa mãn các điều kiện sau: 1. P là một tập hữu hạn các bản rõ có thể 2. C là một tập hữu hạn các bản mã có thể 3. K (không gian khóa) là tập hữu hạn các khóa có thể. 4. Đối với mỗi k є K có một quy tắc mã ek: P→ C và một quy tắc giải mã tương ứng dk є D. Mỗi ek: P→ C và dk: C→ P là những hàm sao cho: dk(ek(x)) = x với mọi bản rõ x є P. Trong đó chúng ta cần lƣu ý tính chất 4: Nội dung của nó là nếu một bản rõ x đƣợc mã hóa bằng ek và bản mã nhận đƣợc sau đó đƣợc giải mã bằng dk thì ta phải thu đƣợc bản rõ ban đầu x. Giả sử ta có bản rõ cần truyền đi là: x= x1, x2, .,xn với số nguyên n≥1 nào đó. Ở đây mỗi kí hiệu của mỗi bản rõ xi є P,1≤ i ≤ n. Mỗi xi sẽ đƣợc mã hóa bằng quy tắc mã ek với khóa k xác định trƣớc đó. Bản mã thu đƣợc là: y=y1, y2, ,yn. Trong đó yk=ek(xi) i=1,2, ,n còn k є K. Khi Bob nhận đƣợc y1, y2, ,yn anh ta sẽ giải mã bằng hàm giải mã dk và thu đƣợc bản rõ gốc x= x1, x2, .,xn. Đỗ Thị Phƣơng- CT1301 Page 14
  15. Đồ án tốt nghiệp Trƣờng DHDL Hải Phòng Hình 1.1 là một ví dụ về một kênh liên lạc C x y x A Bộ mã hóa Bộ giải mã B k k k Kênh an k toàn Nguồn khóa Hình 1.1. Kênh liên lạc Rõ ràng là trong trƣờng hợp này hàm mã hóa phải là hàm đơn ánh( tức là á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ụ y= ek(x1)= ek(x2) trong đó x1 ≠ x2, B sẽ không có cách nào đẻ biết liệu bản rõ là x1 hay x2. 1.2 MỘT SỐ MÃ HÓA ĐƠN GIẢN Mã dịch vòng Mã thay thế Mã Affine Mã Hill Mã chuyển vị Đỗ Thị Phƣơng- CT1301 Page 15
  16. Đồ án tốt nghiệp Trƣờng DHDL Hải Phòng CHƢƠNG 2: CHUẨN MÃ DỮ LIỆU (DES) Các hệ mật mã truyển thống ở chƣơng 1 có một số ƣu điểm là mã hóa và giải mã bằng thủ công đƣợc thực hiện rất dễ dàng, việc trao đổi khóa mã cũng rất đơn giản bằng thủ công hoặc bằng qui ƣớc. Song với lƣợng thông tin quá phong phú nhƣ hiện nay và với mạng truyền thông nhƣ hiện nay thì mật mã thủ công vừa không đảm bảo bí mật. Mặt khác các thuật toán mã hóa thủ công đòi hỏi phải tuyệt đối giữ bí mật Nhƣ vậy mật mã thủ công đòi hỏi bảo mật cả thuật toán mã hóa và cả khóa mã. Sau những năm 70 của thế kỉ trƣớc, các nhà toán học đã nghiên cứu và tạo ra nhiều phƣơng thức mật mã với tốc độ mã hóa rất nhanh (hàng trục thậm chí hàng trăm kilo Byte trong một giây) và ngƣời ta chỉ cầm giữ bí mật khóa mã và mã hóa đƣợc mọi dữ liệu tùy ý. Đó là một bƣớc tiến vĩ đại của kĩ thuật mật mã. Trong đó mã DES ( Data Encryption Standard) là một điển hình của bƣớc tiến này. Chƣơng này em muốn mô phỏng mã hóa và giải mã của thuật toán DES. 2.1 Mô tả DES ( Data Encryption Standard) DES mã hóa một xâu bít x: Bản rõ x độ dài 64 bít. Khóa k độ dài 56 bit. Bản mã y nhận đƣợc cũng là một xâu bit có độ dài 64 bit. Thuật toán tiến hành theo 3 giai đoạn: 1. Với bản rõ cho trƣớc x, một xâu bit x0 sẽ đƣợc tạo ra bằng cách hoán vị các bit của x theo phép hoán vị cố định ban đầu IP. Ta viết : x0=IP(X)=L0R0, trong đó L0 gồm 32 bit đầu và R0 là 32 bit cuối. 2. Sau đó tính toán 16 lần lặp theo một hàm xác định. Ta sẽ tính đƣợc LiRi, 1 ≤ i ≤ 16 theo qui tắc sau: Li = Ri-1 Ri = Li-1 f (Ri-1, Ki) Trong đó kí hiệu cộng theo modulo 2 của 2 xâu bit. f là một hàm mà của Ri-1, ki mô tả sau. ki là các xâu bit độ dài 48 bit đƣợc tính nhƣ hàm của khóa k. (Trên thực tế mỗi ki là một phép chọn hoán vị bit trong k). Đỗ Thị Phƣơng- CT1301 Page 16
  17. Đồ án tốt nghiệp Trƣờng DHDL Hải Phòng -1 3. Áp dụng phép hoán vị ngƣợc IP cho xâu bit R16L16 ta thu đƣợc bản mã -1 y.Tức là y = IP (R16 L16). Li-1 Ri-1 A f J Ki + Li Ri Hình 2.1. Một vòng ( vòng thứ i ) của DES. 2.2 Các bƣớc thực hiện: 2.2.1 Cách tính biến x0: Hoán vị biến x theo phép hoán vi ban đầu IP(X) x0 = IP(X) = L0R0 Bảng 2.1.Bảng IP IP 58 50 42 34 26 18 10 2 60 52 44 36 28 20 12 4 62 54 46 38 31 22 14 6 64 56 48 40 32 24 16 8 57 49 41 33 25 17 9 1 59 51 43 35 27 19 11 3 61 53 45 37 29 21 13 5 63 55 47 39 31 23 15 7 Đỗ Thị Phƣơng- CT1301 Page 17
  18. Đồ án tốt nghiệp Trƣờng DHDL Hải Phòng Theo bảng 2.1 này có nghĩa là bit thứ 58 của x là bit đầu tiên của IP(x), bit thứ 50 của x là bit thứ 2 của IP(x), bit ở vị trí thứ 7 là bit cuối của IP(x). 2.2.2 Cách tính LiRi: Để tính LiRi trƣớc hết ta phải xác định hàm f 2.2.2.1 Các biến trong hàm f: Có 2 biến vào . Biến thứ nhất Ri-1là xâu bit độ dài 32 . Biến thứ hai J là xâu bít độ dài 48 . Đầu ra của f là một xâu bit độ dài 32 bít. Hàm f thực hiện qua các bƣớc sau: Bước 1: Xác định biến thứ nhất (biến A): Xâu bit của Ri-1 đƣợc mở rộng thành một xâu bit có độ dài 48 theo một hàm mở rộng cố định E. Bảng 2.2. Bảng chọn E bit Bảng chọn E bit 32 1 2 3 4 5 4 5 6 7 8 9 8 9 10 11 12 13 12 13 14 15 16 17 16 17 18 19 20 21 20 21 22 23 24 25 24 25 26 27 28 29 28 29 30 31 32 1 Đỗ Thị Phƣơng- CT1301 Page 18
  19. Đồ án tốt nghiệp Trƣờng DHDL Hải Phòng E(Ri-1) gồm 32 bit của Ri-1 (đƣợc hoán vị theo cách cố định) với 16 bit xuất hiện 2 lần.Theo bảng E bit ở vị trí thứ 32 là bit đầu tiên của E(Ri-1), ở vị trí thứ 1 là bit thứ 2 và bit cuối của E(Ri-1). Bước 2: Xác định biến thứ hai (biến J) Biến J thực chất là phép hoán vị và dịch vòng của xâu bit khóa k Thuật toán tạo 16 khóa con k1, k2, k16 K PC-1 C0 D0 LS1 LS1 C1 D1 PC-2 K1 LS16 LS16 C16 D16 PC-2 K16 Hình 2.2. Sơ đồ tạo khóa k Đỗ Thị Phƣơng- CT1301 Page 19
  20. Đồ án tốt nghiệp Trƣờng DHDL Hải Phòng Theo sơ đồ hình 2.2 trên việc xác định ki đƣợc thực hiện nhƣ sau: Với khóa k 64 bit cho trƣớc hoán vị thực chất chỉ có 56 bit dùng để tạo ki với i từ 1 đến 16.Tránh các bit ở vị trí 8,16,24,32,40,48,56,64. Theo phép hoán vị cố định PC-1 ta viết: PC-1(K) = C0D0. Trong đó C0 là 28 bit đầu và D0 là 28 bit cuối. Mỗi phần sẽ đƣợc xử lí một cách độc lập. Ci = LSi (Ci -1) Di = LSi (Ci -1) với 1≤ i≤ 16 LSi biểu diễn phép dịch bit vòng sang trái 1 hoặc 2 vị trí tùy thuộc vào i. Sang trái 1 bit nếu i= 1, 2, 9, 16 hoặc sang trái 2 bit nếu I thuộc các vị trí còn lại. ki = PC-2 (Ci - Di). PC-2 là hoán vị cố định sẽ hoán vị chuỗi Ci - Di 56 bit thành chuỗi 48 bit. 2.2.2.2 Cách tính hàm f: Ri-1 Cộng XORKi E(Ri-1). 48 bit 48 bit B1 B2 B3 B4 B5 B6 B7 B8 S1 S2 S3 S4 S5 S6 S7 S8 C1 C2 C3 C4 C5 C6 C7 C8 P F(Ri-1,k i) Hình 2.3.Sơ đồ hoạt động của hàm f(Ri-1,k i): Đỗ Thị Phƣơng- CT1301 Page 20
  21. Đồ án tốt nghiệp Trƣờng DHDL Hải Phòng Sau khi mở rộng Ri-1 bởi hàm mở rộng E để chuyên Ri-1 gồm 32 bit thành E(Ri-1) gồm 48 bit, E(Ri-1) cộng XOR với khóa ki cho ra là: E(Ri-1) + ki = B = B1B2 B8 B gồm 48 bit đƣợc phân thành 8 khối (block) nhƣ nhau và mỗi block Bi, i =1,8 có độ dài 6 bit. Sau đó mỗi Bi đƣợc đƣa vào hộp Si, i = 1,8 và biến đổi để cho đầu ra là Ci gồm 4 bit (i = 1,8). Sự biến đổi này đƣợc thực hiện nhƣ sau: Giả sử Bi gồm 6 bit là Bi= bi1bi2 bi6. Khi đó bi1bi6 đƣợc nhập thành cặp, bi1bi6 đƣợc chuyển thành số thập phân từ 1 đến 3. Ví dụ: bi1bi6 = 00→0 bi1bi6 =01→1 bi1bi6 =10→2 bi1bi6 =11→3 Còn bi2bi3 bi4bi5 của Bi đƣợc chuyển thành số thập phân từ 0 đến 15 nhƣ sau: Bảng 2.3. Bảng chuyển đổi giá trị. bi2bi3 bi4bi5 Số tự nhiên 0000 0 0001 1 0010 2 0011 3 0100 4 0101 5 0110 6 0111 7 1000 8 1001 9 1010 10 1011 11 1100 12 1101 13 1110 14 1111 15 Đỗ Thị Phƣơng- CT1301 Page 21
  22. Đồ án tốt nghiệp Trƣờng DHDL Hải Phòng Số nguyên dƣơng ri = bi1bi6 và si = bi2bi3 bi4bi5 chính là tọa độ (hoành tung) của ma trận Si từ ti chuyển thành Ci = Ci1Ci2 Ci3Ci4 với Cij є{0,1} i= i =1,8 , j =1,4. Vậy đầu ra của hộp S là: C1C2 C8 mỗi Ci gồm 4 bit tọa thành khối C = C1C2 C8 gồm 32 bit. 32 bit này đƣợc đƣa vào ma trận chuyển vị P để cho đầu ra cũng là 32 bit. Đó là đầu ra của hàm f(Ri-1,Ki). Ta có thể trình bày cụ thể cách tính hàm f nhƣ sau: Với xâu bit có độ dài 6 bit (kí hiệu Bi= b1b2 b6), ta tính đƣợc Sj(Bj ) nhƣ sau: Hai bit bib6 xác định biểu diễn nhị phân của hàng r của Sj (0 ≤ r ≤ 3) và 4 bit b2b3 b4b5 xác định biểu diễn nhị phân của cột c của Sj (0 ≤ c ≤ 15). Khio đó Sj(Bj ) sẽ xác định phần tử Sj(r,c); phần tử này viết dƣới dạng nhị phân là một xâu bit có độ dài là 4.(Bởi vậy mỗi Sj có thể coi là một hàm mã mà đầu vào là một xâu bit có độ dài 2 và một xâu bit độ dài 4, còn đầu ra là một xâu bit cố độ dài 4). Bằng cách tƣơng tự tính các Cj= Sj(Bj ), 1≤ j ≤ 8. Thật vậy mỗi chuỗi B là một chuỗi 6 bit trong đó bit đầu và bit cuối đƣợc dùng để xác định vị trí của hàng trong phạm vi từ 0 đến 3 (hoặc từ 00 đến 11) bốn bit giữa dùng để xác định vị trí của cột trong phạm vi từ 0 đến 15 (hoặc từ 0000 đến 1111). Sauk hi xác định đƣợc vị trí của hàng và cột ta đối chiếu trong bảng S đƣợc một số thập phân ,quy đổi số thập phân đó ra giá trị nhị phân ta đƣợc Cj. Ví dụ: Bit đầu vào của B là B = 100110 Bit đầu và cuối là “10” cho ta thứ tự của hàng là 2, bốn bit giữa là “0011” cho ta thứ tự của cột là 4. Đối chiếu với hộp S1 xuất hiện số 14, chuyển 14 sang nhị phân 14= 1110, Vậy S(B) = S(100110)= 1110. Tám hộp S là: S1 14 4 13 1 2 15 11 8 3 10 3 12 5 9 1 7 1 15 7 4 14 2 13 1 10 6 12 11 9 5 3 8 4 1 14 8 13 6 2 11 15 12 9 7 3 10 5 0 15 12 8 2 4 9 1 7 5 11 3 14 10 0 6 13 Đỗ Thị Phƣơng- CT1301 Page 22
  23. Đồ án tốt nghiệp Trƣờng DHDL Hải Phòng S2 15 1 8 14 6 11 3 4 9 7 2 13 12 0 5 10 3 13 4 7 15 2 8 14 12 0 1 10 6 9 11 5 0 14 7 11 10 4 13 1 5 8 12 6 9 3 2 15 13 8 10 1 3 15 4 2 11 6 7 12 0 5 14 9 S3 10 0 9 14 6 3 15 5 1 13 12 7 11 4 2 8 13 7 0 9 3 4 6 10 2 8 5 14 12 11 15 1 13 6 4 9 8 5 3 0 11 1 2 12 5 10 14 7 1 10 13 0 6 9 8 7 4 15 14 3 11 5 2 12 S4 7 13 14 3 0 6 9 10 1 2 8 5 11 12 4 15 13 8 11 5 6 15 0 3 4 7 2 12 1 10 14 9 10 6 9 0 12 11 7 13 15 1 3 14 5 2 8 4 3 15 0 6 10 1 13 8 9 4 5 11 12 7 2 14 S5 2 12 4 1 7 10 11 6 8 5 3 15 13 0 14 9 14 11 2 12 4 7 13 1 5 0 15 10 3 9 8 6 4 2 1 11 10 13 7 8 15 9 12 5 6 3 0 14 11 8 12 7 1 14 2 13 6 15 0 9 10 4 5 3 Đỗ Thị Phƣơng- CT1301 Page 23
  24. Đồ án tốt nghiệp Trƣờng DHDL Hải Phòng S6 12 1 10 15 9 2 6 8 0 13 3 4 14 7 15 11 10 15 4 2 7 12 9 5 6 1 13 14 0 11 3 8 9 14 15 5 2 8 12 3 7 0 4 10 1 13 11 6 4 3 2 12 9 5 15 10 11 14 11 7 6 0 8 13 S7 4 11 12 14 15 0 8 13 3 12 9 7 5 10 6 1 13 0 11 7 4 9 1 10 14 3 5 12 2 15 8 6 1 4 11 13 12 3 7 14 10 15 6 8 0 5 9 2 6 11 13 8 1 4 10 7 9 5 0 15 14 2 3 12 S8 13 2 8 4 6 15 11 1 10 9 3 14 5 0 12 7 1 5 13 8 10 3 7 4 12 5 6 11 0 14 9 2 7 11 4 1 9 12 14 2 0 6 10 13 15 3 5 8 2 1 14 7 4 10 8 13 15 12 9 0 3 5 6 11 Sau khi thực hiện các phép đối chiếu hộp S ta đƣợc các giá trị SiBi Tính hàm f = P(S1(B1)) = S2(B2) S8(B8) thực hiện theo phép hoán vị P Phép hoán vị P có dạng: Đỗ Thị Phƣơng- CT1301 Page 24
  25. Đồ án tốt nghiệp Trƣờng DHDL Hải Phòng Bảng 2.4. Bảng hoán vị P P 16 7 20 21 29 12 28 17 1 15 23 26 5 18 31 10 2 8 24 14 32 27 3 9 19 13 30 6 22 11 4 25 Theo bảng 2.4 thì bit thứ 16 và bit thứ 7 của xâu bit SjBj lần lƣợt là bít thứ nhất và bit thứ 2 của hàm f LỉRi đƣợc xác định theo công thức sau: Lỉ = Ri-1 Ri= Li-1+ f(Ri-1, ki) 2.2.3 Xác định bản mã y: Sau khi xác định đƣợc LỉRi ta thu đƣợc L16R16 , vậy bản mã y đƣợc xác định theo công thức: -1 y= IP (R16, L16) Đỗ Thị Phƣơng- CT1301 Page 25
  26. Đồ án tốt nghiệp Trƣờng DHDL Hải Phòng Bảng 2.5. Bảng IP-1 IP-1 40 8 48 16 56 24 64 32 39 7 47 15 55 23 63 31 38 6 46 14 54 22 62 30 37 5 45 13 53 21 61 29 36 4 44 12 52 20 60 28 35 3 43 11 51 19 59 27 34 2 42 10 50 18 58 26 33 1 41 9 49 17 57 25 Ví dụ: Ta có bản rõ M= 0123456789ABCDEF Khóa k=133457799BBCDFF1 Giải Bước 1: Tìm x0= IP(X)= L0R0 M=0000.0001. 0010.0011. 0100.0101. 0110.0111. 1000.1001. 1010.1011. 1100.1101. 1110.1111 16 32 L=0000.0001. 0010.0011. 0100.0101. 0110.0111 48 64 R= 1000.1001. 1010.1011. 1100.1101. 1110.1111 Thực hiện phép hoán vị IP Đỗ Thị Phƣơng- CT1301 Page 26
  27. Đồ án tốt nghiệp Trƣờng DHDL Hải Phòng IP 58 50 42 34 26 18 10 2 60 52 44 36 28 20 12 4 62 54 46 38 31 22 14 6 64 56 48 40 32 24 16 8 57 49 41 33 25 17 9 1 59 51 43 35 27 19 11 3 61 53 45 37 29 21 13 5 63 55 47 39 31 23 15 7 IP(M)= 1100.1100. 0000.0000. 11001100. 1111.1111. 1111.0000. 1010.1010. 1111.0000.1010.1010 L0 = 1100.1100. 0000.0000. 11001100. 1111.1111 R0 = 1111.0000. 1010.1010. 1111.0000.1010.1010 Bước 2: Xác định khóa ki k= 0001.0011. 0011.0100. 0101.0111. 0111.1001. 1001.1011. 1011.1100. 1101.1111. 1111.1001 Hoán vị khóa k theo phép hoán vị PC-1 ta thu đƣợc PC-1(k): Đỗ Thị Phƣơng- CT1301 Page 27
  28. Đồ án tốt nghiệp Trƣờng DHDL Hải Phòng Bảng 2.5. Bảng PC-1 PC-1 57 49 41 33 25 17 9 1 58 50 42 34 26 18 10 2 59 51 43 35 27 19 11 3 60 52 44 36 63 55 47 39 31 23 15 7 62 54 46 38 30 22 14 6 61 53 45 37 29 21 13 5 28 20 12 4 PC-1(k) = 1111000 0110011 0010101 0101111 0101010 1011001 1001111 0001111 C0 = 1111000 0110011 0010101 0101111 D0 = 0101010 1011001 1001111 0001111 Tìm CiDi: Ci = Si(Ci-1) Di = Si(Di-1) Trong đó: Si là sự dịch chuyển Ci-1, Di-1 đi 1 sang trái với i= 1,2,9,16 và dịch 2 với các i còn lại. C1 = 1110000 1100110 0101010 1011111 D1 = 1010101 0110011 0011110 0011110 C2 = 1100001 1001100 1010101 0111111 D2 = 0101010 1100110 0111100 0111101 C3 = 0000110 0110010 1010101 1111111 Đỗ Thị Phƣơng- CT1301 Page 28
  29. Đồ án tốt nghiệp Trƣờng DHDL Hải Phòng D3 = 0101011 0011001 1110001 1110101 C4 = 0011001 1001010 1010111 1111100 D4 = 0101100 1100111 1000111 1010101 C5 = 1100110 0101010 1011111 1110000 D5 = 0110011 0011110 0011110 1010101 C6 = 0011001 0101010 1111111 1000011 D6 = 1001100 1111000 1111010 1010101 C7 = 1100101 0101011 1111110 0001100 D7 = 0110011 1100011 1101010 1010110 C8 = 0010101 0101111 1111000 0110011 D8 = 1001111 0001111 0101010 1011001 C9 = 0101010 1011111 1110000 1100110 D9 = 0011110 0011110 1010101 0110011 C10 = 0101010 1111111 1000011 0011001 D10 = 1111000 1111010 1010101 1001100 C11 = 0101011 1111110 0001100 1100101 D11 = 1100011 1101010 1010110 0110011 C12 = 0101111 1111000 0110011 0010101 C13 = 0111111 1100001 1001100 1010101 D13 = 0111101 0101010 1100110 0111100 C14 = 1111111 0000110 0110010 1010101 D14 = 1110101 0101011 0011001 1110001 C15 = 1111100 0011001 1001010 1010111 D15 = 1010101 0101100 1100111 1000111 C16 = 1111000 0110011 0010101 0101111 D16 = 0101010 1011001 1001111 0001111 Cuối cùng các khóa con Ki thu đƣợc từ Ci ,Di qua hoán vị PC-2 cho trƣớc. Đỗ Thị Phƣơng- CT1301 Page 29
  30. Đồ án tốt nghiệp Trƣờng DHDL Hải Phòng Bảng 2.6. Bảng PC-2 PC-2 14 17 11 24 1 5 3 28 15 6 21 10 23 19 12 4 26 8 16 7 27 20 13 2 41 52 31 37 47 55 30 40 51 45 33 48 44 49 39 56 34 53 46 42 50 36 29 32 k1 = 000110 110000 001011 101111 111111 000111 000001 110010 k2 = 011110 011010 111011 011001 110110 111100 100111 100101 k3 = 010101 011111 110010 001010 010000 101100 111110 011001 k4 = 011100 101010 110111 010110 110110 110011 010100 011101 k5 = 011111 001110 110000 000111 111010 110101 001110 101000 K6 = 011000 111010 010100 111110 010100 000111 101100 101111 k7 = 111011 001000 010010 110111 111101 100001 100010 111100 k8 = 111101 111000 101000 111010 110000 010011 101111 111011 k9 = 111000 001101 101111 101011 111011 011110 011110 000001 k10 =101100 011111 001101 000111 101110 100100 011001 001111 k11= 001000 010101 111111 010011 110111 101101 011110 000110 k12= 011101 010111 000111 110101 100101 000110 011111 101001 k13= 100101 111100 010111 010001 111110 101011 101001 000001 k14= 010111 110100 001110 110111 111100 101110 011100 111010 k15= 101111 110011 000110 001101 001111 010011 111100 001010 k16= 110010 110011 110110 001011 000011 100001 011111 110101 Đỗ Thị Phƣơng- CT1301 Page 30
  31. Đồ án tốt nghiệp Trƣờng DHDL Hải Phòng Bước 3:Tìm hàm f(Ri-1, ki) Tính S1(B1) = S1(011000). Bit đầu và bit cuối là “00” cho ta hàng 0 Bốn bit giữa “1100”=12 cho ta cột 12 Chiếu hàng 0 cột 12 vào bảng S1 cho ta giá trị là 5= “0101” Vậy S1(011000) = “0101” Tính S2(B2) = S2(010001) thực hiện hoán vị S1(B1) theo phép hoán vị S1 Bit đầu và bit cuối là “01” cho ta hàng 1 Bốn bit giữa “1000”=8 cho ta cột 8 Chiếu hàng 1 cột 8 vào bảng S2 cho ta giá trị là 12=”1100” Vậy S2(010001)= “1100”. Tính tƣơng tự ta có S1(B1) = S2(B2) = S3(B3) = S4(B4) = S5(B5) = S6(B6) = S7(B7) = S8(B8) =0101 1100 1000 0010 1011 0101 1001 0111 Tính hàm f= P S1(B1) = S2(B2) S8(B8) thực hiện theo phép hoán vị P P 16 7 20 21 29 12 28 17 1 15 23 26 5 18 31 10 2 8 24 14 32 27 3 9 19 13 30 6 22 11 4 25 f= P (S1(B2) = S2(B2) S8(B8) = P (0101 1100 1000 0010 1011 0101 1001 0111) = 0010 0011 0100 1010 1010 1001 1011 1011 Đỗ Thị Phƣơng- CT1301 Page 31
  32. Đồ án tốt nghiệp Trƣờng DHDL Hải Phòng R1 = L0 + f(R0, k1) = 1100 1100 0000 0000 1100 1100 1111 1111 + 0010 0011 0100 1010 1010 1001 1011 1011 = 1110 1111 0100 1010 0110 0101 0100 0100 Tƣơng tự ta tính : R2 = L1 + f(R1, k2) R16 = L15 + f(R15, k16) Ta thực hiện 16 lần vòng lặp thu đƣợc R16L16 L16 = 0100 0011 0100 0010 0011 0010 0011 0100 R16 = 0000 1010 0100 1100 1101 1001 1001 0101 R16L16 = 0000 1010 0100 1100 1101 1001 1001 0101 0100 0011 0100 0010 0011 0010 0011 0100 Thực hiện phép hoán vị ngƣợc IP(IP-1) IP-1 40 8 48 16 56 24 64 32 39 7 47 15 55 23 63 31 38 6 46 14 54 22 62 30 37 5 45 13 53 21 61 29 36 4 44 12 52 20 60 28 35 3 43 11 51 19 59 27 34 2 42 10 50 18 58 26 33 1 41 9 49 17 57 25 Ta đƣợc IP-1 = 10000101 11101000 00010011 01010100 00001111 00001010 10110100 00000101. Chuyển IP-1 sang dạng hexa ta thu đƣợc bản mã : 85E823540F0AB405 Đỗ Thị Phƣơng- CT1301 Page 32
  33. Đồ án tốt nghiệp Trƣờng DHDL Hải Phòng 2.3 Giải mã DES Tƣơng tự nhƣ mã hóa, để giải mã một chuỗi kí tự đã bị mã hóa ta cũng làm tƣơng tự theo các bƣớc trên, tuy nhiên hệ thống khóa lúc này đã đƣợc tạo theo chiều ngƣợc lại. 2.3.1 Thuật toán Mã hóa Giải mã - Cho bản rõ x - Cho bản mã y - x0 = IP(x) = L0 R0 - y0 = IP (y) = R16 L16 = L‟0 R‟0 - i = 1,2,3, .16 - i = 1,2,3, .16 Li = Ri-1 Li „= Ri-1‟ Ri = Li-1 ^f(Ri-1,Ki) Ri „= L‟i-1 ^f(R‟i-1,K17-i) - y0 =( R16 L16) - x0 =( R‟16 L‟16) -1 -1 - y = IP (y0) - x = IP (x0) 2.3.2 Chứng minh thuật toán Có bản mã y -1 y0 = IP (y) = IP(IP (R16 L16)) = R16 L16 = L‟0 R‟0 Vậy L‟0 = R16 , R‟0 = L16; Với i=1 L‟1 = R‟0 = L16 = R15 ; R‟1 = L‟0 ^f(R‟0,k16) = R16 ^f(L16 k16) = L15 ^f(R15,k16) ^f(R15,k16) = L15; Tóm lại: L‟1 = R15 ; R‟1 = L15; Đỗ Thị Phƣơng- CT1301 Page 33
  34. Đồ án tốt nghiệp Trƣờng DHDL Hải Phòng y K IP(x) PC-1 Y0 C0 D0 LSi(Ci-1) Li-1 Ri-1 E Ci + K17-i PC-2(k) B qi B B B 1 2 8 S1 S2 S8 C1 C2 C8 P + L R i- i IP(y) x R16 L16 Hình 2.4. Sơ đồ giải mã DES Đỗ Thị Phƣơng- CT1301 Page 34
  35. Đồ án tốt nghiệp Trƣờng DHDL Hải Phòng Từ đó ta thấy , thuật toán giải mã chỉ khác thuật toán mã hóa ở chỗ tạo hệ thống khóa, nếu mã hóa tạo khóa từ k1, k2 , k16 thì giải mã tạo hệ thống khóa từ k16, k15 , k1. Việc này đƣợc trình bày cụ thể trong hình 2.4 sơ đồ giải mã DES. 2.4 Các vấn đề xung quanh DES 2.4.1 Những ý kiến phản hồi Khi DES đƣợc đề nghị nhƣ một tiêu chuẩn thì đã có những lời phê bình, sự phản hồi có liên quan đến các hộp S. Tất cả các sự tính toán trong DES, ngoại trừ các hộp S, đều là tuyến tính. Các hộp S, thành phần phi tuyến trong hệ thống mật mã là sống còn đối với sự an toàn của hệ thống. Tuy nhiên, tiêu chuẩn thiết kế của hộp S chƣa đƣợc hiểu hết, một số ngƣời gợi ý rằng những hộp S này có chứa đựng những cửa sập còn ẩn dấu ở đâu đó. Những cửa sập này có thể cho phép cục an ninh quốc gia giải mã các thông điệp trong khi ngƣời dùng vẫn cho rằng hệ thống này an toàn. Tất nhiên khó có thể phản đối lại lời tuyên bồ này nhƣng chƣa có bằng chứng nào đƣợc đƣa ra để chỉ rõ rằng trong thực tế các cửa sập tồn tai trong DES. Năm 1976, cục an ninh quốc gia Hoa kỳ tuyên bố rằng những thuộc tính của hộp S là tiêu chuẩn thiết kế: - Mỗi một dòng của một hộp S là sự lặp lại của các số nguyên từ 0 đến 15. - Không có hộp S nào có tuyến tính hay là hàm Affine của các đầu vào. - Thay đổi một bit đầu vào của hộp S gây ra ít nhất 2 bit đầu rat hay đổi. - Đối với bất kì một hộp S và bất kì đầu vào x, S(x) và S(x^001100) gây ra sự khác biệt ở ít nhất hai bit 9x ở dây là một chuỗi có độ dài 6. Hai đặc tính khác của hộp S đƣợc thiết kế nhƣ là đƣợc điều khiển bởi các tiêu chuẩn thiết kế của cục An ninh Quốc gia. - Đối cới bất kì hộp S nào, bất kì x đầu vào và đối với e, f {0,1}, S(x)≠ S(x + 1 lef00 ) - Đối với bất kì hộp S nào, nếu một bit đầu vào là cố định và ta xem giá trị của bit đầu ra cố định, số đầu vào làm cho đầu ra = 0 sẽ gần với số đầu vào làm cho đầu ra = 1( lƣu ý rằng nếu ta cố định giá trị của bit 1 và bit 16 thì sẽ có 16 đầu vào làm cho mỗi bit đầu ra cụ thể = 0 và 16 đầu vào làm cho 1 bit đầu ra cụ thể = 1. Đối với lần thứ 2 thông qua các bit đầu vào thứ 5 thì điều này sẽ không đúng nhƣng gần đúng. Cặn kẽ hơn với bất kì hộp S nào nếu nhƣ giá trị của bất cứ bit đầu vào nào là cố định thì số đầu vào mà nhờ đó bất cứ bit đầu ra cố định nào có giá trị là 0 hoặc 1 Đỗ Thị Phƣơng- CT1301 Page 35
  36. Đồ án tốt nghiệp Trƣờng DHDL Hải Phòng thì luôn luôn nằm giữa 13 và 19). Lời chỉ trích thích đáng nhất về DES là kích cỡ của không gian khóa 256 là khóa nhỏ để trở lên an toàn. Những máy có mục đích đặc biệt khác nhau đƣợc đẹ trình cho tấn công bản rõ, mà nó thực hiện chủ yếu tìm kiếm khóa. Đó là đƣa ra bản rõ x gồm 64bit và một bản tƣơng đƣơng y, thì mỗi một khóa có thể có lớn hơn một khóa k là Ek(x) = y đƣợc tìm thấy.(Lƣu ý rằng có thể lớn hơn một khóa k0). - Đầu năm 1977, Diffie và Hellman đề nghị rằng một ngƣời có thể xây dựng một chip VLSL có thể kiểm tra đƣợc 106 khóa một giây. Một máy với 106 có thể tìm kiếm toàn bộ không gian khóa trong một ngày. Họ dự tính rằng máy này đƣợc xây dựng với giá khoảng 20 USD. - Tại hôi nghị CRYPTO‟93 (phần kéo dài), Michael Wiener đƣa ra một thiết kế rất chi tiết về một máy dò khóa. Máy này dựa trên một chip dò khóa đƣợc nối truyền liên tiếp, vì vậy 16 mã hóa đƣợc diễn ra đồng thời. Chip này có thể kiểm tra 5.107 khóa 1 giây và có thể đƣợc xây dựng sử dụng công nghệ hiện thời với giá 10,5 USD một chip. Một khung bao gồm 5760 chip có thể đƣợc xây dựng với giá 1 triệu USD nhƣng giảm thời gian dò trung bình xuống còn 3,5 giờ. 2.4.2 DES trong thực tế Ngay cả khi việc mô tả DES khá dài dòng thì DES đƣợc thực hiện rất hiệu quả trong cả phần cứng lẫn phần mền. Những tính toán số học duy nhất đƣợc thực hiện là phép XOR của các chuỗi bit. Việc mở rộng hàm E các hộp S, sự hoán vị IP và P, và việc tính toán k1, k2, , k16 tất cả đƣợc thực hiện trong thời gian ngắn bởi bảng tìm kiếm trong phần mền hoặc cách nối dây cứng chúng vào môt mạch. Những thi hành phần cứng hiện thời có thể đạt tốc độ mã hóa cực nhanh, công ty thiết bị số thông báo tại CRYPTO‟92 rằng họ vừa mới chế tạo đƣợc một chip với 50k Transistors có thể mã hóa với tốc độ 1GB/s sử dụng một đồng hồ tốc độ là 250MHz. Giá của chip này khoảng 300USD. Năm 1991 có 45 phần cứng và chƣơng trình cài sẵn thi hành DES đã đƣợc ủy ban tiêu chuẩn quốc gia Mỹ phê chuẩn. Một ứng dụng rất quan trọng của DES là ứng dụng vào việc giao dịch ngân hàng sử dụng các tiêu chuẩn đƣợc hiệp hội các ngân hàng Mỹ phát triển. DES đƣợc sử dụng đẻ mã hóa các con số, nhận dạng các nhân(PIN) và trao đổi tài khoản đƣợc máy thu ngân tự động thực hiện (ATM). DES cũng đƣợc clearing Hourse Interbank System (CHIPS) sử dụng đẻ trao đổi có liên quan đến trên 1,5.1012 USD/ tuần. DES cũng đƣợc sử dụng rộng rãi trong các tổ chức chính phủ nhƣ: Bộ năng lƣợng, Bộ tƣ pháo và hệ thống phản chứng liên bang. Đỗ Thị Phƣơng- CT1301 Page 36
  37. Đồ án tốt nghiệp Trƣờng DHDL Hải Phòng 2.4.3 Một vài kết luận về mã DES Có rất nhiều phƣơng pháp mã hóa đẻ đảm bảo an toàn dữ liệu. Để đánh giá tính ƣu việt một giải thuật mã hóa, nhƣời ta thƣờng dựa vào các yếu tố: Tính bảo mật, độ phức tạp, tốc độ thực hiện giải thuật và vấn đề phân khóa trong môi trƣờng nhiều ngƣời sử dụng. Hiện nay phƣơng pháp mã hóa DES đƣợc sử dụng rộng rãi nhất. Các chip chuyên dung DES đƣợc thiết kế nhằm tăng tốc độ xử lí của DES. Rất nhiều nhà toán học ,tin học đã bỏ nhiều công nghiên cứu trong nhiều năm nhằm tìm cách phá vỡ DES (tức là tìm ra cách giải mã trong khoảng thời gian ngắn hơn thời gian cần để thử lần lƣợt tất cả các khóa). Ngoại trừ việc tìm ra 4 khóa yếu và 12 khóa tƣơng đối yếu cho tới nay chƣa có một thông báo nào về việc tì ra cách phá vỡ phƣơng pháp mã hóa này. Để phá vỡ DES bằng phƣơng pháp “ vét cạn” thử tất cả các khóa trong không gian khóa cần có một khoản tiền lớn và đòi hỏi một khoảng thời gian dài. Nhƣợc điểm của DES: nó là thuật tán mã hóa đối xứng. Khi phƣơng pháp này mới đƣợc tìm ra ý tƣởng thực hiện 50000 tỷ phép mã hóa cần thiết để vƣợt mặt DES bằng cách thử lần lƣợt các khóa có thể là điếu không thể làm đƣợc nhƣng ngày nay với sự phát triển mạnh của phần cứng liệu độ dài 56 bit đã đủ chƣa? Và các phép thay thế đã đủ phức tạp chƣa ? để đạt đƣợc độ an toàn thông tin nhƣ mong muốn, đó là vấn đề ngƣời ta vẫn đang bàn luận. Tuy vậy, DES đã đƣợc phân tích kĩ lƣỡng và công nhận là vững chắc. Các hạn chế của nó đã đƣợc hiểu rõ và có thể xem xét trong quá trình thiết kế và để tăng độ an toàn hơn, ngày nay các hệ thống ma hóa sử dụng DES mở rộng ( 3DES ), đƣợc ứng dụng rộng dãi. Với DES mở rộng khóa có thể là 128 bit, độ lớn khối có thể là 128 bit. Do vậy độ an toàn mở rộng của DES cao hơn rất nhiều. Đỗ Thị Phƣơng- CT1301 Page 37
  38. Đồ án tốt nghiệp Trƣờng DHDL Hải Phòng CHƢƠNG 3. CÁC SƠ ĐỒ CHIA SẺ BÍ MẬT 3.1 Khái niệm về chia sẻ bí mật Thông tin cần giữ bí mật đƣợc chia thành nhiều mảnh và giao cho nhiều ngƣời, mỗi ngƣời giữ một mảnh. Thông tin này có thể đƣợc xem lại, khi mọi ngƣời giữ các mảnh nhất trí. Các mảnh khớp lại để đƣợc tin gốc. - Thông tin cần giữ bí mật đƣợc chia thành nhiều mảnh và trao cho mỗi thành viên tham gia nắm giữ. Thông tin bí mật Các mảnh đƣợc chia - - Khi các mảnh đƣợc khớp lại sẽ cho ta thông tin gốc. Các mảnh đƣợc chia Thông tin bí mật Đỗ Thị Phƣơng- CT1301 Page 38
  39. Đồ án tốt nghiệp Trƣờng DHDL Hải Phòng 3.2 Sơ đồ chia sẻ bí mật Bài toán: Trong một ngân hàng có một két phải mở hằng ngày. Ngân hàng sử dụng 3 thủ quỹ lâu năm nhƣng họ không tin bất kì ngƣời nào. Bởi vậy họ cần thiết kế một hệ thống sao cho bất kì 2 thủ quỹ nào cũng không thể mở đƣợc két song riêng từng ngƣời một thì không thể mở đƣợc. Vấn đề này có thể đƣợc giải quyết đƣợc bằng lƣợc đồ chia sẻ bí mật. 3.2.1 Khái niệm “ sơ đồ chia sẻ bí mật”: Sơ đồ chia sẻ bí mật là một phƣơng thức để chia sẻ bí mật ra nhiều phần sau đó phân phối cho một tập hợp những ngƣời tham gia sao cho các tập con trong số những ngƣời nay đƣợc chỉ thị, có khả năng khôi phục lại bí mật bằng cách kết hợp dữ liệu của họ. Một sơ đồ chia sẻ bí mật là hoàn hảo, nếu bất kì một tập hợp những ngƣời tham gia mà không đƣợc chỉ định, sẽ không thu đƣợc thông tin về bí mật. 3.2.2 Định nghĩa: Cho t, w là các số nguyên dƣơng t ≤ w. Một sơ đồ ngƣỡng A(t,w) là một phƣơng pháp phân chia khóa k cho một tập w thành viên (kí hiệu là P) sao cho t thành viên bất kì có thể tính đƣợc k nhƣng không một nhóm (t-1) thành viên nào có thể làm đƣợc điều đó. Giá trị k đƣợc chọn bởi một thành viên đặc biệt đƣợc gọi là ngƣơi phân phối (D). D P . D phân chia khóa k cho mỗi thành viên trong P bằng cách cho mỗi thành viên một thông tin cục bộ gọi là mảnh. Các mảnh đƣợc phân phát một cách bí mật để không thành viên nào biết đƣợc mảnh đƣợc trao cho mỗi thành viên khác. Một tập con các thành viên B P sẽ kết hợp các mảnh của họ để tính khóa k (cũng có thể trao các mảnh của mình cho một ngƣời đáng tin cậy để tính khóa hộ). Nếu |B| ≥ t thì họ có khả năng tính đƣợc k. Nếu |B| ≤ t thì không thể tính đƣợc k. Gọi P là tập các giá trị đƣợc phân phối khóa K: P = { pi: 1≤ i≤ w} K là tập khóa: tập tất cả các khóa có thể. S tập mảnh: tập tất cả các mảnh có thể. Sau đây ta trình bày một sơ đồ ngƣỡng đƣợc gọi là sơ đồ ngƣỡng Shamir. Đỗ Thị Phƣơng- CT1301 Page 39
  40. Đồ án tốt nghiệp Trƣờng DHDL Hải Phòng Giai đoạn khởi tạo: 1. D chọn w phần tử khác nhau và khác 0 trong Zp và kí hiệu chúng là: xi , 1≤ i ≤ w (w ≥ p+1). Với 1≤ i ≤ w, D cho giá trị xi cho pi .Các giá trị xi là công khai. Phân phối mảnh: 2. Giả sử D muốn phân chia khóa k Zp. D sẽ chọn một cách bí mật (nhẫu nhiên và độc lập) t-1 phần tử Zp, ai ai-1 3. Với 1 ≤ i ≤ w, D tính yi = a (xi), trong đó a(x) = k+ 4. Với 1 ≤ i ≤ w, D sẽ trao mảnh yi cho pi Hình 3.1 : Sơ đồ ngƣỡng Shamir Trong sơ đồ 3.1 D xây dựng một đa thức ngẫu nhiên a(x) có bậc tối đa là t-1. Trong đa thức này hằng số là khóa k. Mỗi thành viên pi sẽ có một điểm (xi,, yi). Ta xét một tập con B gồm t thành viên tạo lại khóa k bằng 2 phƣơng pháp: Phép nội suy đa thức Công thức nội suy Lagrange Tạo lại khóa k bằng phƣơng pháp sử dụng phép nội suy đa thức: Giả sử các thành viên pi , muốn xác định khóa k. Ta biết rằng: yti = a(xi). trong đó a(xi) là một đa thức bí mật đƣợc D chọn. Vì a(x) có bậc lớn nhất là t-1 nên ta có thể viết nhƣ sau: i-1 a(x) = a0 + a1x+ +ai-1x Ta có hệ các phƣơng trình tuyến tính (trong Zp) nhƣ sau: t-1 a0 + a1xi1 +a2x +at-1xit1 = yi1 t-1 a0 + a1xi2 +a2xi2 +at-1xit = yi2 t-1 a0 + a1xi1 +a2xit +at-1xitt = yit Trong đó hệ số a0, a1, . at-1 là các phần tử chƣa biết của Zp , còn a0 = K là khóa. Vì yi = a(xi) nên B có thể thu đƣợc t phƣơng trình tuyến tính t ẩn (a0, a1, .at-1), ở đây tất cả các phép tính số học đều đƣợc thực hiện trên Zp. Đỗ Thị Phƣơng- CT1301 Page 40
  41. Đồ án tốt nghiệp Trƣờng DHDL Hải Phòng Nếu các phƣơng trình này độc lập tuyến tính thì sẽ cho ta nghệm duy nhất và thu đƣợc giá trị khóa a0. Sau đây chúng tôi trình bày một thủ tục (protocol) chia sẻ bí mật dựa trên ý tưởng của Languange: Giá sử ta có n thực thể A1 ,A2, An và có một ngƣời ủy quyền B biết đƣợc toàn bộ khóa bí mật SєN. Ngƣời đƣợc ủy quyền B thực hiện các bƣớc sau đây: 1. B chọn 1 số nguyên tố P đủ lớn sao cho: n << √p. Với SєZp. 2. B, tiếp theo, chọn 2n-1 số một cách ngẫu nhiên: a1, a2, ., an-1 v0, v1, ., vn-1 trong đó: vi ≠ 0, vi ≠ vj, i≠ j 3. B xác định một đa thức với các hệ số a1, a2, ., an-1 trên Zp: n-1 n-2 f(x) = an-1x + an-2x + +a1x + s (mob P) 4. Bây giờ B gửi cho Aj một cách công khai cặp (vj ,f(vj)) với j = 0,1,2, .n-1 coi nhƣ là một mảnh riêng của Aj Khôi phục bí mật S: Tất cả n ngƣời A1 ,A2, An có thể hợp tác lại để khôi phục lại bí mật S bằng cách tính: . (3.1) Khi đó dễ dàng xác định đƣợc S = g(0) Ta có định lí sau: n thực thể kết hợp với nhau thì có thể khôi phục bí mật S một cách có hiệu quả đó là: S= g(0) = f(0) Chứng minh: Thật vậy, dễ thấy rằng g(x) là hàm nội suy Lagrange của hàm f(x) là một đa thức có cấp bé hơn n và g thỏa mãn điều kiện: g(vj) = f(vj) với 0≤ j≤ n Do đó, f-g là đa thức trên Zp có cấp bé hơn n, nhƣng nó lại có ít nhất n nghiệm khác nhau: là các số r thỏa mãn f(r)- g(r) = 0. Chứng tỏ rẳng: f(a)= g(a) a Zp, đặc biệt f(0) = g(0) = S đó là điều cần chứng minh. Sau đây tôi xin lấy một số ví dụ cụ thể: Ví dụ 1: Co 3 ngƣời A1 ,A2,A3 muốn chia sẻ bí mật S = 472 Cho p=1999 công khai. A chọn v0 = 626，v1 = 674，v0 = 93 a1 = 334, a2 = 223 Đỗ Thị Phƣơng- CT1301 Page 41
  42. Đồ án tốt nghiệp Trƣờng DHDL Hải Phòng 2 tính f(vj) = a2 vj + a1 vj + S mob p Áp dụng công thức trên với S = 472 ta có: f(v0) = 1724 f(v1) = 1925 f(v2) = 1241 A1 có cặp (v0, f(v0)) = (626, 1724) A1 có cặp (v1, f(v1)) = (674, 1925) A3 có cặp (v2, f(v2)) = (93, 1241) Ba ngƣời hợp lại sẽ xác định đƣợc S: S= . Với bj = (3.2) Áp dụng công thức (3.2) trên ta tính đƣợc: b0= 1847 b1 = 1847 b2 = 1847 S= . Ví dụ 2: Cho số p=342853815608923 (Đây là một số nguyên tố đƣợc lấy trong bảng các số nguyên tố từ cuốn “ The Art of Programing” của Knut vol2). n=3, ta có: a1= 53958111706386 a2= 151595058245452 v0=111350135012507 v1=207244959855905 v2=20545949133543 Giá sử bí mật là S= 151595058245452 Tính f(v0)=109351520587519 f(v1)=174675701531216 f(v2)=117471713218253 Đặt bj = Ta có: S= b0 = 266921901220910 b1 = 129147516050688 b2 = 289638215946249 Ta tính đƣợc S‟ = 151595058245452. S‟ trùng với khóa bí mật đã cho. Đỗ Thị Phƣơng- CT1301 Page 42
  43. Đồ án tốt nghiệp Trƣờng DHDL Hải Phòng 3.3 Cấu trúc truy nhập và sơ đồ chia sẻ bí mật Trong phần trƣớc ta mong muốn rằng t thành viên bất kì trong w thành viên có khả năng xác định đƣợc khóa. Tình huống tổng quát hơn là phải chỉ rõ một các chính xác các thành viên có khả năng xác định khóa và những tập con không có khả năng này. Ký hiệu: - P là tập gồm m thành viên đƣợc chia mảnh công khai xi. - Г là một tập các tập con của P, các tập con trong Г là các tập con các thành viên có khả năng tính khóa. Г đƣợc gọi là một cấu trúc truy nhập Các tập con trong Г đƣợc gọi là các tập con hợp thức. Ví dụ: Chìa khóa để mở két bạc là chìa khóa số đƣợc chia thành 3 mảnh khóa, có 3 thủ quỹ là P1 , P2 ,P3. Mỗi thủ quỹ giữ một mảnh khóa. Chỉ có thủ quỹ P1 và P2 hoặc P2 và P3 khi khớp 2 mảnh khóa của họ với nhau thì sẽ nhận đƣợc chìa khóa gốc để mở két bạc. Các tập con hợp thúc là các tập con có thể mở khóa: { P1 ,P2 },{ P2 ,P3}. Vậy Г là: { P1 ,P2 },{ P2 ,P3}. 3.3.1 Định nghĩa sơ đồ chia sẻ bí mật hoàn thiện Một sơ đồ chia sẻ bí mật hoàn thiện thể hiện cấu trúc truy nhập Г là phƣơng pháp chia sẻ khóa K cho một tập w thành viên (đƣợc kí hiệu là P) thỏa mãn 2 tính chất sau: 1. Nếu một tập con hợp thức các thành viên B P góp chung các mảnh của họ thì họ có thể xác định đƣợc giá trị của K. 2. Nếu một tập con không hợp thức các thành viên B P góp chung các mảnh của họ thì họ không thể xác định đƣợc khóa k. Ví dụ: Trong sơ đồ Samir A(t, m) thể hiện cấu túc truy nhập sau: Г = {B P : /B/} Vậy sơ đồ Samir là sơ đồ chia sẻ bí mật hoàn thiện. Chú ý: “Tập trên” của một “tập hợp thức” sẽ là “tập hợp thức” Giả sử B Г và B C P, giả sử tập con C muốn K Đỗ Thị Phƣơng- CT1301 Page 43
  44. Đồ án tốt nghiệp Trƣờng DHDL Hải Phòng Vì B là một tập con hợp thức nên nó có thể xác định đƣợc K. Tập con C có thể xác định đƣợc khóa K bằng cách bỏ qua các mảnh (tin) của các thành viên trong B, C. Tức là: Nếu B Г và B C P thì C Г. 3.3.2 Định nghĩa tập hợp thức tối thiểu Nếu Г là một cấu trúc truy nhập thì B Г đƣợc gọi là “tập hợp thức” tối thiểu nếu: A B, A≠ B thì A≠ Г. Nói cách khác B là tập hợp thức nhỏ nhất trong Г. Tập các tập con hợp thức tối thiểu của Г kí hiệu là Г0 và đƣợc gọi là cơ sở của Г. Vì Г chứa tất cả các tập con của P là tập trên của một tập con trong cơ sở Г0 nên Г đƣợc xác định một cách duy nhất nhƣ một hàm của Г0. Biểu diễn về mặt toán học ta có: Г = {C P; B C, B Г0} 3.4 Mạch đơn điệu Một phƣơng pháp đẹp và đơn giản về mặt khái niệm do Benaloh và Leichter đƣa ra. Ý tƣởng của nó là xây dựng một mạch đơn điệu “ghi nhận” cấu trúc truy nhập và sau đó xây dựng một sơ đồ chia sẻ bí mật trên cơ sở xây dựng mô tả về mạch. Ta gọi đó là cấu trúc mạch đơn điệu. 3.4.1 Định nghĩa mạch đơn điệu Một mạch Bolean C với w đầu vào x1 , xw ( tƣơng ứng với w thành viên P1 , Pw ) và một đầu ra y. Mạch này gồm các cổng “hoặc” và các cổng “và” không có bất kì một cổng “phủ định” nào một mạch nhƣ vậy gọi là mạch đơn điệu. Mạch đƣợc ghép có số đàu vào tùy ý nhƣng chỉ có một đầu ra ( tức là một cổng có thể có nhiều dây vào nhƣng chỉ có một dây ra). Xây dựng mạch đơn điệu: Nếu Г là một mạch đơn điệu các tập con của P thì dễ dàng xây dựng đƣợc một mạch đơn điệu C sao cho Г(C) = Г. Giả sử Г0 là cơ sở của Г khi đó ta xây dựng công thức Bolean dạng tuyển hội sau: C = B Г0 (^ Pi BPi) Đỗ Thị Phƣơng- CT1301 Page 44
  45. Đồ án tốt nghiệp Trƣờng DHDL Hải Phòng Ví dụ: Nếu trong tập các thành viên { P1 , P2 , P3 } có tập cơ sở: Г0 ={{ P1 ,P2 },{ P2 ,P3}}. Ta thu đƣợc công thức Bolean sau: C = ( P1^P2 ) ^ ( P2 P3) 3.4.2 Chia sẻ khóa bí mật dựa vào “mạch đơn điệu” Thuật toán thực hiện phép gán một giá trị f(W) K cho mỗi dây W trong mạch C. Đầu tiên, dây ra Wout của mạch sẽ đƣợc gán giá trị khóa K. Thuật toán sẽ đƣợc lặp lại một số lần cho đến khi mỗi dây có một giá trị gán vào nó. Cuối cùng, mỗi thành viên Pi sẽ đƣợc một danh sách các giá trị f(W) sao cho W là một dây vào của mạch có đầu vào xi. Thuật toán chia sẻ khóa K: 1. F(Wout) =K 2. While tồn tại một dây W sao cho f(W) không xác định DO Begin 3. Tìm cổng G của C sao cho f (Wg) đƣợc xác định, Wg là dây ra của G nhƣng f(W) không đƣợc xác định với bất kì dây nào của G. 4. If G là cổng “hoặc” Then f(W) = f(Wg) với mỗi dây vào W của G Else (G là cổng “và”) Cho các dây vào của G là W1 Wt Chọn độc lập, ngẫu nhiên t-1 phần tử của Zm và kí hiệu chúng là: Yg1 , .Ygt-1 End; 5. For 1≤ i≤ m Do f(Wi) = Yg Ví dụ: Giả sử K là khóa. Giá trị K sẻ đƣợc đƣa tới mỗi một trong 3 đầu vào của cổng “hoặc” cuối cùng. Tiếp theo ta xét cổng “và” ứng với mệnh đề P1 ^ P2 ^ P4 . Ba dây vào sẽ đƣợc gán các gía trị tƣơng ứng là: a1, a2, k – a1 – a2 ở đây tất cả các phép tính đều đƣợc thực hiện trên Zm. Tƣơng tự 3 dây vào tƣơng ứng với P1 ^ P3 ^ P4 sẽ đƣợc gán các giá trị b1, b2, k – b1 – b2. Cuối cùng 2 dây vào tƣơng ứng với P2 ^ P3 sẽ đƣợc gán các giá trị c1, k –c1. Chú ý rằng a1, a2, b1, b2 và c1 đều là các biến Đỗ Thị Phƣơng- CT1301 Page 45
  46. Đồ án tốt nghiệp Trƣờng DHDL Hải Phòng ngẫu nhiên độc lập trong Zm. Nếu nhìn vào các mảnh mà 4 thành viên nhận đƣợc thì ta có: 1. P1 nhân a1, b1 2. P2 nhân a2, c 1 3. P3 nhân b2, K-c 1 4. P4 nhân K- a1 - a2, K- b1 – b2 5. Nhƣ vậy mỗi thành viên sẽ nhận 2 phân tử trong Zm làm mảnh của mình. x1 x2 x3 x4 K - c1 a1 a2 b2 K-b1 -b c1 ^ K- a1 - a1 ^ ^ K K K ^ K Hình 3.2 Một mạch đơn điệu Ta sẽ chứng tỏ rằng sơ đồ này là hoàn thiện. Trƣớc tiên ta kiểm tra thấy rằng mỗi tập con cơ sở có thể tính đƣợc k. Tập con hợp thức {P1, P2 , P4} có thể tính : k = a1 + a2 +( k – a1 – a2 ) mob m Tập con {P1, P3 , P4} có thể tính: k= b1 + b2 +( k – b1 – b2 ) mob m Cuối cùng tập con {P2, P3 } có thể tính: K = c1 + (k – c1) mob m Đỗ Thị Phƣơng- CT1301 Page 46
  47. Đồ án tốt nghiệp Trƣờng DHDL Hải Phòng Nhƣ vậy, mọi tập con hợp thức đều có thể tính đƣợc k, do đó ta sẽ hƣớng sự chú ý tới các tập con không hợp thức. Chẳng hạn, nếu B2 và B2 là 2 tập con không hợp thức (B1 B2) và B2 không thể tính đƣơc k thì B1 cũng không thể tính đƣợc k. Ta định nghĩa tập con B P là một tập con không hợp thức tối đa nếu B1 P đối với mọi B1 B, B1 ≠ B. Điều này dẫn đến kết luận là chỉ cần kiểm tra thấy không một tập con không hợp thức nào có thể xác định đƣợc một chút thông tin nào về khóa k là đƣợc. Ở đây các tập con không hợp thức tối đa là: {P1, P2}, {P1, P3}, {P1, P4}, {P2 , P4}, {P3, P4}. Trong mỗi trƣờng hợp, dễ dàng thấy đƣợc k không thể tính đƣợc, hoặc do thiếu một mảnh thông tin ngâu nhiên cần thiết nào đó hoặc do tất cả các mảnh có từ một tập con ngẫu nhiên. Ví dụ tập con {P1, P2 } chỉ có các giá trị ngẫu nhiên a1, b1, a2, c1. Một ví dụ khác, tập con {P3, P4 } có mảnh b2 , k – c1, k -a1 - a2 , k -b1 - b2. Vì các giá trị c1 ,a2,a1 và b1 là các giá trị ngẫu nhiên chƣa biết nên k không thể tính đƣợc, trong mỗi trƣờng hợp có thể mỗi tập con không hợp thức đều không có chút thông tin gì về giá trị của k. Đỗ Thị Phƣơng- CT1301 Page 47
  48. Đồ án tốt nghiệp Trƣờng DHDL Hải Phòng CHƢƠNG 4. ỨNG DỤNG THUẬT TOÁN DES VÀ LƢỢC ĐỒ CHIA SẺ BÍ MẬT VÀO THI TUYỂN SINH 4.1 Các ứng dụng Ta có thể áp dụng thuật toán DES và sơ đồ chia sẻ bí mật vào rất nhiều ứng dụng chẳng hạn trong đấu thầu từ xa, trong mã thẻ ATM, trong thi tuyển sinh Ở đây ta nghiên cứu một ứng dụng là trong thi tuyển sinh, vậy có một bài toán đƣợc đƣa ra là: Trong một kì thi, nơi ra đề thi và nơi tổ chức thi ở cách xa nhau, ta phải thực hiện việc chuyển đề thi từ nơi ra đề tới nơi tổ chức thi trên mạng máy tính sao cho đảm bảo về tính bảo mật. 4.2 Quy trình thực hiện giải bài toán 4.2.1 Sơ đồ Khóa k Đ ề thi (B ả n rõ) Nơi ra đề thi Mã hóa Mã hóa B ả n mã ( n thực thể nhận) Giải mã B ả n rõ Nơi ra đề thi Đỗ Thị Phƣơng- CT1301 Page 48
  49. Đồ án tốt nghiệp Trƣờng DHDL Hải Phòng Khóa DES gồm 56 bit, tƣơng đƣơng với một số nguyên gồm 20 chữ số thập phân. Con số bí mật nay không quá lớn đối với bài toán chia sẻ bí mật. Cho nên việc tính toán là rất hiệu quả. 4.2.2 Các bước thực hiện Theo sơ đồ trên ta phải thực hiện theo các bƣớc sau: - Nơi ra đề thi: . Bản rõ (đề thi) . Mã hóa bản rõ . Tạo khóa k . Mã hóa khóa k . Gửi bản mã - Nơi tổ chức thi: . Nhận bản mã và cặp ( . Giải bản mã ( sau khi nhận đủ các cặp khác từ ngƣời ra đề thi để xác định đƣợc khóa K). Mã hóa bản rõ (đề thi): Bộ giáo dục dùng bảng mã ASCII mở rộng để chuyển bản rõ từ dạng kí tự sang Hexa sau đó dùng thuật toán DES để mã hóa. Tạo khóa k: Dùng dãy kí tự dạng chữ hoặc dạng số, nhóm 8 kí tự thành 1 nhóm sau đó dùng 56 bit để mã hóa. Gửi bản tin: Dựa vào lƣợc đồ chia sẻ bí mật chia khóa k thành 2 mảnh rời nhau k1, k2 : k1 + k2 = k. Sau đó gửi k1 cho n thực thể (các địa chỉ thi). Quy định đến đúng giờ G vụ Đào tạo gửi nốt k2 cho n thực thể đó trên cơ sở k1, k2. Tất cả các nơi đều mở đƣợc đề và trao cho học sinh hoặc gửi cho học sinh thông qua máy tính để làm (qua mail đồng thời). Sau đây là chƣơng trình mô phỏng “chia sẻ bí mật bằng ngôn ngữ C”. 4.2.3 Mô phỏng lược đồ chia sẻ bỉ mật bằng ngôn ngữ C: Chƣơng trình gồm có 5 phần: Đỗ Thị Phƣơng- CT1301 Page 49
  50. Đồ án tốt nghiệp Trƣờng DHDL Hải Phòng Hình 4.1 Giao diện chƣơng trình 4.2.3.1 Chia sẻ khóa bí mật theo giao thức “chia sẻ bí mật” Shamir. void giaothuc::chiakhoa() { int h; cout >k; cout >p; cout >m; cout >t; cout >x[i]; } cout<<”\n Nhap bi mat t-1 phan tu trong Zp”; for(j=1;j<t;j++) Đỗ Thị Phƣơng- CT1301 Page 50
  51. Đồ án tốt nghiệp Trƣờng DHDL Hải Phòng { cout >a[j]; } for(i=1;i<m;i++) { l=0; for(j=1;j<t;j++) h=pow(x[i],j); l=l+a[j]*h; } y=k+l; cout<<”\n Manh y”<<i<<” trao cho thanh vien P”<<i<<” la:”<<y; } } Đỗ Thị Phƣơng- CT1301 Page 51
  52. Đồ án tốt nghiệp Trƣờng DHDL Hải Phòng Hình 4.2 và 4.3 Chia sẻ khóa bí mật theo giao thức Shamir 4.2.3.2 Khôi phục khóa bí mật bằng phương pháp giải hệ phương trình tuyến tính void giaothuc::giaihekhoiphuckhoa() { int n,m,v,b; float mx=0, g,e,c,gt,h; Đỗ Thị Phƣơng- CT1301 Page 52
  53. Đồ án tốt nghiệp Trƣờng DHDL Hải Phòng float G[max] [max] [max], H[max] [max], A[max] [max], B[max] [max], M[max] [max]; cout > p; cout >n; cout >x[j]; } cout > B[l][0]; } for(i=0;i<n;i++) { for(j=0;j<n; j++) { A[i][j]=pow(x[i],j); } } cout<<” He Phuong trinh tuyen tinh la:\n”; for(i=0; i<n; i++) { for(j=0; j<n; j++) { If(j<n-1) { Đỗ Thị Phƣơng- CT1301 Page 53
  54. Đồ án tốt nghiệp Trƣờng DHDL Hải Phòng cout<<”A[i][j]<<”a”<<j<<”+”; } If(j==n-1) { cout<<A[i][j]<<”a”<<j; } } cout<<”=”<<B[i][j]; cout<<”\n; } cout<<”\n Vay nghiem cua he Phuong trinh la:”; for(e=0; e<n; e++) { for(i=0; i<n; i++) { for(j=0; j<n; j++) { G[i][j]=A[i][j]; } } for(j=0; j<n; j++) { If(j==e-1) { for(i=0; i<n; i++) { G[i][j]= B[i][0]; Đỗ Thị Phƣơng- CT1301 Page 54
  55. Đồ án tốt nghiệp Trƣờng DHDL Hải Phòng } } } i=0; t=0; while(t mx) { mx=G[i][j]; v=j; } for(j=0; j<n; j++) { G=G[i][j]; G[i][j]=-G[v][j]; G[v][j]=g; } } If(G[i][i]!=0) { for(k=i+1; k<n; k++) { c=G[k][i]/ G[i][i]; h=c+(G[k][i]-c*G[i][i])/ G[i][i]; for(j=0; j<n; j++) Đỗ Thị Phƣơng- CT1301 Page 55
  56. Đồ án tốt nghiệp Trƣờng DHDL Hải Phòng { G[k][j]=G[k][j]*h; } } i++; } t=t+1; } gt=1; for(i=0; i 0) { cout<<”\n a”<<e<<”=”<<b; If(e==1) { cout<<”\n Khoa dc khoi phuc lai la:K= al=”<<b; } Đỗ Thị Phƣơng- CT1301 Page 56
  57. Đồ án tốt nghiệp Trƣờng DHDL Hải Phòng } } } } Hình 4.4 và 4.5 Khôi phục khóa bí mật bằng phƣơng pháp giải hệ phƣơng trình tuyến tính Đỗ Thị Phƣơng- CT1301 Page 57
  58. Đồ án tốt nghiệp Trƣờng DHDL Hải Phòng 4.2.3.3 Khôi phục khóa bí mật bằng phương pháp dùng công thức nội suy Lagrange void giaothuc::congthuckhoiphuckhoa() { float n,m,b; cout >p; cout >t; cout >x[j]; } cout >g[j]; } k=0; for(l=1; l<=t; l++) { m=1; for(j=1; j<=t; j++) { if(j!=1) { b=x[j] – x[l]; n=x[j]/b; m=m*n; } } Đỗ Thị Phƣơng- CT1301 Page 58
  59. Đồ án tốt nghiệp Trƣờng DHDL Hải Phòng k=k+g[l]*m; } cout<<”\n Vay khoa bi mat khoi phuc lai la:”<<k; } Hình4. 6 và 4.7 Khôi phục khóa bí mật bằng phƣơng pháp dùng công thức nội suy Lagrange Đỗ Thị Phƣơng- CT1301 Page 59
  60. Đồ án tốt nghiệp Trƣờng DHDL Hải Phòng 4.2.3.4 Chia sẻ khóa bí mật theo phương pháp bằng mạch đơn điệu void giaothuc::machchiakhoa() { int n,m h[max],e; char ten[32]; cout >m; cout >k; cout >n; for(j=1; j >t; cout >h[i]; } cout<<”\n Nhap ten thanh vien thu”<<t<<” la:”; gets(ten); for(i=1; i<t; i++) { e=k – h[i]; } cout<<”\n Manh khoa trao cho tung thanh vien thu”<<t<<” trong hop thuc la:\n”<<e; } } Đỗ Thị Phƣơng- CT1301 Page 60
  61. Đồ án tốt nghiệp Trƣờng DHDL Hải Phòng Hình 4.8 và 4.9 Chia sẻ bí mật bằng mạch đơn điệu 4.2.3.5 Khôi phục khóa bí mật theo phương pháp mạch đơn điệu void giaothuc::machphuckhoa() { int h; cout >t; cout<<”\n Nhap cac manh khoa da trao cho moi thanh vien P:”; Đỗ Thị Phƣơng- CT1301 Page 61
  62. Đồ án tốt nghiệp Trƣờng DHDL Hải Phòng for(j=0; j >g[j]; } h=0; for(j=0; j #include #include Đỗ Thị Phƣơng- CT1301 Page 62
  63. Đồ án tốt nghiệp Trƣờng DHDL Hải Phòng #include Const int max=30; class giaothuc { Private: int m, t, y, p; float k; int x[max], a[max], g[max]; int i, j, l; Public: void chiakhoa(); void giaihekhoiphuckhoa(); void congthuckhoiphuckhoa(); void machchiakhoa(); void machphuckhoa(); }; ////////////////////////////////////////////////////////// void giaothuc::chiakhoa() { int h; cout >k; cout >p; cout >m; cout >t; cout<<”\n Nhap gia tri xi de trao cho moi thanh vien p:”; for(i=1; i<=m; i++) { Đỗ Thị Phƣơng- CT1301 Page 63
  64. Đồ án tốt nghiệp Trƣờng DHDL Hải Phòng cout >x[i]; } cout >a[j]; } for(i=1; i >p; cout >n; Đỗ Thị Phƣơng- CT1301 Page 64
  65. Đồ án tốt nghiệp Trƣờng DHDL Hải Phòng cout >x[j]; } cout >B[l][0]; } for(i=0; i<n; i++) { for(j=0; j<n; j++) { A[i][j]=pow(x [i],j); } } cout<<”\n he Phuong trinh tuyen tinh la:\n”; for(i=0; i<n; i++) { for(j=0; j<n; j++) { If(j<n-1) { cout<<A[i][j]<<”a”<<j<<”+”; } If(j==n-1) Đỗ Thị Phƣơng- CT1301 Page 65
  66. Đồ án tốt nghiệp Trƣờng DHDL Hải Phòng { cout<<A[i][j]<<”a”<<j; } } cout<<”=”<<B[i][0]; cout<<”\n”; } cout<<”\n Vay nghiem cua he Phuong trinh la:”; for(e=0; e<=n; e++) { for(i=0; i<n; i++) { for(j=0; j<n; j++) { G[i][j] = A[i][j]; } } for(j=0; j<n; j++) { If(j==e-1) { for(i=0; i<n; i++) { G[i][j] = B[i][j]; } } } Đỗ Thị Phƣơng- CT1301 Page 66
  67. Đồ án tốt nghiệp Trƣờng DHDL Hải Phòng i=0; t=0; while(t mx) { mx= G[i][j]; v=j; } for(j=0; j<n; j++) { g=G[i][j]; G[i][j]= -G[v][j]; G[v][j]=g; } } If(G[i][j]!=0) { for(k=i+1; k<n; k++) { c=G[k][i]/G[i][i]; h=c + (G[k][i]-c*G[i][i])/G[i][i]; for(j=0; j<n; j++) { G[k][j]= G[k][j]- G[i][j]*h; Đỗ Thị Phƣơng- CT1301 Page 67
  68. Đồ án tốt nghiệp Trƣờng DHDL Hải Phòng } } i++; } t=t+1; } gt=1; for(i=0; i 0) {cout<<”\n a”<<e<<”=”<<b; if(e==1) { cout<<”\n Khoa duoc khoi phuc lai la k=al=”<<b; } } } } Đỗ Thị Phƣơng- CT1301 Page 68
  69. Đồ án tốt nghiệp Trƣờng DHDL Hải Phòng } //////////////////////////////////////////////// void giaothuc::congthuckhoiphuckhoa() { float m, n, b; cout >p; cout >t; cout >x[j]; { cout >g[j]; } k=0; for(l=1; l<=t; l++) { m=1; for(j=1; j<=t; j++) { if(j!=1) { b=x[j]- x[l]; n= x[j]/b; m=m*n; } } Đỗ Thị Phƣơng- CT1301 Page 69
  70. Đồ án tốt nghiệp Trƣờng DHDL Hải Phòng k=k+g[l]*m; } cout >t; cout >g[j]; } h=0; for(j=0; j >m; Đỗ Thị Phƣơng- CT1301 Page 70
  71. Đồ án tốt nghiệp Trƣờng DHDL Hải Phòng cout >k; cout >n; for(j=1; j >t; cout >h[i]; } cout<<”\n Nhap ten thanh vien thu”<<t<<” la:”; gets(ten); for(i=1; i<t; i++) { e=k – h[i]; } cout<<”\n Manh khoa trao cho tung thanh vien thu “<<t<<” trong hop thuc la:\n”<<e; } } /////////////////CHUONG TRINH CHINH///////////////////////////// void main() { Clrscr() int chon; giaothuc g; do { Đỗ Thị Phƣơng- CT1301 Page 71
  72. Đồ án tốt nghiệp Trƣờng DHDL Hải Phòng cout >chon; switch(chon) { case 1: clrscr(); g.chiakhoa(); break; case 2: clrscr(); g.giaihekhoiphuckhoa(); break; case 3: clrscr(); g.congthuckhoiphuckhoa(); break; case 4: clrscr(); g.machchiakhoa(); break; case 5: clrscr(); g.machphuckhoa(); break; } }while(chon!=0); getch(); } Đỗ Thị Phƣơng- CT1301 Page 72
  73. Đồ án tốt nghiệp Trƣờng DHDL Hải Phòng KẾT LUẬN Các ứng dụng trên mạng máy tính ngày càng trở lên phổ biến, thuận lợi và quan trọng thì yêu cầu về an toàn mạng, về an ninh dữ liệu càng trở lên cấp bách và cần thiết. Thuật toán mã hóa đƣợc ứng dụng trong rất nhiều lĩnh vực nhƣ: xác thực ngƣời dùng, chữ kí số, mã hóa và xác thực dữ liệu Kết quả của luận văn của em gồm 2 phần chính: 1. Tìm hiểu lí thuyết về mật mã Luận văn nghiên cứu lí thuyết về mật mã, thuật toán DES và lƣợc đồ chia sẻ bí mật. 2. Phần ứng dụng Luận văn đề cập đến vấn đè ứng dụng thuật toán DES và lƣợc đồ chia sẻ bí mật vào thi tuyển sinh. Mô phỏng lƣợc đồ chia sẻ bí mật bằng ngôn ngữ lập trình C. Hạn chế luận văn đề cập tới phần lí thuyết nhiếu hơn những ứng dụng. Phần ứng dụng chƣa đƣợc áp dụng trong thực tế do đó không thể tránh khỏi những thiếu sót, rất mong đƣợc sự góp ý của độc giả để luận văn của tôi đƣợc hoàn thiện hơn. Đỗ Thị Phƣơng- CT1301 Page 73
  74. Đồ án tốt nghiệp Trƣờng DHDL Hải Phòng TÀI LIỆU THAM KHẢO Tiếng Việt: 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. 2. Lê Thị Sinh (2010) Nghiên cứu một số mô hình đảm bảo an ninh cơ sở dữ liệu và thử nghiệm ứng dụng, luaận ăn thạc sĩ Công nghệ thông tin, tr 28-25, Trƣờng Đại học công nghệ - Đại học Quốc gia Hà Nội. 3. Dƣơng Anh Đức (2008) Mã hóa và ứng dụng. Nhà xuất bản Đại học Quốc gia TPHCM. 4. Nguyễn Viết Kính (2007) Mã hóa. Bài giảng cho học viên cao học Trƣờng Đại học Quốc gia Hà Nội. 5. Bảo mật thông tin, mô hình và ứng dụng, Nguyễn Xuân Dũng, 2007, Nhà xuất bản thông kê. 6. Douglas (1994) Mật mã lí thuyết và thực hành. Ngƣời dịch Nguyễn Bình. Đỗ Thị Phƣơng- CT1301 Page 74