암호 입문

알기 쉬운 암호 이야기

Windows 95/98/NT/2000/XP, Netscape Navigator, Lotus Notes를 비롯하여 많은 OS, 소프트웨어에 사용되고 있는 RSA 공개키 암호 및 자유롭게 사용할 수 있는 PGP 등, 이론적 배경을 이루고 있는 것은 실제 소인수분해라고 할 수 있다.

1. 시저암호(종래의 암호로 관용암호, 비밀키 암호, 공통키 암호)

시저 암호는 원시적 암호이지만, 현대 암호의 배경을 이해하는데 좋은 예이다. 시저 암호는 로마 황제 줄리어스 시저가 사용했던 암호이다. 원리는 간단하여 알파벳을 어느 수(또는 키 값)만큼 시프트 시켜 사용한다. 예를 들어,

THE DAZED BROWN FOX QUICKLY GAVE JUMPS

라는 평문(암호화되기 전의 문장)을 3문자씩 시프트 시켜 암호화시키면

WKH GDCHG EURZQ IRA TXLFNOB JDYH MXPSV

와 같이 의미 없는 문장으로 변환된다. 그러나 해석이 용이하기 때문에 문장 내 공백을 제거하여 다음과 같이 사용하는 편이 좋을 것이다.

WKHGDCHGEURZQIRATXLFNOBJDYHMXPSV

복호화(암호문을 평문으로 되돌리는 것) 방법도 단순하여 3문자만큼 원래대로 되돌리면 다음과 같이 된다.

THEDAZEDBROWNFOXQUICKLYGAVEJUMPS

공백을 제거한 상태이므로 단어의 구분이 어딘지 알 수 없지만, 눈여겨보면 의미 있는 구절 단위로 처리를 하게 되면 결국 원문을 파악할 수 있다. 이 예에서 암호를 푸는 키는 3이다.

그러나 알파벳은 모두 26자로, 키로 주어진 3이라는 숫자를 몰라도 1, 2, 3, 4, 5…라는 순서대로 풀어나가면 결국 의미 있는 문장에 도달하게 되므로 해독이 간단하는 것을 알 수 있다.

암호화된 문장을 입력하면, 1, 2, 3…라는 순서대로 조사하여 사전 파일에 등록된 단어와 비교하여 의미 있는 문장을 출력하는 프로그램을 작성할 수 있다.

그러나 이 방법은 현재 인터넷으로 대표되는 네트워크 환경에서는 불리하다. 결국

(가) 통신을 원하는 상대의 수만큼 key가 필요하거나,

(나) 복호 방법을 알면 암호화 방법도 드러난다.

암호는 당연히 군사 및 외교 등에 한정되어 사용되어 왔다. 그러나 네트워크의 발달과 함께 일반인도 인터넷 쇼핑을 할 때, 신용카드 번호의 송신을 수행할 경우에도 통신의 비밀을 확보할 필요가 있어 네트워크에 대해서도 암호가 사용되게 되었다.

네트워크 환경에서도 극히 제한된 사용자뿐만 아니라 불특정 다수의 사용자도 존재한다. 따라서 암호를 사용하여 통신을 하려는 모든 사용자가 각각 암호화 키, 복호화 키를 소지한다는 것은, 네트워크에 존재하는 모든 사용자가 서로 통신을 하기 위해서 방대한 숫자의 키가 필요하게 되므로 실용적이지 못하다. 또한 복호화 방법을 알면, 암호화 방법도 파악할 수 있으므로 마음만 먹으면 타인의 계좌에서 돈을 인출하는 등의 범죄에 노출되기 쉽다. 이러한 문제에 대응하기 위해 제안된 암호가 공개키 암호라고 할 수 있다.

2. 공개키 암호(새로운 암호)

1976년 스탠포드 대학의 Diffe, Hellman은 공개키 암호의 개념을 발표하였다. 공개키 암호는 자신에게 보내오는 메시지로서 암호화키를 대담하게 공개한다. 이러한 암호화키를 공개키라 부르며 책임이 확실한 기관(예를 들어 금융감독원과 같은 장소)에서 공개하여 누구라도 조사할 수 있도록 한다. 이에 대하여 공개키로 보내온 메시지를 해독하기 위한 복호화키는 비밀키라고 불린다. 비밀키는 자기 자신만 아는 키이다. 이렇게 하면 모든 사람들이 자신만이 아는 비밀키를 하나만 가지고 있으면 된다. 네트워크의 누구하고라도 상대방의 공개키를 조사하여, 그 키로 암호화한 메시지를 보내는 것으로 통신이 가능하게 된다.

그러나 시저 암호에서와 같이 종래의 방법으로는 암호화키를 알게 되면 복호화키도 드러나게 되므로 안전성 문제가 발생하게 된다. 여기서 암호화하는 키를 알아도, 복호화하는 키를 해독하는 것은 거의 불가능한 "일방통행"의 함수가 필요하게 된다. 이러한 "일방통행"의 함수로서 소인수 분해를 예로 들 수 있다.

