암호화

암호화와 전자 서명

 

1. 암호화(Encryption)와 크랙(Crack)

 

♦Encryption란?

암호화는 허가받지 않은 사람들이 쉽게 이해할 수 없도록 데이터를 암호문이라고 불리는 형태로 변환하는 것이다. 이렇게 암호화 된 것을 보기 위해서는 암호화된 데이터를 원래의 형태로 되돌림으로서, 누구나 이해할 수 있게 만드는 과정을 해독한다고 한다.

암호화/해독의 사용은 통신 기술의 역사만큼이나 오래 되었다. 전시에는 전송 내용을 적이 훔치는 것을 막기 위하여 암호 코드가 사용되었다. 단순한 암호 코드에는 숫자를 위해 문자들로 치환하는 것, 알파벳 내에서 문자를 교체하는 것, 그리고 측파대 주파수를 전도시킴으로써 목소리 신호의 파장을 바꾸는 것 등이 포함된다. 좀 더 복잡한 암호 코드는 디지털 신호 내의 데이터 비트들을 재배열하는 매우 복잡한 컴퓨터 알고리즘에 따라 조작된다.

암호화된 신호의 내용을 쉽게 복원하기 위해서는, 올바른 암호 해독키가 필요하다. 이 키는 암호화 알고리즘의 작업을 푸는 알고리즘이다. 또한 암호 코드를 풀기 위한 시도에도 컴퓨터가 사용될 수 있다. 보다 복잡한 암호화 알고리즘이 사용되었을 수록 키가 없이는 통신상에서 엿보기 더 어렵게 되어 있다.

암호화/해독은 특별히 무선통신에서 중요하다. 이것은 무선 회로가 배선에 의한 상대에 비해 도청하기가 더 쉽기 때문이다. 그럼에도 불구하고, 온라인상의 신용카드 구매, 또는 조직 내의 다른 부서들 간의 비밀스런 회사업무 토의 등과 같은 민감한 종류의 거래를 수행할 때 암호화/해독을 사용하는 것은 좋은 생각이다. 일반적으로 암호 코드가 더 강력하면 할수록 더 좋다.(여기서 강력하다는 것은 허가되지 않은 사람들이 그 암호를 깨기가 더 어렵다는 것을 의미한다.) 그러나 암호화/해독의 강도가 증가하면, 그에 다라 비용도 늘어난다.

최근 수년동안 이른바 강력한 암호화라는 것에 대한 논쟁이 이야기되었다. 이것은 본질적으로 암호 해독키 없이는 암호가 깨지지 않는 다는 것을 가리킨다. 암호 해독키는 아마도 안전한 장소에 저장되며 오직 허가된 사람에 의해서만 사용된다. 그러나 악의적인 목적을 가진 사람들은 키 보관용 데이터베이스를 해킹하여 불법으로 키를 획득하고 훔치거나 변조할 것이다.

 

♦암호화 알고리즘(Algorithm)

우리가 사용하는 일반적인 컴퓨터는 윈도우즈 등을 사용할 것이다. 그러나 인터넷이 등장하기 전부터 하나의 시스템을 여러 명의 사용자가 사용하였다. 그럼 이러한 여러 명의 사용자에게 개개인마다 비밀번호를 주어지지 않는 다면 어떻게 될 것인가? 누구든지 똑같은 권한을 가지게 될 것이다.

물론 암호화란 컴퓨터가 나오기 전부터있었다. 특히 암호는 전쟁으로 많이 발전되어왔다. 기원전 쥴리어스 시저가 쓴 암호는 암호화의 대표적인 예라 할 수 있다. 시저의 암호는 아주 간단한 것이었는데 a를 d로 b를 e로 하는 식이었다.

(예) ABCDEFG.......XYZ

DEFGHIJ........ABC

이런 식으로 문자를 3개씩 옮기는 형식의 아주 간단한 것이었으며 요즘에는 이런 방식을 쓰지도 않지만, 쉽게 추출될 것이다.

(예) ABCDEFGH.....XYZ

GJACERHIL.....QWE

이런 식으로 무작위로 한다면 복잡하게 될 jt이다. 실제로 2차 대전 때에 이것이 쓰였다고 한다.

