RSA 암호화 기법이란?
1978년 (Ron Rivest), (Adi Shamir), (Leonard Adleman)의 연구에 의해 체계화되었으며, RSA라는 이름은 이들 3명의 이름 앞글자를 딴 것이다. 이 세 발명자는 이 공로로 2002년 튜링상을 수상했다.
RSA는 큰 숫자를 소인수 분해하기 어렵다는 것에 기반을 두고 있다.
그리고 이 특허는 2000년에 만료되어 누구나 사용할 수 있게 되었다.
방법
RSA는 두 개의 키를 사용한다. 여기서 키란 메시지를 열고 잠그는 상수를 의미한다. 일반적으로 많은 공개키 알고리즘의 공개 키는 모두에게 알려져 있으며 메시지를 암호화하는데 쓰이며, 암호화된 메시지는 개인 키를 가진 자만이 복호화해 열어볼 수 있다.
공개키 알고리즘은 누구나 어떤 메시지를 암호화할 수 있지만, 그것을 해독하여 열람할 수 있는 사람은 개인 키를 지닌 단 한 사람만, 즉 인증 기관이 존재한다는 점에서 대칭 키 알고리즘과 차이를 가진다.
예시:
1. A라는 사람에게 B라는 사람이 메시지를 전하고자 한다.
2. B는 A의 열린 자물쇠를 들고 와 그의 메시지를 봉인(공개키 암호화 과정에 해당)한다
3. A에게 전해 주면, 자물쇠의 열쇠(개인 키에 해당)를 가지고 있는 A가 그 메시지를 열어보는(개인 키 복호화 과정에 해당) 식이 된다.
1. 중간에 그 메시지를 가로채는 사람은 그 열쇠를 가지고 있지 않으므로 메시지를 열람할 수 없다.
A와 B가 보안이 보장되어 있지 않은 환경에서 서로 비밀 메시지를 주고 받고 싶을 때는 B가 A에게 메시지를 전달하기 위해서는 A의 공개키가 필요하다.
A는 아래와 같은 방법을 통해 그 만의 공개키와 개인 키를 제작할 수 있다.
과정은 아래와 같다:
1. 두 개의 서로 다른 소수 선택: 두 개의 서로 다른 소수 p와 q를 선택한다.
ex) p = 7, q = 11
- 두 수를 곱하여 N 찾기: 선택한 두 소수 p와 q를 곱하여 N=pq을 찾습니다. N은 공개 키와 개인 키를 생성하는 데 사용된다.
ex) p q = N = 77
- 오일러 피 함수 φ(N) 계산: φ(N)=(p−1)(q−1)를 계산합니다. 이 값은 N보다 작고 N과 서로소인 양의 정수 e를 선택하는 데 사용됩니다.
ex) φ(N)=(7−1)×(11−1)=6×10=60
- 공개키 e 선택: φ(N)과 서로소(소수)인 양의 정수 e를 선택합니다.
ex) e = 13
- 개인키 d 계산: 확장된 유클리드 호제법을 사용하여 d e≡1 (mod φ(N))을 만족하는 d를 찾습니다.
ex) 13d = 1 (mod 60)
유클리드 알고리즘 활용
13d + 60k =1
d = 37, k = -8
481 - 480 = 1
개인 키 d 는 37
키는 이제 만들어 졌다.
이제 암호화를 해보겠다
암호화 과정은 아래와 같다:
- B가 M이란 메시지를 A에게 보내고 싶다고 하자.
ex) M = 890 - 일단 B는 이 M을 N보다 작은 숫자 m으로 변환한다.
m1 = 8,
m2 = 9,
m3 = 0
(이 변환법은 A에게도 미리 알려져 있어야 한다.
예를 들어, 메시지를 토막내어 하나의 메시지가 일정 수의 비트를 넘지 않게 하는 방법이 있다. 하지만 실제로는 이중보안을 위해 더욱 복잡한 변환법이 사용된다.) - 그리고 B는 A의 공개키 <N, e>를 획득하고, 다음과 같이 c를 계산한다.
ex) N = 77, e = 13
c = m^e mod N
그리고 이 c를 A에게 보낸다.
ex)
c1 = 8^13 mod 77 = 50,
c2 = 9^13 mod 77 = 58,
c3 = 0^13 mod 77 = 0
그리고 A가 받은 c를 다시 복호화 한다.
이때 A는 N 과 d를 알고 있다.
m = c^d mod N
ex)
m1 = 50^37 mod 77 = 8,
m2 = 58^37 mod 77 = 9,
m3 = 0^13 mod 77 = 0
m1 = 8, m2 = 9, m3 =0
메시지가 제대로 복호화 되었다.
