Đối với các thuật toán khác, ký hiệu big-O thường ẩn các thừa số không đổi, làm cho phép toán cơ bản chính xác trở thành một chi tiết không quan trọng. Nhưng các bài báo mật mã nêu chính xác sự phức tạp, điều này làm tôi ngạc nhiên.
Bạn có quyền ngạc nhiên --- nói chung, việc viết "độ phức tạp chính xác" là vô vọng do cái được gọi là định lý tăng tốc tuyến tính --- chúng ta chỉ có thể xác định độ phức tạp tính toán cho đến một hệ số nhân tùy ý.
Điều này là do chúng ta luôn có thể tăng kích thước của bảng chữ cái cơ bản lên một hệ số không đổi nào đó để cho phép chúng ta tính toán số lượng thao tác lớn hơn trên mỗi bước thời gian. Điều này (loại) có một thành phần thực tế --- bạn có thể tăng kích thước của kiến trúc tập lệnh để thực hiện nhiều tính toán hơn trên mỗi chu kỳ xung nhịp (với chi phí chip sử dụng nhiều silicon hơn).
Vậy mọi người sử dụng thước đo chi phí nào? Nó Thực ra phụ thuộc vào ứng dụng.
Ví dụ, một cuộc tấn công nổi tiếng vào AES là cuộc tấn công bilic, khôi phục khóa AES phức tạp $2^{126.1}$. Tất nhiên, các tác giả không có xu hướng yêu cầu các con số tùy ý là kết quả của họ --- làm thế nào để họ tính toán điều này?
Toàn bộ sự phức tạp của phương pháp biclique độc lập
được đánh giá như sau:
$$C_{full} = 2^{nâ2d}[C_{biclique} + C_{precomp} + C_{recomp} + C_{falsepos}],$$
ở đâu
- $C_{precomp}$ là độ phức tạp của tiền tính toán trong Bước 3. Nó tương đương với ít hơn $2^d$ chạy của subcipher $g$.
- $C_{recomp}$ là độ phức tạp của việc tính toán lại biến nội $v$ $2^{2d}$ lần. Nó
phụ thuộc rất nhiều vào đặc tính khuếch tán của mật mã. Đối với AES, giá trị này thay đổi từ
$2^{2dâ1,5}$ đến $2^{2dâ4}$.
Cấu trúc biclique khá rẻ trong mô hình này. Phương pháp trong Mục 3.1 cho phép
xây dựng một biclique chỉ trong $2^{d+1}$ cuộc gọi của subcipher $f$. Do đó, thường là chìa khóa đầy đủ
độ phức tạp phục hồi sẽ bị chi phối bởi $2^{nâ2d}C_{recomp}$. Tuy nhiên, nó phụ thuộc vào
chiều rộng của biến phù hợp và kích thước biclique $d$ quá. Chúng tôi cung cấp thêm chi tiết cho trường hợp
của AES trong các phần tiếp theo. Độ phức tạp bộ nhớ của quá trình khôi phục khóa bị giới hạn trên
bằng cách lưu trữ $2^d$ tính toán đầy đủ của mật mã.
Đối với AES nói riêng, sau đó họ nói
Nhìn chung, chúng ta cần một tương đương với $3.4375$ Hoạt động SubByte (nghĩa là 55 hộp S), 2.3125
Hoạt động MixColumns và một lượng XOR không đáng kể trong lịch biểu chính. Số lượng
Tính toán SubBytes rõ ràng là một tổng kết lớn hơn. S-box cũng là nhân tố đóng góp chính
đến sự phức tạp thực tế của AES cả về phần cứng và phần mềm. Vì vậy, nếu chúng ta nhắm đến một
một số duy nhất đề cập đến độ phức tạp, sẽ rất hợp lý khi đếm số lượng SubByte
các hoạt động mà chúng tôi cần và so sánh nó với hoạt động đó trong mật mã đầy đủ. Số sau là
$10 + 2.5 = 12.5$ vì chúng ta phải tính đến tính phi tuyến tính của lịch trình chính. Kết quả là,
$C_{recomp}$ tương đương với $2^{16}\times 3,4375/12,5 = 2^{14,14}$ chạy toàn bộ AES-128. Giá trị $C_{biclique}$
và $C_{precomp}$ cùng nhau không vượt quá $2^8$ các cuộc gọi của AES-128 đầy đủ.
Độ phức tạp tính toán đầy đủ lên tới khoảng
$2^{112} (2^7 + 2^7 + 2^{14.14} + 2^8) = 2^{126.18}$.
Điều này có nghĩa là "hoạt động nguyên thủy" của cuộc tấn công biclique là số lần gọi SubBytes, trong đó người ta bình thường hóa mọi thứ sao cho cuộc tấn công vũ phu sẽ thực hiện $2^{128}$ sự phức tạp.
Tất nhiên có những khái niệm khác về sự phức tạp.
Ví dụ
Tôi đã nghe nói về số liệu "Diện tích x Thời gian", đo lường mức độ phức tạp của một cuộc tấn công theo thời gian cần một mạch có kích thước nhất định để hoàn thành nó (nhưng hiện không thể tìm thấy tài liệu tham khảo),
tương tự, các cuộc tấn công thường đo lường cả một số khái niệm về độ phức tạp tính toán cùng với một số khái niệm về độ phức tạp của bộ nhớ/mẫu,
trong mật mã dựa trên mạng tinh thể, một số liệu nhất định được gọi là "số SVP lõi" khá phổ biến trong phân tích.
Tuy nhiên, nói chung, vì nó không rõ ràng là gì $2^{128}$ các hoạt động nguyên thủy có nghĩa là (ví dụ), tùy thuộc vào các tác giả để xác định các thuật ngữ này, vì vậy họ thường làm như vậy.
