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

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

이 둘은 고전암호이며, 암호학에서 다음과 같이 중요한 특징 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의 길이를 예측하는 것도 가능하다. 

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

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

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

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

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

대칭키 암호와 비대칭키(공개키) 암호

 암호학에서는 암호화 방식을 크게 2가지로 구분짓는다.

1) 암호화와 복호화시 키 값이 똑같은 대칭키 암호화 방식

2) 암호화와 복호화시 키 값이 다른 비대칭키 암호화 방식(공개키 암호화라고도 불린다.)

1. 대칭키 암호 알고리즘

 송신자와 수신자간의 메시지(평문)을 암호화 / 복호화 시 키 값이 똑같은 경우이다.

키 값이 똑같다는 건, 송신자와 수신자간의 키 값을 서로 공유하고 있어야 하며, 이외에 타인으로 부터 노출되지 않도록 비밀로 관리해야 한다. 대칭키 암호알고리즘은 고대 암호학에서도 사용하여 오랜 역사를 가지고있다. 대표적으로 고대 로마에서 시저라는 장군이 사용했던 시저암호(치환 암호방식 중 하나임)가 있다.

1-1) 대칭키 암호알고리즘의 문제점

- 키를 어떻게 공유할것인가...(송신자와 수신자만이 알고있어야 하므로) 

- 키를 타인에게 노출될 경우, 보안에 매우 취약해진다...(암호화 복호화 키가 같으므로 제 3자가 송신자 -> 수신자 전달하는 메시지를 갈취 했을경우, 키값으로 암/복호화가 가능하므로)

1-2) 대칭키 암호알고리즘의 장점

 이러한 키 전달 및 관리에 대해 어려운 점이 있으나, 그에따른 장점도 충분하다.

- 암호화 연산속도가 빨라서 효율적으로 암호시스템을 구축할수 있다.

- 고전 암호학에서도 많이 사용한 방식인 간단한 치환과 전치의 조합으로 되어있어서 쉽게 개발이 용이하며 시스템에서도 빠르게 동작한다.

1-3) 대칭키 암호 알고리즘 암호화 / 복호화 방식

1)수신자<->송신자 키 값을 이전에 공유하고있어야함.

2) 수신자->송신자 메시지 암호화 한 뒤 전달

(엘리스) -> (찰스)

3) 복호화하여 메시지 읽고 다시 암호화해서 메시지 전달.

(찰스) -> (엘리스)

2. 공개키 암호 알고리즘

 공개키 암호 알고리즘은 '비대칭 암호 알고리즘'이라고도 부른다. 말 그대로 암호화와 복호화시 사용하는 키 가 비대칭이다. 즉, 키가 다르다. 그래서 대칭키 암호 알고리즘과는 다르게, 키 값이 타인, 제 3자에게 노출이 되어도 암호화, 복호화시 키가 다르므로 해석이 불가능하다. 송신자는 수신자의 공개키로 메시지(평문)을 암호화 해서 전송하면, 수신자는 이 암호화된 문서를 자신의 개인키로 복호화하여 해석이 가능하다. 이 과정에서 제 3자, 타인으로부터 메세지나 키를 유출시켜도 수신자가 갖고 있는 개인키로만 해석이 가능하므로, 해석이 불가능하다.

2-1) 비대칭키 암호 알고리즘의 문제점

 - 암호화 / 복호화 시간

 : 대칭키 암호 알고리즘에 비해 공개키, 개인키로 2n개의 키의 사용과 복잡한 암/복호화 방식으로 인하여 시간이 많이 걸린다.(통신속도가 느림)

 - 수신자의 개인키 관리

 : 만약, 공격자(C)가 자신이 송신자(A)인것처럼 수신자(B)에게 자신(공격자, C)의 공개키로 암호화해서 평문을 보내면, 수신자(B)는 송신자(A)에게 전달받은 메시지인 줄 알고 전달받은 공개키(공격자, C의 공개키)로 메시지 내용을 암호화 해서 전달하면, 공격자(C)의 개인키로 복호화 해서 보안의 문제점이 발생할 수 도 있다.(이를 방지하고자 인증서 or 인증기관을 이용함)