그러나 이것도 여러 번 한다면 쉽게 풀릴 것이다. 가령 영어의 문장에서 가장 많이 쓰이는 것은 e라는 문자라고 하는데 암호화된 문장에서 가장 많이 나온 문자가 k라면 아마도 e는 k라고 생각될 것이다. 이런 식으로 금방 암호문이 해독될 수 있을 것이다.

 

♦암호화의 용어들

- 평문(Plaintext) : 암호화하지 않은 문장

- 암호문(Ciphertext) : 암호화된 문장

- 키(key) : 암호화시키기 위해서 매개체 역할을 하는 것.

- 공개키(Public key) : 모든 사람이 볼 수 있는 키.

- 비밀키(Private key) : 자기 자신만이 볼 수 있는 키.

- 대칭 암호 알고리즘 : 비밀키를 쓰는 것을 관용 암호 알고리즘 혹은 대칭 암호 알고리즘이라고 한다. 데이터의 암호화/복호화시 동일한 키 사용

- 공개키 암호 알고리즘 : 공개키를 쓰는 것을 공개키 암호 알고리즘 혹은 비대칭 암호 알고리즘이라고 한다. 데이터의 암호화/복호화시 서로 다른 키를 사용한다.

- 암호화 : 평문을 암호문으로 만드는 것.

- 복호화 : 암호문을 다시 평문으로 만드는 것.

- DES(Data Encryption Standard) : 데이터 암호화 규격.

 

♦대칭키 암호화 알고리즘

데이터 처리 형식에 따라 스트림 암호화 알고리즘과 블록 암호화 알고리즘으로 나눈다.

- 스트림(stream) 암호화 알고리즘 : 암호화의 단위가 비트 또는 문자이며 모든 평문에 동일한 암호화 함수가 적용되어지는 블록 암호화와는 달리 평문의 비트 또는 문자가 암호화되어짐에 따라서 상이한 암호화 함수가 적용된다. 스트림 암호에서의 암호화는 비밀키와 평문 그리고 현재의 스트림 암호 시스템 상태와 연동하여 작동된다. 즉 비밀키와 현재의 상태 변수로부터 도출되는 키 수열이 평문과 결합되어져 암호문이 생성되게 된다.

- 블록 암호화 알고리즘 : n비트의 평문 블록을 m비트의 키를 가지고 n비트의 암호문 블록을 바꾸어 주는 것이라고 말할 수 있다.

현재 가장 보편적으로 사용되고 있는 대표적인 대칭형 블록 암호 알고리즘은 1977년 미국에서 연방 정보처리 표준 46으로 채택된 DES를 들 수 있다.

DES는 64비트 키(실제는 56비트)를 적용하여 64비트의 평문을 64비트의 암호문으로 암호화시키는 대칭형 블록 암호이다.

DES를 비롯한 대부분의 블록 암호화 알고리즘들은 Feistel구조를 가진다. 블록 암호화 알고리즘 중에는 DES의 해독과 국내 암호화 알고리즘 표준의 필요성에 의해 KISA 주관 암호 전문가들이 개발한 SEED 알고리즘도 있다.

 

♦공개키 암호 알고리즘

가장 널리 쓰이는 것으로는 RSA를 들 수 있고 기존의 관용 암호 알고리즘이 깨지는 것을 방지하여 만든 암호 알고리즘이다.

< 기본 알고리즘>

 소수 p와 q를 만들고 이것은 비밀로 유지한다.

 n=p*TIMESq, z=(p-1)*(q-1)이고 n은 일반에 공개한다.

 z와 서로소인 관계인 수 d를 만들고 d는 비밀로 유지한다.

 e*d≡1mod z인 e를 찾은 후 e는 일반에 공개한다.

<소수와 mod 연산>

소수는 더 이상 나누어지지 않는 수를 뜻한다. 가령 4는 2로 나누어지므로 소수가 아니다.

예를 들어 2,3,5,7...등 더 이상 나누어지지 않는 수가 그 예이다.

mod는 a-b=M*c 일 때 a는 법 m에 관해서 b와 합동이라고 하고 a≡b mod M

