Tài liệu Nghiên cứu mở rộng phương pháp mã hóa số học ứng dụng trong bảo mật dữ liệu

ĐẠI HỌC QUỐC GIA HÀ NỘI TRƯỜNG ĐẠI HỌC CÔNG NGHỆ NGUYỄN THANH BÌNH NGHIÊN CỨU MỞ RỘNG PHƯƠNG PHÁP MÃ HÓA SỐ HỌC ỨNG DỤNG TRONG BẢO MẬT DỮ LIỆU Ngành: Công nghệ thông tin Chuyên ngành: Hệ thống thông tin Mã số: 60 48 05 LUẬN VĂN THẠC SĨ NGƢỜI HƢỚNG DẪN KHOA HỌC: TS. LÊ HỒNG LAN Hà Nội – 2010 2 MỤC LỤC LỜI CẢM ƠN ..............................................................................Error! Bookmark not defined. LỜI CAM ĐOAN ........................................................................Error! Bookmark not defined. MỤC LỤC .................................................................................................................................. 2 DANH MỤC CÁC KÝ HIỆU, CÁC CHỮ VIẾT TẮT ................................................................ 4 DANH MỤC CÁC BẢNG .......................................................................................................... 5 DANH MỤC CÁC HÌNH VẼ ..................................................................................................... 5 Chƣơng 1. GIỚI THIỆU CHUNG VỀ MÃ HÓA THÔNG TIN .................................................. 8 1.1. Một số thuật ngữ và khái niệm.......................................................................................... 8 1.1.1. Một số thuật ngữ ........................................................................................................ 8 1.1.2. Vì sao cần mã hóa.................................................................................................... 10 1.2. Vài nét về lịch sử ............................................................................................................ 10 1.3. Khái niệm hệ mã hóa ...................................................................................................... 14 1.4. Phân loại hệ mã hóa........................................................................................................ 15 1.4.1. Hệ mã hóa khóa đối xứng ........................................................................................ 15 1.4.1.1. Đặc điểm của hệ mã hóa khóa đối xứng ............................................................ 16 1.4.1.2. Nơi sử dụng hệ mã hóa khóa đối xứng .............................................................. 16 1.4.2. Hệ mã hóa khóa công khai ....................................................................................... 16 1.4.2.1. Đặc điểm của Hệ mã hóa khóa công khai .......................................................... 17 1.4.2.2. Nơi sử dụng Hệ mã hóa khóa đối xứng ............................................................. 17 1.5. Một số hệ mã hóa khóa đối xứng và mã hóa khóa công khai ........................................... 18 1.5.1. Hệ mã hóa đối xứng cổ điển .................................................................................... 18 1.5.1.1. Hệ mã hóa dịch chuyển ..................................................................................... 19 1.5.1.2. Hệ mã hóa thay thế (Hoán vị toàn cục) .............................................................. 19 1.5.1.3. Hệ mã Affine .................................................................................................... 20 1.5.2. Hệ mã hóa khóa công khai ....................................................................................... 21 1.5.2.1. Sơ đồ chung hệ mã hóa khóa công khai ............................................................. 21 1.5.2.2. Hệ mã hóa RSA (Rivest - Shamir - Adleman) ................................................... 21 1.6. Các bài toán về an toàn thông tin .................................................................................... 22 1.7. Thám mã và tính an toàn của các hệ mật mã ................................................................... 23 1.7.1. Vấn đề thám mã ....................................................................................................... 23 1.7.2. Tính an toàn của một hệ mật mã .............................................................................. 24 Chƣơng 2. CƠ SỞ TOÁN HỌC CỦA PHƢƠNG PHÁP MÃ HÓA SỐ HỌC ............................ 26 2.1. Phép chiếu một điểm lên đoạn thẳng............................................................................... 26 2.1.1. Phép chiếu thu nhỏ đồng dạng ................................................................................. 26 2.1.2. Phép biến đổi ngƣợc ................................................................................................ 26 2.2. Phép chiếu một đoạn thẳng lên một đoạn thẳng .............................................................. 27 2.2.1. Phép chiếu thu nhỏ đồng dạng ................................................................................. 27 2.2.1. Phép biến đổi ngƣợc ................................................................................................ 27 2.2.3. Định lý 1 ................................................................................................................. 27 2.3. Một số tính chất của phép chiếu ...................................................................................... 29 2.3.1. Tính chất kết hợp ..................................................................................................... 29 2.3.2. Tính chất chứa trong ................................................................................................ 30 2.3.3. Tính chất chứa trong của phép chiếu ngƣợc ............................................................. 30 Chƣơng 3. CẢI TIẾN PHƢƠNG PHÁP MÃ HÓA SỐ HỌC .................................................... 31 3.1. Giới thiệu phƣơng pháp mã hóa số học ........................................................................... 31 3.2. Thuật toán mã hóa số học truyền thống........................................................................... 32 3.2.1. Thuật toán mã hóa ................................................................................................... 32 3.2.1.1. Thống kê tần suất và xác định miền phân bố của các ký tự trong bản rõ ............ 32 3 3.2.1.2. Ý tƣởng của thuật toán mã hóa ......................................................................... 33 3.2.1.3. Thuật toán mã hóa............................................................................................ 33 3.2.2. Thuật toán giải mã .................................................................................................. 34 3.2.2.1. Hàm g(x) trên [0,D) ......................................................................................... 34 3.2.2.2. Ý tƣởng của thuật toán giải mã ......................................................................... 34 3.2.2.3. Thuật toán giải mã ........................................................................................... 35 3.2.2.4. Chứng minh tính đúng đắn của thuật toán ........................................................ 35 3.2.2.5. Nhận xét về thuật toán giải mã ......................................................................... 36 3.2.3. Ví dụ ...................................................................................................................... 37 3.3. Thuật toán mã hóa số học cải tiến ................................................................................... 39 3.3.1. Thuật toán mã hóa cải tiến ...................................................................................... 39 3.3.2. Thuật toán giải mã cải tiến ...................................................................................... 41 3.4. So sánh độ phức tạp........................................................................................................ 42 3.4.1. Thuật toán mã hóa số học truyền thống ................................................................... 42 3.4.1.1. Thuật toán mã hóa............................................................................................ 42 3.4.1.2. Thuật toán giải mã ........................................................................................... 42 3.4.2. Thuật toán mã hóa số học cải tiến ........................................................................... 42 3.4.2.1. Thuật toán mã hóa............................................................................................ 42 3.4.2.2. Thuật toán giải mã ........................................................................................... 42 3.4.3. So sánh độ phức tạp của 2 phƣơng pháp.................................................................. 42 3.6. Một thuật toán cải tiến khác ............................................................................................ 43 3.6.1. Xác định miền phân bố ........................................................................................... 43 3.6.2. Thuật toán mã hóa cải tiến ...................................................................................... 44 3.6.3. Thuật toán giải mã cải tiến ...................................................................................... 45 3.7. Nghiên cứu tính bảo mật của phƣơng pháp mã hóa số học .............................................. 45 Chƣơng 4. CÀI ĐẶT VÀ THỬ NGHIỆM................................................................................. 53 4.1. Giới thiệu thƣ viện xử lý số nguyên lớn .......................................................................... 53 4.1.1. Cấu trúc của các lớp................................................................................................. 53 4.1.2. Bảng luỹ thừa 2 (bảng h) ......................................................................................... 54 4.2. Thuật toán chuyển đổi .................................................................................................... 55 4.2.1. Thuật toán từ hệ thập phân sang hệ nhị phân ............................................................ 55 4.2.2. Thuật toán từ hệ nhị phân sang hệ thập phân ............................................................ 56 4.3. Thuât toán chia (div, mod) .............................................................................................. 56 4.4. Thuật toán phân rã nhị phân tính luỹ thừa mod ............................................................... 57 4.5. Phƣơng pháp tính logarit ................................................................................................ 59 4.6. Phƣơng pháp tính căn bậc hai ......................................................................................... 60 4.7. Kết quả thử nghiệm ........................................................................................................ 61 KẾT LUẬN .............................................................................................................................. 63 TÀI LIỆU THAM KHẢO ......................................................................................................... 64 4 DANH MỤC CÁC KÝ HIỆU, CÁC CHỮ VIẾT TẮT STT 1 2 3 4 5 6 Ký hiệu / Viết tắt DES PKC RAC RSA SKC UCLN Diễn giải Data Encryption Standard Public Key Cryptosystem Randomized Arithmetic Coding Rivest - Shamir – Adleman Secret Key Ctyptosystem Ƣớc chung lớn nhất 5 DANH MỤC CÁC BẢNG Bảng 3.1 Bảng tần suất của các ký tự ....................................................................................... 32 Bảng 3.2 Bảng phân bố với D = 1000 và dựa theo tần suất ....................................................... 32 Bảng 3.3 Miền phân bố của các ký tự với bản rõ CABAB ........................................................ 38 Bảng 3.4 Miền phân bố của các ký tự với bản rõ BAABB ........................................................ 46 Bảng 3.5 Miền phân bố với bản rõ CABAB ............................................................................. 49 Bảng 4.1 Dùng để lƣu trữ giá trị thập phân của 2i ...................................................................... 54 Bảng 4.2. Kết quả thử nghiệm ................................................................................................... 62 DANH MỤC CÁC HÌNH VẼ Hình 1.1 Mô tả phép mã chuyển vị ........................................................................................... 11 Hình 1.2 Bảng đĩa chữ cái ........................................................................................................ 11 Hình 1.3 Minh họa mã khối...................................................................................................... 12 Hình 1.4 Hệ mã tích hợp .......................................................................................................... 13 Hình 1.5 Ví dụ hệ mã tích hợp ................................................................................................. 13 Hình 2.1 Phép chiếu 1 điểm lên 1 đoạn thẳng ........................................................................... 26 Hình 2.2 Phép chiếu 1 đoạn thẳng lên 1 đoạn thẳng.................................................................. 27 Hình 2.3 Chiếu B1B2 lên A1A2 ................................................................................................. 28 Hình 2.4 Chiếu C1C2 lên X1X2 ................................................................................................. 28 Hình 2.5 Chiếu Z1 Z2 lên A1A2 .................................................................................................. 28 Hình 3.1 Minh họa cách phân tách miền phân bố ...................................................................... 47 Hình 3.2 Sơ đồ khối hệ thống kết hợp hoán vị và mã hóa số học phân tách khoảng .................. 47 6 MỞ ĐẦU Mã hóa là một trong các phƣơng pháp cơ bản của việc đảm bảo an toàn dữ liệu. Thời kỳ sơ khai, con ngƣời đã sử dụng nhiều phƣơng pháp để bảo vệ các thông tin bí mật, nhƣng tất cả các phƣơng pháp đó chỉ mang tính nghệ thuật hơn là khoa học. Ban đầu, mã hóa đƣợc sử dụng phổ biến cho quân đội, qua nhiều cuộc chiến tranh, vai trò của mã hóa ngày càng quan trọng và mang lại nhiều thành quả không nhỏ nhƣ các hệ mã cổ điển Caesar, Playfair…chúng đều là nền tảng cho mật mã học ngày nay. Khi toán học đƣợc áp dụng cho mã hóa thì lịch sử của mã hóa đã sang trang mới. Việc ra đời các hệ mã hóa đối xứng không làm mất đi vai trò của các hệ mã cổ điển mà còn bổ sung cho ngành mật mã nhiều phƣơng pháp mã hóa mới. Từ năm 1976, khi hệ mã phi đối xứng ra đời, nhiều khái niệm mới gắn với mật mã học xuất hiện: chữ ký số, hàm băm, mã đại diện, chứng chỉ số...vv. Mật mã học không chỉ áp dụng cho quân sự mà còn cho các lĩnh vực kinh tế xã hội khác. Hiện nay có nhiều phƣơng pháp mã hóa, mỗi phƣơng pháp có ƣu, nhƣợc điểm riêng. Tùy theo yêu cầu của môi trƣờng ứng dụng mà ngƣời ta có thể dùng phƣơng pháp này hay phƣơng pháp kia. Có những môi trƣờng cần phải an toàn tuyệt đối bất kể thời gian và chi phí. Có những môi trƣờng lại cần giải pháp dung hòa giữa bảo mật và chi phí. Trong lĩnh vực bảo mật dữ liệu, phƣơng pháp mã hóa số học đƣợc xem là một trong những phƣơng pháp hay. Tuy nhiên, việc ứng dụng phƣơng pháp này vào thực tế gặp phải những khó khăn nhất định, bởi tốc độ thực hiện của thuật toán mã hóa và giải mã chậm, đồng thời độ bảo mật của phƣơng pháp chƣa cao. Luận văn này tập trung đi sâu vào nghiên cứu phƣơng pháp mã hóa số học và các vấn đề liên quan. Luận văn đƣa ra một số cải tiến trong thuật toán mã hóa và giải mã nhằm tăng tốc độ thực hiện và xây dựng mô hình mã hóa dựa trên ý tƣởng của lƣợc đồ RAC (do Marco Grangetto đề xuất) để nâng cao độ bảo mật của phƣơng pháp. Ngoài phần mở đầu và kết luận, kết cấu của luận văn gồm 4 chƣơng:  Chƣơng 1 “Giới thiệu chung về mã hóa thông tin” trình bày những khái niệm cơ bản về mã hóa thông tin. 7  Chƣơng 2 “Cơ sở toán học của phương pháp mã hóa số học” trình bày cơ sở toán học cho phƣơng pháp mã hóa số học.  Chƣơng 3 “Cải tiến phương pháp mã hóa số học” trình bày lịch sử ra đời của phƣơng pháp, thuật toán mã hóa số học truyền thống. Đặc biệt trong chƣơng này đề xuất một số cải tiến nhằm tăng tốc độ thực hiện của thuật toán bằng việc thay thế các phép nhân, chia bởi các phép dịch chuyển bít và đƣa ra một số nhận xét về độ an toàn của phƣơng pháp. Dựa vào mô hình RAC của Grangetto [15] đƣa ra một mô hình cải tiến nhằm nâng cao tính bảo mật của phƣơng pháp mã hóa số học.  Chƣơng 4 “Cài đặt và thử nghiệm” giới thiệu thƣ viện xử lý số nguyên lớn, một số kết quả thử nghiệm trên máy của chƣơng trình mã hóa số học truyền thống và cải tiến. 8 Chƣơng 1. GIỚI THIỆU CHUNG VỀ MÃ HÓA THÔNG TIN Tóm tắt chương: Trong chương này luận văn giới thiệu chung về mã hóa thông tin, lịch sử mật mã, các hệ mã, các bài toàn an toàn thông tin và bài toán thám mã. Đưa ra được một số khái niệm cơ bản nhất của mã hóa như: bản rõ, bản mã, hệ mã hóa thám mã, khóa mã, mã hóa khóa công khai, mã hóa khóa đối xứng, mã theo khối, mã theo dòng.v.v…. Các nội dung của chương này được tổng hợp từ các tài liệu [5]-[9]. 1.1. Một số thuật ngữ và khái niệm 1.1.1. Một số thuật ngữ Văn bản (plaintext) là một thông báo gốc cần chuyển, đƣợc ghi bằng hình ảnh, âm thanh, chữ số, chữ viết,... Về sau, khi đƣa ra các ví dụ, ta thƣờng xem các văn bản đƣợc viết bằng chữ viết, hoặc bằng chữ số. Tuy nhiên, ngày nay mọi tín hiệu (âm thanh, hình ảnh...) đều có thể đƣợc số hóa (thành các xâu ký tự số), cho nên việc nghiên cứu trên các văn bản số không hạn chế các ứng dụng đa dạng của nó. Mã hóa (encrytion) là việc "ngụy trang" văn bản (thông tin nói chung) sang một dạng khác để cho những ngƣời "ngoài cuộc" không thể đọc đƣợc, phục vụ cho nhu cầu trao đổi thông tin, dữ liệu và các giao dịch tài chính, thƣơng mại,... Quá trình "ngụy trang" văn bản gọi là lập mã còn quá trình "khôi phục" lại văn bản nguồn (từ văn bản ngụy trang) gọi là giải mã. Nguyên tắc chung của mã hóa là việc giải mã phải rất dễ dàng với "ngƣời trong cuộc", nhƣng rất khó khăn (thậm chí là không thực hiện đƣợc) đối với "ngƣời ngoài cuộc". Văn bản gốc (trƣớc khi mã hóa) thƣờng đƣợc ký hiệu là PT (Plain Text), hay đơn giản là P. Văn bản mã (đã đƣợc cải trang) thƣờng đƣợc ký hiệu là CT (Ciphertext), hay đơn giản là C. Hệ mã (Cryptosystem) là một phƣơng pháp ngụy trang văn bản. Nghệ thuật tạo ra và sử dụng các hệ mã là thuật mã hóa hay mật mã học (Cryptography). Phân tích mã (Cryptanalysis), hay thám mã, là nghệ thuật phá các hệ mã (nhìn xuyên qua các phƣơng pháp ngụy trang). 9 Công nghệ mã (Cryptology) là việc nghiên cứu tổng hợp cả cryptography và cryptanalysis. Lập mã (encrypt) là việc biến văn bản nguồn thành văn bản mã. Giải mã (decrypt) là việc đƣa văn bản đã mã hóa trở về dạng văn bản nguồn. Định mã (encode/decode) là việc định ra phép tƣơng ứng giữa các chữ và số (việc này không bao giờ đƣợc xem là bí mật, vì máy tính ngày nay dễ dàng tìm ra phép tƣơng ứng này trong một thời gian ngắn). Mã dòng (stream cipher) là việc tiến hành mã hóa liên tục trên từng ký tự (hay từng bit). Mã khối (block cipher) là việc tiến hành mã hóa trên từng khối văn bản (khi khối văn bản là một cặp 2 ký tự thì gọi là digraph, còn khi nó là bộ 3 chữ thì gọi là trigraph). Phép mã chuyển vị (transposition cipher) là việc tráo đổi vị trí giữa các ký tự (các bit) trong văn bản. Phép mã thay thế (substitution) là việc thay thế một ký tự này bằng một ký tự khác (mà không thay đổi vị trí). Phép mã tích hợp (product cipher) là việc tiến hành xen kẽ 2 phép mã chuyển vị và thay thế. Chìa khóa mã (cipher key) là bí quyết lập mã và giải mã. Nếu nhƣ quy trình mã hóa đƣợc xem nhƣ một hàm y = f(x,k), trong đó x là đầu vào (văn bản nguồn), y là đầu ra (văn bản mã), f là phương pháp (hay thuật toán) mã hóa, còn k là một tham số điều khiển, thì bí quyết trƣớc đây thƣờng bao gồm cả phương pháp f, và tham số k. Nhu cầu của thực tiễn hiện nay đã khiến công nghệ mã hóa hiện đại phải thay đổi quan điểm này. Phương pháp f là cái thƣờng do không chỉ một ngƣời nắm, nên không thể giữ đƣợc bí mật lâu, và do đó phải đƣợc xem là công khai. Tham số điều khiển k, có tác dụng làm thay đổi kết quả mã hóa (tùy thuộc vào giá trị của nó), đƣợc xem là chìa khóa mã. Thông thƣờng, nó là một xâu bit (hay một con số nào đó) mà ngƣời ta có thể giữ riêng cho mình. 10 Hệ mã bí mật (secret key cryptosystem - SKC) hay hệ mã đối xứng (symmetric cryptosystem) là hệ mã mà trong đó việc lập mã và giải mã cùng sử dụng chung một chìa khóa mã (bí mật). Hệ mã công khai (public key cryptosystem - PKC) hay hệ mã phi đối xứng (asymmetric cryptosystem) là hệ mã mà trong đó việc lập mã và giải mã sử dụng 2 chìa khóa mã riêng biệt, từ chìa này không thể tìm ra chìa kia một cách dễ dàng, chìa dùng để lập mã thƣờng đƣợc thông báo công khai, còn chìa dành cho việc giải mã phải luôn giữ bí mật, thƣờng đƣợc gọi là chìa khóa riêng.. 1.1.2. Vì sao cần mã hóa Đó là một câu hỏi dễ trả lời, bởi vì trong mọi hoạt động của con ngƣời, nhu cầu trao đổi thông tin mật giữa những thành viên thuộc một nhóm nào đó với nhau là hết sức cần thiết. Tuy nhiên, để thực sự thấy rõ yêu cầu cấp bách của mã hóa trong thời đại ngày nay, cần nhấn mạnh rằng với các phƣơng tiện kỹ thuật hiện đại việc giữ giữ gìn bí mật ngày càng trở nên hết sức khó khăn. Các hình ảnh trên mặt đất, các cuộc đàm thoại hữu tuyến và vô tuyến, các thông tin đƣợc truyền qua mạng internet,... tất cả đều có thể dễ dàng thu đƣợc nhờ các thiết bị điện tử trên mặt đất hoặc từ vệ tinh. Vì thế, phƣơng pháp thông dụng nhất để giữ gìn bí mật thông tin là mã hóa chúng bằng một hệ mã nào đó trƣớc khi truyền đi. Dĩ nhiên, việc mã hóa thông tin trƣớc khi truyền đi và việc giải mã các thông tin nhận đƣợc sẽ tạo nên một số khó khăn: giảm tốc độ truyền tin, tăng chi phí... Một hệ mã lý tƣởng là một hệ mã bảo đảm đƣợc các yêu câu: thời gian mã hóa và giải mã nhanh, độ bảo mật cao (gây khó khăn tối đa cho ngƣời thám mã). Các yêu cầu đó luôn mâu thuẫn nhau, và ngƣời sử dụng cần hiểu rõ công nghệ mã hóa để có thể lựa chọn hệ mã thích hợp cho từng việc và mục đích. 1.2. Vài nét về lịch sử Ngƣời Hi Lạp đã sử dụng phép mã chuyển vị từ 400 năm trƣớc công nguyên. Ngƣời ta dùng một dải băng dài và mảnh quấn quanh một khối hình trụ tròn xoay rồi viết chữ lên đó theo cách thức thông thƣờng (từ trái sang phải và từ trên xuống dƣới). Mẩu tin 11 đƣợc chuyển đi dƣới dạng dải băng và chỉ có thể đọc ra đƣợc khi biết đƣợc bán kính của thiết diện khối trụ (và quấn lại dải băng quanh khối trụ nhƣ khi đã viết lên - hình 1.1). N G A Y M A I T I E N V E P H I A T A Y Hình 1.1 Mô tả phép mã chuyển vị Hoàng đế Caesar đã từng sử dụng phép mã thay thế trong quân sự, trong đó mỗi ký tự đƣợc thay thế bởi ký tự đứng sau nó 3 vị trí trong bảng chữ cái alphabet, nghĩa là chữ A đƣợc thay thế bởi chữ D, chữ B đƣợc thay bởi chữ E, ... Trong thực tế, việc triển khai một hệ mã nhƣ vậy là khá đơn giản (và cũng rất thuận tiện cho việc sử dụng), với việc dùng hai chiếc đĩa đồng tâm có bán kính khác nhau và có các bảng chữ cái alphabet rải đều trên mỗi vành đĩa (hình 1.2). Hình 1.2 Bảng đĩa chữ cái Việc xoay (một trong hai đĩa) sao cho chữ A trên vành đĩa nhỏ nằm trên bán kính nối tâm đĩa với chữ D trên vành đĩa lớn sẽ xác định phép mã Caesar nói trên, thông qua phép tƣơng ứng giữa các chữ cái trên vành đĩa nhỏ với các chữ cái trên vành đĩa lớn. Nói chung, việc xoay đĩa đi một góc bất kỳ (miễn sao các chữ trên vành đĩa nhỏ và trên vành đĩa lớn đƣợc tƣơng ứng nhau rõ ràng) sẽ mang lại một phép mã theo kiểu Caesar. 12 Mã khối đƣợc xem là xuất hiện vào những năm đầu thế kỷ XX, với sự ra đời của hệ mã British Playfair vào năm 1910, trong đó mỗi khối là một cặp 2 chữ (digraph). Phép mã ở đây là thay thế theo chìa. Ngƣời ta viết 26 chữ cái (của tiếng Anh) vào một bảng hình vuông (5 cột, 5 dòng), trong đó 2 chữ I và J đƣợc viết vào cùng một chỗ. Hai dòng đầu tiên dành cho chìa khóa (gồm 10 ký tự không trùng lặp), 3 dòng dƣới viết 16 chữ cái còn lại (không có trong chìa khóa) theo thứ tự thông thƣờng (từ trái sang phải và từ trên xuống dƣới). Thí dụ, với chìa khóa là PALMERSTON thì bảng đƣợc xếp nhƣ sau: P A L M E R S T O N B C D F G H IJ K Q U V W X Y Z Hình 1.3 Minh họa mã khối Muốn mã hóa một khối (cặp 2 chữ) nào đó, không ở trên cùng một dòng hay một cột, ta tìm cách thiết lập một hộp (chữ nhật) với 2 đỉnh là 2 chữ trong khối đó, còn 2 đỉnh còn lại cho ta cặp chữ là kết quả mã của cặp chữ nguồn, thí dụ cặp chữ SF sẽ xác định hộp chữ nhật 4 đỉnh là SOFC và do đó cặp chữ SF đƣợc mã hóa thành cặp CO. Muốn mã hóa cặp 2 chữ trên cùng một dòng thì thay thế mỗi chữ bằng chữ kế tiếp bên phải nó trên cùng dòng đó (nếu là chữ cuối dòng thì thay bằng chữ đầu dòng). Thí dụ, cặp chữ SO sẽ đƣợc mã hóa thành TN, còn cặp CG sẽ biến thành cặp DB. Muốn mã hóa cặp 2 chữ nằm trên cùng một cột, ta thay mỗi chữ bằng chữ ngay bên dƣới nó (nếu chữ nằm ở đáy cột thì đƣợc thay bằng chữ ở đỉnh cột). Thí dụ, SI sẽ biến thành CW. Các chữ đúp sẽ đƣợc tách ra bằng chữ X trƣớc khi cho mã hóa, thí dụ chữ BALLOON sẽ đƣợc xử lý thành BALXLOXON. Hệ mã tích hợp (product cipher) đƣợc sử dụng sớm nhất là của quân đội Đức trong Đại chiến Thế giới lần thứ I, mang tên là ADFGVX. Cho trƣớc một bảng nhƣ hình 1.4 A D F G V X A K Z W R 1 F D 9 B 6 C L 5 13 F Q 7 J P G X G E V Y 3 A N V 8 O D H 0 2 X U 4 I S T M Hình 1.4 Hệ mã tích hợp Phần thay thế cho phép thay mỗi ký tự bằng một cặp 2 ký tự ứng với "tung độ" và "hoành độ" của chữ đó trong bảng. Thí dụ chữ P sẽ biến thành cặp FG, chữ R biến thành AG, và PRODUCTCIPHERS sẽ biến thành FGAGVVDVFXADGXVDGXFFGVGGAAGXG Phần chuyển vị đƣợc tiến hành tiếp theo sau và phụ thuộc vào chìa (với các chữ không trùng lặp), thí dụ là DEUTSCH. Hãy đánh số các chữ trong chìa theo thứ tự nhƣ trong bảng chữ cái alphabet (thí dụ: chữ C sẽ đƣợc đánh số 1, chữ D sẽ đƣợc đánh số 2,...). Hãy đặt kết quả "mã hóa nửa vời" thu đƣợc ở trên theo từng dòng (nằm dƣới chìa, nghĩa là D E U S C H 2 3 7 6 1 4 F G A G D V F X A D X V D G X F G V G G A A X G Hình 1.5 Ví dụ hệ mã tích hợp Viết các chữ cái theo từng cột (với thứ tự xác định theo chỉ số cột). Thí dụ, cột thứ nhất gồm các chữ DXGF sẽ đƣợc viết đầu tiên, và cột thứ 2 gồm các chữ FFDG sẽ đƣợc viết tiếp theo, v.v... Tóm lại, ta đƣợc văn bản sau khi mã hóa là DXGXFFDGGXGGVVVGVGFGGDFAAAXA Trong Đại chiến Thế giới lần thứ II, ngƣời ta thấy rằng hệ mã tích hợp (luân phiên giữa thay thế và chuyển vị) là rất an toàn. Tuy nhiên, hệ mã ADFGVX có những điểm yếu ở chỗ chỉ có một vòng (phép thay thế và chuyển vị chỉ đƣợc thực hiện một lần) và phép 14 thay thế lại không có chìa điều khiển. Chính vì vậy, một hệ mã tích hợp khác, phức tạp hơn, đã đƣợc sử dụng trong Thế chiến thứ II, đó là ENIGMA. Tuy nhiên, từ những năm cuối của thập kỷ 60, mối đe dọa về vấn đề "an toàn máy tính" đã trở thành hiện thực. Ngƣời ta cần đến các chƣơng trình mã hóa mạnh hơn để chống lại khả năng phá mã của các siêu máy tính với tốc độ ngày càng lớn. Vấn đề này đã đƣợc quan tâm nghiên cứu tích cực trong các năm 1968-1975 và đƣợc đánh dấu bằng sự ra đời của hệ mã Lucifer (1974) và sau đó đƣợc cải tiến thành hệ mã dữ liệu tiêu chuẩn DES (1975), một hệ mã khối đối xứng với chìa khóa dài 56 bits, kết hợp luân phiên 16 phép thay thế với 15 phép hoán vị. Tiếp sau đó, sự ra đời của hệ mã hóa với kháo công khai, vào cuối những năm 70 của thế kỷ vừa qua, đã khẳng định vai trò then chốt của các phƣơng pháp Toán học trong lĩnh vực mã hóa hiện đại. 1.3. Khái niệm hệ mã hóa Để bảo đảm an toàn thông tin lƣu trữ trong máy tính (giữ gìn thông tin cố định) hay bảo đảm an toàn thông tin trên đƣờng truyền tin (ví dụ trên mạng máy tính), 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ác “khó” nhận ra. Nói cách khác “Mã hóa” thông tin là “che” đi “Ý nghĩa” của thông tin, và ngƣời khác “khó” hiểu đƣợc (“khó” đọc đƣợc) thông tin đã mã hoá. “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. Việc mã hoá phải theo 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ã. 15 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 (T)) = T,  T  P. Ở đây T đƣợc gọi là bản rõ, eke (T) đƣợc gọi là bản mã. Ngƣời gửi G   (có khóa lập mã ke) eke(T)   Ngƣời nhận N (có khóa giải mã kd)  Tin tặc có thể trộm bản mã eke (T) Ngƣời gửi G muốn gửi bản tin T cho ngƣời nhận N. Để bảo đảm bí mật, G mã hoá bản tin bằng khóa lập mã ke, nhận đƣợc bản mã eke(T), sau đó gửi cho N. Tin tặc có thể trộm bản mã eke(T), nhƣng cũng “khó” hiểu đƣợc bản tin gốc T nếu không có khoá giải mã kd. Ngƣời N nhận đƣợc bản mã, họ dùng khoá giải mã kd, để giải mã eke(T), sẽ nhận đƣợc bản tin gốc T = dkd (eke(T)). 1.4. Phân loại hệ mã hóa Hiện có hai loại mã hóa chính: mã hóa khóa đối xứng và mã hóa khoá công khai. Hệ mã hóa khóa đối xứng có khóa lập mã và khóa giải mã “giống nhau”, theo nghĩa biết đƣợc khóa này thì “dễ” tính đƣợc khóa kia. Vì vậy phải giữ bí mật cả 2 khóa. Hệ mã hóa khóa công khai có khóa lập mã khác khóa giải mã (ke  kd), biết đƣợc khóa này cũng “khó” tính đƣợc khóa kia. Vì vậy chỉ cần bí mật khóa giải mã, còn công khai khóa lập mã. 1.4.1. Hệ mã hóa khóa đối xứng Mã hóa khóa đối xứng là Hệ mã hóa mà biết đƣợc khóa lập mã thì có thể "dễ" tính đƣợc khóa giải mã và ngƣợc lại. Đặc biệt một số Hệ mã hóa có khóa lập mã và khóa giải mã trùng nhau (ke = kd), nhƣ Hệ mã hóa "dịch chuyển" hay DES (Data Encryption Standard). Hệ mã hóa khóa đối xứng còn có tên gọi là Hệ mã hóa khoá bí mật hay khóa riêng, vì phải giữ bí mật cả 2 khóa. Trƣớc khi dùng Hệ mã hóa khóa đối xứng, ngƣời gửi và 16 ngƣời nhận phải thoả thuận thuật toán mã hóa và một khoá chung (lập mã hay giải mã), khoá này phải đƣợc giữ bí mật. Độ an toàn của Hệ mã hóa loại này phụ thuộc vào khoá. 1.4.1.1. Đặc điểm của hệ mã hóa khóa đối xứng Ƣu điểm: - Hệ mã hóa khóa đối xứng có tốc độ mã hóa và giải mã nhanh hơn Hệ mã hóa khóa công khai. Hạn chế: - Mã hóa khóa đối xứng chƣa thật an toàn với lý do đơn giản sau: ngƣời mã hóa và ngƣời giải mã phải có "chung" một khóa. Khóa phải đƣợc giữ bí mật tuyệt đối, vì biết khóa này "dễ" xác định đƣợc khóa kia và ngƣợc lại. - Vấn đề thỏa thuận khóa và quản lý khóa chung là khó khăn và phức tạp. Ngƣời gửi và ngƣời nhận phải luôn thống nhất với nhau về khóa. Việc thay đổi khóa là rất khó và dễ bị lộ. Khóa chung phải đƣợc gửi cho nhau trên kênh an toàn. Mặt khác khi hai ngƣời (lập mã, giải mã) cùng biết "chung" một bí mật, thì càng khó giữ bí mật. 1.4.1.2. Nơi sử dụng hệ mã hóa khóa đối xứng Hệ mã hóa khóa đối xứng thƣờng đƣợc sử dụng trong môi trƣờng mà khoá chung có thể dễ dàng trao chuyển bí mật, chẳng hạn trong cùng một mạng nội bộ. Hệ mã hóa khóa đối xứng thƣờng dùng để mã hóa những bản tin lớn, vì tốc độ mã hóa và giải mã nhanh hơn Hệ mã hóa khóa công khai. 1.4.2. Hệ mã hóa khóa công khai Hệ mã hóa khóa phi đối xứng là Hệ mã hóa có khóa lập mã và khóa giải mã khác nhau (ke ≠ kd), biết đƣợc khóa này cũng "khó" tính đƣợc khóa kia. Hệ mã hóa này còn đƣợc gọi là Hệ mã hóa khóa công khai vì: khóa lập mã cho công khai (gọi là khóa công khai - public key), khóa giải mã giữ bí mật còn gọi là khóa riêng (private key) hay khóa bí mật. Một ngƣời bất kỳ có thể dùng khóa công khai để mã hóa bản tin, nhƣng chỉ ngƣời nào có đúng khóa giải mã thì mới có khả năng đọc đƣợc bản rõ. Hệ mã hóa khóa công khai hay Hệ mã hóa phi đối xứng do Diffie và Hellman phát minh vào những năm 1970. 17 1.4.2.1. Đặc điểm của Hệ mã hóa khóa công khai Ƣu điểm: - Thuật toán đƣợc viết một lần, công khai cho nhiều lần dùng, cho nhiều ngƣời dùng, họ chỉ cần giữ bí mật khóa riêng của mình. - Khi biết các tham số ban đầu của hệ mã, việc tính ra cặp khóa công khai và bí mật phải là "dễ", tức là trong thời gian đa thức. Ngƣời gửi có bản rõ P và khóa công khai, thì "dễ" tạo ra bản mã C. Ngƣời nhận có bản mã C và khóa bí mật, thì "dễ" giải đƣợc thành bản rõ P. - Ngƣời mã hóa dùng khóa công khai, ngƣời giải mã giữ khóa bí mật. Khả năng lộ khóa bí mật khó hơn vì chỉ có một ngƣời giữ gìn. Nếu thám mã biết khóa công khai, cố gắng tìm khóa bí mật, thì chúng phải đƣơng đầu với bài toán "khó", số phép thử là vô cùng lớn, không khả thi. Hạn chế: Tốc độ mã hóa và giải mã chậm hơn hệ mã hóa khóa đối xứng. 1.4.2.2. Nơi sử dụng Hệ mã hóa khóa đối xứng Hệ mã hóa khóa công khai thƣờng đƣợc sử dụng chủ yếu trên các mạng công khai nhƣ internet, khi mà việc trao chuyển khóa bí mật tƣơng đối khó khăn. Đặc trƣng nổi bật của hệ mã hóa khóa công khai là khóa công khai và bản mã đều có thể gửi đi trên một kênh truyền tin không an toàn. Có biết cả khóa công khai và bản mã thì thám mã cũng không dễ khám phá đƣợc bản rõ. Nhƣng vì có tốc độ mã hóa và giải mã chậm, nên hệ mã hóa khóa công khai chỉ dùng để mã hóa những bản tin ngắn, ví dụ nhƣ mã hóa khóa bí mật gửi đi. Hệ mã hóa khóa công khai thƣờng đƣợc sử dụng cho cặp ngƣời dùng thỏa thuận khóa bí mật của Hệ mã hóa khóa riêng. 18 1.5. Một số hệ mã hóa khóa đối xứng và mã hóa khóa công khai 1.5.1. Hệ mã hóa đối xứng cổ điển Khái niệm: Hệ mã hóa đối xứng đã đƣợc dùng từ rất sớm, nên còn gọi là Hệ mã hóa đối xứng - cổ điển (gọi ngắn gọn là Hệ mã hóa đối xứng cổ điển). Bản mã và bản rõ là dãy các ký tự Latin. Quá trình lập mã đƣợc thực hiện nhƣ sau: 1. Nhập bản rõ ký tự: Rõ_chữ 2. Chuyển Rõ_chữ thành Rõ_số 3. Chuyển Rõ_số thành Mã_số 4. Chuyển Mã_số thành Mã_chữ Quá trình giải mã thực hiện theo các bƣớc sau: 1. Nhập bản mã ký tự: Mã_chữ 2. Chuyễn Mã_chữ thành Mã_số 3. Chuyển Mã_số thành Rõ_số 4. Chuyễn Rõ_số thành Rõ_chữ Để chuyển từ Chữ sang Số hay ngƣợc lại từ Số trở về Chữ, ngƣời ta theo một quy ƣớc nào đó, ví dụ chữ cái thay bằng số theo modulo 26 nhƣ sau: A B C D E F G H I J K L M N O P Q R S T U V W X Y Z 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 Để thực hiện mã hóa hay giải mã với các "số", ngƣời ta dùng các phép toán số học theo modulo 26. Các hệ mã hóa cổ điển: Mã hóa cổ điển gồm nhiều hệ, ví dụ: Hệ mã hóa dịch chuyển: Khóa có 1 “chìa”. (Thể hiện bằng 1 giá trị). Hệ mã Affine: Khóa có 2 “chìa”. (Thể hiện bằng 2 giá trị). Hệ mã hóa thay thế: Khóa có 26 “chìa”. (Thể hiện bằng 26 giá trị). Hệ mã hóa VIGENERE: Khóa có m “chìa”. (Thể hiện bằng m giá trị). 19 Khóa có ma trận “chìa” (chùm chìa khóa). Hệ mã hóa HILL: 1.5.1.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 Ví dụ: Bản rõ chữ: DAIHOCCONGNGHE Chọn khóa k = 3 Bản rõ số: 3 0 8 7 14 2 2 14 13 6 7 4 Với phép mã hóa y = ek(x) = (x+k) mod 26 = (x+3) mod 26, ta nhận đƣợc: Bản mã số: 6 3 11 10 17 5 5 17 16 9 10 7 Bản mã chữ: GDLKRFFRQJKH Giải mã: từ bản mã chữ ở trên ta chuyển về bản mã số và với phép giải mã x = dk(y) = (y-k) mod 26 = (y-3) mod 26, ta nhận đƣợc lại bản rõ số, sau đó chuyển bản rõ số trở về bản rõ chữ ban đầu. Độ an toàn: Độ an toàn của mã dịch chuyển 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,…,26. 1.5.1.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à một hoán vị trên Z26 ta định nghĩa Hàm mã hóa: y = eп(x) = п(x) Hàm giải mã : x = dп(y) = п-1(y) Ví dụ: Bản rõ chữ: DAIHOCCONGNGHE Chọn khóa k = п là hoán vị sau: A B C D E F G H I J K L M N O P Q R S T U V W X Y Z X N Y A H P O G Z Q W B T S F L R C V M U E K D I J 20 Mã hóa theo công thức y = eп(x) = п(x) ta đƣợc bản mã chữ Bản mã chữ: AXZGFYYFSOSOGH Giải mã theo công thức x = dп(y) = п-1(y) ta nhận lại đƣợc bản rõ ban đầu. Độ an toàn: Hệ mã hóa thay thế có số khóa có thể bằng số các phép hoán vị trên tập Z26, tức là 26! khóa, đó là một số rất lớn. Do đó, việc duyệt lần lƣợt tất cả các khóa có thể để thám mã là không thực tế, ngay cả dùng máy tính. Tuy vậy, có những phƣơng pháp thám mã khác hiệu quả hơn, làm cho hệ mã hóa thay thế không thể đƣợc xem là an toàn. 1.5.1.3. Hệ mã 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: Hàm mã hóa: y = ek(x) = (ax+b) mod 26 Hàm giải mã : x = dk(y) = a-1(y-b) mod 26 Có điều kiện UCLN(a,26) =1 là để bảo đảm có phần tử nghịch đảo a-1 mod 26 của a, làm cho thuật toán giải mã dk luôn thực hiện đƣợc. Có tất cả (26) = 12 số a  Z26 nguyên tố với 26, đó là các số: 1,3, 5, 7, 9, 11, 15, 17, 19, 21, 23, 25 và các số nghịch đảo theo mod26 tƣơng ứng của chúng là: 1, 9, 21, 15, 3, 19, 7, 23, 11, 5, 17, 25. Ví dụ: Bản rõ chữ: DAIHOCCONGNGHE Chọn khóa k = (a,b) = (3,6) Bản rõ số: x = 3 0 8 7 14 2 2 14 13 6 7 4 Mã hóa theo công thức y = ek(x) = (ax + b) mod 26 = (3x+6) mod 26 Bản mã số: 14 6 4 1 22 12 12 22 19 24 1 18 Bản mã chữ: OGEBWMMWTYBS Giải mã theo công thức: x = dk(y) = a-1(y-b) mod 26 = 3-1(y-6) mod 26 = 9(y-6) mod 26 Độ an toàn: Vì có 12 số thuộc Z26 nguyên tố với 26, nên số các khóa có thể có (do đó, số các hệ mật mã affine) bằng 12×26 = 312, một con số không lớn lắm nếu ta sử dụng máy tính để thực hiện việc thám mã bằng cách duyệt lần lƣợt tất cả các khóa có thể, nhƣ vậy, mã affine cũng không đƣợc xem là mã an toàn.