Tác giả: Phan Dương Hiệu
Published: 12/04/2011
(Một phiên bản ngắn hơn của bài này sẽ đăng trong số kỷ niệm 20 năm báo Tia Sáng. Các bạn có thể xem tại đây)
Mã hóa khóa công khai ra đời cách đây 35 năm, đánh dấu bởi công trình khoa học của Whitfield Diffie và Martin Hellman. Đó thực sự là một bước ngoặt đưa mật mã từ một nghệ thuật thành một ngành khoa học. Trong quá trình 35 năm phát triển, những phát kiến trong mật mã hầu hết rất phản trực quan, và do đó càng bất ngờ thú vị, đã có ảnh hưởng lớn đến nhiều ngành khoa học khác: áp dụng những kết quả trừu tượng trong lý thuyết số vào thực tế; thúc đẩy sự phát triển của các thuật toán xác suất; đưa ra những khái niệm quan trọng trong lý thuyết tính toán mà điển hình là khái niệm chứng minh tương tác; tạo cầu nối giữa lý thuyết số và khoa học máy tính thông qua lý thuyết số tính toán… Trong bài này, chúng tôi sẽ điểm sơ qua sự phát triển của mật mã trong mối liên hệ với các ngành khoa học khác, và thảo luận về những hướng phát triển của mật mã trong những năm tới.
Thay đổi trong cách tiếp cận tính an toàn.
Từ ngàn xưa con người ta đã có nhu cầu trao đổi bí mật: từ những mệnh lệnh trong các cuộc chiến tranh cho đến những hẹn hò thường nhật. Ta tìm thấy vết tích của mật mã từ thời Ai cập cổ đại, cho tới hệ mã nổi tiếng mà Ceasar dùng trong thời La mã, cho tới bức thư tình mà George Sand gửi cho Alfred de Musset… Ở thời kỳ sơ khai, mật mã có thể coi như nghệ thuật che giấu thông tin mà độ an toàn đạt được là nhờ có sự thống nhất một qui ước bí mật chung. Như vậy, thuật toán lập mã và giải mã là bí mật. Nhưng khi tầm ứng dụng càng rộng thì yêu cầu bí mật cơ chế mã lại càng không hợp lý vì nhiều người sử dụng nên tất yếu sẽ rất dễ bị lộ. Cuối thế kỷ 19, Kerckhoffs đề nghị một nguyên tắc xem xét độ an toàn chỉ dựa trên khóa bí mật còn thuật toán lập mã/giải mã không cần phải giữ kín. Qui tắc này đến nay vẫn còn là rất cơ bản. Xuyên suốt thế kỷ vừa qua, người ta đã xây dựng được rất nhiều các cơ chế mã tốt, với độ an toàn dựa trên sự bảo mật của khóa chung giữa người gửi và người nhận. Tuy vậy, sự cần thiết chia sẻ khóa bí mật là một điểm bất thuận lợi, nó là rào cản lớn cho việc trao đổi thông tin trên diện rộng: ví dụ để thiết lập kênh bí mật đôi mội giữa một nghìn người thì cần tới cả nửa triệu khóa bí mật.
Thay đổi trong cách tiếp cận tính an toàn.
Từ ngàn xưa con người ta đã có nhu cầu trao đổi bí mật: từ những mệnh lệnh trong các cuộc chiến tranh cho đến những hẹn hò thường nhật. Ta tìm thấy vết tích của mật mã từ thời Ai cập cổ đại, cho tới hệ mã nổi tiếng mà Ceasar dùng trong thời La mã, cho tới bức thư tình mà George Sand gửi cho Alfred de Musset… Ở thời kỳ sơ khai, mật mã có thể coi như nghệ thuật che giấu thông tin mà độ an toàn đạt được là nhờ có sự thống nhất một qui ước bí mật chung. Như vậy, thuật toán lập mã và giải mã là bí mật. Nhưng khi tầm ứng dụng càng rộng thì yêu cầu bí mật cơ chế mã lại càng không hợp lý vì nhiều người sử dụng nên tất yếu sẽ rất dễ bị lộ. Cuối thế kỷ 19, Kerckhoffs đề nghị một nguyên tắc xem xét độ an toàn chỉ dựa trên khóa bí mật còn thuật toán lập mã/giải mã không cần phải giữ kín. Qui tắc này đến nay vẫn còn là rất cơ bản. Xuyên suốt thế kỷ vừa qua, người ta đã xây dựng được rất nhiều các cơ chế mã tốt, với độ an toàn dựa trên sự bảo mật của khóa chung giữa người gửi và người nhận. Tuy vậy, sự cần thiết chia sẻ khóa bí mật là một điểm bất thuận lợi, nó là rào cản lớn cho việc trao đổi thông tin trên diện rộng: ví dụ để thiết lập kênh bí mật đôi mội giữa một nghìn người thì cần tới cả nửa triệu khóa bí mật.
Mật mã khóa công khai đã vượt qua rào cản đó và đưa đến một bước ngoặt trong sự phát triển ngành mật mã. Ý tưởng chính của nó khá giản đơn: lập mã và giải mã là hai quá trình có bản chất khác nhau, nếu như giải mã nhất thiết phải dùng khóa bí mật (nếu không ai cũng giải được) thì lập mã lại không nhất thiết như vậy, và thậm chí sẽ càng tốt hơn khi ai cũng có thể lập mã. Do vậy, nếu ta có thể sinh ra một khóa bí mật cho giải mã và một khóa công khai tương ứng cho lập mã thì quá trình lập mã không còn cần bất kỳ bí mật nào. Tuy có vẻ tự nhiên nhưng việc mã hóa sử dụng khóa công khai làm thay đổi hoàn toàn yêu cầu về sự an toàn: khóa bí mật không cần chia sẻ nữa, mỗi người có khóa bí mật của riêng mình và chỉ cần giữ kín nó, không cần thiết phải chia sẻ nó với bất kỳ ai khác. Sự đảm bảo an toàn không còn cần dựa trên sự tin tưởng lẫn nhau giữa người gửi và người nhận.
Mật mã khóa công khai còn làm thay đổi hoàn toàn phạm vi ứng dụng, cho phép mật mã được sử dụng rộng rãi trong thực tế: việc thiết lập kênh bí mật giữa một nghìn hay một triệu người thì cũng chỉ yêu cầu mỗi người cần giữ một khóa bí mật và công bố một khóa công khai, không cần phải thống nhất khóa chung nào. Áp dụng vào thực tế, một cửa hàng trực tuyến có thể thu hút hàng triệu khách hàng mà chỉ cần công khai duy nhất một khóa để ai mua hàng cũng chỉ cần dùng khóa công khai đó để gửi thông tin bảo mật về thẻ thanh toán.
Mật mã với lý thuyết độ phức tạp tính toán
Bên cạnh những ưu điểm mang tính bước ngoặt, mã hóa khóa công khai ẩn chứa một điều đáng lo ngại về tính an toàn: khi công bố khóa công khai tương ứng với khóa bí mật sẽ có thể dẫn tới việc khóa bí mật không còn … hoàn toàn bí mật! Điều lo ngại đó hoàn toàn có cơ sở bởi một kẻ tấn công có thể thử hết các trường hợp có thể để tìm ra khóa bí mật tương ứng với khóa công khai. Do đó, về nguyên tắc, kẻ tấn công có thể phá được sơ đồ mã hóa, tìm ra khóa bí mật mà không cần quan sát bất kể bản mã nào! Chính vì thế mà độ an toàn của mật mã khóa công khai sẽ không thể chỉ dựa trên sự giữ bí mật khóa nữa. Muốn đảm bảo sự an toàn, ta phải chứng tỏ làm sao, dù về nguyên tắc, kẻ tấn công có thể tìm ra khóa bí mật, nhưng thời gian để đạt được mục đích đó phải là rất lớn, cỡ hàng triệu năm trên một máy tính nhanh nhất chẳng hạn. Hay nói cách khác, độ phức tạp mà kẻ tấn công có thể tìm lại khóa bí mật là lớn phi thực tế.
Một cách rất tự nhiên, nghiên cứu độ an toàn của mật mã khóa công khai đã nằm gọn trong lý thuyết độ phức tạp tính toán (Computational Complexity). Trong lý thuyết độ phức tạp, ta không chỉ quan tâm xem một bài toán có thể giải được hay không, mà điều quan trọng nhất là nghiên cứu xem để giải bài toán đó thì độ khó khăn lớn đến đâu. Độ phức tạp được phân cấp theo các lớp, trong đó hai lớp quan trọng nhất là lớp P và lớp NP. Lớp P bao gồm những bài toán giải được trong thời gian đa thức, và nó được coi là lớp các bài toán có thể giải được trong thực tế. Chẳng hạn các bài toán sắp xếp dữ liệu theo một thứ tự định sẵn, tìm đường đi ngắn nhất giữa hai thành phố, biến đổi Fourrier rời rạc (đều có thể thực hiện được với cỡ nlog(n)bước cho n đối tượng, tức là bị chặn bên bởi một đa thức
) là những bài toán trong P. Lớp NP là lớp các bài toán có thể kiểm tra được lời giải đúng hay sai trong thời gian đa thức. Chẳng hạn trò chơi Sudoku thuộc lớp NP vì để giải nó có thể rất khó (thậm chí nó được chứng minh là một trong những bài toán thuộc lớp khó giải nhất trong NP) nhưng để kiểm tra một phương án có là lời giải không thì có lẽ chỉ cần đến một cậu bé biết phân biệt các con số với nhau và duyệt qua tất cả các ô. Rõ ràng chỉ khi lời giải có thể kiểm tra được trong thực tế thì bài toán mới được quan tâm, do vậy mà lớp NP có vai trò quan trọng. Câu hỏi trọng tâm của lý thuyết độ phức tạp là liệu các bài toán trong NP có thể có lời giải thực tế (tức trong thời gian đa thức) hay không, tức liệu P có bằng NP? Nếu P=NP thì điều đó đem lại một sự bất ngờ cho nhận thức của chúng ta: việc tìm ra lời giải cũng chỉ khó như việc kiểm tra lời giải. Điều khó tin đó làm người ta thường giả thuyết rằng P khác NP. Sự quan trọng của câu hỏi "P chọi NP?" là lý do để nó được viện Clay xếp vào một trong bảy bài toán thiên niên kỷ.
Quay trở lại với lý thuyết mật mã và xem xét nó dưới góc nhìn của lý thuyết độ phức tạp. Giờ đây ta có thể định nghĩa hệ mã bị phá nếu như có thuật toán phá mã (tìm lại khóa bí mật từ khóa công khai, hay đơn giản hơn, tìm lại bản rõ từ bản mã) trong thời gian đa thức. Vậy độ phức tạp của thuật toán phá mã liệu có thể đánh giá trong trường hợp chung? Câu trả lời là có và với mọi sơ đồ mã hóa khóa công khai đều có thuật toán phá mã thuộc lớp NP: do điều kiện cần của hệ mã là khi giải mã ta phải tìm lại đúng bản rõ, bài toán kiểm tra xem 1 khóa bí mật có tương ứng với 1 khóa công khai hay không là dễ dàng (chỉ cần chọn 1 bản rõ, mã nó dùng khóa công khai rồi giải mã nó với khóa bí mật xem có thu lại được đúng bản rõ hay không). Bài toán "P chọi NP" trở nên có tầm quan trọng sống còn tới lý thuyết mật mã: nếu hai lớp này tương đương thì toàn bộ lý thuyết nghiên cứu mật mã dưới góc nhìn độ phức tạp sẽ hoàn toàn sụp đổ vì việc phá mã, vốn thuộc NP, khi đó sẽ có thể thực hiện được trong thời gian đa thức. Và cũng do vậy, nghiên cứu độ phức tạp trong mật mã cần phải dựa trên giả thuyết "P khác NP".
Hàm cửa lật một chiều và sự phát triển của lý thuyết số tính toán
Khi tính an toàn chia tay với nghệ thuật che giấu bí mật để chuyển sang dựa trên lý thuyết độ phức tạp thì cũng là lúc mật mã bất ngờ tìm đến và làm những nghiên cứu trừu tượng trong lý thuyết số bỗng có những áp dụng đầy ý nghĩa trong thực tế. Nó cũng đưa lý thuyết số tính toán (computational number theory) trở thành một nhánh nghiên cứu quan trọng, nằm giữa vùng giao thoa của toán học và tin học.
Tựu chung yêu cầu để xây dựng mật mã khóa công khai là: hàm lập mã thì dễ (với khóa công khai), nhưng hàm giải mã thì khó khi không có khóa bí mật. Đó là các hàm cửa lật một chiều (trapdoor oneway functions): tính xuôi thì dễ, tính ngược lại phải khó, nhưng với cửa lật là khóa bí mật thì tính ngược, tức giải mã, cũng phải dễ. Yêu cầu trông có vẻ đơn giản đó nhưng thực tế là sau rất nhiều năm tìm kiếm vẫn chỉ có rất ít hàm có thể thỏa mãn. Các bài toán trong lớp NP-đầy đủ (là lớp các bài khó nhất trong NP, trò chơi Sudoku là một trong số đó; ta chỉ cần giải được 1 bài trong lớp NP-đầy đủ trong thời gian đa thức là đủ để chứng tỏ P=NP) rõ ràng là những ứng cử viên tiềm năng để xây dựng hàm cửa lật một chiều. Nhưng thực tế không hề dễ như ban đầu người ta hình dung, vì hai lý do: thứ nhất là bởi các bài toán NP chỉ quan tâm đến độ khó trong trường hợp xấu nhất, trong khi mã hóa cần mã an toàn cho mọi bản rõ nên cần ít nhất độ khó trong trường hợp trung bình; thứ hai là bởi tính chất cửa lật, bài toán cần khó nhưng với một số thông tin thì nó lại phải trở nên dễ giải, và chính yêu cầu về tính chất cửa lật đó đã khiến nhiều hệ mã dựa trên bài toán NP-đầy đủ (như hệ mã Chor-Rivest dựa trên bài toán xếp ba lô) bị phá vỡ.
Những hàm cửa lật thông dụng trong mật mã đã đến từ những bài toán rất cổ điển của lý thuyết số! Đó là bài toán phân tích số (cho một số N = pq là tích của hai số nguyên tố, phân tích nó ra thừa số nguyên tố p,q) và bài toán logarit rời rạc trong trường hữu hạn (cho một phần tử sinh g của một nhóm con của một trường hữu hạn, và một phần tử nhóm u=ga, bài toán là phải tìm lại a). Cả hai bài toán này, tuy về mặt toán học là giải được, nhưng cho đến nay không thể giải được trong thời gian đa thức. Bài toán phân tích số là nền tảng cho độ an toàn của hệ mã nổi tiếng RSA, và bài toán logarit rời rạc là cơ sở cho hệ mã Elgamal. Chính vì tính phổ dụng của hai hệ mã này mà một cách tất nhiên, bài toán phân tích số và bài toán logarit rời rạc trở thành đối tượng nghiên cứu rất được quan tâm. Việc nghiên cứu tính phức tạp của việc tìm ra lời giải cho các bài toán lý thuyết số đã đưa tới sự phát triển sâu rộng của lý thuyết số tính toán.
Sau nhiều công trình nghiên cứu quan trọng thì các bài toán bài toán phân tích số và bài toán logarit rời rạc tuy chưa giải được trong thời gian đa thức nhưng cũng không cần đến thời gian hàm mũ để giải nó, mà đã có các thuật toán dưới mũ (sub-exponention) như thuật toán dùng tính chỉ số (index calculus) và thuật toán dùng đường cong elliptic của Lenstra, được giới thiệu năm 1985. Dù cho những công trình này không làm các hệ mã sụp đổ, nhưng nó buộc phép xây dựng các hệ mã phải giảm hiệu quả vì phải dùng các khóa dài hơn để đảm bảo an toàn. Công trình của Lenstra cũng đánh dấu lần đầu tiên lý thuyết các đường cong elliptic được sử dụng vào mật mã, ở đây có vai trò như phá mã. Điều thú vị là ngay sau đó thì lý thuyết các đường cong elliptic đã được sử dụng cho việc lập mã. Koblitz và Miller cùng độc lập đề nghị thay thế việc sử dụng nhóm trong trường hữu hạn bằng nhóm các điểm trên đường cong elliptic vì ở đó, các thuật toán dưới mũ đã biết để giải quyết bài toán logarit rời rạc có vẻ như không thể áp dụng được. Từ đó việc sử dụng đường cong elliptic dẫn tới dẫn đến những hệ mã hiệu quả hơn (do không cần phải chọn khóa quá dài để chống lại các thuật toán dưới mũ).
Các kết quả lý thuyết sâu sắc trong lý thuyết số tiếp tục được áp dụng vào mật mã. Việc sử dụng đường cong elliptic dẫn tới yêu cầu cần phải lựa chọn những đường cong phù hợp. Tấn công MOV (đưa ra bởi Menezes, Okamoto, và Vanstone) chỉ ra không phải loại đường cong elliptic nào cũng có thể được sử dụng, bằng cách đưa việc giải quyết bài toán logarit rời rạc trên đường cong elliptic trở lại bài toán logarit rời rạc trên một trường hữu hạn mở rộng với độ mở rộng tùy thuộc vào loại đường cong. Do đó, các đường cong siêu lạ (supersingular) rất được ưa dùng ở giai đoạn đầu lại trở nên rất yếu vì ở đó độ mở rộng chỉ cao nhất là 6. Nét đặc biệt trong tấn công MOV là việc sử dụng phép ghép cặp (pairings) trên các đường cong elliptic, với những kết quả khá mới mẻ trong lý thuyết số. Không chỉ phục vụ cho việc phá mã, việc sử dụng phép ghép cặp sau đó đã trở nên cực kỳ hữu hiệu trong việc xây dựng mã. Khởi đầu là Joux đã dùng phép ghép cặp để xây dựng sơ đồ trao đổi khóa 3 bên, nhưng sự kiện nổi bật là việc dùng phép ghép cặp để giải quyết vấn đề mở về xây dựng mã hóa dựa trên danh tính-Identity based Encryption. Một cách giản đơn, mã hóa dựa trên danh tính cho phép ta sử dụng một khóa công khai duy nhất cho tất cả mọi người (từ đó giải quyết được vấn đề quản lý khóa của mã hóa khóa công khai, tuy vậy nhược điểm của nó là lại cần có thêm người quản trị đáng tin cậy để sinh ra khóa công khai chung và khóa bí mật cho từng người) và hàm lập mã dựa trên khóa công khai chung và danh tính của người nhận như địa chỉ email. Sau khi Sakai-Ohgishi-Kasahara và Boneh-Franklin đưa ra lời giải cho bài toán mã hóa dựa trên danh tính vào những năm 2000, phép ghép cặp đã được sử dụng hầu khắp trong mọi lĩnh vực của mật mã (mã hóa, chứa ký điện tử, sơ đồ định danh…) để nâng cao tính an toàn và hiệu quả và đôi khi là giải quyết những bài toán mở đã bế tắc trong thời gian dài (chẳng hạn như trong việc xây dựng chữ ký nhóm). Đến cách đây vài năm người ta đã tổ chức hẳn một hội nghị (Pairing-based Cryptograhy) dành cho các nghiên cứu liên quan đến các thuật toán xây dựng và phân tích các phép ghép cặp trên các đường cong elliptic hay hyperelliptic và các phương pháp mã và tấn công mã dựa trên phép ghép cặp.
Nhìn lại các phát triển của lý thuyết số tính toán, ta nhận thấy các phương pháp mới thường được đề nghị đầu tiên cho phá mã, nhưng rồi sau đó lại được sử dụng rất hiệu quả cho việc lập mã. Điều đó cũng phần nào chứng tỏ vai trò tương hỗ giữa cộng đồng những người thám mã và lập mã: trong rất nhiều trường hợp, chính những người say mê tìm cách phá tính an toàn của các hệ thống mật mã, sẽ là những người đem tới những phát kiến mới mẻ để xây dựng những hệ mã an toàn hơn.
Đảm bảo tính an toàn và sự phát triển của lý thuyết các thuật toán xác suất
Để có thể cài đặt được hệ mã RSA, một phần tất yếu là sự cần thiết phải tìm được những số nguyên tố lớn để có thể đảm bảo yêu cầu an toàn tối thiểu (khóa công khai chứa tích của hai số nguyên tố, và nếu một trong hai số nguyên tố là nhỏ thì bài toán phân tích số sẽ là dễ). Từ đó mà yêu cầu tìm các số nguyên tố lớn trở nên rất cần thiết.
Cho tới nay, các phương pháp tìm số nguyên tố lớn đều theo nguyên tắc hai bước: bước 1 là chọn một số tự nhiên đủ lớn và bước 2 là kiểm tra xem số được chọn có là số nguyên tố hay không. Do các số nguyên tố có cấu trúc rất bí hiểm và ta chưa hiểu được quy luật tường minh của chúng nên bước 1 chưa có cách nào khác là chọn một số ngẫu nhiên. Bước thứ 2 là bước kiểm tra tính nguyên tố. Chính những thuật toán kiểm tra tính nguyên tố, mà điển hình là những thuật toán được sử dụng rộng rãi của của Rabin và Solovay, Strassen, đã khởi đầu cho việc dùng xác suất để thiết kế các thuật toán (chú ý rằng trước đó khá lâu phương pháp xác suất đã được Erd ̋os sử dụng trong việc chỉ ra sự tồn tại của các đối tượng tổ hợp). Các thuật toán xác suất cho ta lời giải không hoàn toàn chính xác, nhưng độ không chính xác có thể làm nhỏ tới bao nhiêu cũng được, với điều kiện đầu vào của thuật toán có một nguồn ngẫu nhiên đủ lớn.
Việc phát triển các thuật toán xác suất dẫn tới sự cần thiết tìm nguồn ngẫu nhiên đủ lớn. Điều đó dẫn tới việc nghiên cứu những bài toán sau đó đã trở nên rất có ý nghĩa trong khoa học máy tính như bài toán trích nguồn ngẫu nhiên (randomness extractor, nhằm từ một nguồn không hoàn toàn ngẫu nhiên ta phải trích ra từ đó một lượng tin có độ ngẫu nhiên cao) và bài toán sinh dãy giả ngẫu nhiên (pseudo-random generator – từ một nguồn ngẫu nhiên nhỏ làm sao sinh ra một nguồn gần như ngẫu nhiên lớn hơn rất nhiều, nó không hoàn toàn ngẫu nhiên nhưng không có thuật toán nào trong thời gian đa thức có thể chỉ ra tính không ngẫu nhiên của nó)
Sau nhiều phát triển quan trọng của lý thuyết thuật toán xác suất, người ta quay lại hoài nghi "liệu độ ngẫu nhiên có thực sự mang tới sự hiệu quả?". Bài toán "BPP chọi P" (ở đó BPP là lớp các bài toán giải được theo nghĩa xác suất) là một bài toán mở trọng tâm của lý thuyết độ phức tạp. Cũng như bài toán "P vs. NP", nếu câu trả lời là hai lớp tương đương thì nó sẽ dẫn tới một khẳng định bất ngờ: mọi thuật toán xác suât đều có thể có thuật toán tất định tương đương. Bên cạnh câu hỏi tổng quan này, các nhà nghiên cứu quay lại với bài toán tìm số nguyên tố nhằm đưa ra một lời giải tất định cho nó. Công trình lý thuyết đột phá của Agrawal–Kayal–Saxena đưa ra năm 2000, đã chỉ ra một thuật toán tất định để kiểm thử tính nguyên tố trong thời gian đa thức, giải quyết trọng vẹn bước thứ 2 một cách tất định. Sự hấp dẫn của một lời giải hoàn chỉnh cho bài toán tất định tìm số nguyên tố chính là nguồn cảm hứng chung rất lớn của các nhà toán-tin học và nó được chọn là bài toán khởi đầu cho một kế hoạch đầy tham vọng nhằm thay đổi tư duy trong hợp tác nghiên cứu khoa học: hợp tác mở thông qua đóng góp, trao đổi mở trên mạng. Với sự nhiệt tình của Timothy Gower, Terence Tao (cả hai đều đạt giải thưởng Fields), đã có rất nhiều nhà khoa học tham gia vào dự án mở Polymath để cùng trao đổi nhằm tìm kiếm lời giải cho bài toán này. Tuy chưa thể đưa ra lời giải toàn phần, họ đã có một số kết quả dẫn tới một bài báo khoa học dưới tên tác giả Polymath. Rất có thể đây sẽ là một hình thức cộng tác khoa học xuyên biên giới có sức mạnh tổng hợp lớn trong tương lai.
Chứng minh tương tác không để lộ tri thức
Trong mật mã, mọi trao đổi thông tin đều giả thiết có sự hiện diện của kẻ xấu. Mục đích của ta là vừa có thể thuyết phục người đối thoại về tính đúng đắn của một mệnh đề nào đó, lại vừa không cần tin tưởng anh ta, và không muốn sau khi trao đổi anh ta cũng có khả năng chứng minh mệnh đề đó với người khác. Chẳng hạn, một thành viên của một câu lạc bộ bí mật muốn chứng minh danh tính của mình cho người gác cổng, nhưng lại không muốn nói mật khẩu của mình vì sợ chính người gác cổng sẽ bán nó cho kẻ khác. Trong ngữ cảnh đó, một trong những khái niệm thú vị nhất của khoa học máy tính đã được đề nghị: chứng minh tương tác (interactive proofs). Khái niệm này được đưa ra bởi Babai, Goldwasser, Micali, Moran và Rackof vào đầu những năm 80 và nhờ đó họ đã được trao giải Godel đầu tiên trong lịch sử (giải thưởng hàng năm cho công trình lý thuyết xuất sắc nhất trong khoa học máy tính).
Dưới góc độ toán học, ta thường quan niệm chứng minh là một dãy các lập luận lô gíc có thể trình bày tường minh trên giấy. Liệu chăng yếu tố đối thoại, tương tác giữa người chứng minh và người kiểm tra có mang đến điều mới mẻ? Để trả lời câu hỏi đó, trước hết khái niệm về một chứng minh sẽ phải thay đổi. Goldreich thường trích lời thầy giáo Simon của mình khi giảng về các chứng minh tương tác:
"Chứng minh là bất kể cách gì có thể thuyết phục được tôi" (" A proof is whatever convinces me").
Theo nghĩa đó, một chứng minh tương tác là một chuỗi các chất vấn, cho tới khi người hỏi bị thuyết phục hoàn toàn bởi người chứng minh. Một câu chuyện vui kể rằng, rằng, một cậu bé cho rằng mình có câu thần chú để mở vách ngăn giữa hai nhánh của một hang động. Tất nhiên cậu ta không muốn lộ câu thần chú của mình, nhưng lại muốn chứng minh khả năng đó. Trò chơi đuổi bắt có thể là một chứng minh tương tác hiệu quả: chú bé chạy vào 1 trong hai ngã, một người đuổi chon một hướng nhằm dồn chú vào ngách ngăn nhưng cuối cùng không lần nào bắt được chú. Nếu đuổi một lần ta có thể cho là chú đã chọn ngã khác, nhưng lặp đi lặp lại trò chơi tới 100 lần mà không lần nào đuổi được thì có lẽ ta bị thuyết phục là chú đúng là có câu thần chú (ví dụ lấy từ Wikipedia). Các chứng minh tương tác hầu hết dựa trên một tinh thần như thế.
Có những bài toán mà người ta chưa biết cách nào chứng minh trong thời gian đa thức, nhưng lại chứng minh được thông qua tương tác, chẳng hạn bài toán chứng minh hai đồ thị không đồng cấu với nhau. Hơn thế nữa, trong nhiều bài toán, người chứng minh có thể không cần để lộ ra bất kể tri thức nào anh ta có về cái chứng minh đó (zero-knowledge proofs).
Kết quả rất đẹp của Goldreich, Micali và Wigderson cho ta kết quả bất ngờ: dựa trên giả thuyết tồn tại các hàm một chiều, tất cả những gì ta có thể chứng minh trong thực tế (theo nghĩa trong thời gian đa thức), đều có thể chứng minh mà không để lộ tri thức! Bài toán chứng minh danh tính phía trên là một trong số đó.
Các chứng minh không để lộ tri thức đặc biệt quan trọng trong mật mã, là thành phần cơ bản trong việc xây dựng các sơ đồ mã hóa, chữ ký điện tử. Chứng minh không để lộ tri thức cũng là thành phần không thể thiếu trong một sơ đồ bầu cử điện tử, cho phép mỗi cử tri kiểm tra được lá phiếu của mình đã được tính đến mà việc kiểm phiếu lại không cần phải công bố nội dung từng lá phiếu, đảm bảo quyền lựa chọn bí mật của cử tri.
Ở một khía cạnh khác, chứng minh tương tác cũng là phần hồn của nhánh khoa học «chứng minh tính bảo mật » (provable security), nơi ta cố gắng chứng minh tính an toàn của hệ thống trong một thế giới tương tác rất phức tạp (với sự hiện diện của kẻ tấn công luôn muốn lừa hệ thống thông qua quan sát, nghe trộm, đóng giả người tốt để tương tác với hệ thống) dựa trên những giả thuyết tĩnh, giản đơn của toán học.
Một số hướng đi tương lai của mật mã
Bảo mật trong điện toán đám mây (cloud computing)
Điện toán đám mây cho phép ta lưu trữ những khối lượng thông tin khổng lồ trên mạng và thực hiện các thao tác trên nó một cách dễ dàng. Nó có thể giúp ta giải quyết những bài toán lớn mà trước đây khó có thể giải quyết trên một mạng lưới các máy tính mang tính chất cục bộ. Tuy nhiên, điều đó mang tới một thách thức vô cùng lớn về tính bảo mật. Có hai điều có vẻ như mâu thuẫn nhau: lưu trữ dữ liệu lớn trên các hệ thống xa lạ rõ ràng rất dễ bị đánh cắp thông tin, nhưng nếu ta mã hóa toàn bộ dữ liệu thì sẽ khó có thể tận dụng sức mạnh của tính toán đám mây để thao tác dữ liệu đó.
Nhưng gần đây, vấn đề tưởng khó có thể giải quyết này đã có chút tia hy vọng, với công trình của Gentry năm 2009 về mật mã đẳng cấu theo cả phép nhân và phép cộng (fully homomorphic encryption). Hệ mã này cho phép, từ hai bản mã của hai bản rõ m và m', ta có thể tính được bản mã nhân của mm' và bản mã cộng của m+m'. Vấn đề với bề ngoài đơn giản nhưng chứa đựng không ít nghịch lý trong đó: hệ mã vừa phải đảm bảo an toàn cho dữ liệu (không thể biết thông tin về bản rõ m, m'), mà lại vẫn thao tác được trên dữ liệu đó. Và cũng với bề ngoài giản đơn như vậy, nó lại mang đến một ý nghĩa rất bao quát: do mọi tính toán đều có thể qui về các phép toán cơ bản là cộng và nhân, một hệ mã như thế sẽ cho ta khả năng làm mọi tính toán trên dự liệu được mã hóa! Điều đó có nghĩa ta có thể để tất cả dữ liệu bảo mật trên những máy mạng không an toàn mà vẫn có thể tận dụng được sức tính toán lớn của điện toán đám mây để thao tác trên dữ liệu được mã hóa. Tuy nhiên, hiện tại, hệ mã Gentry và một số hệ mã cải tiến còn có hiệu quả vô cùng thấp, hầu như chỉ mang tính lý thuyết. Một hệ mã hiệu quả sẽ là lời giải tuyệt vời cho bài toán an toàn thông tin trong điện toán đám mây.
Mở rộng mô hình mã hóa: cho đối tượng nhóm và cho việc giải mã bộ phận
Mã hóa thường cho ta thiết lập kênh trao đổi thông tin giữa một người với một người. Tuy nhiên, những ứng dụng thực tế đòi hỏi khả năng ta mã một lần sao cho nhiều người cùng có thể giải mã. Một ví dụ điển hình là việc phát chương trình truyền hình mã hóa sao cho hàng triệu thuê bao đều giải được mã. Nhưng một ứng dụng như vậy sẽ đặt ra hai vấn đề: mã một lần cho nhiều người (broadcast encryption) và ngăn chặn một người hay một nhóm người thuê bao cấu kết nhau để làm một bộ giải mã giả (tracing traitor). Hiện tại các thuật toán được sử dụng trong truyền hình thuê bao hầu hết đang còn ở thời nguyên thủy: độ an toàn buộc phải dựa trên tính bí mật của thuật toán. Nhưng cũng bởi vậy nên khi một nhóm phá mã có thể phá được nguyên lý bằng kỹ nghệ đảo ngược (reverse engineering) thì thị trường chợ đen có thể bán tràn lan các bộ giải mã giả mà không có cách gì truy lại được ai là thủ phạm.
Hai năm trở lại đây, một hướng nghiên cứu khá mới là về một kiểu mã tổng quát có thể bao quát hết các khái niệm về mã hóa công khai, mã hóa dựa trên danh tính, hay mã hóa một lần cho nhiều người. Đó là loại mã hàm (functional encryption) ở đó nó cho phép người lập mã định nghĩa một cơ chế giải mãđể đối với mỗi người nhận, tùy vào thuộc tính được gán có mà có thể truy cập sâu vào bản rõ tới đâu. Cho tới nay, đối với những cơ chế mã với các cấu trúc tương đối phức tạp, các phương án lập mã còn rất hạn chế về hiệu quả. Những kết quả trong tương lai chắc chắn sẽ mang tới những ứng dụng rất hiệu quả, đặc biệt là cho việc truy cập các cơ sở dữ liệu mã hóa lớn.
An toàn trước các tấn công vật lý
Mật mã thường phân tích tính an toàn dựa trên giả thuyết là khóa bí mật được bảo vệ tốt. Tuy nhiên, những tấn công vật lý đôi khi lại có thể tìm ra những thông tin về khóa (chẳng hạn bằng cách đo năng lượng tiêu thụ của máy giải mã trên các bản mã khác nhau). Do vậy, một trong các mục đích của mật mã là tìm cách hình thức hóa các khái niệm tấn công vật lý và tiếp sau đó là thiết kế các sơ đồ mã hóa mà tính an toàn có thể đảm bảo chỉ duy nhất dựa trên các giả thiết toán học. Hướng nghiên cứu an toàn trong mô hình khóa bị lộ (key leakage resilient cryptography) đang khá được quan tâm trong cộng đồng mật mã.
An toàn trước sự tấn công của máy tính lượng tử
Cuối cùng, chúng ta không thể bỏ qua sự hiện diện tiềm tàng của máy tính lượng tử, dù rằng cho tới nay các máy tính lượng tử mới chỉ phân tích được số 21 ra thừa số nguyên tố. Nhưng về mặt lý thuyết, nó có tiềm năng to lớn không thể không kể tới. Công trình của Shor năm 94 đã chỉ ra rằng bài toán phân tích số có thể giải được trong thời gian đa thức bởi máy tính lượng tử. Bài toán logarít rời rạc trong trường hữu hạn hay trên đường cong elliptic cũng có thể giải được trong thời gian đa thức bởi máy tính lượng tử. Điều đó có nghĩa là các hệ mã thông dụng hiện nay sẽ bị phá vỡ một khi máy tính lượng tử được thiết kế chạy được trên dữ liệu lớn. Để phòng ngừa trước điều đó (dù khả năng sớm xảy ra được đánh giá là rất nhỏ), nhiều nghiên cứu nhằm xây dựng các hệ mã có thể an toàn trước máy tính lượng tử được đề nghị. Hai hướng chính đang được quan tâm là các hệ mã dựa trên mã sửa sai (error correcting codes) và dựa trên lý thuyết lưới Euclid (lattice based cryptography), nơi sự hiện diện của máy tính lượng tử có vẻ như không đem lại hiệu quả đặc biệt.
Nguồn: Blog Khoa học máy tính, http://www.procul.org/blog/2011/04/12/m%E1%BA%ADt-ma-khoa-cong-khai-s%E1%BB%B1-phat-tri%E1%BB%83n-t%C6%B0%C6%A1ng-h%E1%BB%97-v%E1%BB%9Bi-cac-nganh-khoa-h%E1%BB%8Dc-khac/
Về tác giả:
I am a professor at XLIM, University of Limoges. From 2007 to 2015, I was an assistant professor atLAGA, University of Paris 8 and an associated member of the CryptoTeam at Ecole Normale Supérieure.
Before joining the University of Paris 8 as a faculty, I obtained a Ph.D degree in Computer Science at Ecole Normale Supérieure, under the supervision of David Pointcheval, then spent 15 months as postdoctoral researcher at University College London and 9 months as a research engineer at France Telecom R&D.
My research is focused on cryptography, in particular on provable security for cryptographic schemes, including protocols for Public-key encryption, Digital Signature, Broadcast Encryption and Traitor Tracing.
From <http://www.di.ens.fr/users/phan/>
https://scholar.google.com/citations?user=8n2aNu8AAAAJ&hl=fr
Mật mã khóa công khai còn làm thay đổi hoàn toàn phạm vi ứng dụng, cho phép mật mã được sử dụng rộng rãi trong thực tế: việc thiết lập kênh bí mật giữa một nghìn hay một triệu người thì cũng chỉ yêu cầu mỗi người cần giữ một khóa bí mật và công bố một khóa công khai, không cần phải thống nhất khóa chung nào. Áp dụng vào thực tế, một cửa hàng trực tuyến có thể thu hút hàng triệu khách hàng mà chỉ cần công khai duy nhất một khóa để ai mua hàng cũng chỉ cần dùng khóa công khai đó để gửi thông tin bảo mật về thẻ thanh toán.
Mật mã với lý thuyết độ phức tạp tính toán
Bên cạnh những ưu điểm mang tính bước ngoặt, mã hóa khóa công khai ẩn chứa một điều đáng lo ngại về tính an toàn: khi công bố khóa công khai tương ứng với khóa bí mật sẽ có thể dẫn tới việc khóa bí mật không còn … hoàn toàn bí mật! Điều lo ngại đó hoàn toàn có cơ sở bởi một kẻ tấn công có thể thử hết các trường hợp có thể để tìm ra khóa bí mật tương ứng với khóa công khai. Do đó, về nguyên tắc, kẻ tấn công có thể phá được sơ đồ mã hóa, tìm ra khóa bí mật mà không cần quan sát bất kể bản mã nào! Chính vì thế mà độ an toàn của mật mã khóa công khai sẽ không thể chỉ dựa trên sự giữ bí mật khóa nữa. Muốn đảm bảo sự an toàn, ta phải chứng tỏ làm sao, dù về nguyên tắc, kẻ tấn công có thể tìm ra khóa bí mật, nhưng thời gian để đạt được mục đích đó phải là rất lớn, cỡ hàng triệu năm trên một máy tính nhanh nhất chẳng hạn. Hay nói cách khác, độ phức tạp mà kẻ tấn công có thể tìm lại khóa bí mật là lớn phi thực tế.
Một cách rất tự nhiên, nghiên cứu độ an toàn của mật mã khóa công khai đã nằm gọn trong lý thuyết độ phức tạp tính toán (Computational Complexity). Trong lý thuyết độ phức tạp, ta không chỉ quan tâm xem một bài toán có thể giải được hay không, mà điều quan trọng nhất là nghiên cứu xem để giải bài toán đó thì độ khó khăn lớn đến đâu. Độ phức tạp được phân cấp theo các lớp, trong đó hai lớp quan trọng nhất là lớp P và lớp NP. Lớp P bao gồm những bài toán giải được trong thời gian đa thức, và nó được coi là lớp các bài toán có thể giải được trong thực tế. Chẳng hạn các bài toán sắp xếp dữ liệu theo một thứ tự định sẵn, tìm đường đi ngắn nhất giữa hai thành phố, biến đổi Fourrier rời rạc (đều có thể thực hiện được với cỡ nlog(n)bước cho n đối tượng, tức là bị chặn bên bởi một đa thức
) là những bài toán trong P. Lớp NP là lớp các bài toán có thể kiểm tra được lời giải đúng hay sai trong thời gian đa thức. Chẳng hạn trò chơi Sudoku thuộc lớp NP vì để giải nó có thể rất khó (thậm chí nó được chứng minh là một trong những bài toán thuộc lớp khó giải nhất trong NP) nhưng để kiểm tra một phương án có là lời giải không thì có lẽ chỉ cần đến một cậu bé biết phân biệt các con số với nhau và duyệt qua tất cả các ô. Rõ ràng chỉ khi lời giải có thể kiểm tra được trong thực tế thì bài toán mới được quan tâm, do vậy mà lớp NP có vai trò quan trọng. Câu hỏi trọng tâm của lý thuyết độ phức tạp là liệu các bài toán trong NP có thể có lời giải thực tế (tức trong thời gian đa thức) hay không, tức liệu P có bằng NP? Nếu P=NP thì điều đó đem lại một sự bất ngờ cho nhận thức của chúng ta: việc tìm ra lời giải cũng chỉ khó như việc kiểm tra lời giải. Điều khó tin đó làm người ta thường giả thuyết rằng P khác NP. Sự quan trọng của câu hỏi "P chọi NP?" là lý do để nó được viện Clay xếp vào một trong bảy bài toán thiên niên kỷ.
Quay trở lại với lý thuyết mật mã và xem xét nó dưới góc nhìn của lý thuyết độ phức tạp. Giờ đây ta có thể định nghĩa hệ mã bị phá nếu như có thuật toán phá mã (tìm lại khóa bí mật từ khóa công khai, hay đơn giản hơn, tìm lại bản rõ từ bản mã) trong thời gian đa thức. Vậy độ phức tạp của thuật toán phá mã liệu có thể đánh giá trong trường hợp chung? Câu trả lời là có và với mọi sơ đồ mã hóa khóa công khai đều có thuật toán phá mã thuộc lớp NP: do điều kiện cần của hệ mã là khi giải mã ta phải tìm lại đúng bản rõ, bài toán kiểm tra xem 1 khóa bí mật có tương ứng với 1 khóa công khai hay không là dễ dàng (chỉ cần chọn 1 bản rõ, mã nó dùng khóa công khai rồi giải mã nó với khóa bí mật xem có thu lại được đúng bản rõ hay không). Bài toán "P chọi NP" trở nên có tầm quan trọng sống còn tới lý thuyết mật mã: nếu hai lớp này tương đương thì toàn bộ lý thuyết nghiên cứu mật mã dưới góc nhìn độ phức tạp sẽ hoàn toàn sụp đổ vì việc phá mã, vốn thuộc NP, khi đó sẽ có thể thực hiện được trong thời gian đa thức. Và cũng do vậy, nghiên cứu độ phức tạp trong mật mã cần phải dựa trên giả thuyết "P khác NP".
Hàm cửa lật một chiều và sự phát triển của lý thuyết số tính toán
Khi tính an toàn chia tay với nghệ thuật che giấu bí mật để chuyển sang dựa trên lý thuyết độ phức tạp thì cũng là lúc mật mã bất ngờ tìm đến và làm những nghiên cứu trừu tượng trong lý thuyết số bỗng có những áp dụng đầy ý nghĩa trong thực tế. Nó cũng đưa lý thuyết số tính toán (computational number theory) trở thành một nhánh nghiên cứu quan trọng, nằm giữa vùng giao thoa của toán học và tin học.
Tựu chung yêu cầu để xây dựng mật mã khóa công khai là: hàm lập mã thì dễ (với khóa công khai), nhưng hàm giải mã thì khó khi không có khóa bí mật. Đó là các hàm cửa lật một chiều (trapdoor oneway functions): tính xuôi thì dễ, tính ngược lại phải khó, nhưng với cửa lật là khóa bí mật thì tính ngược, tức giải mã, cũng phải dễ. Yêu cầu trông có vẻ đơn giản đó nhưng thực tế là sau rất nhiều năm tìm kiếm vẫn chỉ có rất ít hàm có thể thỏa mãn. Các bài toán trong lớp NP-đầy đủ (là lớp các bài khó nhất trong NP, trò chơi Sudoku là một trong số đó; ta chỉ cần giải được 1 bài trong lớp NP-đầy đủ trong thời gian đa thức là đủ để chứng tỏ P=NP) rõ ràng là những ứng cử viên tiềm năng để xây dựng hàm cửa lật một chiều. Nhưng thực tế không hề dễ như ban đầu người ta hình dung, vì hai lý do: thứ nhất là bởi các bài toán NP chỉ quan tâm đến độ khó trong trường hợp xấu nhất, trong khi mã hóa cần mã an toàn cho mọi bản rõ nên cần ít nhất độ khó trong trường hợp trung bình; thứ hai là bởi tính chất cửa lật, bài toán cần khó nhưng với một số thông tin thì nó lại phải trở nên dễ giải, và chính yêu cầu về tính chất cửa lật đó đã khiến nhiều hệ mã dựa trên bài toán NP-đầy đủ (như hệ mã Chor-Rivest dựa trên bài toán xếp ba lô) bị phá vỡ.
Những hàm cửa lật thông dụng trong mật mã đã đến từ những bài toán rất cổ điển của lý thuyết số! Đó là bài toán phân tích số (cho một số N = pq là tích của hai số nguyên tố, phân tích nó ra thừa số nguyên tố p,q) và bài toán logarit rời rạc trong trường hữu hạn (cho một phần tử sinh g của một nhóm con của một trường hữu hạn, và một phần tử nhóm u=ga, bài toán là phải tìm lại a). Cả hai bài toán này, tuy về mặt toán học là giải được, nhưng cho đến nay không thể giải được trong thời gian đa thức. Bài toán phân tích số là nền tảng cho độ an toàn của hệ mã nổi tiếng RSA, và bài toán logarit rời rạc là cơ sở cho hệ mã Elgamal. Chính vì tính phổ dụng của hai hệ mã này mà một cách tất nhiên, bài toán phân tích số và bài toán logarit rời rạc trở thành đối tượng nghiên cứu rất được quan tâm. Việc nghiên cứu tính phức tạp của việc tìm ra lời giải cho các bài toán lý thuyết số đã đưa tới sự phát triển sâu rộng của lý thuyết số tính toán.
Sau nhiều công trình nghiên cứu quan trọng thì các bài toán bài toán phân tích số và bài toán logarit rời rạc tuy chưa giải được trong thời gian đa thức nhưng cũng không cần đến thời gian hàm mũ để giải nó, mà đã có các thuật toán dưới mũ (sub-exponention) như thuật toán dùng tính chỉ số (index calculus) và thuật toán dùng đường cong elliptic của Lenstra, được giới thiệu năm 1985. Dù cho những công trình này không làm các hệ mã sụp đổ, nhưng nó buộc phép xây dựng các hệ mã phải giảm hiệu quả vì phải dùng các khóa dài hơn để đảm bảo an toàn. Công trình của Lenstra cũng đánh dấu lần đầu tiên lý thuyết các đường cong elliptic được sử dụng vào mật mã, ở đây có vai trò như phá mã. Điều thú vị là ngay sau đó thì lý thuyết các đường cong elliptic đã được sử dụng cho việc lập mã. Koblitz và Miller cùng độc lập đề nghị thay thế việc sử dụng nhóm trong trường hữu hạn bằng nhóm các điểm trên đường cong elliptic vì ở đó, các thuật toán dưới mũ đã biết để giải quyết bài toán logarit rời rạc có vẻ như không thể áp dụng được. Từ đó việc sử dụng đường cong elliptic dẫn tới dẫn đến những hệ mã hiệu quả hơn (do không cần phải chọn khóa quá dài để chống lại các thuật toán dưới mũ).
Các kết quả lý thuyết sâu sắc trong lý thuyết số tiếp tục được áp dụng vào mật mã. Việc sử dụng đường cong elliptic dẫn tới yêu cầu cần phải lựa chọn những đường cong phù hợp. Tấn công MOV (đưa ra bởi Menezes, Okamoto, và Vanstone) chỉ ra không phải loại đường cong elliptic nào cũng có thể được sử dụng, bằng cách đưa việc giải quyết bài toán logarit rời rạc trên đường cong elliptic trở lại bài toán logarit rời rạc trên một trường hữu hạn mở rộng với độ mở rộng tùy thuộc vào loại đường cong. Do đó, các đường cong siêu lạ (supersingular) rất được ưa dùng ở giai đoạn đầu lại trở nên rất yếu vì ở đó độ mở rộng chỉ cao nhất là 6. Nét đặc biệt trong tấn công MOV là việc sử dụng phép ghép cặp (pairings) trên các đường cong elliptic, với những kết quả khá mới mẻ trong lý thuyết số. Không chỉ phục vụ cho việc phá mã, việc sử dụng phép ghép cặp sau đó đã trở nên cực kỳ hữu hiệu trong việc xây dựng mã. Khởi đầu là Joux đã dùng phép ghép cặp để xây dựng sơ đồ trao đổi khóa 3 bên, nhưng sự kiện nổi bật là việc dùng phép ghép cặp để giải quyết vấn đề mở về xây dựng mã hóa dựa trên danh tính-Identity based Encryption. Một cách giản đơn, mã hóa dựa trên danh tính cho phép ta sử dụng một khóa công khai duy nhất cho tất cả mọi người (từ đó giải quyết được vấn đề quản lý khóa của mã hóa khóa công khai, tuy vậy nhược điểm của nó là lại cần có thêm người quản trị đáng tin cậy để sinh ra khóa công khai chung và khóa bí mật cho từng người) và hàm lập mã dựa trên khóa công khai chung và danh tính của người nhận như địa chỉ email. Sau khi Sakai-Ohgishi-Kasahara và Boneh-Franklin đưa ra lời giải cho bài toán mã hóa dựa trên danh tính vào những năm 2000, phép ghép cặp đã được sử dụng hầu khắp trong mọi lĩnh vực của mật mã (mã hóa, chứa ký điện tử, sơ đồ định danh…) để nâng cao tính an toàn và hiệu quả và đôi khi là giải quyết những bài toán mở đã bế tắc trong thời gian dài (chẳng hạn như trong việc xây dựng chữ ký nhóm). Đến cách đây vài năm người ta đã tổ chức hẳn một hội nghị (Pairing-based Cryptograhy) dành cho các nghiên cứu liên quan đến các thuật toán xây dựng và phân tích các phép ghép cặp trên các đường cong elliptic hay hyperelliptic và các phương pháp mã và tấn công mã dựa trên phép ghép cặp.
Nhìn lại các phát triển của lý thuyết số tính toán, ta nhận thấy các phương pháp mới thường được đề nghị đầu tiên cho phá mã, nhưng rồi sau đó lại được sử dụng rất hiệu quả cho việc lập mã. Điều đó cũng phần nào chứng tỏ vai trò tương hỗ giữa cộng đồng những người thám mã và lập mã: trong rất nhiều trường hợp, chính những người say mê tìm cách phá tính an toàn của các hệ thống mật mã, sẽ là những người đem tới những phát kiến mới mẻ để xây dựng những hệ mã an toàn hơn.
Đảm bảo tính an toàn và sự phát triển của lý thuyết các thuật toán xác suất
Để có thể cài đặt được hệ mã RSA, một phần tất yếu là sự cần thiết phải tìm được những số nguyên tố lớn để có thể đảm bảo yêu cầu an toàn tối thiểu (khóa công khai chứa tích của hai số nguyên tố, và nếu một trong hai số nguyên tố là nhỏ thì bài toán phân tích số sẽ là dễ). Từ đó mà yêu cầu tìm các số nguyên tố lớn trở nên rất cần thiết.
Cho tới nay, các phương pháp tìm số nguyên tố lớn đều theo nguyên tắc hai bước: bước 1 là chọn một số tự nhiên đủ lớn và bước 2 là kiểm tra xem số được chọn có là số nguyên tố hay không. Do các số nguyên tố có cấu trúc rất bí hiểm và ta chưa hiểu được quy luật tường minh của chúng nên bước 1 chưa có cách nào khác là chọn một số ngẫu nhiên. Bước thứ 2 là bước kiểm tra tính nguyên tố. Chính những thuật toán kiểm tra tính nguyên tố, mà điển hình là những thuật toán được sử dụng rộng rãi của của Rabin và Solovay, Strassen, đã khởi đầu cho việc dùng xác suất để thiết kế các thuật toán (chú ý rằng trước đó khá lâu phương pháp xác suất đã được Erd ̋os sử dụng trong việc chỉ ra sự tồn tại của các đối tượng tổ hợp). Các thuật toán xác suất cho ta lời giải không hoàn toàn chính xác, nhưng độ không chính xác có thể làm nhỏ tới bao nhiêu cũng được, với điều kiện đầu vào của thuật toán có một nguồn ngẫu nhiên đủ lớn.
Việc phát triển các thuật toán xác suất dẫn tới sự cần thiết tìm nguồn ngẫu nhiên đủ lớn. Điều đó dẫn tới việc nghiên cứu những bài toán sau đó đã trở nên rất có ý nghĩa trong khoa học máy tính như bài toán trích nguồn ngẫu nhiên (randomness extractor, nhằm từ một nguồn không hoàn toàn ngẫu nhiên ta phải trích ra từ đó một lượng tin có độ ngẫu nhiên cao) và bài toán sinh dãy giả ngẫu nhiên (pseudo-random generator – từ một nguồn ngẫu nhiên nhỏ làm sao sinh ra một nguồn gần như ngẫu nhiên lớn hơn rất nhiều, nó không hoàn toàn ngẫu nhiên nhưng không có thuật toán nào trong thời gian đa thức có thể chỉ ra tính không ngẫu nhiên của nó)
Sau nhiều phát triển quan trọng của lý thuyết thuật toán xác suất, người ta quay lại hoài nghi "liệu độ ngẫu nhiên có thực sự mang tới sự hiệu quả?". Bài toán "BPP chọi P" (ở đó BPP là lớp các bài toán giải được theo nghĩa xác suất) là một bài toán mở trọng tâm của lý thuyết độ phức tạp. Cũng như bài toán "P vs. NP", nếu câu trả lời là hai lớp tương đương thì nó sẽ dẫn tới một khẳng định bất ngờ: mọi thuật toán xác suât đều có thể có thuật toán tất định tương đương. Bên cạnh câu hỏi tổng quan này, các nhà nghiên cứu quay lại với bài toán tìm số nguyên tố nhằm đưa ra một lời giải tất định cho nó. Công trình lý thuyết đột phá của Agrawal–Kayal–Saxena đưa ra năm 2000, đã chỉ ra một thuật toán tất định để kiểm thử tính nguyên tố trong thời gian đa thức, giải quyết trọng vẹn bước thứ 2 một cách tất định. Sự hấp dẫn của một lời giải hoàn chỉnh cho bài toán tất định tìm số nguyên tố chính là nguồn cảm hứng chung rất lớn của các nhà toán-tin học và nó được chọn là bài toán khởi đầu cho một kế hoạch đầy tham vọng nhằm thay đổi tư duy trong hợp tác nghiên cứu khoa học: hợp tác mở thông qua đóng góp, trao đổi mở trên mạng. Với sự nhiệt tình của Timothy Gower, Terence Tao (cả hai đều đạt giải thưởng Fields), đã có rất nhiều nhà khoa học tham gia vào dự án mở Polymath để cùng trao đổi nhằm tìm kiếm lời giải cho bài toán này. Tuy chưa thể đưa ra lời giải toàn phần, họ đã có một số kết quả dẫn tới một bài báo khoa học dưới tên tác giả Polymath. Rất có thể đây sẽ là một hình thức cộng tác khoa học xuyên biên giới có sức mạnh tổng hợp lớn trong tương lai.
Chứng minh tương tác không để lộ tri thức
Trong mật mã, mọi trao đổi thông tin đều giả thiết có sự hiện diện của kẻ xấu. Mục đích của ta là vừa có thể thuyết phục người đối thoại về tính đúng đắn của một mệnh đề nào đó, lại vừa không cần tin tưởng anh ta, và không muốn sau khi trao đổi anh ta cũng có khả năng chứng minh mệnh đề đó với người khác. Chẳng hạn, một thành viên của một câu lạc bộ bí mật muốn chứng minh danh tính của mình cho người gác cổng, nhưng lại không muốn nói mật khẩu của mình vì sợ chính người gác cổng sẽ bán nó cho kẻ khác. Trong ngữ cảnh đó, một trong những khái niệm thú vị nhất của khoa học máy tính đã được đề nghị: chứng minh tương tác (interactive proofs). Khái niệm này được đưa ra bởi Babai, Goldwasser, Micali, Moran và Rackof vào đầu những năm 80 và nhờ đó họ đã được trao giải Godel đầu tiên trong lịch sử (giải thưởng hàng năm cho công trình lý thuyết xuất sắc nhất trong khoa học máy tính).
Dưới góc độ toán học, ta thường quan niệm chứng minh là một dãy các lập luận lô gíc có thể trình bày tường minh trên giấy. Liệu chăng yếu tố đối thoại, tương tác giữa người chứng minh và người kiểm tra có mang đến điều mới mẻ? Để trả lời câu hỏi đó, trước hết khái niệm về một chứng minh sẽ phải thay đổi. Goldreich thường trích lời thầy giáo Simon của mình khi giảng về các chứng minh tương tác:
"Chứng minh là bất kể cách gì có thể thuyết phục được tôi" (" A proof is whatever convinces me").
Theo nghĩa đó, một chứng minh tương tác là một chuỗi các chất vấn, cho tới khi người hỏi bị thuyết phục hoàn toàn bởi người chứng minh. Một câu chuyện vui kể rằng, rằng, một cậu bé cho rằng mình có câu thần chú để mở vách ngăn giữa hai nhánh của một hang động. Tất nhiên cậu ta không muốn lộ câu thần chú của mình, nhưng lại muốn chứng minh khả năng đó. Trò chơi đuổi bắt có thể là một chứng minh tương tác hiệu quả: chú bé chạy vào 1 trong hai ngã, một người đuổi chon một hướng nhằm dồn chú vào ngách ngăn nhưng cuối cùng không lần nào bắt được chú. Nếu đuổi một lần ta có thể cho là chú đã chọn ngã khác, nhưng lặp đi lặp lại trò chơi tới 100 lần mà không lần nào đuổi được thì có lẽ ta bị thuyết phục là chú đúng là có câu thần chú (ví dụ lấy từ Wikipedia). Các chứng minh tương tác hầu hết dựa trên một tinh thần như thế.
Có những bài toán mà người ta chưa biết cách nào chứng minh trong thời gian đa thức, nhưng lại chứng minh được thông qua tương tác, chẳng hạn bài toán chứng minh hai đồ thị không đồng cấu với nhau. Hơn thế nữa, trong nhiều bài toán, người chứng minh có thể không cần để lộ ra bất kể tri thức nào anh ta có về cái chứng minh đó (zero-knowledge proofs).
Kết quả rất đẹp của Goldreich, Micali và Wigderson cho ta kết quả bất ngờ: dựa trên giả thuyết tồn tại các hàm một chiều, tất cả những gì ta có thể chứng minh trong thực tế (theo nghĩa trong thời gian đa thức), đều có thể chứng minh mà không để lộ tri thức! Bài toán chứng minh danh tính phía trên là một trong số đó.
Các chứng minh không để lộ tri thức đặc biệt quan trọng trong mật mã, là thành phần cơ bản trong việc xây dựng các sơ đồ mã hóa, chữ ký điện tử. Chứng minh không để lộ tri thức cũng là thành phần không thể thiếu trong một sơ đồ bầu cử điện tử, cho phép mỗi cử tri kiểm tra được lá phiếu của mình đã được tính đến mà việc kiểm phiếu lại không cần phải công bố nội dung từng lá phiếu, đảm bảo quyền lựa chọn bí mật của cử tri.
Ở một khía cạnh khác, chứng minh tương tác cũng là phần hồn của nhánh khoa học «chứng minh tính bảo mật » (provable security), nơi ta cố gắng chứng minh tính an toàn của hệ thống trong một thế giới tương tác rất phức tạp (với sự hiện diện của kẻ tấn công luôn muốn lừa hệ thống thông qua quan sát, nghe trộm, đóng giả người tốt để tương tác với hệ thống) dựa trên những giả thuyết tĩnh, giản đơn của toán học.
Một số hướng đi tương lai của mật mã
Bảo mật trong điện toán đám mây (cloud computing)
Điện toán đám mây cho phép ta lưu trữ những khối lượng thông tin khổng lồ trên mạng và thực hiện các thao tác trên nó một cách dễ dàng. Nó có thể giúp ta giải quyết những bài toán lớn mà trước đây khó có thể giải quyết trên một mạng lưới các máy tính mang tính chất cục bộ. Tuy nhiên, điều đó mang tới một thách thức vô cùng lớn về tính bảo mật. Có hai điều có vẻ như mâu thuẫn nhau: lưu trữ dữ liệu lớn trên các hệ thống xa lạ rõ ràng rất dễ bị đánh cắp thông tin, nhưng nếu ta mã hóa toàn bộ dữ liệu thì sẽ khó có thể tận dụng sức mạnh của tính toán đám mây để thao tác dữ liệu đó.
Nhưng gần đây, vấn đề tưởng khó có thể giải quyết này đã có chút tia hy vọng, với công trình của Gentry năm 2009 về mật mã đẳng cấu theo cả phép nhân và phép cộng (fully homomorphic encryption). Hệ mã này cho phép, từ hai bản mã của hai bản rõ m và m', ta có thể tính được bản mã nhân của mm' và bản mã cộng của m+m'. Vấn đề với bề ngoài đơn giản nhưng chứa đựng không ít nghịch lý trong đó: hệ mã vừa phải đảm bảo an toàn cho dữ liệu (không thể biết thông tin về bản rõ m, m'), mà lại vẫn thao tác được trên dữ liệu đó. Và cũng với bề ngoài giản đơn như vậy, nó lại mang đến một ý nghĩa rất bao quát: do mọi tính toán đều có thể qui về các phép toán cơ bản là cộng và nhân, một hệ mã như thế sẽ cho ta khả năng làm mọi tính toán trên dự liệu được mã hóa! Điều đó có nghĩa ta có thể để tất cả dữ liệu bảo mật trên những máy mạng không an toàn mà vẫn có thể tận dụng được sức tính toán lớn của điện toán đám mây để thao tác trên dữ liệu được mã hóa. Tuy nhiên, hiện tại, hệ mã Gentry và một số hệ mã cải tiến còn có hiệu quả vô cùng thấp, hầu như chỉ mang tính lý thuyết. Một hệ mã hiệu quả sẽ là lời giải tuyệt vời cho bài toán an toàn thông tin trong điện toán đám mây.
Mở rộng mô hình mã hóa: cho đối tượng nhóm và cho việc giải mã bộ phận
Mã hóa thường cho ta thiết lập kênh trao đổi thông tin giữa một người với một người. Tuy nhiên, những ứng dụng thực tế đòi hỏi khả năng ta mã một lần sao cho nhiều người cùng có thể giải mã. Một ví dụ điển hình là việc phát chương trình truyền hình mã hóa sao cho hàng triệu thuê bao đều giải được mã. Nhưng một ứng dụng như vậy sẽ đặt ra hai vấn đề: mã một lần cho nhiều người (broadcast encryption) và ngăn chặn một người hay một nhóm người thuê bao cấu kết nhau để làm một bộ giải mã giả (tracing traitor). Hiện tại các thuật toán được sử dụng trong truyền hình thuê bao hầu hết đang còn ở thời nguyên thủy: độ an toàn buộc phải dựa trên tính bí mật của thuật toán. Nhưng cũng bởi vậy nên khi một nhóm phá mã có thể phá được nguyên lý bằng kỹ nghệ đảo ngược (reverse engineering) thì thị trường chợ đen có thể bán tràn lan các bộ giải mã giả mà không có cách gì truy lại được ai là thủ phạm.
Hai năm trở lại đây, một hướng nghiên cứu khá mới là về một kiểu mã tổng quát có thể bao quát hết các khái niệm về mã hóa công khai, mã hóa dựa trên danh tính, hay mã hóa một lần cho nhiều người. Đó là loại mã hàm (functional encryption) ở đó nó cho phép người lập mã định nghĩa một cơ chế giải mãđể đối với mỗi người nhận, tùy vào thuộc tính được gán có mà có thể truy cập sâu vào bản rõ tới đâu. Cho tới nay, đối với những cơ chế mã với các cấu trúc tương đối phức tạp, các phương án lập mã còn rất hạn chế về hiệu quả. Những kết quả trong tương lai chắc chắn sẽ mang tới những ứng dụng rất hiệu quả, đặc biệt là cho việc truy cập các cơ sở dữ liệu mã hóa lớn.
An toàn trước các tấn công vật lý
Mật mã thường phân tích tính an toàn dựa trên giả thuyết là khóa bí mật được bảo vệ tốt. Tuy nhiên, những tấn công vật lý đôi khi lại có thể tìm ra những thông tin về khóa (chẳng hạn bằng cách đo năng lượng tiêu thụ của máy giải mã trên các bản mã khác nhau). Do vậy, một trong các mục đích của mật mã là tìm cách hình thức hóa các khái niệm tấn công vật lý và tiếp sau đó là thiết kế các sơ đồ mã hóa mà tính an toàn có thể đảm bảo chỉ duy nhất dựa trên các giả thiết toán học. Hướng nghiên cứu an toàn trong mô hình khóa bị lộ (key leakage resilient cryptography) đang khá được quan tâm trong cộng đồng mật mã.
An toàn trước sự tấn công của máy tính lượng tử
Cuối cùng, chúng ta không thể bỏ qua sự hiện diện tiềm tàng của máy tính lượng tử, dù rằng cho tới nay các máy tính lượng tử mới chỉ phân tích được số 21 ra thừa số nguyên tố. Nhưng về mặt lý thuyết, nó có tiềm năng to lớn không thể không kể tới. Công trình của Shor năm 94 đã chỉ ra rằng bài toán phân tích số có thể giải được trong thời gian đa thức bởi máy tính lượng tử. Bài toán logarít rời rạc trong trường hữu hạn hay trên đường cong elliptic cũng có thể giải được trong thời gian đa thức bởi máy tính lượng tử. Điều đó có nghĩa là các hệ mã thông dụng hiện nay sẽ bị phá vỡ một khi máy tính lượng tử được thiết kế chạy được trên dữ liệu lớn. Để phòng ngừa trước điều đó (dù khả năng sớm xảy ra được đánh giá là rất nhỏ), nhiều nghiên cứu nhằm xây dựng các hệ mã có thể an toàn trước máy tính lượng tử được đề nghị. Hai hướng chính đang được quan tâm là các hệ mã dựa trên mã sửa sai (error correcting codes) và dựa trên lý thuyết lưới Euclid (lattice based cryptography), nơi sự hiện diện của máy tính lượng tử có vẻ như không đem lại hiệu quả đặc biệt.
Nguồn: Blog Khoa học máy tính, http://www.procul.org/blog/2011/04/12/m%E1%BA%ADt-ma-khoa-cong-khai-s%E1%BB%B1-phat-tri%E1%BB%83n-t%C6%B0%C6%A1ng-h%E1%BB%97-v%E1%BB%9Bi-cac-nganh-khoa-h%E1%BB%8Dc-khac/
Về tác giả:
I am a professor at XLIM, University of Limoges. From 2007 to 2015, I was an assistant professor atLAGA, University of Paris 8 and an associated member of the CryptoTeam at Ecole Normale Supérieure.
Before joining the University of Paris 8 as a faculty, I obtained a Ph.D degree in Computer Science at Ecole Normale Supérieure, under the supervision of David Pointcheval, then spent 15 months as postdoctoral researcher at University College London and 9 months as a research engineer at France Telecom R&D.
My research is focused on cryptography, in particular on provable security for cryptographic schemes, including protocols for Public-key encryption, Digital Signature, Broadcast Encryption and Traitor Tracing.
From <http://www.di.ens.fr/users/phan/>
https://scholar.google.com/citations?user=8n2aNu8AAAAJ&hl=fr
Không có nhận xét nào:
Đăng nhận xét