Luận án tiến sĩ Kỹ thuật: Nghiên cứu xây dựng một lớp hàm băm mở rộng mới và khả năng ứng dụng

Chia sẻ: Trần Văn Yan | Ngày: | Loại File: PDF | Số trang:202

Thêm vào BST

Báo xấu

46
lượt xem 10
download

Download Vui lòng tải xuống để xem tài liệu đầy đủ

Luận án được nghiên cứu với mục tiêu nhằm Xây dựng được một lớp các hàm băm mở rộng mới (là lớp hàm băm có độ khuếch tán cao) với mục đích mở rộng chiều dài mã băm qua việc ghép móc xích để tạo ra sự phụ thuộc các bít đầu ra với các khối bít đầu vào (có kiểm chứng qua mô phỏng). Đồng thời đề xuất khả năng ứng dụng các hàm băm mở rộng mới xây dựng.

Chủ đề:

Bình luận(0) Đăng nhập để gửi bình luận!

Lưu

Nội dung Text: Luận án tiến sĩ Kỹ thuật: Nghiên cứu xây dựng một lớp hàm băm mở rộng mới và khả năng ứng dụng

BỘ THÔNG TIN VÀ TRUYỀN THÔNG HỌC VIỆN CÔNG NGHỆ BƯU CHÍNH VIỄN THÔNG ******************************************** NGUYỄN TOÀN THẮNG NGHIÊN CỨU XÂY DỰNG MỘT LỚP HÀM BĂM MỞ RỘNG MỚI VÀ KHẢ NĂNG ỨNG DỤNG LUẬN ÁN TIẾN SĨ KỸ THUẬT HÀ NỘI – 2017
BỘ THÔNG TIN VÀ TRUYỀN THÔNG HỌC VIỆN CÔNG NGHỆ BƯU CHÍNH VIỄN THÔNG ******************************************** NGUYỄN TOÀN THẮNG NGHIÊN CỨU XÂY DỰNG MỘT LỚP HÀM BĂM MỞ RỘNG MỚI VÀ KHẢ NĂNG ỨNG DỤNG Chuyên ngành : Kỹ thuật Điện tử Mã ngành : 62.52.02.03 LUẬN ÁN TIẾN SĨ KỸ THUẬT NGƯỜI HƯỚNG DẪN KHOA HỌC: GS.TSKH. NGUYỄN XUÂN QUỲNH HÀ NỘI – 2017
i LỜI CAM ĐOAN Tôi xin cam đoan đây là công trình nghiên cứu của tôi. Các nội dung là trung thực và kết quả trình bày trong luận án chưa được công bố ở bất kỳ công trình nghiên cứu nào khác. Tác giả Nguyễn Toàn Thắng
ii LỜI CẢM ƠN Tôi xin tỏ lòng biết ơn đến thầy GS.TSKH. Nguyễn Xuân Quỳnh, người đã trực tiếp định hướng, hướng dẫn và tạo mọi điều kiện thuận lợi cho tôi trong suốt quá trình nghiên cứu. Tôi xin chân thành cảm ơn Học viện Công nghệ Bưu chính Viễn thông - nơi tôi làm luận án - đã tạo những điều kiện thuận lợi để giúp tôi hoàn thành chương trình nghiên cứu. Tôi xin cảm ơn khoa Quốc tế và Đào tạo sau đại học, Ban Tuyên giáo Tỉnh ủy, Sở Thông tin và Truyền thông tỉnh Ninh Bình, cũng như các đồng nghiệp đã tạo điều kiện giúp đỡ tôi hoàn thành được đề tài nghiên cứu của mình. Cuối cùng là sự biết ơn tới gia đình, bạn bè đã tạo điều kiện, động viên tôi, cho tôi có đủ nghị lực để hoàn thành luận án. Hà Nội, tháng 11 năm 2017
iii MỤC LỤC LỜI CAM ĐOAN ..................................................................................................... i LỜI CẢM ƠN .......................................................................................................... ii MỤC LỤC ............................................................................................................... iii DANH MỤC CÁC KÝ HIỆU, CÁC TỪ VIẾT TẮT ............................................. vi DANH MỤC CÁC BẢNG.................................................................................... viii DANH MỤC CÁC HÌNH VẼ.................................................................................. x PHẦN MỞ ĐẦU ...................................................................................................... 1 1. MỞ ĐẦU ....................................................................................................... 1 2. TÌNH HÌNH NGHIÊN CỨU......................................................................... 2 3. LÝ DO CHỌN ĐỀ TÀI ................................................................................. 7 4. MỤC TIÊU NGHIÊN CỨU .......................................................................... 8 5. ĐỐI TƯỢNG, PHẠM VI NGHIÊN CỨU .................................................... 9 6. PHƯƠNG PHÁP NGHIÊN CỨU ................................................................. 9 7. Ý NGHĨA KHOA HỌC VÀ THỰC TIỄN CỦA ĐỀ TÀI ............................ 9 CHƯƠNG 1. TỔNG QUAN VỀ MẬT MÃ VÀ HÀM BĂM .............................. 10 1.1. GIỚI THIỆU ................................................................................................ 10 1.2. PHƯƠNG PHÁP XÂY DỰNG CÁC HỆ MẬT CƠ BẢN .......................... 10 1.2.1. Phương pháp xây dựng các hệ mật khóa bí mật .......................... 10 1.2.2. Phương pháp xây dựng các hệ mật khóa công khai .................... 24 1.3. HÀM BĂM .................................................................................................. 31 1.3.1. Mô tả hàm băm ............................................................................ 31 1.3.2. Các hàm băm có khóa ................................................................. 33 1.3.3. Các hàm băm không có khóa ...................................................... 34 1.3.4. Một số phương pháp toàn vẹn dữ liệu và xác thực thông báo .... 36 1.4. CẤP SỐ NHÂN CYCLIC............................................................................ 38
iv 1.4.1. Nhóm nhân của vành đa thức ...................................................... 38 1.4.2. Các cấp số nhân cyclic cấp n ....................................................... 38 1.4.3. Phân hoạch vành đa thức ............................................................. 39 1.5. KẾT LUẬN CHƯƠNG I ............................................................................. 41 CHƯƠNG 2. XÂY DỰNG CÁC HÀM BĂM MỚI ............................................ 43 2.1. GIỚI THIỆU ................................................................................................ 43 2.2. HÀM BĂM DỰA TRÊN HỆ MẬT THEO SƠ ĐỒ LAI-MASSEY ........... 43 2.2.1. Hệ mật sử dụng cấp số nhân cyclic theo sơ đồ LAI-MASSEY .. 43 2.2.2. Xây dựng hàm băm trên cơ sở hệ mật ......................................... 50 2.3. HÀM BĂM DỰA TRÊN HỆ MẬT MÃ LAI GHÉP .................................. 55 2.3.1. Bài toán Logarit rời rạc và hệ mật POHLIG-HELLMAN .......... 56 2.3.2. Đề xuất một phương pháp xây dựng hệ mật mã lai ghép............ 59 2.3.3. Khả năng xây dựng hàm băm từ hệ mật ...................................... 66 2.4. HÀM BĂM SỬ DỤNG CÁC CẤP SỐ NHÂN CYCLIC ........................... 67 2.4.1. Sơ đồ hàm băm MDC-2 sử dụng lưu đồ FEISTEL ..................... 67 2.4.2. Xây dựng hàm băm và kết quả mô phỏng ................................... 68 2.5. KẾT LUẬN CHƯƠNG II ............................................................................ 74 CHƯƠNG 3. XÂY DỰNG MỘT LỚP CÁC HÀM BĂM MỞ RỘNG MỚI ...... 76 3.1. GIỚI THIỆU ................................................................................................ 76 3.2. XÂY DỰNG HÀM BĂM MỞ RỘNG MỚI MDC-3 .................................. 77 3.3. HÀM BĂM DỰA TRÊN HỆ MẬT MÃ KHỐI KẾT HỢP SƠ ĐỒ LAI- MASSEY VỚI FEISTEL............................................................................ 86 3.3.1. Hệ mật mã khối kết hợp sơ đồ LAI-MASSEY và FEISTEL ...... 87 3.3.2. Xây dựng hàm băm trên cơ sở hệ mật kết hợp ............................ 93 3.4. XÂY DỰNG HÀM BĂM MỞ RỘNG MỚI MDC 512 BÍT ....................... 98 3.4.1. Mô tả hệ mật mã khối 256 bít ..................................................... 98 3.4.2. Đánh giá độ khuếch tán của hệ mật........................................... 102
v 3.4.3. Xây dựng hàm băm 512 bit trên cơ sở hệ mật .......................... 106 3.5. KẾT LUẬN CHƯƠNG III ........................................................................ 110 CHƯƠNG 4. KHẢ NĂNG ỨNG DỤNG CỦA HÀM BĂM XÂY DỰNG MỚI112 4.1. GIỚI THIỆU .............................................................................................. 112 4.2. CHỮ KÝ SỐ .............................................................................................. 112 4.3. KIỂM TRA TÍNH TOÀN VẸN CỦA THÔNG ĐIỆP .............................. 122 4.4. BẢO VỆ MẬT KHẨU .............................................................................. 125 4.5. KẾT LUẬN CHƯƠNG IV ........................................................................ 128 KẾT LUẬN VÀ KIẾN NGHỊ.............................................................................. 130 1. KẾT LUẬN ................................................................................................... 130 2. KIẾN NGHỊ HƯỚNG PHÁT TRIỂN .......................................................... 130 DANH MỤC CÁC CÔNG TRÌNH CÔNG BỐ CỦA TÁC GIẢ ........................ 132 TÀI LIỆU THAM KHẢO .................................................................................... 134 PHỤ LỤC A ......................................................................................................... 140 PHỤ LỤC B ......................................................................................................... 179
vi DANH MỤC CÁC KÝ HIỆU, CÁC TỪ VIẾT TẮT Ký hiệu Tiếng Anh Tiếng Việt CAST Carlisle Adams and Stafford Tavares Hệ mật CAST CBC Cipher Block Chaining Chế độ liên kết khối mã CFB Cipher Feedback Block Chế độ phản hồi mã CGP Cyclic Geometic Progressions Cấp số nhân cyclic CMG Cyclic Multiplicate Group Nhóm nhân cyclic CRC Cyclic Redundancy Check Kiểm tra độ dư tuần hoàn CRF Collision Resistant Function Hàm kháng va chạm CRHF Collision Resistant Hash Function Hàm băm kháng va chạm d0 Hamming distance Khoảng cách Hamming deg Degree Bậc của đa thức DEA Data Encryption Algorithm Thuật toán mã dữ liệu DES Data Encryption Standard Chuẩn mã dữ liệu e( x ) Equity Đa thức lũy đẳng ECB Electronic Codebook Chế độ quyển mã điện tử Field Trường G Group Nhóm GF(p) Group Field Trường đặc số p h Hash Hàm băm I Ideal Trường hợp lý tưởng IDEA International Data Encryption Thuật toán mã hóa dữ liệu Algorithm quốc tế IV Initial Value Giá trị khởi tạo MAC Message Authentication Code Mã xác thực thông báo MDC Manipulation Detection Code Mã phát hiện sự sửa đổi NIST National Institute for Standards and Viện Quốc gia về Tiêu Technology (US) chuẩn và Công nghệ OFB Output Feedback Chế độ phản hồi đầu ra ord Order Cấp của đa thức
vii OWF One-Way Function Hàm một chiều OWHF One-Way Hash Function Hàm băm một chiều R Ring Vành RIPE Race Integrity Primitives Evaluation Đánh giá mức độ toàn vẹn nguyên gốc. RSA Rivest Shamir Adleman Thuật toán mã hóa RSA SHA Secure Hash Algorithm Thuật toán băm SHA SHS Secure Hash Standard Tiêu chuẩn băm an toàn TDEA Triple Data Encryption Algorithm Thuật toán mã hóa TDEA UOWHF Universal One-Way Hash Function Hàm băm một chiều phổ thông VEST Very Efficient Substitution Chuyển vị thay thế hiệu Transposition quả cao W Weight Trọng số
viii DANH MỤC CÁC BẢNG Bảng 2.1. Khoảng cách Hamming dH(C1,Ci) giữa các cặp bản mã ...........................49 Bảng 2.2. Khoảng cách Hamming dH(C1,Ci) của hàm băm khi thay đổi ..................52 Bảng 2.3. Khoảng cách Hamming dH(MD1,MDi) giữa các cặp giá trị băm ............53 Bảng 2.4. Giá trị hàm mũ và Logarit rời rạc cơ số 2 của các phân tử ......................57 Bảng 2.5. Hoán vị ban đầu (IP) .................................................................................59 Bảng 2.6. Hoán vị đảo (IP-1) .....................................................................................61 Bảng 2.7. Khoảng cách Hamming của một vài cặp bản mã khi thay đổi .................64 Bảng 2.8. Khoảng cách Hamming của một vài cặp bản mã khi thay đổi .................65 Bảng 2.9. Khoảng cách Hamming dH(MD1, MDi) khi các khối dữ liệu khác khối ..69 Bảng 2.10. Khoảng cách Hamming dH(MD1, MDi) giữa các cặp giá trị băm .........72 Bảng 3.1. Bảng hoán vị ban đầu (IP) ........................................................................79 Bảng 3.2. Bảng hoán vị đảo (IP-1) .............................................................................80 Bảng 3.3. Khoảng cách Hamming dH(MD0, MDi) khi các bản tin dữ liệu ..............82 Bảng 3.4. Khoảng cách Hamming dH(MD0, MDi) của 8 mã băm ...........................84 Bảng 3.5. Trọng số của các khóa tại các bước băm ..................................................85 Bảng 3.6. Khoảng cách Hamming dH(C0,CI) giữa các cặp bản mã ...........................91 Bảng 3.7. Khoảng cách Hamming dH(C0,CI) giữa các cặp bản mã ...........................92 Bảng 3.8. Khoảng cách Hamming dH(C0,CI) của các mã băm ..................................95 Bảng 3.9. Khoảng cách Hamming dH(C0,CI) của các mã băm ..................................96 Bảng 3.10. Độ khuếch tán giữa các cặp bản mã của một vài bước tính toán .........103 Bảng 3.11. Kết quả của 10 lần tính độ khuếch tán khi thay đổi bản rõ ..................104
ix Bảng 3.12. Độ khuếch tán giữa các cặp bản mã của một vài bước ........................106 Bảng 3.13. Độ khuếch tán của một vài mã băm khi thay đổi dữ liệu .....................108 Bảng 3.14. Kết quả 10 lần tính khuếch tán của hàm băm .......................................109
x DANH MỤC CÁC HÌNH VẼ Hình 1.1. Lưu đồ Feistel ...........................................................................................12 Hình 1.2. Lưu đồ hoạt động của chương trình ..........................................................13 Hình 1.3. Lưu đồ Lai-Massey ...................................................................................14 Hình 1.4. Lưu đồ mã hóa ..........................................................................................16 Hình 1.5. Hàm f của DES..........................................................................................17 Hình 1.6. Tính bảng khóa DES .................................................................................21 Hình 1.7. Phân loại các hàm băm ..............................................................................32 Hình 1.8. Sơ đồ MAC ...............................................................................................33 Hình 1.9. Các sơ đồ hàm băm độ dài đơn .................................................................34 Hình 1.10. Thuật toán MDC-2 ..................................................................................35 Hình 1.11. Thuật toán MDC-4 ..................................................................................36 Hình 1.12. Toàn vẹn dữ liệu dùng MAC ..................................................................37 Hình 1.13. Toàn vẹn dữ liệu dùng MDC và mã hóa .................................................37 Hình 1.14. Toàn vẹn dữ liệu dùng MDC và kênh tin cậy .........................................37 Hình 2.1. Sơ đồ khối bộ mã hóa ................................................................................45 Hình 2.2. Mạch điện mã hóa f với a( x)  1 x  x2 ................................................47 Hình 2.3. Sơ đồ hàm băm Matyas-Mayer–Oseas ....................................................51 Hình 2.4. Sơ đồ khối của hệ mật ...............................................................................60 Hình 2.5. Sơ đồ mã hóa của hệ mật ..........................................................................60 Hình 2.6. Tách các khóa con cho các vòng mã hóa ..................................................62 Hình 2.7. Sơ đồ bộ mã hóa ........................................................................................67
xi Hình 3.1. Sơ đồ hàm băm MDC-3 đề xuất ...............................................................77 Hình 3.2. Sơ đồ khối mật mã E .................................................................................78 Hình 3.3. Sơ đồ khối mã hóa f với khóa K1 1 x4 x5 ..........................................81 Hình 3.4. Sơ đồ mã hóa của hệ mật ..........................................................................88 Hình 3.5. Mạch mã hóa f với a(x) 1 x  x7  x35  x60 ..........................................90 Hình 3.6. Sơ đồ hàm băm MDC-4 (512 bit) .............................................................93 Hình 3.7. Sơ đồ khối của hệ mật ...............................................................................98 Hình 3.8. Sơ đồ mã hóa của hệ mật ..........................................................................99 Hình 3.9. Mạch mã hóa hàm f .................................................................................101 Hình 3.10. Mạch mã hóa với mi 1 x3  x63 ..........................................................102 Hình 3.11. Sơ đồ hàm băm không khóa 512 bít......................................................107 Hình 4.1. Tạo một thông báo có ký bằng chữ ký số ...............................................113 Hình 4.2. Các bước kiểm tra một thông báo đã ký .................................................114 Hình 4.3. Sơ đồ chữ ký số RSA không bí mật bản tin ............................................114 Hình 4.4. Sơ đồ chữ ký số RSA có bí mật bản tin ..................................................115 Hình 4.5. Thủ tục chữ ký kép ..................................................................................118 Hình 4.6. Thủ tục cửa hàng kiểm tra chữ ký ...........................................................119 Hình 4.7. Thủ tục ngân hàng kiểm tra chữ ký .........................................................119 Hình 4.8. Lược đồ tạo chữ ký kép với hàm băm mở rộng mới...............................121 Hình 4.9. Ứng dụng gắn nhãn mã băm của hàm băm mở rộng mới .......................124 Hình 4.10. Dùng hàm băm mở rộng mới để lưu trữ và kiểm tra mật khẩu .............128
1 PHẦN MỞ ĐẦU 1. MỞ ĐẦU Để đảm bảo tính toàn vẹn của thông tin, cần phải phải sử dụng khóa hợp lý. Khi tăng độ dài khóa, sự tính toán tăng lên nhiều lần theo sự tăng lên của độ dài khoá [4]. Một khoá 32 bit đòi hỏi 232 bước thử. Điều này có thể được thực hiện tại một máy tính cá nhân. Một khoá 40 bit đòi hỏi một máy tính cá nhân thử trong vòng khoảng một tuần lễ. Một hệ thống mã hoá 56 bit đòi hỏi nhiều máy tính cá nhân hợp tác trong vòng vài tháng nhưng có thể dễ dàng phá bởi một thiết bị phần cứng đặc biệt. Giá của phần cứng này có thể chấp nhận được đối với một tổ chức tội phạm, một công ty hàng đầu hay một chính phủ. Khoá 64 bit hiện nay có thể được phá bởi một chính phủ, khoá 128 bit được coi là an toàn trong những năm gần đây. Nhiều mã có thể bị phá không bằng cách thử mọi khả năng. Nói chung, rất khó để thiết kế một thuật toán mã hoá mà không thể bị bẻ khóa. Rất khó để giữ bí mật cho một thuật toán mã hoá bởi một người nào đó quan tâm có thể thuê một chuyên gia bẻ khoá để dịch lại và khám phá ra phương pháp mã hoá của chúng ta. Thuật toán mã hoá và chính sách sử dụng là những điểm quan tâm nhất trong việc phá vỡ một hệ thống [4, 5]. Việc bảo mật, xác thực, đảm bảo tính toàn vẹn của dữ liệu hiện nay sử dụng hàm băm kết hợp với mã hoá khoá công khai đang được đánh giá là hết sức hiệu quả. Ví dụ, việc ứng dụng trong chữ ký số: Người gửi sẽ tạo một đoạn mã bǎm, mã hoá đoạn mã bǎm bằng khoá riêng của mình và người nhận sẽ dùng khoá công khai của người gửi để giải đoạn mã bǎm của người gửi, sau đó so sánh với đoạn mã bǎm của thông điệp nhận được (được tạo bằng cùng một thuật toán). Nếu trùng nhau thì người nhận có thể tin rằng thông điệp nhận được không bị thay đổi trong quá trình truyền tải trên mạng và xuất phát từ người gửi xác định. Các hàm băm hiện nay cũng đang được ứng dụng nhiều vào thực tế, nhất là trong việc xác thực bản tin và lĩnh vực chữ ký số. Việc nghiên cứu xây dựng các hàm
2 băm mở rộng mới và đưa ra ý tưởng về khả năng ứng dụng sẽ góp phần tăng được tính bảo mật, tính xác thực, đảm bảo tính toàn vẹn, an toàn cho thông tin dữ liệu. 2. TÌNH HÌNH NGHIÊN CỨU Sau chiến tranh thế giới lần thứ hai, về lĩnh vực điện tử có ba lý thuyết lớn ra đời và đã cùng ảnh hưởng rất mạnh mẽ đến sự phát triển khoa học và công nghệ. Đó là lý thuyết hệ thống (System Theory), lý thuyết điều khiển (Control Theory), lý thuyết thông tin và mã hóa (mà sau được phát triển mạnh hướng mật mã). Ba lý thuyết này cùng với lý thuyết dây và giải tích hàm được coi là năm trong số những lý thuyết lớn của thế kỷ XX. Lúc đầu lý thuyết thông tin và mã hóa được phát triển chủ yếu để phục vụ cho kỹ thuật truyền tin nhưng sau đó với sự phát triển của các kỹ thuật tính toán và kỹ thuật thám mã mà lý thuyết này phát triển thêm về mật mã học cho mọi lĩnh vực. Năm 1949, Claude Shannon đã công bố một bài báo có nhan đề "Lý thuyết thông tin trong các hệ mật" trên tạp chí "The Bell System Technical Journal". Bài báo đã có ảnh hưởng lớn đến việc nghiên cứu khoa học mật mã Mật mã học được phát triển không ngừng để bảo vệ tính xác thực (authentication), tính tin cậy (confidentability), tính toàn vẹn (integrity), cho phép (authorization), công nhận (nonrepudiation), quản trị (administration) và theo dõi kiểm toán (accounting). Các hàm băm cũng đang được phát triển để tăng tính toàn vẹn cho dữ liệu. Các hàm băm mật mã sản sinh ra các mã băm thông điệp. Nó có thể dễ dàng tính toán nhưng nó lại rất khó để đảo ngược (dạng hàm một chiều), cho dù các thuộc tính khác thông thường cũng là cần thiết. Trên thế giới hiện nay, hàm băm có nhiều loại, có những hàm băm đơn giản, có những hàm băm phức tạp, có hàm băm độ dài đơn, có hàm băm dộ dài kép, có những hàm băm chuyên dụng, thương mại. Một cách tổng quan, có những sơ đồ hàm băm phổ biến sau đây: * Hàm băm có độ dài đơn: [3, 4, 6]
3 + Sơ đồ Matyas - Mayer - Oseas (M-M-O). + Sơ đồ Davies - Mayer (D-M). + Sơ đồ Miyaguchi - Preneel (M-P). * Hàm băm có độ dài kép: [3, 4, 5, 7] + MDC-2 + MDC-4 Các sơ đồ hàm băm trên được xây dựng từ nhiều hệ mật khác nhau, trong đó hệ mật mã khóa bí mật được sử dụng nhiều, tiêu biểu là các hệ mật sau: DES, IDEA, RD.5, TDEA, AES, CAST,… Những nghiên cứu về các hệ mật này và phương pháp sử dụng chúng cho lược đồ hàm băm đã xuất hiện trong nhiều công trình từ rất nhiều năm qua [4, 6, 17]. Các hàm băm thông dụng trên thế giới hiện nay là hàm băm họ MD và họ SHS. Trong họ MD, hàm băm thường dùng hiện nay là MD5 - là một thuật toán băm mật mã sử dụng phổ biến được thiết kế bởi giáo sư Ronald L. Rivest tại trường MIT vào năm 1991 để thay thế cho hàm băm trước đó là MD4 (1990). Là một chuẩn Internet (RFC 1321), MD5 đã được dùng trong nhiều ứng dụng bảo mật và cũng được dùng phổ biến để kiểm tra tính toàn vẹn của tập tin. Cũng như các hàm khác như MD4 và SHS (Secure Hash Standard), MD5 là phương pháp có ưu điểm tốc độ xử lý nhanh, thích hợp với các thông báo dài và cho giá trị băm 128 bit. SHS là chuẩn gồm các thuật toán băm mật mã an toàn như SHA-1, SHA-224, SHA-256, SHA-512 do NIST và NSA xây dựng [4, 5, 12]. Trước năm 2005, SHA-1 được coi là bất khả xâm phạm đối với bất kỳ tấn công nào. Nhưng vào tháng 2/2005, tại hội nghị của CRYPTO, nhóm chuyên gia Trung Quốc đã trình bày một tấn công lên SHA-1 với đầy đủ số vòng lặp 80 [12]. Họ đã công bố một cặp xung đột của SHA-1 với thời gian tìm là 1 giờ 5 phút. Quan trọng hơn là các chuyên gia Trung Quốc đã chọn được chiến lược và phương pháp để vượt qua những chướng ngại lớn nhất trong việc tìm các xung đột trong SHA-1. Vào tháng
4 8/2005, tại một hội nghị khác của CRYPTO họ đã trình bày phương án tấn công cải tiến vào SHA-1 chỉ với 263 phép toán. Kết quả nghiên cứu của các chuyên gia người Trung Quốc đã được các nhà mật mã trên thế giới đặc biệt quan tâm và coi đây là sự kiện có ý nghĩa bước ngoặt trong nghiên cứu hàm băm. Một số trung tâm mật mã đã kiểm tra lại và xác nhận kết luận của các nhà mật mã Trung Quốc. Một số khác trực tiếp tham gia tìm kiếm các phương án cải tiến. Tại ASIACRYPT 2006, người ta đã tìm ra phương án tấn công SHA-1 64 vòng chỉ với 235 phép toán [12] Sau sự kiện trên, mặc dù chưa phát hiện một tấn công thực tế nào lên SHA-1 nhưng NIST vẫn khuyến cáo chuyển sang sử dụng họ hàm băm an toàn hơn là SHA- 2 (bao gồm SHA-224, SHA-256, SHA-384, SHA-512) và đã dự kiến không sử dụng SHA-1 trong chữ ký số [12]. Tuy nhiên, nhiều chuyên gia cho rằng do SHA-2 có nhiều nét giống SHA -1 nên cũng không thể có triển vọng lâu dài, đã đến lúc cần xem xét lại họ hàm băm này một cách toàn diện. Bởi vậy trong hai năm 2005 - 2006, Viện NIST đã tổ chức nhiều cuộc hội thảo về hàm băm [12]. Kết quả các cuộc hội thảo cho thấy sự cần thiết phải tổ chức các cuộc thi chọn hàm băm mới tương tự như đã làm với tiêu chuẩn mã dữ liệu mới thay thế thuật toán DES những năm trước. Tuy nhiên, nếu như trong cuộc thi chọn tiêu chuẩn mã dữ liệu mới (với kết quả là thuật toán AES), các nhà tổ chức đã có được hệ thống tiêu chí để lựa chọn các ứng cử viên cho thuật toán mới thì đối với hàm băm lại không như vậy. Có thể nói, trong số các cơ sở nguyên thủy của mật mã thì hàm băm còn được hiểu ít nhất, do đó cần phải có nhiều hàm băm được xây dựng để lựa chọn và ứng dụng vào thực tế đáp ứng yêu cầu công việc đặt ra. Việc phá mã bảo mật như SHA thường đòi hỏi một sức mạnh tính toán rất lớn. Các nhà nghiên cứu Trung Quốc khi crack SHA-1 đã không có nhiều siêu máy tính trong tay, và thay vào đó, họ sử dụng một chương trình điện toán phân tán giống như dự án SETI@Home (setiathome.ssl.berkeley.edu) để khai thác sức mạnh nhàn rỗi của hàng nghìn máy tính trên thế giới và hoàn tất công việc. “Trường hợp đột nhập đáng chú ý nhất từ trước đến nay vào các hệ thống mã hóa là vụ xuyên thủng chuẩn MD5- RC64 nhờ sức mạnh của 300.000 máy tính và phải mất 5 năm”, Callas cho biết. “Phá
5 SHA-1, khó hơn gấp 16 lần, cũng cần 300.000 máy tính nhưng phải mất xấp xỉ 74 năm”. Tuy nhiên, với việc tận dụng được sức mạnh liên kết của nhiều máy tính gia đình như các nhà khoa học Trung Quốc đã làm nói trên, thời gian thực hiện điều này đã được rút ngắn rất nhiều. Một công trình nghiên cứu tiêu biểu gần đây về hàm băm có giá trị là bài báo “A new Design Criteria for Hash-Function” của nhóm tác giả Jean-Sesbastien, Yevgenity Dodis, Cescile Malinaud và Prashant ở các trường Đại học New-York (Mỹ) và Luxembourg [12]. Bài báo này đánh giá các tính chất của các hàm băm thương mại gần đây và chỉ ra rằng các hàm băm thông dụng như SHA-1 và MD5 không còn đáp ứng được các yêu cầu hiện nay về tính bảo mật, tính va chạm và độ khuếch tán cần thiết. Bài báo nêu ra hướng nghiên cứu cần phải có nhiều các hàm băm có độ dài mã băm lớn như SHA-512 thì mới có thể sử dụng được cho nhiều mục đích ứng dụng trong tình hình hiện nay, nhất là khi cấu hình của hệ thống máy tính hiện tại ngày một cao hơn và tốc độ xử lý của chúng ngày một nhanh hơn. Một công trình nghiên cứu khác “Properties of Cryptographic Hash Functions” của tác giả Michal RjaˇSko cũng đã có nêu các thuộc tính cơ bản của hàm băm và ứng dụng, nhưng mới chỉ tập trung vào tính một chiều, tính khó tìm nghịch ảnh, tính kháng va chạm của hàm băm chứ chưa đề cập đến tính khuếch tán của các hàm băm [37]. Cùng với sự phát triển của các hàm băm trên thế giới, trong nước các hàm băm cũng đang nhận được nhiều sự quan tâm. Nhiều cơ sở nghiên cứu, đào tạo trong nước đang tập trung vào hàm băm, một số công trình nghiên cứu về hàm băm đã được công bố, trong đó tiêu biểu tại các đơn vị như Học viện Kỹ thuật Quân sự, Đại học Mật mã, Học viện Công nghệ Bưu chính Viễn thông, Đại học Bách Khoa, Đại học Khoa học Tự nhiên [6, 7], ... Ở nước ta hiện nay, việc nghiên cứu các hệ mật được thực hiện từ nhiều năm qua [19, 20, 21], và cũng đã có một số công trình nghiên cứu về hệ mật có giá trị [13, 14, 15, 16]. Tuy nhiên, sau các nghiên cứu về hệ mật thì việc sử dụng các hệ mật này cho các lược đồ xây dựng hàm băm còn là vấn đề tương đối mới.
6 Các sơ đồ hàm băm thường sử dụng mật mã khối với hàm mật mã được xây dựng theo nhiều cách khác nhau. Trong những năm gần đây, một hướng nghiên cứu về cấu trúc các cấp số nhân cyclic trên vành đa thức áp dụng vào xây dựng các bộ mã hóa, vào các sơ đồ hàm băm hứa hẹn nhiều kết quả khả quan [6, 7, 48]. Một số vành đa thức đặc biệt thường không sử dụng trong mã sửa sai lại có thể áp dụng vào thực hiện hàm mã hóa trong các mật mã khối. Các công trình nghiên cứu về hàm băm còn chưa nhiều, một số đồ án tốt nghiệp đại học, luận văn tốt nghiệp thạc sỹ có nghiên cứu, giới thiệu về hàm băm nhưng hầu hết là những tìm hiểu mang tính chất lý thuyết tổng quan. Một số bài báo và luận án tiến sĩ có đề cập đến hàm băm như bài báo “Xây dựng hàm băm trên các cấp số nhân cyclic” [7] và luận án Tiến sĩ của tác giả Hồ Quang Bửu “Về một phương pháp xây dựng hàm băm cho việc xác thực trên cơ sở ứng dụng thuật toán mã hóa đối xứng” [6]. Bài báo này đưa ra một phương pháp xây dựng hàm băm dựa trên hệ mật được xây dựng từ các cấp số nhân cyclic nhưng hàm băm được xây dựng có độ dài mã băm còn nhỏ, chưa đủ dài để có thể đảm bảo an toàn cho thông tin dữ liệu. Luận án của Tiến sĩ Hồ Quang Bửu đã đề xuất phương pháp xây dựng hệ mật trên các cấp số nhân cyclic của vành đa thức. Hệ mật mới này được xây dựng theo lược đồ Feistel có sửa đổi với sơ đồ mật mã khối có độ dài đầu ra 128 bit. Trên cơ sở hệ mật này, tác giả đã áp dụng vào sơ đồ xây dựng một hàm băm mới có độ dài 128 bit với khối mật mã được xây dựng trên các cấp số nhân cyclic. Tuy nhiên cũng giống như bài báo trên, hàm băm được xây dựng ở đây mới chỉ có độ dài 128 bit, xây dựng trên sơ đồ hàm băm đơn nên dễ dàng bị bẻ gãy. Thực tiễn đặt ra cần các hàm băm mở rộng có độ dài mã băm lớn hơn các hàm băm truyền thống để bảo mật thông tin và đảm bảo tính toàn vẹn của dữ liệu. Luận án của Tiến sĩ Hoàng Văn Quân (Viện Khoa học và Công nghệ Quân sự) mới bảo vệ cũng chưa đề cập đến các hàm băm mở rộng và tính chất khuếch tán của các hàm băm. Theo lý thuyết, các hàm băm có độ dài lớn và có tính khuếch tán tốt sẽ phần nào đáp ứng được yêu cầu hiện nay. Trước đây các hàm băm có độ dài 128-256 bít được
7 cho là đủ lớn để sử dụng nhưng với sự phát triển bùng nổ của ngành công nghệ thông tin trong những năm gần đây mà thực tế đòi hỏi cần có những hàm băm có độ dài lớn hơn, có độ dài mã băm khoảng 384-512 bít thì mới đảm bảo an toàn. 3. LÝ DO CHỌN ĐỀ TÀI Thông tin được truyền trên mạng ngày càng chịu nhiều tác động, các thám mã có mặt ở khắp nơi, luôn rình rập để lấy cắp thông tin hoặc làm thay đổi thông tin một cách có chủ đích. Để bảo vệ bản tin, người ta cần tăng cường bảo vệ tính bí mật và bảo vệ tính toàn vẹn dữ liệu của bản tin. Bên cạnh đó nhiều thông tin cũng cần phải có tính xác thực. Và cùng với sự phát triển của các kỹ thuật mật mã thì hàm băm cũng ra đời. Hàm băm tạo ra các mã băm được sử dụng cho nhiều mục đích. Các ứng dụng điển hình của hàm băm mật mã bao gồm: Xác thực, đảm bảo tính toàn vẹn của dữ liệu, tạo chữ ký số, bảo vệ bản quyền tài liệu số, nhận dạng mật khẩu, nhận dạng đối tượng, ... Những năm gần đây, các công trình nghiên cứu về việc sử dụng cấu trúc nhóm nhân cyclic và cấp số nhân cyclic trên vành đa thức vào bài toán xây dựng các bộ mã ở nước ta đã mang lại những kết quả khả quan [2, 8, 10]. Có được điều này, chúng ta đều biết, cấu trúc nhóm nhân cyclic và cấp số nhân cyclic trên vành đa thức là loại có cấu trúc đại số chặt chẽ, số lượng sinh ra nhiều do đó có thể chọn được nhiều khóa, đồng thời mạch điện phần cứng cần thực hiện để tạo ra các ứng dụng thực tế sẽ khá đơn giản [11, 22, 23]. Chúng ta đã biết hàm băm có 2 tính chất cơ bản là tính chất nén và tính dễ dàng tính toán, ngoài ra hàm băm còn có 3 tính chất khác bổ sung là tính khó tìm nghịch ảnh, khó tìm nghịch ảnh thứ hai và kháng va chạm. Trong số các tính chất đó thì hai tính chất dễ dàng tính toán và khó tìm nghịch ảnh rất gần với đặc điểm của phép biến đổi mật mã, nhất là đối với mật mã khối khoá bí mật (mật mã khoá công khai thường phức tạp và khó tính toán hơn), cho nên việc dùng các thuật toán mật mã khối khoá bí mật vào việc tạo ra các hàm băm là một hướng đi rất hiệu quả.