|
http://www.hackerschool.org/HS_Boards/zboard.php?id=Free_Board&no=1682 [복사]
<암호의 발생과 발전>
암호학이란
암호(cipher)란 원문(plaintext)을 암호문(ciphertext) 으로 변환하여 비밀스러운 글을 쓰는 방법을 말한 다. 암호를 제작(encipher)하고 해독(decipher)하는 과정을 제어하는 것을 키(key)라고 한다.
암호시스템은 보다 알아보기 어렵고 효과적으로 메시지를 변형시키는 방법들을 연구하는 부 분(cryptography)과 주어진 한정된 정보 아래서 키 값을 모른 채 암호문을 복호화하는 연구 를 하는 부분(crytanalysis) 으로 하나의 학문인 암호학(crytology)을 이루고 있다.
암호의 필요성
암호 이야기
암호는 인류역사를 통해 주로 군사 외교적인 목적에 사용되어왔다.
암호에 수학이 사용된 것은 20세기에 들어서이다. 그 이전에도 고대 그리이스 시대 부터많 은 군주와 교황들이 암호를 담당하는 부서를 가지고 있었지만 그런 암호들은 수학을 전혀 배우지 않은 사람이라도 체계적인 분석능력과 끈기만 있다면 해독할 수 있는 것들이었다. 또한 20세기 초반에 무선통신이 사용되기 전에는 적군의 암호문을 탈취하는 효과적인 방법 이 존재하지 않았다. 물론 적군의 연락병을 적군의 영토 안에서 어떻게 해서든 붙잡지 않는 다면 말이다. 그러므로 적군의 통신을 가로채는 일은 사실상 불가능하다고 말할 수 있을 정 도로 어려웠으며 어쩌다가 간신히 가로챈 경우에도 중요한 일부분만 암호문으로 적혀있었기 때문에 암호를 해독해야하는 필요성은 그다지 크지 않았다. 그러던 것이 무선통신의 발명으 로 전혀 새로운 상황이 되었다. 이제는 전파로 날아 다니는 적군의 암호문을 얼마든지 수신 할 수 있게 되었다. 전선에서는 날마다 많은 양의 암호문이 입수 되었으며 이에 따라서 즉 각적으로 방대한 양의 암호문을 해독하는 것이 필요해 져서 일차대전과 이차대전의 사이에 각국은 앞다투어 참모본부 안에 암호해독 부서를 설치하게 되었다. 2 차세계대전에서 양측 은 매우 정교한 암호를 사용했는데 연합군이 승리한 주요 원인중 하나가 암호전에서 승리했 기때문이라고 한다.
전쟁이 끝난후 비군사용 암호가 급격히 늘어나기 시작했다. 컴퓨터와 통신기술의 발달에따 라 컴퓨터통신 전자우편 은행간 대금결제 등에 쓰이는 민수용 암호가 널리 쓰이기 시작했 다.
신용카드나 현금카드의 비밀번호는 아무에게나 알려 줄 수 없는 중요한 정보이다. 남 몰래 지키고 싶은 정보는 외부적으로 물리적으로 완벽하게 차단하여 지킬 수 있으나 필요에 따라 서는 아무도 모르게 전달하고 싶은 사람에게만 정보를 전달해야할 필요를 느낀다. 전산망을 통해 신용카드의 번호 등을 보낼 때가 그 예이다. 누군가가 이 정보를 도청하여 사용하면 개인적으로 큰 손해를 볼 수 있다. 은행카드의 비밀번호 등을 생각하면 정보화 사회에서 정 보가 곧바로 재산이라는 점이 피부로 다가올 것이다. 따라서 정보화 사회가 될수록 이러한 정보를 비밀리에 전달하는 것이 점점 그 중요성을 더 해간다.
암호의 역사
사이테일
기언전 5세기무렵 고대 그리스인들이 쓰던 최초의 암호문.
둥근 막대기에 기다란 양피지를 둘둘 말아 가로로 글을 써놓은 뒤 다시 펴면 셀로 쓰인 글자 순서가 뒤죽박죽이 된다.
똑같은 굵기의 막대기에 양피지를 감으면 원래의 통신문이 나타난다.
시저 암호문
기원전 1세기 로마제국 의 시저 황제가 고안한 글자 바꾸기 암호 법. 알파벳을 일정하게 건너뛰어 쓰는 방법이다. 예를 들면 home 를 세칸씩 건너뛰면 krph가 괸다.
비지넬
16세기 프랑스인 비지넬이 만든 최초의 근대 암호.
복잡한 표를 미리만들어두고 이에따라 암호를 조립하거나 푼다.
예를 들면, 암호의 열쇠가 HOME일 경우 '... H.O.M.E.H.O....'의 순서에 따라 ENEMY라는 원문의 암호문 을 찾으면 LBQQF가 된다.
난수표
가장 많이 알려진 암호법.
0부터 9까지의 수를 완전히 무질서하게 배열했다.
예를 들어 5, 7이란 난수 암호를 받으면 난수표에 따라 이는 3, 9 로 풀이되는데 만일 3이 내일, 9가 공격이란 뜻으로 미리 약속되 어 있으면 5, 7은 내일 공격이라는 뜻이 된다.
DES
77년 개발된 글자 바꾸기식 전산 암호법.
다단계의 글자 바꾸기 과정을 거쳐 암호문을 만들어낸다.
암호를 만드는 열쇠와 이를 푸는 열쇠가 같다.
RSA
78년 개발된 전산 암호법.
인간과 컴퓨터기 가장 계산하기 힘들다는 소인수분해를 이용했다.공개열쇠와 비밀열쇠를 따로 두어 공개열쇠는 한사람또는 다수의 사람에게 공개하며 비밀열쇠는 자신만이 갖는다. 다른사람이 공개열쇠로 암호문을 보내면 이를 비밀열쇠로 따서 볼 수 있다.
암호이론
암호의 이용
크게 두가지 용도로 쓰인다.
보안성(security)
자료의 보안성을 유지하기위하여 도청을 방지하기위해 암호가 사용되는 경우이다.
확증성(authenticity)
자료가 송신도중 제 삼자의 개입으로 인한 교란을 방지하기 위해 사용된다.
암호화기술
암호시스템의 주 목적은 "쉽게 읽을 수 있는 내용을 알아보기 힘든 상태로 변화시키는 것이 다" 라고 말할 수 있다.
초창기
암호는 군사나 외교와같은 한정된 부분에 사용되었기 때문에 역사에 비해일반인들에게 알려진 시기는 늦은 편이다.
초창기 암호제작 기술을 보면 크게대입(substitution)과 치환(transposition)방식으로 나누어 볼 수 있다.
대입법
대입방식은 한 문자를 다른 문자로 교체하는 방식으로 제1차세계대전때 플레이페어(Playfair)라는 암호시스템으로 사용되었다.
치환방식은 평문의 문자 순서를 일정한 규칙에 따라 바꾸는 것으로, 이 결과 평문에 있던 문자만이 그리고 그 갯수 만큼만 암호문에 출현하게 된다.
예로 "나는 당신을 사랑합니다"의 영어표현인 I Love You를 떠올려 보자. 누구든 이 문 장의 뜻을 쉽게 알 수 있다. 그러나 영어 알파벳을 숫자 26개로 대응시켜 (A=1, B=2… Z=26) I Love You를 9 12 15 22 5 25 15 21로 바꾸어 생각한 뒤 3을 더해(12 15 18 25 8 28(28=26+2) 18, 24)로 변경하면 그 뜻은 알기 힘든 L ORYH BRX로 바뀐다. 만일 메시 지를 수신할 사람에게 3을 더했다는 사실을 알려준다면 수신자는전송된 암호문에서 3을 뺌 으로써 원래의 메시지를 읽을 수 있게 된다. 위에서 얘기한 내용을 좀더 체계적으로 얘기 하면 다음과 같다.
1.원래의 메시지를 평문(plainte.t)이라고 한다. ->I Love You
2.암호화하여 바뀐 메시지를 암호문(cipherte.t)이라고 한다.->L ORYH BRX
3.평문에서암호문으로 바꾸는 과정을 암호화(encryption)라 한다. 위에서는암호화 방식 으로 평문에 3을 더했다.
4.암호문에서 평문으로 바꾸는 과정을 복호화(decryption)라 한다.
5.암호화와 복호화 과정에서 알고리즘과 함께 키가 사용된다.
고정된 알고리즘에 동일한 평문을 입력해도 다른 키 값을 사용함으로써 암호화된 결과를 판이하게, 다르게 만들 수 있다. 위의 예의 경우 3이 키로 사용되었다.
현대 암호시스템의 경우 암호화 및 복호화 알고리즘은 공개하고 키의 미공개에 암호의 안전성을 두고 있다. 따라서 현대암호시스템이 제공하는 안전성은 키의 보관이 큰 비중을 차지하고 있다.
DES
이들 두 방식이 혼합하여 사용된 방식을 프로덕트 사이퍼(product cipher)라고 한다.
각각 대입 방식과 치환 방식을 행하도록 설계된 실린더를 여러 개 연결해 놓은 로터머신(roter machine)이 이들 방식을 택해 2차 세계 대전에 사용되었다.
비밀키 알고리즘은 암호화 알고리즘과 복호화 알고리즘에 동일한 키를 사용한다. 따라서 송신자나 수신자 모두 동일한 키를 나누어야 한다.
대표적인 비밀키 방식으로는 전세계적으로 널리 사용되고 있는 DES를 들 수있다.
1970년대에 들어서면서 상용 컴퓨터가 널리 보급되고 기업들은 정부에서 보증하는 믿을수 있는 민간용 암호를 요구하게 되었다. 이렇게 해서 나온 것이 지금도 Unix Password 확인시에 사용하는 DES(Data Encryption Standard)이다. DES는 기밀이 아닌 정보를 보호할 목적으로 설계된 블럭단위 암호시스템이다.
암호가 급속한 발전과 더불어 일반인 사이에서 연구되어진 시기는 컴퓨터의발전과 함께 공개키 개념이 처음 선보인 1970년대이다. 이후로 현대 암호시스템의 양대 산맥인 비밀키 방식과 공개키 방식이 서로 장단점을 제공하며 비약적인 발전을 가져 왔다.
공개키방식 암호와 정수론
발생배경
1970년대에 열쇠가 공개된 암호 체계가 새로이나왔다. 암호체계는 기본적으로 암호화과정 과 암호해독과정을 거친다. 대부분의 암호 체계에서는 첫째과정을 할수있는 사람은 누구나 둘째과정도 할수있다 따라서 암호화방법을 적에게 공개한다는것은 상상할수도 없었다. 그러 니 열쇠를 알려주는 암호체계 제안자들은 이러한 생각이 옳지않다는것을 깨달았다. 암호화 방법을 알더라도 해독하는 법을 알아내지못한다면 암호화방법을 공개해도 큰 피해는없을 것 이기때문이다.
장점
공개키 방식에서 각 사용자는 다른 사용자에게 공개할 공개키와 자신이 보관할 비밀키를 각자 선택한다. 만약 비밀키의 안전성만 제공되면 공개키로 생성된 암호문을 통신상에서 불법적으로 얻었어도 해독하기 어렵다. 왜냐하면해독에는 반드시 공개키에 해당되는 비밀키 를 알아야만 가능하도록 알고리즘이 설계되어 있기 때문이다. 공개키 시스템의 대부분은 그 안전성을 해결하기 어려운 수학적 문제에 기반을 두고 있다. 따라서 비교적 시스템 자체 의 구조는 비밀키에 비해 간단하고 명료하다.
이론
공개키 개념은 1976년 디피 헬만(Diffie Hellman)에 의하여 처음으로 제안되었다. 암호론은 수학적으로는 Complexity Theory 의 기본 가설인 One Way Function 의 존재를 가정하고 있다. n 개의 Bit 를 변수 x 로써 입력했을 때에 함수의 값 f(x) 을 얻는데 필요한 최소한의 연산의 갯수가 n 을 변수로 가지는 다항식이지만, y 가 주어져 있을 때에 f(x)=y 가 되는 x 를 찾는데 필요한 최소한의 연산의 갯수가 n 을 변수로 가지는 어떤 차수의 다 항식보다 많은 것을 One Way Function 이라고 정의한다. 즉 암호문으로 만드는 과정은 간 단하지만 적군이 암호문을 해독하는 것은 어렵다는 것이다. 1980년대에 정수론을 이용하여 제안된 많은 공개열쇠 암호는 소인수분해 등의 문제가 One Way Function(곱셈과 소인수분 해) 이라는 가정하에 나오게 되었다. 공개열쇠라는 용어는 함수 f 와 y 를 공개해도 f(x)=y 가 되는 x 를 찾기가 어렵다는 의미이다. 소인수분해에 기초한 공개열쇠 암호는 제안자 세 사람의 이름 첫글자를 따서 RSA 암호라고 부른다. 이들이 만든 회사 RSA Inc. 는 얼마전 에 일억불 정도에 팔렸다. 요즘에 인기있는 Netscape 나 전자화폐, 전자주민등록증등도 대 개는 RSA 암호를 사용한다. One Way Function 이 존재해야만 Zero-Knowledge Proof 존 재할 수 있다는 것을 증명한 Avi Wigderson 은 1994년도 ICM 에서 Nevanlinna 상을 받았 다. Zero- Knowledge Proof 란 라는 주장을 상대방에게 여러번에 걸쳐서 납득시키지만 x 자체에 관한 정보는 주지 않는다는 의미이다. 좀 더 정확하게 말하면 이런 여러번의 설득과 정에서 상대방이 x 에 관해서 얻는 추가 정보를 가지고는 f(x)=y 가 되는 x 를 찾는데 필 요한 최소한의 연산의 개수가 n 의 다항식이 결코 되지 않는다는 의미이다.
RSA
RSA는 DES에 비해 높은 안전성을 제공하고 있다. RSA와 같은 공개키 시스템은 메시지 와 키 값을 증가시킬 수 있도록 설계되어 있기 때문에 항상 일정한 안정성을 제공해 준다.
이와같은 암호에 기본적인 이론을 재고하는 수학이 정수론이다.이런 아이디어를 수학적으 로 말하면 암호화과정이 하나의 함수라고 볼때 암호해독 과정은 그 함수의 역함수를 찾는 작업이다. 따라서 역함수를 구하기 매우 어려운 함수(陷穽函數)가 무궁무진하듯이 해독이 거 의불가능한 암호도 많은것이다. 암호에 쓰이는 계산방법은 우리가 알고 있는것과는 다르다. 하지만 모르는 사이에 우리는 메일 이런 계산을 하고있다. 시간계산의 예를보자 5 시에서 3 시간후는 8시이고 이것을 식으로 쓰면 3+5=8 이다. 그런데 11 시에서 5시간후는 4시이므로 11+5=4가된다 이것을 12가법(NOD) 인계산이라고 한다. 12가 아닌 다른것도 법이 될수 있으 며 덧셈과 뺄셈외에도 곱셈과 나둣셈도 가능하다. 이러한 계산과 관련돼" 페르마의 작은 정 리 라는것이있다. X가 소수일때 a의 x제곱은 x 를 법으로하는 a와 같다는것이다.요일계산을 예로 들면(이때 7 이 법이다)1 일이 월요일인 달의 21 일은 3 의 7승이므로 이정리에 의 해 3일과 같은 요일 즉 수요일이 된다. 78년 미국 mit 의 리베스트 샤미르에이들만이 제안한 RSA암호 체계는 페르마의 작은 정리와 함정합수의 개념을 이했다.
암호화에 사용되는 법과 암호화열쇠는 공개하지만 암호문을 가로챈 제3자는 해독열쇠가 없어 암호를 읽을 수가 없도록 만든 것이다. 이때 열쇠를 알아내는 방법은 자연수의 소인수 분해와 관련돼 있는데 수가 커지면 이것은 현실적으로 불가능하다. 예를들어 1초에 1 벡만 번 연산을 할수잇는 컴퓨터를 이용 현대 알려진 가장 빠른 방ㅂ 으로 계산해도 1 백자리 숫 자를 소인수분해하는데는 1 백년이 걸린다고한다. 더구나 재래식 방법으로는 우주의 역사보 다도 긴시간이 필요하다 따라서 이러한 암호체계는 소인수분해에 대한 새료운 수학적 발견 이 없다면 깨뜨리기가 불가능한것이다.
실제로 정수론을 전공하는 많은 수학자들이 효과적인 소수판정방법과 소인수분해방법을 찾 는 연구를 하고 있으며 연구결과가 군사기밀혹은 기업비밀로 분류되기도 한다. 소수판정방 법의 연구가 안정한 암호화 열쇠를 만들기 위해 필요한 연구라면 소인수 분해방법의 연구는 이러한 암호체계를 깨뜨리기 위해 필요한 연구라고 할수 있다. 한편 미국 버클리대학의 렌 스트라는 최근 타원곡선이론을 써서 큰 수를 효과적으로 소인수분해하는 기존의 방법과는 전혀 다른 새로운 방법을 발견하여 수학계에 충격과 희망을 주고 있다.
타원곡선이론이란 복소수평면에서 타원곡선의 연산구조를 연구하는 이론이다. 수학계에 는 이처럼 수학자쳬의 심오함과 아름다움에빠져 연구한 결과들이 뜻하지않게 응용돼 각광을 받는 경우가 있다. 많은 수학자들은 그 심오함때문에 타원곡선을 반세기 이상 연구해어왔지 만 누구도 이것이 소인수분해와 연관될것을예상하고 연구하지는 않았다. 페르마도 그의정리 가 암호에 쓰일 것이라고는 꿈에도 생각하지 못했을 것이다.
응용
공개키 시스템은 비밀키 방식과 비교해 전자서명이라는 기능을 제공한다.
앞서 본 암호와 시스템에서는 수신자의 공개키로 임의의 사람이 메시지에 암호를 걸어서 보내면 수신자 B가 자신의 비밀키로 메시지를 복호화 하였는데전자서명 방식에서는 송신 자가 자신의 비밀키를 이용해 메시지를 복호화알고리즘에 돌린 결과를 메시지와 함께 전 송한다. 이 때 수신자 B는 송신자A의 공개키를 이용해 사인된 메시지를 암호화 알고리즘 에 돌려 함께 전송되어온 메시지와의 관계로 사인의 진실 여부를 확인해 볼 수 있다.
한편 인증 기능의 구조를 서명 등의 [본인 확인]의 케이스로 보면 -- ① 수비 기능에서는 복 호의 역할을 다한 비밀 키를 작용시켜 서명문을 작성한다. ② 그 서명문을 받은 사람은 서 명인이 공개하고 있는 공개 키를 작용시켜 서명이 진짜인가, 어떤가를 확인한다는 것이다. 공개 키를 작용시킴으로써 만약 암호가 풀린다면 그 공개 키에 대응한 비밀 키로 서명되었 기 때문이어서 그 비밀 키는 서명자만의 비밀이기 때문에 본인 확인이 끝난 것으로 된다는 이론으로 된다.
PGP의 태동과 활용 사례
E-Mail 메시지를 암호화함으로써 메시지를 누군가가 중간에서 빼간다 하더라도 그 내용을 알아 볼 수 없게 만들고 해시함수를 사용해 메시지의 변경여부도 알아낼 수 있다. 이러한 개념으로 만들어진 것이 바로 PGP(Pretty Good Privacy)이다. PGP는 필립 짐머만(Philip Zimmermann)이라는 한 개인에 의해서 1991년에 만들어졌다 하지만 PGP가 처음 나왔을 때 문제가 발생했다. 사용하는 프로그램중에 공개키 알고리즘으로 사용한 RSA(1977년에 개발 된 공개 암호 해독법으로 암호화와 증명에 사용됐다. 개발자인 Ron Rivest, Adi Shamir, Leonard Adelman 등의 성 머리글자를 따서 RSA라고 이름을 붙였다.) 알고리즘이 이미 특허 등록된 상태였기 때문에 이를 사용한 PGP를 공개버전으로 만들 수 없었다. 그래서 필은 RSA의 개념을 그대로 사용해 C언어를 사용한 프로그램을 자신이 직접 구현, PGP안에 삽입 했다.
|
Hit : 11588 Date : 2003/12/04 11:26
|
22011, 
17/1101 
