2.1. 정보론 개요
“정보”(Information)는 어떤 것의 상태나 대상에 대한 불확실성을 감소시켜 줄 수 있는 지식을 말합니다.
정보를 생성 및 전달하는 과정에서 “송신자”는 정보를 생성하고 최초로 전파하는 원천의 개념입니다.
“통신로”는 정보 전달을 매개하는 전송 매체들을 말합니다.
“부호기”는 정보를 전달하는 매체에 맞게 적합한 형태로 정보를 변환해주는 장치입니다.
“복호기”는 정보가 매체를 타고 전달된 후 다시 사용가능 한 정보로 변환해주는 장치입니다.
위의 개념은 “샤논”의 통신계 모델 이나, 정보 이론적으로 정의 한 개념들에서 가져온 것입니다.
2.2. 정보 엔트로피
요즘 사용하는 암호를 포함하여 모든 암호 중에서 암호 시스템이나 암호문 만을 가지고 있을 때,
과연 이론적으로 해독이 불가능한 완벽한 암호는 존재 할까요?
어떠한 암호가 “완전비밀”(Perfect Secrecy)이라면, 해당 암호는 이론적으로 해독이 불가능한 암호임을 나타냅니다.
이때, 완전비밀암호의 공식은 \(P\)( 평문 | 암호문 ) = \(P\)( 암호문 ) 이 됩니다. ( 평문과 암호문이 수학적으로 독립 사건 )
또한, \(( P, C, K, E, D ), |P| = |C| = |K|\) 인 암호 시스템에서 모든 열쇠 \(K\)가 같은 확률 \(\frac{1}{|K|}\)로
\(E_k (p) = c : ( ∀ p ∈ P , ∃! c ∈ C ) => ∃! k ∈ K\) 이면, 완전비밀암호가 됩니다.
어떤 평문의 집합 \(X\)가 정의 될 때, \(X\)의 각 원소 \(x_i\)들은 서로 독립이고 각 원소의 등장 확률을 \(p( x_i )\)라 가정하고,
\(H(P) = -\sum_{i=1}^{n}{ p( x_i )\log_2{ p( x_i ) } }\) 라고 한다면,
\(H(P)\)는 \(P\)의 “엔트로피”(entropy)라고 표현합니다.
1948년 샤논에 의해 정보관점의 엔트로피를 나타낸 것이고, 정보의 불확실성을 나타낸 것입니다.
단순히, 한 원소가 등장확률이 낮다는 것은 굉장히 긴 비트열일 가능성이 높으며 그만큼 엔트로피는 높아지게 되고,
한 원소가 등장확률이 높다는 것은 짧은 비트열로 끝날 가능성이 높으며 그만큼 엔트로피는 낮아지게 됩니다.
또한, 이미 알고 있는 정보는 확률이 \(0\) 또는 \(1\)로 정해지므로, 엔트로피는 \(0\)이 됩니다.
어떤 평문집합 \(X\)와 \(Y\)가 존재할 때,
\(X\)의 각 원소 \(x_i\)와 \(Y\)의 각 원소 \(y_i\)가 각 원소의 등장 확률을 \(p\)함수로 정의 할 수 있다면,
\(X\)와 \(Y\)의 “결합 엔트로피”(Joint Entropy)는 다음과 같습니다.
\(H( X, Y ) = -\sum_{i = 1}^{n}{\sum_{j = 1}^{m} {p( x_i , y_j )\log_2{ p( x_i , y_j ) } } }\)또한, \(Y\)에 대한 \(X\)의 “조건부 엔트로피”(Conditional Entropy)는 다음과 같습니다.
\(H( X | Y ) = -\sum_{i = 1}^{n}{\sum_{j = 1}^{m}{ p( y_j )p( x_i | y_j )\log_2{ p( x_i | y_j ) } }}\)\(Y\)에 대한 \(X\)의 조건부 엔트로피는 \(Y\)가 주어질 때, \(X\)에 대한 정보량을 나타냅니다.
2.3. 정보 엔트로피의 예
암호학에서 조건부 엔트로피 세 가지를 나열 한 것입니다.
1). 암호문 \(C\)에 대한 열쇠 \(K\)의 조건부 엔트로피는 다음과 같습니다.
\(H( K | C ) = -\sum_{i=1}^{n}{\sum_{j=1}^{m}{ p( c_j )p( k_i | c_j )\log_2{ p( k_i | c_j ) } } }\)이는 “열쇠 불확실도”(Key Equivocation)라고도 표현합니다.
2). 암호문 \(C\)에 대한 평문 \(P\)의 조건부 엔트로피는 다음과 같습니다.
\(H( P | C ) = -\sum_{i=1}^{n}{\sum_{j=1}^{m}{ p( c_j )p( x_i | c_j )\log_2{ p( x_i | c_j ) } } }\)이는 “메시지 불확실도”(Message Equivocation)라고도 표현합니다.
3). 평문 P와 암호문 \(C\)가 주어졌을 때, 열쇠 \(K\)의 조건부 엔트로피는 다음과 같습니다.
\(H( K | P , C ) = -\sum_{h=1}^{l}{\sum_{i=1}^{n}{\sum_{j=1}^{m} { p( k_h , x_i , y_j )\log_2{ p( k_h | x_i , y_j ) } } } }\)이는 “열쇠출현 불확실도”(Key Appearance Equivocation)라고도 표현합니다.
암호시스템 \((P , C , K , E , D)\)이 있을 때,
\(H( K | P , C ) = H( K , C ) – H( P | C )\) 와 \(H( K | C ) = H( K ) + H( P ) – H( C )\) 을 성립합니다.
해독자가 무한한 계산능력을 가지고 있고 암호의 통계적특성을 알고 있는 상황에서
해독방식을 단독공격만을 사용했을 때,
일반적인 잘못된 열쇠들을 제외하더라도 열쇠가 가능 할 수 있는 잘못된 열쇠도 존재 할 수도 있습니다.
예를들어 어떤 암호가 이상한 단어로 바뀌는 열쇠는 잘못된 열쇠라고 즉시 판단 가능하지만,
그럴듯한 단어로 바뀌는 열쇠라고 해서 그 열쇠가 잘못된 열쇠가 아니다 라고 하기에는 무리가 있을 수 있습니다.
이 때의 실제 잘못된 열쇠이지만 해독상 열쇠가 된다고 판단한 열쇠들을 “거짓열쇠”(Spurious Key)라고 표현합니다.
거짓열쇠는 자연어 상에서 가능성 여부로 생긴 개념이기에 거짓열쇠 기댓값의 “상한”을 만약 정의한다면,
이는 자연어의 엔트로피와 유사할 것입니다.
자연어 집합 \(L\)이 있을 때, \(P^n\)을 \(n\)개의 글자 집합 이라고 한다면,
“자연어 \(L\)의 엔트로피”는 \(H_L = lim_{n->∞} \frac{ H( P^n ) }{n}\) 이라고 정의 할 수 있고,
\(R_L = 1 – \frac{ H_L } { \log_2{ | P | } }\) 를 \(L\)의 “과잉정보량”(redundancy)라고 표현합니다.
암호시스템 \((P , C , K , E , D)\)이 있을 때, \(| P | = | C |\) 이고 열쇠는 무작위 확률이라고 한다면,
거짓열쇠의 기대값 \(s_n\)은 \(\frac{| K |} {| P |^{ (nR_L) }} – 1\) 보다 크거나 같습니다.
이 때, 기대값 \(s_n\)이 \(0\)이 되는 지점 즉, \(\frac{| K |} {| P |^{ (nR_L) }} = 1\) 인 지점의 \(n\)을
“열쇠 결정 거리”(Key Unicity Distance)라고 표현하고 \(n_0\)로 따로 표현합니다.
의미는 \(n\)글자에 따른 기대값 \(s_n\)이 \(0\)이 된다는 것은 해당 \(n\)글자 부터 거짓열쇠가 없는
유일해가 나오는 최초지점이기 때문에 이 지점의 \(n\)을 \(n_0\)로 결정거리라는 의미를 부여합니다.