2-2) 비대칭키 암호 알고리즘의 장점

 - 보안성이 강하다.

 대칭키 암호 알고리즘과는 다르게 키가 2개이상을 사용한다.

송신자는 자신의 공개키(이건 유출되도 큰 문제가 되지 않음)와 암호화된 메시지를 전달하면, 수신자는 메시지를 받고 송신자의 공개키로 복호화 한 뒤, 송신자의 공개키로 메시지를 암호화해서 보낸다. 여기서 제3자에게 공개키, 암호화된 메시지를 유출당해도 송신자의 개인키가 필요하므로, 해석이 불가능하다.(개인키는 송신자만 알고 있다.)

2-3) 공개키 암호화 방식

1) 송신자는 인증기관으로부터 공개키, 개인키를 받는다.

2) (송신자)자신의 공개키로 암호화하여 수신자에게 메시지를 전달.

3) 수신자는 인증기관으로부터 받은 송신자의 공개키로 메시지를 복호화하여 해석한다. 여기서 해독이 될경우, 타인이 아닌, 정확한 송신자로부터 받았다는 것을 식별가능. 

4) 수신자는 자신의 메시지를 송신자의 공개키로 암호화하여 전달.

5) 송신자-엘리스는 수신자로부터 받은 메시지를 자신의 개인키로 해독.

고전암호(2) - 비제네르 암호

 이전시간에 OTP암호알고리즘, 시저암호에 대해서 알아보았다.

이번시간에는 비제네르 암호에 대해서 알아보자.

 비제네르 암호란?
단일치환암호인 시저암호와 비슷한 방법의 암호방식이다. 알파벳의 a~z(26개)를 비제네르 표에 맞추어 암호화하는 방법이다. 필자가 방금 말한 비제네르 표에 맞추었다는건, 다음과 같은 표를 보면서 이해해보자.

<비제네르 표>





비제네르 표를보면 세로 x 가로(25X25) 형태로 되어있다는걸 볼수있는데, 키 값의 형태는 알파벳 형태(A~Z)로 길이는 상관없으며, 키의 길이만큼 차례대로 평문의 알파벳과 연산되면서 암호화 된다. 키(A~Z)를 0~25의 수로 바꾸며, 26으로 나누어서 해당 평문이나 암호문에 연산하면 된다.

1) 비제네르 암호화를 살펴보자,
Plaintext  →      Lifeisgood
Key        →       auto;

 이전시간에 알아본 시저암호와 매우 비슷한 암호 알고리즘인데, 이전의 시저암호에서의 키는 숫자이며, 해당 평문 문자열에 키값을 하나씩더해서 암호화를 시켰는데, 비제네르 암호는 키 값을 문자열로 받고, 평문의 길이에 맞게 문자열 하나씩 대입하면서 암호화를 진행한다. 이러한 특성으로 '빈도분석법'으로 해독이 거의 불가능하며, 키 값의 갯수(길이) 또한 제한이 되지않고, 해독시 예상이 불가능하다. 이것은 송신자와 수신자만의 동일한 키로 암호화 / 복호화가 가능하므로, 대칭키 암호 알고리즘에 속한다.

> 비제네르 암호 프로그래밍








 - 비제네르 암호화 복호화 방식
1) 비제네르 암호화 : E = (M(평문) + Key(키값)) mod 26

2) 비제네르 복호화 : D = (C-Key) mod26

 > 비제네르 암호화 / 복호화 결과

암호학 - OTP 암호 알고리즘

이번에는 OTP암호알고리즘에 대해 알아보도록 하겠다.

 우리 주변에서 흔히 전자거래, 금융관련 사이트 등에서  개인정보가(주민번호 또는 아이디, 비밀번호)유출이 되어도 2차적인 피해를 막을 수 있도록 공인인증서 혹은 휴대폰 인증 등을 통해서 조금이나마 안전하게 이용 할 수 있다.
 하지만 보안코드나 인증서 비밀번호를 알게된다면, 얘기가 조금은 달라진다.

