RSA : key generation

  컴퓨터 네트워크 강의에서 배운 RSA 암호 생성에 대해서 간단히 알아보자

 

  이 시스템은 1977년에 Ron Rivest, Adi Shamir, Leonard Adleman에 의해 고안되었고, 이름의 이니셜을 가져다가 시스템의 이름으로 만들었다.  RSA 알고리즘은 데이터의 안전한 전송과 저장을 위한 효과적인 암호화와 복호화 방법을 제공한다. 암호화 방식을 나누는 기준을 갖고 분류해보면 RSA는 양방향, 공개키 방식을 사용한다.  RSA의 동작 알고리즘은 다음과 같다. 

  

  키 생성: RSA는 공개 키와 개인 키를 생성하는 과정으로 시작한다. 

• 먼저, 두 개의 소수 p, q를 고른다. 
• p, q를 곱하여 암호화, 복호화의 계수인 n을 구한다. (n = p*q) 
• o를 p-1, q-1을 곱하여 얻는다. (o = p-1 * q-1) 
• 랜덤한 숫자 e를 선택한다. 
• d *e  = 1 mod o 의 식이 완성되도록 d를 선택한다. 
• 공개키는 e, n이 되고 o와 d는 비밀키로 사용된다. 

 암호화 : 생성된 키를 통해서 보내고자 하는 텍스트를 암호화 한다. 

• C = P^e(mod n)  :  P는 plaintext의 줄임말로 보내고 싶은 기존의 텍스트, C는 Ciphertext로 암호화된 텍스트이다. 암호화 과정에서 보면 알 수 있는 것 처럼, 공개키인 e,n을 사용한다. 

 복호화 : 비밀키를 이용해서 전달받은 암호 텍스트를 복호화 한다. 

• P = C^d(mod n) :  복호화 단계에서는 비밀키인 d를 사용해서 Ciphertext를 다시 Plaintext로 바꾸고 상대방이 보낸 원본 메세지를 확인하면 된다. 

 

 

---

RSA 예시 

• 키 생성을 위해 p,q,n,o를 각각 구해본다. p,q는 소수이여야 하니 7과 11로 정한다.
• n은 두 소수의 곱이니 77이 된다. (n = p*q)  
• o는 두 소수에서 각각 1을 뺀 수의 곱이라서 60이 된다. (o = (7-1 )* (11-1) )
• e는 13이라 가정하면 위의 조건을 만족하는 d는 37이 된다. (13 * 37 = 481 , 481 mod 60 =1 )

만약, Plaintext = 5라 가정하면 , Ciphertext는 아래의 식을 통해 구한다.

•     C = 5^13(mod 77)  = 26 이라서 C는 26이 되니까 5가 아닌 26을 전송한다. 

26을 받고 다시 Plaintext를 얻으려면 P = C^d(mod n)의 식을 이용한다. 

•    P = 26^37(mod 77) = 5 라서 plaintext 5를 다시 구할 수 있다.