Những điểm sáng – tối giữa toán học và mật mã (Phần 1)
Bài báo “Mối quan hệ không dễ dàng giữa toán học và mật mã học” của Giáo sư Neal Koblitz được xuất bản năm 2007. Trong bài báo, tác giả không khảo sát toàn diện mối quan hệ này trong lịch sử mà tập trung nêu ra những ưu điểm và một vài tồn tại của mối quan hệ toán học - mật mã đương đại mà tác giả cho là quan trọng. Nhiều vấn đề quan trọng đã được tác giả lý giải và nhiều tư liệu quý đã được giới thiệu trong bài viết. Tạp chí ATTT xin giới thiệu phần 1 của bài báo về những “điểm sáng” trong quan hệ giữa mật mã và toán học.
Tuy nhiên, cũng đã có những trường hợp ngoại lệ. Trong những năm 1940, Alan Turing (được cho là “cha đẻ” của Khoa học máy tính) làm việc nhiều năm trong lĩnh vực mật mã đã chỉ ra cách sử dụng các kỹ thuật thống kê hiện đại để phá mã. Claude Shannon (cha đẻ của Lý thuyết thông tin) đã xây dựng nên nền tảng của mật mã học. Cùng thời gian này, G.H. Hardy đã viết trong Lời xin lỗi của nhà toán học rằng, “cả Gauss và các nhà toán học cỡ nhỏ hơn có thể đã được biện hộ trong vui mừng rằng dù sao đi nữa có một khoa học [lý thuyết số], và rằng chủ nhân của chúng, những người rất xa với những hoạt động bình thường của con người, mãi giữ cho nó sự cao quý và trong sạch.” Trong thời kỳ của Hardy, hầu hết ứng dụng các kết quả nghiên cứu của các nhà toán học là dành cho quân sự. Là người theo “chủ nghĩa hòa bình”, Hardy đã đưa ra nhận xét rằng, lý thuyết số được nghiên cứu không phải để sử dụng thực tế, mà chỉ để gợi lên những cái đẹp bên trong.
Những điểm sáng trong mối liên hệ toán học và mật mã
Năm 1977, ba nhà khoa học máy tính làm việc tại viện Công nghệ Massachusetts - Ron Rivest, Adi Shamir và Len Adleman đã phát minh ra một hệ mật hoàn toàn mới. Bài báo trong tạp chí Scientific American của Martin Gardner đã mô tả ý tưởng RSA, giải thích ý nghĩa của nó và đã làm bùng phát sự quan tâm trong giới khoa học cả về lĩnh vực mật mã học và lý thuyết số. Trong những năm đó, RSA là phương thức quan trọng nhất để hiện thực cái được gọi là “mật mã khóa công khai”. Những hệ thống mật mã trước đó nhằm xáo trộn thông báo đã làm việc hiệu quả trong các ứng dụng quân sự và ngoại giao. Đó là những lĩnh vực có sự phân cấp chặt chẽ quyền được biết các khóa bí mật. Nhưng vào những năm 1970, máy tính trở nên phổ biến và được ứng dụng trong nhiều ngành nghề, những hạn chế của mật mã cổ điển ngày càng rõ nét, các dạng mật mã trước đó vốn được gọi là “khóa riêng” (hoặc khóa đối xứng) đã trở nên rất khó sử dụng.
Rivest, Shamir và Adleman đã phát minh ra hàm một chiều cửa sập nhờ sử dụng lý thuyết số sơ cấp. Kiến trúc thuật toán của họ dựa trên việc nhân hai số nguyên tố lớn p và q để được hợp số N=pq. Người ta phải giả định rằng, đây là quá trình một chiều theo nghĩa là việc phân tích N để nhận được p và q là hết sức khó khăn.
Như vậy, độ an toàn của hệ mật RSA phụ thuộc hoàn toàn vào độ khó giả định của việc phân tích số nguyên. Vì vậy, phát minh RSA đã kích thích lớn tới việc nghiên cứu các phương pháp phân tích số nguyên, cũng như các phương pháp để sinh các số nguyên tố lớn ngẫu nhiên. Đầu những năm 1980, những điểm nổi bật trong quan hệ mật mã - toán học trước hết là sự phát triển các kỹ thuật sàng bình phương nhằm cải tiến đối với các thuật toán phân tích tính chỉ số được gắn với tên nhà toán học Carl Pomerance. Sau đó là phép chứng minh tính nguyên tố gần đa thức tất định Adleman-Pomerance-Rumely bằng các phương pháp tính tổng jacobi.
Trong một hướng đi khác, Don Coppersmith đã tìm ra thuật toán có thể tìm lôgarít rời rạc trong nhóm nhân của với thời gian (n1/3+e) nhanh hơn nhiều so với các phương pháp tính chỉ số trước đó. Điều này có ý nghĩa với mật mã, vì ElGamal đã đề nghị một lựa chọn khác với hệ mật RSA, nó dựa trên độ khó được giả định về việc đảo ngược hàm xgx (trong đó g cố định) trong trường hữu hạn.
Năm 1984, Hendrik Lenstra đã công bố bản mô tả về phương pháp mới mà ông đã phát triển để phân tích số nguyên nhờ sử dụng đường cong elliptic. Thuật toán thông minh này được tóm tắt trong một trang giấy, tuy nhiên bài phân tích chi tiết về thời gian chạy của nó thì rất dài. Đây là lần đầu tiên các đường cong elliptic được sử dụng trong mật mã và là một thành công lớn, khi Lenstra đã nâng triết lý toán học trong mật mã lên một tầm mới hoàn toàn.
Năm 1985, Andrew Odlyzko, khi đó đang làm việc ở Bell Labs cũng đã mô tả ý tưởng về sử dụng nhóm đường cong elliptic để thiết lập một hệ mật. Odlyzko là một trong số ít nhà toán học lúc đó đã có nhiều công trình lớn trong cả lý thuyết và thực hành. Ngày nay, việc nối liền toán học thuần túy với toán học ứng dụng là chuyện bình thường, nhưng ở giữa thập niên 1980, Odlyzko là người duy nhất về phương diện này trong những nhà toán học mà Koblitz biết. Odlyzko đã nhận xét rằng, ý tưởng của Koblitz về sử dụng nhóm đường cong elliptic để thiết lập hệ mật là một dạng mới của mật mã và là ý tưởng tốt. Trong thực tế, Victor Miller của IBM cũng đã đề nghị giải pháp giống như vậy. Sức lôi cuốn của mật mã đường cong elliptic (ECC) ở chỗ, bài toán lôgarít rời rạc đường cong elliptic thực tế là (không thay đổi sau 20 năm) căn bản khó hơn nhiều bài toán phân tích số nguyên. Ban đầu, Victor và Koblitz không ai tưởng tượng rằng ECC sẽ có tầm quan trọng trong thương mại, mà chỉ thấy nó như một cấu trúc lý thuyết đẹp. Điều ngạc nhiên không phải ở chỗ Koblitz không có ý niệm thương mại hóa ý tưởng này, mà ngay cả Victor Miller cũng không suy nghĩ theo hướng thực tế, thậm chí không đề cập đến bằng phát minh. Mặc dù từ đó đến nay, chính sách của IBM là ủng hộ mạnh mẽ tất cả nhân viên nhận bằng phát minh cho mỗi điều mà họ có thể làm, ngay cả với những cơ sở nhỏ nhất. Do đó, câu hỏi về việc chuyển ECC thành sản phẩm thương mại phải đợi đến khi những người khác quan tâm đến nó nhiều hơn mới trả lời được.
Tại Mỹ, hội nghị mật mã quan trọng nhất là Crypto, hàng năm được tổ chức vào tháng 8 ở Santa Barbara, California. Trong những năm 1980, bầu không khí ở Crypto rất sôi nổi và hứng khởi. Đó thật sự là hội nghị “đa ngành”, với những người đến từ các ngành công nghiệp, cơ quan chính phủ và các học viện, trong các lĩnh vực từ toán học và khoa học máy tính đến các ngành kỹ thuật khác và giới doanh nhân.
Đầu những năm 1980, Ủy ban an ninh quốc gia Mỹ (NSA) đã thử nghiệm một việc (nhưng không thành công) để hạn chế việc nghiên cứu mở trong mật mã. Vì vậy, việc thành lập các hội nghị Crypto trong năm 1981 tự nó là một hành động thách thức.
Tinh thần tự do của các Hội nghị trong những năm 1980 đã phản ánh những cá tính riêng biệt và đầy màu sắc của nhóm những người sáng lập và nghiên cứu ban đầu về mật mã khóa công khai. Một người lỗi lạc trong số đó là Whit Diffie, không bị đánh bại, không thể đoán trước được và thuộc trường phái tự do, người đã cùng viết (với Martin Hellman) bài báo nổi tiếng nhất trong lịch sử mật mã vào năm 1976. Diffie thường thực hiện “phiên họp kéo dài”, nơi mà những sự trình diễn không mang tính hình thức, hài hước và hóm hỉnh. Ảnh hưởng tập thể khi đó là không đáng kể. Có sự chậm trễ kéo dài giữa phát minh mật mã khóa công khai và sự chấp nhận nó trong thế giới thương mại. Cuối thập niên 1980, nhìn chung các doanh nghiệp ít quan tâm đến hậu quả an toàn dữ liệu. Hầu hết các nhà nghiên cứu trong mật mã chưa bao giờ ký một “thỏa thuận không tiết lộ” giới hạn những điều mà người ta có thể nói công khai.
Nhà toán học Scott Vanstone, làm việc tại trường đại học Waterloo, đồng thời là lãnh đạo một nhóm đa ngành thực hiện những thuật toán được cải tiến cho số học trong các trường hữu hạn. Với kinh nghiệm đã có, họ được trang bị tốt để nghiên cứu về ECC. Vanstone, cùng với hai giáo sư khác, một về toán học và một về kỹ thuật, đã thành lập một công ty (tiền thân của tập đoàn Certicom), để phát triển và tiếp thị sản phẩm mật mã ECC.
Các đường cong elliptic không phải là loại đường cong duy nhất có thể được sử dụng trong mật mã. Năm 1989, Neal Koblitz đề xuất sử dụng các nhóm jacobi của các đường cong siêu elliptic. Những nghiên cứu gần đây, đặc biệt ở Đức, đã đề xuất các hệ mật đường cong siêu elliptic.
Tháng 9/1998, Joe Silverman, nhà toán học ở trường Đại học tổng hợp Brown (người viết hai tập sách giáo khoa xuất sắc về đường cong elliptic) đã phác họa một thuật toán mới để giải bài toán lôgarít rời rạc đường cong elliptic – nói cách khác, để phá vỡ mật mã đường cong elliptic. Silverman gọi thuật toán là “tính toán xedni” vì đó là từ “index” được đánh vần ngược. Ý tưởng tổng quát là thực hiện những bước tương tự như trong các thuật toán tính chỉ số nhưng theo thứ tự ngược lại. Lý do mà Silverman cho rằng thuật toán này hiệu quả là dựa trên mối quan hệ sâu xa (đến mức đóng băng) và phức tạp được gọi là phỏng đoán Birch và Swinnerton-Dyer. Điều kỳ lạ là trong cuốn sách của Neal Koblitz có nhan đề Các lĩnh vực đại số của mật mã được công bố trước đó cũng đã thảo luận về phỏng đoán này trong một đoạn mà ông gọi là “nền văn hóa”. Sau đó, Neal Koblitz đã dành một năm nghiên cứu sâu về tấn công của Silverman lên ECC, những tấn công dựa chính xác trên cái ý tưởng đằng sau phỏng đoán đó và Neal Koblitz nhận thấy, sẽ không thận trọng nếu phán đoán rằng, một dạng nhất định của toán học sẽ không bao giờđược ứng dụng trong mật mã.
Scott Vanstone và những người khác ở Certicom đã rất quan tâm về thuật toán của Joe Silverman, bởi vì những người hoài nghi ECC và những đối thủ - đặc biệt những người ở công ty RSA - sẽ nắm lấy thuật toán đó như một lý lẽ chống lại việc sử dụng đường cong elliptic.
Neal Koblitz đã dành nhiều thời gian cho việc phân tích thuật toán của Silverman. Từ lập luận lý thuyết Neal Koblitz nhận thấy, khi sử dụng khái niệm “độ cao” của điểm, chứng tỏ rằng đối với những nhóm đường cong elliptic rất, rất lớn thì tiếp cận xedni cực kỳ không hiệu quả. Tuy nhiên, với đường hướng chung này, Neal Koblitz không thể làm rõ ràng về kích cỡ, mà đối với chúng thuật toán này sẽ là không thực tế. Mặc dù chưa chắc chắn rằng, thuật toán này không thể làm được đối với những đường cong có kích cỡ được sử dụng trong mật mã.
Một kết quả tiệm cận không thể làm chỗ dựa để đảm bảo một sự an toàn bất kỳ nào. Hay đúng hơn, người ta phải phân tích thuật toán này đối với những đường cong elliptic có cỡ được sử dụng trong mật mã. Lý lẽ tiệm cận có thể có ích như một hướng dẫn, nhưng nó không thể thay thế cho việc phân tích an toàn cụ thể. Thực tế, chúng rất phức tạp và tiêu tốn thời gian thực hiện phân tích an toàn cụ thể hơn nhiều so với việc đưa ra các lập luận lý thuyết đối với kết quả tiệm cận.
Để trả lời câu hỏi quyết định về hiệu quả của xedni đối với các đường cong elliptic trong thực tế, Neal Koblitz đã làm việc với nhóm nghiên cứu đa ngành của các nhà toán học trẻ về khoa học máy tính ở trung tâm nghiên cứu mật mã ứng dụng ở Waterloo. Họ giữ liên lạc thường xuyên với Joe Silverman, bởi ông đã đưa ra những gợi ý tốt nhất để kiểm tra thuật toán của mình. Cuối cùng, bằng những tính toán đầy đủ, Silverman đã đồng ý rằng, thuật toán của ông là không thực tế. Thật ra, thuật toán đó có thể là thuật toán chậm nhất từng được nghĩ tới để tìm lôgarít rời rạc đường cong elliptic.
Tuy nhiên, nghiên cứu về xedni được cho là một dự án khuyến khích. Tấn công dự định của Silverman lên mật mã trên đường cong elliptic đã minh chứng việc sử dụng ngày một tăng môn hình học-đại số-số học trong mật mã khóa công khai.
Trong những năm 1990, một ví dụ khác về sự rắc rối lớn hơn của mật mã toán là đề xuất của Gerhard Frey về sử dụng phương pháp Weil descent để tìm logarit rời rạc trên các đường cong elliptic. Các thuật toán tiểu hàm mũ đối với logarit rời rạc trên các đường cong siêu elliptic có giống cao đã được phát triển bởi Adleman và Huang, và ý tưởng của Frey là chuyển bài toán logarit rời rạc trên các đường cong elliptic về bài toán đó trên các đường cong siêu elliptic có giống cao. Đề xuất của Frey đã được nghiên cứu bởi Galbraith, Gaudry, Hess, Menezes, Smart, Teske cùng nhiều người khác và đã được chứng tỏ là dẫn đến thuật toán nhanh hơn trong một vài trường hợp.
Đã có những tiến bộ trong việc tìm những phương pháp nhanh để đếm số các điểm trên đường cong elliptic được sinh ngẫu nhiên. Bước đầu tiên theo hướng này được trình bày trong bài báo được xuất bản vào năm 1985 của Schoof, người đã sử dụng các đa thức chia. Sau đó, những thuật toán tốt hơn đã được phát minh khi sử dụng các dạng modular và các kỹ thuật p-adic.
Một chỉ báo về tổng số nghiên cứu dành cho các ứng dụng mật mã của các đường cong elliptic trong những năm gần đây là loạt hội nghị ECC hàng năm, đến năm 2007 đã là năm thứ 11 (xem http://www.cacr.math.uwaterloo.ca).
Một dạng hoàn toàn mới về mật mã đường cong elliptic được phát triển bắt đầu khoảng năm 2000, dựa theo các ý tưởng của Antoine Joux, Dan Boneh và Matt Franklin. Thực tế cho thấy là các phương pháp ghép cặp Weil và Tate trên các đường cong elliptic có thể được dùng để đạt được chức năng mật mã mà trước đó không thể có (hoặc đã được làm mà không có hiệu quả), nhất là, mã hóa dựa trên nhận dạng (trong đó, khóa công khai chẳng hạn, là địa chỉ email của người sử dụng) và các chữ ký số đặc biệt ngắn. Mật mã dựa trên phương pháp ghép cặp là lĩnh vực nghiên cứu động. Tháng 7/2007, hội nghị đầu tiên trong một chuỗi hội nghị đã dành trọn thời gian cho các phát biểu, phân tích về dạng mật mã đường cong elliptic này được tổ chức ở Nhật Bản. (còn nữa)
Trang liên kết