이렇듯 우리 생활에서는 완벽한 보안방법을 찾기란 쉽지 않다. 그래서 이러한 보안코드나 인증서들이 유출이 되었을 경우에도 어떻게 해야 피해를 최소화 시킬지 알아보자.

만약에 우리가 회원가입을 할 때 휴대폰번호를 통해서 인증을 받아본 경험이 있을 것이다. 이러한 사용자 인증을 통해서 이 계정이 본인임을 확인시킬 수 있는(증명하는) 방법 중 하나이다.

1. 사용자인증
 사용자 인증은 우리의 일상 생활에서도 손쉽게 찾아볼 수 있다. 휴대폰을 사용하더라도 PIN번호 입력, 지문인식, 홍채 등을 통해서 다양하게 인증을 할 수 있다.

2. OTP(One Time Password)
 OTP는 말그대로 One Time Password의 약자로, 보통의 고정적인 패스워드와는 다르게 매번 다른 패스워드를 만든다. 사용자 인증 방법 중 하나로 사용하기에 편리하며 높은 보안성을 가지고 있는데. 자세한 특징을 살펴보자

 2-1) 강력한 보안성
 기존의 ID/PWD를 노출이 되었음에도 2차(사용자 인증 서비스)적인 보인확인을 할수있는 보안성을 가지고 있다. 그리고 2차적인 인증서비스(OTP)의 패스워드를 유출했더라도, 우리는 예측할 수 없는 이 특성으로 보안을 유지할 수 있다. OTP는 해쉬 함수를 통해서 랜덤의 값(난수)을 추출하므로 역으로 입력값을 알아내기가 힘들다. 그러므로 (악의적인)해커에 의해  패스워드를 스니핑 당한다 해도 원래의 패스워드를 찾기 힘들 것이다.

 2-2) 편리성
 한번 사용하고 폐기되는 일회용 비밀번호로, 기존의 ID/PWD, 공인인증서등 사용자 지식기반 인증를을 봤을 경우, 분실우려 및 복잡한 사용방식, 휴대성도 우수하지 못하다.  반면 OTP는 사용자가 소유하고, 동적인 정보를 이용할 수 있으며, 휴대하며 관리하기도 편리하다.

3. OTP 종류
 3- 1) S/Key방식
 먼저 고전적으로 공중망을 통해서 원격시스템에 로그인할 때 패킷들을 스니핑해 패스워드를 노출되어도 매번 패스워드가 바뀌는 방식인 S/Key방식을 통해 방지할 수 있다.

 3-2) OTP 챌린지 리스펀스 방식
 난수를 암호 알고리즘의 입력값으로 사용하여, 일회용 패스워드를 생성한다.

 [OTP챌린지 리스펀스 과정 ]
① 인증서버 or 애플리케이션이 임의의 난수값을 생성 후 사용자에게 전달(Challenge)
② 사용자는 전달받은 난수값을 다시 일회용 패스워드 생성토큰 or 소프트웨어에 입력
③ 사용자는 난수값을 입력 후 나온 출력값을 일회용 패스워드로 입력(Response)
④ 인증 서버에서 사용자에게 전달 했었던(②번과정) 동일한 난수값(Challenge)과 등록된 사용자 정보를 이용해서 OTP를 생성 후 (사용자가 입력한) Response와 비교 후 인증
( ①번의 과정에서 인증서버가 보내준 난수 값은 사용자의 비밀키(혹은 토큰 입력용 패스워드)로 암호화 된다.)


 3- 3) OTP시간 동기화(Time Synchronous) 방식 
 챌린지 리스펀스 방식이 임의의 난수값을 일회용 패스워드의 입력값으로 사용하는 것과 달리, 시간을 일회용 비밀번호의 입력값으로 사용함.
 인증서버와 사용자는 같은시간을 일회용 비밀번호의 입력값으로 넣어야 한다.

