›

Giáo trình Cơ sở mật mã học - Nguyễn Bình

pdf 85 trang huongle 4600
Download
Bạn đang xem 20 trang mẫu của tài liệu "Giáo trình Cơ sở mật mã học - Nguyễn Bình", để tải tài liệu gốc về máy bạn click vào nút DOWNLOAD ở trên

Tài liệu đính kèm:

  • pdfgiao_trinh_co_so_mat_ma_hoc_nguyen_binh.pdf

Nội dung text: Giáo trình Cơ sở mật mã học - Nguyễn Bình

  1. Häc viÖn c«ng nghÖ b­u chÝnh viÔn th«ng GIÁO TRÌNH C¥ së mËt m· häc Chủ biên: GS.TS Nguyễn Bình Cộng tác viên: TS. Ngô Đức Thiện Khoa KTĐT1 - Học viện CNBCVT PTIT Hà Nội - 2013
  2. MỤC LỤC LỜI NÓI ĐẦU i MỤC LỤC iii CHƯƠNG 1. NHẬP MÔN MẬT MÃ HỌC 1 1.1. SƠ ĐỒ KHỐI ĐƠN GIẢN CỦA MỘT HỆ THỐNG THÔNG TIN SỐ 1 1.2. SƠ LƯỢC VỀ MẬT MÃ HỌC 2 1.3. THUẬT TOÁN VÀ ĐỘ PHỨC TẠP 3 1.3.1. Khái niệm về thuật toán 3 1.3.2. Độ phức tạp của thuật toán 4 1.4. LÝ THUYẾT THÔNG TIN TRONG CÁC HỆ MẬT 7 1.4.1. Độ mật hoàn thiện. 7 1.4.2. Entropy 13 BÀI TẬP CHƯƠNG 1. 22 CHƯƠNG 2. MẬT MÃ KHÓA BÍ MẬT 24 2.1. SƠ ĐỒ KHỐI MỘT HỆ TRUYỀN TIN MẬT 24 2.2. MẬT MÃ THAY THẾ 25 2.2.1. Mật mã dịch vòng (MDV) 25 2.2.2. Mã thay thế (MTT) 26 2.2.3. Mật mã Vigenère 26 2.3. MẬT MÃ HOÁN VỊ (MHV) 31 2.4. MẬT MÃ HILL 32 2.5. HỆ MẬT XÂY DỰNG TRÊN CÁC CẤP SỐ NHÂN XYCLIC CỦA VÀNH ĐA THỨC PTIT 36 2.5.1. Nhóm nhân của vành 36 2.5.2. Các phần tử cấp n và các nhóm nhân xyclic cấp n 37 2.5.3. Hệ mật xây dựng trên các cấp số nhân xyclic 38 2.6. CÁC HỆ MẬT MÃ TÍCH 44 2.7. CÁC HỆ MÃ DÒNG 46 2.7.1. Sơ đồ chức năng của hệ mật mã dòng 46 2.7.2. Tạo dãy giả ngẫu nhiên (M-dãy) 48 2.8. CHUẨN MÃ DỮ LIỆU 53 2.8.1. Mở đầu 53 iii
  3. Ch­¬ng 1: NhËp m«n mËt m· häc CHƯƠNG 1. NHẬP MÔN MẬT MÃ HỌC 1.1. SƠ ĐỒ KHỐI ĐƠN GIẢN CỦA MỘT HỆ THỐNG THÔNG TIN SỐ Đầu vào rõ Bản rõ Bản mã Biến đổi A/D Mã Mã bảo Mã (Tương tự - số) nguồn mật kênh Nguồn tin tương tự Từ mã được truyền Kênh truyền (Tạp âm, đa đường, giao thoa, nhiễu, nghe trộm ) Từ mã nhận Đầu ra số Bản rõ Bản mã được Biến đổi D/A Giải mã Giải mã Giải mã (Số - tương tự) nguồn bảo mật kênh Nhận tin Hình 1.1. Sơ đồ hệ thống thông tin số Trường hợp nguồn tin đầu vào là nguồn tin số thì không cần bộ biến đổi A/D ở đầu vào và bộ biến đổi D/A ở đầu ra Trong hệ thống này khối mã bảo mật có chức năng bảo vệ cho thông tin không bị khai thác bất hợp pháp, chống lại các tấn công sau: - Thám mã thụ động: bao gồm các hoạt động: + Thu chặn. PTIT + Dò tìm. + So sánh tương quan. + Suy diễn. - Thám mã tích cực: bao gồm các hoạt động: + Giả mạo. + Ngụy trang. + Sử dụng lại. + Sửa đổi. 1
  4. Ch­¬ng 1: NhËp m«n mËt m· häc 1.2. SƠ LƯỢC VỀ MẬT MÃ HỌC Khoa học về mật mã (cryptology) bao gồm: - Mật mã học (cryptography). - Phân tích mật mã (cryptanalysis). Mật mã học là khoa học nghiên cứu cách ghi bí mật thông tin nhằm biến bản tin rõ thành các bản mã. Phân tích mã là khoa học nghiên cứu cách phá các hệ mật nhằm phục hồi bản rõ ban đầu từ bản mã. Việc tìm hiểu các thông tin về khóa và các phương pháp biến đổi thông tin cũng là một nhiệm vụ quan trọng của phân tích mật mã. Có ba phương pháp tấn công cơ bản của thám mã: Tìm khóa vét cạn. Phân tích thống kê. Phân tích toán học. Việc tấn công của thám mã có thể được thực hiện với các giả định: Tấn công chỉ với bản mã. Tấn công với bản rõ đã biết. Tấn công với các bản rõ được chọn. Tấn công với các bản mã được chọn. Chú ý: Một hệ mật có thể bị phá chỉ với bản mã thường là hệ mật có độ an toàn thấp. Một hệ mật là an toàn với kiểu tấn công có các bản rõ được chọn thường là một hệ mật có độ an toàn cao. Có 4 loại hệ mật mã sau: Hệ mật mãPTIT dòng. Hệ mật mã khối đối xứng. Hệ mật mã có hồi tiếp mật mã. Hệ mật mã khóa công khai (Bất đối xứng). Ta sẽ nghiên cứu các loại hệ mật trên ở các chương sau. Khi xây dựng một hệ mật người ta thường xem xét tới các tiêu chuẩn sau: Độ mật cần thiết. Kích thước không gian khóa. Tính đơn giản và tốc dộ mã hóa và giải mã. Tính lan truyền sai. Tính mở rộng bản tin. 2
  5. Ch­¬ng 1: NhËp m«n mËt m· häc 1.3. THUẬT TOÁN VÀ ĐỘ PHỨC TẠP 1.3.1. Khái niệm về thuật toán 1.3.1.1. Định nghĩa thuật toán Có thể định nghĩa thuật toán theo nhiều cách khác nhau. Ở đây ta không có ý định trình bày chặt chẽ về thuật toán mà sẽ hiểu khái niệm thuật toán theo một cách thông thường nhất. Định nghĩa 1.1: Thuật toán là một quy tắc để với những dữ liệu ban đầu đã cho, tìm được lời giải của bài toán được xét sau một khoảng thời gian hữu hạn. Để minh họa cách ghi một thuật toán cũng như tìm hiểu các yêu cầu đề ra cho thuật toán, ta xét trên các ví dụ cụ thể sau đây: Cho n số X 1,X 2, ,X n ta cần tìm m và j sao cho: m X j  maxX k  1 k n Và j là lớn nhất có thể. Điều đó có nghĩa là cần tìm cực đại của các số đã cho và chỉ số lớn nhất trong các số cực đại. Với mục tiêu tìm số cực đại với chỉ số lớn nhất, ta xuất phát từ giá trị X [n ]. Bước thứ nhất, vì mới chỉ có một số ta có thể tạm thời xem m X [n ] và j n . Tiếp theo ta so sánh X [n ] với X [n 1] . Nếu X [n ] không nhỏ hơn X [n 1] thì ta giữ nguyên, trong trường hợp ngược lại, X [n 1] chính là số cực đại trong hai số đã xét và ta phải thay đổi m và j . Đặt m X [n 1] , j 1, ,n 1. Với cách làm như trên, ở mỗi bước ta luôn nhận được số cực đại trong số những số đã xét. Bước tiếp theo là so sánh nó với những số đứng trước hoặc kết thúc thuật toán trong trường hợp không còn số nào đứng trước nó. 1.3.1.2. Thuật toán tìm cực đại M1: [Bước xuất phát] đPTITặt j  n, k  n 1,m  X [n ] M2: [Đã kiểm tra xong?]. Nếu k 0 , thuật toán kết thúc. M3: [So sánh]. Nếu X [k] m , chuyển sang M5 M4: [Thay đổi m ]. Đặt j  k, m  X [k] (Tạm thời m đang là cực đại). M5: [Giảm k ]. Đặt k  k 1 quay về M2. Dấu "  " dùng để chỉ một phép toán quan trọng là phép thay chỗ (replacement). Trên đây ta ghi thuật toán bằng ngôn ngữ thông thường. Trong trường hợp thuật toán được viết bằng ngôn ngữ của máy tính, ta có một chương trình. 3
  6. Ch­¬ng 1: NhËp m«n mËt m· häc Trong thuật toán có những số liệu ban đầu được cho trước khi thuật toán bắt đầu làm việc được gọi là các đầu vào (input). Trong thuật toán trên đầu vào là các số X [1],X [2], ,X [n] . Một thuật toán có thể có một hoặc nhiều đầu ra (output). Trong thuật toán trên các đầu ra là m và j . Có thể thấy rằng thuật toán vừa mô tả thỏa mãn các yêu cầu của một thuật toán nói chung, đó là: - Tính hữu hạn: Thuật toán cần phải kết thúc sau một số hữu hạn bước. Khi thuật toán ngừng làm việc ta phải thu được câu trả lời cho vấn đề đặt ra. Thuật toán m rõ ràng thỏa mãn điều kiện này, vì ở mỗi bước ta luôn chỉ từ việc xem xét một số sang số đứng trước nó và số các số là hữu hạn. - Tính xác định: Ở mỗi bước thuật toán cần phải xác định, nghĩa là chỉ rõ việc cần làm. Nếu đối với người đọc thuật toán trên chưa thỏa mãn được điều kiện này thì đó là lỗi của người viết. Ngoài những yếu tố kể trên, ta còn phải xét đến tính hiệu quả của thuật toán. Có rất nhiều thuật toán về mặt lý thuyết là hữu hạn bước, tuy nhiên thời gian “hữu hạn” đó vượt quá khả năng làm việc của chúng ta. Những thuật toán đó sẽ không được xét đến ở đây, vì chúng ta chỉ quan tâm những thuật toán có thể sử dụng thực sự trên máy tính. Cũng do mục tiêu trên, ta còn phải chú ý đến độ phức tạp của các thuật toán. Độ phức tạp của một thuật toán có thể được đo bằng không gian tức là dung lượng bộ nhớ của máy tính cần thiết để thực hiện thuật toán và bằng thời gian, tức là thời gian máy tính làm việc. Ở đây khi nói đến độ phức tạp của thuật toán ta luôn hiểu là độ phức tạp của thời gian. 1.3.2. Độ phức tạp của thuật toán Thời gian làm việc của máy tính khi chạy một thuật toán nào đó không chỉ phụ thuộc vào thuật toán mà còn phụ thuộc vào máy tính được sử dụng. Vì thế, để có một tiêu chuẩn chung, ta sẽ đo độ phức tạp của một thuật toán bằng số các phép tính phải làm khi thực hiện thuật toán. Khi tiến hành cùng một thuật toán, số các phép tính phải thực hiện còn phụ thuộc vào cỡ của bài toán, tức là đPTITộ lớn của đầu vào. Vì thế độ phức tạp của thuật toán sẽ là một hàm số của độ lớn đầu vào. Trong những ứng dụng thực tiễn, chúng ta không cần biết chính xác hàm này mà chỉ cần biết “cỡ” của chúng, tức là cần có một ước lượng đủ tốt của chúng. Trong khi làm việc, máy tính thường ghi các chữ số bằng bóng đèn “sáng, tắt”, bóng đèn sáng chỉ số 1, bóng đèn tắt chỉ số 0. Vì thế để thuận tiện nhất là dùng hệ đếm cơ số 2, trong đó để biểu diễn một số, ta chỉ cần dùng hai ký hiệu 0 và 1. Một ký hiệu 0 hoặc 1 được gọi là 1bit “viết tắt của binary digit”. Một số nguyên n biểu diễn bởi k chữ số 1 và 0 được gọi là một số k bit . Độ phức tạp của một thuật toán được đo bằng số các phép tính bit. Phép tính bit là một phép tính logic hay số học thực hiện trên các số một bit 0 và 1. Để ước lượng độ phức tạp của thuật toán ta dùng khái niệm bậc O lớn. 4
  7. Ch­¬ng 1: NhËp m«n mËt m· häc Định nghĩa 1.2: Giả sử f n  và gn  là hai hàm xác định trên tập hợp các số nguyên dương. Ta nói f n có bậc O-lớn của gn  và viết f n  O gn  , nếu tồn tại một số C 0 sao cho với n đủ lớn. Các hàm f n  và gn  đều dương thì f n  C gn  . Ví dụ 1.1. : d d 1 1) Giả sử f n  là đa thức: f n  adn ad 1n a1n a0 trong đó ad 0 . Dễ chứng minh f n  O n d . 2) Nếu f n  O gn  , f2 n  O gn  thì f1 f2 O g . 3) Nếu f1 O g1 , f2 O g2 thì f1 f2 O g1g2 . 4) Nếu tồn tại giới hạn hữu hạn: f n  lim n gn  thì f O g 5) Với mọi số  0 , logn O n  Định nghĩa 1.3: Một thuật toán được gọi là có độ phức tạp đa thức hoặc có thời gian đa thức, nếu số các phép tính cần thiết để thực hiện thuật toán không vượt quá O logd n , trong đó n là độ lớn của đầu vào và d là số nguyên dương nào đó. Nói cách khác nếu đầu vào là các số k bit thì thời gian thực hiện thuật toán là O k d , tức là tương đương với một đa thức của k . Các thuật toán với thờiPTIT gian O n , 0 được gọi là thuật toán với độ phức tạp mũ hoặc thời gian mũ. Chú ý rằng nếu một thuật toán nào đó có độ phức tạp O g thì cũng có thể nói nó có độ phức tạp O h với mọi hàm h g . Tuy nhiên ta luôn luôn cố gắng tìm ước lượng tốt nhất có thể để tránh hiểu sai về độ phức tạp thực sự của thuật toán. Cũng có những thuật toán có độ phức tạp trung gian giữa đa thức và mũ. Ta thường gọi đó là thuật toán dưới mũ. Chẳng hạn thuật toán nhanh nhất được biết hiện nay để phân tích một số nguyên n ra thừa số là thuật toán có độ phức tạp: exp logn loglogn 5
  8. Ch­¬ng 1: NhËp m«n mËt m· häc Khi giải một bài toán không những ta chỉ cố gắng tìm ra một thuật toán nào đó, mà còn muốn tìm ra thuật toán “tốt nhất”. Đánh giá độ phức tạp là một trong những cách để phân tích, so sánh và tìm ra thuật toán tối ưu. Tuy nhiên độ phức tạp không phải là tiêu chuẩn duy nhất để đánh giá thuật toán. Có những thuật toán về lý thuyết thì có độ phức tạp cao hơn một thuật toán khác, nhưng khi sử dụng lại có kết quả (gần đúng) nhanh hơn nhiều. Điều này còn tùy thuộc những bài toán cụ thể, những mục tiêu cụ thể và cả kinh nghiệm của người sử dụng. Chúng ta cần lưu ý thêm một số điểm sau đây. Mặc dù định nghĩa thuật toán mà chúng ta đưa ra chưa phải là chặt chẽ, nó vẫn quá “cứng nhắc” trong những ứng dụng thực tế. Bởi vậy chúng ta còn cần đến các thuật toán “xác suất”, tức là các thuật toán phụ thuộc vào một hay nhiều tham số ngẫu nhiên. Những “thuật toán” này về nguyên tắc không được gọi là thuật toán vì chúng có thể với xác suất rất bé, không bao giờ kết thúc. Tuy nhiên thực nghiệm chỉ ra rằng, các thuật toán xác suất thường hữu hiệu hơn các thuật toán không xác suất. Thậm chí trong rất nhiều trường hợp, chỉ có các thuật toán như thế là sử dụng được. Khi làm việc với các thuật toán xác suất, ta thường hay phải sử dụng các số “ngẫu nhiên”. Khái niệm chọn số ngẫu nhiên cũng cần được chính xác hóa. Thường thì người ta sử dụng một “máy” sản xuất số giả ngẫu nhiên nào đó. Tuy nhiên ở đây khi nói đến việc chọn số ngẫu nhiên ta hiểu đó là được thực hiện trên máy. Cần chú ý ngay rằng, đối với các thuật toán xác suất, không thể nói đến thời gian tuyệt đối, mà chỉ có thể nói đến thời gian hy vọng (expected). Để hình dung được phần nào “độ phức tạp” của các thuật toán khi làm việc với những số lớn, ta xem Bảng 1.1 dưới đây cho khoảng thời gian cần thiết để phân tích một số nguyên n ra thừa số nguyên tố bằng thuật toán nhanh nhất được biết hiện nay. Bảng 1.1. Độ phức tạp để phân tích số nguyên ra thừa số nguyên tố Số chữ số thập phân Số phép tính bit Thời gian 50 1,4.1010 3,9 giờ 75 9.1012 104 ngày 100 PTIT15 74 năm 2,3.10 200 1,2.1023 3,8.109 năm 300 1,5.1029 4,9.1015 năm 500 1,3.1039 4,2.1025 năm Từ Bảng 1.1 trên, ta thấy rằng ngay với một thuật toán dưới mũ, thời gian làm việc với các số nguyên lớn là quá lâu. Vì thế nói chung người ta luôn cố gắng tìm những thuật toán đa thức. 6
  9. Ch­¬ng 1: NhËp m«n mËt m· häc 1.4. LÝ THUYẾT THÔNG TIN TRONG CÁC HỆ MẬT 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ã. Trong chương này ta sẽ thảo luận một vài ý tưởng trong lý thuyết của Shannon. 1.4.1. Độ mật hoàn thiện. Có hai quan điểm cơ bản về độ an toàn của một hệ mật. 1.4.1.1. Độ an toàn tính toán Độ đo này liên quan đến những nỗ lực tính toán cần thiết để phá một hệ mật. Một hệ mật là an toàn về mặt tính toán nếu một thuật toán tốt nhất để phá nó cần ít nhất N phép toán, N là số rất lớn nào đó. Vấn đề là ở chỗ, không có một hệ mật thực tế đã biết nào có thể được chứng tỏ là an toàn theo định nghĩa này. Trên thực tế, người ta gọi một hệ mật là "an toàn về mặt tính toán" nếu có một phương pháp tốt nhất phá hệ này nhưng yêu cầu thời gian lớn đến mức không chấp nhận được. (Điều này tất nhiên là rất khác với việc chứng minh về độ an toàn). Một quan điểm chứng minh về độ an toàn tính toán là quy độ an toàn của một hệ mật về một bài toán đã được nghiên cứu kỹ và bài toán này được coi là khó. Ví dụ, ta có thể chứng minh một khẳng định có dạng. “Một hệ mật đã cho là an toàn nếu không thể phân tích ra thừa số một số nguyên n cho trước". Các hệ mật loại này đôi khi gọi là “An toàn chứng minh được". Tuy nhiên cần phải hiểu rằng, quan điểm này chỉ cung cấp một chứng minh về độ an toàn có liên quan để một bài toán khác chứ không phải là một chứng minh hoàn chỉnh về độ an toàn. (Tình hình này cũng tương tự như việc chứng minh một bài toán là NP đầy đủ: Có thể chứng tỏ bài toán đã cho chí ít cũng khó như một bài toán NP đầy đủ khác, song không phải là một chứng minh hoàn chỉnh về độ khó tính toán của bài toán). 1.4.1.2. Độ an toàn không điều kiện Độ đo này liên quan đến độ an toàn của các hệ mật khi không có một hạn chế nào được đặt ra về khối lượng tính toánPTIT mà Oscar được phép thực hiện. Một hệ mật được gọi là an toàn không điều kiện nếu nó không thể bị phá thậm chí với khả năng tính toán không hạn chế. Khi thảo luận về độ an toàn của một hệ mật, ta cũng phải chỉ ra kiểu tấn công đang được xem xét. Trong chương ta thấy rằng, không một hệ mật nào trong các hệ mã dịch vòng, mã thay thế và mã Vigenère được coi là an toàn về mặt tính toán với phương pháp tấn công chỉ với bản mã (Với khối lượng bản mã thích hợp). Điều mà ta sẽ làm trong phần này là để phát triển lý thuyết về các hệ mật có độ an toàn không điều kiện với phương pháp tấn công chỉ với bản mã. Có thể thấy rằng, cả ba hệ mật nêu trên đều là các hệ mật an toàn vô điều kiện chỉ khi mỗi phần tử của bản rõ được mã hoá bằng một khoá cho trước. Rõ ràng là độ an toàn không điều kiện của một hệ mật không thể được nghiên cứu theo quan điểm độ phức tạp tính toán vì thời gian tính toán cho phép không hạn chế. Ở đây lý 7
  10. Ch­¬ng 1: NhËp m«n mËt m· häc thuyết xác suất là nền tảng thích hợp để nghiên cứu về độ an toàn không điều kiện. Tuy nhiên ta chỉ cần một số kiến thức sơ đẳng trong xác suất; các định nghĩa chính sẽ được nêu dưới đây. Định nghĩa 1.4: Giả sử X và Y là các biến ngẫu nhiên. Kí hiệu xác suất để X nhận giá trị x là p(x) và để Y nhận giá trị y là p y . Xác suất đồng thời p x,y là xác suất để X nhận giá trị x và Y nhận giá trị y. Xác suất có điều kiện p x y là xác suất để X nhận giá trị x với điều kiện Y nhận giá trị y. Các biến ngẫu nhiên X và Y được gọi là độc lập nếu p x,y p x p y với mọi giá trị có thể x của X và y của Y. Quan hệ giữa xác suất đồng thời và xác suất có điều kiện được biểu thị theo công thức: p x,y p x y p y (1.1) Đổi chỗ x và y ta có: p x,y p y x p x (1.2) Từ hai biểu thức trên ta có thể rút ra kết quả sau:(được gọi là định lý Bayes) Định lý 1.1: (Định lý Bayes) Nếu p y 0 thì: p x p y x p x y (1.3) p y Hệ quả 1.1. x và y là các biến độc lập khi và chỉ khi: p x y p x , x,y . Trong phần này ta giả sử rằng, một khoá cụ thể chỉ dùng cho một bản mã. Giả sử có một phân bố xác suất trên không PTITgian bản rõ P . Kí hiệu xác suất tiên nghiệm để bản rõ xuất hiện là pP (x) . Cũng giả sử rằng, khóa K được chọn (bởi Alice và Bob) theo một phân bố xác suất xác định nào đó. (Thông thường khoá được chọn ngẫu nhiên, bởi vậy tất cả các khoá sẽ đồng khả năng, tuy nhiên đây không phải là điều bắt buộc). Kí hiệu xác suất để khóa K được chọn là pK (K ) . Cần nhớ rằng khóa được chọn trước khi Alice biết bản rõ. Bởi vậy có thể giả định rằng khoá K và bản rõ x là các sự kiện độc lập. Hai phân bố xác suất trên P và K sẽ tạo ra một phân bố xác suất trên C . Thật vậy, có thể dễ dàng tính được xác suất pP (y) với y là bản mã được gửi đi. Với một khoá K K , ta xác định: C K eK x :x P  Ở đây C(K ) biểu thị tập các bản mã có thể nếu K là khóa. Khi đó với mỗi y C , ta có: 8
  11. Ch­¬ng 1: NhËp m«n mËt m· häc pC y  pK K pP dK y (1.4) K :y C K  Nhận thấy rằng, với bất kì y C và x P , có thể tính được xác suất có điều kiện pC y x . (Tức là xác suất để y là bản mã với điều kiện bản rõ là x ): pC y x  pK K (1.5) K :x dK y  Bây giờ ta có thể tính được xác suất có điều kiện pP x y (tức xác suất để x là bản rõ với điều kiện y là bản mã) bằng cách dùng định lý Bayes. Ta thu được công thức sau: pP x  pK K K :x dK y  pP y x (1.6)  pK K pP dK y K :y c K  Các phép tính này có thể thực hiện được nếu biết được các phân bố xác suất. Sau đây sẽ trình bày một ví dụ đơn giản để minh hoạ việc tính toán các phân bố xác suất này. Ví dụ 1.2. Giả sử P a,b với pP a 1 4 , pP b 3 4 . Cho K K 1,K 2 ,K 3 với pK K 1 1 2 , pK K 2 pK K 3 1 4. Giả sử C 1,2,3,4 và các hàm mã được xác định là e (a) 1,e (b) 2,  K 1 K 1 e (a) 2, e (b) 3,e (a) 3, e (b) 4 . Hệ mật này được biểu thị bằng ma trận mã hoá K 2 K 2 K 3 K 3 sau: a b K 1 2 PTIT1 K 2 2 3 K 3 2 4 Tính phân bố xác suất pC ta có: pC (1) 1 8 p (2) 3 8 1 16 7 16 C pC (3) 3 16 1 16 1 4 pC (4) 3 16 Bây giờ ta đã có thể các phân bố xác suất có điều kiện trên bản rõ với điều kiện đã biết bản mã. Ta có: 9
  12. Ch­¬ng 1: NhËp m«n mËt m· häc p a |1 1 p b |1 0 p a | 2 1 7 p b | 2 6 7 P P P P pP a | 3 1 4 pP b | 3 3 4 pP a | 4 0 pP b | 4 1 Bây giờ ta đã có đủ điều kiện để xác định khái niệm về độ mật hoàn thiện. Một cách không hình thức, độ mật hoàn thiện có nghĩa là Oscar với bản mã trong tay không thể thu được thông tin gì về bản rõ. Ý tưởng này sẽ được làm chính xác bằng cách phát biểu nó theo các thuật ngữ của các phân bố xác suất định nghĩa ở trên như sau: Định nghĩa 1.5: Một hệ mật có độ mật hoàn thiện nếu pP x y pP x với mọix P , y C . Tức xác suất hậu nghiệm để bản rõ là x với điều kiện đã thu được bản mã y là đồng nhất với xác suất tiên nghiệm để bản rõ là x . Trong ví dụ trên chỉ có bản mã 3 mới thoả mãn tính chất độ mật hoàn thiện, các bản mã khác không có tính chất này. Sau đây sẽ chứng tỏ rằng, mã dịch vòng (MDV - xem chương 2) có độ mật hoàn thiện. Về mặt trực giác, điều này dường như quá hiển nhiên. Với mã dịch vòng, nếu đã biết một phần tử bất kỳ của bản mã y Z 26 , thì một phần tử bất kỳ của bản rõ x Z 26 cũng có thể là bản mã đã giải của y tuỳ thuộc vào giá trị của khoá. Định lý sau cho một khẳng định hình thức hoá và được chứng minh theo các phân bố xác suất. Định lý 1.2: Giả sử 26 khoá trong MDV có xác suất như nhau và bằng1/26. Khi đó MDV sẽ có độ mật hoàn thiện với mọi phân bố xác suất của bản rõ. Chứng minh: Ta có P C K Z 26 và với 0 K 25 , quy tắc mã hoá eK là eK x x K mod 26 (x Z 26 ). Trước tiên tính phân bố pC . Giả sử y Z 26 , khi đó: pC y  pK K pP dK y K Z 26 1 26p y K (1.7) PTIT P K Z 26 1 26  pP y K K Z 26 Xét thấy với y cố định, các giá trị y K mod 26 sẽ tạo thành một hoán vị của Z 26 và pP là một phân bố xác suất. Bởi vậy ta có:  pP y K  pP y 1 K Z 26 K Z 26 Do đó: pC y 1 26 với bất kỳ y Z 26 . Tiếp theo ta có: 10
  13. Ch­¬ng 1: NhËp m«n mËt m· häc pC y x pK y x mod 26 1 26 Với mọi x ,y vì với mỗi cặp x,y khóa duy nhất K (khoá đảm bảo eK (x ) y ) là khoá K y x mod 26. Bây giờ sử dụng định lý Bayes, ta có thể dễ dàng tính: pP x pC y x pC x y pC y p x . 1 26 P 1 26 pP x Bởi vậy, MDV có độ mật hoàn thiện. Như vậy, mã dịch vòng là hệ mật không phá được miễn là chỉ dùng một khoá ngẫu nhiên đồng xác suất để mã hoá mỗi ký tự của bản rõ. Sau đây sẽ nghiên cứu độ mật hoàn thiện trong trường hợp chung. Trước tiên thấy rằng, (sử dụng định lý Bayes) điều kiện để pP x | y pP x với mọi x P, y P là tương đương với pC y | x pC y với mọi x P, y P . Giả sử rằng pC (y) 0 với mọi y C pC (y) 0 thì bản mã sẽ không được dùng và có thể loại khỏi C ). Cố định một giá trị nào đó x P . Với mỗi y C ta có pC y | x pC y 0. Bởi vậy, với mỗi y C phải có ít nhất một khoá K và một x sao cho eK (x ) y . Điều này dẫn đến K C . Trong một hệ mật bất kỳ ta phải có C P vì mỗi quy tắc mã hoá là một đơn ánh. Trong trường hợp giới hạn, K C P , ta có định lý sau (Theo Shannon). Định lý 1.3: Giả sử P,C,K,E,D làPTIT một hệ mật , trong đó K C P . Khi đó, hệ mật có độ mật hoàn thiện khi và chỉ khi khoá K được dùng với xác suất như nhau bằng 1 K , và với mỗi x P , mỗi y C có một khoá duy nhất K sao cho eK (x ) y . Chứng minh Giả sử hệ mật đã cho có độ mật hoàn thiện. Như đã thấy ở trên, với mỗi x P và y C , phải có ít nhất một khoá K sao cho eK (x ) y . Bởi vậy ta có bất đẳng thức: C eK x :K K  K Tuy nhiên, ta giả sử rằng C K , bởi vậy ta phải có: eK x :K C K 11
  14. Ch­¬ng 1: NhËp m«n mËt m· häc Tức là ở đây không tồn tại hai khoá K và K khác nhau để e (x ) e (x ) y . Như 1 2 K 1 K 2 vậy ta đã chứng tỏ được rằng, với bất kỳ x P và y C có đúng một khoá K để eK (x ) y . Ký hiệu n K . Giả sử P xi :1 i n và cố định một giá trị y C Ta có thể ký hiệu các khoá K ,K , ,K sao cho e (x ) y , 1 i n . Sử dụng định lý Bayes ta có: 1 2 n K i i i pC y x i pP xi pP x i y p y C pK K i . pP x i pC y Xét điều kiện độ mật hoàn thiện pP x i y pP x i . Điều kiện này kéo theo pK K i pC y với 1 i n . Tức là khoá được dùng với xác suất như nhau (chính bằng pC (y) ). Tuy nhiên vì số khoá là n K nên ta có pK (K ) 1 K với mỗi K K . Ngược lại, giả sử hai điều giả định đều thoả mãn. Khi đó dễ dàng thấy được hệ mật có độ mật hoàn thiện với mọi phân bố xác suất bất kỳ của bản rõ (tương tự như chứng minh định lý 2.3). Các chi tiết dành cho bạn đọc xem xét. Mật mã khoá sử dụng một lần của Vernam (One-Time-Pad: OTP) là một ví dụ quen thuộc về hệ mật có độ mật hoàn thiện. Gillbert Vernam lần đầu tiên mô tả hệ mật này vào năm 1917. Hệ OTP dùng để mã và giải mã tự động các bản tin điện báo. Điều thú vị là trong nhiều năm OTP được coi là một hệ mật không thể bị phá nhưng không thể chứng minh cho tới khi Shannon xây dựng được khái niệm về độ mật hoàn thiện hơn 30 năm sau đó. Mô tả về hệ mật dùng một lần nêu trên hình 1.2. n n Giả sử n 1 là số nguyên và P C K Z 2 . Với K Z 2 , ta xác định eK (x) là tổng vector theo modulo 2 của K và x (hay tương đương với phép hoặc loại trừ của hai dãy bit tương ứng). Như vậy, nếu x x , ,x và K K , ,K thì: PTIT1 n 1 n eK (x ) x1 K 1, ,xn K n mod 2 Phép mã hoá là đồng nhất với phép giải mã. Nếu y y1, ,yn thì: dK (x ) y1 K 1, ,yn K n mod 2 Hình 1.2. Hệ mật sử dụng khoá một lần (OTP) Sử dụng định lý 2.4, dễ dàng thấy rằng OTP có độ mật hoàn thiện. Hệ thống này rất hấp dẫn do dễ thực hiện mã và giải mã. Vernam đã đăng ký phát minh của mình với hy vọng rằng nó sẽ có ứng dụng thương mại rộng rãi. Đáng tiếc là có những nhược điểm quan trọng đối với các hệ mật an toàn không điều kiện, chẳng hạn như OTP. Điều kiện K P có nghĩa là lượng khóa (cần được thông 12
  15. Ch­¬ng 1: NhËp m«n mËt m· häc báo một cách bí mật) cũng lớn như bản rõ. Ví dụ , trong trường hợp hệ OTP, ta cần n bit khoá để mã hoá n bit của bản rõ. Vấn đề này sẽ không quan trọng nếu có thể dùng cùng một khoá để mã hoá các bản tin khác nhau; tuy nhiên, độ an toàn của các hệ mật an toàn không điều kiện lại phụ thuộc vào một thực tế là mỗi khoá chỉ được dùng cho một lần mã. Ví dụ OTP không thể đứng vững trước tấn công chỉ với bản rõ đã biết vì ta có thể tính được K bằng phép hoặc loại trừ xâu bit bất kỳ x và eK (x). Bởi vậy, cần phải tạo một khóa mới và thông báo nó trên một kênh bảo mật đối với mỗi bản tin trước khi gửi đi. Điều này tạo ra khó khăn cho vấn đề quản lý khoá và gây hạn chế cho việc sử dụng rộng rãi OTP. Tuy nhiên OTP vẫn được áp dụng trong lĩnh vực quân sự và ngoại giao, ở những lĩnh vực này độ an toàn không điều kiện có tầm quan trọng rất lớn. Lịch sử phát triển của mật mã học là quá trình cố gắng tạo các hệ mật có thể dùng một khoá để tạo một xâu bản mã tương đối dài (tức có thể dùng một khoá để mã nhiều bản tin) nhưng chí ít vẫn còn giữ được độ an toàn tính toán. Chuẩn mã dữ liệu (DES) là một hệ mật thuộc loại này. 1.4.2. Entropy Trong phần trước ta đã thảo luận về khái niệm độ mật hoàn thiện và đặt mối quan tâm vào một trường hợp đặc biệt, khi một khoá chỉ được dùng cho một lần mã. Bây giờ ta sẽ xét điều sẽ xẩy ra khi có nhiều bản rõ được mã bằng cùng một khoá và bằng cách nào mà thám mã có thể thực hiện có kết quả phép tấn công chỉ với bản mã trong thời gian đủ lớn. Công cụ cơ bản trong nghiên cứu bài toán này là khái niệm Entropy. Đây là khái niệm trong lý thuyết thông tin do Shannon đưa ra vào năm 1948. Có thể coi Entropy là đại lượng đo thông tin hay còn gọi là độ bất định. Nó được tính như một hàm của phân bố xác suất. Giả sử ta có một biến ngẫu nhiên X nhận các giá trị trên một tập hữu hạn theo một phân bố xác suất p(X ) . Thông tin thu nhận được bởi một sự kiện xảy ra tuân theo một phân bố p(X ) là gì? Tương tự, nếu sự kiện còn chưa xảy ra thì cái gì là độ bất định và kết quả bằng bao nhiêu? Đại lượng này được gọi là Entropy của X và được kí hiệu là H (X ) . Các ý tưởng này có vẻ như khá trừu tượng, bởi vậy ta sẽ xét một ví dụ cụ thể hơn. Giả sử biến ngẫu nhiên X biểu thPTITị phép tung đồng xu. Phân bố xác suất là: p(mặt xấp) = p(mặt ngửa) = 1/2. Có thể nói rằng, thông tin (hay Entropy) của phép tung đồng xu là một bit vì ta có thể mã hoá mặt xấp bằng 1 và mặt ngửa bằng 0. Tương tự Entropy của n phép tung đồng tiền có thể mã hoá bằng một xâu bit có độ dài n . Xét một ví dụ phức tạp hơn một chút. Giả sử ta có một biến ngẫu nhiên X có 3 giá trị có thể là x1,x 2 ,x 3 với các xác suất tương ứng bằng 1/2, 1/4, 1/4. Cách mã hiệu quả nhất của 3 biến cố này là mã hoá x1 là 0, mã của x 2 là 10 và mã của x 3 là 11. Khi đó số bit trung bình trong phép mã hoá này là: 1/2 1 +1/4 2 + 1/4 2 = 3/2. Các ví dụ trên cho thấy rằng, một biến cố xảy ra với xác suất 2 n có thể mã hoá được bằng một xâu bit có độ dài n . Tổng quát hơn, có thể coi rằng, một biến cố xảy ra với xác suất 13
  16. Ch­¬ng 1: NhËp m«n mËt m· häc p có thể mã hoá bằng một xâu bit có độ dài xấp xỉ log2 p . Nếu cho trước phân bố xác suất tuỳ ý p1,p2 , ,pn của biến ngẫu nhiên X, khi đó độ đo thông tin là trọng số trung bình của các lượng log2 pi . Điều này dẫn tới định nghĩa hình thức hoá sau. Định nghĩa 1.6: Giả sử X là một biến ngẫu nhiên lấy các giá trị trên một tập hữu hạn theo phân bố xác suất p(X). Khi đó entropy của phân bố xác suất này được định nghĩa là lượng: n H X pi log2 Pi (1.8) i 1 Nếu các giá trị có thể của X là xi , 1 i n thì ta có: n H X p X x i log2 P X xi (1.9) i 1 Nhận xét: Nhận thấy rằng log2 pi không xác định nếu pi 0 . Bởi vậy đôi khi entropy được định nghĩa là tổng tương ứng trên tất cả các xác suất khác 0. Vì limx log2 x 0 nên trên thực tế x 0 cũng không có trở ngại gì nếu cho pi 0 với giá trị i nào đó. Tuy nhiên ta sẽ tuân theo giả định là khi tính entropy của một phân bố xác suất pi , tổng trên sẽ được lấy trên các chỉ số i sao cho pi 0 . Ta cũng thấy rằng việc chọn cơ số của logarit là tuỳ ý; cơ số này không nhất thiết phải là 2. Một cơ số khác sẽ chỉ làm thay đổi giá trị của entropy đi một hằng số. Chú ý rằng, nếu pi 1 n với 1 i n thì H (X ) log2 n . Cũng dễ dàng thấy rằng H (X ) 0 và H (X ) 0 khi và chỉ khi pi 1 với một giá trị i nào đó và pj 0 với mọi j i . Xét entropy của các thành phần khác nhau của một hệ mật. Ta có thể coi khoá là một biến ngẫu nhiên K nhận các giá trị tuân theo phân bố xác suất pK và bởi vậy có thể tính được H (K ) . Tương tự ta có thể PTITtính các entropy H (P ) và H (C ) theo các phân bố xác suất tương ứng của bản mã và bản rõ. Ví dụ 1.2: (tiếp) Ta có: H P 1 4log2 1 4 3 4log2 3 4 1 4 2 3 4 log 3 2 2 2 3 4log2 3 0,81 bằng các tính toán tương tự, ta có H (K ) 1,5 và H (C ) 1,85. 14
  17. Ch­¬ng 1: NhËp m«n mËt m· häc 1.4.2.1. Các tính chất của Entropy Trong phần này sẽ chứng minh một số kết quả quan trọng liên quan đến Entropy. Trước tiên ta sẽ phát biểu bất đẳng thức Jensen. Đây là một kết quả cơ bản và rất hữu ích. Bất đẳng thức Jensen có liên quan đến hàm lồi có định nghĩa như sau. Định nghĩa 1.7: Một hàm có giá trị thực f là lồi trên khoảng I nếu: x y f (x ) f (y) f (1.10) 2 2 với mọi x,y I . f là hàm lồi thực sự trên khoảng I nếu: x y f (x ) f (y) f (1.11) 2 2 với mọi x,y I , x y . Sau đây ta sẽ phát biểu mà không chứng minh bất đẳng thức Jensen. Định lý 1.4: (Bất đẳng thức Jensen). Giả sử h là một hàm lồi thực sự và liên tục trên khoảng l, n ai 1 i 1 và ai 0; 1 i n Khi đó: n n ai f (xi ) f aixi (1.12) i 1 i 1 trong đó x i I ; 1 i n . Ngoài ra dấu "=" chỉ xảy ra khi và chỉ khi x1 x 2 xn Bây giờ ta sẽ đưa ra một số kết quả về Entropy. Trong định lý sau sẽ sử dụng khẳng định: hàm log x là một hàm lồi thực sự trong khoảng (0, ) (Điều này dễ dàng thấy được từ 2 PTIT những tính toán sơ cấp vì đạo hàm cấp 2 của hàm logarith là âm trên khoảng (0, )). Định lý 1.5: Giả sử X là biến ngẫu nhiên có phân bố xác suất p1,p2 , , pn trong đó pi 0; 1 i n . Khi đó H (X ) log2 n . Dấu "=" xảy ra khi và chỉ khi pi 1 n , 1 i n Chứng minh: Áp dụng bất đẳng thức Jensen, ta có: 15
  18. Ch­¬ng 1: NhËp m«n mËt m· häc n n H (X ) pi log2 pi pi log2 (1/ pi ) i 1 i 1 n log2 (pi 1/ pi ) i 1 log2 n Ngoài ra, dấu "=" chỉ xảy ra khi và chỉ khi pi 1 n , 1 i n . Định lý 1.6: H X ,Y H X H Y (1.13) Đẳng thức (dấu "=") xảy ra khi và chỉ khi X và Y là các biến cố độc lập Chứng minh. Giả sử X nhận các giá trị xi , 1 i m ; Y nhận các giá trị y j , 1 j n . Kí hiệu: pi p X xi ,1 i m và qi p Y y j ,1 j n . Kí hiệu rij p X xi ,Y y j , 1 i m , 1 j n . (Đây là phân bố xác suất hợp). Nhận thấy rằng n pi rij ; 1 i m j 1 m và qj rij ; 1 j n i 1 Ta có m n H (X ) H (Y ) (pi log2 pi qj log2 qj ) i 1 j 1 m n n m (rij log2 pi rij log2 qj ) PTITi 1 j 1 j 1 i 1 m n rij log2 piqj i 1 j 1 m n Mặt khác: H (X ,Y ) rij log2 rij i 1 j 1 Kết hợp lại ta thu được kết quả sau: 16
  19. Ch­¬ng 1: NhËp m«n mËt m· häc m n m n H (X ,Y ) H (X ) H (Y ) rij log2 (1/ rij ) rij log2 piqj i 1 j 1 i 1 j 1 m n log2 piqj i 1 j 1 log2 1 0 (Ở đây đã áp dụng bất đẳng thức Jensen khi biết rằng các rij tạo nên một phân bố xác suất ). Khi đẳng thức xảy ra, có thể thấy rằng phải có một hằng số c sao cho pij rij c với mọi i, j . Sử dụng đẳng thức sau: m n rij log2 (piqj / rij ) i 1 j 1 n m n m rij piqj 1 j 1 i 1 j 1 i 1 Điều này dẫn đến c 1. Bởi vậy đẳng thức (dấu "=") sẽ xảy ra khi và chỉ khi rij pjqj , nghĩa là: p X x j ,Y y j p X x j p Y y j với 1 i m ,1 j n . Điều này có nghĩa là X và Y độc lập. Tiếp theo ta sẽ đưa ra khái niệm Entropy có điều kiện Định nghĩa 1.8: Giả sử X và Y là hai biến ngẫu nhiên. Khi đó với giá trị xác định bất kỳ y của Y, ta có một phân bố xác suất có điều kiện p X |y . Rõ ràng là: H (X | y) p(x | y)log p(x | y) (1.14) PTIT 2 x Ta định nghĩa Entropy có điều kiện H(X|Y) là trung bình có trọng số (ứng với các xác suất p(y) ) của Entropy H(X|y) trên mọi giá trị có thể y. H(X|y) được tính bằng: H (X |Y )  p(y)p(x | y)log2 p(x | y) (1.15) y x Entropy có điều kiện đo lượng thông tin trung bình về X do Y mang lại. Sau đây là hai kết quả trực tiếp ( Bạn đọc có thể tự chứng minh) Định lý 1.7: H X ,Y H Y H X |Y (1.16) 17
  20. Ch­¬ng 1: NhËp m«n mËt m· häc Hệ quả 1.2. H X |Y H X Dấu bằng chỉ xảy ra khi và chỉ khi X và Y độc lập. 1.4.2.2. Các khoá giả và khoảng duy nhất Trong phần này chúng ta sẽ áp dụng các kết quả về Entropy ở trên cho các hệ mật. Trước tiên sẽ chỉ ra một quan hệ cơ bản giữa các Entropy của các thành phần trong hệ mật. Entropy có điều kiện H K |C được gọi là độ bất định về khoá. Nó cho ta biết về lượng thông tin về khoá thu được từ bản mã. Định lý 1.8: Giả sử P,C,K,E,D là một hệ mật. Khi đó: H K |C H K H P H C (1.17) Chứng minh: Trước tiên ta thấy rằng H K ,P ,C H C | K ,P H K ,P . Do y eK (x ) nên khoá và bản rõ sẽ xác định bản mã duy nhất. Điều này có nghĩa là H C K ,P 0 . Bởi vậy H K ,P ,C H K ,P . Nhưng K và P độc lập nên H K ,P H K H P . Vì thế: H K ,P ,C H K ,P H K H P Tương tự vì khoá và bản mã xác định duy nhất bản rõ (tức x dK (y) ) nên ta có H K ,P ,C 0 và bởi vậy H K ,P ,C H K ,P . Bây giờ ta sẽ tính như sau: H K C H K ,C H C H K ,P ,C H C PTIT H K H P H C Đây là nội dung của định lý. Ta sẽ quay lại ví dụ 2.1 để minh hoạ kết quả này. Ví dụ 1.1 (tiếp) Ta đã tính được H P 0,81, H K 1,5 và H C 1,85 . Theo định lý 1.8 ta có H K ,C 1,5 0,81 0,85 0,46 . Có thể kiểm tra lại kết quả này bằng cách áp dụng định nghĩa về Entropy có điều kiện như sau. Trước tiên cần phải tính các xác suất xuất p K j | j , 1 i 3; 1 j 4 . Để thực hiện điều này có thể áp dụng định lý Bayes và nhận được kết quả như sau: 18
  21. Ch­¬ng 1: NhËp m«n mËt m· häc p K 1 |1 1 p K 2 |1 0 p K 3 |1 0 p K 1 | 2 6 7 p K 2 | 2 6 7 p K 3 | 2 0 p K 1 | 3 0 p K 2 | 3 3 4 p K 3 | 3 1 4 p K 1 | 4 0 p K 2 | 4 0 p K 3 | 4 1 Bây giờ ta tính: H K |C 1/ 8 0 7 /16 0,59 1/ 4 0,81 3 /16 0 0,46 Giá trị này bằng giá trị được tính theo định lý 2.10. Giả sử P,C,K,E,D là hệ mật đang được sử dụng. Một xâu của bản rõ x1,x 2 , ,xn sẽ được mã hoá bằng một khoá để tạo ra bản mã y1,y 2 , ,yn . Nhớ lại rằng, mục đích cơ bản của thám mã là phải xác định được khoá. Ta xem xét các phương pháp tấn công chỉ với bản mã và coi Oscar có khả năng tính toán vô hạn. Ta cũng giả sử Oscar biết bản rõ là một văn bản theo ngôn ngữ tự nhiên (chẳng hạn văn bản tiếng Anh). Nói chung Oscar có khả năng rút ra một số khoá nhất định (các khoá có thể hay các khoá chấp nhận được) nhưng trong đó chỉ có một khoá đúng, các khoá có thể còn lại (các khoá không đúng) được gọi là các khoá giả. Ví dụ, giả sử Oscar thu được một xâu bản mã WNAJW mã bằng phương pháp mã dịch vòng. Dễ dàng thấy rằng, chỉ có hai xâu bản rõ có ý nghĩa là river và arena tương ứng với các khoá F(= 5) và W(= 22). Trong hai khoá này chỉ có một khoá đúng, khoá còn lại là khoá giả. (Trên thực tế, việc tìm một bản mã của MDV có độ dài 5 và 2 bản giải mã có nghĩa không phải quá khó khăn, bạn đọc có thể tìm ra nhiều ví dụ khác). Mục đích của ta là phải tìm ra giới hạn cho số trung bình các khoá giả. Trước tiên, phải xác định giá trị này theo Entropy (cho một kí tự) của một ngôn ngữ tự nhiên L (kí hiệu là HL). HL là lượng thông tin trung bình trên một kí tự trong một xâu có nghĩa của bản rõ. (Chú ý rằng, một xâu ngẫu nhiên các kí tự của bảng chữ cái sẽ có Entropy trên một kí tự bằng log2 26 4,76). Ta có thể lấy H(P) là xấp xỉ bậc nhất cho HL. Trong trườngPTIT hợp L là Anh ngữ, ta tính được H(P) 4,19. Dĩ nhiên các kí tự liên tiếp trong một ngôn ngữ không độc lập với nhau và sự tương quan giữa các kí tự liên tiếp sẽ làm giảm Entropy. Ví dụ, trong Anh ngữ, chữ Q luôn kéo theo sau là chữ U. Để làm xấp xỉ bậc hai, tính Entropy của phân bố xác suất của tất cả các bộ đôi rồi chia cho 2. Một cách tổng quát, ta định nghĩa Pn là biến ngẫu nhiên có phân bố xác suất của tất cả các bộ n của bản rõ. Ta sẽ sử dụng tất cả các định nghĩa sau: Định nghĩa 1.9: Giả sử L là một ngôn ngữ tự nhiên. Entropy của L được xác định là lượng sau: H (P n ) H L lim (1.18) n n Độ dư của L là: RL 1 H L log2 P (1.19) 19
  22. Ch­¬ng 1: NhËp m«n mËt m· häc Nhận xét: HL đo Entropy trên mỗi kí tự của ngôn ngữ L. Một ngôn ngữ ngẫu nhiên sẽ có Entropy là log2 P . Bởi vậy đại lượng RL đo phần "kí tự vượt trội" là phần dư. Trong trường hợp Anh ngữ, dựa trên bảng chứa một số lớn các bộ đôi và các tần số, ta có thể tính được H (P 2 ) . Ước lượng theo cách này, ta tính được H (P 2 ) 3,90 . Cứ tiếp tục như vậy bằng cách lập bảng các bộ ba v.v ta thu được ước lượng cho HL. Trên thực tế, bằng nhiều thực nghiệm khác nhau, ta có thể đi tới kết quả sau 1,0 H L 1,5. Tức là lượng thông tin trung bình trong tiếng Anh vào khoảng 1 bit tới 1,5 bit trên mỗi kí tự. Giả sử lấy 1,25 là giá trị ước lượng của giá trị của HL. Khi đó độ dư vào khoảng 0,75. Tức là tiếng Anh có độ dư vào khoảng 75%! (Điều này không có nghĩa loại bỏ tuỳ ý 3 trên 4 kí tự của một văn bản tiếng Anh mà vẫn có khả năng đọc được nó. Nó chỉ có nghĩa là tìm được một phép mã Huffman cho các bộ n với n đủ lớn, phép mã này sẽ nén văn bản tiếng Anh xuống còn 1/4 độ dài của bản gốc). Với các phân bố xác suất C n đã cho trên K và P n . Có thể xác định phân bố xác suất trên là tập các bộ n của bản mã. (Ta đã làm điều này trong trường hợp n 1). Ta đã xác định P n là biến ngẫu nhiên biểu diễn bộ n của bản rõ. Tương tự C n là biến ngẫu nhiên biểu thị bộ n của bản mã. n n Với y C , định nghĩa: K y K K; x P ,p n 0,e x y nghĩa là P x K  K (y) là tập các khoá K sao cho y là bản mã của một xâu bản rõ độ dài n có nghĩa, tức là tập các khoá "có thể" với y là bản mã đã cho. Nếu y là dãy quan sát được của bản mã thì số khoá giả sẽ là K y 0 1vì chỉ có một khoá là khoá đúng trong số các khoá có thể. Số trung bình các khoá giả (trên tất cả các xâu bản mã có thể độ dài n ) được kí hiệu là sn và nó được tính như sau: sn  p y K y 1 y C n  p y K y  p y PTITy C n y C n  p y K y 1 y C n Từ định lý 1.8 ta có: H K C n H K H P n H C n Có thể dùng ước lượng sau: n H P nH L n 1 RL log2 P với điều kiện n đủ lớn. Hiển nhiên là: n H C n log2 C 20
  23. Ch­¬ng 1: NhËp m«n mËt m· häc Khi đó nếu P C thì: n H K C H K nRL log2 P (1.20) n Tiếp theo xét quan hệ của lượng H (K |C ) với số khoá giả sn . Ta có: H K C n  p y K y y C n  p y log2 K y n y C  p y K y y C n log2 sn 1 Ở đây ta áp dụng bất đẳng thức Jensen (định lý 1.5) với f (x ) log2 (x ) . Bởi vậy ta có bất đẳng thức sau: n H (K C ) log2 (sn 1) (1.21) Kết hợp hai bất đẳng thức (1.20) và (1.21), ta có: log2 (sn 1) H (K ) nRL log2 P Trong trường hợp các khoá được chọn đồng xác suất (Khi đó H (K ) có giá trị lớn nhất) ta có kết quả sau. Định lý 1.9: Giả sử P,C,K,E,D là một hệ mật trong đó C P và các khoá được chọn đồng xác suất. Giả sử RL là độ dư của ngôn ngữ gốc. Khi đó với một xâu bản mã độ dài n cho trước (n là số đủ lớn), số trung bình các khoá giả sn thoả mãn bất đẳng thức như sau: s K P nR 1 PTITn L  Lượng K P nRL 1 tiến tới 0 theo hàm mũ khi n tăng. Ước lượng này có thể không chính xác với các giá trị n nhỏ. Đó là do H (P n ) n không phải là một ước lượng tốt cho HL nếu n nhỏ. Ta đưa ra đây một khái niệm nữa Định nghĩa 1.10: Khoảng duy nhất của một hệ mật được định nghĩa là giá trị của n mà ứng với giá trị này, số khoá giả trung bình bằng 0 (kí hiệu giá trị này là n 0 ). Điều đó có nghĩa là n 0 là độ dài trung bình cần thiết của bản mã để thám mã có thể tính toán khoá một cách duy nhất với thời gian đủ lớn. 21
  24. Ch­¬ng 1: NhËp m«n mËt m· häc Nếu đặt sn 0 trong định lý 1.11 và giải theo n ta sẽ nhận được ước lượng cho khoảng duy nhất: n 0 log2 K RL log2 P Ví dụ với mã thay thế, ta có P 26 và K 26!. Nếu lấy RL 0,75 thì ta nhận được ước lượng cho khoảng duy nhất bằng: n 0 88,4 0,75 4,7 25 Điều đó có nghĩa là thông thường nếu mã thám có được xâu bản mã với độ dài tối thiểu là 25, anh ta có thể nhận được bản giải mã duy nhất. BÀI TẬP CHƯƠNG 1. Bài 1.1: Cho n là một số nguyên dương. Một hình vuông lớn latin cấp n (L) là một bảng n n các số nguyên 1, ,n sao cho mỗi một số trong n số nguyên này chỉ xuất hiện đúng một lần ở hàng và mỗi cột của L. Ví dụ hình vuông Latin cấp 3 có dạng: 1 2 3 3 1 2 2 3 1 Với một hình vuông Latin L bất kỳ cấp n , ta có thể xác định một hệ mã tương ứng. Giả sử P = C = K 1, ,n . Với 1 i n , quy tắc mã hóa e1 được xác định là e1 j L i, j (Do đó mỗi hàng của L sẽ cho một quy tắc mã hóa). Chứng minh rằng hệ mật hình vuông Latin này có độ mật hoàn thiện. Bài 1.2: Hãy chứng tỏ rằng mã Affine có độ mật hoàn thiện Bài 1.3: Giả sử một hệ mật đạt được độ hoàn thiện với phân bố xác suất p0 nào đó của bản rõ. Hãy chứng tỏ rằng độPTIT mật hoàn thiện vẫn còn giữ được đối với một phân bố xác suất bất kỳ của bản rõ. Bài 1.4: Hãy chứng tỏ rằng nếu một hệ mật có độ hoàn thiện và K C P thì mọi bản mã là đồng xác suất. Bài 1.5: Hãy chứng tỏ rằng H X ,Y H Y H X Y . Sau đó hãy chứng minh bổ đề là H X Y H X , đẳng thức chỉ xảy ra khi và chỉ khi X và Y độc lập. Bài 1.5: Chứng minh rằng một hệ mật có độ mật hoàn thiện khi và chỉ khi H P C H P . 22
  25. Ch­¬ng 1: NhËp m«n mËt m· häc Bài 1.6: Chứng minh rằng trong một hệ mật H K C H P C (về mặt trực giác kết quả này nói rằng với bản mã cho trước độ bất định của thám mã về khóa ít nhất cũng lớn bằng độ bất định khi thám mã rõ). Bài 1.7: Xét một hệ mật trong đó P a,b,c ,  K 1,K 2 ,K 3 và C 1,2,3,4 . Giả sử ma trận mã hóa như sau: a b c K 1 1 2 3 K 2 2 3 4 K 3 3 4 1 Giả sử các khóa được chọn đồng xác suất và phân bố xác suất của bản rõ là pP a 1/ 2, pP b 1/ 3, pP c 1/ 6. Hãy tính H (P ),H (C ), H (K ) , H K C và H P C . PTIT 23
  26. Lêi nãi ®Çu LỜI NÓI ĐẦU Trong sự phát triển của xã hội loài người, kể từ khi có sự trao đổi thông tin, an toàn thông tin trở thành một nhu cầu gắn liền với nó như hình với bóng. Từ thủa sơ khai, an toàn thông tin được hiểu đơn giản là giữ được bí mật và điều này được xem như một nghệ thuật chứ chưa phải là một ngành khoa học. Với sự phát triển của khoa học kỹ thuật và công nghệ, cùng với các nhu cầu đặc biệt có liên quan tới an toàn thông tin, ngày nay các kỹ thuật chính trong an toàn thông tin bao gồm: - Kỹ thuật mật mã (Cryptography) - Kỹ thuật ngụy trang (mã ẩn) (Steganography) - Kỹ thuật tạo bóng mờ, thủy vân số (Watermarking) Kỹ thuật mật mã nhằm đảm bảo ba dịch vụ an toàn cơ bản: - Bí mật (Confidential) - Xác thực (Authentication) - Đảm bảo tính toàn vẹn (Intergrity) Có thể thấy rằng mật mã học là một lĩnh vực khoa học rộng lớn có liên quan rất nhiều ngành toán học như: Đại số tuyến tính, Lý thuyết thông tin, Lý thuyết độ phức tạp tính toán Bởi vậy việc trình bày đầy đủ mọi khía cạnh của mật mã học trong khuôn khổ một giáo trình là một điều khó có thể làm được. Chính vì lý do đó, trong giáo trình này chúng tôi chỉ dừng ở mức mô tả ngắn gọn các thuật toán mật mã chủ yếu. Các thuật toán này hoặc đang được sử dụng trong các chương trình ứng dụng hiện nay hoặc không còn được dùng nữa, nhưng vẫn được xem như là một ví dụ hay, cho ta hình dung rõ hơn bức tranh tổng thể về sự phát triển của mật mã học cả trên phương diện lý thuyết và ứng dụng. Còn một nội dung rất lý thú chưa được nêu trong giáo trình này là vấn đề thám mã. Bạn đọc PTITquan tâm có thể tham khảo thêm trong các tài liệu [1], [2], [3]. Nội dung giáo trình bao gồm sáu chương: Chương I - Nhập môn mật mã học: Trình bày những khái niệm và sơ lược về mật mã học, độ phức tạp tính toán, và cơ sở lý thuyết thông tin trong các hệ mật. Chương II - Mật mã khóa bí mật: Trình bày các phương pháp xử lý thông tin của các hệ mật khóa bí mật (hệ mật khóa đối xứng) bao gồm các thuật toán hoán vị, thay thế và chuẩn mã dữ liệu của Mỹ (DES) và AES. Chương III - Mật mã khóa công khai: Trình bày một số bài toán một chiều và các thuật toán mật mã khóa công khai (hay mật mã khoá bất đối xứng) liên quan bao i
  27. Lêi nãi ®Çu gồm: hệ mật RSA, Merkle-Hellman, Rabin, McEliece, hệ mật trên đường cong elliptic Chương IV - Hàm băm, xác thực và chữ ký số: Khái quát về hàm băm, một số vấn đề về xác thực, đảm bảo tính toàn vẹn và chữ ký số. Chương V - Các thủ tục và các chú ý trong thực tế khi sử dụng mã hóa Chương VI: Các chuẩn và áp dụng Sau mỗi chương đều có các câu hỏi và bài tập nhằm giúp cho bạn đọc nắm vững hơn các vấn đề đã được trình bày Phần phụ lục cung cấp chương trình nguồn của DES. Do thời gian và trình độ còn hạn chế, việc lựa chọn và trình bày các thuật toán này không thể tránh khỏi những khiếm khuyết nhất định. Rất mong bạn đọc đóng góp ý kiến về mặt cấu trúc, các nội dung được trình bày và các sai sót cụ thể. Các đóng góp ý kiến xin gửi về KHOA KỸ THUẬT ĐIỆN TỬ 1 - HỌC VIỆN CÔNG NGHỆ BƯU CHÍNH VIỄN THÔNG KM 10. ĐƯỜNG NGUYỄN TRÃI - HÀ ĐÔNG Email: KhoaDT1@hn.vnn.vn Hoặc: nguyenbinh1999@yahoo.com Xin chân thành cảm ơn! NGƯỜI BIÊN SOẠN PTIT ii
  28. 2.8.2. Mô tả DES 53 2.8.3. Một số ý kiến thảo luận về DES 64 2.8.4. DES trong thực tế 65 2.8.5. Chuẩn mã dữ liệu tiên tiến (AES) 68 2.9. ƯU VÀ NHƯỢC ĐIỂM CỦA MẬT MÃ KHÓA BÍ MẬT 72 2.9.1. Ưu điểm 72 2.9.2. Nhược điểm 72 BÀI TẬP CHƯƠNG 2 73 CHƯƠNG 3. MẬT MÃ KHOÁ CÔNG KHAI 78 3.1. SỐ HỌC MODULO 78 3.1.1. Số nguyên 78 3.1.2. Các thuật toán trong 80 3.1.3. Các số nguyên modulo n 82 3.1.4. Các thuật toán trong 88 3.1.5. Các ký hiệu Legendre và Jacobi 89 3.1.6. Các số nguyên Blum 94 3.1.7. Ví dụ (Số nguyên Blum) 94 3.2. GIỚI THIỆU VỀ MẬT MÃ KHOÁ CÔNG KHAI 95 3.3. SƠ ĐỒ CHỨC NĂNG CỦA HỆ MẬT KHÓA CÔNG KHAI 96 3.4. BÀI TOÁN LOGARIT RỜI RẠC VÀ CÁC HỆ MẬT LIÊN QUAN 97 3.4.1. Bài toán logarit rời rạc 97 3.4.2. Một số hệ mật xây dựng trên bài toán logarit rời rạc 100 3.5. BÀI TOÁN PHÂNPTIT TÍCH THỪA SỐ VÀ HỆ MẬT RSA 105 3.5.1. Bài toán phân tích thừa số 105 3.5.2. Hệ mật RSA (Rivest – Shamir – Adleman) 105 3.5.3. Vấn đề điểm bất động trong RSA 109 3.5.4. Hệ mật Rabin 110 3.6. BÀI TOÁN XẾP BA LÔ VÀ HỆ MẬT MERKLE – HELLMAN 112 3.6.1. Bài toán xếp ba lô 112 3.6.2. Hệ mật Merkle - Hellman 113 3.6.3. Hệ mật Chor-Rivest (CR) 116 3.7. BÀI TOÁN MÃ SỬA SAI VÀ HỆ MẬT McELIECE 120 iv
  29. 3.7.1. Bài toán mã sửa sai 120 3.7.2. Hệ mật McEliece 122 3.8. ĐƯỜNG CONG ELLIPTIC VÀ CÁC HỆ MẬT LIÊN QUAN 125 3.8.1. Các đường cong Elliptic. 125 3.8.2. Các đường cong Elliptic trên trường Galois 126 3.8.3. Các phép toán cộng và nhân trên các nhóm E 127 3.8.4. Các hệ mật trên đường cong elliptic 130 3.8.5. Độ an toàn của hệ mật trên đường cong Elliptic 133 3.9. ƯU VÀ NHƯỢC ĐIỂM CỦA MẬT MÃ KHÓA CÔNG KHAI 133 3.9.1. Ưu điểm 133 3.9.2. Nhược điểm 134 3.10. XÂY DỰNG CÁC CHƯƠNG TRÌNH ỨNG DỤNG KIẾN TRÚC PGP 134 BÀI TẬP CHƯƠNG 3 135 CHƯƠNG 4. HÀM BĂM, XÁC THỰC VÀ CHỮ KÝ SỐ 139 4.1. CÁC HÀM BĂM VÀ TÍNH TOÀN VẸN CỦA DỮ LIỆU 139 4.1.1. Khái niệm về hàm băm 139 4.1.2. Các định nghĩa, tính chất cơ bản và phân loại hàm băm 140 4.1.3. Các hàm băm không có khóa (MDC) 141 4.1.4. Các hàm băm có khoá (MAC) 145 4.1.5. Tính toàn vẹn của dữ liệu và xác thực thông báo 146 4.2. CHỮ KÝ SỐ 147 4.2.1. Sơ đồ chữ ký số 147 4.2.2. Sơ đồ chữ kýPTIT số RSA. 148 4.3. HỆ MẬT DỰA TRÊN ĐỊNH DANH 150 4.3.1. Ý tưởng cơ bản 150 4.3.2. Sơ đồ trao đổi khoá Okamoto-Tanaka 150 CHƯƠNG 5. CÁC THỦ TỤC VÀ CÁC CHÚ Ý TRONG THỰC TẾ KHI SỬ DỤNG MÃ HOÁ 152 5.1. CÁC THỦ TỤC: HÀNH VI CÓ THỨ TỰ 152 5.1.1. Định nghĩa thủ tục 152 5.1.2. Các loại thủ tục 153 5.1.3. Các thủ tục có trọng tài 153 v
  30. 5.1.4. Các thủ tục có phán xét 154 5.1.5. Các thủ tục tự ràng buộc 155 5.2. CÁC THỦ TỤC ĐỂ GIẢI QUYẾT CÁC VẤN ĐỀ 156 5.2.1. Phân phối khoá 156 5.2.2. Các chữ ký số 168 5.2.3. Giao kèo về khoá 174 5.2.4. Chơi bài qua thư tín 177 5.2.5. Bỏ phiếu bằng máy tính 181 5.2.6. Chuyển giao không nhớ 184 5.2.7. Ký thoả thuận 186 5.2.8. Thư tín được chứng thực 189 5.3. SỬ DỤNG MÃ HOÁ NHƯ THẾ NÀO 190 5.3.1. Mức độ bảo mật 191 5.3.2. Quản lý khoá 192 5.3.3. Các khoá bị mất (bị lộ) 192 5.3.4. Độ phức tạp mã hoá 193 5.3.5. Lan truyền sai 194 5.3.6. Kích thước bản mã 194 5.4. CẢI THIỆN ĐỘ MẬT CỦA HỆ MẬT 194 5.4.1. Ngăn ngừa và phát hiện sai 195 5.4.2. Mã hoá một chiều 198 5.5. CÁC CHẾ ĐỘ MÃ HOÁ 201 5.5.1. Chế độ xíchPTIT khối mật mã (CBC) 201 5.5.2. Chế độ hồi tiếp mật mã (CFB) 201 5.5.3. Hai khoá cho hiệu quả tương đương một khoá 112 bit 203 5.6. TÓM LƯỢC VỀ CÁC THỦ TỤC VÀ CÁC ỨNG DỤNG THỰC TẾ 204 BÀI TẬP CHƯƠNG 5 205 CHƯƠNG 6. CÁC CHUẨN VÀ ÁP DỤNG 206 6.1. BẢO MẬT THƯ ĐIỆN TỬ SỬ DỤNG PRETTY GOOD PRIVACY (PGP) 206 6.1.1. Mở đầu 206 6.1.2. Ký hiệu 206 6.1.3. Mô tả hoạt động 207 vi
  31. 6.2. GIAO DỊCH ĐIỆN TỬ AN TOÀN - SET 211 6.2.1. Mở đầu 211 6.2.2. Mô tả SET 211 6.3. ỨNG DỤNG XÁC THỰC - KERBEROS 215 6.3.1. Mở đầu 215 6.3.2. Kerberos V.4 217 BÀI TẬP CHƯƠNG 6 221 PHỤ LỤC 1: MÃ NGUỒN DES 222 PTIT vii
  32. Chương 2 – Mật mã khóa bí mật CHƯƠNG 2. MẬT MÃ KHÓA BÍ MẬT Có ba phương pháp chính trong mật mã cổ điển (còn gọi là mật mã khoá riêng, mật mã khoá bí mật hay mật mã khóa đối xứng): - Hoán vị - Thay thế - Xử lý bit (chủ yếu nằm trong các ngôn ngữ lập trình) Ngoài ra còn có phương pháp hỗn hợp thực hiện kết hợp các phương pháp trên mà điển hình là chuẩn mã dữ liệu (DES – Data Encryption Standard) của Mỹ. 2.1. SƠ ĐỒ KHỐI MỘT HỆ TRUYỀN TIN MẬT Thám mã (Oscar) Bản rõ Bản mã Bản mã Bản rõ Kênh mở Nguồn tin Bộ mã hoá Bộ giải mã Nhận tin (không an toàn) (Alice) K E K D (Bob) Kênh an toàn Nguồn khoá Hình 2.1. Sơ đồ hệ mật khóa bí mật Định nghĩa 2.1: Một hệ mật là một bộ 5 (P,C,K,E,D) thoả mãn các điều kiện sau: a) P là một tập hữu hạnPTIT các bản rõ có thể b) C là một tập hữu hạn các bản mã có thể c) K là một tập hữu hạn các khoá có thể (không gian khoá) d) Đối với mỗi k K có một quy tắc mã ek E ek : P C (2.1) và một quy tắc giải mã tương ứng dk D dk : C P (2.2) sao cho: dk (ek (x )) x vớix P . 24
  33. Chương 2 – Mật mã khóa bí mật 2.2. MẬT MÃ THAY THẾ 2.2.1. Mật mã dịch vòng (MDV) Giả sử P C K Z26 với 0 k 25, ta định nghĩa: ek x x k mod 26 dk y y k mod 26 (2.3) x, y Z26 Ta sử dụng MDV (với modulo 26) để mã hoá một văn bản tiếng Anh thông thường bằng cách thiết lập sự tương ứng giữa các ký tự và các thặng dư theo mod 26 như sau: Ký tự A B C D E F G H I J K L M Mã tương ứng 0 1 2 3 4 5 6 7 8 9 10 11 12 Ký tự N O P Q R S T U V W X Y Z Mã tương ứng 13 14 15 16 17 18 19 20 21 22 23 24 25 Ví dụ 2.1: Giả sử khoá cho MDV là k 5 và bản rõ là: meet me at sunset. Trước tiên, ta biến đổi bản rõ thành chữ in hoa và biến đổi thành dãy các số nguyên theo bảng trên (không biến đổi dấu cách (space) giữa 2 từ): 12.4.4.19.12.4.0.19.18.20.13.18.4.19 Sau đó ta cộng 5 vào mỗi giá trị ở trên và rút gọn tổng theo mod 26, ta được dãy số sau: 17.9.9.24.17.9.5.24.23.25.18.23.9.24 Cuối cùng, ta lại biến đổi dãy số nguyên trên thành các ký tự tương ứng, ta có bản mã sau: RJJY RJ FY XZSXJY Để giải mã cho bản mã này, trước tiên ta biến bản mã thành dãy số nguyên rồi trừ mỗi giá trị cho 5 (rút gọn theo modulo 26), và cuối cùng là lại biến đổi lại dãy số nhận được này thành các ký tự. Nhận xét: PTIT Khi k 3, hệ mật này thường được gọi là mã Caesar đã từng được Hoàng đế Caesar sử dụng. MDV (theo mod 26) là không an toàn vì nó có thể bị thám theo phương pháp tìm khoá vét cạn (thám mã có thể dễ dàng thử mọi khoá dk có thể cho tới khi tìm được bản rõ có nghĩa). Trung bình có thể tìm được bản rõ đúng sau khi thử khoảng (26 / 2) 13 quy tắc giải mã. Từ ví dụ trên ta thấy rằng, điều kiện cần để một hệ mật an toàn là phép tìm khoá vét cạn phải không thể thực hiện được. Tuy nhiên, một không gian khoá lớn vẫn chưa đủ để đảm bảm độ mật. 25
  34. Chương 2 – Mật mã khóa bí mật 2.2.2. Mã thay thế (MTT) Cho P C Z26 . K chứa mọi hoán vị có thể có của 26 ký tự từ 0 đến 25. Với mỗi phép hoán vị K , ta định nghĩa: e x x 1 và d y y trong đó 1 là hoán vị ngược của Sau đây là một ví dụ về phép hoán vị ngẫu nhiên tạo nên một hàm mã hoá (tương tự như trên, các ký tự của bản rõ được viết bằng chữ thường, còn các ký tự của bản mã được viết bằng chữ in hoa). Ký tự bản rõ a b c d e f g h i j k l m Ký tự bản mã X N Y A H P O G Z Q W B T Ký tự bản rõ n o p q r s t u v w x y z Ký tự bản mã S F L R C V M U E K J D I Như vậy, e (a) X ,e (b) N , Hàm giải mã là phép hoán vị ngược. Điều này được thực hiện bằng cách viết hàng thứ hai lên trước rồi sắp xếp theo thứ tự chữ cái. Ta có: Ký tự bản mã A B C D E F G H I J K L M Ký tự bản rõ d l r y v o h e z x w p t Ký tự bản mã N O P Q R S T U V W X Y Z Ký tự bản rõ b g f j q n m u s k a c i Ví dụ 2.2: Với phép thay thế trên, từ bản rõ: meet me at sunset ta thu được bản rõ sau: PTIT THHM TH XM VUSHM Sử dụng phép hoán vị ngược, ta dễ dàng tìm lại được bản rõ ban đầu. Mỗi khoá của mã thay thế là một phép hoán vị của 26 ký tự. Số các hoán vị này là 26! 4.1026 . Đây là một số rất lớn nên khó có thể tìm được khoá bằng phép tìm khoá vét cạn. Tuy nhiên, bằng phương pháp thống kê, ta có thể dễ dàng thám được các bản mã loại này. 2.2.3. Mật mã Vigenère Trong hai hệ MDV và MTT ở trên, một khi khoá đã được chọn thì mỗi ký tự sẽ được ánh xạ vào một ký tự duy nhất. Vì vậy, các hệ trên còn được gọi là các hệ thay thế đơn biểu. Sau đây ta sẽ trình bày một hệ thay thế đa biểu được gọi là hệ mật Vigenere. 26
  35. Chương 2 – Mật mã khóa bí mật Sử dụng phép tương ứng A  0,B 1, ,Z  25 mô tả ở trên, ta có thể gắn cho mỗi khoá k một chuỗi ký tự có độ dài m , được gọi là từ khoá. Mật mã Vigenère sẽ mã hoá đồng thời m ký tự: mỗi phần tử của bản rõ tương đương với m ký tự. Ví dụ 2.3: Giả sử m 6 và từ khoá là CIPHER. Từ khoá này tương ứng với dãy số k (2,8,15,7,4,17) . Giả sử bản rõ là: meet me at sunset Ta sẽ biến đổi các phần tử của bản rõ thành các thặng dư theo mod 26, viết chúng thành các nhóm 6 rồi cộng với từ khoá theo modulo 26 như sau: 12 4 4 19 12 4 0 19 18 20 13 18 4 19 Bản rõ 2 8 15 7 4 17 2 8 15 7 4 17 2 8 Khoá 14 12 19 0 16 21 2 1 7 1 17 9 6 1 Bản mã Như vậy, dãy ký tự tương ứng với xâu bản mã sẽ là: OMTA QV CB HBRJGB Ta có thể mô tả mật mã Vigenère như sau: Cho m là một số nguyên dương cố định nào đó. n Ta định nghĩa P C K Z26 Với khoá k k1, k2 , , km , ta xác định: ek x1, x 2 , ,xm x1 k1, x 2 k2 , , xm km và dk y1,y 2 , ,ym y1 k1, y 2 k2 , , ym km trong đó tất cả các phép toán được thực hiện trong Z26 . Chú ý: Để giải mã, ta có thể dùng cùng từ khoá nhưng thay cho cộng, ta trừ nó theo modulo 26. PTIT Ta thấy rằng, số các từ khoá có thể với độ dài m trong mật mã Vigenere là 26m . Bởi vậy, thậm chí với m khá nhỏ, phương pháp tìm kiếm vét cạn cũng yêu cầu thời gian khá lớn. Ví dụ, với m 6 thì không gian khoá cũng có kích thước lớn hơn 3.108 khoá. 2.2.3.1. Mã Affine MDV là một trường hợp đặc biệt của MTT chỉ gồm 26 trong số 26! các hoán vị có thể của 26 phần tử. Một trường hợp đặc biệt khác của MTT là mã Affine được mô tả dưới đây. Trong mã Affine, ta giới hạn chỉ xét các hàm mã có dạng: e(x ) ax bmod 26; a,b Z26 Các hàm này được gọi là các hàm Affine (chú ý rằng khi a 1 , ta có MDV). 27
  36. Chương 2 – Mật mã khóa bí mật Để việc giải mã có thể thực hiện được, yêu cầu cần thiết là hàm Affine phải là đơn ánh. Nói cách khác, với bất kỳy Z26 , ta muốn có đồng nhất thức sau: ax b  y mod 26 phải có nghiệm x duy nhất. Đồng dư thức này tương đương với: ax y b mod 26 Vì y thay đổi trên Z26 nên y b cũng thay đổi trên Z26 . Bởi vậy, ta chỉ cần nghiên cứu phương trình đồng dư: ax  y mod 26 Ta biết rằng, phương trình này có một nghiệm duy nhất đối với mỗi y khi và chỉ khi ƯCLN (a,26) 1 (ở đây hàm ƯCLN là ước chung lớn nhất của các biến của nó). Trước tiên ta giả sử rằng, ƯCLN (a,26) d 1. Khi đó, đồng dư thức ax  0mod 26 sẽ có ít nhất hai nghiệm phân biệt trong Z26 là x 0 và x 26 /d . Trong trường hợp này, e(x ) ax bmod 26 không phải là một hàm đơn ánh và bởi vậy nó không thể là hàm mã hoá hợp lệ. Ví dụ 2.4: Do ƯCLN (4,26) 2nên 4x 7 không là hàm mã hoá hợp lệ: x và x 13 sẽ mã hoá thành cùng một giá trị đối với bất kỳx Z26 . Ta giả thiết ƯCLN (a,26) 1. Giả sử với x1 và x 2 nào đó thoả mãn: ax1  ax 2 mod 26 Khi đó: a(x1 x 2 )  0mod 26 bởi vậy PTIT26 |a(x x ) 1 2 Bây giờ ta sẽ sử dụng một tính chất của phép chia sau: Nếu ƯCLN (a,b) 1và a |bc thì a |c . Vì 26 |a(x1 x 2 ) và ƯCLN (a,26) 1nên ta có: 26 | (x1 x 2 ) tức là x1  x 2 mod 26 Tới đây ta đã chứng tỏ rằng, nếu ƯCLN (a,26) 1thì một đồng dư thức dạng ax  y mod 26 chỉ có (nhiều nhất) một nghiệm trong Z26 . Do đó, nếu ta cho x thay đổi trên 28
  37. Chương 2 – Mật mã khóa bí mật Z26 thì ax mod 26 sẽ nhận được 26 giá trị khác nhau theo modulo 26 và đồng dư thức ax  y mod 26 chỉ có một nghiệm y duy nhất. Không có gì đặc biệt đối với số 26 trong khẳng định này. Bởi vậy, bằng cách tương tự, ta có thể chứng minh được kết quả sau: Định lý 2.1: Đồng dư thứcax bmodm chỉ có một nghiệm duy nhất x Zm với mọi b Zm khi và chỉ khi ƯCLN (a,m ) 1. Vì 26 2 13nên các giá trị a Z26 thoả mãn ƯCLN (a,26) 1 là a = 1 3, 5, 7, 9, 11, 13, 15, 17, 19, 21, 23 và 25. Tham số b có thể là một phần tử bất kỳ trong Z26 . Như vậy , mã Affine có 12 26 312 khoá có thể (dĩ nhiên, con số này là quá nhỏ để bảo đảm an toàn). Bây giờ, ta sẽ xét bài toán chung với modulom . Ta cần một định nghĩa khác trong lý thuyết số. Định nghĩa 2.2: Giả sử a 1 và m 2 là các số nguyên. ƯCLN (a,m ) 1 thì ta nói rằng a và m là nguyên tố cùng nhau. Số các số nguyên trong Zm nguyên tố cùng nhau với m thường được ký hiệu là (m ) (hàm này được gọi là hàm phi-Euler). Một kết quả quan trọng trong lý thuyết số cho ta giá trị của (m ) theo các thừa số trong phép phân tích theo luỹ thừa các số nguyên tố của m . (Một số nguyên p 1 là số nguyên tố nếu nó không có ước dương nào khác ngoài 1 và p ). Mọi số nguyên m 1 có thể phân tích được thành tích của các luỹ thừa các số nguyên tố theo cách duy nhất. Ví dụ 60 23 3 5 và 98 2 72 ). Ta sẽ ghi lại công thức cho (m ) trong định lí sau: Định lý 2.2: n Giả sử m p ei ; PTIT  i i 1 Trong đó các số nguyên tố pi khác nhau vàei 0; 1 i n . Khi đó : ei ei 1 (m )  pi pi (2.4) i Định lý này cho thấy rằng, số khoá trong mã Affine trên Z26 bằng m. (m ) , trong đó (m ) được cho theo công thức trên. (Số các phép chọn của b là m và số các phép chọn của a là (m ) với hàm mã hoá là e(x ) ax b ). Ví dụ, khi m 60, (60) 2 2 4 16 và số các khoá trong mã Affine là 960. 29
  38. Chương 2 – Mật mã khóa bí mật Bây giờ, ta sẽ xét xem các phép toán giải mã trong mật mã Affine với modulo m 26 . Giả sử ƯCLN (a,m ) 1. Để giải mã cần giải phương trình đồng dư y ax bmod 26 theo x . Từ thảo luận trên thấy rằng, phương trình này có một nghiệm duy nhất trong Z26 . Tuy nhiên, ta vẫn chưa biết một phương pháp hữu hiệu để tìm nghiệm. Điều cần thiết ở đây là có một thuật toán hữu hiệu để làm việc đó. Rất may là một số kết quả tiếp sau về số học modulo sẽ cung cấp một thuật toán giải mã hữu hiệu cần tìm. Định nghĩa 2.3: 1 Giả sử a Zm . Phần tử nghịch đảo (theo phép nhân) của a là phần tử a Zm sao cho aa 1 a 1a 1modm . Bằng các lý luận tương tự như trên, có thể chứng tỏ rằng a có nghịch đảo theo modulo m khi và chỉ khi ƯCLN (a,m ) 1, và nếu nghịch đảo này tồn tại thì nó phải là duy nhất. Ta cũng thấy rằng, nếu b a 1 thì a b 1 . Nếu p là số nguyên tố thì mọi phần tử khác không của Zp đều có nghịch đảo. Một vành trong đó mọi phần tử khác 0 đều có nghịch đảo được gọi là một trường. Trong [3] có một thuật toán hữu hiệu để tính các nghịch đảo của Zm với m tuỳ ý. Tuy nhiên, trong Z26 , chỉ bằng phương pháp thử và sai cũng có thể tìm được các nghịch đảo của các phần tử nguyên tố cùng nhau với 26: 1 1 1, 3 1 9, 5 1 21, 7 1 15, 11 1 19, 17 1 23, 25 1 25. (Có thể dễ dàng kiểm chứng lại điều này, ví dụ: 7 15 105 1mod 26 , bởi vậy 7 1 15 ). Xét phương trình đồng dư y  ax bmod 26 . Phương trình này tương đương với ax  y b(mod 26) Vì ƯCLN (a,26) 1 nên a có nghịch đảo theo modulo 26. Nhân cả hai vế của đồng dư thức với a 1 , ta có: PTITa 1(ax )  a 1(y b)mod 26 Áp dụng tính kết hợp của phép nhân modulo: a 1(ax )  (a 1a)x 1.x x Kết quả làx  a 1(y b)mod 26 . Đây là một công thức tường minh cho x . Như vậy hàm giải mã là: d(y) a 1(y b)mod 26 Hình 2.2 cho mô tả đầy đủ về mã Affine. Sau đây là một ví dụ nhỏ. 30
  39. Chương 2 – Mật mã khóa bí mật Cho P C Z26 và giả sử: K a, b Z26 Z26 :UCLN a, 26 1  Với k a, b K , ta định nghĩa: ek x ax b mod 26 1 Và dk y a y b mod 26 x, y Z 26 Hình 2.2. Mã Affine Ví dụ 2.5: Giả sử k (7,3) . Như đã nêu ở trên, 7 1 15 . Hàm mã hoá là: ek (x ) 7x 3 Và hàm giải mã tương ứng là: dk (x ) 15(y 3) 15y 19 Ở đây, tất cả các phép toán đều thực hiện trên Z26 . Ta sẽ kiểm tra liệu dk (ek (x )) x với mọi x Z26 không. Dùng các tính toán trên Z26 ta có: dk (ek (x )) dk (7x 3) 15(7x 3) 19 x 45 19 x Để minh hoạ, ta hãy mã hoá bản rõ "hot". Trước tiên, biến đổi các chữ h, o, t thành các thặng dư theo modulo 26. Ta được các số tương ứng là 7, 14 và 19. Bây giờ sẽ mã hoá: 7 7 3mod 26 52mod 26 0 7 14 3mod 26 101mod 26 23 7 19 3mod 26 136mod 26 6 Bởi vậy, ba ký hiệu của bản mã là 0, 23 và 6, tương ứng với xâu ký tự AXG. Việc giải mã sẽ do bạn đọc thực hiện như một bài tập. 2.3. MẬT MÃ HOÁN VỊ (MHV)PTIT Khác với MTT, ý tưởng của MHV là giữ các ký tự của bản rõ không thay đổi nhưng sẽ thay đổi vị trí của chúng bằng cách sắp xếp lại các ký tự này. Ở đây không có một phép toán đại số nào cần thực hiện khi mã hoá và giải mã. Ví dụ 2.6: Giả sử m 6 và khoá là phép hoán vị sau: 1 2 3 4 5 6 3 5 1 6 4 2 Khi đó, phép hoán vị ngược sẽ là: 1 2 3 4 5 6 3 6 1 5 2 4 31
  40. Chương 2 – Mật mã khóa bí mật Giả sử ta có bản rõ: a second class carriage on the train Trước tiên, ta nhóm bản rõ thành các nhóm 6 ký tự: asecon | dclass | carria | geonth | etrain Sau đó, mỗi nhóm 6 chữ cái lại được sắp xếp lại theo phép hoán vị , ta có: EOANCS | LSDSAC | RICARA | OTGHNE | RIENAT Cuối cùng, ta có bản mã sau: EOANCSLSDSACRICARAOTGHNERIENAT Khi sử dụng phép hoán vị ngược 1 trên dãy bản mã (sau khi đã nhóm lại theo các nhóm 6 ký tự), ta sẽ nhận lại được bản rõ ban đầu. Từ ví dụ trên, ta có thể định nghĩa MHV như sau: Cho m là một số nguyên dương xác định nào đó. m Cho P C Z26 và cho K là tất cả các hoán vị có thể có của: 1, 2, , m  . Đối với một khoá π (tức là một phép hoán vị nào đó), ta xác định: e (x1, , xm ) (x 1 , , x m ) và d (x , , x ) (y , , y ) 1 m 1 1 1 m trong đó 1 là phép hoán vị ngược của 2.4. MẬT MÃ HILL Trong phần này sẽ mô tả một hệ mật thay thế đa biểu khác được gọi là mật mã Hill. Mật mã này do Lester S.Hill đưa ra năm 1929. Giả sử m là một số nguyên dương, đặt m P C Z . Ý tưởng ở PTITđây là lấy m tổ hợp tuyến tính của m ký tự trong một phần tử 26 của bản rõ để tạo ra m ký tự ở một phần tử của bản mã. Ví dụ nếu m 2 ta có thể viết một phần tử của bản rõ là x (x1,x 2 ) và một phần tử của bản mã là y (y1,y 2 ) . Ở đây, y1 cũng như y 2 đều là một tổ hợp tuyến tính của x1 và x 2 . Chẳng hạn, có thể lấy: y 11x 3x 1 1 2 (2.5) y 2 8x1 7x 2 Tất nhiên có thể viết gọn hơn theo ký hiệu ma trận như sau: 32
  41. Chương 2 – Mật mã khóa bí mật 11 8 (y1 y 2 ) (x1 x 2 ) (2.6) 3 7 Nói chung, có thể lấy một ma trận k kích thước m m làm khoá. Nếu một phần tử ở hàng i và cột j của k là ki ,j thì có thể viết k ki ,j , với x (x1,x 2 , ,xm ) P và k K , ta tính y ek (x ) (y1,y 2 , ,ym ) như sau : k1,1 k1,2 k1,m k k k (y ,y , ,y ) (x ,x , ,x ) 2,1 2,2 2,m (2.7) 1 2 m 1 2 m km ,1 km ,2 km ,m Nói cách khác y xk . Chúng ta nói rằng bản mã nhận được từ bản rõ nhờ phép biến đổi tuyến tính. Ta sẽ xét xem phải thực hiện giải mã như thế nào, tức là làm thế nào để tính x từ y . Bạn đọc đã làm quen với đại số tuyến tính sẽ thấy rằng phải dùng ma trận nghịch đảo k 1 để giải mã. Bản mã được giải mã bằng công thức x yk 1 . Sau đây là một số định nghĩa về những khái niệm cần thiết lấy từ đại số tuyến tính. Nếu A xi ,j là một ma trận cấp 1 m và B bl,k là một ma trận cấp m n thì tích ma trận AB cl,k được định nghĩa theo công thức : m cl,k ai,jbj ,k (2.8) j 1 với 1 i l và 1 k l . Tức là các phần tử ở hàng i và cột thứ k của AB được tạo ra bằng cách lấy hàng thứ i của A và cột thứ k của B, sau đó nhân tương ứng các phần tử với nhau và cộng lại. Cần để ý rằng AB là một ma trận cấp 1 n . Theo định nghĩa này, phép nhân ma trận là kết hợp (tức(AB)C=A(BC) nhưng nói chung là không giao hoán (khôngPTIT phải lúc nào AB=BA , thậm chí đối với ma trận vuông A và B). Ma trận đơn vị m m (ký hiệu là Im ) là ma trận cấp m m có các số 1 nằm ở đường chéo chính, và các số 0 ở vị trí còn lại. Như vậy, ma trận đơn vị 2 2 là: 1 0 I2 (2.9) 0 1 Im được gọi là ma trận đơn vị vì AIm =A với mọi ma trận cấp 1 m và Im B=B với mọi ma trận cấp m n . Ma trận nghịch đảo của ma trận A cấp m m (nếu tồn tại) là ma 1 1 trận A sao cho AA Im . Không phải mọi ma trận đều có nghịch đảo, nhưng nếu tồn tại thì nó duy nhất. 33
  42. Chương 2 – Mật mã khóa bí mật Với các định nghĩa trên, có thể dễ dàng xây dựng công thức giải mã đã nêu: Vìy xk , ta có thể nhân cả hai vế của đẳng thức với k 1 và nhận được: 1 1 yk (xk)k xIm x (2.10) (Chú ý: sử dụng tính chất kết hợp) Có thể thấy rằng, ma trận mã hoá ở trên có nghịch đảo trong Z26 : 1 11 8 7 18 3 7 23 11 vì 11 8 7 18 11 7 8 23 11 18 8 11 3 7 23 11 3 7 7 23 3 18 7 11 261 286 1 0 182 131 0 1 (Hãy nhớ rằng mọi phép toán số học đều được thực hiện theo modulo 26). Sau đây là một ví dụ minh hoạ cho việc mã hoá và giải mã trong hệ mật mã Hill. Ví dụ 2.7: 11 8 Giả sử khoá k 3 7 Từ các tính toán trên, ta có: 1 7 18 k 23 11 Giả sử cần mã hoá bản rõ "July". Ta có hai phần tử của bản rõ để mã hoá: (9,20) (ứng với Ju) và (11,24) (ứng với ly).PTIT Ta tính như sau: 11 8 (9 20) 99 60 72 140 3 4 3 7 11 8 (11 24) 121 72 88 168 11 22 3 7 Bởi vậy, bản mã của July là DELW. Để giải mã, Bob sẽ tính 3 4 .k 1 9 20 và 11 22 k 1 11 24 Như vậy, Bob đã nhận được bản đúng. Cho tới lúc này, ta đã chỉ ra rằng có thể thực hiện phép giải mã nếu k có một nghịch đảo. Trên thực tế, để phép giải mã là có thể thực hiện được, điều kiện cần là k phải có nghịch 34
  43. Chương 2 – Mật mã khóa bí mật đảo. (Điều này dễ dàng rút ra từ đại số tuyến tính sơ cấp, tuy nhiên sẽ không chứng minh ở đây). Bởi vậy, ta chỉ quan tâm tới các ma trận k khả nghịch. Tính khả nghịch của một ma trận vuông phụ thuộc vào giá trị định thức của nó. Để tránh sự tổng quát hoá không cần thiết, ta chỉ giới hạn trong trường hợp 2 2 . Định nghĩa 2.4: Định thức của ma trận A ai,j cấp 2 2 là giá trị detA a1,1a2,2 a1,2a2,1 Nhận xét: Định thức của một ma trận vuông cấp m m có thể được tính theo các phép toán hàng sơ cấp (hãy xem một giáo trình bất kỳ về đại số tuyến tính). Hai tính chất quan trọng của định thức là: det Im 1 và quy tắc nhân: det (AB) detA det B . Một ma trận thực k là có nghịch đảo khi và chỉ khi định thức của nó khác 0. Tuy nhiên, điều quan trọng cần nhớ là ta đang làm việc trên Z26 . Kết quả tương ứng là ma trận k có nghịch đảo theo modulo 26 khi và chỉ khi ƯCLN(detk,26) 1. Sau đây sẽ chứng minh ngắn gọn kết quả này. Trước tiên, giả sử rằng ƯCLN (detk,26) 1. Khi đó detk có nghịch đảo trong Z26 . Với 1 i m , 1 j m , định nghĩa kij là ma trận thu được từ k bằng cách loại bỏ hàng thứ i và cột thứ j . Và định nghĩa ma trận k * có phần tử (i, j ) của nó nhận giá trị i j * ( 1) detkij (k được gọi là ma trận bù đại số của k ). Khi đó, có thể chứng tỏ rằng: k 1 (detk) 1k * Bởi vậy k là khả nghịch. Ngược lại, k có nghịchPTIT đảo k 1 . Theo quy tắc nhân của định thức: 1 detI det(kk 1) detk detk 1 Bởi vậy detk có nghịch đảo trong Z26 . Nhận xét: Công thức đối với k 1 ở trên không phải là một công thức tính toán có hiệu quả trừ các trường hợp m nhỏ (chẳng hạn m = 2, 3). Với m lớn, phương pháp thích hợp để tính các ma trận nghịch đảo phải dựa vào các phép toán hàng sơ cấp. Trong trường hợp 2 2 , ta có công thức sau: Định lý 2.3: Giả sử A (aij ) là một ma trận cấp 2 2 trên Z26 sao cho: 35
  44. Chương 2 – Mật mã khóa bí mật det A (a1,1a2,2 a1,2a2,1) có nghịch đảo. Khi đó: 1 1 a2,2 a1,2 A (det A) a2,1 a1,1 Trở lại ví dụ đã xét ở trên. Trước hết ta có: 11 8 det 11 7 8 3mod 2 77 24mod 2 53mod 2 1 3 7 Vì 1 1mod26 1 nên ma trận nghịch đảo là: 1 11 8 7 18 3 7 23 11 Đây chính là ma trận đã có ở trên. (Chú ý: 8 18; 3 23) Bây giờ ta sẽ mô tả chính xác mật mã Hill trên Z26 (Hình 2.3). m Cho m là một số nguyên dương cố định. Cho P C Z26 và cho K = { các ma trận khả nghịch cấp m m trên Z26 } Với một khoá k K ta xác định: ek x xk 1 và dk y yk Tất cả các phép toán được thực hiện trong Z26 Hình 2.3. Mật mã Hill 2.5. HỆ MẬT XÂY DỰNG TRÊN CÁC CẤP SỐ NHÂN XYCLIC CỦA VÀNH ĐA THỨC Trong phần này ta xét một ứng dụng của nhóm nhân xyclic trên vành đa thức Z [x ]/ x n 1 với n 2k . ĐâyPTIT là một trường hợp đặc biệt không được xem xét tới khi xây x dựng các mã khống chế sai.Tuy nhiên,trường hợp này lại có những ứng dụng khá lý thú trong mật mã [4]. 2.5.1. Nhóm nhân của vành Bổ đề 2.1: n k Trong vành Zx [x ]/ x 1 với n 2 , tập các đa thức có trọng số lẻ sẽ tạo nên một nhóm nhân các đa thức theo modulo x n 1. Chứng minh: Vì n 2k nên:(x n 1) (1 x )n . Do đó, mọi đa thức a(x ) có trọng số lẻ đều thoả mãn điều kiện: 36
  45. Chương 2 – Mật mã khóa bí mật a(x ),(1 x )n 1 (2.11) Các đa thức này sẽ tạo nên một nhóm nhân G có luỹ đẳng e(x ) 1và có cấp bằng:|G | 2n 1 . Bổ đề 2.2: Mọi phần tử trong nhóm nhân G có cấp là 2k hoặc có cấp là ước của 2k . Chứng minh: Đây là một trường hợp riêng của định lý ở phần 2.4.10. Ta có thể chứng minh bằng qui nạp: k 1: vành này chứa nhóm nhân cấp 2 là nhóm nhân xyclic đơn vị I. k i : Giả sử A {a(x ),a 2 (x ),a 3 (x ), ,a n (x )}là một nhóm nhân xyclic cấp n trong vành (n 2i ). k i 1 : Bình phương các phần tử của A ta có nhóm nhân xyclic sau: A 2 {a 2 (x ),a 4 (x ),a 6 (x ), ,a 2n (x )} Nhóm nhân xyclic này hiển nhiên là nhóm con của nhóm nhân xyclic cấp 2.2i 2i 1 có phần tử sinh là một trong các căn bậc hai của a(x ) . Gọi Q là tập các thặng dư bậc hai trong G. Ta có bổ đề sau: Bổ đề 2.3: Số các thặng dư bậc hai trong nhóm nhân G của vành được xác định theo biểu thức sau : k 1 |Q | 22 1 (2.12) Chứng minh: Xét f (x ) Q . Giả sử căn bậc hai của f (x ) là g(x ) , tức là: g 2 (x ) f (x )modx n 1 Nếu g(x ) g x i thì f (x ) g x 2i .  i PTIT i Tức là f (x ) (có trọng số lẻ) chỉ gồm một số lẻ các đơn thức có mũ chẵn. Số lượng các đa thức này bằng: 1 3 (n /2) 1 Q C n /2 C n /2 C n /2 2.5.2. Các phần tử cấp n và các nhóm nhân xyclic cấp n i Xét a(x ) G . a(x ) aix . Ta có bổ đề sau: Bổ đề 2.4: Đa thức a(x) là phần tử cấp n khi nó có chứa một số lẻ các đơn thức có mũ lẻ có cấp n và một số chẵn các đơn thức có mũ chẵn có cấp là ước của n . Số các đa thức cấp n bằng 2n 2 . 37
  46. Chương 2 – Mật mã khóa bí mật Chứng minh: Vì a(x ) G nên nó có trọng số lẻ. Số lượng các đơn thức có cấp n là (n 2) và số lượng các đơn thức còn lại là (n 2) . Như vậy, số các đa thức a(x ) có cấp n bằng: 2i 1 2j (n /2) 1 (n /2) 1 n 2 C n /2 C n /2 2 2 2 i j Ví dụ 2.8: Với trường hợp n 8, có tất cả 26 64 các phần tử cấp n . Ta có thể sử dụng các phần tử này để xây dựng các nhóm nhân xyclic cấp n . 2 3 n 0 Ai {ai (x ),ai (x ),ai (x ), ,ai (x ) ai (x ) 1} Có tất cả 2n 2 các nhóm nhân xyclic cấp n và nhóm nhân I cũng thuộc vào lớp các nhóm nhân này. Ta gọi nó là nhóm nhân xyclic đơn vị. 2.5.3. Hệ mật xây dựng trên các cấp số nhân xyclic 2.5.3.1. Các cấp số nhân xyclic cấp n Nếu ta nhân các phần tử của một nhóm nhân xyclic cấp n với một phần tử bất kỳ trong nhóm nhóm nhân G của vành đa thức ta sẽ thu được một cấp số nhân xyclic có công bội là phần tử sinh của nhóm nhân và có số hạng ban đầu là đa thức đem nhân. Bổ đề 2.5: Số các cấp số nhân xyclic cấp n xây dựng được trong G xác định theo biểu thức sau: k k N 22 1.22 2 (2.13) Ví dụ 2.9: n 8 N 28 1.28 2 213 8.192 n 16 N 216 1.216 2 229 536.870.912 n 32 N 232 1.232 2 261 PTIT64 1 64 2 125 n 64 N 2 .2 2 n 128 N 2128 1.2128 2 2253 2.5.3.2. Hệ mật xây dựng trên các cấp số nhân xyclic Mỗi cấp số nhân xyclic cấp n có thể coi là một phép biến đổi tuyến tính của vector mã ban đầu (được coi là nhóm nhân xyclic đơn vị I). Gọi là phần tử sinh của một nhóm nhân xyclic cấp n . Ta có bổ đề sau: Bổ đề 2.6: Tổng các số hạng của một cấp số nhân xyclic cấp n có công bội và số hạng đầu  được xác định theo biểu thức sau: 38
  47. Chương 2 – Mật mã khóa bí mật k 1 i 2 (2.14) Sn   1 i 0 Hiển nhiên làSn 0 . Hệ mật xây dựng trên các cấp số nhân này có thể được mô tả theo sơ đồ khối sau: Hệ mật A α, β I Mã hoá Vào A α, β Ra Khoá α β A α, β I Giải mã Vào A 1 α, β Ra Khoá α β Hình 2.4. Mỗi phép biến đổi (mã hoá) A có thể được đặc trưng bởi một ma trận vuông cấp n có dạng sau: . 2 . A  0 . A là một ma trận không suy biến và bởi vậy, luôn tồn tại A 1 thoả mãn: PTITA.A-1=I Tập các phép biến đổi này là một tập kín đối với phép tính (nhân ma trận) và tạo nên một nhóm nhân có phần tử đơn vị là phép biến đổi đồng nhất (ma trận đơn vị I). Nhóm nhân trong vành các ma trận vuông này là nhóm tuyến tính đầy đủ và được ký hiệu là GL n,GF (2) . Thuật toán mã hoá khá đơn giản, chỉ dựa trên phép toán nhân và bình phương một đa thức a(x ) G theo modulo (x n 1) (a(x ) có cấp n ) với một đa thức b(x ) bất kỳ G . 2.5.3.3. Vấn đề giải mã Để giải mã ta phải tìm phép biến đổi ngược A 1 là ma trận nghịch đảo của ma trận A. Tuy nhiên ta có thể dễ dàng thực hiện giải mã dựa trên bổ đề sau: 39
  48. Chương 2 – Mật mã khóa bí mật Bổ đề 2.7: Ma trận A có cấp (order) hoặc là n , hoặc là ước của n . Tức là ta luôn có: An I 2 2 Hay (A2 )2  k lÇn Ở đây, A được xem là phần tử sinh của một nhóm nhân xyclic có cấp bằng n hoặc bằng ước của n . Ví dụ 2.10: n 8 A (012),(024),(01356),(4),(456),(046),(12457),(0) Ma trận tương ứng: 1 1 0 0 0 0 0 1 0 1 0 1 0 0 0 1 1 0 1 0 1 1 0 1 0 0 0 1 0 0 0 0 A 0 0 0 1 1 1 0 0 0 0 0 1 0 1 0 1 1 1 0 1 1 0 1 0 0 0 0 0 0 0 0 1 A2 (014),(2),(236),(4),(045),(6),(267),(0) A3 (124),(024),(01235),(4),(056),(046),(14567),(0) A4 I (1),(2),(3),(4),(5),(6),(7),(0) Chú ý: Ở đây ta biểu diễn các đa thức qua các số mũ của các thành phần khác không. Ví dụ: (01235) 1 x x 2 x 3PTIT x 5 . Vào Mã hoá Ra Vào Giải mã Ra I A A A (A2)2 = I Ví dụ 2.11: Xét cấp số nhân có công bội (023) với số hạng đầu (023) (012) = (015). B 015 , 12457 , 03467 , 456 , 145 , 01356 , 02347 , 012  B2 124 , 136 , 346 , 035 , 056 , 257 , 027 , 147  B3 02567 , 047 , 167 , 23567 , 12346 , 034 , 235 , 12367  B4 02456 , 13567 , 02467 , 01357 , 01246 , 12357 , 02346 , 13457  40
  49. Chương 2 – Mật mã khóa bí mật B5 347 , 12345 , 01245 , 146 , 037 , 01567 , 01456 , 025  B6 245 , 123 , 467 , 345 , 016 , 567 , 023 , 017  B7 24567 , 236 , 127 , 01347 , 01236 , 267 , 356 , 03457  B 1 B8 1 , 2 , 3 , 4 , 5 , 6 , 7 , 0  2 2 I= B2 Thuật toán giải mã chỉ là một thuật toán lặp của thuật toán mã hoá. Số lần lặp tối đa là k . 2.5.3.4. Các ma trận luân hoàn Khi sử dụng cấp số nhân có công bội x và có số hạng đầu là một đa thứca(x ) G ta sẽ có một lớp các biến đổi đặc biệt, được đặc trưng bởi một loại ma trận đặc biệt, được gọi là ma trận luân hoàn. Định nghĩa 2.5: Ma trận vuông A n n trên trường F được gọi là ma trận luân hoàn nếu nó có dạng sau: a(x ) a0 a1 an 1 xa(x ) a a a A n 1 0 n 2 ; a F     n 1 x a(x ) a1 a2 a0 Bổ đề 2.8: Đại số các ma trận luân hoàn cấp n trên trường F đẳng cấu với đại số F[x ] / (x n 1)đối với phép ánh xạ các ma trận luân hoàn thành các đa thức dạng: n 1 i a(x ) aix PTITi 0 Bổ đề 2.9: Tổng và tích của hai ma trận luân hoàn là một ma trận luân hoàn. Ta có: A.B = C Trong đó: c(x ) a(x ).b(x )mod(x n 1) Bổ đề 2.10: Ma trận luân hoàn A là khả nghịch khi và chỉ khi đa thức a(x ) là nguyên tố cùng nhau với (x n 1) . Ma trận nghịch đảo B nếu tồn tại sẽ tương ứng với b(x ) thoả mãn điều kiện: k a(x ).b(x ) 1mod(x 2 1) 41
  50. Chương 2 – Mật mã khóa bí mật n Trong trường hợp vành GF2[x ] / (x 1) và a(x ) G , ta luôn có: k k a(x ),(x 2 1) a(x ),(x 1)2 1 Bổ đề 2.11: Tập các ma trận luân hoàn A ứng với a(x ) G sẽ tạo nên một nhóm con nhân Abel trong nhóm nhân của vành các ma trận vuông. Trong nhóm này tồn tại các nhóm con là các nhóm nhân xyclic có cấp bằng n hoặc ước của n . Mối quan hệ giữa nhóm nhân của vành đa thức và nhóm nhân của vành các ma trận vuông được mô tả trên hình sau (Hình 2.5). Hình 2.5.PTIT Quan hệ giữa vành đa thức và vành ma trận Bổ đề 2.12: Cấp của ma trận luân hoàn A bằng cấp của đa thức a(x ) tương ứng của nó. Khi ord (a(x )) 2 thì ma trận luân hoàn A tương ứng là một ma trận tự nghịch đảo. Bổ đề 2.13: Số các ma trận luân hoàn dùng để lập mã bằng số các phần tử của nhóm nhân trong vành đa thức. Trong trường hợp ma trận luân hoàn, thuật toán mã hoá chỉ là một phép cộng với n bước dịch vòng. 42
  51. Chương 2 – Mật mã khóa bí mật Thuật toán giải mã bao gồm một phép tính nghịch đảo của một đa thức theo modulo (x n 1) và n bước dịch vòng tương ứng của phần tử nghịch đảo này. Ví dụ 2.12: a(x ) 1 x x 2 A 012 , 123 , 234 , 345 , 456 , 567 , 067 , 017  A2 124 , 135 , 246 , 357 , 046 , 157 , 026 , 137  A3 01356 , 12467 , 02357 , 01346 , 12457 , 02356 , 13467 , 02457  A4 4 , 5 , 6 , 7 , 0 , 1 , 2 , 3  A5 456 , 567 , 067 , 017 , 012 , 123 , 234 , 345  A6 046 , 157 , 026 , 137 , 024 , 135 , 246 , 357  A7 { 12457 , 02356 , 13467 , 02457 , 01356 12467 , 02357 , 01346 } A 1 A8 1 , 2 , 3 , 4 , 5 , 6 , 7 , 0  I Vào (7) (6) (5) (4) (3) (2) (1) (0) (10110101) (00001000) Ra A (0) ,(1) , ,(7)  Hình 2.6. Sơ đồ thiết bị mã hoá Vào (7)' (6)'PTIT (5)' (4)' (3)' (2)' (1)' (0)' (00001000) (10110101) Ra A (0),(1), ,(7) Hình 2.7. Sơ đồ thiết bị giải mã a 1(x ) x x 2 x 4 x 5 x 7 Ta có: 43
  52. Chương 2 – Mật mã khóa bí mật 1 1 1 0 0 0 0 0 0 1 1 0 1 1 0 1 1 0 0 0 0 0 0 0 0 1 1 1 0 0 0 0 1 0 1 1 0 1 1 0 0 1 0 0 0 0 0 0 0 0 1 1 1 0 0 0 0 1 0 1 1 0 1 1 0 0 1 0 0 0 0 0 0 0 0 1 1 1 0 0 1 0 1 0 1 1 0 1 0 0 0 1 0 0 0 0 AA 1 I 0 0 0 0 1 1 1 0 1 1 0 1 0 1 1 0 0 0 0 0 1 0 0 0 0 0 0 0 0 1 1 1 0 1 1 0 1 0 1 1 0 0 0 0 0 1 0 0 1 0 0 0 0 0 1 1 1 0 1 1 0 1 0 1 0 0 0 0 0 0 1 0 1 1 0 0 0 0 0 1 1 1 0 1 1 0 1 0 0 0 0 0 0 0 0 1 2.6. CÁC HỆ MẬT MÃ TÍCH Một phát minh khác do Shannon đưa ra trong bài báo của mình năm 1949 là ý tưởng kết hợp các hệ mật bằng cách tạo tích của chúng. Ý tưởng này có tầm quan trọng to lớn trong việc thiết kế các hệ mật hiện nay (chẳng hạn, chuẩn mã dữ liệu - DES ). Để đơn giản, trong phần này chỉ hạn chế xét các hệ mật trong đóC P : các hệ mật loại này được gọi là tự đồng cấu. Giả sử S1 (P ,P ,K1,E1,D1) và S 2 (P ,P ,K 2 ,E2 ,D2 ) là hai hệ mật tự đồng cấu có cùng các không gian bản mã và rõ. Khi đó, tích của S1 và S 2 (kí hiệu làS1 S 2 ) được xác định là hệ mật sau: (P ,P ,K1 K 2 ,E,D) Khoá của hệ mật tích có dạng k (k1,k2 ) trong đó k1 K1 vàk2 K 2 . Các quy tắc mã và giải mã của hệ mật tích được xác định như sau: Với mỗik (k1,k2 ) , ta có một quy tắc mã ek xác định theo công thức: e (x ) e e (x ) (k1 ,k2 ) k2 k1 và quy tắc giải mã: d (y) d d (y) (k1 ,k2 ) k1 k2 Nghĩa là, trước tiên ta mã hoá x bằng e rồi mã lại mã hóa bản kết quả bằng e . Quá k1 k2 trình giải mã tương tự nhưng PTITthực hiện theo thứ tự ngược lại: d e (x ) d e e (x ) d d e e (x ) d e (x ) x (k1,k2 ) (k1 ,k2 ) (k1 ,k2 ) k2 k1 k1 k2 k2 k1 k1 k1 Ta biết rằng, các hệ mật đều có các phân bố xác suất ứng với các không gian khoá của chúng. Bởi vậy, cần phải xác định phân bố xác suất cho không gian khoá K của hệ mật tích. Hiển nhiên ta có thể viết: p (k ,k ) p (k ) p (k ) K 1 2 K 1 1 K 2 2 Nói một cách khác, ta chọn k có phân bố p (k ) rồi chọn một cách độc lập k có phân 1 K 1 1 2 bố p (k ) . K 2 2 44
  53. Chương 2 – Mật mã khóa bí mật Sau đây là một ví dụ đơn giản để minh hoạ khái niệm hệ mật tích. Giả sử định nghĩa hệ mật mã nhân như trong Hình 2.8 sau. Giả sử P C Z26 và giả sử: k a, Z26 :UCLN a, 26 1  Với a K , ta xác định:ea x ax mod 26 1 và da y a y mod 26 x, y Z26 Hình 2.8. Mật mã tích Cho M là một hệ mã nhân (với các khoá được chọn đồng xác suất) và S là MDV (với các khoá chọn đồng xác suất). Khi đó dễ dàng thấy rằng M S chính là hệ mã Affine (cùng với các khoá được chọn đồng xác suất). Tuy nhiên, việc chứng tỏ S M cũng là hệ mã Affine khó hơn một chút (cũng với các khóa đồng xác suất). Ta sẽ chứng minh các khẳng định này. Một khoá dịch vòng là phần tử k Z26 và quy tắc mã hóa tương ứng là ek (x ) x k mod 26 . Còn khoá trong hệ mã nhân là phần từ a Z26 sao cho ƯCLN (a,26) 1. Quy tắc mã tương ứng là ea (x ) a mod 26 . Bởi vậy, một khoá trong mã tích M S có dạng (a,k) , trong đó e(a ,k ) ax k mod 26 Đây chính là định nghĩa về khoá trong hệ mã Affine. Hơn nữa, xác suất của một khoá trong hệ mã Affine là: 1 312 1 12 1 26 . Đó là tích của xác suất tương ứng của các khoá a và k . Bởi vậy M S là hệ mã Affine. Bây giờ ta sẽ xétS M . Một khoá này trong hệ mã này có dạng(k,a) , trong đó: e(k ,a ) (x ) a(x k) ax ak mod 26 Như vậy, khoá (k,a) cPTITủa mã tích S M đồng nhất với khoá (a,ak) của hệ mã Affine. Vấn đề còn lại là phải chứng tỏ rằng mỗi khoá của mã Affine xuất hiện với cùng xác suất 1 1/312 như trong mã tích S M . Nhận thấy rằng ak k1 khi và chỉ khi k a k1 , ( hãy nhớ lại rằng ƯCLN (a,26) 1, bởi vậy a có phần tử nghịch đảo). Nói cách khác, khoá (a,k1) 1 của hệ mã Affine tương đương với khoá a k1,a của mã tích S M . Bởi vậy, ta có một song ánh giữa hai không gian khoá. Vì mỗi khoá là đồng xác suất nên có thể thấy rằng S M thực sự là mã Affine. Ta chứng minh rằng M S S M . Bởi vậy, hai hệ mật là giao hoán. Tuy nhiên, không phải mọi cặp hệ mật đều giao hoán; có thể tìm ta được các cặp phản ví dụ. Mặt khác ta thấy rằng phép tích luôn kết hợp: (S1 S 2 ) S 3 S1 (S 2 S 3 ) 45
  54. Chương 2 – Mật mã khóa bí mật Nếu lấy tích của một hệ mật tự đồng cấu với chính nó thì ta thu được hệ mật S S (kí hiệu là S 2 ). Nếu lấy tích n lần thì hệ mật kết quả là S n . Ta gọi S n là hệ mật lặp. Một hệ mật S được gọi là luỹ đẳng nếu S 2 S . Có nhiều hệ mật đã nghiên cứu trong chương 1 là hê mật luỹ đẳng. Chẳng hạn các hệ MDV, MTT, Affine, Hill, Vigenère và hoán vị đều là luỹ đẳng. Hiển nhiên là nếu hệ mật S là luỹ đẳng thì không nên sử dụng hệ mật tích S 2 vì nó yêu cầu lượng khoá cực lớn mà không có độ bảo mật cao hơn. Nếu một hệ mật không phải là luỹ đẳng thì có thể làm tăng độ mật bằng cách lặp nhiều lần. Ý tưởng này đã được dùng trong chuẩn mã dữ liệu (DES). Trong DES dùng 16 phép lặp, tất nhiên hệ mật ban đầu phải là hệ mật không luỹ đẳng. Một phương pháp có thể xây dựng các hệ mật không luỹ đẳng đơn giản là lấy tích của hai hệ mật đơn giản khác nhau. Nhận xét: Có thể dễ dàng chứng tỏ rằng, nếu cả hai hệ mật S1 và S 2 là luỹ đẳng và giao hoán thì S1 và S 2 cũng là luỹ đẳng. Điều này rút ra từ các phép toán đại số sau: S1 S 2 S1 S 2 S1 S 2 S1 S 2 S S S S 1 1 2 2 S1 S1 S 2 S 2 S1 S 2 (Chú ý: Dùng tính chất kết hợp trong chứng minh trên). Bởi vậy, nếu cả S1 và S 2 đều là luỹ đẳng và ta muốn S1 S 2 là không luỹ đẳng thì điều kiện cần là S1 và S 2 không giao hoán. Rất may mắn là nhiều hệ mật đơn giản thoả mãn điều kiện trên. Kỹ thuật thường được sử dụng trong thực tế là lấy tích các hệ mã kiểu thay thế và các hệ mã kiểu hoán vị. 2.7. CÁC HỆ MÃ DÒNG 2.7.1. Sơ đồ chức năng của hPTITệ mật mã dòng Trong các hệ mật nghiên cứu ở trên, các phần tử liên tiếp của bản rõ đều được mã hoá bằng cùng một khoá k . Tức xâu bản mã y nhận được có dạng: y y1y 2 ek (x1)ek (x 2 ) Các hệ mật thuộc dạng này thường được gọi là các mã khối. Một quan điểm sử dụng khác là mật mã dòng. Ý tưởng cơ bản ở đây là tạo ra một dòng khoá z z1z 2 và dùng nó để mã hoá một xâu bản rõ x x1x 2 theo quy tắc: y y y e (x )e (x ) 1 2 z1 1 z 2 2 Sơ đồ mã hóa và giải mã của hệ mật mã dòng mô tả trong Hình 2.9 46
  55. Chương 2 – Mật mã khóa bí mật x i yi yi xi 101100 111010 111010 101100 k 010110 k 010110 a) Mã hóa b) Giải mã Hình 2.9. Sơ đồ chức năng hệ mật mã dòng Mã dòng hoạt động như sau: Giả sử k K là khoá, và x x1x 2 là xâu bản rõ. Hàm fi được dùng để tạo zi (zi là phần tử thứ i của dòng khoá), trong đó fi là một hàm của khoá k và i 1 là ký tự đầu tiên của bản rõ: zi fi k,x1, ,xi 1 Phần tử z của dòng khoá được dùng để mã x tạo ra y e (x ) . Bởi vậy, để mã hoá i i i zi i xâu bản rõ x x1x 2 ta phải tính liên tiếp z1,y1,z 2 ,y 2 , Việc giải mã xâu bản mã y1y 2 có thể được thực hiện bằng cách tính liên tiếp z1,x1,z 2 ,x 2 , Sau đây là định nghĩa dưới dạng toán học: Định nghĩa 3.6: Mật mã dòng là một bộ P,C,K,L,F,E,D thoả mãn các điều kiện sau: (1) P là một tập hữu hạn các bản rõ có thể. (2) C là tập hữu hạn các bản mã có thể. (3) K là tập hữu hạn các khoá có thể (không gian khoá) (4) L là tập hữu hạn các bộ chữ của dòng khoá. (5) F f1f2 là bộ tạo dòng khoá. Với i 1 f : K P i 1 L PTITi (6) Với mỗi z L có một quy tắc mã ez E và một quy tắc giải mã tương ứngdz D . ez : P C và dz : C P là các hàm thoả mãn dz ez (x ) x với mọi bản rõx P . Ta có thể coi mã khối là một trường hợp đặc biệt của mã dòng, trong đó dùng khoá không đổi: zi k với mọi i 1. Nhận xét: - Để hệ thống an toàn, dãy bit khóa ngẫu nhiên và k m . (Dãy ngẫu nhiên được lấy là kết quả của quá trình tung đồng xu: p 0 p 1 0,5). 47
  56. Chương 2 – Mật mã khóa bí mật - Việc tạo dãy ngẫu nhiên rất tốn kém và việc lưu trữ không hiệu quả, do vậy ta phải sử dụng dãy giả ngẫu nhiên, các dãy này có tính tiền định và được xây dựng từ các bit mầm. 2.7.2. Tạo dãy giả ngẫu nhiên (M-dãy) 2.7.2.1. Tạo dãy giả ngẫu nhiên theo đa thức nguyên thủy Định nghĩa 2.6: Đa thức nguyên thủy Đa thức bất khả quy bậc m được gọi là đa thức nguyên thủy nếu nó là ước của x n 1 với n 2m 1 nhưng không là ước của x l 1 với l n . (chú ý: đa thức bất khả quy là đa thức chia hết cho 1 và chính nó, tương đương số nguyên tố) Ví dụ 2.13: + m 3 n 7 , ta có: x 7 1 (1 x )(1 x x 3 )(1 x 2 x 3 ) . 7 3 2 3 Trên vành đa thức x 1 có hai đa thức: f1(x ) (1 x x ) và f2 (x ) (1 x x ) là hai đa thức nguyên thủy vì nó không là ước của x l 1với l 6 . + m 4 n 15 , ta có x 15 1 (1 x )(1 x x 2 )(1 x x 4 )(1 x 3 x 4 )(1 x x 2 x 3 x 4 ) Với trường hợp này chỉ có hai đa thức 1 x x 4 và 1 x 3 x 4 là nguyên thủy, còn đa thức 1 x x 2 x 3 x 4 không phải nguyên thủy vì nó là ước của x 5 1. x 5 1 (1 x)(1 x x 2 x 3 x 4 ) Bổ đề 2.14: Dãy giả ngẫu nhiên (M-dãy) được tạo từ phương trình đồng dư sau đây: a(x ) b(x ).x i modg(x ) ; i 1,2, ,2n 1 (2.15) Với: g(x ) là đa thứPTITc nguyên thủy bậc m b(x ) là đa thức mầm ứng với m bit, được chọn ngẫu nhiên thỏa mãn degb(x ) m 1 Ví dụ 2.14: Với m 4; g(x ) 1 x x 4 , M-dãy được tạo như sau: a(x )  b(x )x i mod1 x x 4 Coi 1 x x 4 0 x 4 1 x . Giả sử b(x ) 1 x 1100 Trạng thái của M-dãy này được mô tả trong Bảng 2.1 48
  57. Chương 2 – Mật mã khóa bí mật Bảng 2.1. Trạng thái của M-dãy TT a(x ) a 0 1 x 1 1 0 0 1 x x 2 0 1 1 0 2 x 2 x 3 0 0 1 1 3 1 x x 3 1 1 0 1 4 1 x 2 1 0 1 0 5 x x 3 0 1 0 1 6 1 x x 2 1 1 1 0 7 x x 2 x 3 0 1 1 1 8 1 x x 2 x 3 1 1 1 1 9 1 x 2 x 3 1 0 1 1 10 1 x 3 1 0 0 1 11 1 1 0 0 0 12 x 0 1 0 0 13 x 2 0 0 1 0 14 x 3 0 0 0 1 15 1 x 1 1 0 0 Nhận xét: - Khi lấy bất kỳ một cột nào trong 4 cột của a ta sẽ được một M-dãy. - Chu kỳ của dãy: t 2m 1 với trường hợp này m 4 t 15 . m - Số con "1" trong dãy: N 1 2 , với m 4 N 1 8 . m - Số con "0" trong dãy: N 0 2 1, với m 4 N 0 7 . - Khi m ta có: lim p 0 lim p 1 1 2 m m Cấu trúc tổng quát mạch điện phần cứng M-dãy được thực hiện bằng các thanh ghi dịch hồi tiếp tuyến tính (LFSR) vàPTIT có dạng như Hình 2.10. g0 g1 g2 gm 1 gm 1 2 m Clk i 1, ,2m 1 M-dãy M-dãy M-dãy Hình 2.10. Mạch điện thực hiện M-dãy 49
  58. Chương 2 – Mật mã khóa bí mật Trong sơ đồ Hình 2.10 các gi nhận giá trị "0" hoặc "1" là các hệ số của đa thức nguyên 2 m thủy g(x ) g0 g1x g2x gm x . Riêng g0 gm 1 (luôn bằng "1"). Nếu gi 1 thì mạch điện sẽ nối tắt, còn gi 0 thì sẽ hở mạch. Ví dụ 2.15: 4 Giả sử g(x ) 1 x x , (m 4) , ta thấy g0 g1 g4 1;g2 g3 0 , mạch điện tạo M-dãy như sau: g 1 g 1 0 1 g 1 2 3 4 Clk i 1 15 M-dãy M-dãy M-dãy M-dãy Hình 2.11. Mạch điện tạo M-dãy với g(x) 1 x x 4 Bảng 2.2. Trạng thái hoạt động của các ô nhớ Trạng thái các ô nhớ Nhịp i 1 2 3 4 0 1 1 0 0 1 0 1 1 1 2 0 0 1 1 3 1 1 0 1 4 1 0 1 0 5 0 1 0 1 6 1 1 1 0 7 0 1 1 1 8 1 1 1 1 9 1 0 1 1 10 1 0 0 1 11 1 0 0 0 12 PTIT0 1 0 0 13 0 0 1 0 14 0 0 0 1 15 1 1 0 0 Trong Bảng 2.2 thì trạng thái các ô nhớ tại dòng đầu tiên tương ứng với các bit mầm (đa thức b(x ) 1 x ). 2.7.2.2. Tạo dãy giả ngẫu nhiên trên vành đa thức có hai lớp kề xyclic Định nghĩa 2.7: Vành đa thức có hai lớp kề xyclic là vành có phân tích như sau: n 1 x n 1 1 x x i i 0 50
  59. Chương 2 – Mật mã khóa bí mật n 1 Trong đó: 1 x và x i là các đa thức bất khả quy. i 0 Ví dụ: n 5,11,19, x 5 1 1 x 1 x x 2 x 3 x 4 Bổ đề 2.15: M-dãy trên vành đa thức có hai lớp kề xyclic x n 1 được tạo từ phương trình đồng dư sau: n 1 a(x ) b(x )ci (x ) mod x i (2.16) i 0 n 1 Trong đó: x i là đa thức bất khả quy i 0 b(x ) là đa thức bất kỳ, thỏa mãn degb(x ) n 2 c(x ) là đa thức thỏa mãn ord c(x ) max 2n 1 1 Định nghĩa 2.8: Cấp của đa thức c(x ) là cấp của nhóm nhân xyclic sinh bởi c(x ) C ci (x ),i 1,2,  ord c(x ) C Ví dụ 2.16: 4 Xét trường hợp n 5 và x i là đa thức bất khả quy, khi đó M-dãy được xây dựng i 0 theo công thức (2.16) có dạng như sau: 4 a(x ) b(x )ci (x ) mod x i i 0 4 Chú ý: để lấy modulo PTITtheo x i 1 x x 2 x 3 x 4 ta coi 1 x x2 x3 x 4 0 tức  i 0 là coi x 4 1 x x 2 x 3 . Chọn b(x) 1  0 và c(x ) 1 x 2 x 4  024 , chú ý 024 là dạng biểu diễn số mũ của c(x ) . Nhóm nhân xây dựng từ đa thức sinh c(x ) như sau: C ci (x),i 1,2,  024 , 034 , 1 , 013 , 014 , 2 , 124 012 , 3 , 023 , 123 , 4 , 134 , 234 , 0  Trên cơ sở nhóm nhân C ta tính được M-dãy như sau: 51
  60. Chương 2 – Mật mã khóa bí mật 4 i i  A c (x ) mod x  13 , 12 , 1 , 013 , 23 , 2 , 03 , 012 i 0  3 , 023 , 123 , 0123 , 02 , 01 , 0  Bảng 2.3. M-dãy trên vành x 5 1 Đa thức TT Đa thức Dạng vectơ dạng số mũ 1 13 x x 3 0 1 0 1 M -dãy 2 12 x x 2 0 1 1 0 3 1 x 0 1 0 0 4 013 1 x x 3 1 1 0 1 5 23 x 2 x 3 0 0 1 1 6 2 x 2 0 0 1 0 7 03 1 x 3 1 0 0 1 8 012 1 x x 2 1 1 1 0 9 3 x 3 0 0 0 1 10 023 1 x 2 x 3 1 0 1 1 11 123 x x 2 x 3 0 1 1 1 12 0123 1 x x 2 x 3 1 1 1 1 13 02 1 x 2 1 0 1 0 14 01 1 x 1 1 0 0 15 0 1 1 0 0 0 M-dãy trong Bảng 2.3 thực chất là một hoán vị của M-dãy trong Bảng 2.1. Số các đa thức nguyên thủy (các phần tử sinh) tính theo công thức sau: PTITN C Trong đó là hàm Phi-Euler, giá trị của C cho biết số các số nguyên tố cùng nhau với C . Cách tính đã được trình bày ở mục 1.1.12. Ví dụ 2.17: Xét n 15 3.5 , khi đó: 1 1  15 15 1 1 8 3 5 Nếu là một phần tử nguyên thủy thì i cũng là phần tử nguyên thủy với i,n 1. 52
  61. Chương 2 – Mật mã khóa bí mật Với trường hợp n 15 ta có: i 1,2,4,7,8,11,13,14 tức là có 8 phần tử bằng với (15) . Và 8 phần tử nguyên thủy này sẽ tạo thành một nhóm nhân, các phần tử đều có nghịch đảo như mô tả như hình 2.12 sau đây: 024 , 034 , 013 , 124 , 012 , 123 , 134 , 234 1   1  1 1    Hình 2.12. 1 1 024 234 hay 1 x 2 x 4 x 2 x 3 x 4 2.8. CHUẨN MÃ DỮ LIỆU 2.8.1. Mở đầu Ngày 15/5/1973. Uỷ ban tiêu chuẩn quốc gia Mỹ đã công bố một khuyến nghị cho các hệ mật trong Hồ sơ quản lý liên bang. Điều này cuối cùng đã dẫn đến sự phát triển của Chuẩn mã dữ liệu (DES) và nó đã trở thành một hệ mật được sử dụng rộng rãi nhất trên thế giới. DES được IBM phát triển và được xem như một cải biên của hệ mật LUCIPHER. DES được công bố lần đầu tiên trong Hồ sơ Liên bang vào ngày 17/3/1975. Sau nhiều cuộc tranh luận công khai, DES đã được chấp nhận chọn làm chuẩn cho các ứng dụng không được coi là mật vào 5/1/1977. Kể từ đó cứ 5 năm một lần, DES lại được Uỷ ban Tiêu chuẩn Quốc gia xem xét lại. Lần đổi mới gần đây nhất của DES là vào tháng 1/1994 và tiếp tới sẽ là 1998. Người ta đoán rằng DES sẽ không còn là chuẩn sau 1998. 2.8.2. Mô tả DES Mô tả đầy đủ của DES được nêu trong Công bố số 46 về các chuẩn xử lý thông tin Liên bang (Mỹ) vào 15/1/1977. DES mã hoá một xâu bit x của bản rõ độ dài 64 bằng một khoá 54 bit. Bản mã nhận được cũng là một xâu bit có độ dài 64. Trước hết ta mô tả ở mức cao về hệ thống. PTIT Thuật toán tiến hành theo 3 giai đoạn: 1. Với bản rõ cho trước x , một xâu bit x 0 sẽ được xây dựng bằng cách hoán vị các bit của x theo phép hoán vị cố định ban đầu IP. Ta viết: x 0 IP(x ) L0R 0 trong đó L0 gồm 32 bit đầu và R 0 là 32 bit cuối. 2. Sau đó tính toán 16 lần lặp theo một hàm xác định. Ta sẽ tínhLi ,Ri , 1 i 16 theo quy tắc sau: Li Ri 1 Ri Li 1  f Ri 1,ki 53
  62. Chương 2 – Mật mã khóa bí mật trong đó  kí hiệu phép hoặc loại trừ của hai xâu bit (cộng theo modulo 2). f là một hàm mà ta sẽ mô tả ở sau, còn k1,k2 , ,k16 là các xâu bit độ dài 48 được tính như hàm của khoá k . (trên thực tế mỗi ki là một phép chọn hoán vị bit trong k ). k1,k2 , ,k16 sẽ tạo thành bảng khoá. Một vòng của phép mã hoá được mô tả trên Hình 2.13. Li 1 Ri 1 f K i Li Ri Hình 2.13. Một vòng của DES 1 3. Áp dụng phép hoán vị ngược IP cho xâu bit R16L16 , ta thu được bản mã y . Tức là 1 y IP (R16L16 ). Hãy chú ý thứ tự đã đảo của R16 và L16 . Hàm f có hai biến vào: biến thứ nhất A là xâu bit độ dài 32, biến thứ hai J là một xâu bit độ dài 48. Đầu ra của f là một xâu bit độ dài 32. Các bước sau được thực hiện: 1. Biến thứ nhất A được mở rộng thành một xâu bit độ dài 48 theo một hàm mở rộng cố định E(EA) gồm 32 bit của A (được hoán vị theo cách cố định) với 16 bit xuất hiện hai lần. 2. Tính E (A) J và viết kết quả thành một chuỗi 8 xâu 6 bit = B1B 2B 3B 4B 5B 6 . 3. Bước tiếp theo dùng 8 bảng S1,S 2 , ,S 8 (được gọi là các hộp S ). Với mỗi S i là một bảng 4 16 cố định có các hàng là các số nguyên từ 0 đến 15. Với xâu bit có độ dài 6 (kí hiệu B bb b b b b ), ta tính S (B )như sau: hai bit bb xác định biểu diễn nhị i 1 2 3 PTIT4 5 6 j j 1 6 phân của hàng r của S i (0 r 3) và bốn bit b2b3b4b5 xác định biểu diễn nhị phân của cột c của S i (0 c 15) . Khi đó, S j (B j )sẽ xác định phần tử S j (r,c) ; phần tử này viết dưới dạng nhị phân là một xâu bit có độ dài 4. (Bởi vậy, mỗi S j có thể được coi là một hàm mã mà đầu vào là một xâu bit có độ dài 2 và một xâu bit có độ dài 4, còn đầu ra là một xâu bit có độ dài 4). Bằng cách tương tự tính các C j S j (B j ), 1 j 8. 4. Xâu bit C C 1C 2 C 8 có độ dài 32 được hoán vị theo phép hoán vị cố định P . Xâu kết quả là P (C ) được xác định là f (A,J ) . 54
  63. Chương 2 – Mật mã khóa bí mật A J E E(A) B1 B 2 B 3 B 4 B 5 B 6 B 7 B 8 S1 S 2 S 3 S 4 S 5 S 6 S 7 S 8 C 1 C 2 C 3 C 4 C 5 C 6 C 7 C 8 P f (A,J ) Hình 2.14. Hàm f của DES Hàm f được mô tả trong Hình 2.14. Chủ yếu nó gồm một phép thế (sử dụng hộp S), tiếp sau đó là phép hoán vị P. 16 phép lặp của f sẽ tạo nên một hệ mật tích nêu như ở mục 2.6. Trong phần còn lại của mục này, ta sẽ mô tả hàm cụ thể được dùng trong DES. Phép hoán vị ban đầu IP như sau: Bảng 2.4. Bảng IP của DES IP 58 50 42 34 26 18 10 2 60 52 44 36 28 20 12 4 62 54 46 38 30 22 14 6 PTIT64 56 48 40 32 24 16 8 57 49 41 33 25 17 9 1 59 51 43 35 27 19 11 3 61 53 45 37 29 21 13 5 63 55 47 39 31 23 15 7 Bảng này có nghĩa là bit thứ 58 của x là bit đầu tiên của IP(x ) ; bit thứ 50 của x là bit thứ hai của IP(x ) .v.v Phép hoán vi ngược IP 1 là: 55
  64. Chương 2 – Mật mã khóa bí mật Bảng 2.5. Bảng IP 1 của DES IP -1 40 8 48 16 56 24 64 32 39 7 47 15 55 23 63 31 38 6 46 14 54 22 62 30 37 5 45 13 53 21 61 29 36 4 44 12 52 20 60 28 35 3 43 11 51 19 59 27 34 2 42 10 50 18 58 26 33 1 41 9 49 17 57 25 Hàm mở rộng E được xác đinh theo bảng sau: Bảng 2.6. Hàm mở rộng E của DES Bảng chọn E bit 32 1 2 3 4 5 4 5 6 7 8 9 8 9 10 11 12 13 12 13 14 15 16 17 16 17 18 19 20 21 20 21 22 23 24 25 24 25 26 27 28 29 28 29 30 31 32 1 Tám hộp S như sau: S1 14 4 13 1 2 15 11 8 3 10 6 12 5 9 0 7 0 15 7 4 14 2 13 1 10 6 12 11 9 5 3 8 4 1 14 8 13 6 2 11 15 12 9 7 3 10 5 0 15 12 8 2 4 9 1 7 5 11 3 14 10 0 6 13 PTITS2 15 1 8 14 6 11 3 4 9 7 2 13 12 0 5 10 3 13 4 7 15 2 8 14 12 0 1 10 6 9 11 5 0 14 7 11 10 4 13 1 5 8 12 6 9 3 2 15 13 8 10 1 3 15 4 2 11 6 7 12 0 5 14 9 S3 10 0 9 14 6 3 15 5 1 13 12 7 11 4 2 8 13 7 0 9 3 4 6 10 2 8 5 14 12 11 15 1 13 6 4 9 8 15 3 0 11 1 2 12 5 10 14 7 1 10 13 0 6 9 8 7 4 15 14 3 11 5 2 12 56
  65. Chương 2 – Mật mã khóa bí mật S4 7 13 14 3 0 6 9 10 1 2 8 5 11 12 4 15 13 8 11 5 6 15 0 3 4 7 2 12 1 10 14 9 10 6 9 0 12 11 7 13 15 1 3 14 5 2 8 4 3 15 0 6 10 1 13 8 9 4 5 11 12 7 2 14 S5 2 12 4 1 7 10 11 6 8 5 3 15 13 0 14 9 14 11 2 12 4 7 13 1 5 0 15 10 3 9 8 6 4 2 1 11 10 13 7 8 15 9 12 5 6 3 0 14 11 8 12 7 1 14 2 13 6 15 0 9 10 4 5 3 S6 12 1 10 15 9 2 6 8 0 13 3 4 14 7 15 11 10 15 4 2 7 12 9 5 6 1 13 14 0 11 3 8 9 14 15 5 2 8 12 3 7 0 4 10 1 13 11 6 4 3 2 12 9 5 15 10 11 14 1 7 6 0 8 13 S7 4 11 2 14 15 0 8 13 3 12 9 7 5 10 6 1 13 0 11 7 4 9 1 10 14 3 5 12 2 15 8 6 1 4 11 13 12 3 7 14 10 15 6 8 0 5 9 2 6 11 13 8 1 4 10 7 9 5 0 15 14 2 3 12 S8 13 2 8 4 6 15 11 1 10 9 3 14 5 0 12 7 1 15 13 8 10 3 7 4 12 5 6 11 0 14 9 2 7 11 4 1 9 12 14 2 0 6 10 13 15 3 5 8 2 1 14 7 4 10 8 13 15 12 9 0 3 5 6 11 Và phép hoán vị P có dPTITạng: Bảng 2.7. Phép hoàn vị P trong hàm f của DES P 16 7 20 21 29 12 28 17 1 15 23 26 2 8 24 14 5 18 31 10 32 27 3 9 19 13 30 6 22 11 4 25 57