[RSA] RSA에 사용되는 알고리즘

0. RSA의 키 생성 알고리즘

RSA의 키 생성 알고리즘은 다음과 같다. 자세한 건 이전 글을 참고 바란다.

2020/06/18 - [알고리즘/RSA] - [RSA] 소개 & 키 생성 알고리즘

 

1. 서로 다른 큰 소수 p, q를 선택한다. (p ≠ q)
2. N = p x q를 계산한다.
3. φ(N) = (p - 1) x (q - 1)을 계산한다.
4. φ(N) 보다 작고, φ(n)와 서로소인 자연수 e를 선택한다. (gcd(e, φ(N))=1, 1 < e < φ(N)인 e 선택)
5. d x e를 φ(N)로 나누었을 때 나머지가 1인 정수 d를 구한다. ( de ≡ 1 mod φ(N) ) , 유클리드 호제법 이용
6. KU = {e, N}, KR = {d, N}이 된다.

위 알고리즘에서 해결해야 할 문제들이 있다.

 

1. 큰 소수 구하기

1024bit 키 길이에서의 p, q, n의 예시

소수를 구하는 방법 중 가장 간단하고 고전인 방법은 '아리스토텔레스의 체'가 있다.

숫자들을 순서대로 나열해놓고 가장 작은 소수인 2부터 시작해서 소수의 배수들을 하나씩 지워나가며 소수를 작은 소수부터 하나씩 찾아 나가는 방법이다.

이러한 방법 엄청난 오버헤드가 발생된다. 그리고 적어도 1024비트, 요즘은 2048비트의 키 길이를 권장하는데 이 만큼의 숫자를 담을 수 있는 배열을 만들어야 한다는 것 자체가 이미 실효성이 없는 것이다.

 

RSA에서 사용하기 위한 큰 소수를 구하는 알고리즘은 사실 소수를 구하는 것이 아니라 소수일 확률이 높은 수를 고르는 것이다. 이를 위한 여러 수학적 방법들(소수성 테스트)이 있다.

실용적인 소수성 테스트는 확률 알고리즘(Probabilistic algorithms)이다.

 

그 중 하나는 Fermat test(페르마 테스트)이다.

다른 하나는 Miller-Rabin(밀러라빈) test이다.

 

소수성 테스트를 통해 소수가 아닌 합성수라고 판정되면, 그 수는 버리는 것이다.

소수성 테스트를 통해 합성수라고 판정된 수는 항상 참인 명제이다.

소수성 테스트를 통해 소수라고 판정된 수는 참인 확률이 높은 명제이다. (100%가 아니다)

그렇기 때문에 아주 간혹 소수라고 판정한 수가 사실은 합성수일수도 있다. 그러한 수를 카마이클 수라고 부른다.

 

 

2. e와 d 쌍 구하기

암호키 e는 gcd(e, φ(N))=1를 만족한다.

e는 페르마 소정리를 이용해서 계산할 수 있다. (페르마의 소정리는 오일러 정리의 특별한 경우이다.)

 

복호키 d는 de ≡ 1 mod φ(N)를 만족한다.

복호키 d를 구하기 위해서는 확장 유클리드 호제법(EEA, Extended Euclidean Algorithm)이 사용된다.

 

3. 암호화/복호화

RSA 암호화

RSA 복호화

 

RSA에서 암호화와 복호화를 할 때 M와 C에 각각 e, d를 제곱승해준다.

이 계산을 단순히 수행한다면 어마어마하게 큰 수가 만들어질 것이다.

다행히도 이러한 계산을 간단하게 만들어 주는 제곱 후 곱셈 알고리즘(square-and-multiply algorithm)이 있다.

 

4. RSA 속도 상승

위에서 언급한 수학적 알고리즘들 외에도 RSA의 수행 속도를 상승시키기 위한 알고리즘들이 있다.

첫 번째는 짧은 공개 지수(e)를 이용한 빠른 암호화이다.

두 번째는 중국인의 나머지 정리(CRT)를 이용한 복호화 가속화이다.

 

 

5. 정리

• 페르마 소수성 테스트
• 밀러-라빈 소수성 테스트
• 페르마 소정리 (오일러 정리)
• 확장 유클리드 호제법
• 제곱 후 곱셈 알고리즘
• 짧은 공개 지수, 중국인의 나머지 정리