RSA 기반의 공개키 시스템.

안녕하세요 Geeks_Company 입니다.

참고로 이글에 사용된 RSA 관련된 자료는 http://en.wikipedia.org/  에서 기록된 내용을 활용 하여 설명 하였습니다.

만약 저작권을 침해 하게 될경우 알려 주셨음 합니다.

Geeks_Key_Exchanger 는 RSA를 기반으로 한 키 교환 솔루션이며 ,

이 글은 RSA의 설명을 위해 작성된 글임을 밝힙니다.

RSA는  Rivest, Shamir and Adleman 핵심 개발자 3명의 앞 글자를 따서 만든 알고리즘입니다. 

RSA는 D-H 키 교환 방식 을, Rivest 가 Diffie 의 논문을 읽은 후 Shamir, Adleman에게 설명을 한 후 수학적인 연구를 시작하면서 시초가 되었습니다.


D-H 키 교환 방식 역시 비밀키 교환시에는 문제가 없지만, 상대방을 '인증'을 하기 위해서는 부족한 부분이 있습니다.


RSA는 개인키를 사용함으로써 인증 문제를 세련되게 해결하게 됩니다.



RSA에 사용되는 수학적 배경 지식 및 공식입니다.

- Fermat's Little Theorem (만약 p 가 소수고, a가 p에 의해 나눠지지 않는다면, a ^ (p-1) mod p = 1 이다)
- Euler's totient function (만약 n이 소수고, a,p가 서로소 이면, a ^ pi(n) mod n = 1 이다 )
- Modular multiplicative inverse (만약 a, m 이 서로소 이고, a ^ -1 mod m = x 이면, ax mod m = 1이 존재 한다)



RSA에서 제시하는 이론은 이러 합니다.

만약 0 <= a < n 그리고 c = a ^ e mod n, 이면 c ^ d mod n = a 이다.

좀 풀어서 적으면, 

숫자 a 에 e 제곱승 한 값에 n으로 나눈 나머지 값 c (암호문) 을 구한후 , 

나머지 값 c (암호문) 에 d 제곱승을 한 값을 n으로 나눈후 구한 나머지는 숫자 a 이다.

쉽게 풀어 적어놔도 쉽게 알아 보기 힘든게 알고리즘인거 같습니다.


RSA의 알고리듬의 핵심은 1개의 숫자로 암호화(e-encryp) 한것을 다른 1개로 복호화(d-decrpt) 가능하다는것입니다.


위키피디아 에서 인용된 예제를 사용해 보겠습니다. ( 필요 한 부분만 첨부 합니다 )

1. Choose two prime numbers  ( 2개의 소수 p,q를 선택 합니다 )
   
   

   p = 61 and q = 53
   
   

2. Compute n = pq  ( 2개 소수의 곱 합 n  을 구합니다 )
   
   

   
   

3. Compute the totients of product. For primes the totient is maximal and equals x − 1. Therefore
   
   ( totients 의 product를 계산 합니다 소수의 경우 소수 - 1 이 최대의 값이 됩니다 )
   참고로 totients product를 구하는 공식은  phi(61) = 61 ^ 1 * ( 1- 1/61) = 61-1 이 됩니다.
   예제 - If n = p^k , where p is prime, then .
   
            

    

    

4. Choose any number e > 1 that is coprime to 3120. Choosing a prime number for e leaves you with a single check: that e is not a divisor of 3120.
   
   ( 암호화(encryp) 할 수 e > 1 이며, 3120과 서로소 를 선택 합니다. e는 3120를 나눌수 없는것 즉 gcd(e,3120)=1 을 선택 합니다 )
   
   

   e = 17
   
   

5. Compute d such that e.g., by computing the modular multiplicative inverse of e modulo :
   
   (pi(pq)의 modular inverse를 구합니다  )  Modular multiplicative inverse 사용 
   

d = 2753
since 17 · 2753 = 46801 and 46801 mod 3120 = 1, this is the correct answer.(iterating finds (15 times 3120)+1 divided by 17 is 2753, an integer, whereas other values in place of 15 do not produce an integer. The extended euclidean algorithm finds the solution to Bézout's identity of 3120x2 + 17x-367=1, and -367 mod 3120 is 2753)

( 17, 2753의 곱합은 46801 이며, 46801을 3120으로 나눌경우 나머지가 1이 되므로, 이 식을 만족합니다.3120 * 15 + 1 mod 17의 나머지는 정수 2753 이며, 15가 아닐 경우 나머지 정수가 되지 않습니다. 확장 유클리드 알고리즘을 사용시  Bézout's identity 3120x2 + 17x-367=1 와 -367 mod 3129 의 답인 2753을 찾을 수 있다. )

 

The public key is (n = 3233, e = 17). For a padded message m the encryption function is or abstractly:

( 공개키는 17 이며, 암호화될 메시지 함수는 m ^ 17 mod 3233 입니다 ) 

           ( 암호문 c = m ^ e mod n )

The private key is (n = 3233, d = 2753). The decryption function is or in its general form:

( 개인키는 2753 이며, 복호화 함수는 c ^ 2753 mod 3233 입니다 )

           ( 메시지 m = 암호문 c ^ d mod n )

For instance, in order to encrypt m = 123, we calculate

(메시지 123을 암호화 하기위한 계산은 123  ^ 17 (암호화키) mod 3233 = 855  이며, 855는 암호문이 됩니다 ) 

         

To decrypt c = 855, we tap

(암호문 855를 복호화 하기 위해서는  855 ^ 2753 (복호화키) mod 3233 = 123 이며, 123은 복호화된 메시지 입니다.)      
          .