[OTP시간 동기화 과정]
① 사용자는 일회용 비밀번호를 생성해 PIN번호(사용자의 패스워드와 비밀키)를 인증서버에 보냄
② 인증서버는 PIN을 통해 비밀키를 찾고 생성된 일회용 패스워드가 수신한 것과 일치하는 지를 파악함
③ 이때, 인증서버와 사용자 토큰사이에 시간이 일치하지않으면 사용자 인증은 실패 일치하면 인증 성공

 일회용 비밀번호의 입력값을 서버로부터 받지 않는 장점을 갖고있으나 서버와 사용자 토큰의 정보를 일치시켜야 하는 단점과 또한 사용자의 수가 많은 경우 여러개의 시간을 동시에 일치시키는 것도 쉬운일이 아니다. 인증서버와 사용자 토크간에 시간정보를 일치시켜야 하는 불편함을 가지고 있다.


3-4) OTP 이벤트 동기화 방식
 앞서 본 시간 정보 대신에 인증서버와 인증 횟수(counter) 기록을 사용자 측과 인증서버간 공유한다. 또한 이 인증 횟수(counter)를 일회용 패스워드 생성 시 입력값으로 활용한다.

 [OTP 이벤트 동기화 과정]
① 인증 서버측과 사용자측간의 counter는 인증시도가 없을 경우 '0'으로 인식함
② 사용자가 OTP를 실행시키면 카운터값이 0에서 1로(1회 실행시켰으므로)증가하며, 이 값으로 입력한 비밀키(사용자의 패스워드라고 생각해도 무방)를 이용해서 암호화 함
③ 암호화 된 결과값이 일회용 패스워드로써 화면에 나타나고, 이 값을 시스템에 입력하면 인증서버로 전달하게 됨
④ 인증서버는 사용자의 인증기록(counter : 1, 1회 인증 했으므로)을 통해 카운터 값을 알아냄
⑤ 카운터 값(인증기록 횟수)을 알아낸 후 사용자의 비밀키(사용자의 패스워드)를 활용해 복호화 함
⑥ 복호화 후 인증서버측에 저장된 사용자의 비밀키(사용자 패스워드)와 일치하는지 파악한 후 인증여부 결정

 시간 동기화 방식은 [서버 - 사용자]간 시간을 토큰 사이에 일치시켰고,
이벤트 동기화 방식은 [서버 - 사용자]간 인증횟수(counter)를 일치시켜야 인증이 수행됨.
( 인증서버는 사용자의 인증기록, counter를 알고있어야 함.)

[ 그림 : 3-4) OTP이벤트 동기화 알고리즘 ]

▶ OTP 이벤트동기화 과정 프로그래밍

1. 헤더 / 함수

2. 메인문

▶ OTP 이벤트동기화 과정 결과

고전암호 시저암호(Caesar)(초안)

1. 시저암호란?
 줄리어스 시저(Julius Caesar, 기원전 100년 경)라는 로마에서 활약했던 장군으로서 그 당시에 사용했으며, 이 사람의 이름을 본떠서 만든 시저암호를 알아보자. 암호학에서는 시저암호 또는 카이사르 암호(Caesar Cipher)라고도 부르기도 한다.

 시저암호는 대칭키 암호 방식이며, 평문에 키 값을 이용하여 치환시키는 일종의 치환 암호방식이라고도 생각할 수 있다. 키 값의 크기만큼 알파벳을 다른 알파벳으로 치환시키는 역할을 해준다. 그러므로 키 값은 영어 알파벳이 26자이므로  26보다 큰 키 값을 사용 시에 0~25사이로 정해질 수 밖에 없다.

그림을 통해 살펴보자
 1) 평문 → 암호문
 평문: water, 키 값: 3






 2) 암호문 → 평문
 암호문 : OOOOO, 키 값 : 3

 그림을 통해 알아보니 평문을 Key 값을 통해서 몇 번째 위치시키는지 결정해주는 방식이다.
 - 암호화 : 평문 + Key만큼 대칭이동
 - 복호화 : 암호문 -Key만큼 대칭이동
만약 Key 값이 26을 주어진다면  Key 값은 0 이나 다름이 없다. 알파벳은 26자 이므로, 원래 평문값으로 되돌아오는 규칙을 주의해야 한다.
 예를들어 key 값이 27인 경우 27 % 26 = 1으로 key 값이 1인 경우와 같은 결과가 나온다.

 시저암호(Caesar Cipher) 알고리즘 구현

 실행결과
1) 암호화

 

2)복호화