공개키 암호

RSA 암호 알고리즘

RSA는 공개키와 개인키 한 쌍을 사용하는 비대칭키 암호 알고리즘이다. 기밀성을 위해 데이터를 보낼 때는 수신자의 공개키로 암호화하고, 수신자는 개인키로 복호화한다. 반대로 전자서명에서는 개인키로 서명하고 공개키로 검증한다.

기밀성 목적의 RSA 암호화에서는 공개키로 암호화하고 개인키로 복호화한다. 따라서 개인키 및 공개키 생성 과정이 필요하다.

Note

대칭키 암호는 하나의 비밀키를 공유해 암호화와 복호화를 진행한다. RSA는 큰 수의 소인수분해가 어렵다는 점을 이용하기 위해 별도의 키 생성 과정을 거친다.

서로 다른 두 소수 p, q를 선택한다. RSA-2048에서는 보통 각각 약 1024비트 길이의 소수를 사용한다.
p, q를 곱하여 n을 구한다. φ(n)은 0부터 n 사이의 정수 중 n과 서로소인 정수의 개수이며, RSA에서는 φ(n) = (p-1)(q-1)로 계산한다.

φ (n) = (p - 1) (q - 1)

φ(n)보다 작은 수 중 φ(n)과 서로소인 e를 선택, d= $e^{- 1} m o d φ (n)$ 인 d를 구한다. (e의 곱셈의 역원이 존재하기 위해서 φ(n)과 e가 서로소임이 필수적임)

d = e^{- 1} m o d φ (n)

n과 e는 공개키로 d는 비밀키로 사용된다.

공개키 (n, e)로 n보다 작은 평문 m을 암호화할 때, 암호문 c는 다음 식으로 구한다.

c = m^{e} m o d n

암호문 c를 개인키 d로 복호화할 때, 평문 m은 다음과 같이 구한다.

m = c^{d} m o d n

RSA는 오래된 공개키 암호 알고리즘이지만 여전히 널리 사용된다. 다만 패딩을 사용하지 않거나 잘못된 파라미터를 설정하면 취약점이 생길 수 있다.