RSA 알고리즘

RSA 알고리즘이란?

미국 MIT 에서 개발한 암호화 알고리즘으로 Ron Rivest, Adi Shamir, Leonard Adleman 세 사람의 성을 따서 RSA라는 이름이 붙은 비대칭키 암호화 알고리즘에 대해 알아보겠습니다.

RSA-2048은 전 세계 대부분의 인터넷 뱅킹에서 암호화 알고리즘으로 채택할 정도로 견고한 보안성을 가진 알고리즘 입니다. 앞서 디피 헬만 알고리즘은 이산 대수의 어려움으로 만들어졌다고 했습니다.

 

2023.12.28 - [정보관리기술사준비/보안] - 디피-헬만 알고리즘

디피-헬만 알고리즘

 

RSA 알고리즘은 인수분해가 어렵다는 것에 착안해 만들었습니다. 예를 들어 8051이라는 숫자가 있습니다. 이 숫자가 두 수의 곱이라고 했을 때 두 수를 찾으라고 하면 쉽지 않습니다. 하물며 이 숫자의 자리수가 몇백자리가 된다면 더욱 찾기 힘들 것입니다. 하지만 하나의 수가 83이라는 것을 알고 있다면 8051 / 83으로 나머지 하나의 수가 97이라는 것을 금방 알 수 있습니다. 디피 헬만 알고리즘과 비슷해 보이지만 몇가지 차이점이 있습니다.

비대칭키 알고리즘

디피 헬만 알고리즘은 엘리스(Alice)와 밥(Bob)의 비밀키가 같습니다. 그래서 대칭키 알고리즘이라고 합니다. 하지만 RSA 알고리즘은 모두에게 공개되는 공개키와 자신만 알고 있는 비밀키가 따로 있습니다. 그래서 RSA 알고리즘은 비대칭키 알고리즘이라고 합니다. 

잘 생각해보면 이미 디피 헬만에서도 서로 비밀값을 가지고 키를 만들었습니다. 따라서 RSA랑 비슷한 것이 아닌가 생각할 수 있지만 둘은 다른 형태를 가집니다.

 

디피 헬만 알고리즘에서는 서로의 비밀값을 활용해 하나의 비밀키를 만든 것입니다. 비밀키를 인터넷에 공개하면 안되니 비밀값과 공식을 통해 전달하지 않고 같은 대칭키를 만든 것입니다. 이 때 키를 만들기 위해 중간값을 교환하다보니 MITM 공격에 취약하다고 했습니다. 그리고 키를 만들고 난 후에는 더이상 비밀값은 필요하지 않습니다.

 

하지만 RSA 알고리즘은 모두에게 공개된 공개키(Public Key)와 개인만 알고있는 개인키(Private Key) 모두를 사용합니다. RSA는 단순히 더 복잡한 알고리즘이 아닙니다. 디피 헬만의 공개키가 할 수 없었던 기능을 비대칭키로 사용할 수 있게 됩니다. 

 

비대칭키 알고리즘의 가장 큰 특징은 부인 방지 입니다. 부인 방지란 실행 후 사후에 사실 부인을 방지하는 보안 기술입니다. 즉 어떤 보안 문서를 보냈거나, 받은것을 열어보았을 때 자신이 하지 않았다고 부인할 수 없게 하는 기술입니다. 이것이 가능한 이유는 바로 개인의 비밀키 때문입니다.

엘리스가 어떤 문서를 자신의 비밀키로 암호화 해서 밥에게 보냈습니다. 밥은 엘리스의 공개키로 이 문서의 암호를 풀었습니다. 오직 엘리스만 알고 있는 비밀키로 암호화 했기 때문에 엘리스의 공개키로 복호화가 가능한 상태가 됩니다. 따라서 이 문서를 암호화한 사람이 엘리스라는 것을 부인하지 못하게 됩니다.

반대로 밥이 문서를 엘리스의 공개키로 암호화해서 엘리스에게 보냈습니다. 만약 엘리스가 이 문서를 열어보았다면 오직 엘리스만 복호화 할 수 있는 문서를 열었기 때문에 엘리스가 문서를 받았다는 사실을 부인하지 못하게 됩니다.

 

암호화 키 만들기

그럼 RSA 알고리즘의 암호화 과정을 알아보겠습니다. RSA 알고리즘을 이해하기 위해서는 여러가지 복잡한 증명이 필요하지만 여기서는 생략하도록 하겠습니다.

1. N 만들기

두 소수 p, q를 준비합니다. 이 수는 몇백자리의 소수이기 때문에 계산하기가 무척 힘들게 됩니다. 이 두 수의 곱 N을 준비합니다. 

