RSA 암호 1. 개요
수학자들 중에서 정수론을 전문적으로 공부하는 사람을 정수론자라고 한다. 워낙 추상적인 개념을 많이 다루는 직업이기에 매번 "그래서 정수론을 배워서 뭐에 써먹는데?" 라는 질문을 자주 받게 된다. 솔직히 말하면 정수론이 실생활에 응용되어 쓰여지는 일은 드물다. 하지만 컴퓨터의 등장 이후, 모듈러 산술을 이용해 암호론에 정수론에 적용되기 시작되었다. 그 중에서 RSA 암호에 대해서 설명해보려고 한다.
정수론에 대해서 이야기 하기 전에 먼저 암호에 대해서 이야기 해보자. 다음 용어를 숙지해두자.
용어정리
평문: 보호해야 할 메세지암호문: 평문을 특정 대상 외에는 이해하지 못하게 변환한 메세지
암호화: 평문을 암호문으로 바꾸는 과정
복호화: 암호문을 평문으로 바꾸는 과정
기본적으로 우리는 다음을 하고 싶다. 김씨가 박씨에게 비밀 메세지를 보내고 싶다고 하자.
1. 김씨는 평문을 암호화 하여 암호문을 만든다.
2. 김씨는 암호문을 박씨에게 넘긴다.
3. 박씨는 김씨의 암호문을 받아 복호화를 하여 평문을 읽는다.
두 사람이 다른 사람에게 들키지 않고 비밀 메세지를 주고 받는 방법에 대해서 생각해보자. 일단 가장 간단한 방법은 두 사람이 같은 "키"를 가지고 있는 것이다.
대칭키 암호 (Symmetric-Key Cryptography)
예시 1
자물쇠가 달린 상자로 비유해보자.
김씨와 박씨는 다른 사람은 보지 못하게 비밀 메세지를 교환하고 싶다. 이를 위해서 그들은 자물쇠가 달린 상자를 구매했고 서로 같은 키를 구매했다.
1. 김씨는 비밀 메세지 (평문)을 상자에 넣어 자물쇠를 채운다 (암호화).
2. 김씨는 상자 (암호문)을 박씨에게 넘긴다.
3. 박씨는 김씨의가 보낸 상자를 키를 이용해서 자물쇠를 연다 (복호화).
1. 김씨는 비밀 메세지 (평문)을 상자에 넣어 자물쇠를 채운다 (암호화).
2. 김씨는 상자 (암호문)을 박씨에게 넘긴다.
3. 박씨는 김씨의가 보낸 상자를 키를 이용해서 자물쇠를 연다 (복호화).
이와 같이 김씨와 박씨가 같은 키를 쓰는 것을 대칭 키 암호 (Symmetric-Key Algorithm)이라고 부른다. 만약 박씨가 김씨에게 비밀 메세지를 보내고 싶다면 똑같은 방법으로 암호화를 하면 된다.
이와 같은 방식은 다음과 같은 문제점이 존재 한다.
이를 보안한 방법 중에 하나가 바로 RSA 암호이다.
이 방법에선 김씨는 키를 하나만 관리 하면 된다. 여기서 좋은 점은 키는 김씨만 가지고 있기 때문에 중간에서 상자를 누가 가로채도 열 방법이 없다. 여기서 대칭키와는 다르게 같은 상자를 쓰면 안된다. 박씨에게 비밀 메세지를 보내고 싶으면 김씨는 김씨의 상자를 사용을 못하고 박씨의 상자를 사용해야 한다.
이를 컴퓨터에 어떻게 적용을 할까? 이를 설명하기 위해서는 모듈러 산술의 대한 지식이 필요하니 처음 보는 사람은 다음 글로 바로 건너 뛰는 것을 추천한다. 다음 글 부터 모듈러 산술 시작해서 밑에서 설명하는 과정이 왜 성립이 되는지 설명할 예정이다.
처음 우리가 할 일은 메세지 (평문)을 숫자를 전환하는 것이다. 이는 여러 방법이 있으니 나중에 서술하도록 하겠다. 숫자로 전환된 평문을 $m$이라고 부르자.
2. $n = pq$ 를 계산한다.
3. $ (p-1)(q-1) $을 계산한다. 이 수치는 $\varphi(n)$이라고 부르자.
4. $1 < e < \varphi(n)$ 와 $\mathrm{gcd}(e, \varphi(n)) = 1$ 을 만족하는 수 e를 고르자. 여기서 $\mathrm{gcd}$는 최대공약수를 뜻한다.
5. $e$의 모듈로 $n$에 대한 역원 $d$를 구한다.
여기서 $(e,n)$은 공개키 $d$는 개인키라고 부른다. 여기서 숫자 $e$와 $n$이 상자와 열려있는 자물쇠의 역할을 한다. 이 숫자는 누가 봐도 아무 상관이 없다. 하지만 개인키인 $d$는 본인만 알고 있어야 한다.
이와 같은 방식은 다음과 같은 문제점이 존재 한다.
- 누군가가 중간에 상자를 가로채게 되었을 때, 가로챈 사람도 같은 키를 가지고 있으면 상자를 열어 볼 수 있다.
- 즉 물리적으로 만나지 않는 이상 키 교환 자체가 성립이 안 된다.
- 은행과 같이 다수의 사람과 비밀리 소통을 해야되는 기관은 고객의 수 만큼 열쇠를 지니고 있어야 한다. 그 만큼 키 관리가 힘들어진다.
이를 보안한 방법 중에 하나가 바로 RSA 암호이다.
RSA 암호 (Symmetric-Key Cryptography)
예시 2
1. 김씨는 상자와 같은 자물쇠를 대량 구매를 한다.
2. 김씨에게 비밀 메세지를 보내고 싶은 사람들에게 그 상자와 열려 있는 자물쇠를 보낸다.
3. 박씨는 상자에 비밀 메세지 (평문)을 집어넣고 자물쇠를 잠궈서 김씨에게 보낸다.
4. 김씨는 하나의 키로 모든 상자를 열 수 있게 된다.
2. 김씨에게 비밀 메세지를 보내고 싶은 사람들에게 그 상자와 열려 있는 자물쇠를 보낸다.
3. 박씨는 상자에 비밀 메세지 (평문)을 집어넣고 자물쇠를 잠궈서 김씨에게 보낸다.
4. 김씨는 하나의 키로 모든 상자를 열 수 있게 된다.
이 방법에선 김씨는 키를 하나만 관리 하면 된다. 여기서 좋은 점은 키는 김씨만 가지고 있기 때문에 중간에서 상자를 누가 가로채도 열 방법이 없다. 여기서 대칭키와는 다르게 같은 상자를 쓰면 안된다. 박씨에게 비밀 메세지를 보내고 싶으면 김씨는 김씨의 상자를 사용을 못하고 박씨의 상자를 사용해야 한다.
이를 컴퓨터에 어떻게 적용을 할까? 이를 설명하기 위해서는 모듈러 산술의 대한 지식이 필요하니 처음 보는 사람은 다음 글로 바로 건너 뛰는 것을 추천한다. 다음 글 부터 모듈러 산술 시작해서 밑에서 설명하는 과정이 왜 성립이 되는지 설명할 예정이다.
처음 우리가 할 일은 메세지 (평문)을 숫자를 전환하는 것이다. 이는 여러 방법이 있으니 나중에 서술하도록 하겠다. 숫자로 전환된 평문을 $m$이라고 부르자.
상자, 자물쇠, 그리고 키 만드는 과정
1. 서로 다른 소수 $p$ 와 $q$를 고른다. 여기서는 숫자를 크면 클수록 안전하다.2. $n = pq$ 를 계산한다.
3. $ (p-1)(q-1) $을 계산한다. 이 수치는 $\varphi(n)$이라고 부르자.
4. $1 < e < \varphi(n)$ 와 $\mathrm{gcd}(e, \varphi(n)) = 1$ 을 만족하는 수 e를 고르자. 여기서 $\mathrm{gcd}$는 최대공약수를 뜻한다.
5. $e$의 모듈로 $n$에 대한 역원 $d$를 구한다.
여기서 $(e,n)$은 공개키 $d$는 개인키라고 부른다. 여기서 숫자 $e$와 $n$이 상자와 열려있는 자물쇠의 역할을 한다. 이 숫자는 누가 봐도 아무 상관이 없다. 하지만 개인키인 $d$는 본인만 알고 있어야 한다.
암호화
\[ c \equiv m^e \quad (\mathrm{mod}{~n}) \]
을 만족하는 $c$를 구하자. 이 $c$가 평문 $m$을 암호화한 암호문이 된다. 중간에 누가 이 $c$를 어떻게 손에 넣는다고 해도 개인키인 $d$를 알지 못하는 평문인 $m$을 알 수 없다. 위의 합동식을 만족하는 $c$가 많다는 것을 아는 사람도 있을 것이다. 그렇기에 가능하면 $1 < c \leq n$을 만족하는 $c$를 고르는 것이 좋다.
\[ m' \equiv c^d \equiv m^{de} \quad (\mathrm{mod}{~n}) \]
위에서 이야기 했듯이 합동식을 만족하는 $m'$은 여러개가 있지만 $1 < m' \leq n$을 동시에 만족하는 $m'$은 하나 밖에 없다. 모듈러산술에 이론을 이용하면 우리는 $m'=m$임을 증명할 수 있다.
이로써 우리는 암호문 $c$에서부터 평문 $m$을 다시 구할 수 있다.
복호화
암호문 $c$를 받았다면 다음과 같이 복호화를 한다. 다음을 만족하는 $m'$을 구한다.\[ m' \equiv c^d \equiv m^{de} \quad (\mathrm{mod}{~n}) \]
위에서 이야기 했듯이 합동식을 만족하는 $m'$은 여러개가 있지만 $1 < m' \leq n$을 동시에 만족하는 $m'$은 하나 밖에 없다. 모듈러산술에 이론을 이용하면 우리는 $m'=m$임을 증명할 수 있다.
이로써 우리는 암호문 $c$에서부터 평문 $m$을 다시 구할 수 있다.
Comments
Post a Comment