›

Đồ án Vấn đề chia sẻ bí mật và ứng dụng trong bỏ phiếu điện tử

pdf 72 trang huongle 1780
Download
Bạn đang xem 20 trang mẫu của tài liệu "Đồ án Vấn đề chia sẻ bí mật và ứng dụng trong bỏ phiếu điện tử", để 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_van_de_chia_se_bi_mat_va_ung_dung_trong_bo_phieu_dien.pdf

Nội dung text: Đồ án Vấn đề chia sẻ bí mật và ứng dụng trong bỏ phiếu điện tử

  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 VẤN ĐỀ CHIA SẺ BÍ MẬT VÀ ỨNG DỤNG TRONG BỎ PHIẾU ĐIỆN TỬ ĐỒ ÁN TỐT NGHIỆP ĐẠI HỌC HỆ CHÍNH QUY Ngành: Côngnghệ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 VẤN ĐỀ CHIA SẺ BÍ MẬT VÀ ỨNG DỤNG TRONG BỎ PHIẾU ĐIỆN TỬ ĐỒ ÁN TỐT NGHIỆP ĐẠI HỌC HỆ CHÍNH QUY Ngành: CôngnghệThông tin Sinhviênthựchiện: BÙI VĂN TIẾN Giáoviênhƣớngdẫn: PGS. TS TRỊNH NHẬT TIẾN Mãsốsinhviên: 1351010003 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 Độclập - Tự do - Hạnhphúc o0o NHIỆM VỤ THIẾT KẾ TỐT NGHIỆP Sinhviên: BÙI VĂN TIẾNMã SV: 1351010003 Lớp: CT1301Ngành: CôngnghệThông tin Tênđềtài: VẤN ĐỀ CHIA SẺ BÍ MẬT VÀ ỨNG DỤNG TRONG BỎ PHIẾU ĐIỆN TỬ
  5. NHIỆM VỤ ĐỀ TÀI 1. Nội dung vàcácyêucầucầngiảiquyếttrongnhiệmvụđềtàitốtnghiệp a. Nội dung - TìmhiểunghiêncứuvềVấnđề Chia sẻBímật. - TìmhiểumộtsốbàitoánAntoànthông tin trongBỏphiếuđiệntử. - ỨngdụngVấnđề chia sẻbímậttrongmộtsốbàitoántrên. b. Cácyêucầucầngiảiquyết - Tìmhiểuvàtrìnhbày 3 nội dung trên. - Thửnghiệmítnhất 1 chƣơngtrìnhđểgiảiquyếtmộtbàitoán.
  6. CÁN BỘ HƢỚNG DẪN ĐỀ TÀI TỐT NGHIỆP Ngƣờihƣớngdẫnthứnhất: Họvàtên:TrịnhNhậtTiến Họchàm, họcvị: PhóGiáoSƣ, TiếnSĩ Cơquancôngtác: TrƣờngĐạiHọcCôngNghệ, ĐạiHọcQuốcGiaHàNội Nội dung hƣớngdẫn: - TìmhiểunghiêncứuvềVấnđề Chia sẻBímật. - TìmhiểumộtsốbàitoánAntoànthông tin trongBỏphiếuđiệntử. - ỨngdụngVấnđề chia sẻbímậttrongmộtsốbàitoántrên. Ngƣờihƣớngdẫnthứhai: Họvàtên: . Họchàm, họcvị: . Cơquancôngtác: Nội dung hƣớngdẫn: Đềtàitốtnghiệpđƣợcgiaongàythángnăm 2013 Yêucầuphảihoànthànhtrƣớcngàythángnăm 2013 Đãnhậnnhiệmvụ: Đ.T.T.N Đãnhậnnhiệmvụ: Đ.T.T.N Sinhviên Cánbộhƣớngdẫn Đ.T.T.N PGS. TS TrịnhNhậtTiến HảiPhòng, ngày tháng năm 2013 HIỆU TRƢỞNG GS.TS.NGƯT TrầnHữuNghị
  7. PHẦN NHẬN XÉT TÓM TẮT CỦA CÁN BỘ HƢỚNG DẪN 1. Tinhthầntháiđộcủasinhviêntrongquátrìnhlàmđềtàitốtnghiệp: 2. Đánhgiáchấtlƣợngcủađềtàitốtnghiệp (so vớinội dung yêucầuđãđềratrongnhiệmvụđềtàitốtnghiệp) 3. Cho điểmcủacánbộhƣớngdẫn: ( Điểmghibằngsốvàchữ )
  8. Ngày tháng năm 2013 Cánbộhƣớngdẫnchính ( Ký, ghirõhọtên )
  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. Đánhgiáchấtlƣợngđềtàitốtnghiệp (vềcácmặtnhƣcơsởlýluận, thuyết minh chƣơngtrình, giátrịthựctế, ) 2. Cho điểmcủacánbộphảnbiện ( Điểmghibằngsốvàchữ ) Ngày tháng năm 2013 Cánbộchấmphảnbiện ( Ký, ghirõhọtên )
  10. MỤC LỤC LỜI MỞ ĐẦU 1 DANH MỤC HÌNH VẼ 2 DANH MỤC CÁC TỪ VIẾT TẮT 3 Chương 1. MỘT SỐ KHÁI NIỆM CƠ BẢN 4 1.1. TỔNG QUAN VỀ AN TOÀN THÔNG TIN 4 1.1.1. An toàn thông tin 4 1.1.2. Nội dung của an toàn thông tin 4 1.1.3. Hai loại hành vi xâm phạm an toàn thông tin 5 1.1.4. Các chiến lƣợc an toàn hệ thống 5 1.1.5. Các mức bảo vệ trên mạng 6 1.1.6. An toàn thông tin bằng mã hóa 8 1.2. MỘT SỐ KHÁI NIỆM TOÁN HỌC 9 1.2.1. Ƣớc chung lớn nhất, bội chung nhỏ nhất 9 1.2.2. Quan hệ “ Đồng dƣ ” 10 1.2.3. Số nguyên tố 11 1.2.4. Khái niệm nhóm, nhóm con, nhóm Cyclic 11 1.2.5. Phần tử nghịch đảo 12 1.2.6. Các phép tính cơ bản trong không gian modulo 12 1.2.7. Độ phức tạp của thuật toán 13 1.3. CÁC HỆ MÃ HÓA 13 1.3.1. Tổng quan về mã hóa dữ liệu 13 1.3.2. Hệ mã hóa khóa công khai 15 1.3.3. Hệ mã hóa khóa đối xứng – cổ điển 18 1.3.4. Hệ mã hóa khóa đối xứng DES 21 1.4. CHỮ KÝ SỐ 24 1.4.1. Giới thiệu 24 1.4.2. Phân loại “Chữ ký số” 26 1.4.3. Một số loại chữ ký số 27
  11. Chương 2. 31 ỨNG DỤNG VẤN ĐỀ CHIA SẺ BÍ MẬT TRONG BỎ PHIẾU ĐIỆN TỬ 31 2.1. TỔNG QUAN VỀ BỎ PHIẾU ĐIỆN TỬ. 31 2.1.1. Vấn đề bỏ phiếu từ xa. 31 2.1.2. Quy trình bỏ phiếu từ xa. 33 2.2. VẤN ĐỀ CHIA SẺ BÍ MẬT 42 2.2.1. Khái niệm chia sẻ bí mật. 42 2.2.2. Các sở đồ chia sẻ bí mật. 42 2.3. ỨNG DỤNG CHIA SẺ BÍ MẬT TRONG ĐĂNG KÝ BỎ PHIẾU ĐIỆN TỬ. 47 2.3.1. Một số bài toán trong đăng ký bỏ phiếu điện tử. 47 2.3.2. Ứng dụng chia sẻ bí mật. 48 Chương 3. THỬ NGHIỆM CHƢƠNG TRÌNH. 49 3.1. THỬ NGHIỆM CHƢƠNG TRÌNH CHIA SẺ KHÓA BÍ MẬT. 49 3.1.1. Chia sẻ khoá bí mật K 49 3.1.2. Khôi phục khóa K từ t thành viên 49 3.2. CẤU HÌNH HỆ THỐNG. 50 3.3. CÁC THÀNH PHẦN CHƢƠNG TRÌNH. 50 3.4. HƢỚNG DẤN SỬ DỤNG CHƢƠNG TRÌNH. 51 3.4.1. Chia sẻ khóa bí mật. 52 3.4.2. Khôi phục khóa bí mật. 54 KẾT LUẬN 55 TÀI LIỆU THAM KHẢO 56 PHỤ LỤC 57
  12. LỜI CẢM ƠN Trƣớc hết em xin đƣợc bày tỏ sự trân trọng và lòng biết ơn đối với thầy giáo PGS.TS. Trịnh Nhật Tiến - Khoa Công nghệ thông tin trƣờng Đại học Công Nghệ, Đại học Quốc Gia Hà Nội. Trong suốt quá trình làm đồ án tốt nghiệp của em, thầy đã dành rất nhiều thời gian quí báu để tận tình chỉ bảo, hƣớng dẫn và định hƣớng cho em h đồ án tốttrong việc nghiên cứu và hoàn thàn nghiệp. Em cũng xin cảm ơn các Thầy giáo, Cô giáo trong khoa Công nghệ thông tin – Trƣờng Đại học dân lập Hải Phòng đã giúp đỡ, tạo điều kiện thuận lợi cho em trong suốt khóa học tại trƣờng. Sự đóng góp quý báu của các Thầy Cô đã giúp cho em hoàn thành tốt đồ án tốt nghiệp.
  13. Đồ án tốt nghiệp Trường DHDL Hải Phòng LỜI MỞ ĐẦU Trong suốt nhiều thế kỉ qua trên thế giới, các cuộc bầu cử đã giữ một vai trò quan trọng trong việc xác lập thể chế chính trị của các quốc gia. Và trong xu hƣớng phát triển của khoa học công nghệ ngày nay, công nghệ thông tin đã ngày càng phổ biến và đƣợc áp dụng trong mọi lĩnh vực đời sống. Các cuộc bầu cử cũng không phải là ngoại lệ. Ngƣời ta đã bỏ rất nhiều công sức để nghiên cứu cải tiến các phƣơng thức bầu cử để nó ngày càng trở nên tốt và tiện lợi hơn. Các phƣơng thức thay đổi theo từng thời kỳ, theo sự tiến bộ của xã hội. Và với sự tiến bộ của xã hội ngày nay thì các dự án chính phủ điện tử để giúp nhà nƣớc điều hành đất nƣớc là một điều tất yếu, kèm theo đó thì sự phát triển của bỏ phiếu điện tử để thay thế cho bỏ phiếu thông thƣờng là điều sẽ diễn ra trong tƣơng lai. Nắm đƣợc tầm quan trọng và tính tất yếu của bỏ phiếu điện tử, các nƣớc, các tổ chức đã và đang xây dựng giải pháp cho bỏ phiếu điện tử. Trong phạm vi của Đồ án tốt nghiệp này, để cho tập trung, Tôi sẽ trình bày vấn đề chia sẻ bí mật chủ yếu trong giai đoạn Đăng ký bỏ phiếu điện tử. Sinh viên : Bùi Văn Tiến – Lớp: CT1301 1
  14. Đồ án tốt nghiệp Trường DHDL Hải Phòng DANH MỤC HÌNH VẼ Hình 2.1. Quy trình bỏ phiếu từ xa 33 Hình 2.2. Sơ đồ giai đoạn đăng ký. 36 Hình 2.3. Sơ đồ giai đoạn bỏ phiếu. 39 Hình 2.4. Sơ đồ giai đoạn kiểm phiếu. 41 Hình 3.1. Giao diện chƣơng trình chia sẻ khóa bí mật 51 Hình 3.2. Hƣớng dẫn chia khóa bí mật 52 Hình 3.3. Hƣớng dẫn ghép các mảnh khóa bí mật 54 Sinh viên : Bùi Văn Tiến – Lớp: CT1301 2
  15. Đồ án tốt nghiệp Trường DHDL Hải Phòng DANH MỤC CÁC TỪ VIẾT TẮT Các từ viết tắt Viết đầy đủ RSA Tên 3 nhà khoa học: Ron Rivest, Adi Shamir, Leonard Adleman. DES Data Encryption Standard ĐH Ban điều hành ĐK Ban đăng ký KP Ban kiểm phiếu CT Cử tri KT Ban kiểm tra ƢCLN Ƣớc chung lớn nhất BCNN Bội chung nhỏ nhất Sinh viên : Bùi Văn Tiến – Lớp: CT1301 3
  16. Đồ án tốt nghiệp Trường DHDL Hải Phòng Chương 1. MỘT SỐ KHÁI NIỆM CƠ BẢN 1.1. TỔNG QUAN VỀ AN TOÀN THÔNG TIN 1.1.1. An toàn thông tin Khi nhu cầu trao đổi thông tin dữ liệu ngày càng lớn và đa dạng, các tiến bộ về điện tử - viễn thông và công nghệ thông tin không ngừng đƣợc phát triển ứng dụng để nâng cao chất lƣợng và lƣu lƣợng truyền tin thì các quan niệm ý tƣởng và biện pháp bảo vệ thông tin cũng đƣơc đổi mới. Bảo vệ an toàn thông tin là 1 chủ đề rộng, có liên quan đến nhiều lĩnh vực, trong thực tế có nhiều phƣơng pháp đƣơc thực hiện để bảo vệ an toàn thông tin. Các phƣơng pháp bảo vệ an toàn thông tin có thể đƣợc quy tụ vào ba nhóm sau: - Bảo vệ an toàn thông tin bằng các biện pháp hành chính. - Bảo vệ an toàn thông tin bằng các biện pháp kỹ thuật (phần cứng). - Bảo vệ an toàn thông tin bằng các biện pháp thuật toán (phần mềm). Ba nhóm trên có thể đƣợc ứng dung riêng rẽ hoặc phối kết hợp. Môi trƣờng khó bảo vệ an toàn thông tin nhất cũng là môi trƣờng đối phƣơng dễ xâm nhập nhất đó là môi trƣờng mạng và truyền tin. Biện pháp hiệu quả nhất và kinh tế nhất hiện nay trên mạng truyền tin và mạng máy tính là biện pháp thuật toán. 1.1.2. Nội dung của an toàn thông tin An toàn thông tin bao gồm các nội dung sau: 1). Bảo mật : Tính kín đáo riêng tƣ của thông tin. 2). Bảo toàn : Bảo vệ thông tin không cho phép sửa đổi thông tin trái phép. 3). Xác thực : Xác thực đối tác, xác thực thông tin trao đổi, đảm bảo ngƣời gửi thông tin không thể thoái thác về trách nhiệm thông tin mình đã gửi. 4). Sẵn sàng : Luôn sẵn sàng thông tin cho ngƣời dùng hợp pháp. Để đảm bảo thông tin trên đƣờng truyền tin và trên mạng máy tính có hiệu quả, thì điều trƣớc tiên là phải lƣờng trƣớc hoặc dự đoán trƣớc các khả năng không an toàn, khả năng xâm phạm, các sự cố rủi ro có thể xảy ra đối với thông tin đƣợc lƣu trữ và trao đổi trên đƣờng truyền tin cũng nhƣ trên mạng. Xác định càng chính xác các nguy cơ nói trên thì càng quyết định đƣợc tốt các giải pháp để giảm thiểu các thiệt hại. Sinh viên : Bùi Văn Tiến – Lớp: CT1301 4
  17. Đồ án tốt nghiệp Trường DHDL Hải Phòng 1.1.3. Hai loại hành vi xâm phạm an toàn thông tin Có hai loại hành vi xâm phạm thông tin dữ liệu đó là: vi phạm thụ động và vi phạm chủ động. Vi phạm thụ động chỉ nhằm mục đích cuối cùng là nắm bắt đƣợc thông tin (đánh cắp thông tin). Việc làm đó khi không biết đƣợc nội dung cụ thể nhƣng có thể dò ra đƣợc ngƣời gửi, ngƣời nhận nhờ thông tin điều khiển giao thức chứa trong phần đầu các gói tin. Kẻ xâm nhập có thể kiểm tra đƣợc số lƣợng, độ dài và tần số trao đổi. Vì vậy vi phạm thụ động không làm sai lệch hoặc hủy hoại nội dung thông tin dữ liệu đƣợc trao đổi. Vi phạm thụ động thƣờng khó phát hiện nhƣng có thể có những biện pháp ngăn chặn hiệu quả. Vi phạm thụ động là dạng vi phạm có thể làm thay đổi nội dung, xóa bỏ, xắp xếp lại thứ tự hoặc làm lặp lại gói tin tại thời điểm đó hoặc sau đó một thời gian. Vi phạm chủ động có thể thêm vào một số thông tin ngoại lai để làm sai lệch nội dung thông tin trao đổi. Vi phạm chủ động dễ phát hiện nhƣng để ngăn chặn hiệu quả thì khó khăn hơn nhiều. Có một thực tế là không có một biện pháp nào bảo vệ an toàn thông tin dữ liệu nào là an toàn tuyệt đối. Một hệ thống dù đƣợc bảo vệ chắc chắn đến đâu cũng không thể đảm bảo là an toàn tuyệt đối. 1.1.4. Các chiến lƣợc an toàn hệ thống 1). Giới hạn quyền hạn tối thiểu Đây là chiến lƣợc cơ bản nhất theo nguyên tắc này bất kì mội đối tƣợng nào cũng chỉ có những quyền hạn nhất định đối với tài nguyên mạng, khi thâm nhập vào mạng đối tƣợng đó chỉ đƣợc sử dụng một số tài nguyên nhất định. 2). Bảo vệ theo chiều sâu Nguyên tắc này nhắc nhở chúng ta: Không nên dựa vào mội chế độ an toàn nào dù cho chúng rất mạnh, mà nên tạo nhiều cơ chế an toàn để hỗ trợ lẫn nhau. 3). Nút thắt Tạo ra một “cửa khẩu” hẹp, và chỉ cho phép thông tin đi vào hệ thống của mình bằng con đƣờng duy nhất chính là “cửa khẩu” này => phải tổ chức một cơ cấu kiểm soát và điều khiển thông tin đi qua cửa này. Sinh viên : Bùi Văn Tiến – Lớp: CT1301 5
  18. Đồ án tốt nghiệp Trường DHDL Hải Phòng 4). Điểm nối yếu nhất Chiến lƣợc này dựa trên nguyên tắc: “Một dây xích chỉ chắc tại mắt duy nhất, một bức tƣờng chỉ cứng tại điểm yếu nhất”. Kẻ phá hoại thƣờng tìm chỗ yếu nhất của hệ thống để tấng công, do đó ta cần phải gia cố các yếu điểm của hệ thống. Thông thƣờng chúng ta chỉ quan tâm đến kẻ tấn công trên mạng hơn là kẻ tiếp cận hệ thống của chúng ta. 5). Tính toàn cục Các hệ thống an toàn đòi hỏi phải có tính toàn cục của các hệ thống cục bộ. Nếu có một kẻ nào đó có thể bẻ gãy một cơ chế an toàn thì chúng có thể thành công bằng cách tấn công hệ thống tự do của ai đó và sau đó tấn công hệ thống từ nội bộ bên trong. 6). Tính đa dạng bảo vệ Cần phải sử dụng nhiều biện pháp bảo vệ khác nhau cho hệ thống khác nhau, nếu không có kẻ tấn công vào đƣợc một hệ thống, thì chúng cũng dễ dàng tấn công vào các hệ thống khác. 1.1.5. Các mức bảo vệ trên mạng Vì không thể có một giải pháp an toàn tuyệt đối nên ngƣời ta thƣờng phải sử dụng đồng thời nhiều mức bảo vệ khác nhau tạo thành nhiều hàng rào chắn đối với các hoạt động xâm phạm. Việc bảo vệ thông tin trên mạng chủ yếu là bảo vệ thông tin cất giữ trong máy tính, đặc biệt là các server trên mạng. Bởi thế ngoài một số biện pháp nhằm chống thất thoát thông tin trên đƣờng truyền mọi cố gắng tập trung vào việc xây dựng các mức rào chắn từ ngoài vào trong cho các hệ thống kết nối mạng. Thông thƣờng bao gồm các mức bảo vệ sau: 1). Quyền truy nhập Lớp bảo vệ trong cùng là quyền truy nhập nhằm kiểm soát các tài nguyên của mạng và quyền hạn trên tài nguyên đó. Dĩ nhiên là kiểm soát đƣợc các cấu trúc dữ liệu càng chi tiết càng tốt. Hiện tại việc kiểm soát thƣờng ở mức tệp. Sinh viên : Bùi Văn Tiến – Lớp: CT1301 6
  19. Đồ án tốt nghiệp Trường DHDL Hải Phòng 2). Đăng kí tên, mật khẩu Thực ra đây cũng là kiểm soát quyền truy nhập, nhƣng không phải truy nhập ở mức thông tin mà ở mức hệ thống. Đây là phƣơng pháp bảo vệ phổ biến nhất vì nó đơn giản ít phí tổn và cũng rất hiệu quả. Mỗi ngƣời sử dụng muốn đƣợc tham gia vào mạng để sử dụng tài nguyên đều phải có đăng kí tên và mật khẩu trƣớc. Ngƣời quản trị mạng có trách nhiệm quản lý, kiểm soát mọi hoạt động của mạng và xác định quyền truy nhập của những ngƣời sử dụng khác theo thời gian và không gian(nghĩa là ngƣời sử dụng chỉ đƣợc truy nhập trong một khoảng thời gian nào đó tại mỗi vị trí nhất định nào đó). Về lý thuyết nếu mọi ngƣời đều giữ kín đƣợc mật khẩu và tên đăng ký của mình thì sẽ không xảy ra các truy nhập trái phép. Song điều đó khó đảm bảo trong thực tế vì nhiều nguyên nhân rất đời thƣờng làm giảm hiệu quả của lớp bảo vệ này. Có thể khắc phục bằng cách ngƣời quản trị mạng chịu trách nhiệm đặt mật khẩu hoặc thay đổi mật khẩu theo thời gian. 3). Mã hóa dữ liệu Để bảo mật thông tin trên đƣờng truyền ngƣời ta sử dụng các phƣơng pháp mã hóa. Dữ liệu bị biến đổi từ dạng nhận thức đƣợc sang dạng không nhận thức đƣợc theo một thuật toán nào đó và sẽ đƣợc biến đổi ngƣợc lại ở trạm nhận (giải mã). Đây là lớp bảo vệ thông tin rất quan trọng. 4). Bảo vệ vật lý Ngăn cản các truy nhập vật lý vào hệ thống. Thƣờng dùng các biện pháp truyền thống nhƣ ngăn cấm tuyệt đối ngƣời không phận sự vào phòng đặt máy mạng, dùng ổ khóa trên máy tính hoặc các máy trạm không có ổ mềm. 5). Tƣờng lửa Ngăn chặn xâm nhập trái phép và lọc bỏ các gói tin không muốn gửi hoặc nhận vì các lý do nào đó để bảo vệ một máy tính hoặc cả nội bộ (intranet). Sinh viên : Bùi Văn Tiến – Lớp: CT1301 7
  20. Đồ án tốt nghiệp Trường DHDL Hải Phòng 6). Quản trị mạng Trong thời đại phát triển của công nghệ thông tin, mạng máy tính quyết định toàn bộ hoạt động của cơ quan, hay một công ty xí nghiệp. Vì vậy việc bảo đảm cho hệ thống mạng máy tính hoạt động một cách an toàn, không xảy ra sự cố là một công việc cấp thiết hàng đầu. Công tác quản trị mạng máy tính đƣợc thực hiện một cách khoa học đảm vào các yêu cầu sau: - Toàn bộ hệ thống hoạt động bình thƣờng trong giờ làm việc. - Có hệ thống dự phòng khi có sự cố về phần cứng hoặc phần mềm xảy ra. - Sao lƣu dữ liệu quan trọng theo định kỳ. - Bảo dƣỡng mạng theo định kỳ. - Bảo mật dữ liệu, phân quyền truy cập, tổ chức nhóm làm việc trên mạng 1.1.6. An toàn thông tin bằng mã hóa Để bảo vệ thông tin trên đƣờng truyền ngƣời ta thƣờng biến đổi nó từ dạng nhận thức đƣợc sang dạng không nhận thức đƣợc trƣớc khi truyền trên mạng, quá trình này gọi đƣợc gọi là mã hóa thông tin (encryption). Ở trạm nhận phải thực hiện quá trình ngƣợc lại, tức là biến đổi thông tin từ dạng không nhận thức đƣợc (dữ liệu đã đƣợc mà hóa) về dạng nhận thức đƣợc (dạng gốc), quá trình này gọi là giải mã. Đây là một lớp bảo vệ thông tin rất quan trọng và đƣợc sủ dụng rộng rãi trong môi trƣờng mạng. Để bảo vệ thông tin bằng mã hóa ngƣời ta thƣờng tiếp cận theo hai hƣớng: - Theo đƣờng truyền (Link_Oriented_Security) - Từ nút đến nút (End_to_End) Theo cách thứ nhất, thông tin đƣợc mã hóa để bảo vệ trên đƣờng truyền giữa hai nút mà không quan tâm đến nguồn và đích của thông tin đó. Ở đây ta lƣu ý rằng thông tin chỉ đƣợc bảo vệ trên đƣờng truyền, tức là ở mỗi nút đều có quá trình giải mã sau đó mã hóa để truyền đi tiếp, do đó các nút cần phải đƣợc bảo vệ tốt. Sinh viên : Bùi Văn Tiến – Lớp: CT1301 8
  21. Đồ án tốt nghiệp Trường DHDL Hải Phòng Theo cách thứ hai, thông tin trên mạng đƣợc bảo vệ trên toàn đƣờng truyền từ nguồn đến đích. Thông tin sẽ đƣợc mã hóa ngay sau khi mới tạo ra và chỉ đƣợc giải mã khi về đến đích. Cách này mắc phải nhƣợc điểm là chỉ có dữ liệu của ngƣời dùng thì mới có thể mã hóa đƣợc, còn dữ liệu điều khiển thì giữ nguyên để có thể xử lý tại các nút. 1.2. MỘT SỐ KHÁI NIỆM TOÁN HỌC 1.2.1. Ƣớc chung lớn nhất, bội chung nhỏ nhất 1.2.1.1. Ước số và bội số Cho hai số nguyên a và b, b 0. Nếu có một số nguyên q sao cho a = b*q, thì ta nói rằng a chia hết cho b, kí hiệu b\a. Ta nói b là ƣớc của a, và a là bội của b. Ví dụ: Cho a = 6, b = 2, ta có 6 = 2*3, ký hiệu 2\6. Ở đây 2 là ƣớc của 6 và 6 là bội của 2. Cho các số nguyên a, b 0, tồn tại cặp số nguyên (q, r) (0 r /b/) duy nhất sao cho a = b*q + r. Khi đó q gọi là thương nguyên, r gọi là số dư của phép chia a cho b. Nếu r = 0 thì ta có phép chia hết. Ví dụ: Cho a = 13, b = 5, ta có 12 = 5*2 + 3. Ở đây thƣơng q=2, số dƣ là r = 3. 1.2.1.2. Ước chung lớn nhất, bội chung nhỏ nhất. Số nguyên d đƣợc gọi là ước chung của các số nguyên a1, a2, ,an , nếu nó là ước của tất cả các số đó. Số nguyên m đƣợc gọi là bội chung của các số nguyên a1, a2, ,an , nếu nó là bội của tất cả các số đó. Một ƣớc chung d >0 của các số nguyên a1, a2, ,an , trong đó mọi ƣớc chung của a1, a2, ,an , đều là ƣớc của d, thì d đƣợc gọi là ước chung lớn nhất (UCLN) của a1, a2, ,an . Ký hiệu d = gcd(a1, a2, ,an ) hay d = UCLN(a1, a2, ,an ). Nếu gcd(a1, a2, ,an ) = 1, thì các số a1, a2, ,an đƣợc gọi là nguyên tố cùng nhau. Một bội chung m >0 của các số nguyên a1, a2, ,an , trong đó mọi bội chung của a1, a2, ,an đều là bội của m, thì m đƣợc gọi là bội chung nhỏ nhất (BCNN) của a1, a2, ,an . Ký hiệu m = lcm(a1, a2, ,an ) hay m = BCNN(a1, a2, ,an ). Sinh viên : Bùi Văn Tiến – Lớp: CT1301 9
  22. Đồ án tốt nghiệp Trường DHDL Hải Phòng Ví dụ: Cho a =12, b=15, gcd(12,15) = 3, lcm(12,15) = 60. Hai số 8 và 13 là nguyên tố cùng nhau, vì gcd(8, 13) =1. Ký hiệu : Zn = {0, 1, 2, , n-1} là tập các số nguyên không âm 0). Ta nói rằng a và b “đồng dư” với nhau theo modulo m, nếu chia a và b cho m, ta nhận đƣợc cùng một số dƣ. Ký hiệu : a b(mod m). Ví dụ : 17 5 (mod 3) vì 17 và 5 chia cho 3 đƣợc cùng số dƣ là 2. 1.2.2.2. Các tính chất của quan hệ “Đồng dư” 1). Quan hệ “đồng dư” là quan hệ tương đương trong Z. Với mọi số nguyên dƣơng m ta có : a a (mod m) với mọi a Z; a b (mod m) thì b a (mod m); a b (mod m) và b c (mod m) thì a c (mod m); 2). Tổng hay hiệu các “đồng dư” : (a + b) (mod n) = [(a mod n) + (b mod n)] (mod n) (a - b) (mod n) = [(a mod n) - (b mod n)] (mod n) 3). Tích các “đồng dư”: (a * b) (mod n) = [(a mod n) * (b mod n)] (mod n) Sinh viên : Bùi Văn Tiến – Lớp: CT1301 10
  23. Đồ án tốt nghiệp Trường DHDL Hải Phòng 1.2.3. Số nguyên tố 1.2.3.1. Khái niệm Số nguyên tố là số tự nhiên lớn hơn 1 và chỉ có hai ƣớc là 1 và chính nó. Ví dụ : Các số 2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31 là các số nguyên tố. 1.2.3.2. Định lý về số nguyên tố 1). Định lý : Về số nguyên dương > 1. Mọi số nguyên dƣơng n >1 đều có thể biểu diễn đƣợc duy nhất dƣới dạng : n1 n2 nk n=P1 . P1 P1 , trong đó : k,ni (i = 1,2, ,k) là các số tự nhiên, Pi là các số nguyên tố, từng đội một khác nhau. 2). Định lý : Mersenne. Cho p = 2k -1, nếu p là số nguyên tố, thì k phải là số nguyên tố. 3). Hàm Euler. Cho số nguyên dƣơng n, số lƣợng các số nguyên dƣơng bé hơn n và nguyên tố cùng nhau với n đƣợc ký hiệu ø(n) và gọi là hàm Euler. Nhận xét : Nếu p là số nguyên tố, thì ø(p) = p-1. Định lý về Hàm Euler : Nếu n là tích của hai số nguyên tố n = p.q, thì ø(n) = ø(p). ø(q) = (p-1)(q-1) 1.2.4. Khái niệm nhóm, nhóm con, nhóm Cyclic a) Nhóm là bộ các phần tử (G, *) thỏa mãn các tính chất sau: + Tính chất kết hợp: ( x * y ) * z = x * ( y * z ) + Tính chất tồn tại phần tử trung gian e G: e * x = x * e = x, x G + Tính chất tồn tại phần tử nghịch đảo x’ G: x’ * x = x * x’ = e b) Nhóm con của G là tập S ⊂ G, S ø, và thỏa mãn các tính chất sau: + Phần tử trung lập e của G nằm trong S. + S khép kín đối với phép tính (*) trong, tức là x * y S với mọi x, y S. + S khép kín đối với phép lấy nghịch đảo trong G, tức x-1 S với mọi x S. Sinh viên : Bùi Văn Tiến – Lớp: CT1301 11
  24. Đồ án tốt nghiệp Trường DHDL Hải Phòng c) Nhóm cyclic: (G, *) là nhóm đƣợc sinh ra bởi một trong các phần tử của nó. Tức là có phần tử g G mà với mỗi a G, đều tồn tại số n N để gn = a. Khi đó g là phần tử sinh hay phần tử nguyên thủy của nhóm G. Ví dụ: (Z+, *) gồm các số nguyên dƣơng là một nhóm cyclic có phần tử sinh là 1. 1.2.5. Phần tử nghịch đảo 1). Khái niệm. Cho a Zn. Nếu tồn tại b Zn sao cho a b 1 (mod n), ta nói b là phần tử -1 nghịch đảo của a trong Zn và ký hiệu a . Một phần tử có phần tử nghịch đảo, gọi là khả nghịch. 2). Tính chất : -1 + Cho a, b Zn. Phép chia của a cho b theo modulo n là tích của a và b theo modulo n và chỉ đƣợc xác định khi b khả nghịch theo modulo n. + Cho a Zn, a khả nghịch khi và chỉ khi UCLN(a, n) = 1. + Giả sử d = UCLN (a, n). Phƣơng trình đồng dƣ ax b mod n có nghiệm x nếu và chỉ nếu d chia hết cho b, trong trƣờng hợp các nghiệm d nằm trong khoảng [0, n-1] thì các nghiệm đồng dƣ theo modulo . Ví dụ: 4-1= 7 mod 9 vì 4 . 7 1 mod 9 1.2.6. Các phép tính cơ bản trong không gian modulo Cho n là số nguyên dƣơng. Các phần tử trong Zn đƣợc thể hiện bởi các số nguyên {0, 1, 2, , n-1}. Nếu a, b Zn thì: (a + b) mod n = Vì vậy, phép cộng modulo (và phép trừ modulo) có thể đƣợc thực hiện mà không cần thực hiện các phép chia dài. Phép nhân modulo của a và b đƣợc thực hiện bằng phép nhân thông thƣờng a với b nhƣ các số nguyên bình thƣờng, sau đó lấy phần dƣ của kết quả sau khi chia cho n. Sinh viên : Bùi Văn Tiến – Lớp: CT1301 12
  25. Đồ án tốt nghiệp Trường DHDL Hải Phòng 1.2.7. Độ phức tạp của thuật toán 1). Chi phí của thuật toán. Chi phí phải trả cho một quá trình tính toán gồm chi phí thời gian và bộ nhớ. + Chi phí thời gian của một quá trình tính toán là thời gian cần thiết để thực hiện một quá trình tính toán. + Chi phí bộ nhớ của một quá trình tính toán là số ô nhớ cần thiết để thực hiện một quá trình tính toán. Gọi A là một thuật toán, e là dữ liệu vào của bài toán đã đƣợc mã hóa. Thuật toán A tính trên dữ liệu vào e phải trả một giá nhất định. Ký hiệu: tA(e) là giá thời gian và lA(e) là giá bộ nhớ. 2). Độ phức tạp về bộ nhớ: tA(n) = max { lA(e), với |e| n}, n là “kích thƣớc” đầu vào của thuật toán. 3). Độ phức tạp về thời gian: lA(n) = max { tA(e), với |e| n}. 4). Độ phức tạp tiệm cận: Độ phức tạp PT(n) đƣợc gọi là tiệm cận tới hàm f(n), ký hiệu O(f(n)) nếu tồn tại các số n0, c mà PT(n) c.f(n), n n0. 5). Độ phức tạp đa thức: Độ phức tạp PT(n) đƣợc gọi là đa thức, nếu nó tiệm cận tới đa thức p(n). 6). Thuật toán đa thức: Thuật toán đƣợc gọi là đa thức, nếu độ phức tạp về thời gian là đa thức. 1.3. CÁC HỆ MÃ HÓA 1.3.1. Tổng quan về mã hóa dữ liệu 1.3.1.1. Khái niệm mã hóa dữ liệu Để đảm bảo An toàn thông tin lƣu trữ trong máy tính hay đảm bảo An toàn thông tin trên đƣờng truyền tin ngƣời ta phải “Che giấu” các thông tin này. “Che” thông tin (dữ liệu) hay “Mã hóa” thông tin là thay đổi hình dạng thông tin gốc, và ngƣời khách khó nhận ra. “Giấu” thông tin (dữ liệu) là cất giấu thông tin trong bản tin khác, và ngƣời khác cũng khó nhận ra. Thuật toán mã hóa là thủ tục tính toán để thực hiện mã hóa hay giải mã. Sinh viên : Bùi Văn Tiến – Lớp: CT1301 13
  26. Đồ án tốt nghiệp Trường DHDL Hải Phòng Khóa mã hóa là một giá trị làm cho thuật toán mã hóa thực hiện một cách riêng biệt và sinh bản rõ riêng.Thông thƣờng khóa càng lớn thì bản mã càng an toàn, Phạm vi các giá trị có thể có của khóa gọi là không gian khóa. Hệ mã hóa là tập các thuật toán, các khóa nhằm che giấu thông tin , cũng nhƣ làm rõ nó. Hệ mã hóa: Việc mã hóa phải theo các quy tắc nhất định, quy tắc đó gọi là Hệ mã hóa. Hệ mã hóa đƣợc định nghĩa là bộ năm (P, C, K, E, D), trong đó: P là tập hữu hạn các bản rõ có thể. C là tập hữu hạn các bản mã có thể. K là tập hữu hạn các khoá có thể. E là tập các hàm lập mã. D là tập các hàm giải mã. Với khóa lập mã ke K, có hàm lập mã eke E, eke : P C, Với khóa giải mã kd K, có hàm giải mã dkd D, dkd: C P, sao cho dkd (eke (x)) = x, x P. Ở đây x đƣợc gọi là bản rõ, eke (x) đƣợc gọi là bản mã. Mã hóa và giải mã: Ngƣời gửi G eke(T) Ngƣời nhận N (có khóa lập mã ke) (có khóa giải mã kd) Tin tặc có thể trộm bản mã eke(T) 1.3.1.2. Phân loại hệ mã hóa Có nhiều cách để phân loại hệ mã hóa. Dựa vào tính chất đối xứng của khóa có thể phân các hệ mã hóa thành hai loại: - Hệ mã hóa khóa đối xứng (hay còn gọi là mã hóa khóa bí mật): là những hệ mã hóa dùng chung một khóa cả trong quá trình mã hóa dữ liệu và giải mã dữ liệu. Do đó khóa phải đƣợc giữ bí mật tuyệt đối. Sinh viên : Bùi Văn Tiến – Lớp: CT1301 14
  27. Đồ án tốt nghiệp Trường DHDL Hải Phòng - Hệ mã hóa khóa bất đối xứng (hay còn gọi là mã khóa công khai): Hệ mật này dùng 1 khóa để mã hóa, dùng một khóa khác để giải mã, nghĩa là khóa để mã hóa và giải mã là khác nhau. Các khóa này tạo nên từng cặp chuyển đổi ngƣợc nhau và không có khóa nào có thể “dễ” suy đƣợc từ khóa kia. Khóa để mã hóa có thể công khai, nhƣng khóa để giải mã phải giữ bí mật. Ngoài ra nếu dựa vào thời gian đƣa ra hệ mã hóa, ta còn có thể phân làm hai loại: Mã hóa cổ điển (là hệ mật mã ra đời trƣớc năm 1970) và mã hóa hiện đại(ra đời sau năm 1970). Còn nếu dựa vào cách thức tiến hành mã hóa thì hệ mã hóa còn đƣợc chia làm hai loại là mã dòng (tiến hành mã từng khối dữ liệu, mỗi khối lại dựa vào các khóa khác nhau, các khóa này đƣợc sinh ra từ hàm sinh khóa, đƣợc gọi là dòng khóa) và mã khối (tiến hành mã từng khối dữ liệu với khóa nhƣ nhau). 1.3.2. Hệ mã hóa khóa công khai 1.3.2.1. Hệ mã hóa RSA Sơ đồ (Rivest, Shamir, Adleman đề xuất năm 1977) * Tạo cặp khóa (bí mật, công khai) (a, b) : Chọn bí mật số nguyên tố lớn p, q, tính n = p * q, công khai n, đặt P = C = Zn Tính bí mật Ø(n) = (p-1).(q-1). Chọn khóa công khai b < Ø(n), nguyên tố với Ø(n). Khóa bí mật a là phần tử nghịch đảo của b theo mod Ø(n): a*b 1(mod Ø(n)). Tập cặp khóa (bí mật, công khai) K = {(a, b)/ a, b Zn, a*b 1(mod Ø(n)). Với Bản rõ x P và Bản mã y C, định nghĩa: b Hàm Mã hoá: y = ek (x) = x mod n a Hàm Giải mã: x = dk(y) = y mod n Ví dụ: * Bản rõ chữ: R E N A I S S A N C E *Sinh khóa: Chọn bí mật số nguyên tố p= 53, q= 61, tính n = p * q = 3233, công khai n. Đặt P = C = Zn , tính bí mật Ø(n) = (p-1). (q-1) = 52 * 60 = 3120. + Chọn khóa công khai b là nguyên tố với Ø(n), tức là ƢCLN(b, Ø(n)) = 1 Sinh viên : Bùi Văn Tiến – Lớp: CT1301 15
  28. Đồ án tốt nghiệp Trường DHDL Hải Phòng * ví dụ chọn b = 71. + Khóa bí mật a là phần tử nghịch đảo của b theo mod Ø(n): a*b 1(mod Ø(n)). Từ a*b 1 (mod Ø(n)), ta nhận đƣợc khóa bí mật a = 791. * Bản rõ số: R E N A I S S A N C E (Dấu cách) 17 04 13 00 08 18 18 00 13 02 04 26 m1 m2 m3 m4 m5 m6 * b 71 Theo phép lập mã: ci = mi mod n = mi mod 3233, ta nhận đƣợc: * Bản mã số: c1 c2 c3 c4 c5 c6 3106 0100 0931 2691 1984 2927 a 791 * Theo phép giải mã: mi = ci mod n = ci mod 3233, ta nhận lại bản rõ. Độ an toàn : - Hệ mã hóa RSA là tất định, tức là với một bản rõ x và một khóa bí mật a, thì chỉ có một bản mã y. - Hệ mật RSA an toàn, khi giữ đƣợc bí mật khoá giải mã a, p, q, Ø(n). Nếu biết đƣợc p và q, thì thám mã dễ dàng tính đƣợc Ø(n) = (q-1)*(p-1). Nếu biết đƣợc Ø(n), thì thám mã sẽ tính đƣợc a theo thuật toán Euclide mở rộng. Nhƣng phân tích n thành tích của p và q là bài toán “khó”. Độ an toàn của Hệ mật RSA dựa vào khả năng giải bài toán phân tích số nguyên dƣơng n thành tích của 2 số nguyên tố lớn p và q. Sinh viên : Bùi Văn Tiến – Lớp: CT1301 16
  29. Đồ án tốt nghiệp Trường DHDL Hải Phòng 1.3.2.2. Hệ mã hóa Elgamal Sơ đồ: (Elgamal đề xuất năm 1985) * Tạo cặp khóa (bí mật, công khai) (a,b): Chọn số nguyên tố p sao cho bài toán logarit rời rạc trong Zp là “khó” giải. * a Chọn phần tử nguyên thủy g Zp . Tính khóa công khai h g mod p. Định nghĩa tập khóa: K = {(p, g, a, h): h ga mod p}. Các giá trị p, g, h đƣợc công khai, phải giữ bí mật a. Với bản rõ x P và bản mã y C, với khóa k K định nghĩa : * Lập mã : Chọn ngẫu nhiên bí mật r Zp-1, bản mã là y = ek(x, r) = (y1, y2) r r Trong đó : y1 = g mod p và y2 = x * h mod p a -1 * Giải mã : dk (y1, y2) = y2( y1 ) mod p. Ví dụ: * Bản rõ x = 1299. Chọn p = 2579, g = 2, a = 765. Tính khóa công khai h = 2 765 mod 2579 = 949. * Lập mã : Chọn ngẫu nhiên r = 853. Bản mã là y = (435, 2369), 852 853 Trong đó: y1 = 2 mod 2579 = 435 và y2 = 1299 * 949 mod 2579 = 2396 a -1 765 -1 * Giải mã : x = y2(y1 ) mod p = 2369 * (435 ) mod 2579 = 1299. Độ an toàn : - Hệ mã hóa Elgamal là không tất định, tức là với một bản rõ x và 1 khóa bí mật a, thì có thể có nhiều hơn một bản mã y, vì trong công thức lập mã còn có thành phần ngẫu nhiên r. - Độ an toàn của Hệ mật mã Elgamal dựa vào khả năng giải bài toán logarit rời rạc trong Zp. Theo giả thiết trong sơ đồ, thì bài toán này phải là “khó” giải. r Cụ thể là : Theo công thức lập mã : y = ek(x, r) = (y1, y2), trong đó y1 = g mod p và r y2 = x * h mod p . Nhƣ vậy muốn xác định bản rõ x từ công thức y2 , thám mã phải biết đƣợc r, Giá trị này có thể tính đƣợc từ công thức y1 , nhƣng lại gặp bài toán logarit rời rạc. Sinh viên : Bùi Văn Tiến – Lớp: CT1301 17
  30. Đồ án tốt nghiệp Trường DHDL Hải Phòng 1.3.3. Hệ mã hóa khóa đối xứng – cổ điển Khái niệm Hệ mã hóa khóa đối xứng đã đƣợc dùng từ rất sớm, nên còn đƣợc gọi là Hệ mã hóa đối xứng – cổ điển. Bản mã hay bản rõ là dãy các ký tự Lantin. - Lập mã: thực hiện theo các bƣớc sau: Bƣớc 1: nhập bản rõ ký tự: RÕ_CHỮ. Bƣớc 3: chuyển RÕ_SỐ ==> MÃ_SỐ. Bƣớc 2: chuyển RÕ_CHỮ ==> RÕ_SỐ. Bƣớc 4: chuyển MÃ _SỐ ==> MÃ_CHỮ - Giải mã: thực hiện theo các bƣớc sau. Bƣớc 1: nhập bản mã ký tự: MÃ_CHỮ. Bƣớc 3: chuyển MÃ_SỐ ==> RÕ_SỐ. Bƣớc 2: chuyển MÃ_CHỮ ==> MÃ_SỐ Bƣớc 4: chuyển RÕ_SỐ ==> RÕ_CHỮ Các hệ mã hóa cổ điển - Hệ mã hóa dịch chuyển: khóa có 1 “chìa”. - Hệ mã hóa Affine: khóa có 2 “chìa”. - Hệ mã hóa thay thế: khóa có 26 “chìa”. - Hệ mã hóa VIGENERE: khóa có m “chìa”. - Hệ mã hóa HILL: khóa có ma trận “chìa”. 1.3.3.1. Hệ mã hóa dịch chuyển Sơ đồ : Đặt P = C = K = Z26. Bản mã y và bản rõ x Z26. Với khóa k K, ta định nghĩa: Hàm mã hóa: y = ek(x) = (x+k) mod 26 Hàm giải mã: x = dk(y) = (y - k)mod 26 Độ an toàn : Độ an toàn của mã dịch chuyển là rất thấp. Tập khóa K chỉ có 26 khóa, nên việc phá khóa có thể thực hiện dễ dàng bằng cách thử kiểm tra từng khóa: k=1,2,3, ,26. Sinh viên : Bùi Văn Tiến – Lớp: CT1301 18
  31. Đồ án tốt nghiệp Trường DHDL Hải Phòng 1.3.3.2. Hệ mã hóa thay thế (Hoán vị toàn cục) Sơ đồ : Đặt P = C = Z26 . Bản mã y và bản rõ x Z26. Tập khóa K là tập mọi hoán vị trên Z26. Với khóa k = π K, tức là 1 hoán vị trên Z26, ta định nghĩa: Mã hóa: y = e π (x) = π (x) -1 Giải mã: x = d π (y) = π (y) Độ an toàn : Độ an toàn của mã thay thế thuộc loại cao Tập khóa K có 26! Khóa (>4.1026), nên việc phá khóa cố thể thực hiện bằng cách duyệt tuần tự 26! Hoán vị của 26 chữ cái.Để kiểm tra tất cả 26! Khóa, tốn rất nhiều thời gian. Hiện nay với hệ mã này, ngƣời ta có phƣơng pháp thám mã khác nhanh hơn. 1.3.3.3. Hệ mã hóa AFFINE Sơ đồ : Đặt P = C = Z26. Bản mã y và bản rõ x Z26. Tập khóa K = {(a,b), với a,b Z26, UCLN(a, 26) = 1} Với khóa k = (a,b) K, ta định nghĩa: Phép mã hóa : y=ek(x)= (ax + b) mod 26 -1 Phép giải mã : x=dk(y)= a (y-b) mod 26 Độ an toàn: Độ an toàn của Hệ mã hóa Affine: Rất thấp - Điều kiện UCLN(a, 26)=1 để bảo đảm a có phần tử nghịch đảo a-1mod 26, tức là thuật toán giải mã dk luôn thực hiện đƣợc. - Số lƣợng a Z26 nguyên tố với 26 là (26)=12, đó là : 1, 3, 5, 7, 9, 11, 15, 17, 19, 21, 23, 25 - Các số nghịch đảo theo (mod 26) tƣơng ứng là: 1, 9, 21, 15, 3, 19, 7, 23, 11, 5, 17, 25 - Số lƣợng b Z26 là 26. - Số các khóa (a,b) có thể là 12*26 = 312. Rất ít ! - Nhƣ vậy việc dò tìm khóa mật khá dễ dàng. Sinh viên : Bùi Văn Tiến – Lớp: CT1301 19
  32. Đồ án tốt nghiệp Trường DHDL Hải Phòng 1.3.3.4. Hệ mã hóa VIGENERE Sơ đồ: m Đặt P =C=K=(Z26) , m là số nguyên dƣơng, các phép toán thực hiện trong (Z26). m Bản mã Y và bản rõ X (Z26) . Khóa k = (k1, k2, ,km) gồm m phầm tử. Mã hóa Y = (y1, y2, ,ym)=ek(x1, x2, , xm)=(x1+ k1, x2 + k2, , xm+ km) mod 26. Giải mã X= (x1, x2, , xm) = dk(y1,y2, ,ym) = (y1- k1, y2 - k2, , ym- km) mod 26. Độ an toàn: Độ an toàn của mã VIGENERE là tƣơng đối cao Nếu khóa gồm m ký tự khác nhau, mỗi ký tự có thể đƣợc ánh xạ vào trong m ký tự có thể, do đó hệ mật này đƣợc gọi là thay thế đa biểu. Nhƣ vậy số khóa có thể có trong mật Vigenere là 26m. Nếu dùng phƣơng pháp “tấn công vét cạn”, thám mã phải kiểm tra 26m khóa. Hiện nay với hệ mã này, ngƣời ta có phƣơng pháp thám mã khác nhanh hơn. 1.3.3.5. Hệ mã hóa hoán vị cục bộ Sơ đồ : m Đặt P = C = K = (Z26) , m là số nguyên dƣơng. Bản mã Y và bản rõ X Z26. - Tập khóa K là tập tất cả các hoán vị của {1, 2, , m} - Với mỗi khóa k = π K, k = (k1, k2, ,km) gồm m phần tử, ta định nghĩa: * Mã hóa Y = (y1, y2, ,ym) = ek(x1, x2, , xm) = (xk(1), xk(2), , xk(m)) -1 -1 -1 * Giải mã X = (x1, x2, , xm) = dk(y1, y2, ,ym) =(yk(1) , yk(2) , , yk(m) ) - Trong đó k -1 =π -1 là hoán vị ngƣợc của π . Độ an toàn : - Nếu dùng phƣơng pháp “tấn công vét cạn”, thám mã phải kiểm tra số khóa là: 1! + 2! + 3! + + m! trong đó m ≤ 26. - Hiện nay với hệ mã này, ngƣời ta có phƣơng pháp thám mã khác nhanh hơn. Sinh viên : Bùi Văn Tiến – Lớp: CT1301 20
  33. Đồ án tốt nghiệp Trường DHDL Hải Phòng 1.3.3.6. Hệ mã hóa HILL Sơ đồ : m m Đặt P = C = (Z26) , m là số nguyên dƣơng. Bản mã Y và bản rõ X (Z26) . m*n -1 Tập khóa K={ k (Z26) / det(K,26)=1}. (K phải có K ) Mỗi khóa K là một “chùm chìa khóa” : Với mỗi k K, định nghĩa: * Hàm lập mã: Y = (y1, y2, ,ym) = ek(x1, x2, , xm) = (x1, x2, , xm) * k -1 * Hàm giải mã: X = (x1, x2, , xm) = dk(y1, y2, ,ym) = (y1, y2, ,ym) * k Độ an toàn : Nếu dùng phƣơng pháp “tấn công vét cạn”, thám mã phải kiểm tra số khóa có thể với m lần lƣợt là 2, 3, 4, , trong đó m lớn nhất là bằng độ dài bản rõ. 1.3.4. Hệ mã hóa khóa đối xứng DES 1.3.4.1. Hệ mã hóa DES Giới thiệu : 15/05/1973, Ủy ban tiêu chuẩn quốc gia Mỹ đã công bố một khuyến nghị về hệmã hóa chuẩn. - Hệ mã hóa phải có độ an toàn cao. - Hệ mã hóa phải đƣợc định nghĩa đầy đủ và dễ hiểu. - Độ an toàn của hệ mã hóa phải nằm ở khóa, không nằm ở thuật toán. - Hệ mã hóa phải sẵn sàng cho mọi ngƣời dùng ở các lĩnh vực khác nhau. - Hệ mã hóa phải xuất khẩu đƣợc. DES đƣợc IBM phát triển, là một cải biên của hệ mật LUCIPHER DES, nó đƣợc công bố lần đầu tiên vào ngày 17/03/1975. Sau nhiều cuộc tranh luận công khai, cuối cùng DES đƣợc công nhận nhƣ một chuẩn liên bang vào ngày 23/11/1976 và đƣợc công bố vào ngày15/01/1977. Năm 1980, “cách dùng DES” đƣợc công bố. Từ đó chu kỳ 5 năm DES đƣợc xem xét lại một lần bởi Ủy ban tiêu chuẩn quốc gia Mỹ. Sinh viên : Bùi Văn Tiến – Lớp: CT1301 21
  34. Đồ án tốt nghiệp Trường DHDL Hải Phòng Quy trình mã hóa theo DES : Giai đoạn 1: Bản rõ chữ Bản rõ số (Dạng nhị phân) Chia thành Giai doạn 2: Bản rõ số Các đoạn 64 bit rõ số Giai đoạn 3: 64 bit rõ số 64 bit mã số Kết nối Giai đoạn 4: Các đoạn 64 bit mã số Bản mã số (Dạng nhị phân) Giai đoạn 5: Bản mã số Bản mã chữ 1.3.4.2. Lập mã và giải mã Lập mã DES : * Bản rõ là xâu x, bản mã là xâu y, khóa là xâu K, đều cố đọ dài 64 bit. * Thuật toán mã hóa DES thực hiện qua 3 bƣớc chính nhƣ sau: Bước 1: Bản rõ x đƣợc hoán vị theo phép hoán vị IP, thành IP (x). IP(x) = L0R0, trong đó L0 là 32 bit đầu (Left), R0là 32 bit cuối (Right). (IP(x) tách thành L0R0). Bước 2 : Thực hiện 16 vòng mã hóa với những phép toán giống nhau Dữ liệu đƣợc kết hợp với khóa thông qua hàm f: Ll = Rl-1, Rl = Ll-1 f(Rl-1, k1) trong đó: là phép toán hoặc loại trừ của hai xâu bit (cộng theo modulo 2). k1, k2, ,k16 là các khóa con (48 bit) đƣợc tính từ khóa gốc K. -1 Bước 3: Thực hiện phép hoán vị ngƣợc IP cho xâu L16R16, thu đƣợc bản mã y. -1 y = IP ( L16, R16) Quy trình giải mã : Quy trình giải mã của DES tƣơng tự nhƣ quy trình lập mã, nhƣng theo dùng các khóa thứ tự ngƣợc lại: k16, k15, , k1 . Xuất phát (đầu vào) từ bản mã y, kết quả (đầu ra) là bản rõ x. Sinh viên : Bùi Văn Tiến – Lớp: CT1301 22
  35. Đồ án tốt nghiệp Trường DHDL Hải Phòng 1.3.4.3. Độ an toàn của hệ mã hóa DES - Độ an toàn của hệ mã hóa DES có liên quan đến các bảng Sj : Ngoại trừ các bảng S, mọi tính toán trong DES đều tuyến tính, tức là việc tính phép hoặc loại trừ của hai đầu ra cũng giống nhƣ phép hoặc loại trừ của hai đầu vào, rồi tính toán đầu ra. Các bảng S chứa đựng nhiều thành phần phi tuyến của hệ mật, là yếu tố quan trọng nhất đối với độ mật của hệ thống. Khi mới xây dựng hệ mật DES, thì tiêu chuẩn xây dựng các hộp S không đƣợc biết đầy đủ. Và có thể các hộp S này có thể chứa các “cửa sập” đƣợc giấu kín. Và đó cũng là một điểm đảm bảo tính bảo mật của hệ DES - Hạn chế của DES chính là kích thƣớc không gian khóa: Số khóa có thể là 256, không gian này là nhỏ để đảm bảo an toàn thực sự. Nhiều thiết bị chuyên dụng đã đƣợc đề xuất nhằm phục vụ cho phép tấn công với bản rõ đã biết. Phép tấn công này chủ yếu thực hiện theo phƣơng pháp “vét cạn”. Tức là với bản rõ x và bản mã y tƣơng ứng (64 bit), mỗi khóa có thể đều đƣợc kiểm tra cho tới khi tìm đƣợc một khóa K thỏa mãn eK(x) = y. Sinh viên : Bùi Văn Tiến – Lớp: CT1301 23
  36. Đồ án tốt nghiệp Trường DHDL Hải Phòng 1.4. CHỮ KÝ SỐ 1.4.1. Giới thiệu Để chứng thực nguồn gốc hay hiệu lực của một tài liệu ( ví dụ: đơn xin nhập học, giấy báo nhập học, ) lâu nay ngƣời ta dùng chữ ký “tay”, ghi vào phía dƣới của mỗi tài liệu. Nhƣ vậy ngƣời ký phải trực tiếp “ký tay” vào tài liệu. Ngày nay các tài liệu đƣợc số hóa, ngƣời ta cũng có nhu cầu chứng thực nguồn gốc tài liệu. Rõ ràng không thể “ký tay” vào tài liệu vì chúng không đƣợc in ấn trên giấy. Tài liệu “số” là một xâu các bit (0 hay 1), xâu bít có thể rất dài, “Chữ ký” để chứng thực một xâu bít tài liệu cũng không thể là một xâu bit nhỏ đặt phía dƣới xâu bit tài liệu. Một “Chữ ký” nhƣ vậy chắc chắn sẽ bị kẻ gian sao chép để đặt dƣới một tài liệu khác một cách bất hợp pháp. Những năm 80 của thế kỷ 20, các nhà khoa học đã phát minh ra “chữ ký số” để chứng thực một “tài liệu số” . Đó chính là bản mã của xâu bit tài liệu. Ngƣời ta tạo ra “chữ ký số” trên “tài liệu số” giống nhƣ tạo ra “bản mã” của tài liệu với “khóa lập mã”. Nhƣ vậy “ký số” trên “tài liệu số” là “ký” trên từng bit tài liệu. Kẻ gian khó có thể giả mạo “chữ ký số” nếu nó không biết “khóa lập mã”. Để kiểm tra một “chữ ký số” thuộc về một “tài liệu số”, ngƣời ta giải mã “chữ ký số” bằng “khóa giải mã”, và so sánh với tài liệu gốc. Ngoài ý nghĩa để chứng thực nguồn gốc hay hiêu lực của các tài liệu số hóa, Mặt mạnh của “Chữ ký số” hơn “Chữ ký tay” là ở chỗ ngƣời ta có thể “ký” vào tài liệu từ rất xa trên mạng công khai. Hơn thế nữa, có thể “ký” bằng các thiết bị cầm tay nhƣ Điện thoại di động, laptop, tại khắp mọi nơi miễn là kết nối đƣợc vào mạng. Đỡ tốn thời gian, công sức, chi phí Sinh viên : Bùi Văn Tiến – Lớp: CT1301 24
  37. Đồ án tốt nghiệp Trường DHDL Hải Phòng “Ký số” thực hiện trên từng bit tài liệu, nên độ dài của “chữ ký số” ít nhất cũng bằng độ dài của tài liệu. Do đó thay vì ký trên tài liệu dài, ngƣời ta thƣờng dùng “hàm băm” để tạo “đại diện” cho tài liệu, sau đó mới “ký số” lên “đại diện” này. Sơ đồ chữ ký số : Một sơ đồ chữ ký số thƣờng bao gồm hai thành phần chủ chốt là thuật toán ký và thuật toán xác minh. Một sơ đồ chữ ký số là một bộ 5 (P, A, K, S, V) thỏa mãn các điều kiện sau : P là một tập hợp các bản rõ có thể A là tập hữu hạn các chữ ký có thể K là tập hữu hạn các khóa có thể S là tập các thuật toán ký V là tập các thuật toán xác minh Với mỗi k K, tồn tại một thuật toán ký Sigk S , Sigk : P A, có thuật toán kiểm tra chữ ký Verk V, Verk : P x A {đúng, sai}, thỏa mãn điều kiện sau với mọi x P, y A : Verk (x, y) = Đúng, nếu y = Sigk (x) hoặc Sai, nếu y Sigk (x). Chú ý : Ngƣời ta thƣờng dùng hệ mã hóa khóa công khai để lập: “Sơ đồ chữ ký số”. Ở đây khóa bí mật a dùng làm khóa “ký”, khóa công khai b dùng làm khóa kiểm tra “chữ ký”. Ngƣợc lại với việc mã hóa, dùng khóa công khai b để lập mã, dùng khóa bí mật a để giải mã. Sinh viên : Bùi Văn Tiến – Lớp: CT1301 25
  38. Đồ án tốt nghiệp Trường DHDL Hải Phòng Điều này là hoàn toàn tự nhiên, vì “ký” cần giữ bí mật nên phải dùng khóa bí mật a để “ký”. Còn “chữ ký” là công khai cho mọi ngƣời biết, nên họ dùng khóa công khai b để kiểm tra. 1.4.2. Phân loại “Chữ ký số” Có nhiều loại chữ ký tùy theo cách phân loại, sau đây xin giới thiệu một số cách. Cách 1: Phân loại chữ ký theo khả năng khôi phục thông điệp gốc chữ ký 1). Chữ ký khôi phục thông điệp: Là loại chữ ký, trong đó ngƣời gửi chỉ cần gửi “chữ ký”, ngƣời nhận có thể khôi phục lại đƣợc thông điệp, đã đƣợc “ký” bởi “chữ ký” này. Ví dụ : Chữ ký RSA 2). Chữ ký không thể khôi phục thông điệp gốc : Ví dụ: Chữ ký Elgamal là chữ ký đi kèm thông điệp. Cách 2: Phân loại chữ ký theo mức an toàn. 1). Chữ ký “không thể phủ nhận”: Nhằm tránh việc nhân bản chữ ký để sử dụng nhiều lần, tốt nhất là ngƣời gửi tham gia trực tiếp vào việc kiểm thử chữ ký. Điều đó đƣợc thực hiện bằng một giao thức kiểm thử, dƣới dạng một giao thức mời hỏi và trả lời. Ví dụ: Chữ ký không phủ định (Chaum-van Antverpen). Sinh viên : Bùi Văn Tiến – Lớp: CT1301 26
  39. Đồ án tốt nghiệp Trường DHDL Hải Phòng 2). Chữ ký “một lần”: Chữ ký dùng một lần (one-time signature) là một khái niệm vẫn còn khá mới mẻ song rất quan trọng, đặc biệt là trong một số mô hình về bỏ phiếu điện tử và tiền điện tử. Để đảm bảo an toàn, “khóa ký” chỉ dùng 1 lần (one-time) trên 1 tài liệu. Ví dụ: Chữ ký một lần Lamport. Chữ ký Fail-Stop (Van Heyst & Pedersen). Cách 3: Phân loại chữ ký theo ứng dụng đặc trưng. - Chữ ký “mù” (Blind Signature). - Chữ ký “nhóm” (Group Signature). - Chữ ký “bội” (Multy Signature). - Chữ ký “mù nhóm” (Blind Group Signature). - Chữ ký “mù bội” (Blind Multy Signature). 1.4.3. Một số loại chữ ký số 1.4.3.1. Chữ ký RSA Sơ đồ : (đề xuất năm 1978) * Tạo cặp khóa (bí mật, công khai) (a,b): Chọn bí mật nguyên tố lớn p, q, tính n=p*q, công khai n đặt P=C=Zn Tính bí mật = (q-1)(p-1). Chọn khóa công khai b < , nguyên tố với . Khóa bí mật a là phần tử nghịch đảo của b theo mod : a*b=1(mod ). a Ký số: chữ ký trên x P là y = Sigk(x) = x (mod n), y A (R1). b Kiểm tra chữ ký: Verk(x,y) = đúng x= y (mod n) (R2). Sinh viên : Bùi Văn Tiến – Lớp: CT1301 27
  40. Đồ án tốt nghiệp Trường DHDL Hải Phòng Chú ý: Việc “ký số” vào x tƣơng ứng với việc “mã hóa” tài liệu x. Kiểm thử chính là việc giải mã “chữ ký”, để kiểm tra xem tài liệu đã giải mã có đúng với tài liệu trƣớc khi ký hay không. Thuật toán và kiểm thử “chữ ký” là công khai, ai cũng có thể kiểm thử chữ ký đƣợc. Ví dụ: chữ ký trên x = 2 * Tạo cặp khóa (bí mật, công khai) (a,b): Chọn bí mật số nguyên tố p=3, q=5, tính n=p*q=3*5=15, công khai n. Đặt P=C=Zn. tính bí mật = (q-1)(p-1)= (3-1)(5-1) =8 Chọn khóa công khai b= 3< , nguyên tố cùng nhau với =8. Khóa bí mật a =3, là phần tử nghịch đảo của b theo mod : a*b=1(mod ) * Ký số: chữ ký trên x=2 P là : a 3 y = Sigk(x)= x (mod n) = 2 (mod 15) = 8, y A. * Kiểm tra chữ ký : b b Verk(x,y) = đúng x = y (mod n) 2 = 8 (mod15) Sinh viên : Bùi Văn Tiến – Lớp: CT1301 28
  41. Đồ án tốt nghiệp Trường DHDL Hải Phòng 1.4.3.2. Chữ ký ELGAMAL Sơ đồ : (Elgamal đề xuất năm 1985) * Tạo cặp khóa (bí mật, công khai) (a, h): Chọn số nguyên tố p sao cho bài toán logarit rời rạc trong Zp là “khó” giải. * * * Chọn phần tử nguyên thủy g Zp . Đặt P = Zp , A = Zp x Zp-1. * a Chọn khóa bí mật là a Zp . Tính khóa công khai h g mod p. Định nghĩa tập khóa : K = {(p, g, a, h): h ga mod p}. Các giá trị p, g, h đƣợc công khai, phải giữ bí mật a. * * Ký số: Dùng 2 khóa ký: khóa a và khóa ngẫu nhiên bí mật r Zp-1 . * -1 ( Vì r Zp-1 , nên nguyên tố cung p-1, do đó tồn tại r mod(p-1)). Chữ ký trên x P là y = Sig k(x, r) = ( ), y A (E1) * Trong đó Zp , Zp-1 : = g r mod p và = (x – a * )* r -1 mod (p-1) * Kiểm tra chữ ký : γ δ x Ver k (x, ) = đúng h * γ g mod p. (E2) Chú ý: Nếu chữ ký đƣợc tính đúng, kiểm thử sẽ thành công vì h γ * γδ g a γ * g r * δ mod p g (a γ + r * δ) mod p gx mod p. Do δ = (x – a * γ) * r -1 mod (p - 1) nên (a * γ + r * δ ) x mod (p-1) Sinh viên : Bùi Văn Tiến – Lớp: CT1301 29
  42. Đồ án tốt nghiệp Trường DHDL Hải Phòng 1.4.3.3. Chữ ký Schnoor * Sinh khóa: * * Cho Z n , q là số nguyên tố, cho G là nhóm con cấp q của Z n . Chọn phần tử sinh g G, sao cho bài toán logarit rời rạc trên G là “khó giải”. * Chọn hàm băm H: 0, 1 Z q . * a Chọn khóa bí mật là a Z n , khóa công khai là h = g mod n. * Ký số: Chữ ký Schnorr trên m 0, 1 * đƣợc định nghĩa là cặp (c, s), nếu thỏa mãn điều kiện c = H(m, g s h c ). Chú ý: Ký hiệu (m, g s h c ) là phép “ghép nối” m và g s h c . Ví dụ: m = 0110, g s h c = 01010, thì (m, g s h c ) = 011001010. Tạo chữ ký Schnorr: Chữ ký là cặp (c, s). * r + Chọn ngẫu nhiên r Z q . Tính c = H(m, g ), s = r – c a (mod q). * Kiểm tra chữ ký: Cặp (c, s) là chữ ký Schnorr, vì thỏa mãn điều kiện c = H(m, g s h c ). Vì g s h c = g r - c a (g a ) c = g r (mod n), do đó H(m, g s h c )= H(m, g r )= c. Sinh viên : Bùi Văn Tiến – Lớp: CT1301 30
  43. Đồ án tốt nghiệp Trường DHDL Hải Phòng Chương 2. ỨNG DỤNG VẤN ĐỀ CHIA SẺ BÍ MẬT TRONG BỎ PHIẾU ĐIỆN TỬ 2.1. TỔNG QUAN VỀ BỎ PHIẾU ĐIỆN TỬ. 2.1.1. Vấn đề bỏ phiếu từ xa. 2.1.1.1. Khái niệm bỏ phiếu từ xa. Xã hội dân chủ có nhiều việc cần đến “ bỏ phiếu ”: để thăm dò các kế hoạch, để bầu các chức vị, chức danh Nhƣng quĩ thời gian của ngƣời ta không nhiều, mặt khác một ngƣời có thể làm việc tại nhiều nơi, nhƣ vậy ngƣời ta khó có thể thực hiện đƣợc nhiều cuộc bỏ phiếu theo phƣơng pháp truyền thống. Rõ ràng “bỏ phiếu từ xa ” đang và sẽ là nhu cầu cấp thiết, vấn đề trên chỉ còn là thời gian và kỹ thuật cho phép. Đó là cuộc “ bỏ phiếu ” đƣợc thực hiện từ xa trên mạng máy tính qua các phƣơng tiện “ điện tử ” nhƣ máy tính cá nhân, điện thoại di động Nhƣ vậy mọi ngƣời trong cuộc “không thể nhìn thấy mặt nhau” và các “lá phiếu” (lá phiếu “số ”) đƣợc chuyển từ xa trên mạng máy tính tới “ hòm phiếu”. Cũng nhƣ cuộc bỏ phiếu truyền thống, cuộc bỏ phiếu từ xa phải đảm bảo yêu cầu: “ bí mật ” “ toàn vẹn ” và “ xác thực ” của lá phiếu , mỗi cử tri chỉ đƣợc bỏ phiếu một lần, mọi ngƣời đều có thể kiểm tra tính đúng đắn của cuộc bỏ phiếu, cử tri không thể chỉ ra mình đã bỏ phiếu cho ai ( để có cơ hội mua bán phiếu bầu ), Yêu cầu “ bí mật ” của lá phiếu là : ngoài cử tri, chỉ có ban kiểm phiếu mới biết đƣợc biết nội dung lá phiếu, nhƣng họ lại không thể biết ai là chủ nhân của nó. Yêu cầu “ toàn vẹn ” của lá phiếu là : trên đƣờng truyền tin, nội dung lá phiếu không thể bị thay đổi, tất cả lá phiếu đều đƣợc chuyển tới hòm phiếu an toàn, đúng thời gian, chúng đƣợc kiểm phiếu đầy đủ. Yêu cầu “ xác thực ” của lá phiếu là : lá phiếu gửi tới hòm phiếu phải hợp lệ, đúng là của ngƣời có quyền bỏ phiếu, cử tri có thể nhận ra lá phiếu của họ. Sinh viên : Bùi Văn Tiến – Lớp: CT1301 31
  44. Đồ án tốt nghiệp Trường DHDL Hải Phòng 2.1.1.2. Tổ chức hệ thống bỏ phiếu từ xa. a). Các thành phần trong Ban tổ chức bỏ phiếu gồm có : - Ban điều hành (ĐH) quản lý các hoạt động bỏ phiếu, trong đó có thiết lập danh sách cử tri cùng các hồ sơ của mỗi cử tri, qui định cơ chế định danh cử tri. - Ban đăng ký (ĐK) nhận dạng cử tri và ký cấp quyền bỏ phiếu cho họ. Có hệ thống “ ký ” hỗ trợ. - Ban kiểm tra (KT) xác minh tính hợp lệ của lá phiếu. (Vì lá phiếu đã mã hóa nên ban KP không thể biết đƣợc lá phiếu có hợp lệ không, nên cần phải xác minh tính hợp lệ của lá phiếu trƣớc khi nó đến hòm phiếu). - Ban kiểm phiếu (KP) tính toán và thông báo kết quả bỏ phiếu. Có hệ thống “kiểm phiếu ” hỗ trợ. b). Các thành phần kỹ thuật trong Hệ thống bỏ phiếu gồm có: - Hệ thống máy tính và các phần mềm phục vụ quy trình bỏ phiếu từ xa. - Ngƣời trung thực kiểm soát Server đảm bảo yêu cầu bảo mật và toàn vẹn kết quả bỏ phiếu. - Một số kỹ thuật đảm bảo an toàn thông tin : chữ ký mù, mã hóa đồng cấu, chia sẻ bí mật, “ chứng minh không tiết lộ thông tin ”. - Hệ thống phân phối khóa tin cậy sẵn sàng cung cấp khóa cho công việc mã hóa hay ký “ số ”. Sinh viên : Bùi Văn Tiến – Lớp: CT1301 32
  45. Đồ án tốt nghiệp Trường DHDL Hải Phòng 2.1.2. Quy trình bỏ phiếu từ xa. Hiện nay ngƣời ta đã nghiên cứu và thử nghiệm một số quy trình bỏ phiếu từ xa, mỗi quy trình có những ƣu nhƣợc điểm riêng. Quy trình bỏ phiếu từ xa gồm có 3 giai đoạn : đăng ký, bỏ phiếu, kiểm phiếu. Trộn phiếu Chứng minh không Mã hóa đồng cấu tiết lộ thông tin Lá phi ếu Hòm phiếu Lá phiếu Cử tri Bảng niêm yết Ban kiểm phiếu công khai Ban đăng ký Chữ ký mù Sơ đồ chia sẻ bí mật Hình 2.1. Quy trình bỏ phiếu từ xa Sinh viên : Bùi Văn Tiến – Lớp: CT1301 33
  46. Đồ án tốt nghiệp Trường DHDL Hải Phòng 2.1.2.1. Giai đoạn đăng ký. a). Công việc * Cử tri : 1). Cử tri chọn bí mật số định danh x, giấy chứng minh thƣ điện tử (CMT), thông tin nhận dạng (ví dụ nhƣ “vân tay”). Cử tri làm mù x thành y = Blind(x). 2). Cử tri gửi tới Ban đăng ký (ĐK) thông tin nhận dạng của mình, CMT, số y (định danh x đã đƣợc họ làm mù thành y). * Ban đăng ký : 3). Ban đăng ký nhận dạng cử tri, Kiểm tra CMT của cử tri. Nếu hồ sơ của cử tri hợp lệ, khớp với danh sách cử tri của Ban điều hành (ĐH), Cử tri chƣa xin cấp chữ ký lần nào, thì ra lệnh cho Hệ thống “ký” lên y. Đó là chữ ký z = sign(y) . 4). Ban đăng ký ghi số CMT của cử tri vào danh sách các cử tri đã đƣợc cấp chữ ký để tránh việc cử tri đăng ký bỏ phiếu nhiều lần. 5). Ban đăng ký gửi chữ ký z về cho cử tri. * Cử tri : 6). Khi nhận đƣợc chữ ký này, cử tri “xóa mù” trên z, họ sẽ nhận đƣợc chữ ký sign(x) trên định danh thật x . Lá phiếu có gắn chữ ký sign(x) đƣợc xem nhƣ đã có chữ ký của Ban đăng ký. Đó là lá phiếu hợp lệ để cử tri ghi ý kiến của mình. 7). Cử tri có thể kiểm tra chữ ký của Ban đăng ký trên lá phiếu của mình có hợp lệ hay không bằng cách dùng hàm kiểm tra chữ ký và khóa công khai của Ban đăng ký Chú ý rằng khóa ký trên định danh của cử tri đƣợc chia sẻ cho mọi thành viên của Ban đăng ký và Ban kiểm tra, nhờ đó sau này Ban kiểm tra có thể phát hiện những cử tri giả mạo chữ ký của Ban đăng ký. Sinh viên : Bùi Văn Tiến – Lớp: CT1301 34
  47. Đồ án tốt nghiệp Trường DHDL Hải Phòng b). Kỹ thuật sử dụng * Kỹ thuật “ Chia sẻ khóa bí mật ” (Secret Sharing): - Hệ thống phân phối khóa tin cậy (PP khóa) đã chia sẻ khóa ký cho các thành viên Ban đăng ký trƣớc đó. Sau khi xét duyệt hồ sơ xin chữ ký của cử tri, nếu mọi thành viên của Ban đăng ký đều nhất trí cho ký thì họ sẽ khớp các mảnh khóa riêng để nhận đƣợc khóa ký. - Mục đích kỹ thuật : Từng thành viên của Ban đăng ký không thể tùy tiện cấp chữ ký. * Kỹ thuật “ Chữ ký mù ” (Blind Signature): - Ban đăng ký sử dụng kỹ thuật ký “mù” để ký lên định danh “ mù ” của cử tri. - Mục đích của kỹ thuật : Ban đăng ký không thể biết đƣợc ai đã ghi ý kiến vào lá phiếu, tức là bảo đảm không lộ danh tính cử tri. Sinh viên : Bùi Văn Tiến – Lớp: CT1301 35
  48. Đồ án tốt nghiệp Trường DHDL Hải Phòng c). Sơ đồ Giai đoạn đăng ký Để đƣợc quyền bầu cử, Cử tri phải có chữ ký của Ban đăng ký Chọn bí mật bí danh X X đã bị làm mù, Số CMT, Hộ khẩu, Cử tri Ban đăng ký Chữ ký trên X đã làm mù - Kiểm tra các giấy tờ của Cử tri. Xóa mù để thu đƣợc Nếu hợp lệ thì ký trên X đã đƣợc Chữ ký trên X làm mù do Cử tri gửi về. - Ghi lại số CMT của Cử tri để tránh việc Cử tri đăng ký nhiều lần Hình 2.2. Sơ đồ giai đoạn đăng ký. Sinh viên : Bùi Văn Tiến – Lớp: CT1301 36
  49. Đồ án tốt nghiệp Trường DHDL Hải Phòng 2.1.2.2 . Giai đoạn bỏ phiếu. a). Công việc * Cử tri : 1). Sau khi lá phiếu có chữ ký của Ban đăng ký, cử tri ghi ý kiến vào lá phiếu. 2). Cử tri mã hóa lá phiếu bằng khóa công khai của Ban kiểm phiếu. 3). Cử tri gửi tới Ban kiểm tra : lá phiếu đã mã hóa, Định danh x (không bị làm mù) của họ, Chữ ký của Ban đăng ký trên lá phiếu, “Chứng minh không tiết lộ thông tin” về lá phiếu. Lá phiếu không đƣợc chuyển thẳng tới hòm phiếu mà trƣớc đó phải chuyển tới Ban kiểm tra. Tại đây họ kiểm tra chữ ký cấp quyền bỏ phiếu có bị giả mạo không, xác minh tính hợp lệ của lá phiếu. * Ban kiểm tra : 4). Kiểm tra chữ ký cấp quyền bỏ phiếu trên lá phiếu. (Liên hệ với Ban đăng ký) 5). Kiểm tra tính hợp lệ của lá phiếu. (tƣơng tác với cử tri) 6). Mã hóa lại lá phiếu, gửi về hòm phiếu. Khi lá phiếu (đã mã hóa) về Ban kiểm tra, cử tri phải gửi kèm theo định danh thật x (không bị làm mù). Nhƣ vậy Ban kiểm tra biết đƣợc chữ ký thật sign(x) của Ban đăn ký trên lá phiếu và định danh thật x của cử tri, nhƣng không biết danh tính thật của cử tri (họ tên, số CMT, ). Ngƣợc lại, Ban đăng ký biết các thông tin này nhƣng lại không biết đƣợc định danh thật x của cử tri (vì nó đã bị làm mù trƣớc khi gửi tới họ). Khóa ký vào định danh của cử tri đƣợc chia sẻ cho mọi thành viên của Ban đăng ký và Ban kiểm tra. Vì vậy trong giai đoạn này, Ban kiểm tra dùng khóa ký đó để ký lên định danh thật x của cử tri, kiểm tra xem có giống nhƣ chữ ký Sign(x) mà cử tri đã gửi tới họ. Nếu hai chữ ký trong lá phiếu trêm là giả mạo, lá phiếu này sẽ không đƣợc gửi tiếp đến hòm phiếu. Sinh viên : Bùi Văn Tiến – Lớp: CT1301 37
  50. Đồ án tốt nghiệp Trường DHDL Hải Phòng Ban kiểm tra thực hiện các giao thức tƣơng tác với cử tri để kiểm tra tính hợp lệ của lá phiếu. Sau khi xác minh tính hợp lệ của lá phiếu, Ban kiểm tra gửi nó về hòm phiếu. Ban kiểm tra đứng trung gian giữa Cử tri và Ban kiểm phiếu để ngăn chặn một số tình huống thiếu an toàn hay vi phạm luật bỏ phiếu, ví dụ trƣờng hợp mua bán phiếu bầu cử. (Phƣơng pháp bỏ phiếu truyền thống không cần giai đoạn này) b). Kỹ thuật sử dụng. * Kỹ thuật “Mã hóa đông cấu” (Homomorphism Cryptography) Mã hóa đồng cấu có tính chất đặc biệt: tích của các “bản tin” (messenge) đƣợc mã hóa bằng tổng các “bản tin” đƣợc mã hóa. Điều này rất thích hợp cho loại bỏ phiếu điện tử khi mà các “bản tin” đƣợc mã hóa thành 0 hay 1. Mục đích của kỹ thuật : Ban kiểm phiếu không cần giải mã từng lá phiếu, vẫn có thể kiểm phiếu đƣợc. * Kỹ thuật “Chứng minh không tiết lộ thông tin” (Zero_knowlwage proof) Mục đích của kỹ thuật : Ban kiểm tra có cơ sở để xác minh tính hợp lệ của lá phiếu. (Vì dƣới dạng mã hóa, nên không thể biết lá phiếu có hợp lệ không). * Kỹ thuật “Ký số” (Digital Signature) : kiểm tra chữ ký cấp quyền trên lá phiếu. * Kỹ thuật “Mã hóa” (Cryptography) : Mã hóa lại lá phiếu, gửi về hòm phiếu. Sinh viên : Bùi Văn Tiến – Lớp: CT1301 38
  51. Đồ án tốt nghiệp Trường DHDL Hải Phòng c). Sơ đồ giai đoạn bỏ phiếu Chọn ý kiến cho lá phiếu của mình - Chữ ký của Ban đăng ký. - Lá phiếu đã mã hóa bằng khóa công khai của Ban kiểm phiếu Cử tri - “Chứng minh không tiết lộ thông tin” Ban kiểm tra - Kiểm tra chữ ký (Liên hệ với Ban đăng ký) - Thực hiện các giao thức tƣơng tác với Cử tri để kiểm tra tính hợp lệ của lá phiếu. Mã hóa lại lá phiếu, gửi vầ Ban kiểm phiếu. - Hình 2.3. Sơ đồ giai đoạn bỏ phiếu. Sinh viên : Bùi Văn Tiến – Lớp: CT1301 39
  52. Đồ án tốt nghiệp Trường DHDL Hải Phòng 2.1.2.3 . Giai đoạn kiểm phiếu. a. Công việc 1). Các lá phiếu sẽ đƣợc “trộn” nhờ kỹ thuật “trộn” trƣớc khi chúng đƣợc chuyển về Ban kiểm phiếu, nhằm giữ bí mật danh tính cho các cử tri. 2). Ban kiểm phiếu tính kết quả dựa vào các lá phiếu (đã má hóa) gửi về. Theo phƣơng pháp mã hóa đồng cấu, Ban kiểm phiếu không cần giải mã từng lá phiếu, vẫn có thể kiểm phiếu đƣợc. Khi kiểm phiếu, các thành viên trong Ban kiểm phiếu dùng các mảnh khóa riêng của mình để khôi phục khóa bí mật và dùng khóa bí mật này để tính kết quả. 3). Ban kiểm phiếu thông báo kết quả trên bảng niêm yết công khai. b. Kỹ thuật sử dụng. * Kỹ thuật “Trộn” (Mixing). Ban kiểm phiếu gồm m thành viên, để họ không thể biết đƣợc lá phiếu nào là của ai, ngƣời ta xây dựng hệ thống mã hóa m tầng và giải mã m lần mới biết đƣợc nội dung của các lá phiếu. Đầu tiên ngƣời thứ nhất trong Ban kiểm phiếu biết đƣợc từng lá phiếu là của ai, nhƣng lại không biết nội dung của chúng. Anh ta giải mã lần 1, vẫn không biết nội dung của chúng, ngƣời này trộn theo trật tự khác. Mọi ngƣời tiếp theo trong Ban kiểm phiếu thực hiện các công việc nhƣ ngƣời thứ nhất. Sau khi ngƣời cuối cùng giải mã lần thứ m thì nội dung các lá phiếu đã rõ ràng, nhƣng các thành viên trong Ban kiểm phiếu không thể biết đƣợc “tác giả” của từng lá phiếu vì chúng đƣợc “trộn” m-1 lần. * Kỹ thuật “Chia sẻ khóa bí mật ” (Secret Sharing). Chia sẻ khóa bí mật để giải mã lá phiếu, mỗi ngƣời trong ban kiểm phiếm chỉ giữ một mảnh khóa nên không thể tự ý giải mã lá phiểu để sửa lại nội dung lá phiếu. * Kỹ thuật “Mã hóa đồng cấu” (Homomorphism Cryptography). Sinh viên : Bùi Văn Tiến – Lớp: CT1301 40
  53. Đồ án tốt nghiệp Trường DHDL Hải Phòng c). Sơ đồ giai đoạn kiểm phiếu. Trộn các lá phiếu Hòm phiếu Ban kiểm phiếu - Khôi phục khóa bí mật. - Tính kết quả bầu cử. - Công bố kết quả trên bảng niêm yết công khai. Hình 2.4. Sơ đồ giai đoạn kiểm phiếu. Sinh viên : Bùi Văn Tiến – Lớp: CT1301 41
  54. Đồ án tốt nghiệp Trường DHDL Hải Phòng 2.2. VẤN ĐỀ CHIA SẺ BÍ MẬT 2.2.1. Khái niệm chia sẻ bí mật. Khái niệm: Thông tin quan trọng cần bí mật, không nên trao cho một ngƣời nắm giữ, mà phải chia Thông tin đó thành nhiều mảnh và trao cho mỗi ngƣời một mảnh. Thông tin gốc chỉ có thể đƣợc xem lại, khi mọi ngƣời giữ các mảnh thông tin đều nhất trí. Các mảnh thông tin đƣợc khớp lại để đƣợc thông tin gốc. Sơ đồ chia sẻ bí mật dùng để chia sẻ một thông tin cho m thành viên, sao cho chỉ những tập con hợp thức các thành viên mới có thể khôi phục lại thông tin bí mật, còn lại không ai có thể làm đƣợc điều đó. Ứng dụng: - Chia sẻ Thông tin mật thành nhiều mảnh. - Chia sẻ PassWord, Khoá mật thành nhiều mảnh.Mỗi nơi, mỗi ngƣời hay mỗi máy tính cất dấu 1 mảnh. 2.2.2. Các sở đồ chia sẻ bí mật. 2.2.2.1 . Sơ đồ ngưỡng Shamir. a). Sơ đồ chia sẻ ngƣỡng A(t, m) Cho t, m nguyên dƣơng, t ≤ m. Sơ đồ ngƣỡng A(t, m) là phương pháp phân chia Bí mật K cho một tập gồm m thành viên, sao cho t thành viên bất kỳ có thể tính đƣợc K, nhƣng không một nhóm gồm (t-1) thành viên nào có thể làm đƣợc điều đó. Ngƣời phân chia các mảnh khoá không đợc nằm trong số m thành viên trên. Ví dụ: Có m=3 thủ quĩ giữ két bạc. Hãy xây dựng hệ thống sao cho bất kì t=2 thủ quĩ nào cũng có thể mở đƣợc két bạc, nhƣng từng ngời một riêng rẽ thì không thể. Đó là sơ đồ ngƣỡng A(2, 3). Sinh viên : Bùi Văn Tiến – Lớp: CT1301 42
  55. Đồ án tốt nghiệp Trường DHDL Hải Phòng Sơ đồ ngƣỡng Shamir 1979. Bài toán - Chia khoá bí mật K trong Zp thành t mảnh, phân cho mỗi ngƣời giữ 1 mảnh, t ≤ m. t thành viên “khớp t mảnh” sẽ nhận đƣợc K. b). Chia mảnh khoá K (Chủ khóa D) Khởi tạo: Chọn số nguyên tố p. 1. D chọn m phần tử xi khác nhau, ≠ 0 trong Zp, 1≤ i ≤m (m < p, Tl: xi khác nhau, ≠ 0 trong Zp ). D trao xi cho thành viên Pi . Giá trị xi là công khai. Phân phối mảnh khoá K Zp 2. D chọn bí mật (ngẫu nhiên, độc lập) t-1 phần tử Zp là a1, , at-1. t -1 j 3. Với 1≤i≤m, D tính: yi = P(xi), P(x) = K + ∑j=1 aj x mod p 4. Với 1≤i≤m, D sẽ trao mảnh yi cho Pi . Ví dụ 1 Chia mảnh khóa K Khoá K=13 cần chia thành 3 mảnh cho 3 ngƣời P1 , P3 , P5. 1. Chọn số nguyên tố p =17, chọn m=5 phần tử xi = i trong Zp , i =1, 2, 3, 4, 5. D trao giá trị công khai xi cho Pi . 2. D chọn bí mật, ngẫu nhiên t -1 = 2 phần tử trong Zp a1 =10, a2 = 2. 3. D tính yi = P( x i ), 1 ≤ i ≤ m, trong đó: t-1 j 2 P(x)=K + ∑ j=1 aj xj (mod p) =13 + a1 x + a2 x (mod 17). 2 2 y1 =P(x1 )=P(1)=13 + a1 .1 + a2 .1 =13 + 10 .1 + 2 .1 = 8 2 2 y3 =P(x3 )=P(3)=13 + a1 .3 + a2 .3 =13 + 10 .3 + 2 .3 =10 2 2 y5 =P(x5 )=P(5)=13 + a1 .5 + a2 .5 =13 + 10 .5 + 2 .5 =11 4. D trao mảnh yi cho Pi . Sinh viên : Bùi Văn Tiến – Lớp: CT1301 43
  56. Đồ án tốt nghiệp Trường DHDL Hải Phòng c). Cách khôi phục khóa K từ t thành viên Phương pháp: Giải hệ phương trình tuyến tính t ẩn, t phương trình Vì P(x) có bậc lớn nhất là (t-1) nên ta có thể viết: 1 2 t-1 P(x) = K + a1 x + a2 x + + at-1 x Các hệ số K, a1, ,at-1 là các phần tử chƣa biết của Zp, a0= K là khoá. Vì yij = P (xi j ), nên có thể thu đƣợc t phƣơng trình tuyến tính t ẩn a0, a1, ,at-1, Nếu các phƣơng trình độc lập tuyến tính thì sẽ có một nghiệm duy nhất và ta đƣợc giá trị khoá a0 = K. Chú ý: các phép tính số học đều thực hiện trên Zp. Ví dụ 2 Khôi phục khoá K B ={P1, P3, P5} cần kết hợp các mảnh khoá của họ: y1 =8, y3 = 10, y5 = 11, để khôi phục lại khoá K. Theo sơ đồ khôi phục khoá K, yij = P(xij), 1≤ j ≤ t. Thay x1 = 1, x3 = 3, x5 = 5 vào 2 P(x) = a0 + a1 x + a2 x (mod 17), a0 = K. ta nhận đƣợc 3 phƣơng trình với 3 ẩn số a0 , a1, a2. 2 y1 =P(x1 )=P(1)= a0 + a1 .1 + a2 .1 = 8 (mod 17). 2 y3 =P(x3 )=P(3)= a0 + a1 .3 + a2 .3 =10 (mod 17). 2 y5 =P(x5 )=P(5)= a0 + a1 .5 + a2 .5 =11 (mod 17). Giải hệ 3 phƣơng trình tuyến tính trong Z17, nghiệm duy nhất là: a0 =13, a1=10, a2=2. Khoá đƣợc khôi phục là: K= a0 =13. Sinh viên : Bùi Văn Tiến – Lớp: CT1301 44
  57. Đồ án tốt nghiệp Trường DHDL Hải Phòng 2.2.2.2. Cấu trúc mạch đơn điệu. Giả sử ta không muốn tất cả các tập con t thành viên bất kỳ đều có khả năng mở khoá nhƣ trong sơ đồ ngƣỡng Shamir, mà chỉ một số các tập con thành viên chỉ định trƣớc có thể làm đƣợc điều đó. Cấu trúc đơn điệu là một giải pháp cho yêu cầu trên. Tập con các thành viên có thể mở đƣợc khoá gọi là tập con hợp thức. Tập các tập con hợp thức gọi là cấu trúc truy nhập. Ví dụ: Nếu có một tập gồm các thành viên {P1, P2, P3, P4 } trong đó các tập con có thể mở khoá là: {P1, P2,P4 }, {P1,P3, P4 }, {P2, P3} Khi đó ta sẽ thu đƣợc công thức Boolean sau: (P1^ P2^P4 ) v (P1^P3^ P4 ) v (P2^P3) X1 X2 X3 X4 b1 c1 d1 a1 K – a1 K – b1 K – d1 K – c1 ^ ^ ^ ^ ^ ^ ^ K K K K V ^ K Sinh viên : Bùi Văn Tiến – Lớp: CT1301 45
  58. Đồ án tốt nghiệp Trường DHDL Hải Phòng X1 X2 X3 X4 K – b1 K – b1 V K – b1 K – d1 K – a1 c1 ^ a1 ^ b1 ^ ^ ^ ^K K K V ^ K 2.2.2.3 . Cấu trúc không gian vectơ Brickell. Giai đoạn khởi đầu: d 1. Với 1≤ i ≤ w, D sẽ trao vectơ (Pi) (Zp) cho Pi. Các vectơ này đƣợc công khai. Phân phối mảnh: 2. Giả sử D muốn chia sẻ một khóa K Zp, D sẽ chọn một cách bí mật (ngẫu nhiên, độc lập) d-1 phần tử của Zp là a2, , ad 3. Với 1≤ i ≤ w, D tính: yi = (Pi) trong đó = (K, a2, , ad) 4. Với 1≤ i ≤ w, D sẽ trao mảnh yi cho Pi Sinh viên : Bùi Văn Tiến – Lớp: CT1301 46
  59. Đồ án tốt nghiệp Trường DHDL Hải Phòng 2.3. ỨNG DỤNG CHIA SẺ BÍ MẬT TRONG ĐĂNG KÝ BỎ PHIẾU ĐIỆN TỬ. 2.3.1. Một số bài toán trong đăng ký bỏ phiếu điện tử. 1/. Bài toán bảo vệ hồ sơ Đăng ký bỏ phiếu điện tử. Cử tri gửi hồ sơ đăng ký về cho Ban đăng ký thẩm định. Vấn đề nảy sinh : Trên đƣờng truyền, Hồ sơ Đăng ký của Cử tri có thể bị kẻ gian thay đổi thông tin, hoặc đánh cắp hồ sơ Đăng ký. Phương pháp giải quyết : Sử dụng các kỹ thuật mã hóa. 2/. Bài toán thẩm định hồ sơ đăng ký. Trong quá trình đăng ký bỏ phiếu điện tử, để Ban đăng ký có thể cấp quyền bầu cử cho Cử tri thì Ban đăng ký phải xác thực đƣợc thông tin của Cử tri có đáp ứng đƣợc yêu cầu của cuộc bầu cử hay không. ( Ví dụ : Cử tri phải là công dân của nƣớc Việt Nam, Cử tri đủ tuổi để bầu cử .). Vấn đề nảy sinh : Cử tri có thể cấu kết với thành viên trong ban kiểm phiếu để duyệt hồ sơ cho mình trong khi hồ sơ không đủ điều kiện bỏ phiếu. Phương pháp giải quyết : Sử dụng kỹ thuật chia sẻ khóa bí mật để giải mã hồ sơ. 3/. Bài toán Ban đăng ký ký vào lá phiếu ( Đã ẩn danh ). Sau khi thẩm định hồ sơ Đăng ký của Cử tri, nếu hồ sơ hợp lệ thì Ban đăn ký sẽ ký lên lá phiếu và gửi về cho Cử tri. Vấn đề nảy sinh : Cử tri có thể cấu kết với thành viên trong Ban đăng ký để xin cấp chữ ký cho mình nhiều lần. Nhƣ vậy sẽ xảy ra tình trạng bán chữ ký. Phương pháp giải quyết : Sử dụng kỹ thuật chia sẻ khóa bí mật, để ký. Sinh viên : Bùi Văn Tiến – Lớp: CT1301 47
  60. Đồ án tốt nghiệp Trường DHDL Hải Phòng 2.3.2. Ứng dụng chia sẻ bí mật. 1/. Ứng dụng chia sẻ bí mật vào bài toán Thẩm định hồ sơ đăng ký. Khóa giải mã từng hồ sơ đăng ký bỏ phiếu điện tử sẽ đƣợc chia thành nhiều mảnh, mỗi ngƣời trong ban Đăng ký sẽ giữ một mảnh. Khi tất cả mọi ngƣời trong ban Đăng ký đồng ý giải mã hồ sơ thì sẽ ghép các mảnh khóa lại để đƣợc khóa giải mã hồ sơ. Nhƣ vậy một ngƣời trong ban Đăng ký không thể tự ý sửa đổi hồ sơ đăng ký của cử tri để phù hợp với điều kiện đăng ký. 2/. Ứng dụng chia sẻ bí mật vào bài toán Ký vào lá phiếu. Khóa ký mù vào lá phiếu sẽ đƣợc chia thành nhiều mảnh, mỗi ngƣời trong ban Đăng ký sẽ giữ một mảnh khóa. Khi tất cả mọi ngƣời trong ban Đăng ký đồng ý ký thì sẽ ghép các mảnh khóa lại để đƣợc khóa ký và ký lên lá phiếu. Nhƣ vậy một ngƣời trong ban Đăng ký không thể tùy tiện cấp chữ ký đƣợc, mà phải có sự đồng thuận nhất chí của tất cả thành viên trong Ban đăng ký. Sinh viên : Bùi Văn Tiến – Lớp: CT1301 48
  61. Đồ án tốt nghiệp Trường DHDL Hải Phòng Chương 3. THỬ NGHIỆM CHƢƠNG TRÌNH. 3.1. THỬ NGHIỆM CHƢƠNG TRÌNH CHIA SẺ KHÓA BÍ MẬT. * Thử nghiệm chƣơng trình chia sẻ khóa bí mật theo sơ đồ ngƣỡng Shamir : Bài toán Chia khoá bí mật K trong Zp thành t mảnh, phân cho mỗi ngƣời giữ 1 mảnh, t ≤ m. t thành viên “khớp t mảnh” sẽ nhận đƣợc K. 3.1.1. Chia sẻ khoá bí mật K Khởi tạo: Chọn số nguyên tố p. 1/. D chọn m phần tử xi khác nhau, ≠ 0 trong Zp, 1≤ i ≤m (m < p, xi khác nhau, ≠ 0 trong Zp ). D trao xi cho thành viên Pi . Giá trị xi là công khai. Phân phối mảnh khoá K Zp 2/. D chọn bí mật (ngẫu nhiên, độc lập) t-1 phần tử Zp là a1, , at-1. t -1 j 3/. Với 1≤i≤m, D tính: yi = P(xi), P(x) = K + ∑j=1 aj x mod p 4/. Với 1≤i≤m, D sẽ trao mảnh yi cho Pi . 3.1.2. Khôi phục khóa K từ t thành viên Phương pháp: Giải hệ phương trình tuyến tính t ẩn, t phương trình Vì P(x) có bậc lớn nhất là (t-1) nên ta có thể viết: 1 2 t-1 P(x) = K + a1 x + a2 x + + at-1 x Các hệ số K, a1, ,at-1 là các phần tử chƣa biết của Zp, a0= K là khoá. Vì yij = P (xi j ), nên có thể thu đƣợc t phƣơng trình tuyến tính t ẩn a0, a1, ,at-1, Nếu các phƣơng trình độc lập tuyến tính thì sẽ có một nghiệm duy nhất và ta đƣợc giá trị khoá a0 = K. Chú ý: các phép tính số học đều thực hiện trên Zp. Sinh viên : Bùi Văn Tiến – Lớp: CT1301 49
  62. Đồ án tốt nghiệp Trường DHDL Hải Phòng 3.2. CẤU HÌNH HỆ THỐNG. 1/. Cấu hình phần cứng. RAM : tối thiểu 512 MB CPU : Intel core i3-540 @ 3.06GHz 2/. Phần mềm. Hệ điều hành (OS) : Windows 7 : 32bit hoặc 64bit. Chƣơng trình chạy trên nền .NET framework 4. 3.3. CÁC THÀNH PHẦN CHƢƠNG TRÌNH. Chƣơng trình có 2 thành phần chính : a). Chia sẻ khóa bí mật. Phần chia sẻ khóa bí mật bao gồm các ô : - Khóa cần chia sẻ. - Số thành viên giữ khóa. - Số thành viên tối thiểu để mở khóa. - Giá trị p. - Nút “Chia sẻ khóa”. - Nút “Nhập lại” - Bảng kết quả sau khi chia khóa. b). Khôi phục khóa bí mật. Phần khôi phục khóa của chƣơng trình bao gồm : - Bảng chứa các giá trị khóa đã chia sẻ. - Nút “Khôi phục khóa”. - Hộp thông báo kết quả khóa sau khi khôi phục khóa. Sinh viên : Bùi Văn Tiến – Lớp: CT1301 50
  63. Đồ án tốt nghiệp Trường DHDL Hải Phòng 3.4. HƢỚNG DẤN SỬ DỤNG CHƢƠNG TRÌNH. Hình 3.1. Giao diện chương trình chia sẻ khóa bí mật Sinh viên : Bùi Văn Tiến – Lớp: CT1301 51
  64. Đồ án tốt nghiệp Trường DHDL Hải Phòng 3.4.1. Chia sẻ khóa bí mật. Hình 3.2. Hướng dẫn chia khóa bí mật Các bước thực hiện : - Bƣớc đầu tiên ta nhập giá trị khóa cần chia sẻ. - Nhập số lƣợng thành viên cần chia sẻ : Chính là số lƣợng thành viên giữ khóa. - Nhập số lƣợng thành viên tối thiểu để có thể mở khóa. - Nhập giá trị p ( p ở đây là một số nguyên tố). - Click vào nút “Chia sẻ khóa”, và kết quả sẽ đƣợc hiện thị ra bảng kết quả. Ta đem trao giá trị Pi cho ngƣời thứ Xi tƣơng ứng. - Click vào nút “Nhập lại” nếu muốn nhập lại các giá trị từ đầu. Sinh viên : Bùi Văn Tiến – Lớp: CT1301 52
  65. Đồ án tốt nghiệp Trường DHDL Hải Phòng Ví dụ : Nhập các thông tin cần thiết ban đầu nhƣ hình 3.2 thì ta sẽ đƣợc kết quả trong bảng phía dƣới nhƣ sau : Ngƣời thứ 1 giữ mảnh khóa có giá trị : 24 Ngƣời thứ 2 giữ mảnh khóa có giá trị : 47 Ngƣời thứ 3 giữ mảnh khóa có giá trị : 82 Ngƣời thứ 4 giữ mảnh khóa có giá trị : 129 Ngƣời thứ 5 giữ mảnh khóa có giá trị : 188 Sinh viên : Bùi Văn Tiến – Lớp: CT1301 53
  66. Đồ án tốt nghiệp Trường DHDL Hải Phòng 3.4.2. Khôi phục khóa bí mật. Hình 3.3. Hướng dẫn ghép các mảnh khóa bí mật Các bước thực hiện : - Tại bảng chứa các mảnh khóa đã chia, ta tích chọn vào cột “Lựa chọn” để chọn các mảnh khóa đem đi khôi phục (Số lƣợng lựa chọn phải lớn hơn hoặc bằng số lƣợng tối thiểu thành viên có thể ghép khóa. ). - Click vào nút “Khôi phục khóa”. Kết quả sẽ đƣợc hiển thị ra phía bên dƣới. Sinh viên : Bùi Văn Tiến – Lớp: CT1301 54
  67. Đồ án tốt nghiệp Trường DHDL Hải Phòng KẾT LUẬN Đồ án tốt nghiệp có 2 kết quả chính : 1. Về mặt lý thuyết, Đồ án tốt nghiệp đã trình bày : - Tổng quan về An Toàn Thông Tin. - Tổng quan về bỏ phiếu điện tử. - Vấn đề chia sẻ bí mật và ứng dụng trong bỏ phiếu điện tử. 2. Về mặt thực hành, Đồ án tốt nghiệp đã thử nghiệm chƣơng trình : Chia sẻ khóa bí mật dựa vào sơ đồ ngƣỡng Shamir. Chƣơng trình chia sẻ khóa bí mật dựa vào sơ đồ ngƣỡng Shamir bao gồm 2 phần chính là : - Chia sẻ khóa bí mật. - Khôi phục khóa bí mật. Sinh viên : Bùi Văn Tiến – Lớp: CT1301 55
  68. Đồ án tốt nghiệp Trường DHDL Hải Phòng TÀI LIỆU THAM KHẢO 1. “ Giáo trình An toàn dữ liệu ” – PGS. TS Trịnh Nhật Tiến, Đại học Công Nghệ, Đại học Quốc Gia Hà Nội. 2. “Về một quy trình bỏ phiếu từ xa” -Trịnh Nhật Tiến, Trƣơng Thị Thu Hiền, Đại học Công Nghệ, Đại học Quốc Gia Hà Nội. 3. Website : www.tailieu.vn Sinh viên : Bùi Văn Tiến – Lớp: CT1301 56
  69. Đồ án tốt nghiệp Trường DHDL Hải Phòng PHỤ LỤC 1). Code chƣơng trình chia sẻ khóa (ngôn ngữ lập trình vb.net) : Dim p As Integer Dim k As Double Dim m As Integer Dim t As Integer Dim kt As Integer Dim a() As Double Private Sub bt_chia_Click(ByVal sender As System.Object, ByVal e As System.EventArgs) Handles bt_chia.Click If txt_k.Text = "" Or txt_m.Text = "" Or txt_p.Text = "" Or txt_t.Text = "" Then MessageBox.Show("Bạn phải điền đầy đủ thông tin vào các ô !") Else p = Convert.ToDouble(txt_p.Text) k = Convert.ToDouble(txt_k.Text) m = Convert.ToDouble(txt_m.Text) t = Convert.ToDouble(txt_t.Text) ReDim a(0 To p) Dim y(0 To p) As Double Dim tg(0 To p) As Double Dim GetNumber As New Random DataGridView1.Rows.Add(100) DataGridView2.Rows.Add(100) kt = 0 For i = 2 To p - 1 Step 1 If p Mod i = 0 Then kt = 1 Sinh viên : Bùi Văn Tiến – Lớp: CT1301 57
  70. Đồ án tốt nghiệp Trường DHDL Hải Phòng End If Next If kt = 1 Then MessageBox.Show("Giá trị p phải là số nguyên tố !") Else For i = 1 To (t - 1) Step 1 a(i) = GetNumber.Next(1, p) Next For j = 1 To m Step 1 tg(j) = 0 For i = 1 To (t - 1) Step 1 tg(j) = tg(j) + (a(i) * j ^ (i)) Next y(j) = (k + tg(j)) DataGridView1.Item(0, j - 1).Value() = j.ToString DataGridView1.Item(1, j - 1).Value() = y(j).ToString DataGridView2.Item(1, j - 1).Value() = j.ToString DataGridView2.Item(2, j - 1).Value() = y(j).ToString Next End If End If End Sub 2). Code chƣơng trình khôi phục khóa (ngôn ngữ lập trình vb.net) : Private Sub bt_ghep_Click(ByVal sender As System.Object, ByVal e As System.EventArgs) Handles bt_ghep.Click Dim pt(100, 100) As Integer Dim b(100) As Integer Dim y(0 To p) As Integer Dim tg(0 To p) As Integer Dim n As Integer, aa As Integer, s As Integer, jj As Integer, kk As Integer Sinh viên : Bùi Văn Tiến – Lớp: CT1301 58
  71. Đồ án tốt nghiệp Trường DHDL Hải Phòng Dim i1, i2 As Integer, ii As Integer n = t Dim c(n, n + 1) jj = 0 i1 = 0 i2 = 0 For j = 0 To m Step 1 If DataGridView2.Item(0, j).Value t Then MessageBox.Show("Bạn nên chọn số ngƣời ghép khóa bằng " + txt_t.Text.ToString) For j = 0 To m Step 1 DataGridView2.Item(0, j).Value = 0 Next Else For j = 0 To m Step 1 If DataGridView2.Item(0, j).Value <> Nothing Or DataGridView2.Item(0, j).Value = 1 Then i1 = i1 + 1 Sinh viên : Bùi Văn Tiến – Lớp: CT1301 59
  72. Đồ án tốt nghiệp Trường DHDL Hải Phòng b(i1) = DataGridView2.Item(2, j).Value() c(i1, 1) = 1 For ii = 2 To n c(i1, ii) = (j + 1) ^ (ii - 1) Next c(i1, n + 1) = b(i1) End If Next For i = 1 To n s = c(i, i) For j = 1 To n + 1 c(i, j) = c(i, j) / s Next j For j = 1 To n If j <> i Then aa = c(j, i) For kk = 1 To n + 1 c(j, kk) = c(j, kk) - aa * c(i, kk) Next kk End If Next j Next For i = 1 To n a(i - 1) = c(i, n + 1) Next i lb_k.Text = "Khóa bí mật là : " + a(0).ToString End If End If End Sub Sinh viên : Bùi Văn Tiến – Lớp: CT1301 60