[해키피디아] 완전 비밀성(perfect secrecy)

간단히 말해서 “공격자가 아무리 뛰어난 계산 능력과 무한한 시간을 가지고 있어도, 암호문에서 평문에 대한 어떠한 정보도 얻을 수 없을 때” 완벽하게 안전하다고 합니다.

정보 이론(Information theory)의 아버지라고 불리는 클로드 섀넌(Claude Shannon)은 완전 비밀성을 다음과 같이 정의했습니다.

임의의 메세지 M0과 M1에 대하여, M0과 M1의 길이가 len(M0) == len(M1)로 서로 같고, 그 각각을 암호화한 E(K, M0)와 E(K, M1)의 결과가 C가 될 확률이 서로 동일하고, K가 균등 분포일 때 그 암호문은 완벽하게 안전(perfect secrecy)합니다.

만약 Alice 1부터 26까지 중 한 숫자를 이용해 시프트연산을 한다고 했을 때, 26개의 암호 중 하나의 결과로 나타납니다. (ex. BMJDF, CNKEG 등)

하지만 만약 5글자인 Alice를 1부터 25까지 숫자 중 무작위로 5개를 골라 한 글자씩 시프트 할 때 가능한 암호문의 수는 26의 5제곱이 됩니다.

예로 1,2,3,4,5를 선택하면 alice는 bnlgj가 되지만, 어떤 숫자열을 사용하냐에 따라 aaaaa, aaaab, aaaac, aaaad, … zzzza, zzzzb, zzzzz까지 가능합니다.

마찬가지로 yoona를 암호화해도 aaaaa부터 zzzzz까지의 결과를 만들어내기 때문에, 공격자가 암호문 aaaaa를 얻어도 이로부터 평문이 alice인지, yoona인지 알 수 없습니다.

OTP로 알려진 One Time Pad는 이 완전 비밀성을 보장합니다.

만약 키가 무작위하다면, 평문과 키를 XOR 연산한 암호문 역시 키만큼 무작위하기 때문에 키를 모르는 공격자는 암호문만 가지고 있을 때 평문에 대한 어떠한 정보도 얻을 수 없습니다.

4비트를 예시로 들면 평문이 1010이고 키가 1111일 때 암호문은 0101입니다. 키를 모르기 때문에 전수조사로 가능한 키를 생각하면 0000, 0001, 0010 등 16가지가 나옵니다. 이를 평문으로 복호화하면 똑같이 0101, 0100, 0111 등 16가지의 평문이 나오지만, 공격자는 어떤 것이 평문인지 알 수 없습니다.

아무리 계산을 잘하는 공격자라도 1111을 암호문으로 받으면, 이 암호문의 평문이 1010인지, 0101인지 알 수 없죠.

섀넌의 정의에 대입해보면, 임의의 메세지 M0(1010)과 M1(0101)에 대하여 둘의 길이가 같고, K가 균등 분포이며 각각을 암호화한 결과가 1111이 될 확률이 동일하기 때문에, 완전하게 안전하다고 할 수 있습니다.