단일치환 암호방식과 다중치환 암호방식

우리가 이전글에서 시저암호와 비제네르 암호에 대해서 알아보았다.

이 둘은 고전암호이며, 암호학에서 다음과 같이 중요한 특징 2가지들을 갖고있다. 

 1. 단일치환 암호방식(시저암호)

알파벳에서 숫자(키 값)을 이용해서 다른 알파벳이 되도록 치환시키는 방법이다.

 ex) 단일치환 방식

1) 알파벳 "A는 처음시작이므로 0"이라는 숫자로 정의하고 "Z는 알파벳의 끝 25"라고 생각하자('A' ~ 'Z' → 0 ~ 25)

2) 원하는 Key값 만큼 치환시킨다.(key값은 숫자) 알파벳 26개를 0~25로 생각하고 만약 key값이 25를 넘어가면 다시 0으로 생각한다.

  [단일치환 암호화] 

  - key 값 : 4

 2 다중치환 암호방식(비제네르 암호)

평문에서 하나의 알파벳은 여러 알파벳으로 나타낼 수 있다.

단일치환 방식에서 알파벳의 빈도정보를 파악해서 어느정도 유추할수있는 약점이 있었는데, 이 빈도정보를 무력화시키는 방법인 '다중치환 방식' 등장하게 된다.

(같은 알파벳이더라도 다른알파벳으로 치환이 될 수 있으므로) 

  [다중치환 암호화, 복호화] 

  - key 값 : dog / 평문 MidNighT

 3. 단일 / 다중 치환 암호방식의 약점

1) 단일치환 암호방식 약점 

단일치환 암호방식은알파벳의 수는 26개로 한정이 되어있다는 점이다. 

키 값이 알파벳 갯수에 한정이 되어 있으므로 문장을 보호하는데 있어서, 큰 방패가 되어주지는 못한다.(빈 틈이 많이보인다.)

- 평행이동
 문자를 하나씩 평행이동(+n)을 통해서 인해 키 값을 찾아낼 수 있다.
여기서 key값을 1부터 25까지 평행이동을 하게되면, 우리는 암호문으로부터 평문을 찾을 수 있다. 

- 빈도분석법

 수집한 문자들에서 분표현황을 파악하는 방법.

 우리가 문서의 내용을 분석할때, 어느 단어들이 많이쓰였고, 자주쓰이는 알파벳이 무엇이 였는지, 특정 단어들의 사용횟수 등의 여부를 파악해보는 방법이다.

 쉽게 말해서, "내가 이문장에서 얻고싶은게 무엇인지"에 초점을 두고 데이터들을 보고 분석하는 것이다.

2) 비제네르 암호의 약점

 다중치환의 형태로 키 값이 한 단어가 되어 평문에서 하나의 알파벳이 같은 알파벳으로 고정적으로 치환시키는 방법이 아니라, 하나의 알파벳이 다른 알파벳으로도 치환되는 특징을 갖고있다.(유동적이다) 

"이러한 방식의 암호문에 약점이 존재할까?" 의문을 품을 수 도 있는데, 다음은 방법으로 해독이 가능하다.

 2-1) 카지스키 분석법

카지스키 분석법의 핵심은 특정 문자열의 반복적인 등장이다.

 - 비제네르 암호는 다음과 같은 방법으로 분석이 가능하다.

 암호화 된 문서에서 특정 문자열이 자주 등장하면, 키의 길이를 어느정도는 유추할 수 있다. 2개의 특정 문자열이 등장했을때, 이 2개의 구간사이는 키 길이의 배수가 된다. 그리고 이를 다르게 말하면, 키의 길이는 이 구간의 약수이다. 조금 이해하기 어렵지만 다시 정리해보자

 - 특정 문자열 2개 등장할때,

우리는 key 길이는 특정 문자열 2개의 구간(특정 문자열이 떨어져있는 거리)의 약수이다.

그리고 이 구간은 key 길이의 배수가 된다.

[다중치환 암호방식의 약점 예시 - 1]

 Key: dog

 평문: My dog is cool I like dogs better than cats. Dogs do not have hair so dog is good

평문

M

y

d

o

g

i

s

c

o

o

l

i

l

i

k

e

d

o

g

s

b

e

t

t

e

r

t

h

a

n

c

a

t

s

d

o

g

s

d

o

n

o

t

h

a

v

e

h

a

i

r

s

o

d

o

g

i

s

Key

