Bài toán P chọi NP và sự an toàn của toàn bộ hệ thống

Sự ra đời của máy tính lượng tử liệu sẽ giết chết Bitcoin? Và hôm nay nó đã ra đời. Thậm chí IBM còn thương mại hóa nó với cái tên Q System One.

(bài này không liên quan đến thị trường, có đăng tại diễn đàn TradingIG (https://bit.ly/2FwupCi) và blog cá nhân)

Bài này mình trình bày vài hiểu biết liên quan đến toán học trong việc giải quyết bài toán P chọi NP và tầm quan trọng của bài toán này trong mật mã học hiện đại cũng như toàn bộ ngành khoa học máy tính nói chung, với sự tham khảo nhiều định nghĩa và ví dụ của giáo sư Ngô Quang Hưng và các anh em bạn bè IT (vì mình vốn không phải dân lập trình)

Bắt đầu bằng thuật toán tạo số ngẫu nhiên

Nếu bạn là dân IT chắc sẽ biết đến bộ sách đồ sộ “The Art of Computer Programming” của Knuth. Ông dành hẳn cả một chương lớn để bàn về việc làm thế nào để tạo ra được một số ngẫu nhiên. Thực ra vấn đề không chỉ tồn tại trong toán học mà nó cũng thể hiện mối liên hệ mật thiết với triết học trong câu hỏi đến nay vẫn chưa ai dám trả lời quả quyết: “Trên đời có thứ gì là ngẫu nhiên không?”. Chính quy luật nguyên nhân-hệ quả của triết học, đã đặt ra cho toán học một ranh giới chưa thể bước qua, người ta chỉ có thể chấp nhận nó với tên gọi “thuật toán tất định”.

Thuật toán tất định ràng buộc rằng: đầu ra (output) hoàn toàn có thể dự đoán được thông qua đầu vào (input). Nghĩa là chẳng có gì là ngẫu nhiên cả. Cái mà chúng ta nghĩ rằng có một con số ngẫu nhiên tạo ra chẳng qua chỉ vì chúng ta “muốn như thế”. Vì thực tế, nó đã được biết trước bởi input và thuật toán mất rồi. Nhân đây, cũng nói thêm về hai “mẹo” tạo số ngẫu nhiên mà chúng ta có được cho đến nay:

  • dựa vào “số ngẫu nhiên” trước đó và xem nó như một input để sinh ra những con “số ngẫu nhiên” sau này
  • sử dụng một phần cứng đặt biệt để tạo số ngẫu nhiên (seed).

Đọc vào chắc bạn sẽ hình dung đến cấu trúc của blockchain, cấu trúc dữ liệu Linked List. Bản chất là các khối được liên kết với nhau thông qua hash.

KPI quan trọng nhất cho công việc tạo ra một số ngẫu nhiên là làm cho nó “không thể nào dự đoán được”. Người ta cố gắng thêm “muối”, thêm “đường” ùm bà lằng vào để không ai có đủ khả năng dò ra nỗi input của bài toán. Nhưng cuối cùng phải thừa nhận rằng, chỉ cần biết được thuật toán, thì gần như biết được tất cả. Nhưng nói vậy bằng thừa, vấn đề hóc búa đáng quan tâm hơn là: “Liệu có tồn tại một sức mạnh tính toán nào đủ khả năng giải ngược bài toán từ output ra input trong thời gian mà chúng ta có thể chấp nhận được hay không?”.

Thế là sau nhiều thế kỉ tìm kiếm, người ta bắt đầu để ý tới khái niệm “máy tính lượng tử”, và kì vọng sẽ mở ra những chân trời mới cho toán học và sự phát triển của nhân loại.

Cho đến bài toán P chọi NP

Khi đối diện với một bài toán bất kỳ trong mọi lĩnh vực, ở đây xét riêng về toán học, người ta không chỉ quan tâm bài toán ấy giải được hay không giải được, mà còn quan tâm mất bao lâu nếu giải được, nghĩa là quan tâm đến “độ khó” của bài toán. Giả sử, private key của ví bitcoin là một số biểu diễn bởi 256 bit. Vậy thì về lý thuyết thì ta sẽ có 2^256 private key. Nếu bạn là hacker và chơi trò “vét cạn” thì số lần thử chọn của bạn có thể lên đến 10^77 lần. Con số này gần với số ngôi sao chúng ta quan sát được (quá khủng khiếp và phi thực tế!).

Diễn giải theo ngôn ngữ toán học, độ phức tạp được phân theo lớp. Trong đó, 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ế, mà trên đây mình dùng chữ trong thời gian “chấp nhận” được. Còn 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.

Ví dụ, trò chơi sodoku là một bài toán thuộc lớp NP. Dưới góc độ lập trình, nó vô cùng khó khăn để giải quyết, nhưng để kiểm tra xem bảng sokudo đó có lời giải hay không thì chỉ cần một em bé lớp 2 phân biệt được các con số từ 0 đến 9.

Câu hỏi đặt ra là: P = NP hay P khác NP. Nếu P = NP thì có nghĩa là bài toán nào có khả năng kiểm tra lời giải cũng có khả năng tìm ra lời giải. Tức là mọi bài toán thực tế (là bài toán mà ta có thể kiểm tra xem một lời giải là đúng hay sai) đều giải được dễ dàng. Nếu hôm nào đó, một “siêu anh hùng” xuất hiện và chứng minh P = NP thì không chỉ nhận được 1 triệu đô từ viện Clay (giải thưởng hiện tại) mà còn thay đổi toàn bộ nhận thức của nhân loại về bảo mật. Giao thức bảo mật với Public key hoàn toàn vô nghĩa và nhảm nhí. Về phương diện nào đó, siêu anh hùng giữ bí mật của riêng mình thì có thể “tạo ra bitcoin” muốn bao nhiêu cũng được. Điều đó không đáng sợ bằng, tất cả các giao dịch Internet đặt trong tình trạng bất ổn vì hoàn toàn có thể “cướp” được dễ dàng.

“Máy tính lượng tử” đã xuất hiện?

Mình bỏ qua cách mà truyền thông tung hô, vì nó chỉ mang ý nghĩa marketing chứ không giải quyết nỗi lo sợ của chúng ta. Nếu giả sử tồn tại một mô hình máy tính hoàn toán khác với mô hình máy tính hiện tại và đủ khả năng giải quyết các bài toán NP trong thời gian đa thức, thì có hai trường hợp xảy ra.

  • Người ta bí mật kiểm soát nó và kiểm soát luôn cả khái niệm “cái gì mới thật sự là bí mật” trên internet.
  • Người ta công khai nó và toàn bộ ngành mật mã học phải định nghĩa lại rất nhiều thứ. Blockchain với cái xương sống là hàm băm sẽ phải chuyển hóa thành “một cái gì đó” mới mẻ hơn.

Bài viết này không phải phim khoa học viễn tương, mọi thứ đang phát triển quá nhanh và cứ như đang rành rành ngay trước mắt chúng ta.

5 1 vote
Article Rating
Subscribe
Notify of
guest
0 Comments
Inline Feedbacks
View all comments