기호라고 쓴다. 예를 들어 32-7=5*5 이다.

이것을 mod로 표현하면 32≡7 mod 5로 표현할 수 있다.

 

예를 들어보자.p를 3이라 하고 q를 11이라 하면 n=3*11이므로 n=33이고

z=(3-1)*(11-1)이므로 z=20이다. 이때 z와 서로소인 d를 7이라 하면 e*7≡1 mod 20에서 e는 3이 된다.

그러면 RSA는 어떻게 암호화하는가? 평문을 P라 하고 암호문을 C라 하면 C=P mod n이 되고 암호화를 복호화 하는 것은 P=C mod n이 된다. 위 예제에서의 평문은 p이고 n=33과 e=3은 공개한다해서 공개키라고 한다.

 

위의 예제는 아주 간단한 것이지만 실제로 이 암호 알고리즘은 키가 128 비트 이상을 사용하므로 깨지기가 아주 어려워 특히 현재 전자 상거래에서의 인증 등에 쓰이고 있다.

이 암호 알고리즘의 수학적 기반은 대수학에 기초하고 있음.

처음이 있으면 끝이 있고, 만드는 것이 있으면 부수는 것이 있는것처럼 암호화해 놓은 것을 해체하는, 특히 불법적으로 깨는 것을 크랙이라고 한다. 여기에서는 리눅스나 유닉스에서 패스워드를 암호화 알고리즘인 3중 DES를 깨는 법에 대해 간단히 소개한다.

리눅스나 유닉스는 패스워드를 암호화하여 /etc/shadow란 곳에 파일을 저장하고 있다.

이 파일만 얻을 수 있다면 암호 알고리즘을 알고 있으므로 패스워드를 알 수 있다.

물론 /etc/shadow 파일은 비정상적인 방법(해킹 등)을 통해 얻어야 하겠지만 이 파일만 얻으면 모든 계정에 대한 패스워드를 알 수 있을 것이다.

crack jack이란 프로그램이나 john the ripper, ntucrack 등의 프로그램으로 간단히 깰 수 있다.

리눅스나 유닉스에서 쓰는 3중 DES는 암호화는 가능하지만 복호화 시킬 수는 없다.

따라서 3중 DES에서는 사용자가 입력한 암호를 복호화하여 인증하지 않고 우리가 아이디와 패스워드를 넣으면 암호화시켜서 shadow 파일에 있는 암호화 된 패스워드 문자열과 비교하여 맞으면 인증을 하는 방식이다. 위의 크랙 프로그램은 대부분 crypt()함수를 이용하여 만든다.

char *crypt(const char *key, const char *salt);

여기처럼 salt 키라는 것이 필요한데 일반적으로 암호화 된 패스워드의 맨 앞부분 두 개 문자가 salt 키다. 내 아이디에 대한 쉐도우 파일에 대한 것은 다음과 같다.

koen:01oh83XTWmt0.:11179::::::

그런 여기서 salt 키는 01 이다. 그리고 내 패스워드는 crrack0이다.

crypt("crack0","01");

이렇게 하면 실제 암호문장을 crypt() 함수가 암호화 된 패스워드를 되돌린다.

그럼 여기서 암호화한 패스워드를 출력하는 프로그램을 만들어보자.

 

<crack.c파일>

#include <unistd.h>

main(int argc, char **argv)

{

char buf[1024];

strcpy(buf,crypt("crack0","01"));

printf("password is %s∖n",buf);

}

이 프로그램은 첫 번째 인수를 단어로 받고 두 번째 인수로는 salt키를 받는다.

컴파일시에 -lcrypt 라고 옵션을 줘야 한다.

$ gcc - crack crack.c-lcrypt 엔터키

$ ./crack 엔터키

password is 01oh83XTWmt0.

위에서 선보였던 암호화 된 패스워드와 똑같이 출력할 것이다.

이런식으로 cryptc의 첫 번째 인자에 aaaaaaa~zzzzzzz을 계속 넣어주고 salt 키만 주어진다면 알파벳으로 7자로 된 암호는 깰 수 있을 것이다.