Tài liệu Nghiên cứu và phát triển phương pháp rút gọn chữ kí số

  • Số trang: 79 |
  • Loại file: PDF |
  • Lượt xem: 39 |
  • Lượt tải: 0
nhattuvisu

Đã đăng 27125 tài liệu

Mô tả:

i ®¹i häc th¸i nguyªn Tr-êng ®¹i häc C¤NG NGHÖ TH¤NG TIN Vµ TRUYÒN TH¤NG MÃ VĂN LAI NGHIÊN CỨU VÀ PHÁT TRIỂN PHƢƠNG PHÁP RÚT GỌN CHỮ KÍ SỐ LUẬN VĂN THẠC SĨ KHOA HỌC MÁY TÍNH th¸i nguyªn - n¨m 2014 Số hóa bởi Trung tâm Học liệu http://www.lrc-tnu.edu.vn/ ii MỤC LỤC MỤC LỤC.................................................................................................................... i DANH MỤC CÁC CHỮ VIẾT TẮT ........................................................................ iv DANH MỤC CÁC HÌNH VẼ .....................................................................................v MỞ ĐẦU ......................................................................................................................1 Chƣơng 1:TỔNG QUAN VỀ MẬT MÃ KHOÁ CÔNG KHAI VÀ CHỮ KÝ SỐ ....3 1.1. Tổng quan về mật mã ........................................................................................3 1.1.1. An toàn và bảo mật thông tin ......................................................................3 1.1.2. Mật mã học ..................................................................................................4 1.1.3. Tiêu chuẩn đánh giá hệ mật mã...................................................................7 1.2. Mật mã khóa công khai .....................................................................................7 1.2.1. Giới thiệu .....................................................................................................7 1.2.2. Độ an toàn của mật mã công khai .............................................................12 1.2.3. Các ứng dụng của mật mã công khai ........................................................12 1.2.4. Độ phức tạp tính toán của mã công khai. ..................................................12 1.2.5. Những vấn đề về thám mã.........................................................................13 1.3. Hàm băm mật mã .............................................................................................14 1.3.1. Tổng quan về hàm băm .............................................................................14 1.4. Chữ ký số .........................................................................................................17 1.4.1. Khái niệm về chữ ký số .............................................................................17 1.4.2. Thực hiện chữ kí số ...................................................................................19 1.5. Tóm tắt chƣơng ................................................................................................21 Chƣơng 2:CÁC CƠ SỞ TOÁN HỌC VÀ MÔ HÌNH XÂY DỰNG CÁC LƢỢC ĐỒ CHỮ KÍ SỐ ................................................................................................................22 2.1. Một số vấn đề toán học liên quan ....................................................................22 2.1.1. Nhóm .........................................................................................................22 2.1.2. Vành ..........................................................................................................23 2.1.3. Các kiến thức cần thiết khác .....................................................................24 2.2. Bài toán phân tích một số nguyên lớn ra các thừa số nguyên tố .....................26 2.2.1. Một số vấn đề phân tích một số ra thừa số nguyên tố ...............................26 2.2.2. Thuật toán RSA .........................................................................................31 2.2.3. Độ an toàn của hệ mật mã RSA ................................................................32 Số hóa bởi Trung tâm Học liệu http://www.lrc-tnu.edu.vn/ iii 2.3. Bài toán logarit rời rạc trong trƣờng hữu hạn ..................................................33 2.3.1. Vấn đề logarit rời rạc.................................................................................33 2.3.2. Sơ đồ chữ kí số Elgamal............................................................................40 2.4. Hệ mật mã đƣờng cong Elliptic .......................................................................44 2.4.1. Vấn đề về đƣờng cong Elliptic ..................................................................44 2.4.2. Ứng dụng lý thuyết đƣờng cong elliptic vào chữ kí số .............................46 2.5. Tóm tắt chƣơng ................................................................................................48 Chƣơng 3:PHÁT TRIỂN PHƢƠNG PHÁP RÚT GỌN CHỮ KÍ SỐ ......................49 3.1. Đặt vấn đề ........................................................................................................49 3.2. Phƣơng pháp hình thành chữ kí số ..................................................................49 3.2.1. Phƣơng pháp rút gọn chữ kí số .................................................................49 3.2.2. Sơ đồ thuật toán .........................................................................................52 3.2.3. Thảo luận về độ an toàn của sơ đồ chữ kí số mới .....................................53 3.3. Sơ đồ chữ kí dựa vào số nguyên tố δ ...............................................................55 3.3.1. Hàm đƣợc sử dụng ....................................................................................55 3.3.2. Sơ đồ chữ kí số ..........................................................................................55 3.3.3. Thảo luận về độ an toàn sơ đồ chữ kí số ...................................................57 3.3.4. Đánh giá về độ an toàn của sơ đồ chữ kí số mới.......................................58 3.4. Xây dựng chƣơng trình demo ..........................................................................61 3.4.1. Thƣ viện hàm các phép tính trên số lớn ....................................................61 3.4.2. Thuật toán kiểm tra một số lớn là nguyên tố.............................................62 3.4.3. Thuật toán Gordon sinh số nguyên tố mạnh .............................................62 3.4.5. Sơ đồ khối các thủ tục kí và xác nhận chữ kí ............................................63 3.4.6. Các chức năng chính của chƣơng trình ứng dụng .....................................67 3.5. Tóm tắt chƣơng ................................................................................................71 KẾT LUẬN ................................................................................................................72 TÀI LIỆU THAM KHẢO..........................................................................................73 Số hóa bởi Trung tâm Học liệu http://www.lrc-tnu.edu.vn/ iv DANH MỤC CÁC CHỮ VIẾT TẮT Là bậc của số nguyên α Nối độ dài bit của x và y Gcd(x, y) Ƣớc số chung lớn nhất của x và y Lcm(x, y) Bội số chung nhỏ nhất của x và y ECC Elliptic Curve Cryptography – Mật mã trên đƣờng cong Elliptic ECES Elliptic Curve Encrypt Scheme ECDSA Elliptic Curve Digital Signature Algorithm – Thuật toán chữ kí số trên đƣờng cong Elliptic MD5 Message – Digest algorithm 5 hàm băm mật mã tiêu chuẩn 128 bít SHA (Secure Hash Algorithm hay thuật giải băm an toàn RSA Rivest – Shamir – Adleman Zm Vành thƣơng hữu hạn m Số hóa bởi Trung tâm Học liệu http://www.lrc-tnu.edu.vn/ v DANH MỤC CÁC HÌNH VẼ Hình 1.1. Cách mã hóa khóa bí mật .............................................................................6 Hình 1.2. Cách mã hóa khóa công cộng ......................................................................6 Hình 1.3. Hàm băm trong chữ ký số ..........................................................................14 Hình 1.4 Sơ đồ chữ kí số ............................................................................................21 Hình 2.1 Thuật toán Pollar .........................................................................................27 Hình 2.2. Thuật toán Shanks ......................................................................................34 Hình 2.3. Thuật toán Pohlig – Hellman .....................................................................38 Hình 3.1. Sơ đồ thủ tục tạo một bộ khóa ...................................................................64 Hình 3.2. Sơ đồ thủ tục kí ..........................................................................................65 Hình 3.3. Sơ đồ thủ tục xác minh một chữ kí ............................................................66 Hình 3.4. Giao diện chính của chƣơng trình ứng dụng ..............................................67 Hình 3.5. Chức năng tạo bộ khoá...............................................................................68 Hình 3.6. Chức năng kí văn bản.................................................................................68 Hình 3.7. Chức năng xác thực chữ kí – kiểm tra chữ kí là sai ...................................69 Hình 3.8. Chức năng xác thực chữ kí – kiểm tra chữ kí là đúng ...............................69 Số hóa bởi Trung tâm Học liệu http://www.lrc-tnu.edu.vn/ 1 MỞ ĐẦU Mật mã (Cryptography) là ngành khoa học là ngành nghiên cứu các kỹ thuật toán học nhằm cung cấp các dịch vụ bảo vệ thông tin. Đây là ngành khoa học quan trọng, có nhiều ứng dụng trong đời sống xã hội. Ngày nay, các ứng dụng mã hóa và an toàn thông tin đang đƣợc sử dụng ngày càng phổ biến trong các lĩnh vực khác nhau trên thế giới, từ các lĩnh vực an ninh, quốc phòng… cho đến các lĩnh vực dân sự nhƣ thƣơng mại điện tử, ngân hàng…  Vai trò của mật mã trong các giải pháp an toàn thông tin – đề cập đến vấn đề nghiên cứu và ứng dụng mật mã để bảo vệ thông tin. Trong mật mã vấn đề bảo mật luôn đi đôi với vấn đề xác thực thông tin, đặc biệt trong hệ thống mật mã khóa công khai vấn đề xác thực là vô cùng quan trọng. Để giải quyết đƣợc vấn đề xác thực, trong thực tế có một giải pháp kỹ thuật vừa đơn giản vừa hiệu quả là sử dụng chữ ký số. Việc sử dụng chữ ký số ngày càng có nhiều ứng dụng trong thực tế, không chỉ giới hạn trong Ngành Mật Mã mà còn đƣợc áp dụng trong một số lĩnh vực vô cùng quan trọng nhƣ trong lĩnh vực Chính phủ điện tử, Thƣơng mại điện tử,… để xác thực ngƣời gửi, nội dung và nguồn gốc thông tin, chống chối từ.  Vai trò của các thuật toán chữ ký số dựa trên các ứng dụng rộng rãi của chúng. Việc nghiên cứu, tối ƣu và phát triển các lƣợc đồ chữ ký số luôn đƣợc đặt ra trong thực tiễn (nhằm phát triển các lƣợc đồ chữ ký số tối ƣu, hoặc các lƣợc đồ phù hợp cho các ứng dụng phát triển thực tiễn).  Việc nghiên cứu và phát trỉển các lược đồ chữ ký số mới – một trong những mục tiêu chính được đặt ra trong thực tiễn nhằm nâng cao tính độc lập trong xây dựng các giải pháp an toàn thông tin. Trong thực tế, một yêu cầu rất quan trọng đƣợc đăt ra khi tối ƣu và phát triển các lƣợc đồ chữ ký số ứng dụng trong các môi trƣờng hạn chế về băng thông và tài nguyên là các lƣợc đồ chữ ký số với chiều dài chữ ký số ngắn (Giải quyết bài toán làm sao cho độ dài chữ ký tối thiểu nhất có thể mà không thể giả mạo chữ ký đƣợc).  Vịệc nghiên cứu và phát triển các lược đồ chữ ký số rút gọn thể hiện tính khoa học và thực tiễn cao. Số hóa bởi Trung tâm Học liệu http://www.lrc-tnu.edu.vn/ 2 Kết quả nghiên cứu của đề tài nhằm góp phần định hƣớng và tự phát triển các lƣợc đồ chữ ký số có khả năng ứng dụng trong thực tiễn. Mục tiêu của đề tài: Nghiên cứu các giải pháp xây dựng và khả năng ứng dụng chữ ký số trong bảo vệ an toàn thông tin. - Mật mã khóa công khai; - Hàm băm mật mã; - Các kiểu chữ ký số; - Các ứng dụng của chữ ký số. Nghiên cứu các cơ sở toán học, mô hình xây dựng và đánh giá các lƣợc đồ chữ ký số. - Chữ ký số dựa trên tính khó của bài toán phân tích một số nguyên lớn ra các thừa số nguyên tố; - Chữ ký số dựa trên tính khó của bài toán logarit rời rạc; - Chữ ký số dựa trên tính khó của bài toán logarit rời rạc trên các điểm nhánh của vành Elliptic. Phát triển phƣơng pháp rút gọn chữ ký số dựa trên tính khó của bài toán phân tích một số nguyên lớn ra các thừa số nguyên tố. Xây dựng lƣợc đồ rút gọn chữ ký số mới và biến thể của nó. Đánh giá độ an toán của các lƣợc đồ đề xuất dựa trên các phƣơng trình chứng minh đã đƣợc công nhận trên thế giới. Xây dựng các chƣơng trình mô phỏng và đánh giá kết quả nghiên cứu cần đạt đƣợc. Cấu trúc của luận văn gồm 3 chƣơng: Chƣơng 1: Tổng quan về mật mã khóa công khai và chữ ký số Chƣơng 2: Các cơ sở toán học và mô hình xây dựng các lƣợc đồ chữ ký số Chƣơng 3: Phát triển phƣơng pháp rút gọn chữ ký số. Số hóa bởi Trung tâm Học liệu http://www.lrc-tnu.edu.vn/ 3 Chƣơng 1 TỔNG QUAN VỀ MẬT MÃ KHOÁ CÔNG KHAI VÀ CHỮ KÝ SỐ 1.1. Tổng quan về mật mã 1.1.1. An toàn và bảo mật 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 dữ liệu cũng đƣợc đổi mới. Bảo vệ an toàn thông tin dữ liệu là một chủ đề rộng, có liên quan đến nhiều lĩnh vực và trong thực tế có thể có rất nhiều phƣơng pháp đƣợc thực hiện để bảo vệ an toàn thông tin dữ liệu. Các phƣơng pháp bảo vệ an toàn thông tin dữ liệu 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 dụng riêng rẽ hoặc phối kết hợp. Môi trƣờng khó bảo vệ thông tin nhất và 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. An toàn thông tin bao gồm những nội dung sau: - Tính bí mật: Tính kín đáo riêng tƣ của thông tin - Tính xác thực của thông tin, bao gồm xác thực đối tác (bài toán nhận dạng), xác thực thông tin trao đổi - Tính trách nhiệm: Đảm bảo ngƣời gửi thông tin không thể thoái thác trách nhiệm về thông tin mà mình đã gửi. Để đảm bảo an toàn thông tin dữ liệu 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 dữ liệu đƣợ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. Có hai loại hành vi xâm phạm thông tin dữ liệu đó Số hóa bởi Trung tâm Học liệu http://www.lrc-tnu.edu.vn/ 4 là: vi phạm chủ động và vi phạm thụ độ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 đó có 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 chủ động là dạng vi phạm có thể làm thay đổi nội dung, xóa bỏ, làm trễ, sắ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 một số thông tin ngoại lai để làm sai lệch thông tin trao đổi. Vi phạm chủ động dễ phát hiện nhƣng để ngăn chặn thì khó khăn hơn nhiều. Một thực tế là không có một biện pháp 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.2. Mật mã học Mật mã học bao gồm hai lĩnh vực: mã hóa (cryptography) và thám mã (cryptanalysis-codebreaking) trong đó: - Mã hóa: nghiên cứu các thuật toán và phƣơng thức để đảm bảo tính bí mật và xác thực của thông tin (thƣờng là dƣới dạng các văn bản lƣu trữ trên máy tính). Các sản phẩm của lĩnh vực này là các hệ mật mã, các hàm băm, các hệ chữ ký số, các cơ chế phân phối, quản lý khóa và các giao thức mật mã: - Thám mã: Nghiên cứu các phƣơng pháp phá mã hoặc tạo mã giả. Sản phẩm của lĩnh vực này là các phƣơng pháp thám mã, các phƣơng pháp giả mạo chữ ký, các phƣơng pháp tấn công các hàm băm và các giao thức mật mã. Trong giới hạn của luận văn này tác giả chủ yếu vào tìm hiểu một số hệ mã hóa, các hàm băm, các hệ chữ ký số. Nhƣ thế mã hóa có thể đƣợc định nghĩa đơn giản nhƣ sau: Định nghĩa 1.1 Mã hóa (cryptography) là một ngành khoa học của các phương pháp truyền tin bảo mật. Trong tiếng Hy Lạp, “Cryto” (krypte) có nghĩa là che dấu hay đảo lộn, còn “Graphy” (grafik) có nghĩa là từ. Số hóa bởi Trung tâm Học liệu http://www.lrc-tnu.edu.vn/ 5 Ngƣời ta quan niệm rằng: những từ, những ký tự của văn bản gốc có thể hiểu đƣợc sẽ cấu thành nên bản rõ (P – Plaintext), thƣờng thì đây là các đoạn văn bản trong một ngôn ngữ nào đó; còn những từ, những ký tự ở dạng bí mật không thể hiểu đƣợc thì đƣợc gọi là bản mã (C – Ciphertext). a. Vai trò của hệ mật mã Các hệ mật mã phải thực hiện đƣợc các vai trò sau: - Hệ mật mã phải che dấu đƣợc nội dung của văn bản rõ (Plain Text) để đảm bảo sao cho chỉ ngƣời chủ hợp pháp của thông tin mới có quyền truy cập thông tin (Secrety), hay nói cách khác là chống truy cập không đúng quyền hạn. - Tạo các yếu tố xác thực thông tin, đảm bảo thông tin lƣu hành trong hệ thống đến ngƣời nhận hợp pháp là xác thực (Authenticity). - Tổ chức các sơ đồ chữ ký số, đảm bảo không có hiện tƣợng giả mạo, mạo danh để gửi thông tin trên mạng. Ƣu điểm lớn nhất của bất kỳ hệ mật mã nào đó là có thể đánh giá đƣợc độ phức tạp tính toán mà “kẻ địch” phải giải quyết bài toán để có thể lấy đƣợc thông tin của dữ liệu đã đƣợc mã hóa. Tuy nhiên mỗi hệ mật mã có một số ƣu và nhƣợc điểm khác nhau, nhƣng nhờ đánh giá đƣợc độ phức tạp tính toán mà ta có thể áp dụng các thuật toán mã hóa khác nhau cho từng ứng dụng cụ thể tùy theo từng yêu cầu về độ an toàn. b. Các thành phần của một hệ mật mã: 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: - P là một tập hợp hữu hạn các bản rõ (Plain Text), nó đƣợc gọi là không gian bản rõ. - C là tập các hữu hạn các bản mã (Crypto), nó còn đƣợc gọi là không gian các bản mã. Mỗi phần tử của C có thể nhận đƣợc bằng cách áp dụng phép mã hóa Ek lên một phần tử của P, với k K. - K là tập hữu hạn các khóa hay còn gọi là không gian khóa. Đối với mỗi phần tử k của K đƣợc gọi là một khóa (Key). Số lƣợng của không gian khóa phải đủ lớn để “kẻ địch” không đủ thời gian để thử mọi khóa có thể (phƣơng pháp vét cạn). Số hóa bởi Trung tâm Học liệu http://www.lrc-tnu.edu.vn/ 6 - Đối với mỗi 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 mà: dk (ek(x)) = x với mọi bản rõ x P. c. Phân loại hệ mật mã Có nhiều cách để phân loại hệ mật mã. Dựa vào cách truyền khóa có thể phân các hệ mật mã thành hai loại: - Hệ mật đối xứng (hay còn gọi là mật mã khóa bí mật): là những hệ mật 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. Hình 1.1. Cách mã hóa khóa bí mật - Hệ mật mã bất đối xứng (hay còn gọi là mật mã khóa công khai): Các hệ mật này dùng một khóa để mã hóa sau đó 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ể suy đƣợc từ khóa kia. Khóa dùng để mã hóa có thể công khai nhƣng khóa dùng để giải mã phải giữ bí mật. Hình 1.2. Cách mã hóa khóa công cộng Ngoài ra nếu dựa vào thời gian đƣa ra hệ mật mã ta còn có thể phân làm hai loại: Mật mã cổ điển (là hệ mật mã ra đời trƣớc năm 1970) và mật mã hiện đại (ra Số hóa bởi Trung tâm Học liệu http://www.lrc-tnu.edu.vn/ 7 đời sau năm 1970). Còn nếu dựa vào cách thức tiến hành mã thì hệ mật mã 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.1.3. Tiêu chuẩn đánh giá hệ mật mã Để đánh giá một hệ mật mã ngƣời ta thƣờng đánh giá thông qua các tính chất sau: - Độ an toàn: Một hệ mật mã đƣợc đƣa vào sử dụng điều đầu tiên phải có độ an toàn cao. Ƣu điểm của mật mã là có thể đánh giá đƣợc độ an toàn thông qua độ an toàn tính toán mà không cần phải cài đặt. Một hệ mật mã đƣợc coi là an toàn nếu để phá hệ mật mã này phải dùng n phép toán. Mà để giải quyết n phép toán cần thời gian vô cùng lớn, không thể chấp nhận đƣợc. Một hệ mật mã đƣợc gọi là tốt thì nó cần phải đảm bảo các tiêu chuẩn sau: + Chúng phải có phƣơng pháp bảo vệ mà chỉ dựa trên sự bí mật của các khóa, công khai thuật toán. + Khi cho khóa công khai ek và bản rõ P thì chúng ta dễ dàng tính đƣợc eka(P) = C. Ngƣợc lại khi cho dk và bản mã C thì dễ dàng tính đƣợc dk(M) = P. Khi không biết dk thì không có khả năng tìm đƣợc M từ C, nghĩa là khi cho hàm f: X → Y thì việc tính y = f(x) với mọi x X là dễ còn việc tìm x khi biết y lại là vấn đề khó và nó đƣợc gọi là hàm một chiều. + Bản mã C không đƣợc có các đặc điểm gây chú ý, nghi ngờ. - Tốc độ mã và giải mã: Khi đánh giá hệ mật mã chúng ta phải chú ý đến tốc độ mã và giải mã. Hệ mật tốt thì thời gian mã và giải mã nhanh. - Phân phối khóa: Một hệ mật mã phụ thuộc vào khóa, khóa này đƣợc truyền công khai hay truyền khóa bí mật. Phân phối khóa bí mật thì chi phí sẽ cao hơn so với các hệ mật có khóa công khai. Vì vậy đây cũng là một tiêu chí khi lựa chọn hệ mật mã. 1.2. Mật mã khóa công khai 1.2.1. Giới thiệu Trong mô hình mật mã cổ điển mà cho tới nay vẫn còn đang đƣợc nghiên cứu Alice (ngƣời gửi) và Bob (ngƣời nhận) bằng cách chọn một khóa bí mật K. Sau đó. Số hóa bởi Trung tâm Học liệu http://www.lrc-tnu.edu.vn/ 8 Alice dùng khóa K để mã hóa theo luật ek và Bob dùng khóa K đó để giải mã theo luật giải dk. Trong hệ mật này, dk hoặc giống nhƣ ek hoặc dễ dàng nhận đƣợc từ nó vì quá trình giải mã hoàn toàn tƣơng tự nhƣ quá trình mã, nhƣng thủ tục khóa thì ngƣợc lại. Nhƣợc điểm lớn của hệ mật này là nếu ta để lộ ek thì làm cho hệ thống mất an toàn, chính vì vậy chúng ta phải tạo cho các hệ mật mã này một kênh an toàn mà kinh phí để tạo một kênh an toàn không phải là rẻ. Ý tƣởng xây dựng một hệ mật mã khóa công khai là tìm một hệ mật mã không có khả năng tính toán để xác định dk nếu biết đƣợc ek. Nếu thực hiện đƣợc nhƣ vậy thì quy tắc mã ek có thể đƣợc công khai bằng cách công bố nó trong danh bạ, và khi Alice (ngƣời gửi) hoặc bất cứ một ai đó muốn gửi một bản tin cho Bob (ngƣời nhận) thì ngƣời đó không phải thông tin trƣớc với Bob về khóa mật, mà ngƣời gửi sẽ mã hóa bản tin bằng cách dùng luật mã công khai ek. Khi bản tin này đƣợc truyền cho Bob (ngƣời nhận) thì chỉ có duy nhất Bob mới có thể giải đƣợc bản tin này bằng cách sử dụng luật giải mã bí mật dk. Ý tƣởng về hệ mật mã khóa công khai đã đƣợc Diffie và Heliman đƣa ra vào năm 1976. Còn việc thực hiện hệ mật mã khóa công khai thì lại đƣợc Rivest. Shamin và Adieman đƣa ra đầu tiên vào năm 1977. Họ đã tạo nên hệ mật mã RSA nổi tiếng. Kể từ đó đã có một số hệ mật mã đƣợc công bố, độ mật của từ hệ dựa trên các bài toán tính toán khác nhau. Trong đó quan trọng nhất là các hệ mật mã sau: - Hệ mật mã RSA Độ bảo mật của hệ RSA dựa trên độ khó của việc phân tích ra thừa số nguyên tố các số nguyên tố lớn. - Hệ mật mã xếp balô Merkle – Hellman. Hệ mật mã này và các hệ có liên quan dựa trên tính khó giải của bài toán tổng các tập con. - Hệ mật mã McEliece Hệ mật mã này dựa trên lý thuyết mã đại số và vẫn đƣợc coi là an toàn. Hệ mật mã McEliece dựa trên bài toán giải mã cho các mã tuyến tính. - Hệ mật mã ElGamal Số hóa bởi Trung tâm Học liệu http://www.lrc-tnu.edu.vn/ 9 Hệ mật mã ElGamal dựa trên tính khó giải của bài toán Logarit rời rạc trên các trƣờng hữu hạn. Số hóa bởi Trung tâm Học liệu http://www.lrc-tnu.edu.vn/ 10 - Hệ mật mã Chor – Rivest Hệ mật mã Chor – Rivest cũng đƣợc xem nhƣ một loại hệ mật xếp balô. Tuy nhiên hệ mật này vẫn còn đƣợc coi là hệ mật mã an toàn. - Hệ mật mã trên các đường cong Elliptic. Các hệ này là biến tƣớng của hệ mật mã khác, chúng làm việc trên các đƣờng cong Elliptic chứ không phải trên các trƣờng hữu hạn. Hệ mật mã này đảm bảo độ mật với khóa số nhỏ hơn các hệ mật khóa công khai khác. Một chú ý quan trọng là một hệ mật mã khóa công khai không bao giờ có thể đảm bảo đƣợc độ mật tuyệt đối (an toàn vô điều kiện). Sở dĩ nhƣ vậy vì đối phƣơng nghiên cứu một bản mã C có thể mã lần lƣợt các bản rõ có thể bằng luật công khai ek cho tới khi anh ta tìm đƣợc một bản rõ duy nhất P bảo đảm C = ek(P). Bản rõ P này chính là kết quả giải mã của C. Bởi vậy ta chỉ nghiên cứu độ mật về mặt tính toán của hệ này. Một chú ý quan trọng và có ích khi nghiên cứu nữa là khái niệm về hàm cửa sập một chiều. Ta định nghĩa khái niệm này một cách không hình thức. Định nghĩa 1.2 Hàm f: X→Y được gọi là hàm một chiều nếu tính y = f(x) với mọi x X là dễ nhưng việc tìm x khi biết y lại là vấn đề khó. Thực ra phát biểu trên chỉ là định nghĩa phi hình thức (do thuật ngữ “khó” đƣợc dùng đến là không định lƣợng và thậm chí sau này chúng ta đã biết là ngay cả khi đã định lƣợng bằng sự không tồn tại thuật toán giải bài toán ngƣợc trong phạm vi đa thức thì khái niệm “khó” nêu trên có tồn tại hay không cũng chƣa đƣợc ai khẳng định rõ ràng) và điều đáng tiếc hơn nữa là tất cả các hàm ứng cử viên cho khái niệm này cho đến nay chỉ mới “đƣợc coi là một chiều”. Chúng ta dễ dàng thống nhất đƣợc với nhau là chỉ riêng hàm một chiều là không đủ để xây dựng thành một luật mã theo kiểu công khai hàm mã hóa do vì chính bản thân chủ nhân của bức điện mật cũng gặp phải hoàn cảnh tƣơng tự nhƣ ngƣời khác. Nhƣ vậy để có thể giải mã một cách hữu hiệu thì ngƣời giải mã phải có một “hiểu biết tuyệt mật” nào đó về khóa giải (một hiểu biết theo kiểu nếu biết nó thì cách giải dễ dàng) “hiểu biết tuyệt mật” này đƣợc gọi là cửa sập. Hàm một chiều nhƣ trên đƣợc gọi là hàm một chiều có cửa sập. Số hóa bởi Trung tâm Học liệu http://www.lrc-tnu.edu.vn/ 11 Dĩ nhiên dù không biết cửa sập thì ngƣời thám mã vẫn có thể sử dụng hiểu biết về hàm f để lần lƣợt tính tất cả các giá trị f(x) cho mọi bản rõ x cho tới khi tìm đƣợc bản rõ thỏa mãn y = f(x). Bản rõ tìm đƣợc trên chính là kết quả giải mã của y. Ngoài ra ngƣời thám mã còn có thể sử dụng nhiều phƣơng pháp tấn công khác nhằm vào đặc thù riêng của từng hàm f để tìm ra bản rõ trong các trƣờng hợp riêng rẽ khác chứ không nhất thiết phải giải bài toán ngƣợc. Tóm lại độ an toàn của hệ mật mã khóa công khai không chỉ phụ thuộc vào độ khó của việc giải bài toán ngƣợc mà tính bền của sự an toàn này còn phụ thuộc vào các phƣơng pháp tấn công của các thám mã, vả lại nhƣ đã trình bày ở trên thì toàn bộ các hệ mật mã khóa công khai đang đƣợc sử dụng đều chƣa đƣợc sự khẳng định về tính “khó” mà ngay cả khi đã có sự đảm bảo này thì có sự tiến bộ không ngừng của công nghệ tính toán, thì hiển nhiên nhiều vấn đề chƣa thể chấp nhận đƣợc trong hiện tại sẽ đƣợc chấp nhận trong tƣơng lai. Hàm mã công khai ek của Bob phải là một hàm dễ tính toán. Song việc tính hàm ngƣợc (tức là hàm giải mã) phải rất khó khăn (đối với bất kỳ ai không phải là Bob). Đặc tính dễ tính toán nhƣng khó tính ngƣợc thƣờng đƣợc gọi là đặc tính một chiều. Bởi vậy điều cần thiết là ek phải là một hàm một chiều. Các hàm một chiều đóng một vai trò trọng yếu trong mật mã học: Chúng rất quan trọng trong việc xây dựng các hệ mật mã khóa công khai và trong nhiều lĩnh vực khác. Đáng tiếc là, mặc dù có rất nhiều hàm đƣợc coi là hàm một chiều nhƣng cho tới nay vẫn không tồn tại đƣợc một hàm nào có thể minh chứng đƣợc là hàm một chiều. Để xây dựng một hệ một hệ mật mã khóa công khai thì việc tìm một hàm một chiều vẫn chƣa đủ. Ta không muốn ek là hàm một chiều đối với Bob vì anh ta phải có khả năng giải mã các bản tin nhận đƣợc có hiệu quả. Điều cần thiết là Bob phải có một cửa sập chứa thông tin bí mật cho phép dễ dàng tìm ngƣợc của ek. Nhƣ vậy Bob có thể giải mã một cách hữu hiệu vì anh ta có một hiểu biết tuyệt mật nào đó về K. Bởi vậy một hàm đƣợc gọi là cửa sập một chiều nếu nó là hàm một chiều và nó sẽ trở nên dễ tính ngƣợc nếu biết một cửa sập nhất định. Số hóa bởi Trung tâm Học liệu http://www.lrc-tnu.edu.vn/ 12 1.2.2. Độ an toàn của mật mã công khai Về khía cạnh an toàn, các thuật toán mật mã hóa khóa bất đối xứng cũng không khác nhiều với các thuật toán mã hóa khóa đối xứng. Có những thuật toán đƣợc dùng rộng rãi, có thuật toán chủ yếu trên lý thuyết; có thuật toán vẫn đƣợc xem là an toàn, có thuật toán đã bị phá vỡ… Cũng cần lƣu ý là những thuật toán đƣợc dùng rộng rãi không phải lúc nào cũng đảm bảo an toàn. Một số thuật toán có những chứng minh về độ an toàn với những tiêu chuẩn khác nhau. Nhiều chứng mình gắn với việc phá vỡ thuật toán với những bài toán nổi tiếng vẫn đƣợc cho là không có lời giải trong thời gian đa thức. Nhìn chung, chƣa có thuật toán nào đƣợc chứng minh là an toàn tuyệt đối (nhƣ hệ thống mật mã sử dụng khóa mật một lần). Vì vậy, cũng giống nhƣ tất cả các thuật toán mật mã nói chung, các thuật toán mã hóa khóa công khai cần phải đƣợc sử dụng một cách thận trọng. 1.2.3. Các ứng dụng của mật mã công khai Ứng dụng rõ ràng nhất của mật mã hóa khóa công khai là bảo mật: một văn bản đƣợc mã hóa bằng khóa công khai của một ngƣời sử dụng thì chỉ có thể giải mã với khóa bí mật của ngƣời đó. Các thuật toán tạo chữ ký số khóa công khai có thể dùng để nhận thự. Một ngƣời sử dụng có thể mã hóa văn bản với khóa bí mật của mình. Nếu một ngƣời khác có thể giải mã với khóa công khai của ngƣời gửi thì có thể khẳng định rằng văn bản thực sự xuất phát từ ngƣời nắm giữ khóa bí mật tƣơng thích với khóa công khai đó. Các đặc điểm trên còn có ích cho nhiều ứng dụng khác nhƣ: tiền điện tử thỏa thuận khóa… 1.2.4. Độ phức tạp tính toán của mã công khai. Để đạt đƣợc độ an toàn tƣơng đƣơng, thuật toán mật mã hóa khóa bất đối xứng đòi hỏi khối lƣợng tính toán nhiều hơn đáng kể so với các thuật toán mật mã hóa khóa đối xứng. Vì thế trong thực tế hai dạng mã hóa này thƣờng đƣợc dùng một cách bổ sung cho nhau để đạt đƣợc hiệu quả cao. Trong mô hình này, một bên tham gia trao đổi Số hóa bởi Trung tâm Học liệu http://www.lrc-tnu.edu.vn/ 13 thông tin tạo ra một khóa đối xứng dùng cho phiên giao dịch. Khóa này sẽ đƣợc trao đổi an toàn thông quan hệ thống mã hóa khóa bất đối xứng. Sau đó hai bên trai đổi thông tin bí mật bằng hệ thống mã hóa đối xứng trong suốt phiên giao dịch. 1.2.5. Những vấn đề về thám mã Tồn tại khả năng một ngƣời nào đó có thể tìm ra đƣợc khóa bí mật. Không giống với hệ thống mật mã sử dụng một lần (one-time pad) hoặc tƣơng đƣơng, chƣa có thuật toán mã hóa khóa bất đối xứng nào đƣợc chứng minh là an toàn trƣớc các tấn công dựa trên bản chất toán học của thuật toán. Khả năng tồn tại một mối quan hệ nào đó giữa 2 khóa hay một điểm yếu của thuật toán dẫn tới cho phép giải mã không cần tới khóa hay chỉ cần khóa mã mã công khai vẫn chƣa đƣợc loại trừ. An toàn của các thuật toán này đều dựa trên các ƣớc lƣợng về khối lƣợng các phép tính cần phải tính toán để giải các bài toán gắn với chúng nhƣng các ƣớc lƣợng này lại luôn thay đổi tùy thuộc khả năng của máy tính và các phát hiện toán học mới. Mặc dù vậy, độ an toàn của các thuật toán mật mã khóa công khai cũng tƣơng đối đảm bảo. Nếu thời gian để phá một mã (bằng phƣơng pháp duyệt toàn bộ) đƣợc ƣớc lƣợng là 1000 năm thì thuật toán này hoàn toàn có thể dùng để mã hóa các thông tin về thẻ tín dụng – Rõ ràng là thời gian phá mã lớn hơn nhiều lần thời gian tồn tại của thẻ (vài năm). Nhiều điểm yếu của một số thuật toán mật mã hóa khóa bất đối xứng đã đƣợc tìm ra trong quá khứ. Thuật toán đóng gói ba lô là một ví dụ. Nó chỉ đƣợc xem là không an toàn khi một dạng tấn công không lƣờng trƣớc bị phát hiện. Gần đây, một số dạng tấn công đã đơn giản hóa việc tìm khóa giải mã dựa trên việc đo đạc chính xác thời gian mà một hệ thống phần cứng thực hiện mã hóa. Vì vậy, việc sử dụng mã hóa khóa bất đối xứng không thể đảm bảo an toàn tuyệt đối. Đây là một lĩnh vực đang đƣợc tích cực nghiên cứu để tìm ra những dạng tấn công mới. Một điểm yếu tiềm tàng trong việc sử dụng khóa bất đối xứng là khả năng bị tấn công dạng kẻ tấn công đứng giữa (man in the middle attack): kẻ tấn công lợi dụng việc phân phối khóa công khai để thay đổi khóa công khai. Sau khi đã giả mạo đƣợc khóa công khai, kẻ tấn công đứng ở giữa 2 bên để nhận các gói tin, giải mã rồi lại mã hóa khóa đúng và gửi đến nơi nhận để tránh bị phát hiện. Dạng tấn công kiểu Số hóa bởi Trung tâm Học liệu http://www.lrc-tnu.edu.vn/ 14 này có thể phòng ngừa bằng các phƣơng pháp trao đổi khóa an toàn nhằm đảm bảo nhận thực ngƣời gửi và toàn vẹn thông tin. Một điều cần lƣu ý là khi các chính phủ quan tâm đến dạng tấn công này: họ có thể thuyết phục (hay bắt buộc) nhà cung cấp chứng thực số xác nhận một khóa giả mạo và có thể đọc các thông tin mã hóa. 1.3. Hàm băm mật mã 1.3.1. Tổng quan về hàm băm a. Định nghĩa hàm băm Hàm băm mật mã là hàm toán học chuyển đổi một thông điệp có độ dài bất kỳ thành một dãy bit có độ dài cố định (tùy thuộc vào thuật toán băm). Dãy bit này đƣợc gọi là thông điệp rút gọn (message digest) hay giá trị băm (hash value), đại diện cho thông điệp ban đầu. Ví dụ 1.1 Nhƣ khi B muốn kí một bức điện x (độ dài bất kì), đầu tiên anh ta tính cốt của bức điện z = h(x) (độ dài cố định) và sau đó kí y = sigk9(z). Anh ta phát cặp (x,y) lên kênh truyền, bây giờ việc kiểm tra có thể thực hiện bằng việc tính lại cốt của bức điện z = h(x), sau đó kiểm tra verk(x,y) có băng TRUE hay không. Hình 1.3. Hàm băm trong chữ ký số Dễ dàng nhận thấy rằng hàm băm h không phải là một song ánh. Do đó, với thông điệp x bất kỳ, tồn tại thông điệp x’ ≠ x sao cho h(x) = h(x’). Lúc này ta nói rằng “có sự đụng độ xảy ra”. Một hàm băm h đƣợc gọi là an toàn (hay “ít bị đụng Số hóa bởi Trung tâm Học liệu http://www.lrc-tnu.edu.vn/ 15 độ”) khi không thể xác định đƣợc (bằng cách tính toán) cặp thông điệp x và x‟ thỏa mãn x’ ≠ xvà h(x) = h(x’). Trên thực tế, các thuật toán băm là hàm một chiều, do đó, rất khó để xây dựng lại thông điệp ban đầu từ thông điệp rút gọn. Hàm băm giúp xác định đƣợc tính toàn vẹn dữ liệu của thông tin: mọi thay đổi, dù là rất nhỏ, trên thông điệp cho trƣớc, ví dụ nhƣ đổi giá trị 1 bit, đều làm thay đổi thông điệp rút gọn tƣơng ứng. Tính chất này hữu ích trong việc phát sinh, kiểm tra chữ ký số, các đoạn mã chứng nhận thông điệp, phát sinh số ngẫu nhiên, tạo ra khóa cho quá trình mã hóa… b. Tính an toàn của hàm băm. - Tính an toàn của hàm băm đối với hiện tƣợng đụng độ Hàm băm đƣợc xem là an toàn đối với hiện tƣợng đụng độ khi rất khó tìm đƣợc hai thông điệp có cùng giá trị băm. Nhận xét: Trong một tập hợp mà các phần tử mang một trong N giá trị cho trƣớc với xác suất bằng nhau, chúng ta cần khoảng phép thử ngẫu nhiên để tìm ra một cặp phần tử có cùng giá trị. Nhƣ vậy, phƣơng pháp hàm băm đƣợc xem là an toàn đối với hiện tƣợng đụng độ nếu chƣa có phƣơng pháp tấn công nào có thể tìm ra cặp thông điệp có cùng giá trị hàm băm với số lƣợng tính toán ít hơn đáng kể so với ngƣỡng 2n/2, với n là kích thƣớc (tính bằng bit) của giá trị băm. Phƣơng pháp tấn công dựa vào đụng độ: + Tìm ra 2 thông điệp có nội dung khác nhau nhƣng cùng giá trị băm. + Ký trên một thông điệp, sau đó, ngƣời ký sẽ không thừa nhận đây là chữ ký của mình mà nói rằng mình đã ký trên một thông điệp khác. + Nhƣ vậy, cần phải chọn 2 thông điệp “đụng độ” với nhau trƣớc khi ký. - Tính 1 chiều Hàm băm đƣợc xem là hàm một chiều khi cho trƣớc giá trị băm, không thể tái tạo lại thông điệp ban đầu, hay còn gọi là “tiềm ảnh” (“pre-image”). Nhƣ vậy, trong trƣờng hợp lý tƣởng, cần phải thực hiện hàm băm cho khoảng 2n thông điệp để tìm ra đƣợc “tiềm ảnh” tƣơng ứng với một giá trị băm. Số hóa bởi Trung tâm Học liệu http://www.lrc-tnu.edu.vn/
- Xem thêm -