선형 공격 문서 원본 보기

{{위키데이터 속성 추적}}
'''선형 공격'''(linear cryptanalysis)은 [[암호 공격]]의 한 방법으로, [[암호화]] 과정에서의 근사적 [[선형 변환|선형 관계식]]을 찾는 것을 목적으로 한다.

선형 공격은 [[마쓰이 미쓰루]](松井 充)의 논문에서 처음 공개되었으며, 해당 논문에서는 선형 공격으로 [[FEAL]] 암호를 공격하는 방법을 제시했다.

선형 공격은 [[차분 공격]]과 함께 [[블록 암호]]를 공격하는 방법으로 널리 응용된다.

== 공격 방법 ==

선형 공격은 먼저 암호화 과정에서의 근사적인 선형 관계성을 찾는다.
어떤 암호화 함수가 입력값 <math>P = (P_1, \cdots, P_n)</math>와 암호화 키 <math>K = (K_1, \cdots, K_k)</math>를 받아 암호화된 출력값 <math>C = (C_1, \cdots, C_n)</math>을 반환한다고 할 때,
:<math>P_{i_1} \oplus P_{i_2} \oplus \cdots \oplus C_{j_1} \oplus C_{j_2} \oplus \cdots = K_{k_1} \oplus K_{k_2} \oplus \cdots</math>
과 같은 형태의 관계식들이 어떤 확률로 성립하는지를 관측한다.
이상적인 암호화 함수는 이 확률이 1/2이어야 하지만, 암호화 방법에 따라서 이 확률이 1/2과 크게 다를 수 있다.

이러한 선형 관계식을 찾는 방법은 암호화 과정에 따라 다르다.
[[대입-혼합 네트워크]](substitution-permutation network)의 경우 혼합 과정은 선형적이며, [[S-박스]]에서의 대입 과정에서만 비선형적인 변환이 일어난다. 따라서 S-박스의 연산을 선형 과정으로 근사화할 방법을 찾는 것이 목표가 된다.

근사 선형 관계성을 찾았다면, 이를 통해 chosen-plaintext 공격을 수행할 수 있다. 암호화 모듈에 임의의 입력값을 입력할 수 있을 때, 관계식에서 입력값 부분과 출력값 부분이 얼마나 일치하는지 횟수를 측정한다. 이 횟수를 기반으로 [[키 (암호)|암호화 키]] 비트들에 대한 관계식을 확률적으로 추정할 수 있다.
== 같이 보기 ==
* [[차분 공격]]

{{블록 암호}}

[[분류:암호 공격]]