Đề tài Tìm hiểu mật mã học và ứng dụng trong xác thực chữ ký điện tử

Nội dung text: Đề tài Tìm hiểu mật mã học và ứng dụng trong xác thực chữ ký điện tử

1. TRƯỜNG ĐẠI HỌC SƯ PHẠM HÀ NỘI KHOA CÔNG NGHỆ THÔNG TIN  NGHIÊN CỨU KHOA HỌC Đề tài: TÌM HIỂU MẬT MÃ HỌC VÀ ỨNG DỤNG TRONG XÁC THỰC CHỮ KÝ ĐIỆN TỬ Giáo viên hƣớng dẫn:PGS.TS.Vũ Đình Hòa Sinh viên thực hiện:Trịnh Mai Hương Hà nội ,2008
2. Mục lục Lời nói đầu 4 Chương 1.Tổng quan về mật mã học 5 1.1.Lịch sử phát triển của mật mã 5 1.1.1.Mật mã học cổ điển 5 1.1.2.Thời trung cổ 6 1.1.4.Mật mã học trong Thế chiến II 8 1.1.5.Mật mã học hiện đại 11 1.2.Một số thuật ngữ sử dụng trong hệ mật mã 16 1.3.Định nghĩa mật mã học 19 1.4.Phân loại hệ mật mã học 21 1.4.1.Mật mã cổ điển. 21 1.4.2.Mật mã hiện đại 23 Chương 2.Hệ mật mã cổ điển 28 2.1.Hệ mã Caesar 28 2.2.Hệ mã Affinne 29 2.3.Hệ mã Vigenère 31 2.4.Hệ mật Hill 33 2.5. Hệ mật Playfair 34 Chương 3. Một số công cụ hỗ trợ cho thuyết mật mã 36 3.1.Lý thuyết số 36 3.1.1.Kiến thức đồng dƣ thức 36 3.1.2.Một số định lý sử dụng trong thuật mã hóa công khai 38 3.2.Lý thuyết độ phức tạp 44 Chương 4. Hệ mật mã công khai 47 4.1.Giới thiệu mật mã với khóa công khai 47 4.1.1.Lịch sử 47 4.1.2.Lý thuyết mật mã công khai 49 4.1.3.Những yếu điểm, hạn chế của mật mã với khóa công khai 51 4.1.4.Ứng dụng của mật mã 52 4.2.Hệ mật RSA 54 4.2.1.Lịch sử 54 4.2.2.Mô tả thuật toán 55 4.2.3.Tốc độ mã hóa RSA 59 4.2.4.Độ an toàn của RSA 61 4.2.5.Sự che dấu thông tin trong hệ thống RSA 64 4.3.Hệ mật Rabin 66 4.3.1.Mô tả giải thuật Rabin 67 4.3.2.Đánh giá hiệu quả 68 4.4.Chữ ký điện tử 68 4.4.1.Định nghĩa 70
3. 4.4.2.Hàm băm 71 4.4.3.Một số sơ đồ chữ ký điện tử 75 Chương 5. Xây dựng phần mềm ứng dụng 82 5.1.Định nghĩa bài toán 82 5.2.Phân tích và thiết kế 82 5.2.1. Quá trình ký trong Message 83 5.2.2. Quá trình kiểm tra xác nhận chữ ký trên tài liệu. 84 5.3.Chƣơng trình cài đặt 88
4. Lời nói đầu Hiện nay , công nghệ thông tin, công nghệ Internet, công nghệ E-mail, E- business phát triển nhƣ vũ bão.Việt Nam đã, đang từng bƣớc áp dụng công nghệ mới để ―tin học hóa xã hội‖ tức là đƣa tin học vào các lĩnh vực của xã hội để cải thiện hoạt động thủ công trƣớc đây.Tin học hóa đã giải phóng sức lao động của con ngƣời bằng cách sáng chế máy hút bụi, máy giặt , máy rửa bát, các con robot làm việc trong hầm mỏ-nơi rất nguy hiểm và độc hại cho sức khỏe của con ngƣời Ngoài ra,Tin học còn đƣợc đƣa vào quản lý hành chính Nhà nƣớc.Trong giai đoạn 2001-2005, Thủ tƣớng Phan Văn Khải phê duyệt nhiều đề án tin học hóa quản lý hành chính Nhà nƣớc với mục tiêu quyết tâm xây dựng một Chính phủ điện tử ở Việt Nam.Nếu đề án này thành công thì ngƣời dân có thể tìm hiểu thông tin cần thiết vốn mang tính giấy tờ nhƣ giấy khai sinh, khai tử, đăng kí lớp học, xin thành lập doanh nghiệp,xin cấp hộ chiếu, xin bảo hộ tác quyền hay quyền sở hữu công nghiệp thông qua địa chỉ mạng mà không cần phải đến cơ quan hành chính.Nhƣ vậy chúng ta có thể trao đổi mọi thông tin qua mạng.Thông tin mà chúng ta gửi đi có thể là thông tin quân sự, tài chính, kinh doanh hoặc đơn giản là một thông tin nào đó mang tính riêng tƣ Điều này dẫn tới một vấn đề xảy ra là Internet là môi trƣờng không an toàn, đầy rủi ro và nguy hiểm, không có gì đảm bảo rằng thông tin mà chúng ta truyền đi không bị đọc trộm trên đƣờng truyền. Do đó, một biện pháp đƣợc đƣa ra nhằm giúp chúng ta tự bảo vệ chính mình cũng nhƣ những thông tin mà chúng ta gửi đi là cần phải mã hóa thông tin.Ngày nay biện pháp này đƣợc nhiều nơi sử dụng nhƣ là công cụ để bảo vệ an toàn cho bản thân.Một ví dụ điển hình các ngân hàng lợi dụng tính năng của mã hóa đã tích hợp công nghệ chữ ký số vào các giao dịch thƣơng mại điện tử trực tuyến, đảm bảo tính toàn v n của dữ liệu, tính bí mật, tính chống chối bỏ giao dịch bằng chứng trong các giao dịch thƣơng mại điện tử online Vì lẽ đó mục đích chính của luận văn là tìm hiểu lý thuyết mật mã để đƣa lý thuyết ứng dụng vào thực tế.
5. Chương 1.Tổng quan về mật mã học 1.1.Lịch sử phát triển của mật mã Mật mã học là một ngành có lịch sử từ hàng nghìn năm nay. Trong phần lớn thời gian phát triển của mình ngoại trừ vài thập kỷ trở lại đây , lịch sử mật mã học chính là lịch sử của những phƣơng pháp mật mã học cổ điển - các phƣơng pháp mật mã hóa với bút và giấy, đôi khi có hỗ trợ từ những dụng cụ cơ khí đơn giản. Vào đầu thế kỷ XX, sự xuất hiện của các cơ cấu cơ khí và điện cơ, chẳng hạn nhƣ máy Enigma, đã cung cấp những cơ chế phức tạp và hiệu quả hơn cho việc mật mã hóa. Sự ra đời và phát triển mạnh mẽ của ngành điện tử và máy tính trong những thập kỷ gần đây đã tạo điều kiện để mật mã học phát triển nhảy vọt lên một tầm cao mới. Sự phát triển của mật mã học luôn luôn đi kèm với sự phát triển của các kỹ thuật phá mã hay thám mã . Các phát hiện và ứng dụng của các kỹ thuật phá mã trong một số trƣờng hợp đã có ảnh hƣởng đáng kể đến các sự kiện lịch sử. Một vài sự kiện đáng ghi nhớ bao gồm việc phát hiện ra bức điện Zimmermann khiến Hoa Kỳ tham gia Thế chiến 1 và việc phá mã thành công hệ thống mật mã của Đức Quốc xã góp phần làm đẩy nhanh thời điểm kết thúc thế chiến II. Cho tới đầu thập kỷ 1970, các kỹ thuật liên quan tới mật mã học hầu nhƣ chỉ nằm trong tay các chính phủ. Hai sự kiện đã khiến cho mật mã học trở nên thích hợp cho mọi ngƣời, đó là: sự xuất hiện của tiêu chuẩn mật mã hóa DES và sự ra đời của các kỹ thuật mật mã hóa khóa công khai. 1.1.1.Mật mã học cổ điển Những bằng chứng sớm nhất về sử dụng mật mã học là các chữ tƣợng hình không tiêu chuẩn tìm thấy trên các bức tƣợng Ai Cập cổ đại cách đây khoảng 4500 . Những ký hiệu tỏ ra không phải để phục vụ mục đích truyền thông tin bí mật mà có vẻ nhƣ là nhằm mục đích gợi nên những điều thần bí, trí tò mò hoặc thậm chí để tạo sự thích thú cho ngƣời xem. Ngoài ra còn rất nhiều ví dụ khác về những ứng dụng của mật mã học hoặc là những điều tƣơng tự. Muộn hơn, các học
6. giả về tiếng Hebrew có sử dụng một phƣơng pháp mã hóa thay thế bảng chữ cái đơn giản chẳng hạn nhƣ mật mã hóa Atbash khoảng năm 500 đến năm 600 . Mật mã học từ lâu đã đƣợc sử dụng trong các tác phẩm tôn giáo để che giấu thông tin với chính quyền hoặc nền văn hóa thống trị. Ví dụ tiêu biểu nhất là "số chỉ kẻ thù của Chúa" tiếng Anh: Number of the Beast xuất hiện trong kinh Tân Ƣớc của Cơ đốc giáo. Ở đây, số 666 có thể là cách mã hóa để chỉ đến Đế chế La Mã hoặc là đến hoàng đế Nero của đế chế này. Việc không đề cập trực tiếp sẽ đỡ gây rắc rối khi cuốn sách bị chính quyền chú ý. Đối với Cơ đốc giáo chính thống thì việc che dấu này kết thúc khi Constantine cải đạo và chấp nhận đạo Cơ đốc là tôn giáo chính thống của đế chế. Ngƣời Hy Lạp cổ đại cũng đƣợc biết đến là đã sử dụng các kỹ thuật mật mã chẳng hạn nhƣ mật mã scytale . Cũng có những bằng chứng rõ ràng chứng tỏ ngƣời La Mã nắm đƣợc các kỹ thuật mật mã mật mã Caesar và các biến thể . Thậm chí đã có những đề cập đến một cuốn sách nói về mật mã trong quân đội La Mã; tuy nhiên cuốn sách này đã thất truyền. Tại Ấn Độ, mật mã học cũng khá nổi tiếng. Trong cuốn sách Kama Sutra, mật mã học đƣợc xem là cách những ngƣời yêu nhau trao đổi thông tin mà không bị phát hiện. 1.1.2.Thời trung cổ Nguyên do xuất phát có thể là từ việc phân tích bản kinh Qur’an, do nhu cầu tôn giáo, mà kỹ thuật phân tích tần suất đã đƣợc phát minh để phá vỡ các hệ thống mật mã đơn ký tự vào khoảng năm 1000. Đây chính là kỹ thuật phá mã cơ bản nhất đƣợc sử dụng, mãi cho tới tận thời điểm của thế chiến thứ II. Về nguyên tắc, mọi kỹ thuật mật mã đều không chống lại đƣợc kỹ thuật phân tích mã (cryptanalytic technique này cho tới khi kỹ thuật mật mã đa ký tự đƣợc Alberti sáng tạo năm 1465 . Mật mã học ngày càng trở nên quan trọng dƣới tác động của những thay đổi, cạnh tranh trong chính trị và tôn giáo. Chẳng hạn tại châu Âu, trong và sau
7. thời kỳ Phục hƣng, các công dân của các thành bang thuộc Ý, gồm cả các thành bang thuộc giáo phận và Công giáo La Mã, đã sử dụng và phát triển rộng rãi các kỹ thuật mật mã. Tuy nhiên rất ít trong số này tiếp thu đƣợc công trình của Alberti các công trình của họ không phản ảnh sự hiểu biết hoặc tri thức về kỹ thuật tân tiến của Alberti và do đó hầu nhƣ tất cả những ngƣời phát triển và sử dụng các hệ thống này đều quá lạc quan về độ an toàn. Điều này hầu nhƣ vẫn còn đúng cho tới tận hiện nay, nhiều nhà phát triển không xác định đƣợc điểm yếu của hệ thống. Do thiếu hiểu biết cho nên các đánh giá dựa trên suy đoán và hy vọng là phổ biến. Mật mã học, phân tích mã học và sự phản bội của nhân viên tình báo, của ngƣời đƣa thƣ, đều xuất hiện trong âm mƣu Babington diễn ra dƣới triều đại của nữ hoàng Elizabeth I dẫn đến kết cục xử tử nữ hoàng Mary I của Scotland. Một thông điệp đƣợc mã hóa từ thời "ngƣời dƣới mặt nạ sắt" (Man in the Iron Mask) đƣợc giải mã vào khoảng 1900 bởi Étienne Bazeries cho biết một số thông tin về số phận của tù nhân này đáng tiếc thay là những thông tin này cũng chƣa đƣợc rõ ràng cho lắm . Mật mã học, và những lạm dụng của nó, cũng là những phần tử liên quan đến mƣu đồ dẫn tới việc xử tử Mata Hari và âm mƣu quỷ quyệt dẫn đến trò hề trong việc kết án Dreyfus và bỏ tù hai ngƣời đầu thế kỷ 20. May mắn thay, những nhà mật mã học cryptographer cũng nhúng tay vào việc phơi bày mƣu đồ dẫn đến các khúc mắc của Dreyfus; Mata Hari, ngƣợc lại, đã bị bắn chết. Ngoài các nƣớc ở Trung Đông và châu Âu, mật mã học hầu nhƣ không đƣợc phát triển. Tại Nhật Bản, mãi cho tới 1510, mật mã học vẫn chƣa đƣợc sử dụng và các kỹ thuật tiên tiến chỉ đƣợc biết đến sau khi nƣớc này mở cửa với phƣơng Tây thập kỷ 1860). 1.1.3.Mật mã học từ năm 1800 đến Thế chiến II Tuy mật mã học có một lịch sử dài và phức tạp, mãi cho đến thế kỷ 19 nó mới đƣợc phát triển một cách có hệ thống, không chỉ còn là những tiếp cận nhất thời, vô tổ chức. Những ví dụ về phân tích mã bao gồm công trình của Charles Babbage trong kỷ nguyên của Chiến tranh Krim (Crimean War về toán phân tích mật mã đơn ký tự. Công trình của ông, tuy hơi muộn màng, đã đƣợc Friedrich
8. Kasiski, ngƣời Phổ, khôi phục và công bố. Tại thời điểm này, để hiểu đƣợc mật mã học, ngƣời ta thƣờng phải dựa vào những kinh nghiệm từng trải (rules of thumb ; xin xem thêm các bài viết về mật mã học của Auguste Kerckhoffs cuối thế kỷ 19. Trong thập niên 1840, Edgar Allan Poe đã xây dựng một số phƣơng pháp có hệ thống để giải mật mã. Cụ thể là, ông đã bày tỏ khả năng của mình trong tờ báo hằng tuần Alexander's Weekly (Express) Messenger ở Philadelphia, mời mọi ngƣời đệ trình các phƣơng pháp mã hóa của họ, và ông là ngƣời đứng ra giải. Sự thành công của ông gây chấn động với công chúng trong vài tháng. Sau này ông có viết một luận văn về các phƣơng pháp mật mã hóa và chúng trở thành những công cụ rất có lợi, đƣợc áp dụng vào việc giải mã của Đức trong Thế chiến II. Trong thời gian trƣớc và tới thời điểm của Thế chiến II, nhiều phƣơng pháp toán học đã hình thành đáng chú ý là ứng dụng của William F. Friedman dùng kỹ thuật thống kê để phân tích và kiến tạo mật mã, và thành công bƣớc đầu của Marian Rejewski trong việc bẻ gãy mật mã của hệ thống Enigma của Quân đội Đức . Sau Thế chiến II trở đi, cả hai ngành, mật mã học và phân tích mã, ngày càng sử dụng nhiều các cơ sở toán học. Tuy thế, chỉ đến khi máy tính và các phƣơng tiện truyền thông Internet trở nên phổ biến, ngƣời ta mới có thể mang tính hữu dụng của mật mã học vào trong những thói quen sử dụng hằng ngày của mọi ngƣời, thay vì chỉ đƣợc dùng bởi các chính quyền quốc gia hay các hoạt động kinh doanh lớn trƣớc đó. 1.1.4.Mật mã học trong Thế chiến II Trong thế chiến II, các hệ thống mật mã cơ khí và cơ điện tử đƣợc sử dụng rộng rãi mặc dù các hệ thống thủ công vẫn đƣợc dùng tại những nơi không đủ điều kiện. Các kỹ thuật phân tích mật mã đã có những đột phá trong thời kỳ này, tất cả đều diễn ra trong bí mật. Cho đến gần đây, các thông tin này mới dần đƣợc tiết lộ do thời kỳ giữ bí mật 50 năm của chính phủ Anh đã kết thúc, các bản lƣu của Hoa Kỳ dần đƣợc công bố cùng với sự xuất hiện của các bài báo và hồi ký có liên quan.
9. Ngƣời Đức đã sử dụng rộng rãi một hệ thống máy rôto cơ điện tử, dƣới nhiều hình thức khác nhau, có tên gọi là máy Enigma. Vào tháng 12 năm 1932, Marian Rejewski, một nhà toán học tại Cục mật mã Ba Lan (tiếng Ba Lan: Biuro Szyfrów , đã dựng lại hệ thống này dựa trên toán học và một số thông tin có đƣợc từ các tài liệu do đại úy Gustave Bertrand của tình báo quân sự Pháp cung cấp. Đây có thể coi là đột phá lớn nhất trong lịch sử phân tích mật mã trong suốt một nghìn năm trở lại. Rejewski cùng với các đồng sự của mình là Jerzy Różycki và Henryk Zygalski đã tiếp tục nghiên cứu và bắt nhịp với những tiến hóa trong các thành phần của hệ thống cũng nhƣ các thủ tục mật mã hóa. Cùng với những tiến triển của tình hình chính trị, nguồn tài chính của Ba Lan trở nên cạn kiệt và nguy cơ của cuộc chiến tranh trở nên gần kề, vào ngày 25 tháng 7 năm 1939 tại Warszawa, cục mật mã Ba Lan, dƣới chỉ đạo của bộ tham mƣu, đã trao cho đại diện tình báo Pháp và Anh những thông tin bí mật về hệ thống Enigma. Ngay sau khi Thế chiến II bắt đầu ngày 1 tháng 9 năm 1939), các thành viên chủ chốt của cục mật mã Ba Lan đƣợc sơ tán về phía tây nam; và đến ngày 17 tháng 9, khi quân đội Liên Xô tiến vào Ba Lan, thì họ lại đƣợc chuyển sang Romania. Từ đây, họ tới Paris Pháp . Tại PC Bruno, ở gần Paris, họ tiếp tục phân tích Enigma và hợp tác với các nhà mật mã học của Anh tại Bletchley Park lúc này đã tiến bộ kịp thời. Những ngƣời Anh, trong đó bao gồm những tên tuổi lớn của ngành mật mã học nhƣ Gordon Welchaman và Alan Turing, ngƣời sáng lập khái niệm khoa học điện toán hiện đại, đã góp công lớn trong việc phát triển các kỹ thuật phá mã hệ thống máy Enigma. Ngày 19 tháng 4 năm 1945, các tƣớng lĩnh cấp cao của Anh đƣợc chỉ thị không đƣợc tiết lộ tin tức rằng mã Enigma đã bị phá, bởi vì nhƣ vậy nó sẽ tạo điều kiện cho kẻ thù bị đánh bại cơ sở để nói rằng họ đã "không bị đánh bại một cách sòng phẳng" were not well and fairly beaten). Các nhà mật mã học của Hải quân Mỹ với sự hợp tác của các nhà mật mã học Anh và Hà Lan sau 1940 đã xâm nhập đƣợc vào một số hệ thống mật mã của Hải quân Nhât. Việc xâm nhập vào hệ thống JN-25 trong số chúng đã mang lại
10. chiến thắng vẻ vang cho Mỹ trong trận Midway. SIS, một nhóm trong quân đội Mỹ, đã thành công trong việc xâm nhập hệ thống mật mã ngoại giao tối mật của Nhật một máy cơ điện dùng "bộ chuyển mạch dịch bƣớc" stepping switch đƣợc ngƣời Mỹ gọi là Purple ngay cả trƣớc khi thế chiến II bắt đầu. Ngƣời Mỹ đặt tên cho những bí mật mà học tìm đƣợc từ việc thám mã, có thể đặc biệt là từ việc phá mã máy Purple, với cái tên "Magic". Ngƣời Anh sau này đặt tên cho những bí mật mà họ tìm ra trong việc thám mã, đặc biệt là từ luồng thông điệp đƣợc mã hóa bởi các máy Enigma, là "Ultra". Cái tên Anh trƣớc đó của Ultra là Boniface. Quân đội Đức cũng cho triển khai một số thử nghiệm cơ học sử dụng thuật toán mật mã dùng một lần (one-time pad . Bletchley Park gọi chúng là mã Fish, và ông Max Newman cùng đồng nghiệp của mình đã thiết kế ra một máy tính điện tử số khả lập trình programmable digital electronic computer đầu tiên là máy Colossus để giúp việc thám mã của họ. Bộ ngoại giao Đức bắt đầu sử dụng thuật toán mật mã dùng một lần vào năm 1919; một số luồng giao thông của nó đã bị ngƣời ta đọc đƣợc trong Thế chiến II, một phần do kết quả của việc khám phá ra một số tài liệu chủ chốt tại Nam Mỹ, do sự bất cẩn của những ngƣời đƣa thƣ của Đức không hủy thông điệp một cách cẩn thận. Bộ ngoại giao của Nhật cũng cục bộ xây dựng một hệ thống dựa trên nguyên lý của "bộ điện cơ chuyển mạch dịch bƣớc" đƣợc Mỹ gọi là Purple , và đồng thời cũng sử dụng một số máy tƣơng tự để trang bị cho một số tòa đại sứ Nhật Bản. Một trong số chúng đƣợc ngƣời Mỹ gọi là "Máy-M" (M-machine), và một cái nữa đƣợc gọi là "Red". Tất cả những máy này đều ít nhiều đã bị phía Đồng Minh phá mã. SIGABA đƣợc miêu tả trong Bằng sáng chế của Mỹ 6.175.625, đệ trình năm 1944 song mãi đến năm 2001 mới đƣợc phát hành
11. Các máy mật mã mà phe Đồng minh sử dụng trong thế chiến II, bao gồm cả máy TypeX của Anh và máy SIGABA của Mỹ, đều là những thiết kế cơ điện dùng rôto trên tinh thần tƣơng tự nhƣ máy Enigma, song với nhiều nâng cấp lớn. Không có hệ thống nào bị phá mã trong quá trình của cuộc chiến tranh. Ngƣời Ba Lan sử dụng máy Lacida, song do tính thiếu an ninh, máy không tiếp tục đƣợc dùng. Các phân đội trên mặt trận chỉ sử dụng máy M-209 và các máy thuộc họ M-94 ít bảo an hơn. Đầu tiên, các nhân viên mật vụ trong Cơ quan đặc vụ của Anh Special Operations Executive - SOE sử dụng "mật mã thơ" các bài thơ mà họ ghi nhớ là những chìa khóa , song ở những thời kỳ sau trong cuộc chiến, họ bắt đầu chuyển sang dùng các hình thức của mật mã dùng một lần (one-time pad). 1.1.5.Mật mã học hiện đại Nhiều ngƣời cho rằng kỷ nguyên của mật mã học hiện đại đƣợc bắt đầu với Claude Shannon, ngƣời đƣợc coi là cha đẻ của mật mã toán học. Năm 1949 ông đã công bố bài Lý thuyết về truyền thông trong các hệ thống bảo mật (Communication Theory of Secrecy Systems trên tập san Bell System Technical Journal - Tập san kỹ thuật của hệ thống Bell - và một thời gian ngắn sau đó, trong cuốn Mathematical Theory of Communication - Lý thuyết toán học trong truyền thông - cùng với tác giả Warren Weaver. Những công trình này, cùng với những công trình nghiên cứu khác của ông về lý thuyết về tin học và truyền thông (information and communication theory , đã thiết lập một nền tảng lý thuyết cơ bản cho mật mã học và thám mã học. Với ảnh hƣởng đó, mật mã học hầu nhƣ bị
12. thâu tóm bởi các cơ quan truyền thông mật của chính phủ, chẳng hạn nhƣ NSA, và biến mất khỏi tầm hiểu biết của công chúng. Rất ít các công trình đƣợc tiếp tục công bố, cho đến thời kỳ giữa thập niên 1970, khi mọi sự đƣợc thay đổi. Thời kỳ giữa thập niên kỷ 1970 đƣợc chứng kiến hai tiến bộ công chính lớn (công khai . Đầu tiên là sự công bố đề xuất Tiêu chuẩn mật mã hóa dữ liệu (Data Encryption Standard) trong "Công báo Liên bang" (Federal Register ở nƣớc Mỹ vào ngày 17 tháng 3 năm 1975. Với đề cử của Cục Tiêu chuẩn Quốc gia National Bureau of Standards - NBS hiện là NIST , bản đề xuất DES đƣợc công ty IBM (International Business Machines đệ trình trở thành một trong những cố gắng trong việc xây dựng các công cụ tiện ích cho thƣơng mại, nhƣ cho các nhà băng và cho các tổ chức tài chính lớn. Sau những chỉ đạo và thay đổi của NSA, vào năm 1977, nó đã đƣợc chấp thuận và đƣợc phát hành dƣới cái tên Bản Công bố về Tiêu chuẩn Xử lý Thông tin của Liên bang (Federal Information Processing Standard Publication - FIPS phiên bản hiện nay là FIPS 46-3 . DES là phƣơng thức mật mã công khai đầu tiên đƣợc một cơ quan quốc gia nhƣ NSA "tôn sùng". Sự phát hành bản đặc tả của nó bởi NBS đã khuyến khích sự quan tâm chú ý của công chúng cũng nhƣ của các tổ chức nghiên cứu về mật mã học. Năm 2001, DES đã chính thức đƣợc thay thế bởi AES viết tắt của Advanced Encryption Standard - Tiêu chuẩn mã hóa tiên tiến khi NIST công bố phiên bản FIPS 197. Sau một cuộc thi tổ chức công khai, NIST đã chọn Rijndael, do hai nhà mật mã ngƣời Bỉ đệ trình, và nó trở thành AES. Hiện nay DES và một số biến thể của nó nhƣ Tam phần DES (Triple DES); xin xem thêm trong phiên bản FIPS 46-3 , vẫn còn đƣợc sử dụng, do trƣớc đây nó đã đƣợc gắn liền với nhiều tiêu chuẩn của quốc gia và của các tổ chức. Với chiều dài khoá chỉ là 56-bit, nó đã đƣợc chứng minh là không đủ sức chống lại những tấn công kiểu vét cạn (brute force attack - tấn công dùng bạo lực . Một trong những cuộc tấn công kiểu này đƣợc thực hiện bởi nhóm "nhân quyền cyber" cyber civil-rights group) tên là Tổ chức tiền tuyến điện tử (Electronic Frontier Foundation vào năm 1997, và đã phá mã thành công trong 56 tiếng đồng hồ câu chuyện này đƣợc nhắc đến trong cuốn Cracking DES Phá vỡ DES , đƣợc xuất bản bởi "O'Reilly and Associates".
13. Do kết quả này mà hiện nay việc sử dụng phƣơng pháp mật mã hóa DES nguyên dạng, có thể đƣợc khẳng định một cách không nghi ngờ, là một việc làm mạo hiểm, không an toàn, và những thông điệp ở dƣới sự bảo vệ của những hệ thống mã hóa trƣớc đây dùng DES, cũng nhƣ tất cả các thông điệp đƣợc truyền gửi từ năm 1976 trở đi sử dụng DES, đều ở trong tình trạng rất đáng lo ngại. Bất chấp chất lƣợng vốn có của nó, một số sự kiện xảy ra trong năm 1976, đặc biệt là sự kiên công khai nhất của Whitfield Diffie, chỉ ra rằng chiều dài khóa mà DES sử dụng 56-bit là một khóa quá nhỏ. Đã có một số nghi ngờ xuất hiện nói rằng một số các tổ chức của chính phủ, ngay tại thời điểm hồi bấy giờ, cũng đã có đủ công suất máy tính để phá mã các thông điệp dùng DES; rõ ràng là những cơ quan khác cũng đã có khả năng để thực hiện việc này rồi. Tiến triển thứ hai, vào năm 1976, có lẽ còn đột phá hơn nữa, vì tiến triển này đã thay đổi nền tảng cơ bản trong cách làm việc của các hệ thống mật mã hóa. Đó chính là công bố của bài viết phƣơng hƣớng mới trong mật mã học (New Directions in Cryptography của Whitfield Diffie và Martin Hellman. Bài viết giới thiệu một phƣơng pháp hoàn toàn mới về cách thức phân phối các khóa mật mã. Đây là một bƣớc tiến khá xa trong việc giải quyết một vấn đề cơ bản trong mật mã học, vấn đề phân phối khóa, và nó đƣợc gọi là trao đổi khóa Diffie-Hellman (Diffie-Hellman key exchange . Bài viết còn kích thích sự phát triển gần nhƣ tức thời của một lớp các thuật toán mật mã hóa mới, các thuật toán chìa khóa bất đối xứng (asymmetric key algorithms). Trƣớc thời kỳ này, hầu hết các thuật toán mật mã hóa hiện đại đều là những thuật toán khóa đối xứng (symmetric key algorithms , trong đó cả ngƣời gửi và ngƣời nhận phải dùng chung một khóa, tức khóa dùng trong thuật toán mật mã, và cả hai ngƣời đều phải giữ bí mật về khóa này. Tất cả các máy điện cơ dùng trong thế chiến II, kể cả mã Caesar và mã Atbash, và về bản chất mà nói, kể cả hầu hết các hệ thống mã đƣợc dùng trong suốt quá trình lịch sử nữa đều thuộc về loại này. Đƣơng nhiên, khóa của một mã chính là sách mã codebook , và là cái cũng phải đƣợc phân phối và giữ gìn một cách bí mật tƣơng tự.
14. Do nhu cầu an ninh, khóa cho mỗi một hệ thống nhƣ vậy nhất thiết phải đƣợc trao đổi giữa các bên giao thông liên lạc bằng một phƣơng thức an toàn nào đấy, trƣớc khi họ sử dụng hệ thống thuật ngữ thƣờng đƣợc dùng là 'thông qua một kênh an toàn' , ví dụ nhƣ bằng việc sử dụng một ngƣời đƣa thƣ đáng tin cậy với một cặp tài liệu đƣợc khóa vào cổ tay bằng một cặp khóa tay, hoặc bằng cuộc gặp gỡ mặt đối mặt, hay bằng một con chim bồ câu đƣa thƣ trung thành Vấn đề này chƣa bao giờ đƣợc xem là dễ thực hiện, và nó nhanh chóng trở nên một việc gần nhƣ không thể quản lý đƣợc khi số lƣợng ngƣời tham gia tăng lên, hay khi ngƣời ta không còn các kênh an toàn để trao đổi khóa nữa, hoặc lúc họ phải liên tục thay đổi các chìa khóa - một thói quen nên thực hiện trong khi làm việc với mật mã. Cụ thể là mỗi một cặp truyền thông cần phải có một khóa riêng nếu, theo nhƣ thiết kế của hệ thống mật mã, không một ngƣời thứ ba nào, kể cả khi ngƣời ấy là một ngƣời dùng, đƣợc phép giải mã các thông điệp. Một hệ thống thuộc loại này đƣợc gọi là một hệ thống dùng chìa khóa mật, hoặc một hệ thống mật mã hóa dùng khóa đối xứng. Hệ thống trao đổi khóa Diffie-Hellman cùng những phiên bản đƣợc nâng cấp kế tiếp hay các biến thể của nó tạo điều kiện cho các hoạt động này trong các hệ thống trở nên dễ dàng hơn rất nhiều, đồng thời cũng an toàn hơn, hơn tất cả những gì có thể làm trƣớc đây. Ngƣợc lại, đối với mật mã hóa dùng khóa bất đối xứng, ngƣời ta phải có một cặp khóa có quan hệ toán học để dùng trong thuật toán, một dùng để mã hóa và một dùng để giải mã. Một số những thuật toán này, song không phải tất cả, có thêm đặc tính là một trong các khóa có thể đƣợc công bố công khai trong khi cái kia không thể nào ít nhất bằng những phƣơng pháp hiện có đƣợc suy ra từ khóa 'công khai'. Trong các hệ thống này, khóa còn lại phải đƣợc giữ bí mật và nó thƣờng đƣợc gọi bằng một cái tên, hơi có vẻ lộn xộn, là khóa 'cá nhân' private key) hay khóa bí mật. Một thuật toán thuộc loại này đƣợc gọi là một hệ thống 'khóa công khai' hay hệ thống khóa bất đối xứng. Đối với những hệ thống dùng các thuật toán này, mỗi ngƣời nhận chỉ cần có một cặp chìa khóa mà thôi bất chấp số ngƣời gửi là bao nhiêu đi chăng nữa . Trong 2 khóa, một khóa luôn đƣợc giữ bí mật và một đƣợc công bố công khai nên không cần phải dùng đến một kênh an toàn để trao đổi khóa. Chỉ cần đảm bảo khóa bí mật không bị lộ thì an ninh của hệ
15. thống vẫn đƣợc đảm bảo và có thể sử dụng cặp khóa trong một thời gian dài. Đặc tính đáng ngạc nhiên này của các thuật toán tạo khả năng, cũng nhƣ tính khả thi, cho phép việc triển khai các hệ thống mật mã có chất lƣợng cao một cách rộng rãi, và ai cũng có thể sử dụng chúng đƣợc. Các thuật toán mật mã khóa bất đối xứng dựa trên một lớp các bài toán gọi là hàm một chiều (one-way functions . Các hàm này có đặc tính là rất dễ dàng thực hiện theo chiều xuôi nhƣng lại rất khó về khối lƣợng tính toán để thực hiện theo chiều ngƣợc lại. Một ví dụ kinh điển cho lớp bài toán này là hàm nhân hai số nguyên tố rất lớn. Ta có thể tính tích số của 2 số nguyên tố này một cách khá dễ dàng nhƣng nếu chỉ cho biết tích số thì rất khó để tìm ra 2 thừa số ban đầu. Do những đặc tính của hàm một chiều, hầu hết các khóa có thể lại là những khóa yếu và chỉ còn lại một phần nhỏ có thể dùng để làm khóa. Vì thế, các thuật toán khóa bất đối xứng đòi hỏi độ dài khóa lớn hơn rất nhiều so với các thuật toán khóa đối xứng để đạt đƣợc độ an toàn tƣơng đƣơng. Ngoài ra, việc thực hiện thuật toán khóa bất đối xứng đòi hỏi khối lƣợng tính toán lớn hơn nhiều lần so với thuật toán khóa đối xứng. Bên cạnh đó, đối với các hệ thống khóa đối xứng, việc tạo ra một khóa ngẫu nhiên để làm khóa phiên chỉ dùng trong một phiên giao dịch là khá dễ dàng. Vì thế, trong thực tế ngƣời ta thƣờng dùng kết hợp: hệ thống mật mã khóa bất đối xứng đƣợc dùng để trao đổi khóa phiên còn hệ thống mật mã khóa đối xứng dùng khóa phiên có đƣợc để trao đổi các bản tin thực sự. Mật mã học dùng khóa bất đối xứng, tức trao đổi khóa Diffie-Hellman, và những thuật toán nổi tiếng dùng khóa công khai / khóa bí mật ví dụ nhƣ cái mà ngƣời ta vẫn thƣờng gọi là thuật toán RSA , tất cả hình nhƣ đã đƣợc xây dựng một cách độc lập tại một cơ quan tình báo của Anh, trƣớc thời điểm công bố của Diffie and Hellman vào năm 1976. Sở chỉ huy giao thông liên lạc của chính phủ (Government Communications Headquarters - GCHQ) - Cơ quan tình báo Anh Quốc - có xuất bản một số tài liệu quả quyết rằng chính họ đã xây dựng mật mã học dùng khóa công khai, trƣớc khi bài viết của Diffie và Hellman đƣợc công bố. Nhiều tài liệu mật do GCHQ viết trong quá trình những năm 1960 và 1970, là những bài cuối cùng cũng dẫn đến một số kế hoạch đại bộ phận tƣơng tự nhƣ
16. phƣơng pháp mật mã hóa RSA và phƣơng pháp trao đổi chìa khóa Diffie-Hellman vào năm 1973 và 1974. Một số tài liệu này hiện đƣợc phát hành, và những nhà sáng chế James H. Ellis, Clifford Cocks, và Malcolm Williamson cũng đã cho công bố một số công trình của họ. 1.2.Một số thuật ngữ sử dụng trong hệ mật mã Sender/Receiver: Ngƣời gửi/Ngƣời nhận dữ liệu. Văn bản (Plaintext -Cleartext : Thông tin trƣớc khi đƣợc mã hoá. Đây là dữ liệu ban đâu ở dạng rõ. Thông tin gốc đƣợc ghi bằng hình ảnh âm thanh, chữ số, chữ viết mọi tín hiệu đều có thể đƣợc số hóa thành các xâu ký tự số Ciphertext: Thông tin, dữ liệu đã đƣợc mã hoá ở dạng mờ Khóa key : Thành phần quan trọng trong việc mã hoá và giải mã. Khóa là đại lƣợng bí mật, biến thiên trong một hệ mật. Khóa nhất định phải là bí mật. Khóa nhất định phải là đại lƣợng biến thiên. Tuy nhiên, có thể có trƣờng hợp đại lƣợng biến thiên trong hệ mật không phải là khóa. Ví dụ: vector khởi tạo IV = Initial Vector ở chế độ CBC, OFB và CFB của mã khối. CryptoGraphic Algorithm: Là các thuật toán đƣợc sử dụng trong việc mã hoá hoặc giải mã thông tin Hệ mã CryptoSystem hay còn gọi là hệ thống mã : Hệ thống mã hoá bao gồm thuật toán mã hoá, khoá, Plaintext,Ciphertext Kỹ thuật mật mã (cryptology là môn khoa học bao gồm hai lĩnh vực: mật mã (crytography) và mã thám (cryptoanalysis). Mật mã cryptography là lĩnh vực khoa học về các phƣơng pháp biến đổi thông tin nhằm mcụ đích bảo vệ thông tin khỏi sự truy cập của những ngƣời không có thẩm quyền. Mã thám cryptoanalysis là lĩnh vực khoa học chuyên nghiên cứu, tìm kiếm yếu điểm của các hệ mật để từ đó đƣa ra phƣơng pháp tấn công các hệ mật đó. Mật mã và mã thám là hai lĩnh vực đối lập nhau nhƣng gắn bó mật thiết với nhau. Không thể xây dựng một hệ mật tốt nếu không hiểu biết sâu về mã thám. Mã thám
17. chỉ ra yếu điểm của hệ mật. Yếu điểm này có thể đƣợc sử dụng để tấn công hệ mật này nhƣng cũng có thể đƣợc sử dụng để cái tiến hệ mật cho tốt hơn. Nếu ngƣời xây dựng hệ mật không có hiểu biết rộng về mã thám, không kiểm tra độ an toàn của hệ mật trƣớc các phƣơng pháp tấn công thì hệ mật của anh ta có thể tỏ ra kém an toàn trƣớc một phƣơng pháp tấn công nào đó mà anh ta chƣa biết. Tuy nhiên, không ai có thể khẳng định là có những phƣơng pháp thám mã nào đã đƣợc biết đến. Đặc nhiệm của các nƣớc luôn giữ bí mật những kết quả thu đƣợc trong lĩnh vực mã thám: kể cả phƣơng pháp thám mã và kết qủa của việc thám mã. Sơ đồ mật mã là tập hợp các thuật toán mã hóa, giả mã, kiểm tra sự toàn v n và các chức năng khác của một hệ mật. Giao thức mật mã là tập hợp các quy tắc, thủ tục quy định cách thức sử dụng sơ đồ mật mã trong một hệ mậ. Có thể thấy rằng "giao thức mật mã" và "sơ đồ mật mã" không đi liền với nhau. Có thể có nhiều giao thức khác mật mã khác nhau quy định các cách thức sử dụng khác nhau của cùng một sơ đồ mật mã nào đó. Lập mã Encrypt là việc biến văn bản nguồn thành văn bản mã Giải mã Decrypt là việc đƣa văn bản đã mã hóa trở thành dạng văn bản nguồn. Định mã encode/decode là việc xác định ra phép tƣơng ứng giữa các chữ và số - Tốc độ mã đƣợc đặc trƣng bởi số lƣợng phép tính N cần thực hiện để mã hóa giải mã một đơn vị thông tin. Cần hiểu rằng tốc độ mã chỉ phụ thuộc vào bản thân hệ mã chứ không phụ thuộc vào đặc tính của thiết bị triển triển khai nó tốc độ máy tính, máy mã . Độ an toàn của hệ mã đặc trƣng cho khả năng của hệ mã chống lại sự thám mã; nó đƣợc đo bằng số lƣợng phép tính đơn giản cần thực hiện để thám hệ mã đó trong điều kiện sử dụng thuật toán phƣơng pháp thám tốt nhất. Cần phải nói thêm rằng có thể xây dựng những hệ mật với độ an tòan bằng vô cùng tức là không thể thám đƣợc về mặt lý thuyết . Tuy nhiên các hệ mật này không thuận tiện cho việc sử dụng, đòi hỏi chi phí cao. Vì thế, trên thực tế, ngƣời ta sử dụng những hệ mật có giới hạn đối với độ an tòan. Do đó bất kỳ hệ mật nào cũng có thể bị thám trong thời gian nào đó ví dụ nhƣ sau 500 năm chẳng hạn).
18. Khả năng chống nhiễu của mã là khả năng chống lại sự phát tán lỗi trong bản tin sau khi giải mã, nếu trƣớc đó xảy ra lỗi với bản mã trong quá trình bản mã đƣợc truyền từ ngƣời gửi đến ngƣời nhận. Có 3 loại lỗi là: lỗi thay thế k ý tự: một k ý tự bị thay đổi thành môt ký tự khác. Ví dụ: abcd → atcd lỗi chèn k ý tự: một ký tự đƣợc chèn vào chuỗi ký tự đƣợc truyền đi. Ví dụ: abcd → azbcd lỗi mất k ý tự: một ký tự trong chuỗi bị mất. Ví dụ: abcd → abd. Nhƣ vậy khái niệm ―khả năng chống nhiễu‖ trong mật mã đƣợc hiểu khác hẳn so với khái niệm này trong lĩnh vực truyền tin. Trong truyền tin ―khả năng chống nhiễu‖ là một trong những đặc trƣng của ―mã chống nhiễu‖ noise combating code) - khả năng phát hiện và sửa lỗi của mã chống nhiễu. Ví dụ: mã 7,4 của Hemming có thể phát hiện 2 lỗi và sửa 1 lỗi trong khối 7 bits 4 bits thông tin có ích và 3 bits dùng để kiếm tra và sửa lỗi . Mã dòng Stream cipher là việc tiến hành mã hóa liên tục trên từng ký tự hay từng bit. Mã khối Block cipher là việc tiến hành mã trên từng khối văn bản. Mục đích của mã hóa là che dấu thông tin trƣớc khi truyền trên kênh truyền. Có nhiều phƣơng pháp mật mã khác nhau, tuy vậy tất cả chúng có hai phép toán thực hiện trong mật mã là phép ―mã hóa‖ và ―giải mã‖. Có thể biểu thị phép mã hóa và phép toán giải mã nhƣ các hàm của hai biến số, hoặc có thể nhƣ một thuật toán, có nghĩa là một thủ tục đối xứng để tính kết quả khi giá trị các tham số đã cho. Bản tin rõ ở đây là tập hợp các dữ liệu trƣớc khi thực hiện mã hóa. Kết quả của phép mã hóa là bản tin đã đƣợc mã hóa. Viêc giải mã bản tin đã đƣợc mã hóa sẽ thu đƣợc bản tin rõ ban đầu. Có biểu thức ―bản tin rõ‖ và ―bản tin đã mã hóa‖ đều có liên quan đến một mật mã cụ thể. Các chữ cái viết hoa D Decipherment và E Encipherment là ký hiệu cho các hàm giải mã và mã hóa tƣơng ứng. Ký
19. hiệu x là là bản tin và y là bản tin đã mã hóa thì biểu thức toán học của phép mã hóa là: y= Ek(x) và của phép giải mã là: x=Dk(y) Trong đó tham số phụ k là khóa mã Khóa mã là một đặc tính quan trọng của thuật toán mật mã.Về nguyên lý nếu hàm y=E x không có một khóa mã nào, thì cũng có thể che dấu đƣợc giá trị của x Tập hợp các giá trị của kháo k đƣợc gọi là ―không gian các khóa‖. Trong một mật 20 mã nào đó, nếu khóa mã có 20 số thập phân sẽ cho khôn gian các khóa là 10 . Nếu khóa nào đó có 50 số nhị phân thì không gian các khóa sẽ là 250. Nếu khóa là một hoán vị của 26 chữ cái A,B,C Z thì không gian các khóa sẽ là 26! Kí hiệu chung: P là thông tin ban đầu, trƣớc khi mã hoá. E là thuật toán mã hoá. D là thuật toán giải mã. C là thông tin mã hoá. K là khoá. Chúng ta biểu diễn quá trình mã hoá và giải mã nhƣ sau: Quá trình mã hoá đƣợc mô tả bằng công thức: Ek(P)=C Quá trình giải mã đƣợc mô tả bằng công thức: Dk(C)=P 1.3.Định nghĩa mật mã học Đối tƣợng cơ bản của mật mã là tạo ra khả năng liên lạc trên một kênh không mật cho hai ngƣời sử dụng tạm gọi là Alice và Bob sao cho đối phƣơng Oscar không thể hiểu đƣợc thông tin truyền đi. Kênh này có thể là một đƣờng dây điện thoại hoặc một mạng máy tính. Thông tin mà Alice muốn gửi cho Bob bản rõ có thể là bản tiếng anh, các dữ liệu bằng số hoặc bất kì tài liệu nào có cấu trúc tùy ý. Alice sẽ mã hóa bản rõ bằng một khóa đã đƣợc xác định trƣớc và gửi bản mã kết quả trên kênh. Osar có bản mã thu trộm đƣợc trên kênh song không thể xác định nọi dung của bản rõ, nhƣng Bob ngƣời đã biết khóa mã có thể giải mã và thu đƣợc bản rõ. Ta sẽ mô tả hình thức hóa nội dung bằng cách dùng khái niệm toán học nhƣ sau Một hệ mật mã là một bộ 5 thành phần P,C,K,E,D thỏa mãn các tính chất sau:
20. 1.P là một tập hữu hạn các bản rõ có thể 2.C là một tập hữu hạn các bản mã có thể 3.K(không gian khóa là tập hữu hạn các khóa có thể 4.Đối với mỗi k K có một quy tắc mã ek: P C và một quy tắc giải mã tƣơng ứng dk D. Mỗi ek:P C và dk :C P là những hàm Dk(ek x =x với mọi bản rõ x P Trong tính chất 4 là tính chất chủ yếu ở đây. Nội dung của nó là nếu mọt bản rõ x đƣợc mã hóa bằng ek và bản mã nhận đƣợc sau đó đƣợc giải mã bằng dk thì ta phải thu đƣợc bản rõ ban đầu x. Alice và Bob sẽ áp dụng thủ tục sau khi dùng hệ mật khóa riêng. Trƣớc tiên họ chọn một khóa ngẫu nhiên k K. Điều này đƣợc thực hiện khi họ ở cùng một chỗ và không bị Oscar theo dõi hoặc họ có một kênh mật trong trƣờng hợp họ ở xa nhau. Sau đó giả sử Alice muốn gửi một thông báo cho Bob trên một kênh không mật và ta xem thông báo này là một chuỗi: x = x1,x2 ,. . .,xn với số nguyên n≥1 nào đó. Ở đây mỗi ký hiệu của mỗi bản rõ xi P, 1≤ i ≤n. Mỗi xi sẽ đƣợc mã hóa bằng quy tắc mã ek với khóa k xác định trƣớc đó.Bởi vậy Alice sẽ tính yi =ek(xi , 1≤ i ≤n và chuỗi bản nhận đƣợc y = y1,y2 ,. . .,yn sẽ đƣợc gửi trên kênh. Khi Bob nhận đƣợc y = y1,y2 ,. . .,yn anh ta sẽ giải mã bằng hàm giải mã dk và thu đƣợc bản rõ gốc x1,x2 ,. . .,xn. Hình 1.1. là một ví dụ về một kênh liên lạc Oscar Alice Bộ mã hóa Bộ giải mã Bob Kênh an toàn Nguồn khóa
21. Rõ ràng trong trƣờng hợp này hàm mã háo phải là hàm đơn ánh tức là ánh xạ 1- 1 , nếu không việc giai rmax sẽ không thực hiện đƣợc một cách tƣờng minh. Ví dụ y= ek(x1)=ek(x2) trong đó x1 ≠ x2, thì Bob sẽ không có cách nào biết liệu sẽ phải giải mã thành x1 hay x2. Chú ý rằng nếu P = C thì mỗi hàm mã hóa ize=‖2‖. Bản quyền Công ty Phát tập các bản mã và tập các bản rõ là đồng nhất thì mỗi một hàm mã sẽ là một sự sắp xếp lại hay hoán vị các phàn tử của tập này 1.4.Phân loại hệ mật mã học Lịch sử của mật mã học chính là lịch sử của phƣơng pháp mật mã học cổ điển- phƣơng pháp mã hóa bút và giấy. Sau này dựa trên nền tảng của mật mã học cổ điển đã xuất hiện phƣơng pháp mã hóa mới. Chính vì vậy mật mã học đƣợc phân chia thành mật mã học cổ điển và mật mã học hiện đại 1.4.1.Mật mã cổ điển (cái này ngày nay vẫn hay dùng trong trò chơi tìm mật thư). Dựa vào kiểu của phép biến đối trong hệ mật mã cổ điển, ngƣời ta chia hệ mật mã làm 2 nhóm: mã thay thế substitution cipher và mã hoán vị permutation/ transposition cipher). • Substitution: thay thế – phƣơng pháp mã hóa trong đó từng kí tự hoặc từng nhóm kí tự của văn bản ban đầu bản rõ - Plaintext đƣợc thay thế bằng một hay một nhóm kí tự khác để tạo ra bản mờ Ciphertext . Bên nhận chỉ cần đảo ngƣợc trình tự thay thế trên Ciphertext để có đƣợc Plaintext ban đầu. Một ví dụ về mã thay thế thuần túy là ―mã bằng từ điển‖. Ngƣời làm công tác mật mã có một quyển từ điển. Để mã hóa một bản tin dạng văn bản , anh ta tìm từ hoặc cụm từ của bản tin trong từ điển và thay bằng một nhóm chữ số tƣơng ứng. Nó giống nhƣ tra từ điển Việt-XXX, trong đó XXX là thứ ngôn ngữ mà chỉ bao gồm các chữ số, đồng thời các ―từ‖ luôn có độ dài cố định thƣờng là 4-5 chữ số . Sau khi ―dịch‖ từ tiếng Việt sang tiếng XXX, ngƣời ta sẽ cộng từng ―từ‖ trong của văn bản trong tiếng XXX với khóa theo module nào đó. Khóa cũng là một ―từ‖ ngẫu nhiên trong tiếng XXX.
22. Một ví dụ đơn giản nữa để minh họa mã thay thế: cho một văn bản chỉ gồm các kí tự latin, tìm trong các nguyên âm a,e,i,o,u và biến đổi chúng theo quy tắc ―a‖ thay bởi ―e‖, ―e‖ thay bởi ―i‖, , ―u‖ thay bởi ―a‖. Ví dụ 2: Viết trên một dòng các ký tự trong bảng chữ cái theo đúng thứ tự.Trên dòng thứ hai, cũng viết ra các ký tự của bản chữ cái nhƣng không bắt đầu bằng chữ ―a‖ mà bằng chữ ―f‖ chẳng hạn.Để mã hóa một ký tự của bản rõ , hãy tìm nó trên dòng thứ nhất , thay nó bởi ký tự nằm trên dòng thứ hai ngay dƣới nó . Thay thế đơn trị và thay thế đa trị là hai trƣờng hợp riêng của mã thay thế.Trở lại với ví dụ về mã từ điển, với ngôn ngữ XXX đã nêu trên.Nếu nhƣ trong từ điển, 1 từ Tiếng Việt tƣơng ứng với 1 và chỉ 1 từ tiếng XXX thì đó là mã thay thế đơn trị.Còn nếu một từ Tiếng Việt tƣơng ứng với 2 hay nhiều hơn 2 từ trong tiếng XXX tức là nhiều từ trong tiếng XXX có cùng một nghĩa trong Tiếng Việt thì đó là mã thay thế đa trị. Tuy không còn đƣợc sử dụng nhƣng ý tƣởng của phƣơng pháp này vẫn đƣợc tiếp tục trong những thuật toán hiện đại • Transposition: hoán vị Bên cạnh phƣơng pháp mã hoá thay thế thì trong mã hoá cổ điển có một phƣơng pháp khác nữa cũng nổi tiếng không kém, đó chính là mã hoá hoán vị. Nếu nhƣ trong phƣơng pháp mã hoá thay thế, các kí tự trong Plaintext đƣợc thay thế hoàn toàn bằng các kí tự trong Ciphertext, thì trong phƣơng pháp mã hoá hoán vị, các kí tự trong Plaintext vẫn đƣợc giữ nguyên, chúng chỉ đƣợc sắp xếp lại vị trí để tạo ra Ciphertext. Tức là các kí tự trong Plaintext hoàn toàn không bị thay đổi bằng kí tự khác. Cụ thể phƣơng pháp hoán vị là phƣơng pháp mã hóa trong đó các kí tự trong văn bản ban đầu chỉ thay đổi vị trí cho nhau còn bản thân các kí tự không hề bị biến đổi. Ví dụ đơn giản nhất: mã hóa bản rõ bằng cách đảo ngƣợc thứ tự các ký tự của nó. Giả sử bản rõ của bạn có độ dài N ký tự. Bạn sẽ hoán đổi vị trí ký tự thứ 1 và ký tự N, ký tự 2 và ký tự N-1, Phức tạp hơn một chút, hoán vị không phải toàn bộ bản rõ mà chia nios ra các đoạn với độ dài L và thực hiện phép hoán vị
23. theo từng đoạn.Khi đó L sẽ là khóa của bạn! Mặt khác L có thể nhận giá trị tuyệt đối 2,3,4 hoặc giá trị tƣơng đối 1/2,1/3,1/4 của N . Vào khoảng thể kỷ V-IV trƣớc Công nguyên, ngƣời ta đã nghĩ ra ―thiết bị mã hóa‖. Đó là một ống hình trụ với bán hình R. Để mã hóa, ngƣời ta quấn băng giấy nhỏ, dài nhƣ giấy dùng trong điện tín quanh ống hình trụ này và viết nọi dung cần mã hóa lên giấy theo chiều dọc của ống. Sau khi gỡ băng giấy khỏi ống thì nội dung sẽ đƣợc che dấu. Muoons giải mã thì phải cuốn băng giấy lên ống cùng có bán kính R.Bán kính R chính là khóa trong hệ mật này. 1.4.2.Mật mã hiện đại a. Symmetric cryptography: mã hóa đối xứng, tức là cả hai quá trình mã hóa và giải mã đều dùng một chìa khóa. Để đảm bảo tính an toàn, chìa khóa này phải đƣợc giữ bí mật. Vì thế các thuật toán loại này còn có tên gọi khác là secret key cryptography (hay private key cryptography), tức là thuật toán mã hóa dùng chìa khóa riêng hay bí mật . Các thuật toán loại này lý tƣởng cho mục đích mã hóa dữ liệu của cá nhân hay tổ chức đơn lẻ nhƣng bộc lộ hạn chế khi thông tin đó phải đƣợc chia sẻ với một bên thứ hai. Giả sử nếu Alice chỉ gửi thông điệp đã mã hóa cho Bob mà không hề báo trƣớc về thuật toán sử dụng, Bob sẽ chẳng hiểu Alice muốn nói gì. Vì thế bắt buộc Alice phải thông báo cho Bob về chìa khóa và thuật toán sử dụng tại một thời điểm nào đó trƣớc đấy. Alice có thể làm điều này một cách trực tiếp mặt đối mặt hay gián tiếp gửi qua email, tin nhắn . Điều này dẫn tới khả năng bị ngƣời thứ ba xem trộm chìa khóa và có thể giải mã đƣợc thông điệp Alice mã hóa gửi cho Bob.
24. Hình 1.Thuật toán mã hóa đối xứng Bob và Alice có cùng một khóa KA-B. Khóa này đƣợc xây dựng sao cho: m = KA-B(KA-B(m)). Trên thực tế, đối với các hệ mật đối xứng, khoá K luôn chịu sự biến đổi trƣớc mỗi pha mã hóa và giải mã. Kết quả của sự biến đổi này ở pha giải mã Kd sẽ khác với kết quả biến đổi ở pha mã hóa Ke.Nếu coi Ke và Kd lần lƣợt là khóa mã hóa và khóa giải mã thì sẽ có khóa giải mã không trùng với khóa mã hóa. Tuy nhiên nếu biết đƣợc khóa Ke thì có thể dễ dàng tính đƣợc Kd và ngƣợc lại. Vậy nên có một định nghĩa rộng hơn cho mã đối xứng là: ―Mã đối xứng là nhóm mã trong đó khóa dùng để giải mã Kd có thể dễ dàng tính đƣợc từ khóa dùng để mã hóa Ke‖. Trong hệ thống mã hoá đối xứng, trƣớc khi truyền dữ liệu, 2 bên gửi và nhận phải thoả thuận về khoá dùng chung cho quá trình mã hoá và giải mã. Sau đó, bên gửi sẽ mã hoá bản rõ Plaintext bằng cách sử dụng khoá bí mật này và gửi thông điệp đã mã hoá cho bên nhận. Bên nhận sau khi nhận đƣợc thông điệp đã mã hoá sẽ sử dụng chính khoá bí mật mà hai bên thoả thuận để giải mã và lấy lại bản rõ Plaintext . Trong quá trình tiến hành trao đổi thông tin giữa bên gửi và bên nhận thông qua việc sử dụng phƣơng pháp mã hoá đối xứng, thì thành phần quan trọng nhất cần phải đƣợc giữ bí mật chính là khoá. Việc trao đổi, thoả thuận về thuật toán đƣợc sử dụng trong việc mã hoá có thể tiến hành một cách công khai, nhƣng bƣớc thoả thuận về khoá trong việc mã hoá và giải mã phải tiến hành bí mật. Chúng ta có thể thấy rằng thuật toán mã hoá đối xứng sẽ rất có lợi khi đƣợc áp dụng trong các cơ quan hay tổ chức đơn lẻ. Nhƣng nếu cần phải trao đổi thông tin với một bên thứ ba thì việc đảm bảo tính bí mật của khoá phải đƣợc đặt lên hàng đầu.
25. Mã hóa đối xứng có thể phân thành hai nhóm phụ: - Block ciphers: thuật toán khối – trong đó từng khối dữ liệu trong văn bản ban đầu đƣợc thay thế bằng một khối dữ liệu khác có cùng độ dài. Độ dài mỗi khối gọi là block size, thƣờng đƣợc tính bằng đơn vị bit. Ví dụ thuật toán 3-Way có kích thƣớc khối bằng 96 bit. Một số thuật toán khối thông dụng là:DES, 3DES, RC5, RC6, 3-Way, CAST, Camelia, Blowfish, MARS, Serpent, Twofish, GOST - Stream ciphers: thuật toán dòng – trong đó dữ liệu đầu vào đƣợc mã hóa từng bit một. Các thuật toán dòng có tốc độ nhanh hơn các thuật toán khối, đƣợc dùng khi khối lƣợng dữ liệu cần mã hóa chƣa đƣợc biết trƣớc, ví dụ trong kết nối không dây. Có thể coi thuật toán dòng là thuật toán khối với kích thƣớc mỗi khối là 1 bit. Một số thuật toán dòng thông dụng: RC4, A5/1, A5/2, Chameleon b. Asymmetric cryptography: mã hóa bất đối xứng, sử dụng một cặp chìa khóa có liên quan với nhau về mặt toán học, một chìa công khai dùng để mã hoá public key và một chìa bí mật dùng để giải mã private key . Một thông điệp sau khi đƣợc mã hóa bởi chìa công khai sẽ chỉ có thể đƣợc giải mã với chìa bí mật tƣơng ứng. Do các thuật toán loại này sử dụng một chìa khóa công khai không bí mật nên còn có tên gọi khác là public-key cryptography (thuật toán mã hóa dùng chìa khóa công khai). Một số thuật toán bất đối xứng thông dụng là : RSA, Elliptic Curve, ElGamal, Diffie Hellman Quay lại với Alice và Bob, nếu Alice muốn gửi một thông điệp bí mật tới Bob, cô ta sẽ tìm chìa công khai của Bob. Sau khi kiểm tra chắc chắn chìa khóa đó chính là của Bob chứ không của ai khác thông qua chứng chỉ điện tử – digital certificate , Alice dùng nó để mã hóa thông điệp của mình và gửi tới Bob. Khi Bob nhận đƣợc bức thông điệp đã mã hóa anh ta sẽ dùng chìa bí mật của mình để giải mã nó. Nếu giải mã thành công thì bức thông điệp đó đúng là dành cho Bob. Alice và Bob trong trƣờng hợp này có thể là hai ngƣời chƣa từng quen biết. Một hệ thống nhƣ vậy cho phép hai ngƣời thực hiện đƣợc giao dịch trong khi không chia sẻ trƣớc một thông tin bí mật nào cả.
26. Hình 2.Thuật toán mã hóa bất đối xứng Trong ví dụ trên ta thấy khóa public và khóa private phải đáp ứng và từ khóa public ngƣời ta không thể tìm ra đƣợc khóa private. Mã hoá khoá công khai ra đời để giải quyết vấn đề về quản lý và phân phối khoá của các phƣơng pháp mã hoá đối xứng. Quá trình truyền và sử dụng mã hoá khoá công khai đƣợc thực hiện nhƣ sau: - Bên gửi yêu cầu cung cấp hoặc tự tìm khoá công khai của bên nhận trên một server chịu trách nhiệm quản lý khoá. - Sau đó hai bên thống nhất thuật toán dùng để mã hoá dữ liệu, bên gửi sử dụng khoá công khai của bên nhận cùng với thuật toán đã thống nhất để mã hoá thông tin đƣợc gửi đi. - Khi nhận đƣợc thông tin đã mã hoá, bên nhận sử dụng khoá bí mật của mình để giải mã và lấy ra thông tin ban đầu. Vậy là với sự ra đời của Mã hoá công khai thì khoá đƣợc quản lý một cách linh hoạt và hiệu quả hơn. Ngƣời sử dụng chỉ cần bảo vệ Private key. Tuy nhiên nhƣợc điểm của Mã hoá khoá công khai nằm ở tốc độ thực hiện, nó chậm hơn rất nhiều so với mã hoá đối xứng. Do đó, ngƣời ta thƣờng kết hợp hai hệ thống mã hoá khoá đối xứng và công khai lại với nhau và đƣợc gọi là Hybrid Cryptosystems. Một số thuật toán mã hoá công khai nổi tiếng: Diffle-Hellman, RSA, Trên thực tế hệ thống mã hoá khoá công khai có hạn chế về tốc độ chậm nên chƣa thể thay thế hệ thống mã hoá khoá bí mật đƣợc, nó ít đƣợc sử dụng để mã hoá dữ
27. liệu mà thƣờng dùng để mã hoá khoá. Hệ thống mã hoá khoá lai ra đời là sự kết hợp giữa tốc độ và tính an toàn của hai hệ thống mã hoá ở trên. Vì vậy ngƣời ta thƣờng sử dụng một hệ thống lai tạp trong đó dữ liệu đƣợc mã hóa bởi một thuật toán đối xứng, chỉ có chìa dùng để thực hiện việc mã hóa này mới đƣợc mã hóa bằng thuật toán bất đối xứng. Hay nói một cách khác là ngƣời ta dùng thuật toán bất đối xứng để chia sẻ chìa khóa bí mật rồi sau đó dùng thuật toán đối xứng với chìa khóa bí mật trên để truyền thông tin. Chúng ta có thể hình dung đƣợc hoạt động của hệ thống mã hoá này nhƣ sau: - Bên gửi tạo ra một khoá bí mật dùng để mã hoá dữ liệu. Khoá này còn đƣợc gọi là Session Key. - Sau đó, Session Key này lại đƣợc mã hoá bằng khoá công khai của bên nhận dữ liệu. - Tiếp theo dữ liệu mã hoá cùng với Session Key đã mã hoá đƣợc gửi đi tới bên nhận. - Lúc này bên nhận dùng khoá riêng để giải mã Session Key và có đƣợc Session Key ban đầu. - Dùng Session Key sau khi giải mã để giải mã dữ liệu. Nhƣ vậy, hệ thống mã hoá khoá lai đã tận dụng tốt đƣợc các điểm mạnh của hai hệ thống mã hoá ở trên đó là: tốc độ và tính an toàn. Điều này sẽ làm hạn chế bớt khả năng giải mã của tin tặc. Cần lƣu ý rằng trên đây, chúng ta đã nhắc đến hai khái niệm có tính chất tƣơng đối là ―dễ‖ và ―khó‖. Ngƣời ta quy ƣớc rằng nếu thuật toán có độ phức tạp không vƣợt quá độ phức tạp đa thức thì bài toán đƣợc coi là dễ; còn lớn hơn thì bài toán đƣợc coi là khó.
28. Chương 2.Hệ mật mã cổ điển 2.1.Hệ mã Caesar Hệ mã Caesar đƣợc xác định trên Z26 do có 26 chữ cái trên bảng chữ cái tiếng Anh mặc dù có thể xác định nó trên Zm với modulus m tùy ý.Dễ dàng thấy rằng , mã dịch vòng sẽ tạo nên một hệ mật nhƣ đã xác định ở trên, tức là Dk(Ek(x)) = x với x Z26. Định nghĩa: Một hệ mật gồm bộ 5 P,C,K,E,D . Giả sử P = C = K = Z26 với 0 ≤ k ≤25, định nghĩa: Ek(x)=x+k mod 26 Và Dk(x)=y-k mod 26 (x,y Z26) Nhận xét:Trong trƣờng hợp k=3, hệ mật thƣờng đƣợc gọi là mã Caesar đã từng đƣợc Julius Caesar sử dụng Ta sẽ sử dụng mã dịch vòng với modulo 26 để mã hóa một văn bản tiếng Anh thông thƣờng bằng cách thiết lập sự tƣơng ứng giữa các ký tự và các thặng dƣ theo modulo 26 nhƣ sau: A0, B1, .,Z25. A B C D E F G H I J K L M 0 1 2 3 4 5 6 7 8 9 10 11 12 N O P Q R S T U V W X Y Z 13 14 15 16 17 18 19 20 21 22 23 24 25 Ví dụ Giả sử khóa cho mã dịch vòng k=11 và bản rõ là: wewillmeetatmidnight Trƣớc tiên biến đổi bản rõ thành dãy các số nguyên nhờ dùng phép tƣơng ứng trên.Ta có: 22 4 22 8 11 11 12 4 4 19 0 19 12 8 3 13 8 6 7 19 Sau đó cộng 11 vào mỗi giá trị rồi rút gọn tổng theo modulo 26
29. 7 15 7 19 22 22 23 15 15 4 11 4 23 19 14 24 19 17 18 4 Cuối cùng biến đổi dãy số nguyên này thành các ký tự thu đƣợc bản mã sau HPHTWWXPPELEXTOYTRSE Để giả mã bản mã này, trƣớc tiên, Bob sẽ biến đổi bản mã thành dãy các số nguyên rồi trừ đi giá trị cho 11 rút gọn modulo 26 và cuối cùng biến đổi lại dãy này thành các ký tự 2.2.Hệ mã Affinne Định nghĩa: Mã tuyến tính Affinne là bộ 5 (P,C,K,E,D thỏa mãn: 1.Cho P=C=Z26 và giả sử P={ a,b Z26 x Z26:UCLN(a,26)=1} 2.Với k= a,b K, ta định nghĩa: Ek(x)=ax+bmod26 -1 Và Dk(y)=a (y-b)mod26, x,y Z26 Để việc giải mã thực hiện đƣợc, yêu cầu cần thiết là hàm Affine phải là đơn ánh.Nói cách khác, với bất kỳ y Z26, ta muốn có đồng nhất thức sau: ax+by(mod26) phải có nghiệm x duy nhất.Đồng dƣ thức này tƣơng đƣơng với axy-b(mod 26) vì y thay đổi trên Z26 nên y-b cũng thay đổi trên Z26.Bởi vậy, ta chỉ cần nghiên cứu phƣơng trình đồng dƣ: axy(mod 26) (y Z26) ta biết rằng phƣơng trình này có một nghiệm duy nhất đối với mỗi y khi và chỉ khi UCLN(a,26)=1. Chứng minh:Trƣớc tiên ta giả sử rằng, UCLN a,26 =d>1. Khi đó, đồng dƣ thức ax0 mod26 sẽ có ít nhất hai nghiệm phân biệt trong Z26 là x=0 và x=26/d. Trong trƣờng hợp này, E x =ax+b mod 26 không pahir là một hàm đơn ánh và bởi vậy nó không thể là hàm mã hóa hợp lệ.
30. Ví dụ do UCLN 4,26 =2 nên 4x+7 không là hàm mã hóa hợp lệ: x và x+13 sẽ mã hóa thành cùng một giá trị đối với bất kỳ x Z26. Ta giả thiết UCLN a,26 =1.Giả sử với x1 và x2 nào đó thỏa mãn: ax1 ax2(mod 26) Khi đó a(x1 – x2)  0 (mod 26) bởi vậy 26| a(x1 – x2) Bây giờ ta sẽ sử dụng một tính chất của phép chia sau: Nếu UCLN a,b =1 và a | bc thì a |c. Vì 26 | a(x1 – x2) và UCLN(a,26)=1 nên ta có: 26 |(x1 –x2) Tức là x1 x2 (mod 26) Tới đây ta chứng tỏ rằng, nếu UCLN a,26 =1 thì một đồng dƣ thức dạng axy mod 26 chỉ có nhiều nhất một nghiệm trong Z26.Dó đó, nếu ta cho x thay đổi trên Z26 thì ax mod 26 sẽ nhận đƣợc 26 giá trị khác nhau theo modulo 26 và đồng dƣ thức axy mod 26 chỉ có nghiệm duy nhất. Ví dụ: Giả sử k= 7,3 .Ta có 7-1 mod 26= 15.Hàm mã hóa là: Ek(x)=7x+3 Và hàm giải mã tƣơng ứng là Dk(x)=15(y-3) mod 26=15y-19 ở đây tất cả các phép toán đều thực hiện trên Z26. Ta sẽ kiểm tra liệu Dk(Ek(x))=x với x Z26 không? Dùng các tính toán trên Z26, ta có Dk(Ek(x))= Dk(7x+3) = 15(7x+3)-19 =x+45-19 =x Để minh họa, ta hãy mã hóa bản rõ ―hot‖. Trƣớc tiên biến đổi các chữ h,o,t thành các thặng dƣ theo modulo 26. Ta đƣợc các số tƣơng ứng là: 7, 14 và 19.Bây giờ mã hóa:
31. 7 7 +3 mod 26 = 52 mod 26 = 0 7 14 + 3 mod 26 = 101 mod 26 =23 7 19 +3 mod 26 = 136 mod 26 = 6 Bây giờ 3 ký tự của bản mã là 0, 23 và 6 tƣơng ứng với xâu ký tự AXG. Giải mã: từ xâu ký tự của bản mã chuyển thành số nguyên trong bảng chữ cái tiếng Anh 26 chữ cái , ta đƣợc các số tƣơng ứng 0, 23, 6 Dk(0)=15 0- 19 mod 26 =7 Dk(23)=15 23- 19 mod 26 =14 Dk(6)=15 6- 19 mod 26 =19 Bây giờ 3 ký tự của bản rõ: h, o, t. 2.3.Hệ mã Vigenère Trong cả hai hệ mã dịch chuyển và mã tuyến tính một khi khóa đã đƣợc chọn mỗi ký tự sẽ đƣợc ánh xạ vào một ký tự duy nhất. Vì lý do đó, các hệ mật còn lại đƣợc gọi là hệ thay thế đơn biểu. Bây giờ tôi sẽ trình bày một hệ mật không phải là bộ chữ đơn, đó là hệ mã Vigenère nổi tiếng. Mật mã này lấy tên của Blaise de Vigenère sống vào thế kỷ XVI. Sử dụng phép tƣơng ứng A 0, B 1, .,Z 25 mô tả trên, ta có thể gắn cho mỗi khóa k với một chuỗi ký tự có độ dài m đƣợc gọi là từ khóa.Mật mã V sẽ mã hóa đồng thời m ký tự: mỗi phần tử của bản rõ tƣơng đƣơng với m ký tự Ví dụ Giả sử m=6 và từ khóa là CIPHER. Từ khóa này tƣơng ứng với dãy số k= 2,8,15,4,17 .Giả sử bản rõ là xâu thiscryptosystemisnotsecure Định nghĩa: m Cho m là một số dƣơng cố định nào đó. Cho P=C=K=(Z26) . Với khóa K= k1, k2 , ,km ta xác định: EK(x1, x2, . . . ,xm) = (x1+k1, x2+k2, . . . , xm+km) và DK(y1, y2, . . . ,ym) = (y1-k1, y2-k2, . . . , ym-km) Trong đó tất cả các phép toán đƣợc thực hiện trong Z26
32. Ta sẽ biến đổi các phần tử của bản rõ thành các thặng dƣ theo modulo 26, viết chúng thành các nhóm 6 rồi cộng với từ khóa theo modulo nhƣ sau 19 7 8 18 2 17 24 15 19 14 18 24 2 8 15 7 4 17 2 8 15 7 4 17 21 15 23 25 6 8 0 23 8 21 22 15 18 19 4 12 8 18 13 14 19 18 4 2 2 8 15 7 4 17 2 8 15 7 4 17 20 1 19 19 12 9 15 22 8 15 8 19 20 17 4 2 8 15 22 25 19 Bởi vậy, dãy ký tự tƣơng ứng của xâu bản mã sẽ là: V P X Z G I A X I V W P U B T T M J P W I Z I T W Z T Để giải mã ta có thể dùng cùng từ khóa nhƣng thay cho cộng, ta trừ nó theo modulo 26 Ta thấy rằng các từ khóa có thể với số độ dài m trong mật mã Vigenère là 26m, bởi vậy, thậm chí với các giá trị m khá nhỏ, phƣơng pháp tìm kiếm vét cạn cũng yêu cầu thời gian khá lớn. Ví dụ, nếu m=5 thì khôn gian khóa cũng có kích 7 thƣớc lớn hơn 1,1 10 . Lƣợng khóa này đã đủ lớn ngăn ngừa việc tìm khóa bằng tay Trong hệ mật Vigenère có từ khóa độ dài m, mỗi ký tự có thể đƣợc ánh xạ vào trong m ký tự có thể có giả sử rằng từ khóa chứa m ký tự phân biệt .Một hệ mật nhƣ vậy đƣợc gọi là hệ mật thay thê đa kiểu poly alphabetic . Nói chung, việc thám mã hệ thay thế đa kiểu sẽ khó khăn hơn so việc thám mã hệ đơn kiểu.
33. 2.4.Hệ mật Hill Trong phần này sẽ mô tả một hệ mật thay thế đa kiểu khác đƣợc gọi là mật mã Hill. Mật mã này do Lester S.Hill đƣa ra năm 1929. Giả sử m là một số m nguyên, đặt P = C = (Z26) . Ý tƣởng ở đây là lấy tổ hợp tuyến tính của m ký tự trong một phần tử của bản rõ để tạo ra m ký tự ở một phần tử của bản mã. Định nghĩa: Mật mã Hill là bộ 5(P, C, K, E, D). Cho m là một số nguyên dƣơng cố m định. Cho P = C = (Z26) và cho K={các ma trận khả nghịch cấp m m trên Z26} Với một khóa K K ta xác định EK(x) = xK -1 và DK(y) = yK tất cả các phép toán đƣợc thực hiện trong Z26 Ví dụ Giả sử khóa Từ các tính toán trên ta có Giả sử cần mã hóa bản rõ ―July‖. Ta có hai phần tử của bản rõ để mã hóa: 9,20 ứng với Ju và 11,24 ứng với ly . Ta tính nhƣ sau: Và Bởi vậy bản mã của july là DELW. Để giải mã Bob sẽ tính Và
34. Nhƣ vậy Bob đã nhận đƣợc bản đúng Cho tới lúc này ta đã chỉ ra rằng có thể thực hiện phép giải mã nếu K có một nghịch đảo. Trên thực tế, để phép giải mã là có thể thực hiện đƣợc, điều kiện cần là K phải có nghịch đảo. Điều này dễ dàng rút ra từ đại số tuyến tính sơ cấp . 2.5. Hệ mật Playfair Phép thay thế n-gram:thay vì thay thế đối với các kí tự, ngƣời ta có thể thay thế cho từng cụm 2 kí tự (gọi là digram) hoặc cho từng cụm 3 kí tự (gọi là trigram) và tổng quát cho từng cụm n kí tự (gọi là n-gram). Nếu bảng chữ cái Σ gồm 26 kí tự tiếng Anh thì phép thay thế n-gram sẽ có khoá là một hoán vị của 26n n-gram khác nhau. Trong trƣờng hợp digram thì hoán vị gồm 262 digram và có thể biểu diễn tốt nhất bằng một dãy 2 chiều 26 × 26 trong đó các hàng biểu diễn kí hiệu đầu tiên, các cột biểu diễn kí hiệu thứ hai, nội dung của các ô biểu diễn chuỗi thay thế. Ví dụ bảng 2 chiều sau biểu thị AA đƣợc thay bằng EG, AB đƣợc thay bằng RS, BA đƣợc thay bằng BO, BB đƣợc thay bằng SC, A B A EG RS B BO SC Đây là một sơ đồ dựa trên sự thay thế digram trong đó khoá là một hình vuông kích thƣớc 5 × 5 chứa một sự sắp xếp nào đó của 25 kí tự của bảng chữ cái (không tính kí tự J vì sự xuất hiện ít của nó và có thể thay nó bằng I). Giả sử chúng ta có ma trận khoá nhƣ sau B Y D G Z W S F U P L A R K X C O I V E Q N M H T
35. Sự thay thế sẽ đƣợc thực hiện nhƣ sau. Chẳng hạn nếu digram cần thay thế là AV thì trong hình chữ nhật có A, V là hai đỉnh chéo nhau thay A bằng đỉnh kề của nó theo đƣờng thẳng đứng chính là O và tƣơng tự thay V bằng đỉnh kề của nó theo đƣờng thẳng đứng chính là K. Tƣơng tự nếu digram cần thay thế là VN thì chuỗi thay thế là HO. Nếu các kí tự của digram nằm trên hàng ngang thì chuỗi thay thế là các kí tự bên phải của chúng. Chẳng hạn nếu digram là WU thì chuỗi thay thế là SP, nếu digram là FP thì chuỗi thay thế là UW, nếu digram là XR thì chuỗi thay thế là LK. Tƣơng tự nếu các kí tự của digram nằm trên hàng dọc thì chuỗi thay thế là các kí tự bên dƣới của chúng. Chẳng hạn nếu digram là SO thì chuỗi thay thế là AN, nếu digram là MR thì chuỗi thay thế là DI, nếu digram là GH thì chuỗi thay thế là UG. Trong trƣờng hợp digram là một cặp kí tự giống nhau chẳng hạn OO hoặc là một kí tự đƣợc đi kèm một khoảng trắng chẳng hạn B� thì có nhiều cách xử lý, cách đơn giản nhất là giữ nguyên không biến đổi digram này.
36. Chương 3. Một số công cụ hỗ trợ cho thuyết mật mã 3.1.Lý thuyết số 3.1.1.Kiến thức đồng dư thức a. Định nghĩa: Cho là số nguyên dƣơng. Hai số nguyên và đƣợc gọi là đồng dƣ với nhau theo module m nếu hiệu a Ký hiệu a  b mod m đƣợc gọi là một đồng dƣ thức. Nếu không chia hết cho , ta viết Ví dụ 3  -1 (mod 4) 5  17 (mod 6) 18  0 (mod 6) Điều kiện a  0 mod m nghĩa là a b. Tính chất và các hệ quả Tính chất 1: Với mọi số nguyên , ta có: a  a (mod m) Tính chất 2: a  b (mod m) b  a (mod m) Tính chất 3 a  b (mod m), b  c (mod m) a  c (mod m) Chứng minh: a  b (mod m) m | (a - b) b c(mod m) m | (b- c vì a – c = (a – b) + (b – c ) m | (a - c Tính chất 4 Chứng minh:
37. Tính chất 5 Chứng minh: Theo tính chất 4 ta có: Nhân từng vế hai ĐT ta có: Nhận xét: 1, Nếu a  1(mod 2) và b  1(mod 2) thì a + b  2(mod 2), và 2  0 (mod 2) suy ra: a + b  0(mod 2), còn a.b  1(mod 2) Điều này có nghĩa : Tổng của hai số lẻ là một số chẵn; Tích của hai số lẻ là một số lẻ 2,Nếu a  3(mod 7) a2  9 (mod 7)  2(mod 7) Có nghĩa: Nếu một số chia cho 7 dƣ 3 thì bình phƣơng số đó chia 7 dƣ 2. Các hệ quả của tính chất 4 và 5: 3. , với Chú ý: 1_Chia hai vế cho một đẳng thức, nói chung là không đƣợc. nhƣng 2 nhƣng ab có thể đồng dƣ với 0 theo module m. Chẳng hạn : nhƣng 2.5=10  0(mod 10)
38. 3.1.2.Một số định lý sử dụng trong thuật mã hóa công khai a.Thuật giải Euclid- Tìm UCLN của hai số nguyên Giải thuật Euclid hay thuật toán Euclid, là một giải thuật giúp tính ƣớc số chung lớn nhất ƢSCLN của hai số một cách hiệu quả. Giải thuật này đã đƣợc biết đến từ khoảng năm 300 trƣớc Công Nguyên. Nhà toán học Hy Lạp cổ Euclid đã viết giải thuật này trong cuốn sách toán nổi tiếng Elements. Giả sử a = bq + r, với a, b, q, r là các số nguyên, ta có: Giải thuật Input: hai số nguyên không âm a và b, b>0 Output: UCLN của a, b. (1) While b ≠ 0 do r= a mod b, a= b, b=r (2) Return (a) b.Giải thuật Euclid mở rộng Giải thuật Euclid mở rộng sử dụng để giải phƣơng trình vô định nguyên còn đƣợc gọi là phƣơng trình Đi-ô-phăng) a*x+b*y=c, trong đó a, b,c là các hệ số nguyên, x, y là các ẩn nhận giá trị nguyên. Điều kiện cần và đủ để phƣơng trình này có nghiệm nguyên là UCLN(a,b) là ƣớc của c. Khẳng định này dựa trên một mệnh đề sau: Trong số học đã biết rằng nếu d=UCLN(a,b) thì tồn tại các số nguyên x, y sao cho a*x+b*y = d Giải thuật Input: hai số nguyên không âm a và b , a>b Output: d= UCLN a,b và các số nguyên x và y thỏa mãn ax + by = d (1) Nếu b = 0 thì đặt d =a, y = 0, và return d,x,y (2) Khai báo 5 biến trung gian x1, x2, y1, y2 và q (3) Đặt x2 = 1, x1 = 0, y2 = 0, y1 = 1
39. (4) While b > 0 do (4.1) q = [a/b], r = a – qb, x = x2 – qx1, y = y2 – qy1 (4.2) a = b, b = r, x2 = x1 , x1 = x, y2 = y1, y1 = y 5 Đặt d = a, x = x2, y = y2 và return (d,x,y). Đánh giá độ phức tạp: Thuật toán Euclid mở rộng có độ phức tạp về thời gian là O((lg n)2). Ví dụ: Xét ví dụ với a=4864 và b=3458. q r x y a b x2 x1 y2 y1 — — — — 4864 3458 1 0 0 1 1 1406 1 -1 3458 1406 0 1 1 -1 2 646 -2 3 1406 646 1 -2 -1 3 2 114 5 -7 646 114 -2 5 3 -7 5 76 -27 38 114 76 5 -27 -7 38 1 38 32 -45 76 38 -27 32 38 -45 2 0 -91 128 38 0 32 -91 45 128 Ứng dụng thuật toán Euclid mở rộng để tìm phẩn tử nghịch đảo Thuật toán Euclid mở rộng đƣợc sử dụng rất thƣờng xuyên trong mật mã với khóa công khai để tìm phần tử nghịch đảo. Xét một trƣờng hợp riêng khi vận dụng thuật toán Euclid mở rộng: Cho hai số nguyên dƣơng nguyên tố cùng nhau a, n: n>a, a,n =1. Cần tìm số nguyên dƣơng b nhỏ nhất sao cho ab ≡ 1 mod n . Số b nhƣ thế đƣợc gọi là "nghịch đảo" của a theo module n và ngƣợc lại, a là "nghịch đảo" của b theo module n). Áp dụng thuật toán Euclid mở rộng cho cặp số (n,a) ta tìm đƣợc bộ 3 số d,x,y thỏa mãn d=(n,a) và nx+ay=d. Bởi vì a và n nguyên tố cùng nhau nên d=1 và nx+ay=1. Vì nx luôn chia hết cho n nên từ đẳng thức cuối cùng ta suy ra đƣợc ay ≡ 1 mod n . Đối chiếu với yêu cầu của bài toán, ta có b = y + zn. Trong đó z là số nguyên nhỏ nhất thõa mãn b > 0. Dạng rút gọn của thuật toán Euclid mở rộng. Bởi vì bài tóan tìm "phần tử nghịch đảo" là trƣờng hợp riêng của thuật toán Euclid mở rộng, lại đƣợc dùng rất thƣờng xuyên trong mật mã với khóa công khai nên
40. ngƣời ta xây dựng thuật toán đơn giản hơn để giải bài toán này. Thuật toán đƣợc thể hiện ở bảng dƣới đây: I ui vi qi 1 0 n 2 1 a [n/a] 3 u1-q2.u2 v1-q2.v2 [v2/v3] K uk-2-qk-1.uk-1 vk-2-qk-1.vk-1 [vk-1/vk] ? y 1 I ui vi qi 1 0 23 2 1 5 4 3 -4 3 1 4 5 2 1 5 -9 1 Bƣớc 1: 1. u := 0; 2. v := n; ví dụ: n=23 3. Chuyển đến bƣớc 2 Bƣớc 2: 1. u := 1; 2. v := a; ví dụ: a=5 3. Nếu v=1 thì chuyển đến bƣớc 5. 4. q = n/a 5. Chuyển đến bƣớc 3 Bƣớc 3:
41. 1. uk := uk-2-qk-1.uk-1; 2. vk := vk-2-qk-1.vk-1; 3. Nếu vk=1 thì chuyển đến bƣớc 5. 4. qk := [vk-1/vk]; 5. Chuyển đến bƣớc 4 Bƣớc 4: Trở lại bƣớc 3. Bƣớc 5: Đến đây ta thu đƣợc giá trị v = y. Số b cần tìm đƣợc xác định bởi b = y + zn. Trong đó, z là số nguyên nhỏ nhất thỏa mãn b > 0. Ở ví dụ trên đây, đối với n=23 và a=5 ta tìm đƣợc y = -9 nên b = 14 với z=1 . c.Định lý phần dƣ Trung Hoa Định lý phần dƣ Trung Hoa, hay bài toán Hàn Tín điểm binh, là một định lý nói về nghiệm của hệ phƣơng trình đồng dƣ bậc nhất. Nội dung Cho tập các số nguyên tố cùng nhau từng đôi một :m1, m2, , mk. Với mỗi bộ số nguyên bất kỳ a1, a2, , ak. Hệ phƣơng trình đồng dƣ: Luôn có nghiệm duy nhất theo mođun M = m1.m2 mk là: trong đó M1 = M / m1, M2 = M / m2, , Mk = M / mk − 1 − 1 − 1 y1 = (M1) (mod m1), y2 = (M2) (mod m2), , yk = (Mk) (mod mk) d.Thuật giải Rabin – Miller (1980)
42. Cho n ≥ 3 lẻ, thuật toán sau đây xác định rằng n là một hợp số hoặc in ra thông bao sn là số nguyên tố (1) Write n – 1 = 2k m, where m is old (2) Chose a random integer, 1 ≤ a ≤ n – 1 (3) Compute b = am mod n (4) If b=1 (mod n) then anwer ―n is prime‖ and quit (5) For i =0 to k – 1 do If b = -1 mod n then anwer ―n is prime‖ and quit else b = b2 (mod n) (6) Anwser ―n is composite‖ f. Thuật giải tính xp mod m Cho x Zm và một số nguyên p N* có biểu diễn nhị phân i p p = pi2 (i = 0, 1). Việc tính giá trị y = x mod m đƣợc gọi là phép lũy thừa mod i Input: x Zm, p = pi2 (i = 0, 1) Output: y = xp mod m (1) y = 1 (2) for i = 1 downto 0 do y = y2 mod m if pi = 1 then y = (y*x) mod m (3) return y g. Định lý Ferma
43. Nếu p là một số nguyên tố còn a là một số nguyên thì ap  a(mod p). Nếu p không chia hết cho a tức là a mod p ≠ 0 thì ap-1  1 mod p định lý Ferma nhỏ Dễ nhận thấy rằng định lý Fermat nhỏ là trƣờng hợp riêng của định lý Euler khi n là số nguyên tố. h. Định lý Euler Định nghĩa hàm Euler: Cho n là một số nguyên dƣơng. Hàm Euler của n đƣợc ký hiệu là φ(n) và đƣợc xác định bởi công suất của tập hợp M các số nguyên dƣơng nhỏ hơn n và nguyên tố cùng nhau với n. Giải thích: Cho trƣớc số nguyên dƣơng n Xác định tập hợp M dối với số n đã cho : số x thuộc tập hợp M khi và chỉ khi thõa mãn các điều kiện sau: 1. 2. 0 < x < n 3. (x,n) = 1 Hàm Euler của n có giá trị bằng số phần tử của tập hợp M: φ(n) = #M Quy tắc tính giá trị của hàm Euler: 1. φ p = p – 1, nếu p là số nguyên tố; 2. φ ∏pi = ∏ pi – 1 , trong đó pi là các số nguyên tố khác nhau; k k 3. φ ∏pi i = ∏ pi∙ pi – 1) i , trong đó pi là các số nguyên tố khác nhau; 4. φ m∙n = φ m ∙φ n , nếu m,n =1. Định lý Euler:Cho a và n là 2 số nguyên dƣơng, nguyên tố cùng nhau: a,n)=1. Định lý Euler khẳng định: aφ n ≡ 1 mod n , trong đó φ(n) là hàm Euler của n.
44. 3.2.Lý thuyết độ phức tạp Một chƣơng trình máy tính thƣờng đƣợc cài đặt dựa trên một thuật toán đúng để giải quyết bài toán hay vấn đề. Tuy nhiên, ngay cả khi thuật toán đúng, chƣơng trình vẫn có thể không sử dụng đƣợc đối với một dữ liệu đầu vào nào đó vì thời gian để cho ra kết quả là quá lâu hoặc sử dụng quá nhiều bộ nhớ vƣợt quá khả năng đáp ứng của máy tính . Khi tiến hành phân tích thuật toán nghĩa là chúng ta tìm ra một đánh giá về thời gian và "không gian" cần thiết để thực hiện thuật toán. Không gian ở đây đƣợc hiểu là các yêu cầu về bộ nhớ, thiết bị lƣu trữ, của máy tính để thuật toán có thể làm việc. Việc xem xét về không gian của thuật toán phụ thuộc phần lớn vào cách tổ chức dữ liệu của thuật toán. Trong phần này, khi nói đến độ phức tạp của thuật toán, chúng ta chỉ đề cập đến những đánh giá về mặt thời gian mà thôi. Phân tích thuật toán là một công việc rất khó khăn, đòi hỏi phải có những hiểu biết sâu sắc về thuật toán và nhiều kiến thức toán học khác. Ðây là công việc mà không phải bất cứ ngƣời nào cũng làm đƣợc. Rất may mắn là các nhà toán học đã phân tích cho chúng ta độ phức tạp của hầu hết các thuật toán cơ sở sắp xếp, tìm kiếm, các thuật toán số học, . Chính vì vậy, nhiệm vụ còn lại của chúng ta là hiểu đƣợc các khái niệm liên quan đến độ phức tạp của thuật toán. Ðánh giá về thời gian của thuật toán không phải là xác định thời gian tuyệt đối chạy thuật toán mất bao nhiêu giây, bao nhiêu phút, để thực hiện thuật toán mà là xác định mối liên quan giữa dữ liệu đầu vào input của thuật toán và chi phí số thao tác, số phép tính cộng,trừ, nhân, chia, rút căn, để thực hiện thuật toán. Sở dĩ ngƣời ta không quan tâm đến thời gian tuyệt đối của thuật toán vì yếu tố này phụ thuộc vào tốc độ của máy tính, mà các máy tính khác nhau thì có tốc độ rất khác nhau. Một cách tổng quát, chi phí thực hiện thuật toán là một hàm số phụ thuộc vào dữ liệu đầu vào : T = f(input)
45. Tuy vậy, khi phân tích thuật toán, ngƣời ta thƣờng chỉ chú ý đến mối liên quan giữa độ lớn của dữ liệu đầu vào và chi phí. Trong các thuật toán, độ lớn của dữ liệu đầu vào thƣờng đƣợc thể hiện bằng một con số nguyên n. Chẳng hạn : sắp xếp n con số nguyên, tìm con số lớn nhất trong n số, tính điểm trung bình của n học sinh, Lúc này, ngƣời ta thể hiện chi phí thực hiện thuật toán bằng một hàm số phụ thuộc vào n : T = f(n) Việc xây dựng một hàm T tổng quát nhƣ trên trong mọi trƣờng hợp của thuật toán là một việc rất khó khăn, nhiều lúc không thể thực hiện đƣợc. Chính vì vậy mà ngƣời ta chỉ xây dựng hàm T cho một số trƣờng hợp đáng chú ý nhất của thuật toán, thƣờng là trƣờng hợp tốt nhất và xấu nhất. Để đánh giá trƣờng hợp tốt nhất và xấu nhất ngƣời ta dựa vào định nghĩa sau: Cho hai hàm f và g có miền xác định trong tập số tự nhiên . Ta viết f n = O g n và nói f n có cấp cao nhất là g n khi tồn tại hằng số C và k sao cho | f n | ≤ C.g n với mọi n > k Tuy chi phí của thuật toán trong trƣờng hợp tốt nhất và xấu nhất có thể nói lên nhiều điều nhƣng vẫn chƣa đƣa ra đƣợc một hình dung tốt nhất về độ phức tạp của thuật toán. Ðể có thể hình dung chính xác về độ phức tạp của thuật toán, ta xét đến một yếu tố khác là độ tăng của chi phí khi độ lớn n của dữ liệu đầu vào tăng. Một cách tổng quát, nếu hàm chi phí của thuật toán xét trong một trƣờng hợp nào đó bị chặn bởi O f n thì ta nói rằng thuật toán có độ phức tạp là O f n trong trƣờng hợp đó. Nhƣ vậy, thuật toán tìm số lớn nhất có độ phức tạp trong trƣờng hợp tốt nhất và xấu nhất đều là O n . Ngƣời ta gọi các thuật toán có độ phức tạp O n là các thuật toán có độ phức tạp tuyến tính.
46. Sau đây là một số "thƣớc đo" độ phức tạp của thuật toán đƣợc sử dụng rộng rãi. Các độ phức tạp đƣợc sắp xếp theo thứ tự tăng dần. Nghĩa là một bài toán có độ phức tạp O nk sẽ phức tạp hơn bài toán có độ phức tạp O n hoặc O logn .
47. Chương 4. Hệ mật mã công khai 4.1.Giới thiệu mật mã với khóa công khai 4.1.1.Lịch sử Mật mã hóa khóa công khai là một dạng mật mã hóa cho phép ngƣời sử dụng trao đổi các thông tin mật mà không cần phải trao đổi các khóa chung bí mật trƣớc đó. Điều này đƣợc thực hiện bằng cách sử dụng một cặp khóa có quan hệ toán học với nhau là khóa công khai và khóa cá nhân hay khóa bí mật . Thuật ngữ mật mã hóa khóa bất đối xứng thƣờng đƣợc dùng đồng nghĩa với mật mã hóa khóa công khai mặc dù hai khái niệm không hoàn toàn tƣơng đƣơng. Có những thuật toán mật mã khóa bất đối xứng không có tính chất khóa công khai và bí mật nhƣ đề cập ở trên mà cả hai khóa cho mã hóa và giải mã đều cần phải giữ bí mật. Trong mật mã hóa khóa công khai, khóa cá nhân phải đƣợc giữ bí mật trong khi khóa công khai đƣợc phổ biến công khai. Trong 2 khóa, một dùng để mã hóa và khóa còn lại dùng để giải mã. Điều quan trọng đối với hệ thống là không thể tìm ra khóa bí mật nếu chỉ biết khóa công khai. Hệ thống mật mã hóa khóa công khai có thể sử dụng với các mục đích: Mã hóa: giữ bí mật thông tin và chỉ có ngƣời có khóa bí mật mới giải mã đƣợc. Tạo chữ ký số: cho phép kiểm tra một văn bản có phải đã đƣợc tạo với một khóa bí mật nào đó hay không. Thỏa thuận khóa: cho phép thiết lập khóa dùng để trao đổi thông tin mật giữa 2 bên. Thông thƣờng, các kỹ thuật mật mã hóa khóa công khai đòi hỏi khối lƣợng tính toán nhiều hơn các kỹ thuật mã hóa khóa đối xứng nhƣng những lợi điểm mà chúng mang lại khiến cho chúng đƣợc áp dụng trong nhiều ứng dụng.
48. Trong hầu hết lịch sử mật mã học, khóa dùng trong các quá trình mã hóa và giải mã phải đƣợc giữ bí mật và cần đƣợc trao đổi bằng một phƣơng pháp an toàn khác không dùng mật mã nhƣ gặp nhau trực tiếp hay thông qua một ngƣời đƣa thƣ tin cậy. Vì vậy quá trình phân phối khóa trong thực tế gặp rất nhiều khó khăn, đặc biệt là khi số lƣợng ngƣời sử dụng rất lớn. Mật mã hóa khóa công khai đã giải quyết đƣợc vấn đề này vì nó cho phép ngƣời dùng gửi thông tin mật trên đƣờng truyền không an toàn mà không cần thỏa thuận khóa từ trƣớc. Năm 1874, William Stanley Jevons xuất bản một cuốn sách mô tả mối quan hệ giữa các hàm một chiều với mật mã học đồng thời đi sâu vào bài toán phân tích ra thừa số nguyên tố sử dụng trong thuật toán RSA). Tháng 7 năm 1996, một nhà nghiên cứu đã bình luận về cuốn sách trên nhƣ sau: Trong cuốn The Principles of Science: A Treatise on Logic and Scientific Method đƣợc xuất bản năm 1890, William S. Jevons đã phát hiện nhiều phép toán rất dễ thực hiện theo một chiều nhƣng rất khó theo chiều ngƣợc lại. Một ví dụ đã chứng tỏ mã hóa rất dễ dàng trong khi giải mã thì không. Vẫn trong phần nói trên ở chƣơng 7 Giới thiệu về phép tính ngƣợc tác giả đề cập đến nguyên lý: ta có thể dễ dàng nhân các số tự nhiên nhƣng phân tích kết quả ra thừa số nguyên tố thì không hề đơn giản. Đây chính là nguyên tắc cơ bản của thuật toán mật mã hóa khóa công khai RSA mặc dù tác giả không phải là ngƣời phát minh ra mật mã hóa khóa công khai. Thuật toán mật mã hóa khóa công khai đƣợc thiết kế đầu tiên bởi James H. Ellis, Clifford Cocks, và Malcolm Williamson tại GCHQ (Anh vào đầu thập kỷ 1970. Thuật toán sau này đƣợc phát triển và biết đến dƣới tên Diffie-Hellman, và là một trƣờng hợp đặc biệt của RSA. Tuy nhiên những thông tin này chỉ đƣợc tiết lộ vào năm 1997. Năm 1976, Whitfield Diffie và Martin Hellman công bố một hệ thống mật mã hóa khóa bất đối xứng trong đó nêu ra phƣơng pháp trao đổi khóa công khai. Công trình này chịu sự ảnh hƣởng từ xuất bản trƣớc đó của Ralph Merkle về phân phối khóa công khai. Trao đổi khóa Diffie-Hellman là phƣơng pháp có thể áp
49. dụng trên thực tế đầu tiên để phân phối khóa bí mật thông qua một kênh thông tin không an toàn. Kỹ thuật thỏa thuận khóa của Merkle có tên là hệ thống câu đố Merkle. Thuật toán đầu tiên cũng đƣợc Rivest, Shamir và Adleman tìm ra vào năm 1977 tại MIT. Công trình này đƣợc công bố vào năm 1978 và thuật toán đƣợc đặt tên là RSA. RSA sử dụng phép toán tính hàm mũ môđun môđun đƣợc tính bằng tích số của 2 số nguyên tố lớn để mã hóa và giải mã cũng nhƣ tạo [chữ ký số]. An toàn của thuật toán đƣợc đảm bảo với điều kiện là không tồn tại kỹ thuật hiệu quả để phân tích một số rất lớn thành thừa số nguyên tố. Kể từ thập kỷ 1970, đã có rất nhiều thuật toán mã hóa, tạo chữ ký số, thỏa thuận khóa đƣợc phát triển. Các thuật toán nhƣ ElGamal mật mã do Netscape phát triển hay DSA do NSA và NIST cũng dựa trên các bài toán lôgarit rời rạc tƣơng tự nhƣ RSA. Vào giữa thập kỷ 1980, Neal Koblitz bắt đầu cho một dòng thuật toán mới: mật mã đƣờng cong elliptic và cũng tạo ra nhiều thuật toán tƣơng tự. Mặc dù cơ sở toán học của dòng thuật toán này phức tạp hơn nhƣng lại giúp làm giảm khối lƣợng tính toán đặc biệt khi khóa có độ dài lớn. 4.1.2.Lý thuyết mật mã công khai Khái niệm về mật mã khóa công khai đã tạo ra sự cố gắng để giải quyết hai vấn đề khó khăn nhất trong mật mã khóa quy ƣớc, đó là sự phân bố khóa và chữ ký số: - Trong mã quy ƣớc sự phân bố khóa yêu cầu hoặc là hai ngƣời truyền thông cùng tham gia một khóa mà bằng cách nào đó đã đƣợc phân bố tới họ hoặc sử dụng chung một trung tâm phân bố khóa. - Nếu việc sử dụng mật mã đã trở nên phổ biến, không chỉ trong quân đội mà còn trong thƣơng mại và những mục đích cá nhân thì những đoạn tin và tài liệu điện tử sẽ cần những chữ ký tƣơng đƣơng đã sử dụng trong các tài liệu giấy. Tức là, một phƣơng pháp có thể đƣợc nghĩ ra có quy định làm hài lòng tất cả những ngƣời tham gia khi mà một đoạn tin số đƣợc gửi bởi một cá nhân đặc biệt hay không
50. Trong sơ đồ mã hóa quy ƣớc, các khóa đƣợc dùng cho mã hóa và giải mã một đoạn tin là giống nhau. Đây là mọt điều kiện không cần thiết, nó có thể phát triển giải thuật mã hóa dựa trên một khóa cho mã hóa và một khóa khác cho giải mã Các bƣớc cần thiết trong quá trình mã hóa công khai - Mỗi hệ thống cuối trong mạng tạo ra một cặp khóa để dùng cho mã hóa và giải mã đoạn tin mà nó sẽ nhận - Mỗi hệ thống công bố rộng rãi khóa mã hóa bằng cách đặt khóa vào một thanh ghi hay một file công khai, khóa còn lại đƣợc giữ riêng - Nếu A muốn gửi một đoạn tin tới B thì A mã hóa đoạn tin bằng khóa công khai của B - Khi B nhận đoạn tin mã hóa, nó có thể giải ãm bằng khóa bí mật của mình. Không một ngƣời nào khác có thể giải mã đoan tin này bởi vì chỉ có mình B biết khóa bí mật đó thôi . Việc các tiếp cận này, tất cả những ngƣời tham gia có thể truy xuất khóa công khai. Khóa bí mật đƣợc tạo bởi từng cá nhân, vì vậy không bao giờ đƣợc phân bố. Ở bất kỳ thời điểm nào, hệ thống cũng có thể chuyển đổi cặp khóa để đảm bảo tính bí mật. Bảng sau tóm tắt một số khía cạnh quan trọng vè mã hóa quy ƣớc và mã hóa công khai : để phân biệt đƣợc hai loại chúng ta tổng quát hóa liên hệ khóa sử dụng trong mã hóa quy ƣớc là khóa bí mật, hai khóa sử dụng trong mã hóa công khai là khóa công khai và khóa bí mật. Mã hóa quy ước Mã hóa công khai * Yêu cầu * Yêu cầu - Thuật giải tƣơng tự cho mã hóa và - Một thuật giải cho mã hóa và một giải mã. thuật giải cho giải mã
51. - Ngƣời gửi và ngƣời nhận phải tham - Ngƣời gửi và ngƣời nhận, mỗi gia cùng thuật giải và cùng khóa ngƣời phải có cặp khóa riêng của mình * Tính bảo mật * Tính bảo mật - Khóa phải đƣợc bí mật - Một trong hai khóa phải đƣợc giữ - Không thể hay ít nhất không có tính bí mật thực tế để giải mã đoạn tin nếu thông tin khác có sẵn - Không thể hay ít nhất không có tính thực tế để giải mã đoạn tín nếu thông - Kiến thức về thuật giải cộng với tin khác không có sẵn các mẫu về mật mã không đủ để xác định khóa - Kiến thức về thuật giải cộng với một trong các khóa, cộng với các mẫu về mật mã không đủ để xác định khóa 4.1.3.Những yếu điểm, hạn chế của mật mã với khóa công khai Tồn tại khả năng một ngƣời nào đó có thể tìm ra đƣợc khóa bí mật. Không giống với hệ thống mật mã sử dụng một lần (one-time pad hoặc tƣơng đƣơng, chƣa có thuật toán mã hóa khóa bất đối xứng nào đƣợc chứng minh là an toàn trƣớc các tấn công dựa trên bản chất toán học của thuật toán. Khả năng một mối quan hệ nào đó giữa 2 khóa hay điểm yếu của thuật toán dẫn tới cho phép giải mã không cần tới khóa hay chỉ cần khóa mã hóa vẫn chƣa đƣợc loại trừ. An toàn của các thuật toán này đều dựa trên các ƣớc lƣợng về khối lƣợng tính toán để giải các bài toán gắn với chúng. Các ƣớc lƣợng này lại luôn thay đổi tùy thuộc khả năng của máy tính và các phát hiện toán học mới. Mặc dù vậy, độ an toàn của các thuật toán mật mã hóa khóa công khai cũng tƣơng đối đảm bảo. Nếu thời gian để phá một mã bằng phƣơng pháp duyệt toàn bộ) đƣợc ƣớc lƣợng là 1000 năm thì thuật toán này hoàn toàn có thể dùng để mã hóa
52. các thông tin về thẻ tín dụng - Rõ ràng là thời gian phá mã lớn hơn nhiều lần thời gian tồn tại của thẻ vài năm . Nhiều điểm yếu của một số thuật toán mật mã hóa khóa bất đối xứng đã đƣợc tìm ra trong quá khứ. Thuật toán đóng gói ba lô là một ví dụ. Nó chỉ đƣợc xem là không an toàn khi một dạng tấn công không lƣờng trƣớc bị phát hiện. Gần đây, một số dạng tấn công đã đơn giản hóa việc tìm khóa giải mã dựa trên việc đo đạc chính xác thời gian mà một hệ thống phần cứng thực hiện mã hóa. Vì vậy, việc sử dụng mã hóa khóa bất đối xứng không thể đảm bảo an toàn tuyệt đối. Đây là một lĩnh vực đang đƣợc tích cực nghiên cứu để tìm ra những dạng tấn công mới. Một điểm yếu tiềm tàng trong việc sử dụng khóa bất đối xứng là khả năng bị tấn công dạng kẻ tấn công đứng giữa man in the middle attack : kẻ tấn công lợi dụng việc phân phối khóa công khai để thay đổi khóa công khai. Sau khi đã giả mạo đƣợc khóa công khai, kẻ tấn công đứng ở giữa 2 bên để nhận các gói tin, giải mã rồi lại mã hóa với khóa đúng và gửi đến nơi nhận để tránh bị phát hiện. Dạng tấn công kiểu này có thể phòng ngừa bằng các phƣơng pháp trao đổi khóa an toàn nhằm đảm bảo nhận thực ngƣời gửi và toàn v n thông tin. Một điều cần lƣu ý là khi các chính phủ quan tâm đến dạng tấn công này: họ có thể thuyết phục hay bắt buộc nhà cung cấp chứng thực số xác nhận một khóa giả mạo và có thể đọc các thông tin mã hóa. 4.1.4.Ứng dụng của mật mã a.Bảo mật Ứng dụng rõ ràng nhất của mật mã hóa khóa công khai là bảo mật: một văn bản đƣợc mã hóa bằng khóa công khai của một ngƣời sử dụng thì chỉ có thể giải mã với khóa bí mật của ngƣời đó. Phần mềm PGP miễn phí chỉ đƣợc sử dụng cho ngƣời dùng cá nhân với mục đích phi thƣơng mại, có thể tải về tại địa chỉ :
53. b.Chứng thực Các thuật toán tạo chữ ký số khóa công khai có thể dùng để nhận thực. Một ngƣời sử dụng có thể mã hóa văn bản với khóa bí mật của mình. Nếu một ngƣời khác có thể giải mã với khóa công khai của ngƣời gửi thì có thể tin rằng văn bản thực sự xuất phát từ ngƣời gắn với khóa công khai đó. Dùng chữ ký số cho email và mã hóa email khi gửi đi thông qua nhà cung cấp chứng chỉ số làm trọng tài điều khiển Nhà chứng chỉ số của nhà cung cấp Thawte www.thawte.com) cho phép bạn có thể đăng ký cho mình một tài khoản Personal Email Certificate haonf toàn miễn phí tại đây để thực hiện giao dịch khi gởi và nhận mail ( c.Ứng dụng trong thƣơng mại điện tử Nhiều đơn vị, tổ chức ở Việt Nam đã đang xây dựng mạng máy tính có quy mô lớn phục vụ cho công việc kinh doanh của mình: mạng chứng khoán, mạng ngân hàng, mạng bán vé tàu xe, kê khai và nộp thuế qua mạng . Công ty phần mềm và Truyền thông VASC đã chính thức ký kết hợp đồng ―ứng dụng chứng chỉ số trong giao dịch ngân hàng điện tử‖ với ngân hàng cổ phần thƣơng mại Á Châu ACB từ ngày 30/9/2003, cho phép khách hàng ACB sẽ giao dịch trực tuyến trên mạng với chữ ký điện tử do VASC cấp. Mạng giao dịch chứng khoán VCBS : mở tài khoản ngân hàng cho phép giao dịch trực tiếp qua sàn, báo giá cổ phiếu, cho phép đặt lệnh mua bán cổ phần chỉ bằng thao tác click chuột. Mạng ngân hàng VCB, EAB cho phép xem số dƣ, chuyển khoản cho tài khoản khác cùng hệ thống từ 20-500 triệu đồng mỗi ngày, bản kê chi tiết gaio dịch của tài khoản trên Internet.
54. Hệ thống bán vé qua mạng của ngành hàng không ( , đƣờng sắt đã triển khai 1/2007, mua bán trực tuyến Chi cục thuế thành phố Hồ Chí Minh đang thử nghiệm cho phép doanh nghiệp đăng ký tự in hóa đơn theo mẫu, tự kê khai báo cáo thuế, khấu trừ thuế qua mạng Nếu nhƣ có đƣợc một cơ chế bảo mật tốt, đảm bảo xác thực rõ ràng giữa các bên tham gia vào hệ thống thì chắc chắn rằng những vấn đề liên quan đến mạng máy tính nêu trên chỉ còn là vấn đề thời gian. 4.2.Hệ mật RSA Trong mật mã học, RSA là một thuật toán mật mã hóa khóa công khai. Đây là thuật toán đầu tiên phù hợp với việc tạo ra chữ ký điện tử đồng thời với việc mã hóa. Nó đánh dấu một sự tiến bộ vƣợt bậc của lĩnh vực mật mã học trong việc sử dụng khóa công cộng. RSA đang đƣợc sử dụng phổ biến trong thƣơng mại điện tử và đƣợc cho là đảm bảo an toàn với điều kiện độ dài khóa đủ lớn. 4.2.1.Lịch sử Thuật toán đƣợc Ron Rivest, Adi Shamir và Len Adleman mô tả lần đầu tiên vào năm 1977 tại Học viện Công nghệ Massachusetts MIT . Tên của thuật toán lấy từ 3 chữ cái đầu của tên 3 tác giả. Trƣớc đó, vào năm 1973, Clifford Cocks, một nhà toán học ngƣời Anh làm việc tại GCHQ, đã mô tả một thuật toán tƣơng tự. Với khả năng tính toán tại thời điểm đó thì thuật toán này không khả thi và chƣa bao giờ đƣợc thực nghiệm. Tuy nhiên, phát minh này chỉ đƣợc công bố vào năm 1997 vì đƣợc xếp vào loại tuyệt mật. Thuật toán RSA đƣợc MIT đăng ký bằng sáng chế tại Hoa Kỳ vào năm 1983 Số đăng ký 4,405,829 . Bằng sáng chế này hết hạn vào ngày 21 tháng 9 năm 2000. Tuy nhiên, do thuật toán đã đƣợc công bố trƣớc khi có đăng ký bảo hộ nên sự bảo hộ hầu nhƣ không có giá trị bên ngoài Hoa Kỳ. Ngoài ra, nếu nhƣ công trình của
55. Clifford Cocks đã đƣợc công bố trƣớc đó thì bằng sáng chế RSA đã không thể đƣợc đăng ký. 4.2.2.Mô tả thuật toán Thuật toán RSA có hai khóa: khóa công khai hay khóa công cộng và khóa bí mật (hay khóa cá nhân). Mỗi khóa là những số cố định sử dụng trong quá trình mã hóa và giải mã. Khóa công khai đƣợc công bố rộng rãi cho mọi ngƣời và đƣợc dùng để mã hóa. Những thông tin đƣợc mã hóa bằng khóa công khai chỉ có thể đƣợc giải mã bằng khóa bí mật tƣơng ứng. Nói cách khác, mọi ngƣời đều có thể mã hóa nhƣng chỉ có ngƣời biết khóa cá nhân bí mật mới có thể giải mã đƣợc. Ta có thể mô phỏng trực quan một hệ mật mã khoá công khai nhƣ sau : Bob muốn gửi cho Alice một thông tin mật mà Bob muốn duy nhất Alice có thể đọc đƣợc. Để làm đƣợc điều này, Alice gửi cho Bob một chiếc hộp có khóa đã mở sẵn và giữ lại chìa khóa. Bob nhận chiếc hộp, cho vào đó một tờ giấy viết thƣ bình thƣờng và khóa lại nhƣ loại khoá thông thƣờng chỉ cần sập chốt lại, sau khi sập chốt khóa ngay cả Bob cũng không thể mở lại đƣợc-không đọc lại hay sửa thông tin trong thƣ đƣợc nữa . Sau đó Bob gửi chiếc hộp lại cho Alice. Alice mở hộp với chìa khóa của mình và đọc thông tin trong thƣ. Trong ví dụ này, chiếc hộp với khóa mở đóng vai trò khóa công khai, chiếc chìa khóa chính là khóa bí mật. a. Tạo khóa Giả sử Alice và Bob cần trao đổi thông tin bí mật thông qua một kênh không an toàn ví dụ nhƣ Internet . Với thuật toán RSA, Alice đầu tiên cần tạo ra cho mình cặp khóa gồm khóa công khai và khóa bí mật theo các bƣớc sau: 1. Chọn 2 số nguyên tố lớn p và q với p≠q, lựa chọn ngẫu nhiên và độc lập. 2. Tính: n= pq 3. Tính: giá trị hàm số Ơle (n)= (p-1)(q-1). 4. Chọn một số tự nhiên e sao cho 1< e< (n) và là số nguyên tố cùng nhau với (n) .
56. 5. Tính: d sao cho de 1 (mod (n). Một số lƣu ý: Các số nguyên tố thƣờng đƣợc chọn bằng phƣơng pháp thử xác suất. Các bƣớc 4 và 5 có thể đƣợc thực hiện bằng giải thuật Euclid mở rộng (xem thêm: số học môđun ). Bƣớc 5 có thể viết cách khác: Tìm số tự nhiên sao cho cũng là số tự nhiên. Khi đó sử dụng giá trị . Từ bƣớc 3, PKCS#1 v2.1 sử dụng thay cho ). Khóa công khai bao gồm: n, môđun e, số mũ công khai cũng gọi là số mũ mã hóa). Khóa bí mật bao gồm: n, môđun, xuất hiện cả trong khóa công khai và khóa bí mật, và d, số mũ bí mật cũng gọi là số mũ giải mã). Một dạng khác của khóa bí mật bao gồm: p and q, hai số nguyên tố chọn ban đầu, d mod (p-1) và d mod (q-1) thƣờng đƣợc gọi là dmp1 và dmq1), (1/q) mod p thƣờng đƣợc gọi là iqmp) Dạng này cho phép thực hiện giải mã và ký nhanh hơn với việc sử dụng định lý số dƣ Trung Quốc tiếng Anh: Chinese Remainder Theorem - CRT . Ở dạng này, tất cả thành phần của khóa bí mật phải đƣợc giữ bí mật.
57. Alice gửi khóa công khai cho Bob, và giữ bí mật khóa cá nhân của mình. Ở đây, p và q giữ vai trò rất quan trọng. Chúng là các phân tố của n và cho phép tính d khi biết e. Nếu không sử dụng dạng sau của khóa bí mật dạng CRT thì p và q sẽ đƣợc xóa ngay sau khi thực hiện xong quá trình tạo khóa. b. Mã hóa Giả sử Bob muốn gửi đoạn thông tin M cho Alice. Đầu tiên Bob chuyển M thành một số m < n theo một hàm có thể đảo ngƣợc từ m có thể xác định lại M đƣợc thỏa thuận trƣớc. Quá trình này đƣợc mô tả ở phần sau Lúc này Bob có m và biết n cũng nhƣ e do Alice gửi. Bob sẽ tính c là bản mã hóa của m theo công thức: Hàm trên có thể tính dễ dàng sử dụng phƣơng pháp tính hàm mũ theo môđun bằng thuật toán bình phƣơng và nhân. Cuối cùng Bob gửi c cho Alice. c. Giải mã Alice nhận c từ Bob và biết khóa bí mật d. Alice có thể tìm đƣợc m từ c theo công thức sau: Biết m, Alice tìm lại M theo phƣơng pháp đã thỏa thuận trƣớc. Quá trình giải mã hoạt động vì ta có . Do ed ≡ 1 mod p-1) và ed ≡ 1 mod q-1), (theo Định lý Fermat nhỏ) nên:
58. và Do p và q là hai số nguyên tố cùng nhau, áp dụng định lý số dư Trung Quốc, ta có: . hay: . Ví dụ Sau đây là một ví dụ với những số cụ thể. Ở đây chúng ta sử dụng những số nhỏ để tiện tính toán còn trong thực tế phải dùng các số có giá trị đủ lớn. Lấy: p = 61 — số nguyên tố thứ nhất giữ bí mật hoặc hủy sau khi tạo khóa q = 53 — số nguyên tố thứ hai giữ bí mật hoặc hủy sau khi tạo khóa n = pq = — môđun công bố công khai 3233 e = 17 — số mũ công khai d = 2753 — số mũ bí mật Khóa công khai là cặp e, n . Khóa bí mật là d. Hàm mã hóa là: encrypt(m) = me mod n = m17 mod 3233 với m là văn bản rõ. Hàm giải mã là: decrypt(c) = cd mod n = c2753 mod 3233 với c là văn bản mã.
59. Để mã hóa văn bản có giá trị 123, ta thực hiện phép tính: encrypt(123) = 12317 mod 3233 = 855 Để giải mã văn bản có giá trị 855, ta thực hiện phép tính: decrypt(855) = 8552753 mod 3233 = 123 Cả hai phép tính trên đều có thể đƣợc thực hiện hiệu quả nhờ giải thuật bình phƣơng và nhân. 4.2.3.Tốc độ mã hóa RSA Tốc độ và hiệu quả của nhiều phần mềm thƣơng mại có sẵn và công cụ phàn cứng của RSA đang gia tăng một cách nhanh chóng. Việc Pentium 90Mhz, bộ toolkit BSAFE 3.0 của cơ quan bảo mật dữ liệu RSA đạt tốc độ tính khóa bí mật là 21,6 Kbps với khóa 512 bit và 7,4 Kbps với khóa 1024 bit. Phần cứng RSA nhanh nhất đạy 300 Kbps với khóa 512 bit, nếu đƣợc xử lý song song thì đạt 600 Kbps với khóa 512 bit và 185 Kbps với khóa 970 bit. So sánh với giải thuật DES và các giải thuật mã khối khác thì RSA chậm hơn: về phần mềm DES nhanh hơn RSA 100 lần, về phần cứng DES nhanh hơn RSA từ 1000 tới 10000 lần tùy thuộc công cụ implementation sử dụng thông tin này đƣợc lấy từ Kích thƣớc của khóa trong RSA: Hiệu quả của một hệ thống mật mã khóa bất đối xứng phụ thuộc vào độ khó (lý thuyết hoặc tính toán của một vấn đề toán học nào đó chẳng hạn nhƣ bài toán phân tích ra thừa số nguyên tố. Giải các bài toán này thƣờng mất nhiều thời gian nhƣng thông thƣờng vẫn nhanh hơn là thử lần lƣợt từng khóa theo kiểu duyệt toàn bộ. Vì thế, khóa dùng trong các hệ thống này cần phải dài hơn trong các hệ thống mật mã khóa đối xứng. Tại thời điểm năm 2002, độ dài 1024 bít đƣợc xem là giá trị tối thiểu cho hệ thống sử dụng thuật toán RSA.
60. Năm 2003, công ty RSA Security cho rằng khóa RSA 1024 bít có độ an toàn tƣơng đƣơng với khóa 80 bít, khóa RSA 2048 bít tƣơng đƣơng với khóa 112 bít và khóa RSA 3072 bít tƣơng đƣơng với khóa 128 bít của hệ thống mật mã khóa đối xứng. Họ cũng đánh giá rằng, khóa 1024 bít có thể bị phá vỡ trong khoảng từ 2006 tới 2010 và khóa 2048 bít sẽ an toàn tới 2030. Các khóa 3072 bít cần đƣợc sử dụng trong trƣờng hợp thông tin cần giữ bí mật sau 2030. Các hƣớng dẫn về quản lý khóa của NIST cũng gợi ý rằng khóa RSA 15360 bít có độ an toàn tƣơng đƣơng với khóa đối xứng 256 bít. Một dạng khác của thuật toán mật mã hóa khóa bất đối xứng, mật mã đƣờng cong elliptic ECC , tỏ ra an toàn với khóa ngắn hơn khá nhiều so với các thuật toán khác. Hƣớng dẫn của NIST cho rằng khóa của ECC chỉ cần dài gấp đôi khóa của hệ thống khóa đối xứng. Giả định này đúng trong trƣờng hợp không có những đột phá trong việc giải các bài toán mà ECC đang sử dụng. Một văn bản mã hóa bằng ECC với khóa 109 bít đã bị phá vỡ bằng cách tấn công duyệt toàn bộ. Tùy thuộc vào kích thƣớc bảo mật của mỗi ngƣời và thời gian sống của khóa mà khóa có chiều dài thích hợp - loại Export 512 bit - loại Person 768 bit - loại Commercial 1024 bit - loại Militery 2048 bit Chu kỳ sống của khóa phụ thuộc vào - việc đăng ký và tạo khóa - việc phân bố khóa - việc kích hoạt và không kích hoạt khóa - việc thay thế hoặc cập nhật khóa - việc hủy bỏ khóa - việc kết thúc khóa bao gồm sự phá hoại hoặc sự lƣu trữ
61. 4.2.4.Độ an toàn của RSA Độ an toàn của hệ thống RSA dựa trên 2 vấn đề của toán học: bài toán phân tích ra thừa số nguyên tố các số nguyên lớn và bài toán RSA. Nếu 2 bài toán trên là khó không tìm đƣợc thuật toán hiệu quả để giải chúng thì không thể thực hiện đƣợc việc phá mã toàn bộ đối với RSA. Phá mã một phần phải đƣợc ngăn chặn bằng các phƣơng pháp chuyển đổi bản rõ an toàn. Bài toán RSA là bài toán tính căn bậc e môđun n với n là hợp số : tìm số m sao cho me=c mod n, trong đó e, n) chính là khóa công khai và c là bản mã. Hiện nay phƣơng pháp triển vọng nhất giải bài toán này là phân tích n ra thừa số nguyên tố. Khi thực hiện đƣợc điều này, kẻ tấn công sẽ tìm ra số mũ bí mật d từ khóa công khai và có thể giải mã theo đúng quy trình của thuật toán. Nếu kẻ tấn công tìm đƣợc 2 số nguyên tố p và q sao cho: n = pq thì có thể dễ dàng tìm đƣợc giá trị p-1)(q-1 và qua đó xác định d từ e. Chƣa có một phƣơng pháp nào đƣợc tìm ra trên máy tính để giải bài toán này trong thời gian đa thức polynomial-time). Tuy nhiên ngƣời ta cũng chƣa chứng minh đƣợc điều ngƣợc lại sự không tồn tại của thuật toán . Tại thời điểm năm 2005, số lớn nhất có thể đƣợc phân tích ra thừa số nguyên tố có độ dài 663 bít với phƣơng pháp phân tán trong khi khóa của RSA có độ dài từ 1024 tới 2048 bít. Một số chuyên gia cho rằng khóa 1024 bít có thể sớm bị phá vỡ cũng có nhiều ngƣời phản đối việc này . Với khóa 4096 bít thì hầu nhƣ không có khả năng bị phá vỡ trong tƣơng lai gần. Do đó, ngƣời ta thƣờng cho rằng RSA đảm bảo an toàn với điều kiện n đƣợc chọn đủ lớn. Nếu n có độ dài 256 bít hoặc ngắn hơn, nó có thể bị phân tích trong vài giờ với máy tính cá nhân dùng các phần mềm có sẵn. Nếu n có độ dài 512 bít, nó có thể bị phân tích bởi vài trăm máy tính tại thời điểm năm 1999. Một thiết bị lý thuyết có tên là TWIRL do Shamir và Tromer mô tả năm 2003 đã đặt ra câu hỏi về độ an toàn của khóa 1024 bít. Vì vậy hiện nay ngƣời ta khuyến cáo sử dụng khóa có độ dài tối thiểu 2048 bít. Năm 1993, Peter Shor công bố thuật toán Shor chỉ ra rằng: máy tính lƣợng tử (trên lý thuyết có thể giải bài toán phân tích ra thừa số trong thời gian đa thức. Tuy
62. nhiên, máy tính lƣợng tử vẫn chƣa thể phát triển đƣợc tới mức độ này trong nhiều năm nữa. Vì khóa là khóa công khai nên ngƣời giải mã thƣờng dựa vào cặp khóa này để tìm cặp khóa bí mật. Điều quan trọng là dựa vào n để tính hai thừa số p,q của n từ đó tính đƣợc d. Có nhiều giải thuật nhƣ thế, đàu tiên ta xét trƣờng hợp đơn giản nhất là ngƣời giải mã biết đƣợc  n . Khi đó tính p,q đƣa về việc giải hai phƣơng trình sau: n = p. q (n) = (p - 1)(q -1) Thay q= n/p ta đƣợc phƣơng trình bậc hai: p2 – (n- (n) +1 )p+n=0 Hai nghiệm của phƣơng trình bậc hai sẽ là p,q. tuy nhiên vấn đề có đƣợc (n) còn khó hơn tính hai thừa số nhiều Nếu ta chọn các số p,q khoảng 100 chữ số thập phân, thì n sẽ có khoảng 200 chữ số thập phân. Để phân tích một số nguyên cỡ lớn nhƣ thế, với các thuật toán nhanh nhất hiện nay và với những máy tính hiện đại nhất, ta mất hàng tỷ năm. Có một vài điều cần lƣu ý khi chọn các số p,q để tránh rơi vào trƣờng hợp tích hợp của pq bị phân tích nhanh nhờ những thuật toán đặc biệt: p và q cần chọn sao cho p-1 và q-1 không chỉ có toàn ƣớc nguyên tố nhỏ. Ngoài ra, UCLN p-1,q-1 phải là số nhỏ, p và q phải có chữ số trong khai triển thập phân khác nhau không nhiều. Một nhận định chung là tất cả các cuộc tấn công giải mã đều mang mục đích không tốt. Tính bảo mật của RSA chủ yếu dựa vào việc giữ bí mật khóa giải mã hay giữ bí mật các thừa số p,q của n. Ta thử xét một vài phƣơng thức tấn công điển hình của kẻ địch nhằm giải mã trong thuật toán này nhằm xâm phạm tới các yếu tố bí mật đó .
63. Trƣờng hợp 1: Chúng ta xét đến trƣờng hợp khi kẻ địch nào đó biết đƣợc modulo n, khóa công khai KB và bản tin mã hóa C, khi đó kẻ địch sẽ tìm ra bản tin gốc plaintext nhƣ thế nào. Để làm đƣợc điều đó kẻ địch thƣờng tấn công vào hệ thống mật mã bằng hai phƣơng thức sau đây: - phƣơng thức thứ nhất: Trƣớc tiên dựa vào phân tích thừa sô modulo n. Tếp theo sau chúng sẽ tìm cách tính otans ra hai thừa số p,q và có khả năng thành công khi đó sẽ tính đƣợc (n)=(p-1)(q-1) và khóa bí mật KB. Ta thấy n cần phải là tích của hai số nguyên tố, vì nếu n là tích của hai số nguyên tố thì thuật toán phân tích thừa số đơn giản cần tối đa n1/2 bƣớc, bởi vì có một số nguyên tố nhỏ hơn n1/2. Mặt khác, nêu sn là tích của n số nguyên tố thì thuật phân tích thừa sô đơn giản cần n1/n bƣớc. - Phƣơng thức thứ hai: phƣơng thức tấn công thứ hai vào hệ mã hóa RSA là có thể khởi đầu bằng cách giải quyết trƣờng hợp thích hợp của bàn toán logarit rời rạc. Trƣờng hợp này kẻ địch đã có trong tay bản mã C và khóa công khai KB tức là cặp KB,C) Trƣờng hợp 2: Chúng ta xét trƣờng hợp khi kẻ địch biết đƣợc modul n và  n , khi đó kẻ địch sẽ tìm ra bản gốc plaintext bằng cách sau: Biết  n thì có thể tính p,q theo hệ phƣơng trình: pq=n, (p-1)(q-1)= (n) do đó p,q là hai nghiệm của phƣơng trình bậc hai: p2 – (n- (n) +1 )p+n=0 Ví dụ n=84773093 và biết  n =84754668. Giải phƣơng trình bậc hai tƣơng ứng ta sẽ đƣợc hai nghiệm p=9539, q=8887.
64. 4.2.5.Sự che dấu thông tin trong hệ thống RSA Hệ thống RSA có một đặc điểm đặc trƣng là thông tin không phải luôn luôn đƣợc che dấu. Giả sử ngƣời gửi có e= 17, n=35. Nếu anh ta muốn gửi bất cứ data nào thuộc tập sau: {1,6,7,8,13,14,15,20,21,22,27,28,29,34} Thì mọi mật mã cũng chính là data ban đầu. Nghĩa là: M=Me mod n. Còn khi p=109, q=97, e= 865 thì hệ thống hoàn toàn không có sự che dấu thông tin bởi vì: M=Me mod 109*97 với mọi M Với mỗi modul n, không che dấu đƣợc ít nhất 9 message: M=Me mod n(1) Hay M=Me mod p và M=Me mod q(2) Với mỗi e, 2 có ít nhất 3 giải pháp thuộc tập {-1,0,1}. Do đó tất cả message thỏa (1) là: {M=[M(mod p), M(mod q)] | M(mod p), M(mod q) {-1,0,1}} Để xác định chính xác số message không đƣợc che dấu không bị thay đổi sau khi mã hóa ta sử dụng định lý sau: ―Nếu các message đƣợc mã hóa trong hệ thống RSA đƣợc xác định bởi số modul n=pq p,q, là số nguyên tố và khóa công khai e thì có: m=[1+UCLN(e-1,p-1)][1+UCLN(e-1,q-1)] message không bị che dấu ‖. Một số lƣu ý khi sử dụng hệ mật mã RSA Mọi ngƣời đều biết ―điểm mạnh ‖ của hệ mã với chìa khóa công khai RSA là dựa trên ―điểm yếu‖ của máy tính trong việc phân tích một số nguyên đủ lớn ra các thừa số nguyên tố. Với thời gian hơn 20 năm tồn tại trên via trò một hệ mã công kahi thông dụng nhất, RSA dã đƣơng đầu với các kiểu tấn công đủ loại của giới thám mã chuyên nghiệp. Kết quả hơn 20 năm ―công phá‖ hệ mã RSA của các nhà thám mã đã đƣợc tóm lƣợc trong bài báo của Dan Boneh với tiêu đề ―Hai mƣơi năm tấn công hệ mã RSA‖ đăng trong tờ
65. Notice ò the AMS, tháng 2-1999 , trong đó cho thấy rõ RSA có thể bị ―bẻ‖ khi ngƣời ta không biết dùng nó một cách ―bài bản‖. Khi chìa khóa lập mã hoặc giải mã là một số nguyên tố nhỏ thì ngƣời ta có những giải pháp ―bẻ‖ RSA một cách không mấy khó khăn. Thêm vào đó, không phải mọi hợp số lớn đều khó phân tích kể cả khi nó là tích của 2 số nguyên tố rất lớn , cho nên việc chọn các số nguyên tố p,q phải rất thận trọng. Gần đây ngƣời ta có đề cập đến khả năng phá hệ mã RSA bằng các máy tính đặc biệt với các con chip đặc chủng chuyên dụng cho việc phân tích số hoặc dùng thuật toán song song. Mặc dù hứa h n những tiến bộ vƣợt bậc nhƣng khả năng này vẫn chƣa trở thành hiện thực trong tƣơng lai gần, nhất là chuẩn của RSA đƣợc nâng cao thêm một bậc Trong các hệ mã RSA, một bản tin có thể đƣợc mã hóa trong thời gian tuyến tính Đối với các bản tin dài, độ dài của các số đƣợc dùng cho các khóa có thể đƣợc coi nhƣ là hằng. Tƣơng tự nhƣ vậy, nâng một số lên lũy thừa đƣợc thực hiện trong thời gian hằng, các số không đƣợc phép dài hơn một độ dài hằng. Thực ra tham số này che dấu nhiều chi tiết cài đặt có liên quan đến việc tính toán với các con số dài, chi phí của các phép toán thực sự là một yếu tố ngăn cản sự phổ biến ứng dụng của phƣơng pháp này. Phần quan trọng nhất của việc tính toán có liên quan đến việc mã hóa bản tin. Nhƣng chắc chắn là sẽ không có hệ mã hóa nào hết nếu không tính đƣợc các khóa của chúng là các số lớn. Các khóa cho hệ mã hóa RSA có thể đƣợc tạo ra mà không phải tính toán quá nhiều. Một lần nữa ta nói đến các phƣơng pháp kiểm tra số nguyên tố. Mỗi số nguyên tố lớn có thể đƣợc phát sinh băng cách đầu tiên tạo ra một số ngẫu nhiên lớn, sau đó kiểm tra các số kế tiếp cho tới khi tìm đƣợc một số nguyên tố. Một phƣơng pháp đơn giản thực hiện một phép tính trên một con số ngẫu nhiên, với xác suất ½ sẽ
66. chứng minh rằng số đƣợc kiểm tra không phải nguyên tố. Bƣớc cuối cùng tính p dựa vào thuật toán Euclid Nhƣ phần trên đã trình bày trong hệ mã hóa công khai thì khóa giải mã private key) kB và các thừa số p,q là đƣợc giữ bí mật và sự thành công của phƣơng pháp là tùy thuộc vào kẻ địch có khả năng tìm ra đƣợc giá trị của kB hay không nếu cho trƣớc n và KB .Rất khó có thể tìm ra đƣợc kB từ KB, cần biết về p, q.Nhƣ vậy cần phân tích n ra thành thừa số để tính p,q. Nhƣng việc tính phân tích ra thừa số là một việc làm tốn rất nhiều thời gian, với kỹ thuật hiện đại ngày nay thì cần tới hang triệu năm để phan tích một số có 200 chữ số ra thừa số. Độ an toàn của thuật toán RSA dựa trên cơ sở những khó khăn của việc xác định các thừa số nguyên tố của một số lớn. Bảng dƣới đây cho biết các thời gian dự đoán, giả sử rằng mỗi phép toán thực hiện trong một micro giây Số các chữ số Thời gian phân tích trong số đƣợc phân tích 50 4 giờ 75 104 giờ 100 74 năm 200 4.000.000 năm 300 5x 1015 năm 500 4x 1025 năm 4.3.Hệ mật Rabin Hệ thống mã hoá Rabin: có thể xem nhƣ gần gũi với RSA, mặc dù nó có quá trình giải mã khác. Điều thú vị là sự phá mã Của Rabin tƣơng với việc phân tích thừa số. Rabin sử dụng lũa thừa của 2 hay bất kì một số tự nhiên nào thay thế cho các số nguyên tố nhƣ trong RSA. Điều này dẫn tới 2 kết quả sau: Trƣớc tiên, hệ