[보안] RSA의 개념과 특징, 예제: 소수를 이용한 비대칭키(공개키) 암호화 기법

 RSA 알고리즘에 대해서 알아보고, 암복호화하는 법과 그 예시를 살펴보겠습니다.

 

[ Contents ]

 

 

1. RSA

소수를 이용한 비대칭키 암호화 알고리즘

 

 RSA는 개발자들의 이름에서 유래되었으며, 소수를 이용한 대표적인 공개키 알고리즘입니다. 

 

2023.05.15 - [CS] - [보안] 대칭키 방식과 비대칭키(공개키) 방식: 개념과 장단점, 차이점

[보안] 대칭키 방식과 비대칭키(공개키) 방식: 개념과 장단점, 차이점

 

 RSA에서 소수를 사용하는 이유는, 소인수분해하고 소수를 판별하는 과정이 상당히 어렵기 때문입니다. 소수 판별은 아직도 명확한 공식이 나오지 않았으며, 지금도 에라토스테네스의 체를 이용해서 선별합니다. 그렇기에 소수 판별은 파이 계산과 함께 슈퍼컴퓨터의 성능을 측정하는 대표 연산으로도 쓰입니다.

 

2022.02.08 - [Algorithm] - [Algorithm] 소수 판별 알고리즘, 에라토스 테네스의 체

[Algorithm] 소수 판별 알고리즘, 에라토스 테네스의 체

 

 

 

2. RSA 알고리즘 과정

1. 서로 다른 소수 p, q 선택
2. n = p*q
3. φ(n) = (p-1) * (q-1)
4. 공개키 e 선택 (단, e와 φ(n)는 서로소, e < φ(n))
5. 개인키 d 선택 (단, d는 e*d mod φ(n) = 1)

6. 평문 m 암호화  c = (m^e) mod n
7. 평문 m 복호화 m = (c^d) mod n 

 

 소수 p, q는 크면 클수록 보안성이 좋습니다. 

 공개키는 {e, n}이고 개인키는 {d, n}입니다. n을 통해 유추할 수도 있겠지만 p, q는 공개된 정보가 아닙니다.

 

 

 

3. RSA 알고리즘 예시

p = 11, q = 3
n = p*q = 11*3 = 33
φ(n) = (10-1) * (3-1) = 20
e = 7
e*d mod φ(n) = 7d mod 20 = 1,   ∴ d = 3

m = 9
c = (m^e) mod n = (9^7) mod 33 = 27
m = (c^d) mod n = (27^3) mod 33 = 9

 

 RSA 알고리즘의 예시를 살펴보면 위와 같습니다. 실제 RSA는 아주 큰 소수를 사용하므로, 이것보다 훨씬 복잡하며 단순히 브루트포스로 구할 수 없는 연산량이 됩니다.

 

2022.01.16 - [Algorithm] - [Algorithm] 브루트 포스(Brute Force)는 노가다 기법?

[Algorithm] 브루트 포스(Brute Force)는 노가다 기법?