RSA 암호

* RSA란 암호화와 인증을 할수있는 공개키 암호시스템이다. 이것은 1977년 RonRivest와 Adi Shamir, Leonard Adleman에 의해서 개발되었다. 이것은 다음과 같은 동작원리를 가진다.
커다란 두 소수 p와 q를 가지고, 이 둘의 곱 n=pq을 구한다. n보다 작고 (p-1)(q-1)와 서로소 관계인 e를 정한다. 즉 e는 (p-1)(q-1)와 1을 제외한 어떠한 공통근을 가지지 않는다. 또다른 숫자 d는 (ed-1)이 (p-1)(q-1)로 나누어 질수 있도록 정한다. e와 d값은 공개지수 비밀 지수라 불린다. 공개키는 (n,e)쌍이 되고 비밀키는 (n,d)쌍이 된다. p,q값은 비밀키로 유지하던지 소멸한다.
RSA 암호 예: 송신자가 메시지 m을 암호화 할때는 다음과 같다. c=me mod n,여기서 e와 n은 수신자의 공개키 이다. 이때 수신자는 m=cd mod n 이렇게 하여 메시지 m을 얻는다.

송신자 Alice는 평문 P와 공개키 (n,e) 를 이용하여

③

 C º Pe mod n 를 계산하여 암호문  C를 Bob에게 송신한다

 

 

 수신자 Bob은 개인키 d를 이용하여

⑤ Cd º  P mod n 를 계산하여 평문 P를 얻는다.

 

<준비 과정(Setup 과정)>

1. B는 p = 7 과 q = 11을 선택하고 n = 7 * 11 = 77 을 구한다.

2. B는  φ(n) = (p - 1)(q - 1) = 6 * 10 = 60 을 구한다.

3. B는 60과 서로소가 되도록 e = 37 을 선택하고 Euclid 호제법을 이용하여

   ed º 1 mod 60 을 만족하는 d = 13 을 구한다.

60x + 37y = 1

큰수 60 을 작은수 37로 나누겠습니다.
60 = 37 * 1 + 23    23 = (60-37)
제수였던 37을 나머지 23으로 나누겠습니다.
37 = 23 * 1 + 14   14 = (37-23)
제수였던 23을 나머지 14으로 나누겠습니다.
23 = 14 * 1 + 9      9 = (23-14)
14 = 9 * 1 + 5       5 = (14-9)
9 = 5 * 1 + 4         4 = (9- 5)
5 = 4 * 1 + 1     

1 = 5 - 4
1 = 5 - 9 + 5
  = 2 * (14-9) - 9
  = 2 * 14 - 3 * 9
  = 2 * (37-23) - 3 * (23-14)
  = 2 * 37 - 5 * 23 + 3 * 14
  = 2 * 37 - 5 * 23 + 3 * (37-23)
  = 5 * 37 - 8 * 23
  = 5 * 37 - 8 * (60-37)
  = 5 * 37 - 8 * 60 + 8 * 37
  =13 * 37 - 8 * 60

 

4. B 는  n = 77 과 e = 37 을 공개한다.

 

<암호화 과정>

5. A는 공개키 n = 77 과 e = 37 을 이용하여 평문 17로 부터

   C = 17^37 º 52 mod 77 을 계산하여 암호문 52를 B에게 보낸다.

 

<복호화 과정>

6. B는 개인키 n = 77 과 d = 13을 이용하여 암호문 52로 부터

   P = 52^13 º 17 mod 77 을 계산하여 평문 17을 얻는다.

[RSA]

 

-1978년 미국의 Rivest, Shamir, Adleman이 개발한 대표적인 공개키 암호 커다란 두 소수의 곱 n=pq의 인수분해문제에 안전성을 둠

 

[RSA 암복호화과정]

-키선택: 큰 소수 p,q, n=pq 과 자연수 e ( (e,f(n))=1)를 선택 하여  edº1 mod f(n)를 만족하는 e를 찾는다. 공개키 (n,e) , 비밀키 (p,q,d)

 

-암호화: 송신자는 C º Pe mod n 를 계산하여 암호화

-복호화: Cd º  P mod n 로 복호화

 

[모듈라 지수승(exponentiation)]: gk mon n 계산, 암호화 및 복호화의 속도에 가장 큰 영향을 미치며, RSA 뿐만 아니라 대부분의 공개키 암호의 효율성에서 가장 중요한 부분임

 

[RSA 해독]

-n의 소인수  p,q를 구한다

-Euler 함수f(n)의 값을 구한다.

-공개키 e와 공개정보 n을 가지고

 비밀키 edº1 mod f(n)을 만족하는 d를 구한다.

 

[RSA 암호의 안전성을 높이기 위한 조건]

-p와 q는 같지 않고 거의 같은 크기의 자릿수이어야 한다.

-p-1과 q-1은 커다란 소인수를 각각 가져야 한다.

-p-1과 q-1의 최대공약수는 작은 수이어야 한다.

-p와 q 의 크기는 충분히 커야 한다 (현재 1024비트 이상요구)