3. 인증

그러면 공개키 암호에서는, 누구라도 자신에게 메시지를 보내올 때, 키(공개키)를 공개하고 있으므로 인증이라는 절차가 필요하게 된다.

예를 들어, 대학생 삼돌이가 삼순이에게 줄 선물을 구매하기 위하여 인터넷 구매를 하고자 한다. 그러나 돈이 부족하여 짝퉁 가방을 주문하려고 했을 때, 다른 사람에게 주문 내용이 알려지면 부끄러워 암호화시켜 주문을 하려고 한다. 여기서

"주례동의 삼돌이라는 사람인데, 짝퉁 가방 하나 부탁합니다."

라는 메시지를 쇼핑몰에서 공개하고 있는 공개키로 암호화시켜 송신한다. 그러나 이것만으로는 부족하다. 공개키 암호에서는 암호화를 위한 키(공개키)를 공개하고 있으므로 누구라도 알 수 있다. 구지 삼돌이가 아니라 꾀돌이도

"주례동의 삼돌이라는 사람인데, 짝퉁 가방 하나 부탁합니다."

라는 메시지를 쇼핑몰에 공개키를 이용하여 주문 내용을 암호화시켜 보낼 수 있다.

그러므로 이 메시지에 삼돌이라고 되어 있어도 정말로 삼돌이가 보낸 주문한 것이라는 것을 확인하지 않으면 안 된다. 따라서 삼돌이는 비밀키를 이용하여 다음과 같이 2개의 메시지를 보낼 수밖에 없다.

① “주례동의 삼돌이라는 사람인데, 짝퉁 가방 하나 부탁합니다.” 라는 메시지에 쇼핑몰에서 공개하고 있는 공개키로 키를 건다.

② “나는 삼돌이랍니다.” 라는 메시지에 삼돌이의 비밀키로 키를 걸고, 다음으로 쇼핑몰의 공개키로 다시 한 번 키를 건다.

귀찮으므로

① 쇼핑몰의 공개키 「“주례동의 삼돌이라는 사람인데, 짝퉁 가방 하나 부탁합니다.”」

② 쇼핑몰의 공개키 『삼돌이의 비밀키「“나는 삼돌이랍니다.”」』

결국은 “나는 삼돌이랍니다”라는 메시지를 이중으로 키를 걸고 있다. 메시지를 전해 받은 쇼핑몰은 쇼핑몰의 비밀키로 메시지를 열어 본다.

① “주례동의 삼돌이라는 사람인데, 짝퉁 가방 하나 부탁합니다.”

② 삼돌이의 비밀키 『“나는 삼돌이랍니다.”』

라는 메시지를 볼 수 있게 된다. 그러나 “나는 삼돌이랍니다.”라는 메시지는 이 시점에서 삼돌이의 비밀키로 둘러싸여 있으므로 의미 불분명한 메시지로 보일 것이다. 그러나 한 쪽의 메시지에서는 “주례동의 삼돌이라는 사람인데, 짝퉁 가방 하나 부탁합니다.”라고 되어 있으므로 쇼핑몰은 삼돌이의 공개키로 의미 불분명한 메시지를 열어본다. 결국 쇼핑몰은 “나는 삼돌이랍니다”라는 메시지를 확인하게 된다. 삼돌이의 비밀키는 본인만 알고 있으므로 분명히 본인으로부터의 전해 온 메시지라는 것을 확인할 수 있다.

4. 소인수분해

소인수분해는 이미 알고 있듯이

를 예로 들 수 있다. 이러한 것이 암호 이론의 근간을 이룰 수 있는지 의문을 가질 것이다. 그러나 이 정도는 소인수 분해가 가능하겠지만, 자리수가 200정도 되면 소인수분해가 그렇게 간단하지 않다.

그럼, “순서대로 1, 2, 3, 4…으로 나누면 되지 않겠는가?” 라고 생각할 수 있다. 그러나 200 정도의 자리수를 가지는 숫자를 소인수분해하면 현재 최고속의 슈퍼컴퓨터를 사용하여도 수십억 년 정도 소요되어 현실적이지 못하다.

소수는 2 이외는 모두 홀수이므로 “2, 3, 4, 7, 9, 11, 14…”와 같이 2 이외에는 2씩 건너뛰며 나누게 되면 계산의 효율은 두 배로 늘어날 것이다. 그러나 이렇게 하여도 수십억년 걸리던 시간이 절반으로 줄어 들뿐 달라질 것은 없을 것이다. 수억년 걸려 암호를 해독했다 하여도 그 때쯤이면 해독된 암호는 의미가 없을 것이다.

구체적 설명은 어렵지만, 현재 200 정도의 자리수를 가지는 수자라고 해도 소수인지 아닌지 정도는 비교적 단시간 내에(5분정도) 효율적으로 판단할 수 있다. 어떤 숫자를 조사하였을 때, “소수일 확률은 99.9999999%”라는 숫자가 있다고 가정하자.