d

o

g

d

o

g

d

o

g

d

o

g

d

o

g

d

o

g

d

o

g

d

o

g

d

o

g

d

o

g

d

o

g

d

o

g

d

o

g

d

o

g

d

o

g

d

o

g

d

o

g

d

o

g

d

o

g

d

암호문

p

m

j

r

u

o

v

q

u

o

z

r

o

w

q

h

r

u

j

g

h

h

h

z

h

f

z

k

o

t

f

o

z

v

r

u

j

g

j

r

b

u

w

v

g

y

s

n

d

w

x

v

c

j

r

u

o

v

 : 2개의 특정 문자열 "ruj"의 등장 " 평문 : dog → 암호문 : ruj "

이때, 우리는 2가지를 알 수 있다. (이 단어는 같은단어로 의심할 수 있다.)

"ruj"가 존재하는 두 구간은 키의 배수이며, 키의 길이는 이 구간의 약수이다. 이 외에도 비슷한 단어를 가진것들이 존재한다. "평문 is → 암호문 ov", "평문의 do → 암호문 jr" 

 하지만, 이 두개의 문자열로 이루어진 것들은 단지 우연히 이루어진 것이라고 생각할 수 도있고, 알파벳 2개의 문자열로 이루어진 단어로는 두개의 단어가 서로 같을 확률이 낮다.

이로써, 암호문에서 3개 이상의 알파벳으로 이루어진 문자열의 등장은 

"아! 평문에서 똑같은 단어가 2번 사용이된거구나!" 라고 이해할 수 있다.

[다중치환 암호방식의 약점 예시 - 2]

 실제 key길이 : 3(dog)

: 그림을 잘 생각해보면, "ruj"에 사용된 key 값은 "ogd" 로 두개가 겹친다.(즉 같은키값의 사용)
그러면 똑같은 key로 2번 암호화 되었다는 의미이다. 즉, 첫번째 등장한 ruj와 뒤에 등장한 ruj의 구간에서 "key가 최소 2번은 사용되었구나!"라고 생각 할 수  있다.
 다르게 말하면, "key의 길이는 15이하라는것을 판정지을 수 있다!" 라고 분석이 된 것이다.

 그래서 우리는 암호문의 내용이 길다면, 알파벳 3개의 이상으로 이루어진 특정 문자열(특정 단어)로 키의 길이를 어느정도 예측할 수 있다.
 "왜 2개의 알파벳으로 이루어진 특정 문자열은 안되나요?"라고 생각할 수 있는데, 물론 이 특정 문자열도 중요한 핵심이되는데, 하지만 암호화 도중 우연히 생긴 문자열인 가능성이 더 높기 때문이다.
따라서 암호문에 특정 문자열이 많으면 많을수록 그리고 평문에서의 반복적인 단어의 사용이 많다면(예 : The) 우리는 key길이를 예측할 수 있게되는 것이다.



2-2) 프리드만 암호공격

암호문에서 특정 문자열이 2개 쓰였을 경우, 두 개의 문자열이 서로 같을 확률이다.('일치지수' 라고 함)

 ■ 단일 치환 방식

특정 알파벳이 암호문에서 다른 알파벳으로 대응되는 알파벳의 일치 지수는 같다.(즉, 키 값이 고정적이다)

 ■ 다중 치환 방식 

특정 문자열이 암호문에서 다른 문자열로 대응되는 일치 지수가 감소하게 된다. 

왜냐? 하나의 알파벳당 키 값인 문자열에 하나씩 대응되면서 암/복호화 되는 방식이므로)

 프리드만의 암호공격에는 암호화된 문서의 전체내용에서 "알파벳 사용빈도", "자주 등장하는  특정 문자열(3개이상)", "수학적인 공식(암호문에서의 특정 문자열, 알파벳의 사용빈도 등 계산하는 공식)"의 사용으로 key의 길이를 예측하는 것도 가능하다. 

 마무리로내용들을 정리해보면,

 첫째, 암호문의 내용이 길수록 해독할 가능성이 높아진다.

 둘째, 암호문에서 "하나의 알파벳이 반복되는 것"보단 "하나의 특정한 문자열의 반복을 찾는게 핵심"이다. 

 마지막으로, 강력한 보안방식은 존재하지만, 완벽한 보안방식은 존재하지 않는다.

   (강력한 보안방식도 몇년 혹은 몇십년에 걸려서 뚫리게 되어있다.)