Giáo trình Lý thuyết mật mã và an toàn thông tin - Phan Đình Diệu

Nội dung text: Giáo trình Lý thuyết mật mã và an toàn thông tin - Phan Đình Diệu

1. Đại học quốc gia hà nội Khoa công nghệ Phan Đình Diệu Lý thuyết mật mã & an toàn thông tin NXB đại học quốc gia hà nội - 2002 1
2. Lý thuyết mật mã & An toàn thông tin 2
3. Lý thuyết mật mã & An toàn thông tin Phan Đình Diệu Đại học Quốc gia Hà Nội Khoa Công nghệ- ĐHQG Hà nội 3
4. Nội dung Lời mở đầu 4 Ch−ơng 1 Giới thiệu chung về mật mã 8 1.1. Sơ lựoc lịch sử về khoa mật mã 8 1.2. Hệ thống mật mã. Mã theo khối và mã theo dòng 12 1.3. Mật mã khóa đối xứng và mật mã có khóa công khai 15 1.4. Các bài toán an toàn thông tin 16 1.5. Thám mã và tính an toàn của các hệ mật mã 18 Ch−ơng 2. Cơ sở toán học của lý thuyết mật mã 20 2.1.Số học các số nguyên.Thuật toán Euclide 20 2.2. Xác suất và thuật toán xác suất 31 2.3. Độ phức tạp tính toán 36 2.4.Số nguyên tố. Phân tích thành thừa số.Lôgarit rời rạc 42 1
5. Ch−ơng 3 Các hệ mật mã khoá đối xứng 55 3.1. Các hệ mật mã cổ điển 55 3.2. Thám mã đối với các hệ mật mã cổ điển 63 3.3. Mật mã theo dòng và các dãy số giả ngẫu nhiên 72 3.4. Hệ mật mã chuẩn DES 80 Ch−ơng 4 Các hệ mật mã khoá công khai 92 4.1. Giới thiệu mở đầu 92 4.1. Hệ mật mã khoá công khai RSA 97 4.2. Hệ mật mã khoá công khai Rabin 101 4.3. Hệ mật mã khoá công khai ElGamal 103 4.4. Các hệ mật mã dựa trên các bài toán NP-đầy đủ 107 4.5. Các hệ mật mã xác suất khoá công khai 111 Ch−ơng 5 Bài toán xác nhận và Chữ ký điện tử 115 5.1. Bài toán xác nhận và sơ đồ chữ ký 115 5.2. Sơ đồ chữ ký ElGamal và chuẩn chữ ký điệ tử 118 5.3. Hàm băm và chữ ký 122 5.4. Một số sơ đồ chữ ký khác 127 5.5.Chữ ký không phủ định đ−ợc&không chối bỏ đ−ợc 131 2
6. Ch−ơng 6 Các sơ đồ x−ng danh và xác nhận danh tính 136 6.1. Vấn đề x−ng danh 136 6.2. Sơ đồ x−ng danh Schnorr 137 6.3. Sơ đồ x−ng danh Okamoto 140 6.4. Sơ đồ x−ng danh Guillou-Quisquater 142 6.5. Giao thức Feige-Fiat-Shamir 145 6.6. Phép chứng minh không lộ tri thức 147 Ch−ơng 7 Vấn đề phân phối khoá và thoả thuận khoá 152 7.1. Quản trị khoá trong các mạng truyền tin 152 7.2. Một số hệ phân phối khoá 153 7.3. Trao đổi khoá và thoả thuận khoá 157 Chú dẫn về tài liệu tham khảo 163 3
7. Lời mở đầu Từ khi con ng−ời có nhu cầu trao đổi thông tin, th− từ cho nhau thì nhu cầu giữ bí mật và bảo vệ tính riêng t− của những thông tin, th− từ đ−ợc trao đổi đó cũng nẩy sinh. Hình thức thông tin đ−ợc trao đổi phổ biến và sớm nhất là d−ới dạng các văn bản, để giữ bí mật của thông tin ng−ời ta đã sớm nghĩ đến cách che dấu nội dung các văn bản bằng cách biến dạng các văn bản đó để ng−ời ngoài không đọc hiểu đ−ợc, đồng thời có cách khôi phục lại nguyên dạng ban đầu để ng−ời trong cuộc vẫn đọc hiểu đ−ợc; theo cách gọi ngày nay thì dạng biến đổi của văn bản đ−ợc gọi là mật mã của văn bản, cách lập mật mã cho một văn bản đ−ợc gọi là phép lập mật mã, còn cách khôi phục lại nguyên dạng ban đầu của văn bản từ bản mật mã đ−ợc gọi là phép giải mã. Phép lập mật mã và phép giải mã đ−ợc thực hiện nhờ một chìa khoá riêng nào đó mà chỉ những ng−ời trong cuộc đ−ợc biết, sau đây ta sẽ gọi là khoá mật mã. Ng−ời ngoài cuộc không đ−ợc biết khoá mật mã, nên dù có "ăn cắp" đ−ợc bản mật mã trên đ−ờng truyền tin, về nguyên tắc cũng không thể giải mã để hiểu đ−ợc nội dung của văn bản truyền đi. Hiển nhiên, tiêu chuẩn của một bản mật mã là tạo đ−ợc tính bí mật cho văn bản; vì vậy khái niệm bí mật là khái niệm cốt lõi nhất đối với một lý thuyết về mật mã. Có thể có một định nghĩa khoa học cho khái niệm bí mật hay không? Đã có nhiều cách tiếp cận để tìm hiểu nội dung của khái niệm bí mật, nh−ng một định nghĩa khoa học, hay hơn nữa, một định nghĩa toán học cho khái niệm đó thì ch−a có. Một cách tiếp cận khá phổ biến là gắn khái niệm bí mật với khái niệm "ngẫu nhiên", nếu một văn bản rõ có một nội dung xác định thì điều ta mong muốn là bản mật mã của nó phải là một bản gồm các ký tự đ−ợc sắp xếp hỗn độn, có vẻ nh− ngẫu nhiên khiến 4
8. ng−ời ngoài nhìn vào không thể xác định đ−ợc nội dung của văn bản gốc. Tuy nhiên, nếu "bí mật" là khái niệm ch−a định nghĩa đ−ợc, thì khái niệm "ngẫu nhiên", hay cụ thể hơn, khái niệm "dãy bit ngẫu nhiên", cũng khó định nghĩa nh− vậy, ta ch−a qui định đ−ợc một tiêu chuẩn toán học để xác định một dãy bit có là "ngẫu nhiên" hay không, mà chỉ mới tìm hiểu đ−ợc một số thuộc tính gần với "ngẫu nhiên", dùng làm căn cứ để tạm xác định một dãy bit có là "giả ngẫu nhiên" theo nghĩa có các thuộc tính đó hay không mà thôi. Từ mấy thập niên gần đây, b−ớc vào kỷ nguyên máy tính, cũng nh− đối với nhiều lĩnh vực khác, lĩnh vực mật mã cũng đã có những chuyển biến to lớn từ giai đoạn mật mã truyền thống sang giai đoạn mật mã máy tính; máy tính điện tử đ−ợc sử dụng ngày càng phổ biến trong việc lập mật mã, giải mật mã, và những chuyển biến đó đã kích thích việc nghiên cứu các giải pháp mật mã, biến việc nghiên cứu mật mã thành một khoa học có đối t−ợng ngày càng rộng lớn và đ−ợc sử dụng có hiệu quả trong nhiều phạm vi hoạt động của cuộc sống. Vì các nghiệp vụ chủ yếu của mật mã đ−ợc thực hiện bằng máy tính, nên các khái niệm bí mật, ngẫu nhiên cũng dần đ−ợc "máy tính hoá", và với sự ra đời của Lý thuyết về độ phức tạp tính toán vào giữa những năm 1960, các khái niệm đó tìm đ−ợc một nội dung chung có thể đ−ợc nghiên cứu một cách toán học là tính phức tạp. Bây giờ ta có thể nói, một bản mật mã đối với anh là bí mật, nếu từ bản mật mã đó để tìm ra bản rõ anh phải thực hiện một tiến trình tính toán mà độ phức tạp của nó v−ợt quá mọi năng lực tính toán (kể cả mọi máy tính) của anh; một dãy bit có thể xem là ngẫu nhiên , nếu dựa vào một đoạn bit đã biết để tìm một bit tiếp theo của dãy anh cũng phải thực hiện một tiến trình tính toán có độ phức tạp cực lớn t−ơng tự nh− nói trên. Việc chuyển sang giai đoạn mật mã máy tính tr−ớc hết đã có tác dụng phát triển và hiện đại hoá nhiều hệ thống mật mã theo kiểu truyền thống, làm cho các hệ thống đó có các cấu trúc tinh tế hơn, đòi hỏi lập mật mã và giải mã phức tạp hơn, do đó hiệu quả giữ bí mật của các giải pháp mật mã đ−ợc nâng cao hơn tr−ớc rất nhiều. Tuy nhiên, một b−ớc chuyển có tính chất cách mạng mà mật mã máy tính mang lại là việc phát minh ra các hệ mật mã có khoá công khai, bắt đầu từ cuối những năm 1970, cơ sở lý thuyết của các phát 5
9. minh đó là sự tồn tại của các hàm một phía (one-way function), tức là những hàm số số học y = f (x) mà việc tính theo phía thuận từ x tính y là t−ơng đối dễ, nh−ng việc tính theo phía ng−ợc từ y tìm lại x (x = f 1(y)) là cực kỳ phức tạp. Các hệ mật mã có khoá công khai đã làm thay đổi về bản chất việc tổ chức các hệ truyền thông bảo mật, làm dễ dàng cho việc bảo mật trên các hệ truyền thông công cộng, và do tính chất đặc biệt đó chúng đã là cơ sở cho việc phát triển nhiều giao thức an toàn thông tin khác khi sử dụng mạng truyền thông công cộng, chẳng hạn các loại giao thức về xác nhận nguồn tin và định danh ng−ời gửi, chữ ký điện tử, các giao thức xác nhận không để lộ thông tin gì khác ngoài việc xác nhận, các giao thức trao đổi khoá trong tổ chức truyền tin bảo mật và trong xác nhận, v.v , và gần đây trong việc phát triển nhiều giao thức đặc thù khác trong các giao dịch ngân hàng và th−ơng mại điện tử, phát hành và mua bán bằng tiền điện tử, Cũng cần nói thêm là lý thuyết mật mã hiện đại, tức là mật mã máy tính trên cơ sở lý thuyết về độ phức tạp tính toán tuy có nhiều ứng dụng đặc sắc và có triển vọng to lớn, nh−ng cũng mới đang trong giai đoạn phát triển b−ớc đầu, còn phải khắc phục nhiều khó khăn và tìm kiếm thêm nhiều cơ sở vững chắc mới để tiếp tục hoàn thiện và phát triển. Chẳng hạn, nh− trên đã nói, một cơ sở quan trọng của lý thuyết mật mã hiện đại là sự tồn tại của các hàm một phía, nh−ng ngay có thật tồn tại các hàm một phía hay không cũng còn là một bài toán ch−a có câu trả lời! Ta chỉ mới đang có một số hàm một phía theo sự hiểu biết của con ng−ời hiện nay, nh−ng ch−a chứng minh đ−ợc có một hàm cụ thể nào đó chắc chắn là hàm một phía! Tuy nhiên, nếu theo quan điểm khoa học hiện đại, ta không xem mục đích khoa học là đi tìm những chân lý chắc chắn tuyệt đối, mà là đi tìm những cách giải quyết vấn đề (problem solving) gặp trong thực tiễn, thì ta vẫn có thể tin vào những giải pháp "t−ơng đối" rất có hiệu quả mà lý thuyết hiện đại về mật mã đang cống hiến cho con ng−ời hiện nay. Tập giáo trình Lý thuyết mật mã và an toàn thông tin này đ−ợc soạn để phục vụ cho việc học tập của sinh viên các lớp theo ch−ơng trình đại học hoặc cao học thuộc ngành Công nghệ thông tin của Đại học Quốc gia Hà nội. Trong khoảng m−ơi năm gần đây, trên thế giới đã xuất hiện nhiều sách và tài liệu có tính chất giáo khoa 6
10. hoặc tham khảo về lý thuyết mật mã hiện đại và ứng dụng. Ng−ời viết tập giáo trình này chỉ có cố gắng lựa chọn và sắp xếp một số nội dung mà mình nghĩ là cần thiết và thích hợp nhất để trong một phạm vi hạn chế về thời gian (và không gian) trình bày và giới thiệu đ−ợc cho ng−ời học một cách t−ơng đối hệ thống những kiến thức cơ bản về lý thuyết mật mã hiện đại, bao gồm cả một số kiến thức toán học cần thiết. Giáo trình này đã đ−ợc giảng dạy cho sinh viên các khoá cao học về Công nghệ thông tin thuộc Đại học Bách khoa Hà nội và khoa Công nghệ Đại học Quốc gia Hà nội từ năm 1997 đến 2004. Ng−ời viết chân thành cảm ơn các bạn đồng nghiệp và ng−ời đọc chỉ cho những chỗ thiếu sót để có thể kịp thời sửa chữa cho những lần in sau, nếu có. Tháng 12 năm 2002 Phan Đình Diệu 7
11. CHƯƠNG I Giới thiệu chung về mật mã 1.1. Sơ l−ợc lịch sử về mật mã. Nh− đã giới thiệu trong Lời mở đầu, nhu cầu sử dụng mật mã đã xuất hiện từ rất sớm, khi con ng−ời biết trao đổi và truyền đ−a thông tin cho nhau, đặc biệt khi các thông tin đó đã đ−ợc thể hiện d−ới hình thức ngôn ngữ, th− từ. Lịch sử cho ta biết, các hình thức mật mã sơ khai đã đ−ợc tìm thấy từ khoảng bốn nghìn năm tr−ớc trong nền văn mịnh Ai cập cổ đại. Trải qua hàng nghìn năm lịch sử, mật mã đã đ−ợc sử dụng rộng rãi trên khắp thế giới từ Đông sang Tây để giữ bí mật cho việc giao l−u thông tin trong nhiều lĩnh vực hoạt động giữa con ng−ời và các quốc gia, đặc biệt trong các lĩnh vực quân sự, chính trị, ngoại giao. Mật mã tr−ớc hết là một loại hoạt động thực tiễn, nội dung chính của nó là để giữ bí mật thông tin (chẳng hạn d−ới dạng một văn bản) từ một ng−ời gửi A đến một ng−ời nhận B, A phải tạo cho văn bản đó một bản mã mật t−ơng ứng, và thay vì gửi văn bản rõ thì A chỉ gửi cho B bản mã mật, B nhận đ−ợc bản mã mật và sẽ có cách từ đó khôi phục lại văn bản rõ để hiểu đ−ợc thông tin mà A muốn gửi cho mình. Vì bản gửi đi th−ờng đ−ợc chuyển qua các con đ−ờng công khai nên ng−ời ngoài có thể "lấy trộm" đ−ợc, nh−ng do đó là bản mật mã nên không đọc hiểu đ−ợc, còn A có thể tạo ra bản mã mật và B có thể giải bản mã mật thành bản rõ để hiểu đ−ợc là do giữa hai ng−ời đã có một thỏa thuận về một chìa khóa chung, chỉ với chìa khóa chung này thì A mới tạo đ−ợc bản mã mật từ bản rõ, và B mới từ bản mã mật khôi phục lại đ−ợc bản rõ. Sau này ta sẽ gọi đơn giản chìa khóa chung đó là khóa mật mã. Tất nhiên để thực hiện đ−ợc một phép mật mã, ta 8
12. còn cần có một thuật toán biến bản rõ, cùng với khóa mật mã, thành bản mã mật, và một thuật toán ng−ợc lại, biến bản mã mật, cùng với khóa mật mã, thành bản rõ. Các thuật toán đó đ−ợc gọi t−ơng ứng là thuật toán lập mật mã và thuật toán giải mật mã. Các thuật toán này th−ờng không nhất thiết phải giữ bí mật, mà cái cần đ−ợc giữ tuyệt mật luôn luôn là khóa mật mã. Trong thực tiễn, đã có hoạt động bảo mật thì cũng có hoạt động ng−ợc lại là khám phá bí mật từ các bản mã mật "lấy trộm" đ−ợc, ta th−ờng gọi hoạt động này là mã thám, hoạt động này quan trọng không kém gì hoạt động bảo mật! Vì các thuật toán lập mật mã và giải mật mã không nhất thiết là bí mật, nên mã thám th−ờng đ−ợc tập trung vào việc tìm khóa mật mã, do đó cũng có ng−ời gọi công việc đó là phá khóa. Suốt mấy nghìn năm lịch sử, các thông báo, th− từ đ−ợc truyền đ−a và trao đổi với nhau th−ờng là các văn bản, tức là có dạng các dãy ký tự trong một ngôn ngữ nào đó; vì vậy, các thuật toán lập mật mã th−ờng cũng đơn giản là thuật toán xáo trộn, thay đổi các ký tự đ−ợc xác định bởi các phép chuyển dịch, thay thế hay hoán vị các ký tự trong bảng ký tự của ngôn ngữ t−ơng ứng; khóa mật mã là thông tin dùng để thực hiện phép lập mật mã và giải mật mã cụ thể, thí dụ nh− số vị trí đối với phép chuyển dịch, bảng xác định các cặp ký tự t−ơng ứng đối với phép thay thế hay hoán vị, Mật mã ch−a phải là một khoa học, do đó ch−a có nhiều kiến thức sách vở để lại, tuy nhiên hoạt động bảo mật và thám mã trong lịch sử các cuộc đấu tranh chính trị, ngoại giao và quân sự thì hết sức phong phú, và mật mã đã có nhiều tác động rất quan trọng đ−a đến những kết quả lắm khi có ý nghĩa quyết định trong các cuộc đấu tranh đó. Do trong một thời gian dài, bản thân hoạt động mật mã cũng đ−ợc xem là một bí mật, nên các tài liệu kỹ thuật về mật mã đ−ợc phổ biến đến nay th−ờng chỉ ghi lại các kiến thức kinh nghiệm, thỉnh thoảng mới có một vài "phát minh" nh− các hệ mật mã Vigenère vào thế kỷ 16 hoặc hệ mật mã Hill ra đời năm 1929 là các hệ mã thực hiện phép chuyển dịch (đối với mã Vigenère) hay phép thay thế (mã Hill) đồng thời trên một nhóm ký tự chứ không phải trên từng ký tự riêng rẽ. Vấn đề thám mã, ng−ợc lại, khi thành công th−ờng đ−a đến những cống hiến nổi trội và ấn t−ợng trong những 9
13. tình huống gay cấn của các cuộc đấu tranh, và cũng th−ờng đòi hỏi nhiều tài năng phát hiện với những kinh nghiệm và suy luận tinh tế hơn, nên để lại nhiều chuyện hấp dẫn hơn. Nhiều câu chuyện kỳ thú của lịch sử thám mã đã đ−ợc thuật lại trong quyển sách nổi tiếng của David Kahn The Codebreakers . The Story of Secret Writing , xuất bản năm 1967 (sách đã đ−ợc dịch ra nhiều thứ tiếng, có bản dịch tiếng Việt Những ng−ời mã thám, 3 tập, xuất bản tại Hà nội năm 1987). B−ớc sang thế kỷ 20, với những tiến bộ liên tục của kỹ thuật tính toán và truyền thông, ngành mật mã cũng đã có những tiến bộ to lớn. Vào những thập niên đầu của thế kỷ, sự phát triển của các kỹ thuật biểu diễn, truyền và xử lý tín hiệu đã có tác động giúp cho các hoạt động lập và giải mật mã từ thủ công chuyển sang cơ giới hóa rồi điện tử hóa. Các văn bản, các bản mật mã tr−ớc đây đ−ợc viết bằng ngôn ngữ thông th−ờng nay đ−ợc chuyển bằng kỹ thuật số thành các dãy tín hiệu nhị phân, tức các dãy bit, và các phép biến đổi trên các dãy ký tự đ−ợc chuyển thành các phép biến đổi trên các dãy bit, hay các dãy số, việc thực hiện các phép lập mã, giải mã trở thành việc thực hiện các hàm số số học. Toán học và kỹ thuật tính toán bắt đầu trở thành công cụ cho việc phát triển khoa học về mật mã. Khái niệm trung tâm của khoa học mật mã là khái niệm bí mật. Đó là một khái niệm phổ biến trong đời sống, nh−ng liệu có thể cho nó một nội dung có thể định nghĩa đ−ợc một cách toán học không? Nh− đã l−ợc qua trong Lời mở đầu, khái niệm bí mật thoạt đầu đ−ợc gắn với khái niệm ngẫu nhiên, rồi về sau trong những thập niên gần đây, với khái niệm phức tạp, cụ thể hơn là khái niệm độ phức tạp tính toán. Việc sử dụng lý thuyết xác suất và ngẫu nhiên làm cơ sở để nghiên cứu mật mã đã giúp C.Shannon đ−a ra khái niệm bí mật hoàn toàn của một hệ mật mã từ năm 1948, khởi đầu cho một lý thuyết xác suất về mật mã. Trong thực tiễn làm mật mã, cácdãy bit ngẫu nhiên đ−ợc dùng để trộn với bản rõ (d−ới dạng một dãy bit xác định) thành ra bản mật mã. Làm thế nào để tạo ra các dãy bit ngẫu nhiên? Có thể tạo ra bằng ph−ơng pháp vật lý đơn giản nh− sau: ta tung đồng xu lên, nếu đồng xu rơi xuống ở mặt sấp thì ta ghi bit 0, ở mặt ngửa thì ta ghi bit 1; tung n lần ta sẽ đ−ợc một dãy n 10
14. bit, dãy bit thu đ−ợc nh− vậy có thể đ−ợc xem là dãy bit ngẫu nhiên. Nh−ng tạo ra theo cách nh− vậy thì khó có thể sử dụng một cách phổ biến, vì không thể tìm ra qui luật để theo đó mà sinh ra dãy bit ngẫu nhiên đ−ợc. ở đây ta gặp một khó khăn có tính bản chất: nếu có qui luật thì đã không còn là ngẫu nhiên nữa rồi! Nh− vậy, nếu ta muốn tìm theo qui luật, thì không bao giờ có thể tìm ra các dãy bit ngẫu nhiên, mà cùng lắm cũng chỉ có thể đ−ợc các dãy bit gần ngẫu nhiên, hay giả ngẫu nhiên, mà thôi. Từ nhiều chục năm nay, ng−ời ta đã nghiên cứu đề xuất nhiều thuật toán toán học để sinh ra các dãy bit giả ngẫu nhiên, và cũng đã đ−a ra nhiều thuộc tính để đánh giá một dãy bit giả ngẫu nhiên có đáng đ−ợc xem là "gần" ngẫu nhiên hay không. Một vài thuộc tính chủ yếu mà ng−ời ta đã đề xuất là: cho một dãy bit X = (x1,x2, ,xn, ); dãy đó đ−ợc xem là giả ngẫu nhiên "tốt" nếu xác suất xuất hiện bit 0 hay bit 1 trong toàn dãy đó cũng nh− trong mọi dãy con bất kỳ của nó đều bằng 1/2; hoặc một tiêu chuẩn khác: nếu mọi ch−ơng trình sinh ra đ−ợc đoạn đầu n bit của dãy đều phải có độ phức tạp (hay độ dài) cỡ n ký tự ! Về sau này, khi lý thuyết về độ phức tạp tính toán đã đ−ợc phát triển thì tiêu chuẩn về ngẫu nhiên cũng đ−ợc qui về tiêu chuẩn phức tạp tính toán, cụ thể một dãy bit X đ−ợc xem là giả ngẫu nhiên "tốt" nếu mọi thuật toán tìm đ−ợc bit thứ n (xn) khi biết các bit tr−ớc đó (x1,, ,xn-1) với xác suất đúng > 1/2 đều phải có độ phức tạp tính toán thuộc lớp NP-khó! Lý thuyết về độ phức tạp tính toán ra đời từ giữa những năm 1960 đã cho ta một cách thích hợp để qui yêu cầu bí mật hoặc ngẫu nhiên về một yêu cầu có thể định nghĩa đ−ợc là yêu cầu về độ phức tạp tính toán. Bây giờ ta có thể nói: một giải pháp mật mã là bảo đảm bí mật, nếu mọi thuật toán thám mã, nếu có, đều phải đ−ợc thực hiện với độ phức tạp tính toán cực lớn! Cực lớn là bao nhiêu? Là v−ợt quá giới hạn khả năng tính toán (bao gồm cả máy tính) mà ng−ời thám mã có thể có. Về lý thuyết, có thể xem đó là những độ phức tạp tính toán với tốc độ tăng v−ợt quá hàm mũ, hoặc thuộc loại NP-khó. Tuy nhiên, lý thuyết độ phức tạp tính toán không chỉ cống hiến cho ta một khái niệm để giúp chính xác hóa tiêu chuẩn bí mật của các giải pháp mật mã, mà còn mở ra một giai đoạn mới của ngành mật mã, biến ngành mật mã thành một khoa học có nội dung 11
15. lý luận phong phú và có những ứng dụng thực tiễn quan trọng trong nhiều lĩnh vực của đời sống hiện đại. B−ớc ngoặt có tính cách mạng trong lịch sử khoa học mật mã hiện đại xẩy ra vào năm 1976 khi hai tác giả Diffie và Hellman đ−a ra khái niệm về mật mã khóa công khai và một ph−ơng pháp trao đổi công khai để tạo ra một khóa bí mật chung mà tính an toàn đ−ợc bảo đảm bởi độ khó của một bài toán toán học cụ thể (là bài toán tính "lôgarit rời rạc"). Hai năm sau, năm 1978, Rivest, Shamir và Adleman tìm ra một hệ mật mã khóa công khai và một sơ đồ chữ ký điện tử hoàn toàn có thể ứng dụng trong thực tiễn, tính bảo mật và an toàn của chúng đ−ợc bảo đảm bằng độ phức tạp của một bài toán số học nổi tiếng là bài toán phân tích số nguyên thành các thừa số nguyên tố. Sau phát minh ra hệ mật mã đó (mà nay ta th−ờng gọi là hệ RSA), việc nghiên cứu để phát minh ra các hệ mật mã khóa công khai khác, và ứng dụng các hệ mật mã khóa công khai vào các bài toán khác nhau của an toàn thông tin đã đ−ợc tiến hành rộng rãi, lý thuyết mật mã và an toàn thông tin trở thành một lĩnh vực khoa học đ−ợc phát triển nhanh trong vài ba thập niên cuối của thế kỷ 20, lôi cuốn theo sự phát triển của một số bộ môn của toán học và tin học. Trong các ch−ơng về sau của tập giáo trình này ta sẽ lần l−ợt làm quen với một số thành quả chủ yếu của lý thuyết đó. 1.2. Các hệ thống mật mã. 1.2.1. Sơ đồ hệ thống mật mã. Mật mã đ−ợc sử dụng để bảo vệ tính bí mật của thông tin khi thông tin đ−ợc truyền trên các kênh truyền thông công cộng nh− các kênh b−u chính, điện thoại, mạng truyền thông máy tính, mạng Internet, v.v Giả thử một ng−ời gửi A muốn gửi đến một ng−ời nhận B một văn bản (chẳng hạn, một bức th−) p, để bảo mật A lập cho p một bản mật mã c, và thay cho việc gửi p, A gửi cho B bản mật mã c, B nhận đ−ợc c và "gíải mã" c để lại đ−ợc văn bản p nh− A định gửi. Để A biến p thành c và B biến ng−ợc lại c thành p , A và B phải thỏa thuận tr−ớc với nhau các thuật toán lập mã và giải mã, và đặc biệt một khóa mật mã chung K để thực hiện các thuật toán đó. Ng−ời ngoài, không biết các thông tin đó (đặc biệt, không biết khóa 12
16. K), cho dù có lấy trộm đ−ợc c trên kênh truyền thông công cộng, cũng không thể tìm đ−ợc văn bản p mà hai ng−ời A, B muốn gửi cho nhau. Sau đây ta sẽ cho một định nghĩa hình thức về sơ đồ mật mã và cách thức thực hiện để lập mật mã và giải mật mã. Định nghĩa 1.2.1. Một sơ đồ hệ thống mật mã là một bộ năm S = (P , C , K , E , D ) (1) thỏa mãn các điều kiện sau đây: P là một tập hữu hạn các ký tự bản rõ, C là một tập hữu hạn các ký tự bản mã, K là một tập hữu hạn các khóa, E là một ánh xạ từ KxP vào C , , đ−ợc gọi là phép lập mật mã; và D là một ánh xạ từ KxC vào P , đ−ợc gọi là phép giải mã. Với mỗi K∈K , ta định nghĩa eK : P →C , dK :C →P là hai hàm cho bởi : ⎠x εP : eK(x) = E (K,x) ; ⎠yε C : dK(y) = D (K,y). eK và dK đ−ợc gọi lần l−ợt là hàm lập mã và hàm giải mã ứng với khóa mật mã K. Các hàm đó phải thỏa mãn hệ thức: ⎠x ε P : dK(eK(x)) = x. Về sau, để thuận tiện ta sẽ gọi một danh sách (1) thoả mãn các tính chất kể trên là một sơ đồ hệ thống mật mã , còn khi đã chọn cố định một khoá K, thì danh sách (P , C , eK , dK) là một hệ mật mã thuộc sơ đồ đó. Trong định nghĩa này, phép lập mật mã (giải mã) đ−ợc định nghĩa cho từng ký tự bản rõ (bản mã). Trong thực tế, bản rõ của một thông báo th−ờng là một dãy ký tự bản rõ, tức là phần tử của tập P *, và bản mật mã cũng là một dãy các ký tự bản mã, tức là phần tử của tập C *, việc mở rộng các hàm eK và dK lên các miền t−ơng ứng P * và C * để đ−ợc các thuật toán lập mật mã và giải mã dùng trong thực tế sẽ đ−ợc trình bày trong tiết sau. Các tập ký tự bản rõ và bản mã th−ờng dùng là các tập ký tự của ngôn ngữ thông th−ờng nh− tiếng Việt, tiếng Anh (ta ký hiệu tập ký tự tiếng Anh là A tức A = {a,b,c, ,x,y,z } gồm 26 ký tự; tập ký tự nhị phân B chỉ gồm hai ký tự 13
17. 0 và 1; tập các số nguyên không âm bé hơn một số n nào đó (ta ký hiệu tập này là Zn tức Zn = {0,1,2, , n- 1}). Chú ý rằng có thể xem B = Z2. Để thuận tiện, ta cũng th−ờng đồng nhất tập ký tự tiếng Anh A với tập gồm 26 số nguyên không âm đầu tiên Z26 = {0,1,2, , 24,25} với sự t−ơng ứng sau đây: a b c d e f g h i j k l m n o p q r s t u v w x y z 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25. Đôi khi ta cũng dùng với t− cách tập ký tự bản rõ hay bản mã là các m m m tập tích của các tập nói trên, đặc biệt là các tập A , B , Zn . 1.2.2. Mã theo khối và mã theo dòng. Nh− nói ở trên, bản rõ của thông báo mà ta muốn gửi đi th−ờng là một dãy ký tự, trong khi theo định nghĩa của sơ đồ mật mã, hàm lập mật mã và hàm giải mã đ−ợc định nghĩa cho từng ký tự. Từ các định nghĩa của hàm lập mật mã và hàm giải mã, ta mở rộng thành thuật toán lập mã (và giải mã) xác định cho mọi bản rõ (bản mã) nh− sau: Theo cách mã theo khối (block cipher), tr−ớc hết ta xác định một độ dài khối (chẳng hạn là k), tiếp đó mở rộng không gian khóa k k từ K thành K , và với mỗi K =K1 Kk ε K , ta mở rộng eK và dK k k k k thành các thuật toán eK : P → C và dK : C →P nh− sau: với mọi k k x1 xk ∈P và y1 yk ∈C ta có exKk( 11 x) = eK(x) eK(xk); dyK ( 11 ykK) = d(y) dK(yk) . 1 k 1 k Giả thử bản rõ mà ta muốn lập mật mã cho nó là dãy ký tự X∈ P * .Ta cắt X thành từng khối, mỗi khối có độ dài k, khối cuối cùng có thể có độ dài <k, ta luôn có thể giả thiết là có thể bổ sung vào phần cuối của khối một số ký tự qui −ớc nào đó để nó cũng có độ dài k. Do đó ta có thể giả thiết X = X1 Xm , trong đó mỗi X1, ,Xm là một khối có độ dài k. Và ta định nghĩa bản mật mã của X là: eK(X) = eK(X1 Xm ) = eK(X1) eK(Xm). Đặt Y = eK(X1) eK(Xm), ta có thể viết Y = Y1 Ym với Yi =eK(Xi), và do đó có 14
18. dK(Y) = dK(Y1) dK(Ym) = X1 Xm = X. Cách mã theo khối đơn giản và thông dụng nhất là khi ta chọn độ dài khối k =1. Khi đó với mọi bản rõ X = x1 xm ∈ P * ta có eK(X) = eK(x1 xm ) = eK(x1) eK(xm). Với cách mã theo dòng (stream cipher), tr−ớc hết ta phải xác * định một dòng khóa, tức là một phần tử K = K1 Km ∈ K , với dòng khóa đó ta xác định với mọi bản rõ X = x1 xm ∈ P * bản mã t−ơng ứng là e (X) =ex( x) = e(x) e(x). K Km11K1 Km m Giải mã Y = eK(X) ta đ−ợc d (Y) = de( (x)) d(e(x))=x x=X. K KK111KmmK m 1m Để sử dụng cách lập mật mã theo dòng, ngoài sơ đồ mật mã gốc ta còn phải có một dòng khóa, tức là một dãy có độ dài tùy ý các ký tự khóa. Đó th−ờng là các dãy các ký tự khóa đ−ợc sinh ra bởi một bộ "tạo dãy ngẫu nhiên" nào đó xuất phát từ một "mầm" chọn tr−ớc. Trong các ứng dụng thực tế, ng−ời ta th−ờng dùng cách mã theo dòng có sơ đồ mật mã gốc là sơ đồ Vernam với P = C = K = {0,1} và các hàm lập mã và giải mã đ−ợc xác định bởi eK(x) = x + K mod 2, dK(y) = y +K mod 2 (K = 0 hoặc 1); dòng khóa là dãy bit ngẫu nhiên đ−ợc sinh ra bởi một bộ tạo dãy bit ngẫu nhiên nào đó. 1.3. Mật mã khóa đối xứng và mật mã có khóa công khai. Theo định nghĩa 1.2.1 về sơ đồ mật mã, cứ mỗi lần truyền tin bảo mật, cả ng−ời gửi A và ng−ời nhận B phải cùng thỏa thuận tr−ớc với nhau một khóa chung K, sau đó ng−ời gửi dùng eK để lập mật mã cho thông báo gửi đi, và ng−ời nhận dùng dK để giải mã bản mật mã nhận đ−ợc. Ng−ời gửi và ng−ời nhận cùng có một khóa 15
19. chung K, đ−ợc giữ nh− bí mật riêng của hai ng−ời, dùng cả cho lập mật mã và giải mã, ta gọi những hệ mật mã với cách sử dụng đó là mật mã khóa đối xứng, đôi khi cũng gọi là mật mã truyền thống, vì đó là cách đã đ−ợc sử dụng từ hàng ngàn năm nay. Tuy nhiên, về nguyên tắc hai hàm lập mã và giải mã là khác nhau, không nhất thiết phải phụ thuộc cùng một khóa. Nếu ta xác định mỗi khóa K gồm có hai phần K = (K' , K'' ), K' dành cho việc lập mật mã (và ta có hàm lập mã eK' ), K'' dành cho việc giải mã (và có hàm giải mã dK'' ), các hàm lập mã và giải mã thỏa mãn hệ thức dK'' (eK' (x)) = x với mọi x ∈P , thì ta đ−ợc một hệ mật mã khóa phi đối xứng. Nh− vậy, trong một hệ mật mã khóa phi đối xứng, các khóa lập mã và giải mã (K' và K'' ) là khác nhau, nh−ng tất nhiên có quan hệ với nhau. Trong hai khóa đó, khóa cần phải giữ bí mật là khóa giải mã K'' , còn khóa lập mã K' có thể đ−ợc công bố công khai; tuy nhiên điều đó chỉ có ý nghĩa thực tiễn khi việc biết K' tìm K'' là cực kỳ khó khăn đến mức hầu nh− không thể thực hiện đ−ợc. Một hệ mật mã khóa phi đối xứng có tính chất nói trên, trong đó khóa lập mật mã K' của mỗi ng−ời tham gia đều đ−ợc công bố công khai, đ−ợc gọi là hệ mật mã khóa công khai. Khái niệm mật mã khóa công khai mới đ−ợc ra đời vào giữa những năm 1970, và ngay sau đó đã trở thành một khái niệm trung tâm của khoa học mật mã hiện đại. Ta sẽ dành phần lớn nội dung giáo trình này cho các hệ mật mã đó và những ứng dụng của chúng vào các vấn đề an toàn thông tin. 1.4. Các bài toán về an toàn thông tin. Chúng ta đang sống trong một thời đại bùng nổ thông tin. Nhu cầu trao đổi thông tin và các ph−ơng tiện truyền đ−a thông tin phát triển một cách nhanh chóng. Và cùng với sự phát triển đó, đòi hỏi bảo vệ tính bí mật và an toàn của thông tin cũng càng ngày càng to lớn và có tính phổ biến. Có nhiều bài toán khác nhau về yêu cầu an toàn thông tin tùy theo những tình huống khác nhau, nh−ng tựu 16
20. trung có một số bài toán chung nhất mà ta th−ờng gặp trong thực tiễn là những bài toán sau đây: - bảo mật : giữ thông tin đ−ợc bí mật đối với tất cả mọi ng−ời, trừ một ít ng−ời có thẩm quyền đ−ợc đọc, biết thông tin đó; - toàn vẹn thông tin : bảo đảm thông tin không bị thay đổi hay xuyên tạc bởi những kẻ không có thẩm quyền hoặc bằng những ph−ơng tiện không đ−ợc phép; - nhận thực một thực thể : xác nhận danh tính của một thực thể, chẳng hạn một ng−ời, một máy tính cuối trong mạng, một thẻ tín dụng, ; - nhận thực một thông báo : xác nhận nguồn gốc của một thông báo đ−ợc gửi đến ; - chữ ký : một cách để gắn kết một thông tin với một thực thể, th−ờng dùng trong bài toán nhận thực một thông báo cũng nh− trong nhiều bài toán nhận thực khác ; - ủy quyền : chuyển cho một thực thể khác quyền đ−ợc đại diện hoặc đ−ợc làm một việc gì đó ; - cấp chứng chỉ : cấp một sự xác nhận thông tin bởi một thực thể đ−ợc tín nhiệm ; - báo nhận : xác nhận một thông báo đã đ−ợc nhận hay một dịch vụ đã đ−ợc thực hiện ; - làm chứng : kiểm thử việc tồn tại một thông tin ở một thực thể khác với ng−ời chủ sở hữu thông tin đó ; - không chối bỏ đ−ợc : ngăn ngừa việc chối bỏ trách nhiệm đối với một cam kết đã có (thí dụ đã ký vào một văn bản) ; - ẩn danh : che giấu danh tính của một thực thể tham gia trong một tiến trình nào đó (th−ờng dùng trong giao dịch tiền điện tử) ; - thu hồi : rút lại một giấy chứng chỉ hay ủy quyền đã cấp; - vân vân Cơ sở của các giải pháp cho các bài toán kể trên là các ph−ơng pháp mật mã, đặc biệt là mật mã khóa công khai, ta sẽ xem xét kỹ một vài bài toán đó trong các ch−ơng tiếp theo. 17
21. 1.5. Thám mã và tính an toàn của các hệ mật mã. 1.5.1. Vấn đề thám mã. Mật mã đ−ợc sử dụng tr−ớc hết là để bảo đảm tính bí mật cho các thông tin đ−ợc trao đổi, và do đó bài toán quan trọng nhất của thám mã cũng là bài toán phá bỏ tính bí mật đó, tức là từ bản mật mã có thể thu đ−ợc dễ dàng (trên các kênh truyền tin công cộng) ng−ời thám mã phải phát hiện đ−ợc nội dung thông tin bị che giấu trong bản mật mã đó, mà tốt nhất là tìm ra đ−ợc bản rõ gốc của bản mật mã đó. Tình huống th−ờng gặp là bản thân sơ đồ hệ thống mật mã, kể cả các phép lập mã và giải mã (tức các thuật toán E và D ), không nhất thiết là bí mật, do đó bài toán qui về việc tìm chìa khóa mật mã K, hay chìa khóa giải mã K'', nếu hệ mật mã có khóa phi đối xứng. Nh− vậy, ta có thể qui −ớc xem bài toán thám mã cơ bản là bài toán tìm khóa mật mã K (hay khóa giải mã K''). Để giải bài toán đó, giả thiết ng−ời thám mã biết thông tin về sơ đồ hệ mật mã đ−ợc dùng, kể cả các phép lập mã và giải mã tổng quát E và D . Ngoài ra, ng−ời thám mã có thể biết thêm một số thông tin khác, tùy theo những thông tin đ−ợc biết thêm này mà ta có thể phân loại bài toán thám mã thành các bài toán cụ thể nh− sau: - bài toán thám mã chỉ biết bản mã : là bài toán phổ biến nhất, khi ng−ời thám mã chỉ biết một bản mật mã Y; - bài toán thám mã khi biết cả bản rõ : ng−ời thám mã biết một bản mật mã Y cùng với bản rõ t−ơng ứng X; - bài toán thám mã khi có bản rõ đ−ợc chọn : ng−ời thám mã có thể chọn một bản rõ X, và biết bản mật mã t−ơng ứng Y . Điều này có thể xẩy ra khi ng−ời thám mã chiếm đ−ợc (tạm thời) máy lập mã; - bài toán thám mã khi có bản mã đ−ợc chọn : ng−ời thám mã có thể chọn một bản mật mã Y, và biết bản rõ t−ơng ứng X. Điều này có thể xẩy ra khi ng−ời thám mã chiếm đ−ợc tạm thời máy giải mã. 1.5.2. Tính an toàn của một hệ mật mã. 18
22. Tính an toàn của một hệ thống mật mã phụ thuộc vào độ khó khăn của bài toán thám mã khi sử dụng hệ mật mã đó. Ng−ời ta đã đề xuất một số cách hiểu cho khái niệm an toàn của hệ thống mật mã, để trên cơ sở các cách hiểu đó nghiên cứu tính an toàn của nhiều hệ mật mã khác nhau, sau đây ta giới thiệu vài cách hiểu thông dụng nhất: - An toàn vô điều kiện : giả thiết ng−ời thám mã có đ−ợc thông tin về bản mã. Theo quan niệm lý thuyết thông tin, nếu những hiểu biết về bản mã không thu hẹp đ−ợc độ bất định về bản rõ đối với ng−ời thám mã, thì hệ mật mã là an toàn vô điều kiện, hay theo thuật ngữ của C. Shannon, hệ là bí mật hoàn toàn. Nh− vậy, hệ là an toàn vô điều kiện, nếu độ bất định về bản rõ sau khi ng−ời thám mã có đ−ợc các thông tin (về bản mã) bằng độ bất định về bản rõ tr−ớc đó. Tính an toàn vô điều kiện đã đ−ợc nghiên cứu cho một số hệ mật mã khóa đối xứng mà ta sẽ trình bày trong ch−ơng 3. - An toàn đ−ợc chứng minh : một hệ thống mật mã đ−ợc xem là có độ an toàn đ−ợc chứng minh nếu ta có thể chứng minh đ−ợc là bài toán thám mã đối với hệ thống đó khó t−ơng đ−ơng với một bài toán khó đã biết, thí dụ bài toán phân tích một số nguyên thành tích các thừa số nguyên tố, bài toán tìm lôgarit rời rạc theo một môđuyn nguyên tố, v.v (khó t−ơng đ−ơng có nghĩa là nếu bài toán này giải đ−ợc thì bài toán kia cũng giải đ−ợc với cùng một độ phức tạp nh− nhau). - An toàn tính toán : hệ mật mã đ−ợc xem là an toàn (về mặt) tính toán, nếu mọi ph−ơng pháp thám mã đã biết đều đòi hỏi một nguồn năng lực tính toán v−ợt mọi khả năng (kể cả ph−ơng tiện thiết bị) tính toán của một kẻ thù giả định. An toàn theo nghĩa này, nói theo ngôn ngữ của lý thuyết về độ phức tạp tính toán, là bao hàm cả khái niệm an toàn theo nghia "đ−ợc chứng minh" nói trên. Tính an toàn theo nghĩa đ−ợc chứng minh hay tính toán đ−ợc sử dụng nhiều trong việc nghiên cứu các hệ thống mật mã hiện đại, đặc biệt là các hệ thống mật mã khóa công khai, ta sẽ trình bày riêng cho từng hệ mật mã đ−ợc trình bày trong các ch−ơng về sau. ở mục 19
23. 1,4 ta đã giới thiệu một số bài toán về an toàn thông tin nói chung. Các bài toán đó đều có hạt nhân là tính an toàn của một hệ mật mã nào đó, cho nên việc nghiên cứu tính an toàn của các hệ mật mã cũng góp phần giải quyết các vấn đề an toàn thông tin kể trên. CHƯƠNG II Cơ sở toán học của lý thuyết mật mã 2.1. Số học các số nguyên. Thuật toán Euclide. Ta ký hiệu Z là tập hợp các số nguyên, Z = { ,-2,-1,0,1,2, }, và Z + là tập hợp các số nguyên không âm, Z += {0,1,2, }. Trong mục này ta sẽ nhắc lại một số kiến thức về số học của các số nguyên cần cho việc trình bày lý thuyết mật mã. Vì để tập giáo trình không quá dài dòng, các kiến thức sẽ đ−ợc nhắc đến chủ yếu là các khái niệm, các mệnh đề sẽ đ−ợc sử dụng, v.v , còn các phần chứng minh sẽ đ−ợc l−ợc bỏ, bạn đọc nào muốn tìm hiểu kỹ hơn có thể tham khảo các sách chuyên về Số học. 2.1.1. Tính chia hết của các số nguyên. Tập hợp Z là đóng kín đối với các phép cộng, trừ và nhân, nh−ng không đóng kín đối với phép chia: chia một số nguyên cho một số nguyên không phải bao giờ cũng đ−ợc kết quả là một số nguyên! Vì vậy, tr−ờng hợp chia hết, tức khi chia số nguyên a cho số nguyên b đ−ợc th−ơng là một số nguyên q , a = b.q, có một ý nghĩa đặc biệt. Khi đó, ta nói a chia hết cho b, b chia hết a, a là bội số của b, b là −ớc số của a, và ký hiệu là b⏐a. Dễ thấy ngay rằng số 1 là −ớc 20
24. số của mọi số nguyên bất kỳ, số 0 là bội số của mọi số nguyên bất kỳ, mọi số nguyên a là −ớc số, đồng thời là bội số, của chính nó. Cho hai số nguyên bất kỳ a và b , b > 1. Thực hiện phép chia a cho b ta sẽ đ−ợc hai số q và r sao cho a = b.q + r , 0 0, d là −ớc số chung của a và b, và mọi −ớc số chung của a và b đều là −ớc số của d . Ta ký hiệu −ớc số chung lớn nhất của a và b là gcd(a,b). Thí dụ gcd(12,18) = 6, gcd(-18, 27) = 3. Dễ thấy rằng với mọi số nguyên d−ơng a ta có gcd(a,0) = a , ta cũng sẽ qui −ớc xem rằng gcd(0, 0) = 0. Một số nguyên a > 1 đ−ợc gọi là số nguyên tố, nếu a không có −ớc số nào ngoài 1 và chính a ; và đ−ợc gọi là hợp số , nếu không phải là nguyên tố. Thí dụ các số 2 ,3 , 5, 7 là số nguyên tố; các số 4, 6, 8, 10, 12, 14, 15 là hợp số. Hai số a và b đ−ợc gọi là nguyên tố với nhau, nếu chúng không có −ớc số chung nào khác 1, tức là nếu gcd(a,b) = 1. Một số nguyên n > 1 bất kỳ đều có thể viết d−ới dạng: αα12 αk np= 12.p pk trong đó p1 , p2 , , pk là các số nguyên tố khác nhau, α1 , α2 , , αk là các số mũ nguyên d−ơng. Nếu không kể thứ tự các thừa số nguyên tố, thì dạng biểu diễn đó là duy nhất, ta gọi đó là dạng khai triển chính tắc của n . Thí dụ dạng khai triển chính tắc của 1800 là 233252. Các số nguyên tố và các vấn đề về số nguyên tố có một vai trò quan trọng trong số học và trong ứng dụng vào lý thuyết mật mã, ta sẽ xét riêng trong một mục sau. Định lý 2.1.1. Nếu b > 0 và b ⏐a thì gcd(a ,b) = b. 21
25. Nếu a = bq + r thì gcd(a,b) = gcd(b,r). Một số nguyên m đ−ợc gọi là bội số chung của a và b nếu a ⏐m và b⏐m. Số m đ−ợc gọi là bội số chung bé nhất của a và b , và đ−ợc ký hiệu là lcm(a ,b), nếu m > 0, m là bội số chung của a và b , và mọi bội số chung của a và b đều là bội của m . Thí dụ lcm(14,21) = 42. Với hai số nguyên d−ơng a và b bất kỳ ta có quan hệ lcm(a,b).gcd(a,b) = a.b. Từ định lý 2.1.1 ta suy ra thuật toán sau đây thực hiện việc tìm −ớc số chung lớn nhất của hai số nguyên bất kỳ: Thuật toán Euclide tìm −ớc số chung lớn nhất : INPUT: hai số nguyên không âm a và b , với a ≥b . OUTPUT: −ớc số chung lớn nhất của a và b. 1. Trong khi còn b > 0, thực hiện: 1.1. đặt r ←a modb , a ←b , b ← r. 2. Cho ra kết quả (a). Thí dụ: Dùng thuật toán Euclide tìm gcd( 4864, 3458), ta lần l−ợt đ−ợc các giá trị gán cho các biến a, b và r nh− sau: a b r 4864 3458 4864 = 1. 3458 + 1406 3458 1406 1406 3458 = 2. 1406 + 646 1406 646 646 1406 = 2. 646 + 114 646 114 114 646 = 5. 114 + 76 114 76 76 114 = 1. 76 + 38 76 38 38 76 = 2. 38 + 0 38 0 0 22
26. Và thuật toán cho ta kết quả: gcd(4864, 3458) = 38. Ta biết rằng nếu gcd(a,b) = d, thì ph−ơng trình bất định a.x + b.y = d có nghiệm nguyên (x,y), và một nghiệm nguyên (x,y) nh− vậy có thể tìm đ−ợc bởi thuật toán Euclide mở rộng nh− sau: Thuật toán Euclide mở rộng : INPUT: hai số nguyên không âm a và b với a ≥b. OUTPUT: d = gcd(a,b) và hai số x,y sao cho a.x + b.y = d. 1. Nếu b = 0 thì đặt d← a , x ←1, y ← 0, và cho ra (d,x,y). 2. Đặt x2 = 1, x1 = 0 , y2 = 0 , y1 = 1. 3. Trong khi còn b > 0, thực hiện: 3.1. q←a divb, r ← a modb , x ← x2 − qx1 , y ← y2 − qy1. 3.2. a ←b, b ←r , x2 ← x1 , x1← x , y2← y1 và y1←y. 4. Đặt d ← a, x ←x2 , y ← y2 , và cho ra kết quả (d,x,y). Thí dụ: Dùng thuật toán Euclide mở rộng cho các số a = 4864 và b = 3458, ta lần l−ợt đ−ợc các giá trị sau đây cho các biến a, b, q, r, x, y, x1 , x2 , y1 , y2 (sau mỗi chu trình thực hiện hai lệnh 3.1 và 3.2) : q x x y y a b r x y 1 2 1 2 4864 3458 0 1 1 0 3458 1406 1 1406 1 -1 1 0 -1 1 1406 646 2 646 -2 3 -2 1 3 -1 646 114 2 114 5 -7 5 -2 -7 3 114 76 5 76 -27 38 -27 5 38 -7 23
27. 76 38 1 38 32 -45 32 -27 -45 38 38 0 2 0 -91 128 -91 32 128 -45 Ta dễ thử lại rằng sau mỗi lần thực hiện chu trình gồm hai lệnh 3.1 và 3.2, các giá trị x,y,r thu đ−ợc luôn thoả mãn 4864.x + 3458.y = r , và do đó khi kết thúc các vòng lặp (ứng với giá trị b = 0), thực hiện tiếp lệnh 4 ta đ−ợc kết quả d = 38, x = 32 và y = -45, cặp số (32,-45) thoả mãn: 4864.32 + 3458. (-45) = 38. 2.1.2. Đồng d− và ph−ơng trình đồng d− tuyến tính. Cho n là một số nguyên d−ơng. Ta nói hai số nguyên a và b là đồng d− với nhau theo môđuyn n , và viết a ≡ b (modn ), nếu n ⏐ a−b (tức cũng là nếu a − b chia hết cho n , hay khi chia a và b cho n ta đ−ợc cùng một số d− nh− nhau). Thí dụ: 23 ≡ 8 (mod 5 ), vì 23 − 8 = 5.3, -19 ≡ 9 (mod 7) vì -19 − 9 = -4 . 7. Quan hệ đồng d− (theo một môđuyn n ) trên tập hợp các số nguyên có các tính chất phản xạ, đối xứng và bắc cầu,tức là một quan hệ t−ơng đ−ơng, do đó nó tạo ra một phân hoạch trên tập hợp tất cả các số nguyên Z thành ra các lớp t−ơng đ−ơng: hai số nguyên thuộc cùng một lớp t−ơng đ−ơng khi và chỉ khi chúng cho cùng một số d− nếu chia cho n. Mỗi lớp t−ơng đ−ơng nh− vậy đ−ợc đại diện bởi một số duy nhất trong tập hợp Zn = {0, 1, 2, 3, , n -1}, là số d− chung khi chia các số trong lớp đó cho n. Vì vậy, ta có thể đồng nhất Zn với tập hợp tất cả các lớp t−ơng đ−ơng các số nguyên theo modn ; trên tập đó ta có thể xác định các phép tính cộng, trừ và nhân theo modn. Thí dụ: Z25 = {0, 1, 2, , 24}. Trong Z25 , 15 + 14 = 4, vì 15 + 14 = 29 = 4 (mod 25). T−ơng tự, 15.14 = 10 trong Z25 . 24
28. Cho a ∈Zn . Một số nguyên x ∈ Zn đ−ợc gọi là nghịch đảo của a theo mod n , nếu a.x ≡ 1 (modn). Nếu có số x nh− vậy thì ta nói a là khả nghịch, và ký hiệu x là a-1modn. Thí dụ 22-1 mod25 = 8, vì 22 .8 = 176 ≡ 1 (mod25). Từ định nghĩa ta có thể suy ra rằng a là khả nghịch theo modn khi và chỉ khi gcd(a,n ) = 1, tức là khi a và n nguyên tố với nhau. - Ta định nghĩa phép chia trong Zn nh− sau: a : b (mod n) = a.b 1 modn. Phép chia chỉ thực hiện đ−ợc khi b là khả nghịch theo modn. Thí dụ 15 : 22 (mod25) = 15.22-1mod 25 = 20. Bây giờ ta xét các ph−ơng trình đồng d− tuyến tính. Ph−ơng trình đồng d− tuyến tính có dạng a.x ≡ b (modn ), (1) trong đó a, b, n là các số nguyên, n > 0, x là ẩn số. Ph−ơng trình đó có nghiệm khi và chỉ khi d = gcd(a,n )⏐b, và khi đó nó có đúng d nghiệm theo modn. Thực vậy, đặt a ‘ = a/d , b = b/d , n = n/d , ta thấy ph−ơng trình đồng d− (1) t−ơng đ−ơng với ph−ơng trình a.x ≡ b (modn ), Vì gcd(a,n ) = 1, nên ph−ơng trình này có một nghiệm theo modn : -1 x = x0 ≡ b.a (modn ), và do đó ph−ơng trình (1) có d nghiệm theo modn là : x = x0 , x0 + n, , x0 + (d − 1)n (modn). Tất cả d nghiệm đó khác nhau theo modn , nh−ng cùng đồng d− với nhau theo modn. 25
29. Bây giờ ta xét hệ thống các ph−ơng trình đồng d− tuyến tính. Một hệ nh− vậy có thể đ−a về dạng ⎧x ≡an(mod ) ⎪ 11 1 ⎪ ⎪x22≡an(mod 2) ⎨ (2) ⎪ ⎪ ⎩⎪xkk≡an(mod k) Ta ký hiệu: n = n1.n2 nk , Ni = n/ni . Ta có định lý sau đây: Định lý 2.2.1 (định lý số d− Trung quốc). Giả sử các số nguyên n1, n2, ,nk là từng cặp nguyên tố với nhau. Khi đó, hệ ph−ơng trình đồng d− tuyến tính (2) có một nghiệm duy nhất theo modn. Nghiệm duy nhất nói trong định lý 2.2.1 đ−ợc cho bởi biểu thức: k aN M modn, x = ∑i=1 ii i -1 trong đó Mi = Ni modni (có Mi vì Ni và ni nguyên tố với nhau). Thí dụ: Cặp ph−ơng trình x ≡ 3 (mod7) và x ≡ 7 (mod13) có một nghiệm duy nhất x ≡ 59 (mod91). Nếu (n1 , n2) = 1, thì cặp ph−ơng trình x ≡ a (modn1) và x ≡ a (modn2) có nghiệm duy nhất x ≡ a (modn) theo modn với n = n1n2 . 2.1.3.Thặng d− thu gọn và phần tử nguyên thuỷ. Tập Zn = { 0,1,2, , n −1} th−ờng đ−ợc gọi là tập các thặng d− đầy đủ theo modn, vì mọi số nguyên bất kỳ đều có thể tìm đ−ợc trong Zn một số đồng d− với mình (theo modn ). Tập Zn là đóng đối với các phép tính cộng, trừ và nhân theo modn , nh−ng không đóng đối với phép chia, vì phép chia cho a theo modn chỉ có thể thực hiện đ−ợc khi a và n nguyên tố với nhau, tức khi gcd( a ,n ) =1. 26
30. * * Bây giờ ta xét tập Zn = { a ∈ Zn : gcd( a ,n ) = 1} , tức Zn là tập con của Zn bao gồm tất cả các phần tử nguyên tố với n. Ta gọi tập đó là tập các thặng d− thu gọn theo modn. Mọi số nguyên nguyên tố với * n đều có thể tìm thấy trong Zn một đại diện đồng d− với mình * theo modn . Chú ý rằng nếu p là một số nguyên tố thì Zp = {1,2, ,p- 1}. * Tập Zn lập thành một nhóm con đối với phép nhân của Zn , vì trong * * Zn phép chia theo modn bao giờ cũng thực hiện đ−ợc, ta sẽ gọi Zn là nhóm nhân của Zn . Theo đại số học, ta gọi số các phần tử trong một nhóm là cấp của nhóm đó. Ta ký hiệu φ(n) là số các số nguyên d−ơng bé hơn n và * nguyên tố với n. Nh− vậy, nhóm Zn có cấp φ(n) , và nếu p là số * nguyên tố thì nhóm Zp có cấp p -1. * Ta nói một phần tử g ∈Zn có cấp m , nếu m là số nguyên d−ơng bé m * nhất sao cho g =1 trong Zn . Theo một định lý trong Đại số, ta có * φ(n ) m ⏐ φ(n) . Vì vậy, với mọi b ∈Zn ta luôn có b ≡ 1 modn . * Nếu p là số nguyên tố, thì do φ(p) = p − 1, ta có với mọi b ∈Zp : bp−1 ≡1(modp) (3) Nếu b có cấp p - 1, tức p - 1 là số mũ bé nhất thoả mãn công thức (3), thì các phần tử b, b2, , b P-1 đều khác nhau và theo modp, chúng lập * * thành Zp . Theo thuật ngữ đại số, khi đó ta nói Zp là một nhóm cyclic và b là một phần tử sinh, hay phần tử nguyên thuỷ của nhóm đó. Trong lý thuyết số, ng−ời ta đã chứng minh đ−ợc các tính chất sau đây của các phần tử nguyên thuỷ: * 1. Với mọi số nguyên tố p, Zp là nhóm cyclic, và có φ(p-1) phần tử nguyên thuỷ. αα12 αs 2. Nếu pp−=1 12.p ps là khai triển chính tắc của p -1, và nếu 27
31. p−1 p−1 p p ap1 ≡≡1(mod ), ,aps 1(mod ), * thì a là phần tử nguyên thuỷ theo modp (tức của Zp ). 3. Nếu g là phần tử nguyên thuỷ theo modp , thì β = gi modp với mọi i mà gcd(i, p -1) = 1, cũng là phần tử nguyên thuỷ theo modp . Ba tính chất đó là cơ sở giúp ta tìm các phần tử nguyên thuỷ theo modp , với p là số nguyên tố bất kỳ. Ngoài ra, ta cũng chú ý một số tính chất sau đây, có thể đ−ợc sử dụng nhiều trong các ch−ơng sau: a) Nếu p là số nguyên tố và gcd(a,p) =1, thì ap -1≡ 1 (modp) (định lý Fermat ). * φ()n b) Nếu a∈Zn , thì a≡1(modn). Nếu rs≡ (modφ(n)) thì aars≡ (mod n) (định lý Euler). 2.1.4. Ph−ơng trình đồng d− bậc hai và thặng d− bậc hai. Ta xét ph−ơng trình đồng d− bậc hai có dạng đơn giản sau đây: x2 ≡ an(mod ) , trong đó n là một số nguyên d−ơng, a là số nguyên với gcd(a,n) =1, và x là ẩn số. Ph−ơng trình đó không phải bao giờ cũng có nghiệm, khi nó có nghiệm thì ta nói a là một thặng d− bậc hai modn ; nếu không thì nói a là một bất thặng d− bậc hai modn. Tập các số nguyên nguyên tố với n đ−ợc phân hoạch thành hai tập con: tập Qn các thặng d− bậc hai modn , và tậpQn các bất thặng d− modn. Khi n = p là số nguyên tố, ta có tiêu chuẩn Euler sau đây: Số a là thặng d− bậc hai modp nếu và chỉ nếu ap(1p− )/2≡1(mod ). Tiêu chuẩn đó đ−ợc chứng minh nh− sau: Giả sử có x sao cho x2 ≡ a(mod p) , khi đó ta cũng sẽ có ax(1pp−−)/2≡≡()2(1)/2 xp−1≡1(modp). 28
32. (1p− )/2 * Ng−ợc lại, giả sử ap≡1(mod ). Khi đó a∈ Zp . Lấy b là một phần tử nguyên thuỷ modp , ắt có một số i nào đó sao cho ab= i mod p.Từ đó, ab(1pi−−)/2≡≡(p1)/2 1(mod p). Phần tử b có cấp p - 1, do đó (p - 1) chia hết i(p - 1)/2, i phải là số chẵn, i = 2j , và a có căn bậc hai là ±b jmodp. Cho p là một số nguyên tố lẻ. Với mọi a ≥ 0 ta định nghĩa ⎛⎞a ký hiệu Legendre ⎜ ⎟ nh− sau: ⎝⎠⎜ p⎟ ⎧ ⎪0, khi a ≡ 0(modp); ⎛⎞a ⎪ ⎜ ⎟=⎟ ⎪1,khi a ∈Q ; ⎜ ⎟ ⎨ p ⎝⎠⎜ p ⎪ ⎪−∉1, khi a Q . ⎩⎪ p Từ định nghĩa ta suy ra ngay a là thặng d− bậc hai modp khi và chỉ ⎛⎞a khi ⎜ ⎟= 1. Và theo tiêu chuẩn Euler nói trên, với mọi a ≥ 0, ta có: ⎝⎠⎜ p⎟ ⎛⎞ a ⎟ (1p− )/2 ⎜ ⎟≡ap(mod ). ⎝⎠⎜ p⎟ Bây giờ ta mở rộng ký hiệu Legendre để đ−ợc ký hiệu Jacobi đối với mọi số nguyên lẻ n ≥1 và mọi số nguyên a ≥ 0, cũng đ−ợc ký hiệu ⎛⎞a bởi ⎜ ⎟và đ−ợc định nghĩa nh− sau: Giả sử a có khai triển chính tắc ⎝⎠⎜n⎟ αα12 αk thành thừa số nguyên tố là np= 12.p pk thì αα12 αk ⎛⎞aa⎛⎞⎟⎟⎛a⎞ ⎛⎞a⎟ ⎜ ⎟=⎜⎜⎟⎟. ⎜ ⎟ . ⎜ ⎟ ⎜⎜⎟⎟⎜ ⎟ ⎝⎠np⎝⎠12⎝p⎠ ⎝⎠pk 29
33. Khi n = p là số nguyên tố thì giá trị của các ký hiệu Legendre và Jacobi là nh− nhau. Việc tính ký hiệu Legendre có thể phức tạp khi p rất lớn, trong khi việc tính ký hiệu Jacobi có thể thuận lợi hơn do có thể sử dụng các tính chất 1-4 sau đây: ⎛⎞mm⎛⎞ ⎜12⎟⎟⎜ 1. Nếu mm12≡ (mod n) , thì ⎜⎟⎟=⎜. ⎝⎠⎜nn⎟⎟⎝⎜⎠ ⎛⎞2 ⎪⎧1, khi n ≡±1(mod 8), ⎜ ⎟=⎪ 2. ⎜ ⎟ ⎨ ⎝⎠n ⎪⎩−≡1, khi n ±3 (mod 8). ⎛⎞mm. ⎛m⎞⎛m⎞ 3. ⎜⎜12⎟⎟= 1 ⎜2⎟ ⎝⎠⎜⎜nn⎟⎟⎝⎠⎝⎜n⎠⎟ 4. Nếu m và n đều là số lẻ, thì ⎪⎧ ⎛⎞n ⎪−≡⎜ ⎟,khi m 3(mod 4) & n ≡3(mod 4), ⎪⎜⎜ ⎟ ⎛⎞m ⎪ ⎝⎠m ⎜ ⎟= ⎨ ⎝⎠⎜ n ⎟ ⎪ ⎛⎞n ⎪ ⎜ ⎟ ≡∨≡ ⎪ ⎜ ⎟,khi m 1(mod 4) n 1(mod 4). ⎩⎪ ⎝⎠m Thí dụ: Dùng các tính chất đó, ta tính đ−ợc: ⎛⎞7411 ⎛⎞9283 ⎛1872⎞⎛2 ⎞4 ⎛117 ⎞ ⎜⎜⎜⎟==⎟⎟⎟=⎜.⎜⎟= ⎝⎠⎜⎜⎜9283⎟⎝⎠7411⎟⎟⎟⎝7411⎠⎝⎜7411⎠⎝⎜7411⎠⎟ ⎛117 ⎞ ⎛7411⎞⎛⎞40 ⎛⎞2 3 ⎛⎞5 ⎜⎜⎟=− ⎟⎟⎟=−⎜=−⎜.⎜⎟= ⎝⎜⎜7411⎠⎟⎝117 ⎠⎟⎟⎟⎝⎠⎜117 ⎝⎠⎜117 ⎝⎠⎜117⎟ ⎛⎞5 ⎛117⎞⎛2⎞ ⎜⎜⎜⎟=⎜⎜⎟⎟==⎜ −1. ⎝⎠⎜117⎟ ⎝⎜⎜5 ⎠⎝⎟⎟5⎠ 9283 là một số nguyên tố. Do đó, giá trị -1 của ký hiệu Jacobi ⎛7411⎞ ⎜ ⎟ cũng là giá trị của cùng ký hiệu Legendre đó, và ta kết luận ⎝⎠⎜9283⎟ đ−ợc rằng 7411 là bất thặng d− bậc hai mod 9283 , hay ph−ơng trình x2 ≡7411(mod9283) 30
34. là vô nghiệm. Bây giờ ta xét việc giải ph−ơng trình đồng d− bậc hai x2 ≡a(mod n) (4) trong một tr−ờng hợp đặc biệt khi n = p là số nguyên tố có dạng p = 4m +3, tức p đồng d− với 3 theo mod4, và a là một số nguyên nguyên tố với p. Theo tiêu chuẩn Euler ta biết ph−ơng trình (4) có nghiệm khi và chỉ khi a(1p− )/2≡1(mod p). Khi đó ta có: p−1 +1 2 aa≡ (mod p), aa2(m+1) ≡ (mod p), do đó x ≡ ±am +1 (modp) là hai nghiệm của ph−ơng trình (4). 2.2. Xác suất và thuật toán xác suất. 2.2.1. Khái niệm xác suất. Ta xét một tập hợp Ω , đ−ợc gọi là không gian các sự kiện sơ cấp (hay không gian mẫu). Các phần tử của Ω, tức các sự kiện sơ cấp hay các mẫu, có thể đ−ợc xem nh− các kết quả có thể có (và loại trừ lẫn nhau) của một thực nghiệm nào đó. Về sau ta chỉ xét các không gian rời rạc, tức tập Ω là hữu hạn, giả sử Ω={}ss12, , , sn . Một phân bố xác suất P trên Ω đ−ợc định nghĩa là một tập các số thực không âm P = { p1, p2, ,pn} có tổng ∑pi = 1. Số pi đ−ợc coi là xác suất của sự kiện sơ cấp si . Một tập con E ⊆ Ω đ−ợc gọi là một sự kiện . Xác suất của sự kiện E đ−ợc định nghĩa bởi p (E ) = ∑ p(s). sE∈ Giả sử E là một sự kiện trong không gian xác suất Ω. Ta định nghĩa sự kiện bù của E, ký hiệu E , là sự kiện gồm tất cả các sự kiện sơ cấp 31
35. trong Ω mà không thuộc E . Dùng các thuật ngữ của lý thuyết tập hợp, ta có thể định nghĩa cácsự kiện hợp E 1 ∪E 2 và sự kiện giao E 1 ∩E 2 của hai sự kiện E 1 và E 2 bất kỳ. Và ta có: 1) Giả sử E là một sự kiện. Khi đó 0 ≤ p (E ) ≤ 1 và p( E ) = 1 - p (E ). Ngoài ra, p (Ω) = 1 và p (∅) = 0. 2) Giả sử E 1 và E 2 là hai sự kiện. Nếu E 1 ⊆E 2 thì p (E 1) ≤ p (E 2) . Và có p (E 1∪E 2) + p (E 1 ∩E 2) =p (E 1) + p (E 2) . Do đó p (E 1∪E 2) =p (E 1) + p (E 2) khi và chỉ khi E 1 ∩E 2 = ∅, tức là khi E 1 và E 2 là hai sự kiện loại trừ lẫn nhau. Cho E 1 và E 2 là hai sự kiện, với p (E 2) > 0. Ta định nghĩa xác suất có điều kiện của E 1 khi có E 2 , ký hiệu pE(1E2), là pE()12∩ E pE()12E = . pE()2 Từ định nghĩa ta suy ra công thức Bayes : p()Ep12. ()EE1 pE()12E = . . pE()2 Ta nói hai sự kiện E 1 và E 2 là độc lập với nhau, nếu p (E 1 ∩E 2) = p(E1).p(E2). Khi đó ta có: pE( 12E)= p(E1) và p()EE21= p(E2). Giả sử Ω là một không gian mẫu với một phân bố xác suất P . Ta gọi một đại l−ợng ngẫu nhiên ξ trên Ω là một ánh xạ gán cho mỗi s ∈Ω một số thực ξ (s ). Hiển nhiên, nếu ξ và η là các đại l−ợng ngẫu nhiên trên Ω, thì ξ+η , ξ.η đ−ợc định nghĩa bởi : 32
36. ∀s ∈Ω: (ξ+η ) (s ) = ξ (s) + η (s ) , (ξ.η ) (s) = ξ (s).η (s). cũng là các đại l−ơng ngẫu nhiên trên Ω . Giả sử ξ là một đại l−ợng ngẫu nhiên trên không gian mẫu Ω. Điều đó có nghĩa là với mọi s ∈Ω, ξ lấy giá trị bằng ξ (s ) với xác suất p(s). Ta định nghĩa giá trị kỳ vọng (hay trung bình, hay kỳ vọng toán học) của ξ là E()ξξ=∑ ()s.p(s). s∈Ω Ph−ơng sai của đại l−ợng ngẫu nhiên ξ có giá trị trung bình à đ−ợc định nghĩa là Var (ξ ) = E ((ξ − à )2 ). Căn bậc hai không âm của Var (ξ )đ−ợc gọi là độ lệch chuẩn của ξ . 2.2.2. Tính bí mật hoàn toàn của một hệ mật mã. Năm 1949, C. Shannon công bố công trình Lý thuyết truyền thông của các hệ bí mật , đ−a ra nhiều quan niệm làm cơ sở cho việc đánh giá tính bí mật của các hệ mật mã, trong đó có khái niệm tính bí mật hoàn toàn của một hệ mật mã đ−ợc định nghĩa nh− sau: Cho hệ mật mã S = (P , C , K , E , D ) . Giả thử trên các tập P , C và K đ−ợc xác định t−ơng ứng các phân bố xác suất pP(.), pC(.) và pK(.). Nh− vậy, với mọi x ∈P , y ∈ C và K ∈K , pP(x), pC(y) và pK(K) t−ơng ứng là các xác suất để ký tự bản rõ là x, ký tự bản mã là y và khoá là K. Xác suất có điều kiện, chẳng hạn, xác suất của việc bản rõ là x khi bản mã là y, đ−ợc ký hiệu là pP(x⏐y). Một hệ mật mã đ−ợc gọi là bí mật hoàn toàn, nếu với mọi x ∈P , y ∈ C có pP(x⏐y) = pP(x). Điều đó có nghĩa là việc biết xác suất bản rõ là x là nh− nhau dù biết hay không biết bản mã là y ; nói cách khác, có thông tin về bản mã 33
37. không cho ta biết gì thêm về bản rõ; bản rõ và bản mã, với t− cách các biến ngẫu nhiên, là độc lập với nhau. Ta có định lý sau đây: Định lý 2.2.1. Giả sử S = (P , C , K , E , D ) là một hệ mật mã với điều kiện ⏐P ⏐ = ⏐C ⏐ = ⏐K ⏐ , tức các tập P , C , K có số các phần tử bằng nhau. Khi đó, hệ là bí mật hoàn toàn nếu và chỉ nếu mỗi khoá K ∈K đ−ợc dùng với xác suất bằng nhau là 1/⏐K ⏐ , và với mọi x ∈P , y ∈ C có một khoá duy nhất K ∈K sao cho eK (x ) = y. Chứng minh. a) Giả thử hệ S là bí mật hoàn toàn. Khi đó, với mọi x ∈P và y ∈ C có pP(x⏐y) = pP(x). Ngoài ra ta có thể giả thiết pC(y) > 0 với mọi y ∈ C . Từ đó theo công thức Bayes ta có pC(y⏐x ) = pC(y) > 0 . Điều đó có nghĩa là có ít nhất một khoá K sao cho eK (x ) = y . Vì vậy, nếu cố định một x ∈P thì ta có ⏐C ⏐ = ⏐{ eK(x ): K ∈K }⏐ ≤ ⏐K ⏐ . Theo giả thiết của định lý, ⏐C ⏐ = ⏐K ⏐ , do đó ⏐{ eK(x ): K ∈K }⏐ = ⏐K ⏐ . Nh−ng điều này lại có nghĩa là không thể có hai khoá K1 ≠ K2 sao cho ex()= e(x). Vậy ta đã chứng minh đ−ợc với mọi x ∈ và y ∈ K1K2 P C có đúng một khoá K sao cho eK (x ) = y . Ký hiệu n = ⏐K ⏐ và đặt K = {K1, , Kn }. Cố định một y ∈ C và giả thử ex()= y với = {x , , x }, 1≤ i ≤ n. Dùng công thức Bayes ta lại Kii P 1 n có pyCi()x.pP(xi)pK ()KpiP.(xi) pxPi()y==. pyCC() py() 34
38. Do giả thiết hệ là bí mật hoàn toàn, ta có pP(xi ⏐y) = pP(xi ). Từ đó suy ra với mọi i , 1≤ i ≤ n, pK (Ki ) = pC (y). Vậy các pK (Ki ) (1≤ i ≤ n ) đều bằng nhau, và do đó đều bằng 1/⏐K ⏐ . b) Bây giờ ta chứng minh điều ng−ợc lại. Giả thiết pK(K) = 1/⏐K ⏐ với mọi K ∈K , và với mọi x ∈P , y ∈ C có đúng một khoá K∈K sao cho eK (x ) = y . Ta tính: 1 pyC()= ∑∑pKK( ).pPK(d()y)==pPK(d()y) KK∈∈KKK 1 = ∑ pdPK((y)). K K∈K Khi K chạy qua tập khoá K thì dK (y ) chạy qua tập P , do đó ∑ pdPK((y))= ∑ pP(x)= 1, Kx∈∈KP và ta đ−ợc pC (y ) = 1/⏐K ⏐ với mọi y ∈ C . Mặt khác, gọi K là khoá duy nhất mà eK (x ) = y , ta có pC(y ⏐x) = pK(K) = 1/⏐K ⏐ . Dùng công thức Bayes ta lại đ−ợc với mọi x ∈P , y ∈ C : pxPC().p(yx) pP(x).1/K pxPP()y===p(x). pyC () 1/K Vậy hệ là bí mật hoàn toàn. Định lý đ−ợc chứng minh. 2.2.3. Thuật toán xác suất: 35
39. Khái niệm thuật toán mà ta th−ờng hiểu là thuật toán tất định, đó là một tiến trình thực hiện các phép toán trên dữ liệu đầu vào và cho kết quả ở đầu ra. Theo D.E. Knuth, thuật toán có 5 thuộc tính cơ bản: tính hữu hạn, thuật toán luôn kết thúc sau một số hữu hạn b−ớc; tính xác định, mỗi b−ớc của thuật toán phải đ−ợc xác định một cách chính xác; tập hợp đầu vào và đầu ra của mỗi thuật toán cũng đ−ợc xác định rõ ràng; và tính hiệu quả, mọi phép toán trong thuật toán phải là cơ bản, có thể đ−ợc thực hiện chính xác trong một thời gian xác định. Thuật toán là khái niệm cơ bản đối với việc lập trình trên máy tính, và đã đ−ợc sử dụng rất phổ biến. Nh−ng nh− ta biết, đối với nhiều bài toán trong thực tế, không phải bao giờ ta cũng tìm đ−ợc thuật toán giải chúng với độ phức tạp tính toán chấp nhận đ−ợc (ta sẽ xét qua vấn đề này trong một tiết sau). Vì vậy, cùng với các thuật toán tất định, đối với một số bài toán ta sẽ xét thêm các thuật toán xác suất, đó là những thuật toán mà cùng với dữ liệu đầu vào ta bổ sung thêm giá trị của một đại l−ợng ngẫu nhiên t−ơng ứng nào đó, th−ờng là các số ngẫu nhiên. Các thuật toán xác suất th−ờng đ−ợc xây dựng cho các bài toán quyết định, tức các bài toán xác định trên một tập hợp dữ liệu sao cho ứng với mỗi dữ liệu bài toán có một trả lời có hoặc không . Ng−ời ta chia các thuật toán xác suất thành hai loại: loại thuật toán Monte Carlo và loại thuật toán Las Vegas . Thuật toán Monte Carlo luôn kết thúc với kết quả có hoặc không đối với mọi dữ liệu đầu vào bất kỳ; còn thuật toán Las Vegas tuy cũng kết thúc với mọi dữ liệu, nh−ng có thể kết thúc với một thông báo không có trả lời có hoặc không. Thuật toán Monte Carlo đ−ợc gọi là thiên về có, nếu nó cho trả lời có thì trả lời đó chắc chắn là đúng, còn nếu nó cho trả lời không thì trả lời đó có thể sai với một xác suất ε nào đó. T−ơng tự, một thuật toán Monte Carlo đ−ợc gọi là thiên về không, nếu nó cho trả lời không thì trả lời đó chắc chắn là đúng, còn nếu nó cho trả lời có thì trả lời đó có thể sai với một xác suất ε nào đó. Còn với thuật toán Las Vegas, nếu nó kết thúc với trả lời có hoặc không , thì trả lời đó chắc chắn đúng, và nó có thể kết thúc với thông báo không có trả 36
40. lời với một xác suất ε nào đó. Trong tiết 2.8 sau đây ta sẽ cho vài thí dụ cụ thể về một số thuật toán xác suất thuộc cả hai loại đó. 2.3. Độ phức tạp tính toán. 2.3.1. Khái niệm về độ phức tạp tính toán. Lý thuyết thuật toán và các hàm số tính đ−ợc ra đời từ những năm 30 của thế kỷ 20 đã đặt nền móng cho việc nghiên cứu các vấn đề “tính đ−ợc”, “giải đ−ợc” trong toán học, đ−a đến nhiều kết quả rất quan trọng và lý thú. Nh−ng từ cái “tính đ−ợc” một cách trừu t−ợng, hiểu theo nghĩa tiềm năng,đến việc tính đ−ợc trong thực tế của khoa học tính toán bằng máy tính điện tử, là cả một khoảng cách rất lớn. Biết bao nhiêu thứ đ−ợc chứng minh là tính đ−ợc một cách tiềm năng, nh−ng không tính đ−ợc trong thực tế, dù có sự hỗ trợ của những máy tính điện tử ! Vấn đề là do ở chỗ những đòi hỏi về không gian vật chất và về thời gian để thực hiện các tiến trình tính toán nhiều khi v−ợt quá xa những khả năng thực tế. Từ đó, vào khoảng giữa những năm 60 (của thế kỷ tr−ớc), một lý thuyết về độ phức tạp tính toán bắt đầu đ−ợc hình thành và phát triển nhanh chóng, cung cấp cho chúng ta nhiều hiểu biết sâu sắc về bản chất phức tạp của các thuật toán và các bài toán, cả những bài toán thuần tuý lý thuyết đến những bài toán th−ờng gặp trong thực tế. Sau đây ta giới thiệu sơ l−ợc một số khái niệm cơ bản và vài kết quả sẽ đ−ợc dùng đến của lý thuyết đó. Tr−ớc hết, ta hiểu độ phức tạp tính toán (về không gian hay về thời gian) của một tiến trình tính toán là số ô nhớ đ−ợc dùng hay số các phép toán sơ cấp đ−ợc thực hiện trong tiến trình tính toán đó. Dữ liệu đầu vào đối với một thuật toán th−ờng đ−ợc biểu diễn qua các từ trong một bảng ký tự nào đó. Độ dài của một từ là số ký tự trong từ đó. 37
41. Cho một thuật toán A trên bảng ký tự Σ (tức có đầu vào là các từ trong Σ ) . Độ phức tạp tính toán của thuật toán A đ−ợc hiểu là một hàm số fA(n ) sao cho với mỗi số n , fA(n ) là số ô nhớ, hay số phép toán sơ cấp tối đa mà A cần để thực hiện tiến trình tính toán của mình trên các dữ liệu vào có độ dài ≤ n . Ta nói thuật toán A có độ phức tạp thời gian đa thức , nếu có một đa thức P (n ) sao cho với mọi n đủ lớn ta có fA(n) ≤ P(n ), trong đó fA(n ) là độ phức tạp tính toán theo thời gian của A. Về sau khi nói đến các bài toán, ta hiểu đó là các bài toán quyết định , mỗi bài toán P nh− vậy đ−ợc xác định bởi: - một tập các dữ liệu vào I (trong một bảng ký tự Σ nào đó), - một câu hỏi Q trên các dữ liệu vào, sao cho với mỗi dữ liệu vào x ∈ I , câu hỏi Q có một trả lời đúng hoặc sai. Ta nói bài toán quyết định P là giải đ−ợc , nếu có thuật toán để giải nó, tức là thuật toán làm việc có kết thúc trên mọi dữ liệu vào của bài toán, và cho kết quả đúng hoặc sai tuỳ theo câu hỏi Q trên dữ liệu đó có trả lời đúng hoặc sai. Bài toán P là giải đ−ợc trong thời gian đa thức , nếu có thuật toán giải nó với độ phức tạp thời gian đa thức. Sau đây là vài thí dụ về các bài toán quyết định: Bài toán SATISFIABILITY (viết tắt là SAT ): - mỗi dữ liệu vào là một công thức F của lôgich mệnh đề, đ−ợc viết d−ới dạng hội chuẩn tắc, tức dạng hội của một số các “clause”. - Câu hỏi là: công thức F có thoả đ−ợc hay không ? Bài toán CLIQUE : - mỗi dữ liệu vào là một graph G và một số nguyên k . - Câu hỏi là: Graph G có một clique với ≥ k đỉnh hay không ? (một clique của G là một graph con đầy đủ của G ). Bài toán KNAPSACK : 38
42. - mỗi dữ liệu là một bộ n +1 số nguyên d−ơng I = (s1, ,sn ; T ). - Câu hỏi là: có hay không một vectơ Boole (x1, ,xn) sao cho n x .?sT= ∑ i=1 ii (vectơ boole là vectơ có các thành phần là 0 hoặc 1). Bài toán thặng d− bậc hai : - mỗi dữ liệu gồm hai số nguyên d−ơng (a , n ). - Câu hỏi là: a có là thặng d− bậc hai theo modn hay không ? Bài toán hợp số : - mỗi dữ liệu là một số nguyên d−ơng N. - Câu hỏi: N là hợp số hay không ? Tức có hay không hai số m, n >1 sao cho N =m . n ? T−ơng tự, nếu đặt câu hỏi là “N là số nguyên tố hay không?” thì ta đ−ợc bài toán số nguyên tố . Đối với tất cả các bài toán kể trên, trừ bài toán hợp số và số nguyên tố, cho đến nay ng−ời ta đều ch−a tìm đ−ợc thuật toán giải chúng trong thời gian đa thức. 2.3.2. Lớp phức tạp. Ta xét một vài lớp các bài toán đ−ợc xác định theo độ phức tạp tính toán của chúng. Tr−ớc hết, ta định nghĩa P là lớp tất cả các bài toán có thể giải đ−ợc bởi thuật toán trong thời gian đa thức. Giả sử cho hai bài toán P1 và P2 với các tập dữ liệu trong hai bảng ký tự t−ơng ứng là Σ1 và Σ2 . Một thuật toán f :Σ→1Σ2 đ−ợc gọi là một phép qui dẫn bài toán P1 về bài toán P2 , nếu nó biến mỗi dữ liệu x của bài toán P1 thành một dữ liệu f (x ) của bài toán P2 , và sao cho câu hỏi của P1 trên x có trả lời đúng khi và chỉ khi câu hỏi của P2 trên f (x ) cũng có trả lời đúng. Ta nói bài toán P1 qui dẫn đ−ợc về bài toán P2 trong thời gian đa thức , và ký hiệu P1 ∝ P2 , nếu có thuật toán f với độ phức tạp thời gian đa thức qui dẫn bài toán P1 về bài toán P2 .Ta dễ thấy rằng, nếu P1 ∝ P2 và P2 ∈ P , thì cũng có P1 ∈ P . Một lớp quan trọng các bài toán đã đ−ợc nghiên cứu nhiều là lớp các bài toán khá th−ờng gặp trong thực tế nh−ng cho đến nay 39
43. ch−a có khả năng nào chứng tỏ là chúng có thể giải đ−ợc trong thời gian đa thức. Đó là lớp các bài toán NP-dầy đủ mà ta sẽ định nghĩa sau đây: Cùng với khái niệm thuật toán tất định thông th−ờng (có thể mô tả chính xác chẳng hạn bởi máy Turing tất định), ta xét khái niệm thuật toán không đơn định với một ít thay đổi nh− sau: nếu đối với máy Turing tất định, khi máy đang ở một trạng thái q và đang đọc một ký tự a thì cặp (q,a ) xác định duy nhất một hành động kế tiếp của máy, còn đối với máy Turing không đơn định, ta qui −ớc rằng (q,a) xác định không phải duy nhất mà là một tập hữu hạn các hành động kế tiếp; máy có thể thực hiện trong b−ớc kế tiếp một trong các hành động đó. Nh− vậy, đối với một dữ liệu vào x , một thuật toán không đơn định (đ−ợc xác định chẳng hạn bởi một máy Turing không đơn định) không phải chỉ có một tiến trình tính toán duy nhất, mà có thể có một số hữu hạn những tiến trình tính toán khác nhau. Ta nói thuật toán không đơn định A chấp nhận dữ liệu x , nếu với dữ liệu vào x thuật toán A có ít nhất một tiến trình tính toán kết thúc ở trạng thái chấp nhận (tức với kết quả đúng). Một bài toán P đ−ợc gọi là giải đ−ợc bởi thuật toán không đơn định trong thời gian đa thức nếu có một thuật toán không đơn định A và một đa thức p(n ) sao cho với mọi dữ liệu vào x có độ dài n , x ∈P (tức câu hỏi của P có trả lời đúng trên x ) khi và chỉ khi thuật toán A chấp nhận x bởi một tiến trình tính toán có độ phức tạp thời gian ≤ p(n ). Ta ký hiệu lớp tất cả các bài toán giải đ−ợc bởi thuật toán không đơn định trong thời gian đa thức là NP. Ng−ời ta đã chứng tỏ đ−ợc rằng tất cả những bài toán trong các thí dụ kể trên và rất nhiều các bài toán tổ hợp th−ờng gặp khác đều thuộc lớp NP, dù rằng hầu hết chúng đều ch−a đ−ợc chứng tỏ là thuộc P. Một bài toán P đ−ợc gọi là NP.-đầy đủ, nếu P ∈NP và với mọi Q ∈NP đều có Q ∝ P . Lớp NP có một số tính chất sau đây: 40
44. 1) P ⊆ NP, 2) Nếu P1 ∝ P2 và P2 ∈NP , thì P1 ∈ NP . 3) Nếu P1 ,P2 ∈NP , P1 ∝ P2 , và P1 là NP-đầy đủ, thì P2 cũng là NP -đầy đủ. 4) Nếu có P sao cho P là NP-đầy đủ và P ∈ P , thì P = NP. Từ các tính chất đó ta có thể xem rằng trong lớp NP , P là lớp con các bài toán “ dễ ” nhất, còn các bài toán NP-đầy đủ là các bài toán “ khó ” nhất; nếu có ít nhất một bài toán NP-đầy đủ đ−ợc chứng minh là thuộc P , thì lập tức suy ra P = NP , dù rằng cho đến nay tuy đã có rất nhiều cố gắng nh−ng toán học vẫn ch−a tìm đ−ợc con đ−ờng nào hy vọng đi đến giải quyết vấn đề [P = NP ?], thậm chí vấn đề đó còn đ−ợc xem là một trong 7 vấn đề khó nhất của toán học trong thiên niên kỷ mới! 2.3.3. Hàm một phía và cửa sập một phía. Khái niệm độ phức tạp tính toán cung cấp cho ta một cách tiếp cận mới đối với vấn đề bí mật trong các vấn đề bảo mật và an toàn thông tin. Dù ngày nay ta đã có những máy tính điện tử có tốc độ tính toán cỡ hàng tỷ phép tính một giây đồng hồ, nh−ng với những thuật toán có độ phức tạp tính toán cỡ f (n ) = 2n , thì ngay với những dữ liệu có độ dài khoảng n = 1000, việc thực hiện các thuật toán đó đã không thể xem là khả thi, vì nó đòi hỏi thực hiện khoảng 10300 phép tính! Nh− vậy, một giải pháp mật mã chẳng hạn có thể xem là có độ bảo mật cao, nếu để giải mã cần phải thực hiện một tiến trình tính toán có độ phức tạp rất lớn. Do đó, việc phát hiện và sử dụng các hàm số có độ phức tạp tính toán rất lớn là có ý nghĩa hết sức quan trọng đối với việc xây dựng các giải pháp về mật mã và an toàn thông tin. Hàm số số học y = f (x ) đ−ợc gọi là hàm một phía (one-way function), nếu việc tính thuận từ x ra y là “dễ”, nh−ng việc tính 41
45. ng−ợc từ y tìm lại x là rất “khó”, ở đây các tính từ “dễ” và “khó” không có các định nghĩa chính xác mà đ−ợc hiểu một cách thực hành, ta có thể hiểu chẳng hạn dễ là tính đ−ợc trong thời gian đa thức (với đa thức bậc thấp), còn khó là không tính đ−ợc trong thời gian đa thức! Thực tế thì cho đến hiện nay, việc tìm và chứng minh một hàm số nào đó là không tính đ−ợc trong thời gian đa thức còn là việc rất khó khăn, cho nên “khó” th−ờng khi chỉ đ−ợc hiểu một cách đơn giản là ch−a tìm đ−ợc thuật toán tính nó trong thời gian đa thức! Với cách hiểu t−ơng đối nh− vậy về “dễ” và “khó”, ng−ời ta đã đ−a ra một số thí dụ sau đây về các hàm một phía: Thí dụ 1. Cho p là một số nguyên tố, và α là một phần tử nguyên x * * thuỷ modp. Hàm số y = α modp (từ Z p vào Z p ) là một hàm một phía, vì hàm ng−ợc của nó, tính từ y tìm x mà ta ký hiệu x= logα ( y) , là một hàm có độ phức tạp tính toán rất lớn. Thí dụ 2. Cho n =p.q là tích của hai số nguyên tố lớn. Hàm số y = x 2 modn (từ Zn vào Zn ) cũng đ−ợc xem là một hàm một phía. Thí dụ 3. Cho n =p.q là tích của hai số nguyên tố lớn, và a là một số a nguyên sao cho gcd(a , φ(n)) =1. Hàm số y = x modn (từ Zn vào Zn ) cũng là một hàm một phía, nếu giả thiết là biết n nh−ng không biết p,q . Hàm y = f (x ) đ−ợc gọi là hàm cửa sập một phía (trapdoor one-way function), nếu việc tính thuận từ x ra y là “dễ”, việc tính ng−ợc từ y tìm lại x là rất “khó”, nh−ng có một cửa sập z để với sự trợ giúp của cửa sập z thì việc tính x từ y và z lại trở thành dễ. Thí dụ 4 (tiếp tục thí dụ 3). Hàm số y = x a modn khi biết p và q là hàm cửa sập một phía. Từ x tính y là dễ, từ y tìm x (nếu chỉ biết n , a ) là rất khó, nh−ng vì biết p và q nên biết φ(n) = (p -1)(q -1), và dùng thuật toán Euclide mở rộng tìm đ−ợc b sao cho a.b ≡ 1 (modφ(n)) , từ đó dễ tính đ−ợc x = y b modn . ở đây, có thể xem b là cửa sập. 42
46. 2.4. Số nguyên tố. Phân tích thành thừa số. Logarit rời rạc. Trong tiết này ta sẽ xét ba bài toán có vai trò quan trọng trong lý thuyết mật mã, đó là ba bài toán: thử tính nguyên tố của một số nguyên, phân tích một số nguyên thành tích của các thừa số nguyên tố, và tính logarit rời rạc của một số theo một môđuyn nguyên tố. 2.4.1. Thử tính nguyên tố của một số. Bài toán đặt ra rất đơn giản: Cho một số nguyên d−ơng n bất kỳ. Hãy thử xem n có là số nguyên tố hay không? Bài toán đ−ợc đặt ra từ những buổi đầu của số học, và trải qua hơn 2000 năm đến nay vẫn là một bài toán ch−a có đ−ợc những cách giải dễ dàng. Bằng những ph−ơng pháp đơn giản nh− ph−ơng pháp sàng Euratosthène, từ rất sớm ng−ời ta đã xây dựng đ−ợc các bảng số nguyên tố đầu tiên, rồi tiếp tục bằng nhiều ph−ơng pháp khác tìm thêm đ−ợc nhiều số nguyên tố lớn. Tuy nhiên, chỉ đến giai đoạn hiện nay của lý thuyết mật mã hiện đại, nhu cầu sử dụng các số nguyên tố và thử tính nguyên tố của các số mới trở thành một nhu cầu to lớn và phổ biến, đòi hỏi nhiều ph−ơng pháp mới có hiệu quả hơn. Trong mục này ta sẽ l−ợc qua vài tính chất của số nguyên tố, sau đó giới thiệu môt vài ph−ơng pháp thử tính nguyên tố của một số nguyên bất kỳ. Ta đã biết một số tính chất sau đây của các số nguyên tố và hợp số (trong các phát biểu d−ới đây, ký hiệu A chỉ cho số phần tử của tập hợp A ): 1. Tiêu chuẩn Euler-Solovay-Strassen: a) Nếu n là số nguyên tố, thì với mọi số nguyên d−ơng a [ n -1: ⎛⎞a (1n− )/2 ⎜ ⎟≡anmod . ⎝⎠⎜n⎟ b) Nếu n là hợp số , thì 43
47. ⎪⎪⎧⎫⎛⎞an−1 ⎪⎪aa:1≤≤n−1,⎜ ⎟≡a(1n− )/2mod n≤ . ⎨⎬⎜ ⎟ ⎩⎭⎪⎪⎝⎠n 2 2. Tiêu chuẩn Solovay-Strassen-Lehmann : a) Nếu n là số nguyên tố, thì với mọi số nguyên d−ơng a [ n -1: an(1n− )/2≡±1(mod ). b) Nếu n là hợp số, thì n−1 {}aa:1 ≤≤n−1, a(1n− )/2≡±1mod n≤ . 2 3. Tiêu chuẩn Miller-Rabin : a) Cho n là số nguyên lẻ, ta viết n - 1 = 2e .u, với u là số lẻ. Nếu n là số nguyên tố, thì với mọi số nguyên d−ơng a [ n -1: k (1anuu≡∨mod)∃k<e(a2. ≡−1modn). b) Nếu n là hợp số, thì k n−1 aa:1≤≤n−1,(au≡1mod n)∨∃k<e(a2.u≡−1mod n) ≤ . {}4 Các tiêu chuẩn kể trên là cơ sở để ta xây dựng các thuật toán xác suất kiểu Monte-Carlo thử tính nguyên tố (hay hợp số) của các số nguyên. Chẳng hạn, từ tiêu chuẩn thứ nhất ta có thuật toán Euler- Solovay-Strassen sau đây: Dữ liệu vào: số nguyên d−ơng n và t số ngẫu nhiên a1, ,at (1[ai[n -1), 1. for i = 1 to t do ⎛⎞a ⎜ i ⎟ (1n− )/2 2. if ⎜ ⎟ ≡ ani mod , then ⎝⎠⎜ n ⎟ 3. answer “n là số nguyên tố ” 4. else 5. answer “n là hợp số ” and quit 44
48. Thuật toán này nếu cho trả lời “n là hợp số ” thì đúng n là hợp số, nh−ng nếu nó cho trả lời “n là số nguyên tố ” thì trả lời đó có thể sai với một xác suất ε nào đó. Nh− vậy, thuật toán đó là một thuật toán xác suất Monte-Carlo thiên về có nếu xem nó là thuật toán thử tính là hợp số ; còn nó là một thuật toán xác suất thiên về không nếu xem nó là thuật toán thử tính nguyên tố của các số nguyên. T−ơng tự nh− vậy, dựa vào các tiêu chuẩn 2 và 3 ta cũng có thể xây dựng các thuật toán xác suất Solovay-Strassen-Lehmann và Miller-Rabin kiểu Monte-Carlo để thử tính nguyên tố (hay là hợp số) của các số nguyên. Hai thuật toán đó chỉ khác thuật toán Euler- Solovay-Strassen kể trên ở chỗ công thức trong hàng lệnh thứ 2 cần đ−ợc thay t−ơng ứng bởi an(1n− )/2≡±1mod hay k (anuu≡∨1mod ) ∃k<e(a2. ≡−1mod n) trong đó u và e đ−ợc xác định bởi: n - 1 = 2e.u , u là số lẻ. Xác suất sai lầm ε khi nhận đ−ợc kết quả “n là số nguyên tố ” trong các thuật toán đó đ−ợc tính nh− sau: Giả sử n là một số lẻ trong khoảng N và 2N , tức N <n < 2N . Gọi A là sự kiện “n là hợp số ”, và B là sự kiện “thuật toán cho kết quả trả lời n là số nguyên tố ”. Ta phải tính xác suất ε =p (A⏐ B). Theo tính chất b) của tiêu chuẩn Euler-Solovay-Strassen, nếu n là hợp số, thì sự kiện ⎛⎞a (1n− )/2 ⎜ ⎟≡anmod ⎝⎠⎜n⎟ đối với mỗi a ngẫu nhiên (1[a [n - 1) có xác suất [ 1/2, vì vậy ta có 1 pB()A≤ . 2t Theo công thức Bayes ta có 45
49. pB()A.(pA) p()BA.p(A) pA()B== . pB() p()BA.(pA)+ p()BA.p(A) Theo định lý về số nguyên tố, số các số nguyên tố giữa N và 2N Nn Nn 2 xấp xỉ ≈ , số các số lẻ là ≈ , do đó pA()≈ , và ln Nnln 22 ln n 2 pA()≈−1 . Dĩ nhiên ta có pB( A)=1. Thay các giá trị đó vào ln n công thức trên, ta đ−ợc 2 2(−t 1− ) ln n−2 pA()B≤ln n =. (5) 22 t+1 2(−t 1−+) ln n−+2 2 ln nnln Đánh giá đó cũng đúng đối với thuật toán Solovay-Strassen- Lehmann, còn đối với thuật toán Miler-Rabin thì ta đ−ợc một đánh giá tốt hơn, cụ thể là ln n−2 pA()B= . (6) ln n−+2 22t+1 Chú ý rằng khi t =50 thì đại l−ợng ở vế phải của (5) ≈10−13 , và vế phải của (6) ≈10−28 ; do đó nếu chọn cho dữ liệu vào thêm khoảng 50 số ngẫu nhiên ai thì các thuật toán Euler-Solovay- Strassen và Solovay-Strassen-Lehmann sẽ thử cho ta một số là nguyên tố với xác suất sai lầm [ 10-13 và thuật toán Miller-Rabin với xác suất sai lầm [ 10-28 ! Ta có thể tính đ−ợc rằng độ phức tạp tính toán về thời gian của các thuật toán xác suất kể trên là vào cỡ đa thức của logn , tức là đa thức của độ đài biểu diễn của dữ liệu vào (là số n ), tuy nhiên các thuật toán đó chỉ cho ta thử tính nguyên tố của một số với một xác suất sai lầm ε nào đó, dù ε là rất bé. Trong nhiều ứng dụng, ta muốn có đ−ợc những số nguyên tố với độ chắc chắn 100% là số nguyên tố. Do đó, dù đã có các thuật toán xác suất nh− trên, ng−ời ta vẫn không ngừng tìm kiếm những thuật toán tất định để thử tính nguyên tố với độ chính xác tuyệt đối. Trong mấy chục năm gần đây, 46
50. một số thuật toán đã đ−ợc đề xuất, trong đó có những thuật toán đặc sắc nh− thuật toán thử tổng Jacobi, đ−ợc phát hiện bởi Adleman, Pomerance và Rumely, sau đó đ−ợc đơn giản hoá bởi Cohen và Lenstra; thuật toán thử bằng đ−ờng cong elliptic, đ−ợc đề xuất bởi Goldwasser, Kilian, Adleman và Huang, đ−ợc tiếp tục hoàn thiện bởi Atkin và Morain, các thuật toán này đã đ−ợc dùng để tìm nhiều số nguyên tố rất lớn, thí dụ dùng thuật toán Atkin-Morain đã chứng tỏ đ−ợc số (23539+ 1)/3 có 1065 chữ số thập phân là số nguyên tố. Gần đây, vào tháng 8/2002, các nhà toán học Ân độ Agrawal, Kayal và Saxena đã đ−a ra một thuật toán tất định mới thử tính nguyên tố có độ phức tạp tính toán thời gian đa thức khá đơn giản, thuật toán đó đ−ợc mô tả nh− sau: Thuật toán Agrawal-Kayal-Saxena: Input: integer n > 1 1. if (n is of the form ab, b > 1 ) ouput COMPOSITE; 2. r =2; 3. while (r < n ) { 4. if (gcd(n , r )≠ 1) ouput COMPOSITE; 5. if (r is prime ) 6. let q be the largest prime factor of r - 1; r−1 7. if (4qr≥ logn)and (nrq ≠1(mod )) 8. break; 9. r ← r + 1; 10. } 11. for a = 1 to 2lrnog 12. if ((x−≠−ax)nn( a)(mod xr−1,n)) ouput COMPOSITE; 13. output PRIME; 47
51. Thuật toán này đã đ−ợc một số nhà toán học kiểm nghiệm , đánh giá cao và xem là một thuật toán đẹp, có thể dùng cho việc kiểm thử tính nguyên tố của các số nguyên. Trong thực tiễn xây dựng các giải pháp mật mã, th−ờng có nhu cầu có các số nguyên tố rất lớn. Để tìm đ−ợc các số nh− vậy, ng−ời ta th−ờng chọn ngẫu nhiên một số rất lớn, rồi dùng tr−ớc cho nó một thuật toán xác suất chẳng hạn nh− thuật toán Miller-Rabin; nếu thuật toán cho ta kết quả “là số nguyên tố” với một xác suất sai ε nào đó, thì sau đó ta dùng tiếp một thuật toán tất định (chẳng hạn nh− thuật toán trên đây) để bảo đảm chắc chắn 100% rằng số đó là số nguyên tố. Thuật toán Agrawal-Kayal-Saxena trên đây đ−ợc chứng tỏ là có độ phức tạp thời gian đa thức cỡ O((logn)12) khi thử trên số n ; và nếu số nguyên tố đ−ợc thử có dạng Sophie Germain, tức dạng 2p +1, thì độ phức tạp thời gian sẽ chỉ là cỡ O((logn)6). 2.4.2. Phân tích thành thừa số nguyên tố. Bài toán phân tích một số nguyên > 1 thành thừa số nguyên tố cũng đ−ợc xem là một bài toán khó th−ờng đ−ợc sử dụng trong lý thuyết mật mã. Biết một số n là hợp số thì việc phân tích n thành thừa số mới là có nghĩa; do đó th−ờng khi để giải bài toán phân tích n thành thừa số, ta thử tr−ớc n có là hợp số hay không (chẳng hạn bằng một trong các thuật toán ở mục tr−ớc); và bài toán phân tích n thành thừa số có thể dẫn về bài toán tìm một −ớc số của n, vì khi biết một −ớc số d của n thì tiến trình phân tích n đ−ợc tiếp tục thực hiện bằng cách phân tích d và n/d. Bài toán phân tích thành thừa số, hay bài toán tìm −ớc số của một số nguyên cho tr−ớc, đã đ−ợc nghiên cứu nhiều, nh−ng cũng ch−a có một thuật toán hiệu quả nào để giải nó trong tr−ờng hợp tổng quát; do đó ng−ời ta có khuynh h−ớng tìm thuật toán giải nó trong những tr−ờng hợp đặc biệt, chẳng hạn khi n có một −ớc số nguyên tố p với p -1 là B-mịn với một cận B >0 nào đó, hoặc khi n là số Blum, tức là số có dạng tích của hai số nguyên tố lớn nào đó (n =p.q ). 48
52. Ta xét tr−ờng hợp thứ nhất với (p -1)-thuật tóan Pollard nh− sau: Một số nguyên n đ−ợc gọi là B-mịn, nếu tất cả các −ớc số nguyên tố của nó đều ≤B. ý chính chứa trong (p-1)- thuật toán Pollard là nh− sau: Giả sử n là B-mịn. Ký hiệu Q là bội chung bé nhất của tất cả các luỹ thừa của các số nguyên tố ≤B mà bản thân chúng ≤n. Nếu q l ⎢ln n⎥ ≤n thì l lnq ≤ lnn , tức l ≤ ⎢ ⎥ ( ⎣⎢x⎦⎥ là số nguyên bé nhất lớn hơn x ). ⎣⎢ln q⎦⎥ Ta có ⎢ ⎥ Qq= ∏ ⎣ln nq/ ln ⎦ , qB≤ trong đó tích lấy theo tất cả các số nguyên tố khác nhau q ≤B . Nếu p là một thừa số nguyên tố của n sao cho p -1 là B-mịn, thì p -1⏐Q, và do đó với mọi a bất kỳ thỏa mãn gcd(a,p) = 1, theo định lý Fermat ta có a Q ≡ 1 (modp ). Vì vậy, nếu lấy d =gcd(aQ - 1, n ) thì p ⏐d. Nếu d = n thì coi nh− thuật toán không cho ta điều mong muốn, tuy nhiên điều đó chắc không xẩy ra nếu n có ít nhất hai thừa số nguyên tố khác nhau. Từ những lập luận đó ta có: (p - 1)-thuật toán Pollard phân tích thành thừa số : INPUT: một hợp số n không phải là luỹ thừa của một số nguyên tố. OUTPUT: một thừa số không tầm th−ờng của n . 1. Chọn một cận cho độ mịn B. 2. Chọn ngẫu nhiên một số nguyên a , 2≤ a ≤ n - 1, và tính d = gcd(a,n ). Nếu d ≥ 2 thì cho ra kết quả (d ). 3. Với mỗi số nguyên tố q ≤ B thực hiện: ⎢ln n⎥ 3.1 Tính l =⎢ ⎥. ⎣⎢ln q⎦⎥ l 3.2 Tính aa← q mod n. 49
53. 4. Tính d = gcd(a -1, n). 5. Nếu 1< d < n thì cho ra kết quả (d ). Nếu ng−ợc lại thì thuật toán coi nh− không có kết quả. Thí dụ: Dùng thuật toán cho số n = 19048567. Ta chọn B =19, và a =3, và tính đ−ợc gcd(3,n ) =1. Chuyển sang thực hiện b−ớc 3 ta đ−ợc bảng sau đây (mỗi hàng ứng với một giá trị của q ) : q l a 2 24 2293244 3 15 13555889 5 10 16937223 7 8 15214586 11 6 9685355 13 6 13271154 17 5 11406961 19 5 554506 Sau đó ta tính d =gcd(554506-1,19048567) = 5281. Vậy ta đ−ợc một thừa số p = 5281, và do đó một thừa số nữa là q = n/p = 3607. Cả hai thừa số đó đều là nguyên tố. Chú ý rằng ở đây p -1 = 5280 = 25.3.5.11 , có tất cả các −ớc số nguyên tố đều ≤ 19, do đó chắc chắn thuật toán sẽ kết thúc có kết quả. Thuật toán sẽ kết thúc không có kết quả khi độ mịn B đ−ợc chọn quá bé để không một thừa số nguyên tố p nào của n mà p -1 chỉ chứa các −ớc số nguyên tố ≤ B. Nh− vậy, có thể xem (p -1)-thuật toán Pollard phân tích n thành thừa số nguyên tố là có hiệu quả đối với những số nguyên n là B-mịn, ng−ời ta tính đ−ợc thời gian cần để thực hiện thuật toán đó là cỡ O(B lnn /lnB ) phép nhân theo môđuyn. Bây giờ ta xét tr−ờng hợp các số nguyên Blum, tức là các số có dạng n = p.q , tích của hai số nguyên tố lớn. Tr−ớc hết ta chú ý rằng 50
54. 22 nếu ta biết hai số nguyên khác nhau x và y sao cho x ≡ yn(mod ) thì ta dễ tìm đ−ợc một thừa số của n . Thực vậy, từ x22≡ yn(mod ) ta có x22−=yx()+y(x−y)chia hết cho n , do n không là −ớc số của x + y hoặc x - y, nên gcd(x - y, n) phải là một −ớc số của n, tức bằng p hoặc q . Ta biết nếu n = p.q là số Blum, thì ph−ơng trình đồng d− x22≡an(mod ) có 4 nghiệm, hai nghiệm tầm th−ờng là x = a và x = -a . Hai nghiệm không tầm th−ờng khác là ±b , chúng là nghiệm của hai hệ ph−ơng trình đồng d− bậc nhất sau đây: ⎪⎧≡xa≡ (mod p) ⎪⎧x −ap(mod ) ⎨⎨⎪⎪ ⎩⎪⎪⎪xa≡− (mod q) ⎪x≡aq()mod ⎩ Bằng lập luận nh− trên, ta thấy rằng nếu n là số Blum, a là một số nguyên tố với n, và ta biết một nghiệm không tầm th−ờng của ph−ơng trình x22≡a(mod n) , tức biết một x ≠ ±a sao cho x22≡a(mod n) thì gcd(x - a , n ) sẽ là một −ớc số của n . Những điều trên đây là căn cứ cho một số ph−ơng pháp tìm −ớc số nguyên tố của một số nguyên dạng Blum; ý chung của các ph−ơng pháp đó là dẫn về việc tìm một nghiệm không tầm th−ờng của một ph−ơng trình dạng x22≡a(mod n) , chẳng hạn nh− ph−ơng trình x2 ≡1(modn). Một tr−ờng hợp khá lý thú trong lý thuyết mật mã là khi ta biết hai số a ,b là nghịch đảo của nhau theo modφ (n ) (nh−ng không biết φ (n ) ), và tìm một phân tích thành thừa số của n. Bài toán đ−ợc đặt ra cụ thể là: Biết n có dạng Blum, biết a và b sao cho ab ≡ 1(modφ (n )). Hãy tìm một −ớc số nguyên tố của n , hay tìm một nghiệm không tầm th−ờng của ph−ơng trình x2 ≡1(modn). Ta giả thiết ab - 1 = 2s. r với r là số lẻ. Ta phát triển một thuật toán xác suất kiểu Las Vegas nh− sau: Ta chọn một số ngẫu nhiên v (1≤ v ≤ n - 1). Nếu may mắn v là bội số của p hay q, thì ta đ−ợc ngay một −ớc số của n là gcd(v,n ). Nếu v nguyên tố với n , thì ta tính các bình ph−ơng liên tiếp kể từ t v r, đ−ợc vvrrr, 24,v, cho đến khi đ−ợc vn2.r ≡1m(od ) với một t nào 51
55. đó. Số t nh− vậy bao giờ cũng đạt đ−ợc, vì có 2s. r ≡ 0 (modφ(n )) s t−1 nên có v2.r ≡1m(odn). Nh− vậy, ta đã tìm đ−ợc một số x=v2.r sao cho x2 ≡1(modn). Tất nhiên có x≠ 1 modn . Nếu cũng có x≠ -1 (modn ) thì x là nghiệm không tầm th−ờng của x2 ≡1(modn), từ đó ta có thể tìm −ớc số của n . Nếu không thì thuật toán coi nh− thất bại, cho ta kết quả không đúng. Ng−ời ta có thể −ớc l−ợng xác suất cho kết quả không đúng với một lần thử với một số v là < 1/2, do đó nếu ta thiết kế thuật toán với m số ngẫu nhiên v1, vm , thì sẽ có thể đạt đ−ợc xác suất cho kết quả không đúng là < 1/2m ! 2.4.3. Tính logarit rời rạc theo môđuyn nguyên tố. Cho p là một số nguyên tố, và α là một phần tử nguyên thuỷ theo * modp, tức là phần tử nguyên thuỷ của nhóm Z p . Bài toán tính * logarit rời rạc theo modp là bài toán tìm, với mỗi số β ∈ Z p ,một số a ( a 1≤ a ≤ p -1) sao cho β = α modp , tức là a = logαβ (modp -1). Một thuật toán tầm th−ờng để giải bài toán này là thuật toán duyệt toàn bộ các số a từ 1 đến p - 1, cho đến khi tìm đ−ợc a thoả mãn β = αa modp . Tất nhiên, thuật toán này là không hiệu quả nếu p là số nguyên tố rất lớn. Một biến dạng của thuật toán đó với ít nhiều hiệu quả hơn là thuật toán Shanks sau đây: m=⎡ p−1⎤ Đặt ⎣⎢ ⎦⎥ . Ta tìm a d−ới dạng am=+ji,0≤j,i≤m−1. Rõ ràng β = αa modp khi và chỉ khi αβmj ≡ αi (mod p) . Ta lập hai danh sách gồm các cặp (,j αmj)và các cặp (,i βα−i )với j và i chạy từ 0 đến m - 1. Khi phát hiện ra có hai cặp từ hai danh sách đó có hai phần tử thứ hai bằng nhau là ta đ−ợc kết quả am=j+i, đó chính là giá trị logαβ mà ta cần tìm. Thuật toán Shanks có độ phức tạp cỡ O(m) phép toán nhân và O(m) bộ nhớ (ch−a kể O(m2) phép so sánh). Một thuật toán khác, thuật toán Polig-Hellman, th−ờng đ−ợc dùng có hiệu quả trong tr−ờng hợp p -1 chỉ có các thừa số nguyên tố 52
56. bé, có nội dung nh− sau: Giả thiết rằng p - 1 có dạng phân tích chính tắc là k ci pp−=1.∏ i i=1 ci Để tìm a = logαβ (modp -1), ta tìm các số ai sao cho aaii≡ mod p với i = 1, ,k. Sau khi tìm đ−ợc các ai nh− vậy, thì hệ ph−ơng trình ci x ≡apiimod (i=1, ,k) ,đ−ợc giải theo định lý số d− Trung quốc, sẽ cho ta lời giải xa≡(mod p−1) cần tìm. Vậy, vấn đề là xác định các ci apiimod (i=1, ,k) . Vấn đề này đ−ợc phát biểu lại nh− sau: Giả sử q là một −ớc số nguyên tố của p - 1, và q c ⏐ p - 1 nh−ng không còn q c + 1 ⏐ p - 1 . Ta cần tìm x = a modq c . Ta biểu diễn x d−ới dạng số q - phân nh− sau: c−1 xx=≤∑ iiq(0 xi≤q−1). i=0 Vì x = a modq c nên a viết đ−ợc d−ới dạng a = x + q c s , và vì α p−1 ≡1(mod p) , nên ta có pp−−11 (1px− )0 a a βαqq≡≡()αp−1 q ≡αq(modp). Ta đặt γα= (1p− )/q, và tính lần l−ợt γγ01, ,γ2, , đồng thời so sánh với β (1pq− )/mod p, ta sẽ tìm đ−ợc i sao cho γβip≡ (1− )/qmod p. Ta lấy số i đó là x0, tức x0 = i . Nếu c = 1 thì x = x0 , ta tìm xong x . −x0 c Nếu c >1 thì bằng cách đặt ββ' = α và x ' = logα β 'mod q ta dễ thấy rằng c−1 x '=∑ xqii. i=1 Từ đó ta suy ra 2 βα'm(1pq− )/≡ (1px− )1 /q odp. T−ơng tự nh− ở b−ớc trên, tính lần l−ợt γγ01, ,γ2, , đồng thời so (1p− )/q2 sánh với β ',ta sẽ tìm đ−ợc x 1. 53
57. Cứ làm nh− vậy, ta sẽ tìm đ−ợc dần tất cả các giá trị xi với i = 0,1, ,c -1, tức là tính đ−ợc x. Sau khi tìm đ−ợc tất cả các giá trị x ứng với mọi −ớc số nguyên tố q của p , thì theo một nhận xét ở trên, chỉ cần giải tiếp một hệ ph−ơng trình đồng d− bậc nhất theo các môđuyn từng cặp nguyên tố với nhau (bằng ph−ơng pháp số d− Trung quốc), ta sẽ tìm đ−ợc số a cần tìm, a = logαβ theo modp. Thí dụ: Cho p = 29 và α = 2. Hãy tính a =log 218 theo mod29. Ta có p - 1 = 28 = 22. 71 . Theo thuật toán Polig-Hellman, ta tìm lần l−ợt a mod 4 và a mod 7. Theo các b−ớc tính toán nh− mô tả ở trên, ta sẽ tìm đ−ợc a mod 4 = 3 và a mod 7 =4 .Từ đó giải hệ ph−ơng trình ⎪⎧x ≡ 3(mod4), ⎨⎪ ⎩⎪x ≡4(mod7) ta đ−ợc nghiệm x ≡ 11 (mod28), tức đ−ợc 11 = log 218 theo mod29. Thuật toán Polig-Hellman cho ta một cách tính logarit rời rạc khá hiệu quả, nh−ng chỉ khi p -1 chỉ có các thừa số nguyên tố bé. Vì vậy, nếu p -1 có ít nhất một thừa số nguyên tố lớn thì thuật toán đó khó đ−ợc thực hiện có hiệu quả, tức trong tr−ờng hợp đó bài toán tính logarit rời rạc theo modp vẫn là một bài toán khó. Một lớp các số nguyên tố p mà p - 1 có ít nhất một −ớc số nguyên tố lớn là lớp các số nguyên tố dạng p = 2q + 1, trong đó q là nguyên tố. Những số nguyên tố dạng đó đ−ợc gọi là số nguyên tố Sophie Germain, có vai trò quan trọng trong việc xây dựng một lớp khá thông dụng các hệ mật mã có khoá công khai. Ng−ời ta cũng đã nghiên cứu phát triển nhiều thuật toán khác, cả thuật toán tất định, cả thuật toán xác suất, để tính logarit rời rạc, nh−ng ch−a có thuật toán nào đ−ợc chứng tỏ là có độ phức tạp tính toán với thời gian đa thức. 54
58. CHƯƠNG III Các hệ mật mã khóa đối xứng 3.1. Một số hệ mật mã cổ điển. Trong ch−ơng này ta sẽ giới thiệu một số hệ mật mã có khóa đối xứng, tức là những hệ mật mã mà khóa lập mật mã và khóa giải mật mã là trũng nhau, và vì vậy khóa mật mã chung đó phải đ−ợc giữ bí mật, chỉ riêng hai đối tác (ng−ời lập mật mã để gửi đi và ng−ờn nhận mật mã gửi đến) đ−ợc biết mà thôi. Trong suốt một thời kỳ lịch sử dài từ thời cổ đại cho đến vài ba thập niên gần đây, các ph−ơng pháp mật mã đ−ợc sử dụng trong thực tế đều là mật mã khoá đối xứng, từ hệ mật mã Ceasar đã đ−ợc dùng hơn nghìn năm tr−ớc cho đến các hệ mật mã đ−ợc sử dụng với sự trợ giúp của kỹ thuật máy tính hiện đại trong thời gian gần đây. Tr−ớc hết ta hãy bắt đầu với một số hệ mật mã cổ điển. 3.1.1. Mã chuyển dịch (shift cipher) Các hệ mật mã dùng phép chuyển dịch nói trong mục này cũng nh− nhiều hệ mật mã tiếp sau đều có bảng ký tự bản rõ và bảng ký tự bản mã là bảng ký tự của ngôn ngữ viết thông th−ờng. Vì bảng ký tự tiếng Việt có dùng nhiều dấu phụ làm cho cách xác định ký tự khó thống nhất, nên trong tài liệu này ta sẽ lấy bảng ký tự tiếng Anh để minh hoạ, bảng ký tự này gồm có 26 ký tự, đ−ợc đánh số từ 0 đến 25 nh− trình bày ở tiết 1.2.1, ta có thể đồng nhất nó với tập Z26. Nh− vậy, sơ đồ các hệ mật mã chuyển dịch đ−ợc định nghĩa nh− sau: S = (P , C , K , E , D ) , trong đó P = C = K = Z26 , các ánh xạ E và D đ−ợc cho bởi: 55
59. với mọi K, x , y ∈ Z26 : E (K, x) = x +K mod26, D (K, y) = y - K mod26. Các hệ mật mã đ−ợc xác định nh− vậy là đúng đắn, vì với mọi K, x , y ∈ Z26 ta đều có: dK(eK(x)) = (x +K ) - K mod26 = x. Các hệ mật mã chuyển dịch đã đ−ợc sử dụng từ rất sớm, theo truyền thuyết, hệ mã đó với K =3 đã đ−ợc dùng bởi J. Caesar từ thời đế quốc La mã, và đ−ợc gọi là hệ mã Caesar. Thí dụ: Cho bản rõ hengapnhauvaochieuthubay, chuyển dãy ký tự đó thành dãy số t−ơng ứng ta đ−ợc: x = 7 4 13 6 0 15 13 7 0 20 21 0 14 2 7 8 4 20 19 7 20 1 0 24. Nếu dùng thuật toán lập mật mã với khoá K = 13, ta đ−ợc bản mã là: y = 20 17 0 19 13 2 0 20 13 7 8 13 1 15 20 21 17 7 6 20 7 14 13 11, chuyển d−ới dạng ký tự thông th−ờng ta đ−ợc bản mật mã là: uratncaunhinbpuv rhguhonl . Để giải bản mật mã đó, ta chỉ cần chuyển nó lại d−ới dạng số (để đ−ợc dãy y), rồi thực hiện thuật toán giải mã, tức trừ từng số hạng với 13 (theo môđuyn 26), đ−ợc lại dãy x, chuyển thành dãy ký tự là đ−ợc bản rõ ban đầu. Các hệ mật mã chuyển dịch tuy dễ sử dụng, nh−ng việc thám mã cũng khá dễ dàng, số các khoá có thể có là 26; nhận đ−ợc một bản mã, ng−ời thám mã chỉ cần thử dùng lần l−ợt tối đa là 26 khoá đó để giải mã, ắt sẽ phát hiện ra đ−ợc khoá đã dùng và cả bản rõ! 3.1.2. Mã thay thế (substitution cipher). Sơ đồ các hệ mật mã thay thế đ−ợc định nghĩa nh− sau: S = (P , C , K , E , D ) , trong đó P = C = Z26 , K là tập hợp tất cả các phép hoán vị trên Z26 các ánh xạ E và D đ−ợc cho bởi: 56
60. exπ ()= π ()x, −1 dyπ ()= π ()y, với mọi x ∈ P , y ∈ C , π ∈ K là một phép hoán vị trên Z26 . Ta th−ờng đồng nhất Z26 với bảng ký tự tiếng Anh, do đó phép hoán vị trên Z26 cũng đ−ợc hiểu là một phép hoán vị trên tập hợp các ký tự tiếng Anh, thí dụ một phép hoán vị π đ−ợc cho bởi bảng : a b c d e f g h i j k l m n o p q r x n y a h p o g z q w b t s f l r c s t u v w x y z v m u e k j d i Với hệ mật mã thay thế có khoá π, bản rõ x = hengapnhauvaochieuthubay sẽ đ−ợc chuyển thành bản mật mã y = ghsoxlsgxuexfygzhumgunxd . Thuật toán giải mã với khoá π, ng−ợc lại sẽ biến y thành bản rõ x. Sơ đồ hệ mật mã có số khoá có thể bằng số các phép hoán vị 26 trên tập Z26 , tức là 26! khoá, đó là một số rất lớn (26!> 4.10 ). Do đó, việc duyệt lần l−ợt tất cả các khoá có thể để thám mã là không thực tế, ngay cả dùng máy tính. Tuy vậy, có những ph−ơng pháp thám mã khác hiệu quả hơn, làm cho các hệ mật mã thay thế không thể đ−ợc xem là an toàn. 3.1.3. Mã apphin. Sơ đồ các hệ mật mã apphin đ−ợc định nghĩa nh− sau: 57
61. S = (P , C , K , E , D ) , trong đó P = C = Z26 , K = { (a,b) ∈ Z26 x Z26 ⏐ gcd(a, 26) = 1} , các ánh xạ E và D đ−ợc cho bởi: eK(x ) = ax + b mod26, -1 dK(y ) = a (y - b) mod26, với mọi x ∈ P , y ∈ C , K = (a, b) ∈ K . Có điều kiện gcd (a, 26) = 1 là để bảo đảm có phần tử nghịch -1 đảo a mod26 của a , làm cho thuật toán giải mã dK luôn thực hiện đ−ợc. Có tất cả φ(26) = 12 số a ∈ Z26 nguyên tố với 26, đó là các số 1, 3, 5, 7 ,9, 11, 15, 17, 19, 21, 23, 25, và các số nghịch đảo theo mod26 t−ơng ứng của chúng là 1, 9, 21, 15, 3, 19, 7, 23, 11, 5, 17, 25. Thí dụ với bản rõ hengapnhauvaochieuthubay, có dãy số t−ơng ứng là: x = 7 4 13 6 0 15 13 7 0 20 21 0 14 2 7 8 4 20 19 7 20 1 0 24. Nếu dùng hệ mật mã apphin với khoá K=(5, 6) ta sẽ đ−ợc bản mật mã y = 15 0 19 10 6 3 19 15 6 2 7 6 24 16 15 20 0 2 23 15 2 11 6 22, chuyển sang dòng ký tự tiếng Anh ta đ−ợc bản mật mã d−ới dạng patkgdtpgchgyqpuacxpclgw . Vì có 12 số thuộc Z26 nguyên tố với 26, nên số các khoá có thể có (do đó , số các hệ mật mã apphin) là bằng 12x26 =312, một con số không lớn lắm nếu ta sử dụng máy tính để thực hiện việc thám mã bằng cách duyệt lần l−ợt tất cả các khoá có thể; nh− vậy, mã apphin cũng không còn đ−ợc xem là mã an toàn ! 3.1.4. Mã Vigenère. 58
62. Sơ đồ mật mã này lấy tên của Blaise de Vigenère, sống vào thế kỷ 16. Khác với các hệ mật mã đã kể tr−ớc, các hệ mật mã Vigenère không thực hiện trên từng ký tự một, mà đ−ợc thực hiện trên từng bộ m ký tự (m là số nguyên d−ơng). Sơ đồ các hệ mật mã Vigenère đ−ợc định nghĩa nh− sau: S = (P , C , K , E , D ) , m trong đó P = C = K = Z26 , các ánh xạ E và D đ−ợc cho bởi: eK(x1, , xm ) = ( x1+k1, , xm+km ) mod26 dK(y1, , ym ) = ( y1-k1 , , ym-km ) mod26 với mọi x =(x1, , xm ) ∈ P , y =(y1, , ym ) ∈ C , K = (k1, ,km)∈ K . Sơ đồ mã Vigenère có thể đ−ợc xem là mở rộng của sơ đồ mã chuyển dịch, nếu mã chuyển dịch thực hiện việc chuyển dịch từng ký tự một thì mã Vigenère thực hiện đồng thời từng bộ m ký tự liên tiếp. Thí dụ lấy m = 6 và K = (2, 8, 15, 7, 4, 17). Để lập mật mã cho bản rõ hengapnhauvaochieuthubay, ta cũng chuyển nó thành dãy số và tách thành từng đoạn 6số liên tiếp: x = 7 4 13 6 0 15⏐ 13 7 0 20 21 0⏐ 14 2 7 8 4 20 ⏐19 7 20 1 0 24. (nếu độ dài của x không phải là bội số của 6, ta có thể qui −ớc thêm vào đoạn cuối của x một số phần tử nào đó, chẳng hạn là các số 0, để bao giờ cũng có thể xem là x tách đ−ợc thành các đoạn có 6 số liên tiếp). Cộng theo mod26 các số trong từng đoạn đó với các số t−ơng ứng trong khoá K ta sẽ đ−ợc bản mật mã y = 9 12 2 13 4 6 ⏐15 15 15 1 25 17⏐ 16 10 22 15 8 11⏐ 21 15 9 8 4 15 chuyển sang dãy ký tự ta đ−ợc bản mã là jmcnegpppbzrqkwpilvpjiep . 59
63. Từ bản mã đó, dùng thuật toán giải mã t−ơng ứng ta lại thu đ−ợc bản rõ ban đầu. Tập K có tất cả là 26m phần tử, do đó với mỗi m có tất cả là 26m hệ mật mã Vigenère khác nhau (với m = 6 thì số đó là 308,915,776), duyệt toàn bộ chừng ấy khoá để thám mã bằng tính thủ công thì khó, nh−ng nếu dùng máy tính đủ mạnh thì cũng không đến nỗi khó lắm! 3.1.5. Mã Hill. Sơ đồ mật mã này đ−ợc đề xuất bởi Lester S. Hill năm 1929. Cũng giống nh− sơ đồ mã Vigenère, các hệ mã này đ−ợc thực hiện trên từng bộ m ký tự liên tiếp, điều khác là mỗi ký tự của bản mã đ−ợc xác định bởi một tổ hợp tuyến tính (trên vành Z26) của m ký tự trong bản rõ. Nh− vậy, khoá sẽ đ−ợc cho bởi một ma trận cấp m, tức là một phần tử của K ∈ Z m xm. Để phép biến đổi tuyến tính xác định bởi ma trận K có phép nghịch đảo, bản thân ma trận K cũng phải có ma trận nghịch đảo K -1 theo mod26; mà điều kiện cần và đủ để K có nghịch đảo là định thức của nó, ký hiệu detK, nguyên tố với 26. Vậy, sơ đồ mật mã Hill đ−ợc định nghĩa là sơ đồ S = (P , C , K , E , D ) , m mmì trong đó P = C = Z26 , K = {KZ∈ 26 : gcd(det K,26) = 1} , các ánh xạ E và D đ−ợc cho bởi: eK(x1, , xm ) = (x1, , xm ).K mod26, -1 dK(y1, , ym ) = (y1, , ym ). K mod26 với mọi x =(x1, , xm ) ∈ P , y =(y1, , ym ) ∈ C , K ∈ K . ⎛⎞11 8 Thí dụ : Chọn m = 2, và K =⎜⎟. ⎝⎠37 60
64. Với bộ hai ký tự x = (x1 ,x2) ta có mã y = (y1 , y2).K đ−ợc tính bởi: y1 = 11x1 + 3x2 mod26 y2 = 8x1 + 7x2 mod26 . Ta lấy lại bản rõ hengapnhauvaochieuthubay, ta cũng chuyển nó thành dãy số và tách thành từng đoạn 2 số liên tiếp: x = 7 4 ⏐13 6⏐ 0 15⏐ 13 7 ⏐0 20⏐ 21 0⏐ 14 2 ⏐7 8⏐ 4 20 ⏐19 7⏐ 20 1⏐ 0 24. Lập mật mã cho từng đoạn hai số liên tiếp, rồi nối ghép lại ta đ−ợc y = 11 6⏐5 16⏐ 19 1⏐8 21⏐8 2⏐23 12⏐4 22⏐23 8⏐0 16⏐22 19⏐15 11⏐20 12. Và từ đó ta đ−ợc bản mật mã d−ới dạng dãy ký tự là lgfqtbivicxmewxiaqwtplum . Chú ý rằng −1 -1 ⎛⎞11 8 ⎛7 18⎞ K = ⎜⎟(mod 26) = ⎜ ⎟, ⎝⎠37 ⎝2311⎠ và giải mã bằng cách nhân từng đoạn hai số liên tiếp của y với K -1 ta sẽ đ−ợc lại dãy x, và từ đó đ−ợc lại bản rõ. Với mỗi số m cho tr−ớc, số các khoá có thể có là bằng số các ma trận K có detK nguyên tố với 26. Ta không có công thức để tính con số đó, tuy biết rằng khi m lớn thì số đó cũng là rất lớn, và tất nhiên việc thám mã bằng cách duyệt lần l−ợt toàn bộ các hệ mã Hill có cùng số m là không khả thi. Mặc dù vậy, từ lâu ng−ời ta cũng đã tìm đ−ợc những ph−ơng pháp thám mã khác đối với hệ mã Hill một cách khá hiệu quả mà ta sẽ giới thiệu trong một phần sau. 3.1.6. Mã hoán vị. Các hệ mã hoán vị cũng đ−ợc thực hiện trên từng bộ m ký tự liên tiếp, nh−ng bản mật mã chỉ là một hoán vị của các ký tự trong từng bộ m ký tự của bản rõ. Ta ký hiệu Sm là tập hợp tất cả các phép hoán vị của tập hợp { 1,2, ,m }. Sơ đồ các phép mã hoán vị đ−ợc cho bởi S = (P , C , K , E , D ) , 61
65. m trong đó P = C = Z26 , K = Sm , các ánh xạ E và D đ−ợc cho bởi: eK(x1, , xm ) = (xππ(1) , , x(m) ), (y, , y), dK(y1, , ym ) = π−1(1) π−1(m) -1 với mọi x =(x1, , xm ) ∈ P , y =(y1, , ym ) ∈ C , K = π ∈ Sm , π là hoán vị nghịch đảo của π . Thí dụ: Chọn m = 6 và phép hoán vị π ∈S6 đ−ợc cho bởi: i = 1 2 3 4 5 6 ( π (i) = 3 5 1 6 4 2 . Khi đó phép hoán vị π -1 sẽ là j = 1 2 3 4 5 6 π π -1 (j ) = 3 6 1 5 2 4 . Với bản rõ hengapnhauvaochieuthubay, tức cũng là với x = 7 4 13 6 0 15⏐ 13 7 0 20 21 0⏐ 14 2 7 8 4 20 ⏐19 7 20 1 0 24. ta sẽ có bản mã t−ơng ứng là: y = 13 0 7 15 6 4 0 21 13 0 20 7 7 4 14 20 8 2 20 0 19 24 1 7 chuyển thành dãy ký tự là nahpgeavnauhheouicuatybh . Dùng cho từng bộ 6 ký tự liên tiếp của bản mật mã này (tức là của y) phép giải mã dK ta sẽ thu lại đ−ợc x và bản rõ ban đầu. Chú ý rằng mã hoán vị là một tr−ờng hợp riêng của mã Hill. Thực vậy, cho phép hoán vị π trên {1,2, ,m } , ta xác định ma trận Kπ = (ki j ) với ki j = 1 nếu i = π(j ), và = 0 nếu ng−ợc lại, thì dễ thấy rằng mã Hill với khoá Kπ cho cùng một phép mật mã nh− mã loán vị với khoá π. Với mỗi m cho tr−ớc, số các hệ mật mã hoán vị có thể có là m ! 62
66. 3.2. Thám mã đối với các hệ mật mã cổ điển. 3.2.1. Một vài nhận xét chung. Nh− đã trình bày trong tiết 1.5 ch−ơng 1, mục đích của việc thám mã là dựa vào thông tin về bản mật mã có thể thu thập đ−ợc trên đ−ờng truyền tin mà phát hiện lại đ−ợc bản rõ của thông báo. Vì sơ đồ của hệ mật mã đ−ợc sử dụng th−ờng khó mà giữ đ−ợc bí mật, nên ta th−ờng giả thiết thông tin xuất phát của bài toán thám mã là sơ đồ hệ mật mã đ−ợc sử dụng và bản mật mã của thông báo, nhiệm vụ của thám mã là tìm bản rõ của thông báo đó. Ngoài các thông tin xuất phát đó, tuỳ tr−ờng hợp cụ thể, còn có thể có thêm các thông tin bổ sung khác, vì vậy bài toán thám mã đ−ợc phân thành các loại bài toán khác nhau nh−: thám mã chỉ dựa vào bản mã, thám mã khi biết cả bản rõ, thám mã khi có bản rõ đ−ợc chọn, thám mã khi có bản mã đ−ợc chọn (xem mục 1.5, ch−ơng 1). Trong tiết này ta sẽ trình bày một vài ph−ơng pháp thám mã đối với các hệ mật mã cổ điển mô tả trong tiết tr−ớc. Và ta cũng giả thiết các bản rõ cũng nh− bản mã đều đ−ợc xây dựng trên bảng ký tự tiếng Anh, và hơn nữa các thông báo là các văn bản tiếng Anh. m Nh− vậy, ta luôn có P = C = Z26 hay Z26 , và có thêm thông tin là các bản rõ tuân theo các qui tắc từ pháp và cú pháp của ngôn ngữ tiếng Anh. Đây là một căn cứ quan trọng của các ph−ơng pháp thám mã đối với các hệ mật mã cổ điển. Tiếc là việc dùng mật mã để truyền đ−a thông tin tiếng Việt không để lại cho ta nhiều t− liệu để nghiên cứu, và những nghiên cứu về từ pháp và cú pháp cũng ch−a cho ta những qui tắc thống kê xác suất đủ tin cậy, nên trong tài liệu này ta ch−a trình bày đ−ợc trên các thí dụ mật mã bằng ngôn ngữ Việt, ta đành tạm m−ợn các thí dụ bằng văn bản tiếng Anh để minh hoạ, mong đ−ợc bạn đọc bổ sung sau. Các kết quả chủ yếu đ−ợc sử dụng nhiều nhất trong thám mã là các qui tắc thống kê tần suất xuất hiện các ký tự hay các bộ đôi, bộ ba, ký tự liên tiếp trong các văn bản tiếng Anh. Trên cơ sở phân tích các số liệu thống kê từ một l−ợng rất lớn các văn bản th− từ, sách vở, báo chí, v.v ng−ời ta đã 63
67. thu đ−ợc những kết quả mà các tác giả Beker và Piper đã tổng hợp lại nh− sau: Phân bố xác suất xuất hiện của các ký tự đ−ợc sắp xếp theo thứ tự: 1. Ký tự e có xác suất xuất hiện cao nhất là 0. 127, 2. Các ký tự t, a, o, i, n, s, h, r có xác suất từ 0. 060 đến 0. 090, 3. Các ký tự d , l có xác suất khoảng 0. 04, 4. Các ký tự c, u, m,w, f, g, y, p, b có xác suất từ 0. 015 đến 0.028, 5. Các ký tự v, k, j, x, q, z có xác suất d−ới 0. 01. Ba m−ơi bộ đôi ký tự có xác suất xuất hiện cao nhất là (kể từ cao xuống): th, he, in, er, an, re, ed, on, es, st, en, at, to, nt, ha, nd, ou, ea, ng, as, or, ti, is, et, it, ar, te, se, hi, of. M−ời hai bộ ba ký tự có xác suất xuất hiện cao nhất là: the, ing, and, her, ere, ent, tha, nth, was, eth, for, dth. Sau đây là bảng phân bố xác suất của tất cả các ký tự: A (0) 0.082 B (1) 0.015 C (2) 0.028 D (3) 0.043 E (4) 0.127 F (5) 0. 022 G (6) 0.020 H (7) 0. 061 I (8) 0.070 J (9) 0.002 K (10) 0.008 L (11) 0.040 M (12) 0.024 N (13) 0.067 O (14) 0.075 P (15) 0.019 Q (16) 0.001 R (17) 0.060 S (18) 0.063 T (19) 0.091 U (20) 0.028 V (21) 0.010 W (22) 0.023 X (23) 0.001 Y (24) 0.020 Z (25) 0.001. 3.2.2. Thám mã đối với mã apphin. Khoá mã apphin có dạng K = (a,b) với a, b ∈ Z26 và gcd(a,26)=1. Ký tự mã y và ký tự bản rõ x t−ơng ứng có quan hệ y = a.x + b mod 26. Nh− vậy, nếu ta biết hai cặp (x, y) khác nhau là ta có đ−ợc hai ph−ơng trình tuyến tính để từ đó tìm ra giá trị hai ẩn số a,b, tức là tìm ra K. 64
68. Thí dụ: Ta có bản mật mã: fmxvedkaphferbndkrxrsrefmorudsdkdvshvufedkaprkdlyevlrhhrh . Hãy tìm khoá mật mã và bản rõ t−ơng ứng. Ta thấy trong bản mật mã nói trên, r xuất hiện 8 lần, d 7 lần, e, k, h mỗi ký tự 5 lần, f, s, v mỗi ký tự 4 lần, v.v ; vậy có thể phán đoán r là mã của e , d là mã của t, khi đó có 4a + b = 17 mod26, 19a + b = 3 mod26, giải ra đ−ợc a = 6 , b = 19. Vì gcd(a, 26) = 2 ≠ 1, nên (a, b) không thể là khoá đ−ợc, phán đoán trên không đúng. Ta lại thử chon một phán đoán khác: r là mã của e, h là mã của t . Khi đó có: 4 4a + b = 17 mod26, 19a + b = 7 mod26, ta giải ra đ−ợc a = 3, b = 5. Vì (a, 26) = 1 nên K = (3,5) có thể là khóa cần tìm. Khi đó phép lập mật mã là eK(x ) = 3x +5 mod26, và phép giải mã t−ơng ứng là dK (y) = 9) = 9y - 19 mod26. Dùng phép giải mã đó cho bản mã ta sẽ đ−ợc (d−ới dạng ký tự) bản rõ là: algorithmsarequitegeneraldefinitionsofarithmeticprocesses . Ta có thể kết luận khoá đúng là K = (3, 5) và dòng trên là bản rõ cần tìm. 3.2.3. Thám mã đối với mã Vigenère. Mã Vigenère có thể coi là mã chuyển dịch đối với từng bộ m ký tự. Khoá mã là một bộ K = (k1, , km) gồm m số nguyên mod 26. Việc thám mã gồm hai b−ớc: b−ớc thứ nhất xác định độ dài m, b−ớc thứ hai xác định các số k1, , km. Có hai ph−ơng pháp để xác định độ dài m : phép thử Kasiski và ph−ơng pháp dùng chỉ số trùng hợp. 65
69. Phép thử Kasiski (đề xuất từ 1863). Phép thử dựa vào nhận xét rằng hai đoạn trùng nhau của bản rõ sẽ đ−ợc mã hoá thành hai đoạn trùng nhau của bản mã, nếu khoảng cách của chúng trong văn bản rõ (kể từ ký tự đầu của đoạn này đến ký tự đầu của đoạn kia) là bội số của m. Mặt khác, nếu trong bản mã, có hai đoạn trùng nhau và có độ dài khá lớn (≥ 3 chẳng hạn) thì rất có khả năng chúng là mã của hai đoạn trùng nhau trong bản rõ. Vì vậy, ta thử tìm một đoạn mã (có ba ký tự trở lên) xuất hiện nhiều lần trong bản mã, tính khoảng cách của các lần xuất hiện đó, chẳng hạn đ−ợc d1,d2 ,dt ; khi đó ta có thể phán đoán m = d = gcd(d1, d2, , dt )- −ớc số chung lớn nhất của d1, d2 , dt ; hoặc m là −ớc số của d. Ph−ơng pháp dùng chỉ số trùng hợp: (định nghĩa chỉ số trùng hợp do W.Friedman đ−a ra năm 1920). Định nghĩa 3.1. Cho x = x1, x2 xn là một dãy gồm n ký tự. Xác suất của việc hai phần tử của x trùng nhau đ−ợc gọi là chỉ số trùng hợp của x , ký hiệu là IC(x). Ký hiệu f0, f1, , f25 lần l−ợt là tần suất xuất hiện của a, b, ,z trong x, ta có: 25 25 fi ffii(1+ ) ∑()2 ∑ i=0 i=0 IxC ()==n . ()2 nn(1+ ) Giả sử x là một dãy ký tự (tiếng Anh). Ta có thể hy vọng rằng: 25 2 IC(x) ≈ ∑ pi = 0,065 , i=0 trong đó pi là xác suất của ký tự ứng với số hiệu i cho bởi bảng phân bố xác suất các ký tự (trang 61) Nếu x là một dãy ký tự hoàn toàn ngẫu nhiên thì ta có: 2 IC ≈ 26. (1/26) = 1/26 = 0,038 . 66