“이 숫자는 확률이 높으므로, 당연히 소수일 것이다”라고 생각하는가? 아니면 “판정의 방법이 잘못된 것으로 소인수분해는 가능하지 않는가?”라고 생각할 수도 있다.

일반적으로 전자일 가능성이 높다. 거의 소수라고 생각하여 틀림이 없을 경우는 이러한 수자를 유사소수라고 한다. 이에 대해 소인수분해가 가능한 숫자를 합성수라고 부른다.

여기서 자리수 100정도의 숫자를 적당히 선택하여 유사 소수인지 판정하여 보자. 만약, 유사 소수가 아니라면 바로 다음의 수를 마찬가지로 판정한다. 컴퓨터를 사용하면 수 만개의 숫자를 일순간에 판정할 수 있다. 이와 같이 하여 걸러낸 유사 소수 두 개를 선택한다.

물론 이 두개의 수자는 소수일 확률이 높을 뿐, 소수라는 확증이 없으므로 두개의 숫자는 몇 가지 소수 판정법을 이용하여 반복 판정을 하지 않으면 된다.

일반적으로 Adleman-Rumely라는 소수 판정법을 사용하면 100%의 확률로(또는 확실하게) 판정이 가능하다. 단지, 이 방법은 계산에 약간 시간이 걸리므로 먼저 소수 판정을 확률적으로 “소수일 확률이 99.9999999%”인 수자를 발견한 경우에는 이 방법을 사용하여 최종 판정하는데 사용할 수 있다.

주의를 기울여 추출한 자리수 100 정도의 두 개의 소수를 곱하면, 자리수 200정도의 합성수(즉 소수가 아닌 수)가 된다. 앞에서 서술한 것처럼, 소수인지 아닌지 판정하는 것은 비교적 간단하므로 자리수 200 정도의 숫자도 소수인지 아닌지 판정을 하면, “소수가 아니다”라는 판정이 가능할 것이다.

“소수가 아니다”라는 판정이 나오면, 소인수분해가 가능하겠지만, 자리수 200정도의 숫자는 10억년 정도 소요되므로 거의 안전하다고 할 수 있다.

5. 타원곡선법과 MPQS법

소인수 분해의 어려움을 설명하였으나, 현재 소인수 분해의 유효한 방법으로서 타원곡선법(ECM, Elliptic Curve Method)과 MPQS(Multiple Polynomial Quadratic Sieve) 두 가지를 예로 들 수 있다. 최근 소인수 분해된 수자의 일람표를 확인하면 대부분이 타원곡선법이 아니면 MPQS라고 알려져 있다.

타원 곡선법은 인수분해를 수행하려는 수자의 성질(어떠한 소인수를 가지고 있는가)에 따라서 인수분해에 걸리는 시간이 결정된다. 자리수가 많아지더라도, 그 수의 성질에 따라서 단시간에 인수분해가 가능해진다.

한편, MPQS법은 인수분해 하려고 하는 수자의 성질에 좌우되지 않고, 자리수에만 의존한다. 최근에는 NFS(Number Field Sieve)라는 소인수분해법도 사용되고 있다.

이들 방법을 사용하더라도, 60 자리수의 소인수분해에 15-30분, 80 자리수에서 40시간 정도 (Pentium 200MHz 기준), 100 자리수에서 0.5-1년 정도 소요된다고 한다.

실제 RSA 암호에 사용되는 200자리수 정도의 수자의 소인수분해는 약 10억년 정도 시간이 걸린다고 보면, 소인수분해의 어려움이 암호의 강도가 된다는 것을 이해할 수 있다.

6. 나프사크문제

소인수 분해 이외에도 “일방통행” 함수는 존재한다. 수학의 세계에서 "나프사크의 문제"로 알려진 것이 그것이다. 예를 들면,

1, 3, 4, 5, 13, 14, 17, 18, 23, 29

라는 수자가 있다고 생각하자. 이들 수자를 조합해서(사용하지 않는 수자가 있어도 좋다),

"서로 더하여 적당히 50이 되는 조합은 존재하는가?", "존재한다면 그와 같은 조합의 경우는 얼마나 존재하는가?"라는 문제이다.

이 문제는 숫자가 있어봐야 10개 정도 있으므로, 자세히 조사하면 결국은 해답이 존재하는지, 몇 개의 패턴이 존재하는지 알 수 있을 것이다. 일반적으로 이 문제에 대해서 “이것이다”라는 결정적인 해법은 없으며, 조합의 수가 얼마나 있는지도 조사하지 않으면 안 된다.

그러므로 숫자가 100개, 1000개라는 식으로 늘어날수록 시간이 많이 걸리게 된다.

이러한 문제는 수학에서 "P = NP문제"라는 문제와 밀접한 관계가 있다. 이전에 배운 해의 공식을 떠올려 보자.

의 해는

이와 같이 일반적인 해법이 존재한다면, 미리 계산에 필요한 시간을 대략 파악할 수 있다. 이것을 “다항식 시간(Polynomial-time)으로 풀이 한다”라고 말한다.

