Cách tìm dấu vết tối ưu trong phân tích mật mã tuyến tính

Tôi đang đọc và thực hiện điều này hướng dẫn, tác giả giải thích mọi thứ khá rõ ràng, điều duy nhất tôi còn thiếu là cách anh ấy quyết định sử dụng đường nào (trang 12). Tôi hiểu rằng người ta nên ưu tiên các đường có ít S-Box hoạt động nhất và tối đa hóa độ lệch của đường đó (trên thực tế, việc tìm ra đường tối ưu dường như là bước quan trọng nhất khi cố gắng áp dụng phân tích mật mã tuyến tính cho thuật toán mã hóa đối xứng) .

Đối với tôi, nó giống như một số loại vấn đề lập trình động, nhưng tôi tự hỏi liệu có một thuật toán chung để giải quyết vấn đề tìm đường tối ưu (hoặc ít nhất, một loạt các đường ứng cử viên).

Phương pháp của Matsui là phương pháp cổ điển, nhưng ngày nay xu hướng hướng tới tìm kiếm dựa trên MILP/SAT/SMT. Tính chính xác của dấu vết và liên kết của nó với xác suất chuyển đổi được mã hóa vào hệ thống và sau đó được tối ưu hóa để giảm thiểu tổng xác suất (đối với tìm kiếm nhị phân SAT/SMT có thể được sử dụng, đối với MILP, tối ưu hóa là tự nhiên).

Một số ví dụ (hầu hết các nghiên cứu là dành cho các cuộc tấn công khác biệt, nhưng nó thường được dịch sang các cuộc tấn công tuyến tính):

• Tăng tốc việc tìm kiếm các đặc tính vi phân và tuyến tính bằng phương pháp SAT
• Các thuật toán tìm kiếm tự động dựa trên MILP cho các vệt vi sai và tuyến tính cho Speck
• Cải thiện thuật toán đánh giá bảo mật dựa trên MILP đối với phân tích mật mã vi sai/tuyến tính bằng cách sử dụng phương pháp chia để trị
• Xem lại các cuộc tấn công khác biệt khóa liên quan đến AES với lập trình ràng buộc