Thuật toán mật mã nổi tiếng được nâng cấp | Tạp chí Quanta

Trong cuộc sống ngày càng số hóa của chúng ta, bảo mật phụ thuộc vào mật mã. Gửi tin nhắn riêng tư hoặc thanh toán hóa đơn trực tuyến và bạn đang dựa vào các thuật toán được thiết kế để giữ bí mật dữ liệu của mình. Đương nhiên, một số người muốn khám phá những bí mật đó — vì vậy các nhà nghiên cứu nỗ lực kiểm tra sức mạnh của những hệ thống này để đảm bảo chúng sẽ không bị sụp đổ dưới bàn tay của một kẻ tấn công thông minh.

Một công cụ quan trọng trong công việc này là thuật toán LLL, được đặt theo tên của các nhà nghiên cứu xuất bản nó năm 1982 - Arjen Lenstra, Hendrik Lenstra Jr. và László Lovász. LLL, cùng với nhiều hậu duệ của nó, có thể phá vỡ các sơ đồ mật mã trong một số trường hợp; nghiên cứu cách chúng hoạt động giúp các nhà nghiên cứu thiết kế các hệ thống ít bị tấn công hơn. Và tài năng của thuật toán còn vượt xa cả mật mã: Nó còn là một công cụ hữu ích trong các lĩnh vực toán học tiên tiến như lý thuyết số tính toán.

Trong nhiều năm, các nhà nghiên cứu đã mài giũa các biến thể của LLL để làm cho phương pháp này trở nên thực tế hơn - nhưng chỉ ở một mức độ nhất định. Giờ đây, một cặp nhà mật mã đã xây dựng một thuật toán kiểu LLL mới với hiệu suất tăng đáng kể. Kỹ thuật mới đã giành được giải thưởng Giải thưởng Giấy xuất sắc nhất tại Hội nghị mật mã quốc tế 2023, mở rộng phạm vi các tình huống trong đó các nhà khoa học máy tính và toán học có thể sử dụng các phương pháp tiếp cận giống LLL một cách khả thi.

“Nó thực sự rất thú vị,” nói Chris Peikert, một nhà mật mã học tại Đại học Michigan, người không tham gia vào bài báo. Ông cho biết công cụ này đã là trọng tâm nghiên cứu trong nhiều thập kỷ. “Thật tuyệt khi một mục tiêu đã được thực hiện trong một thời gian dài… cho thấy rằng vẫn còn những điều bất ngờ được tìm thấy.”

Các thuật toán loại LLL hoạt động trong thế giới mạng: tập hợp vô hạn các điểm cách đều nhau. Một cách để hình dung điều này, hãy tưởng tượng bạn đang lát sàn nhà. Bạn có thể phủ nó bằng những viên gạch hình vuông, và các góc của những viên gạch đó sẽ tạo thành một lưới. Ngoài ra, bạn có thể chọn một hình dạng ô xếp khác - chẳng hạn như hình bình hành dài - để tạo một mạng lưới khác.

Một mạng có thể được mô tả bằng cách sử dụng “cơ sở” của nó. Đây là một tập hợp các vectơ (về cơ bản là danh sách các số) mà bạn có thể kết hợp theo nhiều cách khác nhau để có được mọi điểm trong mạng. Hãy tưởng tượng một mạng có cơ sở gồm hai vectơ: [3, 2] và [1, 4]. Mạng chỉ là tất cả các điểm bạn có thể đạt được bằng cách cộng và trừ các bản sao của các vectơ đó.

Cặp vectơ đó không phải là cơ sở duy nhất của mạng. Mọi mạng có ít nhất hai chiều đều có vô số cơ sở có thể. Nhưng không phải tất cả các cơ sở đều được tạo ra như nhau. Một cơ sở có các vectơ ngắn hơn và gần góc vuông với nhau hơn thường dễ làm việc hơn và hữu ích hơn trong việc giải một số vấn đề tính toán, vì vậy các nhà nghiên cứu gọi những cơ sở đó là “tốt”. Một ví dụ về điều này là cặp vectơ màu xanh lam trong hình bên dưới. Các cơ sở bao gồm các vectơ dài hơn và ít trực giao hơn - như các vectơ màu đỏ - có thể bị coi là "xấu".

Đây là công việc của LLL: Cung cấp cho nó (hoặc những người anh em của nó) một nền tảng của mạng đa chiều, và nó sẽ tạo ra một mạng tốt hơn. Quá trình này được gọi là giảm cơ sở mạng tinh thể.