이에 대하여 소인수분해 및 나프사크의 문제는 결정적인 해법이 알려져 있지 않으므로 생각할 수 있는 경우를 조사해나갈 수밖에 없다. 이러한 문제를 "다항식 시간으로는 풀 수 없다(Non -deterministic Polynomial-time)"이라 한다.

그러나 소인수분해 및 나프사크 문제를 풀기 위한 적절한 계산방법을 몰라도, 좋은 방법을 발견할 수도 있다.

여기서 P문제와 NP문제에 대해서,

(1) (이 세상에는 일반적인 해법이 있는 문제와 적당히 추측하여 조사할 수 있는 문제 두 가지로 분류할 수 있다)

(2) (생각해보면 어떠한 문제라도 일반적인 해법이 존재)

중 어느 쪽에 해당하는 문제인지 의문이 생긴다. 수학자를 포함하여 머리가 뛰어난 사람이라면 아직 적절한 해법이 발견되지 않았을 뿐이므로 라고 생각할 수 있으나, 아직 이를 증명한 사람은 아무도 없다.

7. 수학적 지식

◆ modulus

어떤 수를 나눈 뒤에 나머지 숫자에 주목해 보자. 예를 들어 57을 13으로 나누면

이 되므로, 13을 기준으로 했을 경우 57과 5는 동일한 숫자로 간주할 수 있다. 이를

과 같이 적을 수 있다. 다른 예를 들면,

◆ 역원

곱셈의 경우, 3에 1/3을 곱하면 1이 된다. 이와 같이 어느 숫자에 곱셈을 하여 1이 되도록 하는 수자를 역원이라고 부른다(곱셈의 경우는 역수라고 부르는 편이 편리할 것이다). 13을 기준으로, 5의 역원을 구하여 보자.

으로 부터, 5의 역원은 8이 된다.

◆ 반복 제곱법

이 방법은 과 같은 계산을 효율적으로 할 수 있다. 있는 그대로 계산한다면 9회 곱셈을 수행하여야 하지만, 다음과 같이 하면 곱셈의 횟수가 줄어드는 것을 알 수 있다.

컴퓨터를 이용할 경우, 몇 번의 곱셈을 수행하였는가가 문제가 되므로

7 X 7, 49 X 49, 2401 X 2401, 5764801 X 49

전부해서 4번의 곱셈으로 계산이 가능하다. 마찬가지로 의 계산에 대해서도 9번의 곱셈만으로 가능하므로, 이 방법을 이용하면 계산을 빠르게 수행할 수 있다(확인해 보라).

◆ 최대공약수

a, b의 최대공약수를 gcd(a,b)라고 또는 단순히 (a,b)라고 기술하기로 하자(gcd는 greatest common divisor). 특히 (a,b) = 1이 될 경우, a와 b는 서로소라고 한다. 예를 들면,

(10,6) = 2

(24,15) = 3

(24,36) = 12

(7,6) = 1.

◆ 오일러 함수

오일러 함수 이라는 것은 을 만족하는 정수 a중 (a,n)=1이 되는 정수의 개수를 의미한다.

예를 들면, 이라는 것은 을 만족하는 정수(a=1,2,3,4,5,6,7,8,9)중에서 (a,10)=1이 되는 정수(결국 서로소가 되는 정수)의 개수를 의미하므로

(1,10) = 1

(2,10) = 2

(3, 10) = 1

(4, 10) = 2

(5, 10) = 5

(6,10) = 2

(7,10) = 1

(8,10) = 2

(9,10) = 1

이 되므로, a=1,3,7,9의 4개가 되어 =4가 된다. 또한 오일러 함수는 다음의 성질을 만족한다.

◆ 오일러 함수의 성질(1)

p가 소수라면, 이 된다.

예를 들어 13은 소수이므로, 가 된다. 왜냐하면 이라는 것은 사이의 정수 중에서 (a,13)=1이 되는 정수의 개수를 의미한다. 만약 서로소가 되지 않는 수를 발견한다면 약수가 존재한다는 것을 의미하므로 13이 소수라는 가정에 위반된다. 그러므로 p가 소수일 경우는 오일러 함수의 계산은 매우 간단하다(합성수의 경우는 조금 연구가 필요하다).

◆ 오일러 함수의 성질(2)

n = ab, (a,b)=1이면, 가 된다.

예를 들어, 91 = 7 X 13, (7,13) = 1이므로,

라고 계산된다.

마찬가지로 84 = 7 X 12, (7,12)=1이므로, 까지는 계산되지만, 는 12가 소수가 아니므로 간단히 계산되지 않는다.

◆ 페르마의 정리

p가 소수라고 가정하면, (a,p)=1이 되도록 하는 a에 대해서도

가 성립한다.

예로서 13은 소수이므로, (a,13)=1이 되는 모든 a에 대해서도

이 된다. 구체적으로

이 된다. 실제 의 계산은

와 같이 반복 곱셈법과 13을 이용한 나머지 연산을 통하여 계산을 조합함으로써 커다란 숫자를 사용하지 않고도 효율적으로 계산이 가능하다.

