RSA 알고리즘

RSA 알고리즘은 비대칭키 암호화 방식 중 가장 유명한 방식 중 하나이며, 1977년 로널드 리베스트(Ron Rivest), 아디 셔미어(Adi Shamir), 레오나드 아들만(Leonard Adleman) 세 명의 수학자의 앞글자를 따서 RSA로 명칭됩니다. RSA 알고리즘은 소인수분해 문제를 기반으로 하기 때문에, 현재까지 발견된 가장 안전한 암호화 방식 중 하나로 평가받고 있습니다. RSA 알고리즘은 사용되는 키 길이에 따라 명칭이 정해지는데, 주로 사용되는 RSA 알고리즘은 617자리의 RSA-2048입니다.

 

(아래는 이해를 돕기 위한 간단한 예시로 작은 숫자를 활용해보았습니다. 실제 사용되는 RSA는 2048비트의 숫자이며, 출력되는 암호화 결과는 보통 Base64 형태로 표현됩니다.)

공개키/개인키 생성 과정

1. 소수(p,q) 선택

RSA 알고리즘에서는 매우 큰 소수(p,q)를 선택합니다. 보통은 1024비트 이상의 숫자가 사용됩니다.

p=11, q=13

2. n 값 계산

n은 두 소수(p,q)의 곱셈 n = p * q 으로 계산됩니다.

n=143

3. 오일러 파이 함수(φ) 계산

오일러 파이 함수는 n과 서로소인 자연수의 개수를 의미합니다. 이 값을 계산하기 위해서는 p와 q의 값이 필요합니다. 오일러 파이 함수 값은 φ(n) = (p-1) * (q-1)로 계산됩니다.

φ(n)=120

4. 공개키 생성

e는 공개키로 사용될 값으로, 오일러 파이 함수의 값보다 작고, 오일러 파이 함수와 서로소인 값을 선택합니다. 일반적으로 e는 65537을 사용하며, 공개키는 (e,n)가 됩니다.

e=7, 따라서 공개키는 (7,143)

5. 개인키 생성

d는 개인키로 사용될 값으로, e와 오일러 파이 함수 값의 모듈러 역수를 계산하여 구합니다. 즉, e * d ≡ 1 (mod φ(n))을 만족하는 d 값을 찾게 되면, 개인키는 (d,n)가 됩니다.

d=103, 따라서 개인키는 (103,143)

6. 키 유효성 검사

1. 공개키(e, n)의 경우, e와 n이 모두 양의 정수이고, e가 φ(n)과 서로소인지 검사합니다.

2. 개인키(d, n)의 경우, d와 n이 모두 양의 정수이고, e와 d가 모듈러스 φ(n)에 대한 역원 관계에 있는지 검사합니다.

공개키 (7, 143)와 개인키 (103, 143)는 유효합니다

암호화 과정

1. 암호화하는 메세지를 ASCII 코드로 변환

암호화하기 위한 평문의 모든 글자를 ASCII 코드로 변환하여 각 글자를 1바이트로 변환합니다. 이후 바이트 단위로 암호화가 진행됩니다. 이외에 utf-8 인코딩으로 변환되어 진행되기도 합니다.

“pop”를 암호화하기 위해 ASCII 코드를 변환: p=112, o=111, p=112

2. 공개키로 암호화

공개키(e, n)를 이용하여 암호화합니다. 공개키 중 공개된 값인 e는 암호화에 사용되는 지수이며, n은 모듈러 연산에 사용되는 값입니다. 암호화하고자 하는 메시지가 M일 때 다음 수식을 통해 암호화된 메세지 C를 얻을 수 있습니다.

RSA 암호화 수식

공개키(e,n)=(7,143)를 사용하면 다음과 같이 변환됩니다. 암호화된 문구 C = 18 45 18

복호화 과정

1. 개인키로 복호화

개인키(d, n)를 이용하여 복호화합니다. 개인키 중 비밀값인 d는 복호화에 사용되는 지수이며, n은 모듈러 연산에 사용되는 값입니다. 복호화하고자 하는 메시지가 C일 때 다음 수식을 통해 복호화된 메세지 M를 얻을 수 있습니다.

RSA 복호화 수식

개인키(d,n)=(103,143)를 사용하면 다음과 같이 변환됩니다. 복호화된 문구 M("pop") = 112 111 112

2. 복호화된 ASCII 코드를 메세지로 변환

복호화된 메세지를 ASCII코드에서 대응되는 값으로 변환하여, 초기 암호화에 사용되었던 메세지 원문을 확보할 수 있습니다.

ASCII 코드를 변환하면 해당 값들은 다시 “pop”으로 표기됩니다.