Làm thế nào để mã hóa thông tin là câu hỏi đã trở thành trọng tâm của mật mã học trong hàng ngàn năm và nằm ở trung tâm của những nỗ lực bảo mật thông tin cá nhân trên internet. Mã hóa đơn giản là biến những thông tin cần bảo vệ thành những ký tự mà người khác không thể hiểu được, kiểu như “@#$%*% ...”, nhưng vẫn đảm bảo giải mã được khi chúng ta xem thông tin đó.

Trong một bài báo mới, các nhà nghiên cứu của Cornell Tech đã xác định một vấn đề quan trọng là liệu tất cả mã hóa có thể bị phá vỡ hay không và bên cạnh đó là nghiên cứu một khái niệm toán học có liên quan tới nó nhằm xác định và đo lường tính ngẫu nhiên.

Trong nhiều thiên niên kỷ, mật mã được cho là có một chu kỳ tồn tại nhất định: Ai đó phát minh ra một mã, mã này có hiệu lực cho đến khi cuối cùng có người phá vỡ nó và mã đó trở nên không hiệu quả. Vào những năm 1970, các nhà nghiên cứu tìm kiếm một lý thuyết tốt hơn về mật mã học đã đưa ra khái niệm về hàm một chiều – dễ dàng giải quyết nó theo một hướng và đơn giản là không thể giải quyết theo hướng khác. Ví dụ, thật dễ dàng để thắp sáng một que diêm, nhưng không thể đưa một que diêm đang cháy về trạng thái lúc nó chưa cháy mà không sắp xếp lại các nguyên tử - một nhiệm vụ vô cùng khó khăn. Ý tưởng là, nếu chúng ta có chức năng một chiều như vậy, có lẽ đó là điểm khởi đầu rất tốt để hiểu về mật mã học. Mã hóa tin nhắn rất dễ dàng, và nếu bạn có chìa khóa, bạn cũng có thể giải mã nó. Nhưng ai đó không biết khóa thì phải làm điều tương tự như khôi phục lại một que diêm đang cháy.

Nhưng các nhà nghiên cứu đã không thể chứng minh sự tồn tại của chức năng một chiều. Ứng cử viên nổi tiếng nhất - cũng là cơ sở của các chương trình mã hóa được sử dụng phổ biến nhất trên internet – phân tích số nguyên thành số nguyên tố. Thật dễ dàng để nhân hai số nguyên tố ngẫu nhiên - ví dụ 23 và 47 - nhưng khó hơn đáng kể để tìm lại hai nhân tử ban đầu đó nếu chỉ đưa ra tích của chúng, là 1081.

Câu hỏi trung tâm cần giải quyết là: Có tồn tại thuật toán để giải quyết ví dụ trên cho những số nguyên lớn không? Có vấn đề tự nhiên nào đặc trưng cho sự tồn tại của các chức năng một chiều không? Nếu có, đó sẽ là chìa khóa của tất cả các vấn đề và nếu bạn có cách giải quyết vấn đề đó, bạn có thể phá vỡ tất cả các chức năng một chiều có mục đích. Và nếu bạn không biết cách giải quyết vấn đề đó, bạn thực sự có thể nhận được mật mã an toàn.

Trong khi đó, các nhà toán học trong những năm 1960 đã xác định được cái gọi là Độ phức tạp Kolmogorov, trong đó đề cập đến việc định lượng lượng ngẫu nhiên hoặc mô hình của một chuỗi số. Độ phức tạp Kolmogorov của một chuỗi số được định nghĩa là độ dài của chương trình máy tính ngắn nhất có thể tạo ra chuỗi. Đối với một số chuỗi, chẳng hạn như 121212121212121212121212121212, có một chương trình ngắn tạo ra nó - thay thế luân phiên số 1 và 2. Nhưng đối với các chuỗi số phức tạp hơn và rõ ràng hơn, chẳng hạn như 37539017332840393452954329, có thể không tồn tại một chương trình ngắn hơn độ dài của chính chuỗi đó.

Vấn đề đã được các nhà toán học và các nhà khoa học máy tính quan tâm từ lâu, bao gồm Juris Hartmanis, giáo sư danh dự của khoa học máy tính và kỹ thuật. Bởi vì chương trình máy tính cố gắng tạo ra con số có thể mất hàng triệu hoặc thậm chí hàng tỷ năm để giải mã, các nhà nghiên cứu ở Liên Xô trong những năm 1960, cũng như Hartmanis và những người khác trong những năm 1980, đã phát triển Độ phức tạp Kolmogorov giới hạn thời gian - độ dài của chương trình ngắn nhất có thể xuất ra một chuỗi số trong một khoảng thời gian nhất định.

Các nhà nghiên cứu của Cornell Tech đã chỉ ra rằng nếu tính toán Độ phức tạp Kolmogorov giới hạn thời gian là khó khăn, thì chức năng một chiều tồn tại. Mặc dù phát hiện của họ chỉ là lý thuyết, nhưng nó có ý nghĩa tiềm năng đối với mật mã học, bao gồm cả bảo mật internet. Các nhà nghiên cứu cho rằng, nếu bạn có thể đưa ra một thuật toán để giải quyết vấn đề phức tạp Kolmogorov bị ràng buộc theo thời gian, thì bạn có thể phá vỡ tất cả tiền điện tử, tất cả các sơ đồ mã hóa, tất cả chữ ký số. Tuy nhiên, nếu không có thuật toán hiệu quả tồn tại để giải quyết vấn đề này, bạn có thể có chức năng một chiều, và do đó bạn có thể nhận được mã hóa và chữ ký số thực sự an toàn. Chi tiết tham khảo tại:

Cornell University. "Randomness theory could hold key to internet security." ScienceDaily. <www.sciencedaily.com/releases/2020/07/200727194721.htm>.

(Sưu tầm)
VIỆN IMC
Tòa nhà IMC Tower, Số 176 Trường Chinh, Phường Khương
Thượng, Quận Đống Đa, Thành phố Hà Nội, Việt Nam
Tel/Fax : (+84) 24 3566 6232 / 24 3566 6234
Email: contact@imc.org.vn   Website: http://imc.org.vn