◆ 오일러의 정리

m을 양의 정수(반드시 소수일 필요는 없다)라고 하자.

이때 (a,m)=1을 만족하면 이 성립한다.

예로서 m=15라고 하면

이 되므로 (a,m)=1이면 가 성립된다고 바꾸어 적을 수 있다. 여기서 a=1,…,14중에서, 15와 서로소인 수를 찾으면

(1,15) = 1

(2,15) = 1

(3,15) = 3

(4,15) = 1

(5,15) = 5

(6,15) = 3

(7,15) = 1

(8,15) = 1

(9,15) = 3

(10,15) = 5

(11,15) = 1

(12,15) = 3

(13,15) = 1

(14,15) = 1

이 되므로, a=1,2,4,7,8,11,13,14가 된다. 실제 계산하여 보면

이 되므로, 정리가 옳다는 것을 확인할 수 있다.

◆ 지수법칙(1) : 이 성립한다.

예를 들면,

◆ 지수법칙(2) :

8. 메시지의 수치화

메시지를 수치화시켜 나타내 보자. 방법은 여러 가지 있을 수 있으나, 여기에서는 26진수 표시를 사용하는 것으로 한다. 통상, 267은 10진수를 의미한다. 10진수를 명확히 하기 위해서는 (267)₁₀이라고 표시하면 된다. 이것은

2X + 6X + 7X = 2X100 + 6X10 + 7X1 = 267이라는 의미다.

마찬가지로 2진수 표시의 1101은 (1101)₂라고 쓰고, 10진수로 다시 표시하면

1X + 1X + 0X + 1X = 1X8 + 1X4 + 0X2 + 1X1 = 13

이 된다. 알파벳은 전부 26문자로 알파벳을 수치로 환산하면, 26진수 표시가 가능하다. 예를 들어, a=0, b=1, c=2, …, z=25라고 가정하자. cat이라는 문자열을 숫자로 바꾸면 2, 0, 19가 된다. 이것을 26진수로 표시하기 위해, 10진수로 바꾸면

2X + 0X + 19X = 2X676 + 0X26 + 19X1 = 1352 + 0 + 19 = 1371

이 된다. 따라서 cat이라는 문자열은 1371이라는 숫자를 보내는 것과 같다. 역으로 1371이라는 수자를 26진수로 표시하면 2, 0, 19라는 수열이 얻어지므로 cat이라는 문자열로 바꾸는 것이 가능하다. cat이라는 문자열과 1371이라는 숫자에 1대1 대응을 시켰다는 점에 주의하자.

여기서 “메시지를 보내는 것은, 숫자를 보내는 것과 같다”라고 가정하면, 실제로는 “한자를 이용할 경우에는 어떻게?” 또는 “공백은 어떻게 표현하는가?”라는 어려운 문제가 남지만, 관심이 있으면 전문서적을 참고하기 바란다.

9. RSA 계산 예

실제 암호화를 수행하여 보자.

1371(cat이라는 문자열을 수치화시킨 것을 상기하자)을 암호화하면, 곱셈을 이용하여 1371보다 큰 두 개의 소수를 적절히 선택할 수 있다. 여기서는 43과 53으로 가정하자(43X53=2279). 그리고 43과 53이라는 숫자는 비밀에 붙이고, 2279라는 숫자는 공개하는 것으로 한다(이것이 공개키의 하나가 된다). 다음으로 를 계산한다. 이 경우에

- 2279 = 43 X 53

- 43과 53은 소수이다.

- 43과 53은 서로소

라는 사실로부터, 오일러 함수의 성질 (1), (2)를 사용하면 간단히 계산될 수 있다. 결국 다음과 같이 된다.

다음으로, 위 2184와 서로소가 되는 숫자를 적절히 선택해 나간다. 여기서는 1241을 선택하자(이것도 공개키가 된다).

다음으로 2184를 1241의 역원을 구하면 1649가 된다(이것도 공개키이다). 확인하여 보면,

1249 X 1649 = 2046409 (1)

= 1 ( mod 2184) (2)

가 되므로, 1649는 1241의 역원이 된다는 것을 확인할 수 있다. 실제 나누어 보면

2046409 / 2184 = 937…1

이 된다. 이것은

2046409 = 2184 X 937 + 1 (3)

인 것과 같다.

다소 숫자가 많아지겠지만, 정리하여 보면 다음과 같다.

- 공개키는 2279와 1241

- 비밀키는 1649

- 43과 53과 2184는 비밀

간단히 말하면, “나에게 메시지를 보낼 경우, 1241을 곱하고, 2279를 고려한 숫자(말하자면 2279로 나눈 나머지)를 보내세요”라는 것이 된다.

1371(cat이라는 문자열을 수치화시킨 것)을 공개키 1241과 2279를 사용하여 암호화하면

1371^(1241) = 2003 (mod 2279) (4)

와 같이 된다. 여기서 2003이라는 숫자가 암호문이 된다.

복호화하기 위한 비밀키 1649를 이용하면,

