4. Theory of Secure Communication

Birthday Paradox

23명의 사람들이 있다면 50% 의 확률로 같은 생일을 가진 사람이 존재할 수 있다.

 

Digital Signature Susceptibility

MD5에서의 Hash 값은 다음과 같다.

Hash 연산은 m -> f(m) 이고,

m'≠m이면 f(m')≠f(m) 이어야한다.

m'≠m인데 f(m')=f(m)이면 attacker가 m'으로 f(m)에 접근할 수 있기때문에 보안이 취약해진다.

 

이를 해결하기 위한 방법은 다음과 같다.

1. MD5 를 더 많은 bit 로 사용한다.

2. 해시함수의 결과값은 충분히 더 커야한다.

 

 

Model of Secure System

M 이라는 메시지를 전송할 때,

M -> E(M,K) 로 암호화 -> Cipher text 생성 -> D(C,K) 로 암호해독 -> M 

이때 안전한 루트인 Secure channel 을 이용한다면, 암호화된 메시지를 디코딩할 특정키 만을 전송하고, 

수신자가 암호화된 메시지를 특정키와 함께 디코딩하는 구조이다.

 

 

Shannon Theory

secrecy problem 은 noisy-channel problem 과 유사하다.

Noisy Channel에서 redundancy(필요없는 정보) 를 통해 original message를 찾듯이,

해독 과정에서 암호화된 Cipher(Message+Noise)에서 Noise를 제거하여 M을 찾아내는 것이 서로 유사하다.

 

 

Priori and Posterior Probaabilities

사전 확률 Pi 로 모든 K중에서 Ki 를 선택하고, 사전확률 Qj 로 모든 M중에서 Mj 를 선택하여 M은 Ciphertext로 변환된다. -> Cl=E(Mj,Ki)

attacker 는 CI 만 볼 수 있으며, 가능한 Mj 와 Ki 의 사후확률을 계산할 수 있다.

 

 

Condition for Perfect Secrecy

사후확률(posteriori probability) 는 attacker 의 knowledge 를 나타낸다.

P(M|C) = C가 주어졌을 때 M을 찾을 확률

P(C|M) = M에 의해 만들어진 C를 찾을 확률

P(M) = M이 선택될 확률

P(C) = C가 포함될 확률

 

만약, P(M|C) = P(M) 이라면, attacker 는 C로부터 아무런 정보를 얻지 못함을 뜻한다.

또한, P(C|M) = P(C) 라면, 주어진 M 으로부터 C를 찾기 위한 아무런 정보를 얻지 못함을 뜻한다.

따라서 이러한 조건을 Perfect Secrecy 라고 한다.

 

perfect system 이란 다수의 C와 M이 존재할 때, M을 C로 변환하기 위한 적어도 하나의 key 가 있는 상태다.

 

 

Shannon Entropy

랜덤한 변수에서 예측 불가능한 정도를 측정하는 것을 말한다.

따라서 Entropy 가 크다고 하는 것은, 예측이 어려움을 뜻한다.

이때, b는 bit의 경우 2, digit의 경우 10이 된다. 즉, 가능한 경우의 수를 말한다.

 

예시 1) Political Poll 

- 투표의 결과를 미리 알 수 없는 경우, 투표의 결과는 많은 정보를 준다. -> 엔트로피가 크다.

- 첫 번째 투표 이후 똑같은 투표를 시행한다. 이때는 어느 정도 투표 결과가 예측 가능하다. -> 엔트로피기 작다.

 

예시 2) 동전 던지기

동전의 어느 방향이 나올지 예측할 수 없으므로, 확률은 정확히 1/2 이다.

엔트로피를 위 식대로 계산한다면, entropy(H) = 1 이다.

동전의 앞면과 뒷면이 나올 확률이 1/2 로 균등할 때, entropy 가 가장 높으므로 가장 예측불가능함을 알 수 있다.

 

 

Message Entropy

특정 메세지가 N개의 메시지에서 선택될 때의 확률이 P(M) 일 때, 메시지가 선택되었을 때의 정보량은 다음과 같다.

Key Entropy

특정 key가 N개의 key에서 선택될 때의 확률이 P(K) 일 때, key가 선택되었을 때의 정보량은 다음과 같다.

system 에 알려진 불확실성의 양은 적어도 key 의 불확실성보다는 클 수 없다.

따라서 Message information 은 만약 key 불확실성이 적어도 message 불확실성 이상이라면, 완벽하게 은폐될 수 있다.

-> Key Entropy≥Message Entropy일 때 메시지 정보가 완벽히 은폐된다.

 

 

Equivocation

key K 와 message M 에 대한 조건적인 entropy 이다.

H(K|C) = C 가 주어졌을 때 K의 엔트로피

H(M|C) = C 가 주어졌을 때 M 의 엔트로피

P(C,K) = C와 K의 동시 확률 분포

P(C,M) = C와 M의 동시 확률 분포

 

-> cipertext 의 길이가 길수록 uncertainty 가 줄어든다. 즉, 예측하기 쉬워진다.

 

 

N 길이의 ciphertext (C) 가 intercept 됐다고 가정하자.

H(K, N|C) 는 N에 대한 감소 하는 그래프이다.

즉, 뺏긴 정보가 길수록 엔트로피가 감소하기 때문이다. -> key 에 대한 예측이 쉬워짐

 

