phần mở đầu và kết luận, kết cấu của luận văn gồm 4 chƣơng: - Chƣơng 1 “Giới thiệu chung và cơ sở toán học của lý thuyết mật mã” nhằm trình bày các vấn đề chung nhất của mật mã, đƣa ra các khái niệm cơ bản. Phần cơ sở toán học trình bày các kiến thức toán học làm nền cho các nội dung chính trong luận văn nhƣ: số học các số nguyên, thuật toán Euclid, thuật toán Euclid mở rộng, lý thuyết đồng dƣ, thặng dƣ thu gọn, phần tử nguyên thủy, phƣơng trình đồng dƣ tuyến tình và đồng dƣ bậc hai. Ngoài ra trình bày về độ phức tạp thuật toán, hàm một phía và cửa sập một phía. - Chƣơng 2 “Phương pháp kiểm tra và sinh số nguyên tố” trình bày các định nghĩa, định lý về số nguyên tố.
Giới thiệu một số phƣơng pháp với các thuật toán kiểm tra và sinh số nguyên tố nói chung và số nguyên tố lớn nói riêng, đóng vai trò rất quan trọng trong việc cung cấp số nguyên tố lớn giúp thực thi, ứng dụng các hệ mã hóa khóa công khai. Các phƣơng pháp đƣợc trình bày trong luận văn là: phƣơng pháp cổ điển, phƣơng pháp xác suất và phƣơng pháp xác định. Trong chƣơng này cũng trình bày một phƣơng pháp phân tích một số ra thừa số nguyên tố. LUAN VAN CHAT LUONG download : add luanvanchat@agmail.com 9 - Chƣơng 3 “Đề xuất cấu trúc dữ liệu và thuật toán xử lý số nguyên lớn” trình bày cụ thể cấu trúc dữ liệu và đề xuất các thuật toán để có thể xây dựng hoàn chỉnh thƣ viện xử lý số nguyên lớn.
Thực tế xây dựng thì khả năng xử lý của thƣ viện này lên tới hàng nghìn chữ số và tốc độ thực hiện các phép toán nhƣ trong các ngôn lập trình, tƣơng đƣơng với thƣ viện đã có (có bổ sung so với nội dung đăng trong Kỷ yếu hội thảo quốc gia lần thứ XII “Một số vấn đề chọn lọc của công nghệ thông tin và truyền thông”, Đồng Nai, 8/2009, NXB KHKT 2010). - Chƣơng 4 “Một số hệ mã hóa khóa công khai và cải tiến hệ mã hóa Rabin” trình bày lịch sử ra đời, một số bài toán nền tảng xây dựng hệ mã hóa khóa công khai. Trong chƣơng này cũng trình bày một số hệ mã hóa khóa công khai RSA, ElGamal, Rabin. Hơn nữa chƣơng này đƣa ra hƣớng cải tiến nhằm nâng cao độ an toàn của hệ mã hóa khóa công khai Rabin và hƣớng khắc phục một số nhƣợc điểm trong quá trình giải mã.
Đƣa ra một số công thức tính nghịch đảo để quy trình giải mã của hệ mã hóa Rabin và Rabin cải tiến đƣợc dễ dàng. LUAN VAN CHAT LUONG download : add luanvanchat@agmail.com 10 Chƣơng 1 - GIỚI THIỆU CHUNG VÀ CƠ SỞ TOÁN HỌC CỦA LÝ THUYẾT MẬT MÃ Tóm tắt chương: Trong chương này luận văn giới thiệu lịch sử mật mã, các hệ mã, các bài toàn an toàn thông tin và bài toán thám mã. Đưa ra được một số khái niệm cơ bản nhất của mã hóa như: bản rõ, bản mã, hệ mã hóa thám mã, khóa mã, mã hóa khóa công khai, mã hóa khóa đối xứng, mã theo khối, mã theo dòng.v…Ngoài ra nội dung chương cũng trình bày về số học các số nguyên, thuật toán Eucild, thuật toán Euclid mở rộng, lý thuyết đồng dư, thặng dư thu gọn, phần tử nguyên thủy, phương trình đồng dư tuyến tình và đồng dư bậc hai. Ngoài ra trình bày về độ phức tạp thuật toán, hàm một phía và cửa sập một phía.
Các nội dung của chương này được tổng hợp từ các tài liệu [7][16]. Giới thiệu chung về mật mã 1. Sơ lƣợc lịch sử về mật mã Nhu cầu sử dụng mật mã đã xuất hiện từ rất sớm, khi con ngƣời biết trao đổi và truyền đƣa thông tin cho nhau, đặc biệt khi các thông tin đó đã đƣợc thể hiện dƣới hình thức ngôn ngữ, thƣ từ. Mật mã trƣớc hết là một loại hoạt động thực tiễn, lúc này nội dung chính của nó là để giữ bí mật thông tin từ một ngƣời gửi A đến một ngƣời nhận B.
Vì bản gửi đi thƣờng đƣợc chuyển qua các con đƣờng công khai nên ngƣời ngoài có thể “lấy trộm” đƣợc, nên thay vì gửi bản rõ thì A gửi cho B bản mã mật của bản rõ ngƣời ngoài không hiểu đƣợc. Nhƣng B có thể giải bản mã mật này thành bản rõ để hiểu đƣợc là do giữa hai ngƣời đã có một thỏa thuận về một chìa khóa chung. Chìa khóa chung đó đƣợc gọi đơn giản là khóa mật mã. Tất nhiên để thực hiện đƣợc một phép mật mã, còn cần có một thuật toán biến bản rõ, cùng với khóa mật mã, thành bản mã mật, và một thuật toán ngƣợc lại, biến bản mã mật, cùng với khóa mật mã, thành bản rõ.
Các thuật toán đó đƣợc gọi là tƣơng ứng là thuật toán lập mật mã và thuật toán giải mật mã. Các thuật toán này thƣờng không nhất thiết phải giữ bí mật, mà cái cần đƣợc giữ tuyệt mật luôn luôn là khóa mật mã. Trong thực tiễn, đã có hoạt động bảo mật thì cũng có hoạt động ngƣợc lại là khám phá bí mật từ các bản mật mã “lấy trộm” đƣợc, ta thƣờng gọi hoạt động này là mã thám, hoạt động này quan trọng không kém gì hoạt động bảo mật! Vì các thuật toán lập mật mã và giải mật mã không nhất thiết là bí mật, nên mã thám thƣờng đƣợc tập trung vào việc tìm khóa mật mã, do đó cũng có ngƣời gọi công việc đó là phá khóa. Suốt mấy nghìn năm lịch sử, các thông báo, thƣ từ đƣợc truyền đƣa và trao đổi với nhau thƣờng là các văn bản, tức là có dạng các dãy ký tự trong một ngôn ngữ nào đó; vì vậy, các thuật toán lập mật mã thƣờng cũng đơn giản là thuật toán xáo trộn, thay đổi các ký tự đƣợc xác định bởi các phép chuyển dịch, thay thế hay hoán vị các ký tự trong bảng ký tự của ngôn ngữ tƣơng ứng; khóa mật mã là thông tin dùng để thực hiện phép lập mật mã và giải mật mã cụ thể,.
Lúc này mật mã chƣa phải là một khoa học. Do trong một thời gian dài bản thân hoạt động mật mã cũng đƣợc xem là một bí mật, nên các tài liệu kỹ thuật về mật mã đƣợc phổ biến đến nay thƣờng chỉ ghi lại các kiến thức kinh nghiệm, thỉnh thoảng mới có một vài “phát minh” nhƣ các hệ mật mã Vigenère vào thế kỷ 16 hoặc hệ mật mã Hill ra đời năm 1929 là các hệ mã thực hiện phép chuyển dịch (đối với mã Vigenère) hay phép thay thế (mã Hill) đồng thời trên một nhóm ký tự chứ không phải trên LUAN VAN CHAT LUONG download : add luanvanchat@agmail.com 11 từng ký tự riêng rẽ. Vấn đề thám mã, ngƣợc lại, khi thành công thƣờng đƣa đến những cống hiến nổi trội và ấn tƣợng trong những tình huống gay cấn của các cuộc đấu tranh, và cũng thƣờng đòi hỏi nhiều tài năng phát hiện với những kinh nghiệm và suy luận tinh tế hơn. Nhƣ vậy, trƣớc đây mật mã chỉ đƣợc hiểu theo nghĩa hẹp, chủ yếu dùng đề bảo mật dữ liệu, ngƣời ta quan niệm: mật mã học là khoa học nghiên cứu mật mã: tạo mã và phân tích mã (thám mã) [16].
Bƣớc sang thế kỷ 20, với những tiến bộ liên tục của kỹ thuật tính toán và truyền thông, ngành mật mã cũng đã có những tiến bộ to lớn. Vào những thập niên đầu của thế kỷ, sự phát triển của các kỹ thuật biểu diễn, truyền và xử lý tín hiệu đã có tác động giúp cho các hoạt động lập và giải mật mã từ thủ công chuyển sang cơ giới hóa rồi điện tử hóa. Các văn bản, các bản mật mã trƣớc đây đƣợc viết bằng ngôn ngữ thông thƣờng nay đƣợc chuyển bằng kỹ thuật số thành các dãy tín hiệu nhị phân, tức các dãy bit, và các phép biến đổi trên các dãy ký tự đƣợc chuyển thành các phép biến đổi trên các dãy bit, hay các dãy số, việc thực hiện các phép lập mã, giải mã trở thành việc thực hiện các hàm số số học. Toán học và kỹ thuật tính toán bắt đầu trở thành công cụ cho việc phát triển khoa học về mật mã.
Khái niệm trung tâm của khoa học mật mã là khái niệm bí mật. Đó là một khái niệm phổ biến trong đời sống, nhƣng liệu có thể cho nó một nội dung có thể định nghĩa đƣợc một cách toán học không? Khái niệm bí mật thoạt đầu đƣợc gắn với khái niệm ngẫu nhiên, rồi về sau trong những thập niên gần đây, với khái niệm phức tạp, cụ thể hơn là khái niệm độ phức tạp tính toán. Việc sử dụng lý thuyết xác suất và ngẫu nhiên làm cơ sở để nghiên cứu mật mã đã giúp C.Shannon đƣa ra khái niệm bí mật hoàn toàn của một hệ mật mã từ năm 1948, khởi đầu cho một lý thuyết xác suất về mật mã. Trong thực tiễn làm mật mã, các dãy bit ngẫu nhiên đƣợc dùng để trộn với bản rõ (dƣới dạng một dãy bit xác định) thành ra bản mật mã.
Làm thế nào để tạo ra các dãy bit ngẫu nhiên? Có thể tạo ra bằng phƣơng pháp vật lý đơn giản nhƣ sau: ta tung đồng xu lên, nếu đồng xu rơi xuống ở mặt sấp thì ta ghi bit 0, ở mặt ngửa thì ta ghi bit 1; tung n lần ta sẽ đƣợc một dãy n bit, dãy bit thu đƣợc nhƣ vậy có thể đƣợc xem là dãy bit ngẫu nhiên. Nhƣng tạo ra theo cách nhƣ vậy thì khó có thể sử dụng một cách phổ biến, vì không thể tìm ra quy luật để theo đó mà sinh ra dãy bit ngẫu nhiên đƣợc. Ở đây ta gặp một khó khăn có tính bản chất: nếu qui luật thì đã không còn là ngẫu nhiên nữa rồi! Nhƣ vậy, nếu ta muốn tìm theo qui luật, thì không bao giờ có thể tìm ra các dãy bit ngẫu nhiên, hay giả ngẫu nhiên, mà thôi. Từ vài chục năm nay, ngƣời ta đã nghiên cứu đề xuất nhiều thuật toán toán học để sinh ra các dãy bit giả ngẫu nhiên, và cũng đã đƣa ra nhiều thuộc tính để đánh giá một dãy bit giả ngẫu nhiên có đáng đƣợc xem là “gần” ngẫu nhiên hay không.
Một vài thuộc tính chủ yếu mà ngƣời ta đã đề xuất là: cho một dãy bit X = (x1, x2, .); dãy đó đƣợc xem là giả ngẫu nhiên “tốt” nếu xác suất xuất hiện bit 0 hay bit l trong toàn dãy đó cũng nhƣ trong mọi dãy con bất kỳ của nó đều bằng 1/2; hoặc một tiêu chuẩn khác: nếu mọi chƣơng trình sinh ra đƣợc đoạn đầu n bit của dãy đều phải có độ phức tạp (hay độ dài) cỡ n ký tự!