2003^(1649) = [(1371^(1241)]^(1649) (mod 2279) (5)

= 1371^(1241 X 1649) (mod 2279) (6)

= 1371^(2046409) (mod 2279 (7)

= 1371^(2184 X 937 + 1) (mod 2279) (8)

= 1371^(2184 X 937) X 1371^(1) (mod 2279) (9)

= [1371^(2184)]^(937) X 1371 (mod 2279) (10)

= 1^(1371) (mod 2279) (11)

= 1 X 1371 (mod 2279) (12)

= 1371 (mod 2279) (13)

과 같이 되므로, 원래대로 복원하는 것이 가능하게 된다.

[각주]

(5)로 변환은 (4)식 이용

(5)->(6) 지수법칙(2) 사용

(6)->(7) (1)식 사용

(7)->(8) (3)식 사용

(8) -> (9) 지수법칙 (1) 사용

(9)->(10) 지수법칙 (2) 사용

(10)->(11) 1371과 2279는 서로소이므로, 오일러 정리로부터

1371^() = 1 (mod 2279)

과 같이 된다. 이 식을 정리하면

1371^2184 = 1 (mod 2279) (14)

이 된다.

[주석]

(11)->(12) 1은 몇 번을 곱해도 1이다.

(12)->(13) 누구라도 알고 있다.

요령이 있다면 (2)식과 (14)식을 사용하여, (6)->(12)까지로 건너뛸 것을 생각할 것이다.

◆ 사용상의 주의

이 예에서는 공개키로 2279, 1241 두 개의 수자를 사용하였으나, 공개키는 한번 공개하면 자주 변경하는 것은 어렵다(메시지를 전송하는 쪽에서는 곤란해진다).

그러므로 메시지를 보고 공개키를 결정한 듯한 인상을 줄 수 있으나, 실제로는 먼저 공개키를 결정한 뒤 이에 응하여 메시지를 가공한다.

실제의 공개키는 자리수 200정도의 숫자가 되므로, 이 범위에 들어오도록 메시지를 세밀히 나누는 등의 연구가 필요하다. 예를 들면, 메시지가 길 경우에는 20문자 정도로 분할하여, 여러 번 송신하면 된다.

◆ RSA는 깨어지는가?

이 암호를 깨기 위해, 비밀키 1649를 획득할 필요가 있으나, 1649는 2184를 고려한 1241의 역원이다. 1241은 공개되어 있으므로 문제가 되지 않지만, 2184는 비밀이므로 해독하기 위해서는 2279에서 를 계산하지 않으면 안 된다.

우리는 2279 = 43 X 53이라는 사실을 알고 있으므로, 오일러 함수의 성질 (1), (2)를 사용함으로써 간단히 계산하였으나, 이를 모르는 사람은 2279를 소인수분해 할 필요가 있다.

그러나 실제로는 자리수 200 정도의 숫자가 사용되므로 소인수분해는 거의 불가능하다고 볼 수 있다. “우연히 생각한 숫자로 나누어서 소인수분해가 되었다”는 가능성도 거의 희박하다고 볼 수 있다.

10. RSA 공개키 암호

RSA 공개키 암호는 이 암호를 고안한 Rivest, Shamir, Adleman 3인의 이름 문자를 따서 붙이게 되었다. 이 암호의 근간을 이루는 것은 소인수분해가 상당히 어렵다는 사실이다. 아직까지도 그 안전성에 대해서는 견고한 시큐리티를 자랑하고 있지만, 계산에 시간이 많이 소요된다는 단점을 가지고 있다.

RSA는 DES와 비교하여 소프트웨어적인 측면에서 백분의 일, 하드웨어 측면에서는 천분의 일에서 일만분의 일 정도 속도가 나온다고 한다. 따라서 공개키 암호방식의 하나인 RSA와 종래의 비밀키 암호방식 DES와의 조합을 이용하는 것이 효율적이라 할 수 있다.

통상의 암호에 대해서는 DES를 사용하고(RSA를 사용하는 것보다 시간 단축이 된다), 정기적으로 행하는 키 교환으로는 RSA를 사용하는 것이 현실적이라 할 수 있다. 어떠한 암호라 하여도 동일 키를 장기적으로 사용하는 것은 위험하다. 여기서 특히 DES와 같은 종래의 암호는 일주일 간격으로 키를 교환하는 작업을 수행한다.

전송된 키가 해독이 되면, 이후 보내지는 메시지 모두는 해독되고 만다. 따라서 키를 전송하는 아주 중요한 통신에는 다소 시간이 걸려도 좋으므로, 안전성이 높은 RSA를 사용하게 된다. 예를 들면, 마이크로 소프트사의 데이터베이스 Access, 유명한 웹브라우저 Netscape Navigator 등의 많은 소프트웨어에 이러한 RSA 공개키를 적용하고 있다.

11. 암호 툴 PGP

PGP(Pretty Good Privacy)는 1991년 Zimmermann씨에 의해 만들어졌다. 그러나 이전에는 미국에서 암호 유출에 대한 규제가 있었으므로 미국 국외에서 사용하는 것은 불가능했다. 이러한 이유로 PGP를 기본으로 Schmacher가 국제 버전의 PGP(PGPi)를 만들게 됐다. 따라서 미국 내에서는 PGP가, 미국 외에서는 PGPi(PGP International)가 사용되게 되었다. 2000년 초반에 미국에서의 규제가 풀리면서 버전 6.5.1i를 최후로 PGP 국제 버전은 사라지게 되었다. 버전 5부터는 GUI가 지원되며 비교적 간단히 사용할 수 있다.

참고 사이트:

ftp://pgp.iijlab.net/pub/pgp5/6.5/6.5.1int/PGPfreeware651int.exe

RSA 공개 암호 해설부분에서 설명한 바와 같이, 보다 현실적인 방법으로 PGP에서는 통신문의 암호화를 위해 IDEA(International Data Encryption Algorithm)라는 종래의 암호 시스템을 이용하여 키의 암호화를 위해 RSA를 사용하고 있다.

12. DES 암호

DES암호는 1977년, 미국 상무성 표준국(ANSI)에서 데이터 암호화 규격(Data Encryption Standard)을 공모 했을 때 IBM이 제출한 방식에 수정을 덧붙인 것이다. 기본적으로 DES는 종래의 암호계열이지만, 여러 가지 암호화 방법의 조합을 통하여, 해독이 어렵도록 고안되었다. 발표당시는 하드웨어를 필요로 하였으나, 나중에는 소프트웨어만으로도 구현할 수 있게 되어 UNIX 등에서는 가장 일반적으로 쓰이는 암호 방식이다.

그러나 암호화 규격은 국방이라는 측면에서 대단히 중요시되었으므로, 미국 바깥으로 유출되는 것은 규제 대상이었다(Netscape Navigator 등에서 사용되는 RSA 공개암호도 규제 대상으로 결국 국내와 국외용 두 종류가 존재하였다. 국외 사용의 경우는 사용되는 키의 비트수가 적었다).

현재 DES의 사양은 공개되어 있으므로 소프트웨어만으로 실현가능하다. 많은 암호학자에 의해서 연구되었으나 해독된 적이 없다고 한다. DES 발표 당시는 미국 정부의 허가를 받은 기업만 하드웨어로 DES를 실현시켰으므로 암호의 안전성에 대해서 외부로부터의 평가는 거의 이루어지지 못하였다.

암호화 알고리즘을 공개할지 여부는 커다란 문제이다. 알고리즘을 공개하면, 암호의 안전성을 외부로부터 객관적인 평가를 받을 수 있다. 그러나 악용하여 공격할 가능성도 없지 않다.

알고리즘을 공개하지 않으면 악용되거나 공격에 대한 걱정은 줄어들지만, 암호의 안정성에 대해 객관적인 평가를 받기는 어려울 것이다. 또한 의도적으로 가공하여 암호화 알고리즘을 구현한 사람은 자신만이 해독할 수 있도록 준비하여 둘 수도 있을 것이다.

정부나 군사적 목적으로 사용된다면 상관없겠으나, 상용으로 쓰이기 위해서는 알고리즘 비공개는 커다란 장애 요인이 아닐 수 없다.

DES 암호는 키의 길이가 고정되어 있다. 원래의 DES 암호는 56bit 키를 사용하고 있다. 그리고 DES에서는 56비트 키를 사용하는 시스템과 40비트를 사용하는 시스템과의 호환성이 전혀 없어, 결국 40비트의 시스템에서 사용되는 키는 56비트 시스템에서는 사용할 수 없다. 한편, RSA 암호 및 PGP 암호에서는 키의 길이는 사용자측에서 자유롭게 바꿀 수 있다(동일 시스템 내에서 키의 bit수를 변경할 수 있다). 물론 커다란 bit수의 키를 사용할 수도 있으나, 계산시간이 많이 소요되므로 적절한 트레이드오프가 필요하다.

13. NSA(National Security Agency)

암호를 거론하는데 NSA를 빼놓고는 되지 않을 것이다. NSA는 미국 국가안전보장국을 의미하며, 그 임무는 미국 안전을 지키기 위해 세계 대부분의 통신을 감청, 도청한다. 이를 위해서 NSA는 전 세계의 미군 기지에 걸쳐져 있는 에슈론이라는 네트워크를 사용하여 모든 통신을 감시하고 있다. 해저 케이블에도 도청기가 설치되어 있다고 할 정도이다.

활동은 대한항공 격추사건이 발생했을 때도, 스크램블을 장착한 소련 전투기와 기지 사이의 교신내용을 감청하여 미국 정보 수집능력을 자랑하였다. 1996년에 발생한 페루 일본 대사관저 인질 점거사건에서도 사전에 특수부대 돌입을 미리 알아챘다고 하니 이것도 NSA의 능력이다.

NSA에 대해 알고 싶으면 http://www.nsa.org/를 방문하면 된다. 암호박물관은 빼 놓을 수 없는 곳이다. 세계 2차대전에서 독일과 일본이 사용한 유명한 암호기 에니그마가 전시되어 있다. 절대로 해독되지 않을 것이라고 믿었던 에니그마는, 실제 연합군측에서 해독하고 있었으며 정보가 옆으로 새고 있었다는 사실은 이미 알고 있을 것이다. 진주만 공격에 대해서도 사전에 알고 있으면서도 암호를 해독하고 있었다는 사실을 모르고 있어, 공격을 받게 되었다고 한다.

NSA에서는 임무 수행상의 이유로 암호통신이 이루어지는 것을 탐탁치 않게 여기고 있다. 이렇게 될 경우, NSA의 임무 수행이 원만히 이루어지지 않게 되기 때문이다. NSA에서는 막대한 예산과 많은 수퍼 컴퓨터, 유능한 과학자, 기술자를 필요로 하고 있으나, 강력한 RSA 암호를 깨는 것은 불가능하다(현재 수출이 허가된 56비트 DES 정도는 NSA 수퍼 컴퓨터를 가지고 있으면 해독 가능하다고 한다). 이러한 이유로 미국 정부는 암호의 수출에 대해서 강력히 규제를 하고 있다. 미국 기업은 뛰어난 암호화 기술을 가지고 있음에도 불구하고 미국 국외의 기업과 자유롭게 거래를 할 수 없다.

어떻게든 암호화 기술을 독점하려던 미국 정부이지만, 이에 반대하는 사람들과 기업의 저항에 최근(1997년경)에는 규제를 약간 완화하여 마스터 키를 미국 정부에 제출하면, 국외로 암호기술을 자유롭게 수출하는 것을 인정한다는 방침을 내놓았다(사실상 규제하고 있다는 점에는 변함이 없다). 재판부의 사법적 판단에 따르면, 미국 정부는 마스터 키를 이용하여 암호통신을 해독하는 것이 가능하다고 한다(어디까지 신용할 수 있는가?).

14. 그 외

◆ Camellia: NTT와 미쯔비시가 개발한 블록암호이다. AES에 응모한 암호방식으로 E2의 설계기법 및 안전성 평가기술을 토대로 만들어진 것이다.

◆ MultiPrime: 암호화 툴킷 RSA BSAFE WTLS-C에 채용된 암호기술이다. RSA 알고리즘을 사용한다. 통상 RSA 알고리즘에서는 두개의 소수를 사용하고 있으나, MultiPrime에서는 3개의 소수를 사용한다. 종래의 RSA 공개키 암호방식을 이용한 스킴 내용을 거의 변경하지 않도고 RSA 알고리즘의 계산효율을 향상시킬 수 있는 뛰어난 기술로 알려져 있다.

◆ Blowfish: Web상에서 암호화가 가능한 사이트에서 사용되는 알고리즘이다. 이렇게 해서, 암호의 유출 규제를 면하고 있다. http://www.encryption.com/

◆ CAST: PGP 5.X에서 채용된 비밀키이다. Northern Telecom사의 Carlisle Adams와 Stafford Tavares에 의해 만들어졌다.

◆ MALTI2, MALTI4, M6: 히다치에서 고안된 암호이다. 유료 위성 디지털방송에 사용되고 있다.

◆ 타원곡선암호: 마츠시타전기에서 고안한 암호이다.

◆ MISTY: 미쯔비시전기에서 고안한 암호이다. 공통키 암호의 하나로 차분공격에 강하다고 알려져있다.

◆ FEAL(Fast Data Encipherment ALgorithm): NTT가 개발한 종래의 암호이다.

암호화가 고속으로 가능하지만, 결국 해독이 가능하다는 것이 알려져 그후 개량이 이루어졌다. 그러나 그때마다 해독되고 말아, 이 암호에 대한 평가는 아직 엇갈려 있다.

◆ RC2, RC4, RC5, RC6(Rivest Cipher 또는 Ron's Code 2,4,5,6):

RSA사의 Ron Rivest가 고안한 종래 방식의 암호(비밀키 암호)이다. Netscape Navigator에서 사용되고 있다. 알고리즘은 비공개로 되어 있다.

◆ Skipjack: NSA(National Security Agency)가 설계한 Clipper 칩이라는 암호화 칩에 내장된 암호화 알고리즘이다. 오래 동안 알고리즘은 비공개로 되어 있었으나, 근래에 공개되었다. 암호학자에 의해 해독되어, 상당히 엉성한 암호?

◆ MD2, MD4, MD5: RSA사의 Rivest가 고안한 메시지 다이제스트 함수이다. 대상 파일의 고유 값을 고정 길이의 문자열로서 출력한다. PGP 암호의 공개키 지문(Key fingerprint)이라는 것은 공개키의 MD5를 사용한 출력 그것이다.

◆ SHS: NIST(National Institute of Standards and Technology, 미국 표준기술협회)가

제공하는 메시지 다이제스트 함수이다. 미국 정부의 규격으로서 채용되고 있다.

◆ DSS: NIST가 제공하는 전자서명이다.