Tất cả những điều này có liên quan gì đến mật mã? Hóa ra, trong một số trường hợp, nhiệm vụ phá vỡ một hệ thống mật mã có thể được coi là một vấn đề khác: tìm một vectơ tương đối ngắn trong một mạng. Và đôi khi, vectơ đó có thể được lấy ra từ cơ sở rút gọn được tạo bởi thuật toán kiểu LLL. Chiến lược này đã giúp các nhà nghiên cứu lật đổ các hệ thống mà nhìn bề ngoài dường như ít liên quan đến mạng tinh thể.

Theo nghĩa lý thuyết, thuật toán LLL ban đầu chạy nhanh: Thời gian chạy không tăng theo cấp số nhân với kích thước của đầu vào - nghĩa là kích thước của mạng và kích thước (tính bằng bit) của các số trong các vectơ cơ sở. Nhưng nó tăng lên như một hàm đa thức và “nếu bạn thực sự muốn làm điều đó, thì thời gian đa thức không phải lúc nào cũng khả thi”, ông nói. Léo Ducas, một nhà mật mã học tại viện nghiên cứu quốc gia CWI ở Hà Lan.

Trong thực tế, điều này có nghĩa là thuật toán LLL ban đầu không thể xử lý các đầu vào quá lớn. “Các nhà toán học và nhà mật mã muốn có khả năng làm được nhiều hơn thế,” nói Keegan Ryan, một nghiên cứu sinh tiến sĩ tại Đại học California, San Diego. Các nhà nghiên cứu đã làm việc để tối ưu hóa các thuật toán kiểu LLL để đáp ứng đầu vào lớn hơn, thường đạt được hiệu suất tốt. Tuy nhiên, một số nhiệm vụ vẫn nằm ngoài tầm với.

Bài báo mới, được viết bởi Ryan và cố vấn của ông, Nadia Heninger, kết hợp nhiều chiến lược để nâng cao hiệu quả của thuật toán kiểu LLL. Thứ nhất, kỹ thuật này sử dụng cấu trúc đệ quy để chia nhiệm vụ thành các phần nhỏ hơn. Mặt khác, thuật toán quản lý cẩn thận độ chính xác của các con số liên quan, tìm sự cân bằng giữa tốc độ và kết quả chính xác. Công trình mới giúp các nhà nghiên cứu có thể giảm cơ sở của các mạng có hàng nghìn chiều.

Công việc trước đây đã theo một cách tiếp cận tương tự: A giấy 2021 cũng kết hợp đệ quy và quản lý chính xác để thực hiện nhanh chóng các mạng lớn, nhưng nó chỉ hoạt động với các loại mạng cụ thể chứ không phải tất cả các mạng quan trọng trong mật mã. Thuật toán mới hoạt động tốt trên phạm vi rộng hơn nhiều. “Tôi thực sự vui mừng vì có ai đó đã làm điều đó,” nói Thomas Espitau, nhà nghiên cứu mật mã tại công ty PQShield và là tác giả của phiên bản 2021. Ông nói rằng công việc của nhóm ông đã đưa ra một “bằng chứng về khái niệm; kết quả mới cho thấy rằng “bạn có thể thực hiện việc giảm mạng rất nhanh một cách hợp lý”.

Kỹ thuật mới đã bắt đầu tỏ ra hữu ích. trang Aurel, một nhà toán học của viện nghiên cứu quốc gia Pháp Inria, cho biết ông và nhóm của mình đã áp dụng thuật toán thích ứng để thực hiện một số nhiệm vụ lý thuyết số tính toán.

Các thuật toán kiểu LLL cũng có thể đóng một vai trò trong nghiên cứu liên quan đến các hệ thống mật mã dựa trên mạng được thiết kế để giữ an toàn ngay cả trong tương lai với máy tính lượng tử mạnh mẽ. Chúng không gây ra mối đe dọa cho những hệ thống như vậy, vì việc hạ gục chúng đòi hỏi phải tìm ra các vectơ ngắn hơn những gì các thuật toán này có thể đạt được. Nhưng các cuộc tấn công tốt nhất mà các nhà nghiên cứu biết sử dụng thuật toán kiểu LLL làm “khối xây dựng cơ bản”, cho biết Wessel van Woerden, một nhà mật mã học tại Đại học Bordeaux. Trong các thí nghiệm thực tế để nghiên cứu các cuộc tấn công này, khối xây dựng đó có thể làm chậm mọi thứ. Bằng cách sử dụng công cụ mới, các nhà nghiên cứu có thể mở rộng phạm vi thử nghiệm mà họ có thể chạy trên các thuật toán tấn công, đưa ra một bức tranh rõ ràng hơn về cách chúng thực hiện.

Quanta đang tiến hành một loạt cuộc khảo sát để phục vụ khán giả của chúng tôi tốt hơn. Lấy của chúng tôi khảo sát độc giả khoa học máy tính và bạn sẽ được tham gia để giành chiến thắng miễn phí Quanta hàng hóa.