Wednesday, 26/06/2019
News
Home » Kỹ Thuật » Mật mã khóa công khai: Hành trình 35 năm (P1)

Mật mã khóa công khai: Hành trình 35 năm (P1)

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.

Mật mã khóa công khai

Mật mã khóa công khai 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. Quy 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

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 mã khóa công khai

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 p(n)=n^2) 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.

Bài viết được đăng trên Blog Khoa học Máy tính vào năm 2011.

1 Star2 Stars3 Stars4 Stars5 Stars6 Stars7 Stars8 Stars9 Stars10 Stars (No Ratings Yet)
Loading...

Leave a Reply

Your email address will not be published. Required fields are marked *

*

:cuoi: :hix: :hihihi: :kiss: :sexy: :dotay: :ngacnhien: :oh: :love: more »