[정보이론] 정보이론과 암호

정보이론과 암호

 

 

 

샤논의 보안 시스템

 

 

 

좋은 암호 시스템

암호화와 복호가 용이해야 함

키를 알지 못하는 공격자에 의한 암호 해독은 어려워야함

- 키 공간이 크면 암호해독이 어려움

- 해독을 위한 많은 양의 평문, 암호문이 필요하면 암호해독이 어려움

 

 

간단한 암호 시스템

단순 대치 암호

 

Vigenere 암호기

평문의 다른 문자들을 서로 다른 양만큼 이동

단순 대치 암호와 유사함

 

 

암호 시스템의 안전성

안전성의 분류

Unconditinal security

Computational security

 

알고리즘 해독에 대한 분류

total break : 키 K를 발견

Global deduction : $D_{k}(C)$ 와 같은 값 계산하는 임의의 알고리즘 A 발견

Instance deduction : 가로챈 암호문에 대한 평문 발견

Information deductrion : 키나 평문에 대한 어떤 정보 획득

 

 

 

샤논의 Secrecy System

"Communication Theory of Secrecy Systems"

 

암호 시스템에 정보 이론 적용

무한대의 시간과 계산 능력을 가진 공격자에 대한 암호 시스템의 안전성

암호 시스템 해독을 위해 필요한 암호문의 양

무조건적으로 안전한 암호 시스템의 존재 가능성

 

 

 

 

 

완전 보안 (Perfect Secrecy)

암호문은 평문에 대한 정보를 전혀 갖지 않음

y로부터 x의 정보를 얻을 수 없음

y를 얻기 위해 특정 x를 암호화할 확률은 모든 가능한 x에 대하여 동일하다

평문의 숫자만큼 많은 암호문이 존재해야함

모든 가능한 평문/암호문 쌍 (x,y)에 대하여 $y=E_{K}(x)$ 를 만족하는 키 K가 있어야만 함

 

완전 보안의 정리

|K| = |X| = |Y| 인 암호 시스템은 모든 키가 같은 확률로 사용되고

모든 $x\in X, y\in Y$ 에 대하여 $E_{k}(x) = y $를 만족하는 유일한 $k \in K$ 가 존재하면 완전 보안을 제공함

 

키의 수가 유한하다면 가능한 평문의 수가 무한인 암호 시스템은 완전한 비밀을 보장할 수 없음

 

One-time pad 암호 = 완전 보안 제공하는 암호

 

 

 

암호 시스템과 엔트로피

 

 

암호 시스템의 엔트로피

키 공간의 크기 K가 척도 가 된다.

엔트로피가 클수록 안전함(불확실성이 큼)

 

 

암호문이 키에 관해 얼마만큼의 정보를 가지는가?

 

 

 

 

언어 엔트로피

 

 

언어비

메시지 길이 N

메시지 X

언어비 r

 

 

절대비

문자마다 부호화할 수 있는 최대 비트수

L 문자 언어의 절대비 R

예시)

영어 언어의 절대비 R

영어 알파벳의 개수 26문자

 

$ R = log_{2}L $

 

 

중복도 (Redundacy)

 

중복도 D = 절대비R - 언어비r

 

예시)

영어의 언어비 1.3(bit/letter)

영어의 절대비 4.7(bit/letter)

 

영어의 중복도 D = 4.7 - 1.3 = 3.4 (bit/letter)

 

 

판별 거리 (Unicity Distance)

암호 해독에 필요한 암호문 양의 근사치

암호 해독에 있어서 단 하나의 유의미한 해를 얻기 위해 필요한 암호문의 양 표시

 

판별거리가 길수록 좋은 암호 시스템

샤논, "판별거리가 무한인 암호시스템은 이론적으로 안전함"

 

 

 

 

확산과 혼란

 

 

확산법 (Diffusion)

평문의 중복도를 암호문 전체에 퍼뜨리는 것

공격에 시간이 많이 걸림

 

예시)

 

y에서의 x 출현 빈도는 더 균일 해짐

 

 

혼란법 (Confusion)

평문과 암호문의 관계를 숨김

- 암호문과 키 사이의 관계를 복잡한 연산에 의해 숨김

 

비선형 함수와 키 요소들을 사용함 (s-box 등)

 

 

곱셈 암호기

평문 x를 암호시스템으로 암호화

 

각 암호 시스템은 자신의 키(key)를 가짐

교환 불가능함 : 암호 시스템의 적용 순서가 중요함

 

 

혼합 변환 (Mixing Transformation)

샤논의 혼합 변환