Đồ á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

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 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 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 BỘ GIÁO DỤC VÀ ĐÀO TẠO TRƢỜNG ĐẠI HỌC DÂN LẬP HẢI PHÒNG CỘNG HÒA XA HỘI CHỦ NGHĨA VIỆT NAM Độ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. 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. Đồ án tốt nghiệp Trƣờng DHDL Hải Phòng Đỗ Thị Phƣơng- CT1301 Page 6 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 Sinh viên Đã nhận nhiệm vụ: Đ.T.T.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ị Đồ án tốt nghiệp Trƣờng DHDL Hải Phòng Đỗ Thị Phƣơng- CT1301 Page 7 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ữ ) Đồ án tốt nghiệp Trƣờng DHDL Hải Phòng Đỗ Thị Phƣơng- CT1301 Page 8 ........................................................................................................................ ........................................................................................................................ ........ Ngày.......tháng.........năm 2013 Cán bộ hƣớng dẫn chính ( Ký, ghi rõ họ tên ) Đồ án tốt nghiệp Trƣờng DHDL Hải Phòng Đỗ Thị Phƣơng- CT1301 Page 9 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 ) Đồ án tốt nghiệp Trƣờng DHDL Hải Phòng Đỗ Thị Phƣơng- CT1301 Page 10 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 Đồ án tốt nghiệp Trƣờng DHDL Hải Phòng Đỗ Thị Phƣơng- CT1301 Page 11 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 Đồ án tốt nghiệp Trƣờng DHDL Hải Phòng Đỗ Thị Phƣơng- CT1301 Page 12 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. Đồ án tốt nghiệp Trƣờng DHDL Hải Phòng Đỗ Thị Phƣơng- CT1301 Page 13 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. Đồ án tốt nghiệp Trƣờng DHDL Hải Phòng Đỗ Thị Phƣơng- CT1301 Page 14 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. Đồ án tốt nghiệp Trƣờng DHDL Hải Phòng Đỗ Thị Phƣơng- CT1301 Page 15 Hình 1.1 là một ví dụ về một kênh liên lạc x y x k k k k 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ị C Bộ mã hóa Bộ giải mã A B Kênh an toàn Nguồn khóa Đồ án tốt nghiệp Trƣờng DHDL Hải Phòng Đỗ Thị Phƣơng- CT1301 Page 16 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). Đồ án tốt nghiệp Trƣờng DHDL Hải Phòng Đỗ Thị Phƣơng- CT1301 Page 17 3. Áp dụng phép hoán vị ngƣợc IP-1 cho xâu bit R16L16 ta thu đƣợc bản mã y.Tức là y = IP-1(R16 L16). A J 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 Ki Li-1 Ri-1 Li Ri f + Đồ án tốt nghiệp Trƣờng DHDL Hải Phòng Đỗ Thị Phƣơng- CT1301 Page 18 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