예제를 위해 작은 소수인 p를 11, q는 5라고 예를 들어보겠습니다. N은 두 수의 곱이기 때문에 11 * 5로 55가 됩니다.

 

2. 오일러 파이 함수 만들기

RSA 알고리즘을 제대로 이해하려면 오일러 정리(Euler's theorem)와 오일러 파이 함수(Euler phi Function)을 알아야 합니다.

오일러 정리는 페르마의 소정리를 확장한 버전입니다. 오일러 정리는 아래와 같습니다.

$$ a^{\phi(n)} \equiv 1 \bmod n(단, a와 n은 서로소) $$

오일러 정리의 증명에 대해서는 다음에 소개하도록 하겠습니다. 여기서는 RSA 알고리즘을 알기위한 것이기 때문에 RSA에 집중하도록 하겠습니다.

 

l = (p - 1)(q - 1)을 구합니다. 여기서 l을 오일러 파이 함수 φ(N) 라고 합니다. 오일러 파이 함수는 1부터 N까지 서로소인 숫자의 개수를 뜻합니다. N과 서로소인 숫자의 개수가 (p - 1)(q - 1)이 되는 이유는 두 수 p, q가 소수이기 때문 입니다. 1부터 p까지 서로소인 숫자의 개수는 (p - 1)개 입니다. 왜냐하면 2부터 p-1까지 p로 나누어지는 숫자가 없는 것이 소수이기 때문에 p - 1개가 p와 서로소인 숫자의 개수가 됩니다. q 도 마찬가지 이유로 q - 1개가 q와 서로소인 숫자의 개수 입니다. N은 p 와 q의 곱이기 때문에 N과 서로소인 숫자의 개수는 (p - 1)(q - 1)이 되는 것입니다.

 

여기서 l값은 (p - 1)(q - 1) = (11 - 1)(5 - 1) = 10 * 4 = 40이 됩니다.

 

3. e 선택하기

l보다 작으면서 l과 서로소인 값 e를 구합니다. 여기서 e는 40과 서로소인 3으로 하겠습니다. 이렇게 구한 e와 N 값이 공개키가 됩니다. 즉 여기서 공개키 (e, N)은 (3, 55)가 됩니다.

 

4. d 결정하기

마지막으로 d를 결정합니다. d를 결정하는 공식은 아래와 같습니다.

$$ e \times d \bmod l \equiv 1 (1 < d < l) $$

즉 e와 d를 곱한 값이 l로 나누었을 때 나머지가 1이 나와야 합니다. (e * d) % l == 1인 값을 찾아보면 (3 * d) % 40 이기 때문에 d가 27이 되었을 때 3 * 27 = 81이 되고 이 숫자를 40으로 나누었을 때 나머지가 1이 됩니다. 이것을 구하기 위해서는 확장 유클리드 호제법이라는 것을 사용해야 되지만 여기서는 따로 소개하지는 않겠습니다.

 

이렇게 비밀키 (d, N)은 (27, 55)가 됩니다.

암호화 하기

암호화는 다음과 같은 공식으로 진행 됩니다.

$$ x \equiv a^e (\bmod N) $$

그럼 숫자 13을 암호화 해보겠습니다. (13 ** 3) % 55 = 52가 됩니다.

복호화 하기

복호화 역시 암호화와 반대로 진행 됩니다.

$$ a \equiv x^d (\bmod N) $$

가 됩니다. 식에 대입해보면 (52 ** 27) % 55 = 13이 되어 복호화가 됩니다.

정리하기

간단하게 RSA 알고리즘에 대해 알아보았습니다. 복잡하고 어려워 보이지만 제대로 이해하면 그렇게 어렵지 않은 알고리즘 입니다. 다만 숫자가 너무 커져서 계산이 힘들다는 점 때문에 지금도 많이 사용되는 알고리즘 입니다. 

RSA 알고리즘은 너무 숫자가 커서 계산이 느리다는 단점이 있습니다. 따라서 큰 숫자를 암호화 하기 힘듭니다. 그래서 보통 앞에서 배웠던 대칭키로 문서를 암호화하고, 이 대칭키를 RSA 같은 알고리즘으로 암호화 합니다. 이렇게 하면 큰 숫자를 암호화 할 필요도 없고, RSA 알고리즘으로 아까 위에서 배웠던 부인방지가 됩니다. 이것을 전자 봉투라 합니다. 전자 봉투에 대해서도 나중에 한 번 정리해서 올리도록 하겠습니다.