콘텐츠로 건너뛰기

About RSA Algorithm

태그:

Overview

RSA는 기본적으로 public key cryptosystem이다. 1977년 Rivest, Shamir 그리고 Adleman에 의해서 만들어졌다.

다른 public key cryptosystem과 마찬가지로 RSA도 trapdoor function에 크게 의존하고 있는데 RSA도 마찬가지로 trapdoor function 중의 하나인 integer factorization problem을 이용해서 안전성을 확보하고 있다.

trapdoor-function concept

trapdoor function은 간단히 말하면 위의 그림과 같이 x를 가지고 f(x)를 구하는 것은 쉽지만 f(x)를 알고 있을 때 x를 구하는 것은 어려운 함수를 말한다.

대표적인 예로 RSA에서 사용하고 있는 integer factorization problem을 예로 들 수 있다. integer factorization problem은 어떤 f(x1, x2, …, xn)의 값을 알고 있을 때 그 값을 이루는 x1, x2, … xn을 찾는 문제를 말한다.

이 때 x1, x2, … xn을 알고 있다면 f(x1, x2, … xn)의 값을 찾는 것은 쉽지만 반대로 f(x1, x2, … xn)을 알고 있을 때 x1, x2, … xn을 특정 주어진 시간 동안 찾는 것은 쉽지 않다. 이렇게 한쪽 방향으로 해를 구하는 것은 쉽지만 반대 방향으로 해를 구하는 것은 쉽지 않기 때문에 integer factorization problem을 trapdoor function이라고 볼 수 있다.

Background

relative prime

relative prime은 두 정수를 두고 불리는데 예를 들어 a와 b가 relative prime이라면 (a, b)=1임을 뜻한다.

Euler’s Φ(n) function

Fermat’s little theorem에 따르면 p를 양의 소수라고 할 때 p와 relative prime인 양의 정수 a에 대해서 다음과 같은 식이 성립한다.

복잡할 거 없이 mod 의 의미대로 위의 식을 읽어보면, ap-1은 p로 나눠떨어진다는 뜻을 담고 있다. 여기서 우리는 위의 식을 한 걸음 더 나아가서 Euler’s Φ(n) function으로 일반화시킬 수 있다.

