Phân tích mật mã tuyến tính là một cuộc tấn công bản rõ đã biết, trong đó kẻ tấn công nghiên cứu các mối quan hệ tuyến tính xác suất được gọi là xấp xỉ tuyến tính giữa các bit chẵn lẻ của bản rõ, Bản mã và khóa ẩn.
Trong cách tiếp cận này, kẻ tấn công có được các giá trị xấp xỉ xác suất cao cho bit chẵn lẻ của khóa ẩn bằng cách tính toán các bit chẵn lẻ của các bản rõ và bản mã đã biết. Bằng cách sử dụng một số phương pháp tiếp cận bao gồm cả kỹ thuật phụ trợ, kẻ tấn công có thể mở rộng cuộc tấn công để khám phá các bit bổ sung của khóa bí mật.
Phân tích mật mã tuyến tính cùng với phân tích mật mã vi sai là các cuộc tấn công thường được sử dụng vào mật mã khối. Kỹ thuật phân tích mật mã tuyến tính lần đầu tiên được phát minh bởi Mitsuru Matsui, người lần đầu tiên sử dụng nó cho mật mã FEAL.
Nói chung, có hai phần đối với phân tích mật mã tuyến tính, chẳng hạn như thứ nhất là lập phương trình tuyến tính kết hợp với bản rõ, Bản mã và các bit khóa có độ chệch lớn; đó là xác suất nắm giữ gần nhất có thể áp dụng cho 0 0r 1.
Phần thứ hai là cần các phương trình tuyến tính này kết hợp với các cặp bản rõ-bản mã đã biết để điều khiển các bit chính.
Linear Cryptanalysis sử dụng phép gần đúng tuyến tính để mô hình hóa quá trình phi tuyến tính trong quy trình mã hóa. Nó có thể được sử dụng gần đúng với một lượng lớn bản rõ đã biết, cuối cùng sẽ tìm thấy một bit khóa chính xác với một xác suất cụ thể. Các cải tiến cụ thể về mật mã của phương pháp này có thể tìm thấy nhiều bit khóa.
Cuộc tấn công phân tích mật mã tuyến tính dựa trên việc khám phá các xấp xỉ tuyến tính để xác định các phép biến đổi được thực hiện trong Tiêu chuẩn mã hóa dữ liệu. Cách tiếp cận này có thể khám phá khóa Chuẩn mã hóa dữ liệu được cung cấp cho 243 bản rõ đã biết, được phân biệt với 247 bản rõ được chọn để phân tích mật mã vi phân.
Ngay cả khi đây là một tiến bộ nhỏ, vì có thể dễ dàng hơn để có được bản rõ đã biết thay vì bản rõ đã chọn và nó có thể khiến việc phân tích mật mã tuyến tính không khả thi như một cuộc tấn công vào Tiêu chuẩn mã hóa dữ liệu.
Mục tiêu của phân tích mật mã tuyến tính là khám phá một phương trình tuyến tính hiệu quả có dạng -
$$ \ mathrm {P \ left [\ alpha 1, \:\ alpha 2 \:... \ alpha a \ right] \ oplus \, C \ left [\ beta 1, \:\ beta 2 \:.. . \ beta b \ right] =K \ left [\ gamma 1, \, \ gamma 2 \:... \ gamma c \ right]} $$
(trong đó x =0 hoặc 1; 1≤ a, b≤ n, 1 ≤ c ≤ m và trong đó các số hạng α, β và γ đại diện cho các vị trí bit cụ thể) ảnh hưởng với xác suất p ≠ 0,5.
P càng xa 0,5 thì phương trình càng có hiệu. Bởi vì phân tích tiền cứu được quyết định, quá trình này là đánh giá kết quả bên trái của phương trình trước đó cho một số lượng lớn các cặp bản rõ-bản mã. Nếu kết quả là0 quá nửa thời gian, giả sử K [γ1, γ2 ... γc] =0.
Nếu đó là 1 phần lớn thời gian, giả sử K [γ1, γ2 ... γc] =1. Điều này cung cấp cho chúng ta một biểu thức tuyến tính trên các bit khóa. Nó có thể cố gắng nhận thêm các quan hệ như vậy để có thể giải các bit chính. Bởi vì trong bài báo này quản lý bằng phương trình tuyến tính, vấn đề có thể được tiếp cận một vòng của mật mã tại một thời điểm, với các kết quả được kết nối.