유일성 거리 (Unicity Distance)

유일성 거리(unicity distance)는 클로드 섀넌이 정의한 개념으로, 가능한 모든 키를 시험하는 공격자에게 의미 있는 평문을 만드는 키가 하나만 남도록 하는 데 필요한 암호문의 최소 길이입니다. 이보다 짧은 암호문에서는 그럴듯한 평문을 만드는 거짓 키(spurious key)가 여러 개 남을 수 있습니다.

자세히 알아보기

섀넌은 1949년 논문 「Communication Theory of Secrecy Systems」에서 비밀 통신을 정보 이론으로 분석하며 이 개념을 제시했습니다. 기대 유일성 거리는 U = H(K) / D로 구합니다. H(K)는 키 공간의 엔트로피(비트), D는 평문 언어의 문자당 중복도(redundancy, 비트)입니다.

중복도는 문자 하나가 담을 수 있는 최대 정보량과 실제로 담는 정보량의 차이입니다. 영어 알파벳 26자는 문자당 log₂26 ≈ 4.7비트를 담을 수 있지만, 의미 있는 영어 문장은 문자당 약 1.5비트만 담는 것으로 봅니다. 따라서 D ≈ 4.7 − 1.5 = 3.2비트입니다. 언어에 중복이 있기 때문에 잘못된 키로 복호화한 결과는 대개 의미 없는 문자열이 되고, 암호문이 길어질수록 우연히 말이 되는 거짓 키는 빠르게 줄어듭니다.

유일성 거리가 알려 주는 것은 계산 능력에 제한이 없다고 가정할 때 정답이 하나로 정해지는 데 필요한 정보의 양입니다. 해독에 드는 시간이나 계산량은 나타내지 않습니다. 같은 영어 모델을 2¹²⁸개의 키에 적용하면 128 / 3.2 = 40자 정도에서 유일성 거리에 도달하지만, 그 키를 모두 시험하는 것은 현실적으로 불가능합니다. 그러므로 유일성 거리가 크다고 무차별 대입 공격에 강한 것은 아니며, 실제 암호의 강도는 계산적 안전성으로 따로 평가합니다.

블록체인·암호화폐에서는

블록체인에서 쓰는 해시 함수와 전자서명은 유일성 거리가 아니라 계산적 안전성, 즉 현실적인 자원으로는 풀 수 없다는 가정에 기대어 안전성을 설명합니다. 유일성 거리는 대신 사람이 외운 비밀번호처럼 엔트로피 H(K)가 작은 비밀이 적은 단서로도 하나의 답으로 좁혀질 수 있다는 점을 이해하는 데 도움이 됩니다. 이런 비밀은 키 공간 자체도 작아 모두 시험해 보기가 쉽습니다.

예시

단순 치환 암호는 알파벳 26자를 다른 순서로 바꾸는 방식이라 키가 26 × 25 × … × 1 ≈ 4.03 × 10²⁶개이고, H(K) ≈ 88.4비트입니다. 영어의 D ≈ 3.2를 넣으면 U ≈ 88.4 / 3.2 ≈ 28이므로, 이론적으로는 암호문 약 28자로 영어 평문과 키를 하나로 정할 수 있습니다. 반면 메시지만큼 긴 무작위 키를 한 번만 쓰는 일회용 패드(one-time pad)는 유일성 거리가 무한대이며, 이는 일회용 패드를 깰 수 없다는 사실과 일치합니다.

쉽게 말하면

찢어진 사진 조각 몇 개만 보면 여러 장소처럼 보이지만, 조각이 충분히 모이면 맞는 장소가 하나로 좁혀집니다. 유일성 거리는 그 조각이 최소 몇 개 필요한지를 계산하는 개념이며, 장소를 실제로 찾는 데 걸리는 시간과는 다른 문제입니다.