식이 무지막지하다. 첫 번째 식과 비교했을 때 달라진 것은 a의 지수가 Φ(n)로 바뀌었다는 것인데, Φ(n)이 Euler’s Φ(n) function에서 핵심이다. Φ(n) function은 n보다 작거나 큰 양의 정수 n’ (0<n'<=n)에 대해서 n과 relative prime인 n’의 개수를 그 값으로 가진다.

예를 들어보자. Φ(5)에서 5보다 작은 양의 정수는 1, 2, 3, 4가 있는데 이들 중 5와 relative prime인 숫자의 개수는 4개이다. 따라서 Φ(5)=4이다. Φ(8)은 어떨까? 8보다 양의 정수는 {1, … ,7}이 존재하는데 이때 8과 relative prime인 숫자는 1, 3, 5, 7 총 4개이므로 Φ(8)=4이다. 마지막으로 Φ(7)에 대해서 생각해보면 7보다 작은 양의 정수는 {1…6}이 존재하고 이들 중 7과 relative prime은 {1…6} 전체이므로 Φ(7)=6이다.

이와 같이 계산을 하다보면 n이 소수인 경우는 Φ(n)=n-1인 규칙을 가지는데 생각해보면 당연하다. 왜냐하면 소수의 정의가 n보다 작은 정수 n’에 대해서 (n, n’)=1이기 때문이다. 우리는 이런 특징을 RSA 알고리즘에 사용할 것이다.

Modular Inverse

어떤 정수 a에 대해서 a와 어떤 수 x를 곱했을 때 1을 만드는 x를 우리는 a의 곱셈 역원(multiplicative inverse)이라고 부르고 보통 a-1로 나타낸다.

모듈러 연산에서도 곱셈 역원과 비슷한 개념이 있다. 어떤 정수 a와 m에 대해서 a와 어떤 수 x를 곱한 것에 대해 (mod m)한 결과가 1이 되는 x를 우리는 모듈러 역원(modular inverse)이라고 부르고 a-1로 나타낸다.


위의 수식을 보면 중요한 점을 하나 느낄 수 있는데 a와 m이 relative prime일 때만 a가 modular inverse를 가진다.

그렇다면 이제 궁금해지는 것은 a-1는 어떻게 구할 수 있을까? 한 가지 방법은 brute-force 방법을 사용할 수 있다. [0, m-1] 중에 정수를 하나씩 가져와서 모듈러 연산을 해볼 수 있을 것이다.

여기서 한 가지 주목해야할 부분은 brute-force 방법을 이용해서 a-1 구할 때의 시간 복잡도이다. [0, m-1]의 정수에 대해서 하나씩 가져오기 때문에 O(m)이라고 생각할 수 있다. 그런데 cryptosystem에서 다루는 input은 입력값 그 자체가 아니라 입력값을 바이트(or 비트)를 다룬다. 그렇기 때문에 전체 시간 복잡도는 O(2m)이 된다.

이와 같이 어떤 정수 a와 m이 있을 때 a와 m의 a에 대한 모듈러 역원을 구하기 위해서는 m의 지수적인 시간이 걸린다. 하지만 a와 a의 모듈러 역원이라고 생각하는 a’가 있다면 a’가 정말로 a의 모듈러 역원인지 확인하는 것은 어려운 문제가 아니다. 그래서 modular inverse를 구하는 것trapdoor function으로 볼 수 있다.

RSA Algorithm

이제 RSA 알고리즘에 대해서 살펴보려고 한다. 여기에서 RSA 암호화 방식이 어떤 방식으로 진행되는지 알아보고 각 단계에 대해서 짚고 넘어가보자.

  • 먼저 2개의 큰 소수 p, q를 생성한다. 소수를 생성하는 방법 중 하나인 Rabin-Miller 알고리즘을 사용할 수도 있다.
  • n=pq를 계산해야한다. 이 때 계산한 n은 나중에 public key와 private key의 modular 연산에 사용되고 n을 bit로 나타냈을 때 그 길이는 RSA 알고리즘의 키길이가 된다.
  • public key e 파라미터를 구해야하는데, 이 때 e는 (e, Φ(n))=1을 만족해야한다. Φ(n)는 Euler’s Φ(n) function에서 살펴보았듯이 Φ(n)=(p-1)(q-1)로 계산할 수 있다.
  • 다음으로 private key d 파라미터를 구하기 위해서는 public key e의 modular inverse를 구해야한다. 이를 수식으로 나타내면 다음과 같다.

이렇게 d, e를 구하게되면 사용자는 (e, n)을 public key로 사용하고 (d, n)을 private key로 사용하게 된다. 그렇다면 이를 이용해서 어떻게 평문을 암호화하고 복호화할 수 있을까?

먼저 평문을 바이트 배열로 바꾼 뒤 n보다 작은 바이트 블럭들로 나눈다. 그리고 이렇게 나눈 각 블럭들에 대해서

ciphertext_block = plaintext_block e (mod n)

을 이용해서 평문을 암호화할 수 있고 반대로 복호화를 할 때는

plaintext_block = ciphertext_block e (mod n)

을 이용해서 암호화된 메세지를 다시 복호화할 수 있다.

Example

그럼 이제 이해를 돕기위해 실제 숫자를 넣어서 RSA 알고리즘 과정을 따라가보자.

  • 먼저 두 개의 큰 소수 p, q를 생성해야하는데 이번 예시에서는 p=17, q=23이라고 해보자.
  • 다음으로 n=pq=17 * 23 = 391을 구하고 Φ(n)=(p-1)(q-1)=(17-1)(23-1)=352 를 구할 수 있다.
  • public key 파라미터 e를 구하기 위해서 (e, Φ(n))=1을 만족하는 e를 구해야하고 이를 계산하면 e=21이다.
  • private key 파라미터 d는 e의 modular inverse를 통해서 구할 수 있고 이를 계산하면 d=285이다.
  • 사용자는 public key/private key 파라미터 e, d를 이용해 public key와 private key를 구할 수 있고 각각 (e, n)=(21, 391), (d, n)=(285, 391) 로 계산할 수 있다.
  • 이렇게 구한 public key/private key를 이용해서 사용자가 ‘a’란 문자열을 암호화하고 싶다고 해보자. 우선 ‘a’의 ASCII 코드는 97이다. 이를 이용해서 ‘a’의 ciphertext를 구하고 다시 복호화하기 위해서는 다음과 같은 수식을 통해 계산할 수 있다.
// 암호화
ciphertext_block = plaintext_block e (mod n) = 97 21 (mod 391) = 37

// 복호화
plaintext_block = ciphertext_block e (mod n) = 37 285 (mod 391) = 97

Cracking

공격자가 RSA 알고리즘으로 암호화된 메세지를 복호화하려고 하는 경우에 대해 쓰고 이번 글을 마무리하려고 한다. 먼저 공격자는 e, n을 알고 있다. 왜냐하면 e, n은 퍼블릭한 정보기 때문이다. 이제 공격자의 목표는 private key인 (d, n)을 구하는 것이다.

공격자는 RSA 알고리즘이 어떻게 돌아가는지 알고 있고 그래서 d * e mod Φ(n) = 1을 통해 d를 구하고자한다. 그런데 d를 구하는 문제는 modular inverse를 문제이고 이를 푸는데 걸리는 시간은 위에서 설명했다시피 O(2Φ(n))이다. 따라서 Φ(n)이 크면 클수록 RSA 알고리즘이 안전하다는 것을 알 수 있다.

Leave a comment