Mutual information

I(M|C) : C가 주어졌을 때 M에 대해 새롭게 알려지는 정보량

I(K|C) : C가 주어졌을 때 K에 대해 새롭게 알려지는 정보량

 

-> C가 주어짐으로써 새로 알게된 정보 = Uncertainty - C를 알고 난 뒤의 Uncertainty

I(M|C) = H(M)-H(M|C)

 

이 때 I(M|C)=0이 되는 것이 가장 이상적이다.

∴H(M)=H(M|C)가 되어야한다.

-> 새롭게 알려지는 정보가 없으므로, C가 uncertainty of message를 낮추지 않는다.

 

또한, H(K) >= H(M) 이여야 한다. 즉, key bits 수가 Message bits 보다 같거나 많아야 한다.

H(M|C) 는 C가 주어졌을 때의 M의 엔트로피이다.

이는 당연히 C가 주어졌을 때 M,K 의 엔트로피를 아는 것보다 작은 값일 것이다.

또한, H((M,K)|C) = H(K|C) + H(M|(C,K)) 이다.

이는 Ciphertext 가 주어졌을 때의 key 를 구하고, 구한 key 와 알고있던 ciphertext 로 Message 를 구하는 것이다.

이때, H(M|(C,K)) 에서, C 와 K 가 구해졌다면 당연히 M을 구할 수 있으므로 엔트로피는 0이 된다.

즉, H(M|C) <= H(K|C) <= H(K) 라는 식이 도출된다.

여기서, perfect secrecy 를 위해선 H(M|C) = H(M) 을 만족해야 한다.

 

 

H(M) <= H(K) 는 무엇을 의미할까?

I(M|C) = H(M) - H(M|C) 인데,

만약 H(M|C) >= H(K) 이라면, I(M|C) >= H(M) - H(K) 이다.

따라서, H(K) 가 작을 수록, I(M|C) 가 커지게 되고, attacker 가 ciphertext 로부터 Message에 대해 새롭게 알게된 정보가 많아짐을 뜻한다.

그러나, 원래대로 H(K) >= H(M) 이라면, I(M|C) <= 0 이 될 것이므로 attacker 는 정보를 얻지 못하게 된다.

-> perfect secrecy

 

 

Intercepted Ciphertext

intercepted 된 ciphertext 가 많아진다면?

intercepted 된게 많아질 수록 불확실성이 작아진다 -> Entnropy 가 작아진다.

 

 

noisy-channel 에서는 redundancy 가 더해져서, 에러가 발견될 수 있다고 하였다. 

Redundancy 란?

Redundancy 란 불필요한 정보를 뜻하는 것으로

D = R - r 로 정의할 수 있다.

R: Absolute Rate of the language, 조합가능한 모든 경우의 bit 수(entropy)

ex) cat, cta, act...

알파벳 사이즈가 L 일 때 L = 26, R = Log2L = 4.7bits/letter

 

r: Rate of the language, 실제 사용하는 조합의 entropy

ex) cat

N 개의 문자를 가진 message 에 대해서

r = H(M) / N

영어에 대한 엔트로피는

r = 1.0~1.5 bits/letter

 

따라서  R- r 의 결과는 사용하지 않는 무의미한 단어가 된다.

영어 문장에 대한 중복성 D = R - r = 4.7 - 1.5 = 3.2 bits/letter

 

 

Random Cipher

M' = D(C,K)

M' 은 N길이의 모든 2^RN 메시지들에 독립적으로 분포되어있다.

 

Spurious Key Decipherment

spurious key decipherment 란 거짓된 solution 을 뜻한다.

이는 C = E(M,K) 가 주어졌을 때, 다른 K' 로 같은 ciphertext C 를 생성해내는 것을 뜻한다.

 

즉, 공격자는 K' 를 선택했지만 결론적으로 C = E(M,K) = E(M', K') 로 동일하다.

 

모든 정확한 solution C에 대해서,

틀린 답의 개수는 2^H(K) - 1 개가 되고, 이는 각각 거짓된 해답을 산출하는 확률 q 를 가진다.

 

만약, plaintext (2^rN) 이 동일하게 거짓된 해답을 포함할 확률을 가진다면,

q는 이와 같이 될 것이다.

 

 

Unicity Distance

spurious keys 를 0으로 줄이기 위해 필요한 진짜 ciphertext 의 길이를 말한다.

만약 특정 길이의 ciphertext가 존재하다면 불확실성은 0 이 될 것이다.

F: number of false solutions

q: false solution을 생산할 확률

F 값을 0으로 두어 암호를 해독하는데 필요한 원래 암호 텍스트 길이를 계산할 수 있다.

0 = H(K) - DN

H(K) = DN

따라서 unicity distance N 은 다음과 같다.

즉, Entropy 가 커지고 Redundancy 가 작아질 수록 unicity distance 는 커짐을 알 수 있다.

 

계산 예시 )

즉, attacker 는 17.5 letter 의 문자로 key 를 알 수 있다.

8bits per letter 이므로 17.5 * 8bits = 140bits = 2blocks

 

 

Computational Complexity Theory

알고리즘의 복잡성은 time T 와 space S 으로 묘사된다.

만약, f(n) 이 지수형태라면, 

이므로, 따라서 f(n) = O(n^t) 가 될 것이다.