RSA 암호화란?

1. RSA란??

RSA는 공개키 암호시스템의 하나, 암호화 뿐만아니라 전자서명이 가능한 최초의 알고리즘으로 알려져있다.

RSA가 갖는 전자서명 기능은 인증이 필요한 전자상거래 등에 광범위하게 사용되고있다.

2. 왜 이름이 RSA??

단순함. 모든 자연법칙이나 과학 및 수학의 이론의 이름이 발견한 사람 또는 만든 사람의 이름을 붙이는 것 처럼 RSA도

RSA를 만든 세명의 이름에서 이니셜을 따서 만든 것임. 이름들은 생략

3. RSA암호화 방식의 안정성

수학을 조금이라도 해봤으면 알 것이다. 우리가 보편적으로 다루는 4~5자리 까지만 해도 소인수분해를 하는데 어느정도의 시간이 걸린다.

그런데 RSA암호화는 큰 숫자를 소인수분해하기 어렵다는 점에 기반을 두고있다. 만약 큰 숫자를 소인수분해하는 지금까지 나온 방법과는 다른 획기적인 방법이 나오면 RSA암호화 방식은 안정성이 떨어질것이다.

양자컴퓨터 개발시 소인수분해 시간이 엄청나게 단축되어 RSA암호화 방식은 무용지물 될 가능성이 크다고 예견됌.

4. RSA암호화 방식 그림

(출처 : 네이버 지식백과) - https://terms.naver.com/entry.nhn?docId=2270499&cid=51173&categoryId=51173

5. 공개키와 비밀키

1. 두 수를 곱하여 ${\displaystyle N=pq\,}$ 을 찾는다.
2. ${\displaystyle \varphi (N)=(p-1)(q-1)\,}$ 를 구한다.
3. ${\displaystyle \varphi (N)}$ 보단 작고, ${\displaystyle \varphi (N)}$와 서로소인 정수 e를 찾는다.
4. 확장된 유클리드 호제법을 이용하여 ${\displaystyle d\times e}$를 ${\displaystyle \varphi (N)}$로 나누었을 때 나머지가 1인 정수 d를 구한다. (${\displaystyle de\equiv 1{\pmod {\varphi (N)}}}$
   (기호 쓰기 귀찮아서 이건 복붙함)

이렇게 얻은 (N, e) 를 공개키, (N, d)를 비밀키로 지정한다.  여기서 p와 q의 보안이 매우 중요함.

N을 소인수분해에서 p와 q를 얻기는 힘들지만 p와 q를 알아내기만 한다면 e와 d를 계산할 수 있기 때문이다.

그러므로 p와 q는 지워버리는것이 안전하다.

6. 암호화와 복호화

(1) 암호화

B가 M이란 메시지를 A에게 보내고 싶다고 하자. 일단 B는 이 M을 N보다 작은 숫자 m으로 변환한다. (이 변환법(padding scheme)은 A에게도 미리 알려져 있어야 한다. 이를테면, 메시지를 토막내어 하나의 메시지가 일정 수의 비트를 넘지 않게 하는 방법이 있다. 하지만 실제로는 이중보안을 위해 더욱 복잡한 변환법이 사용된다.) 그리고 B는 A의 공개키 <N, e>를 획득하고, 다음과 같이 c를 계산한다.

${\displaystyle c=m^{e}\mod {N}}$

그리고 이 c를 A에게 보낸다. 

위와같이 위키백과에 나와있는것을 복붙해보았다. (타이핑하기 귀찮아서 복붙) 

M을 N보다 작은 숫자 m으로 변환하는 방법은 아직 공부를 하지 못했다.

(2) 복호화

A는 암호화된 메시지 c를 B에게서 건네받았고, N과 d를 알고 있다. ------> (자기 비밀번호니깐 알 고 있는 것이 당연하다.)

 다음 식을 통해 m을 찾는다.

${\displaystyle m=c^{d}\mod {N}}$

위에서 설명하였듯 m을 가지고 A는 M을 찾아낼 수 있는 방법을 알고 있다.

예시)

A가 B에게 B의 공개키를 이용해 암호화하고  B가 A로부터 암호화 된 자료를 받고 자신의 비밀키로 복호화시키는 것을 보자.

두 소수 p = 13, q = 11를 선택한다. 

N = p*q = 13*11 = 143

Φ(N) = (13 - 1)(11 - 1) = 12 * 10 = 120

gcd(e,Φ(N)) = gcd(e, 120) = 1 과 1 < e < Φ(N) 을 만족하는 e를 선택한다.

→ Φ(N)보다 작고, Φ(N)와 서로소인 정수 e를 선택한다. 여기선 23을 선택한다.

e*d ≡ 1 (mod Φ(N)) , 1 < d < Φ(N) 인 d를 선택한다.

23*d ≡ 1 (mod 120),  1 < d < 120 를 만족하는 47을 d로 선택한다.

이 때  p,q,Φ(N)은 공개하지 않도록한다.

이렇게 되면 (143, 23)이 공개키가 되고, (143, 47)이 비밀키가 된다.

A라는 사람이 B에게 'J'라는 문자를 보내는 상황이라고 가정하자. 문자 J는 아스키 코드값으로 

1001010(2진수값), 10진수로는 74이다.

c = m^e mod n (c는 암호화값)

c = 74²³ mod 143

  = 94

c = 94 이다.

이 c(94)를 A가 B에게 보낸다.

B는 암호문자 c(94)를 A로부터 받았다. 이걸 B의 비밀키 (143, 47)을 이용해 풀어본다면 

m = c^d mod n

m = 94⁴⁷ mod 143

    = 74

m = 74이므로 74는 A가 B에게 보냈던 'J'의 아스키 코드값이다. 이런 식으로 평문 문자 'J'를 얻을 수 있다.

제 3자가 암호문자 94를 가로 챘더라도 공개키 (143, 23)만으로는 암호화된 것을 평문으로 변환할 수 없다.

위의 예제에서는 수학적 관점에서의 복호화인데, 큰 수를 다룰 때 pq같은 거대한 수에 대한 연산은 부담되므로 중국인의 나머지정리 라는 암호화 라이브러리를 사용하는데 그것은 나중에 다시 공부하겠다.