[암호] RSA 암호화

※ RSA 암호화 

RSA 암호는 공개키 암호 시스템 중 하나이다.

공개키 암호시스템은 공개키(public key)와 개인키(private key)를 사용하여 암호화/복호화를 하는 시스템이다.

RSA 암호체계의 안전성은 큰 숫자를 소인수 분해하는 것이 어렵다는 것에 기반을 둔다.

RSA 암호화/복호화 방법은?

RSA 알고리즘도 그렇지만, 모든 공개키 암호화 알고리즘은 일방향 함수를 사용한다. 

일방향 함수라는 것은 한쪽으로는 계산이 용이한 반면, 역으로 계산하기는 매우 어려운 함수를 의미한다.

공개키 암호화 알고리즘에서는 일방향 함수를 사용해서 평문을 암호화한다. 한쪽으로는 계산하기가 쉬우므로 평문을 암호화하기는 쉽다. 그러나 반대쪽으로 계산하기는 어려우므로 암호문을 평문으로 바꾸는 것은 매우 어렵다. 그래서 키가 두 개가 필요한데 여기서 키란 메세지를 열고 잠그는 '상수(constant)'를 의미한다. 

일반적으로 많은 공개키 알고리즘의 공개키는 모두에게 알려져있으며 일방향 함수를 이용하여 메세지를 암호화(encrypt)하는 데에 쓰이며, 암호화된 메세지는 개인키를 가진자만 복호화(decrypt)하여 열어 볼 수 있다. 

즉, RSA는 공개키(ks)와 개인키(ks)를 생성하고, 그 과정에서 나오는 N을 이용해서 다음과 같이 암호화/복호화한다.

암호화 : 평문^kp mod N = 암호문

복호화 : 암호문^ks mod N = 평문 

RSA 알고리즘에서 공개키와 개인키는 어떻게 만들어질까?

공개키와 개인키는 다음 순서로 생성된다. 

1. 서로 다른 소수인 p와 q를 선택

2. N = p*q 인 N 생성    

   →  이때 사용자의 공개키는 (e, N)가 되고 개인키는 (d, N)이다.

   e와 d는 어떻게 구할까?

3. ∮(N) = (p-1)*(q-1)   

   →  오일러 피 함수 성질 두 가지에 의하여 성립 

       ∮(A*B) = ∮(A)*∮(B)

p가 소수일 때 ∮(p) = p-1

4. 1<e<∮(N) 이며 ∮(N)와 서로수 관계인 e 선택

5. e*d ≡ 1 mod ∮(N) 인 d 구하기   

    →  e와 d가 이러한 관계이기 때문에 암호화/복호화 방법이 성립된다.

         d를 구하기 위해 유클리드호제법을 사용 

▷ 유클리드호제법이란 ?

정수 a, b (≠0) 와 r에 대해서 a = b*q + r (0 ≤ r ≤ |b|) 일 때,

gcd( a, b) = gcd( b, r) 이 성립한다.

정수 a, b의 최대공약수를 gcd(a, b)라고 나타낼 때, 확장된 유클리드 호제법을 이용하여,

a*X + b*Y = gcd(a, b) 인 부정방정식의 해인 정수 X와 Y를 구할 수 있다. 

이러한 유클리드호제법을 사용하여 어떻게 개인키를 구하느냐?

e*d = k*∮(N) + 1 를 통해 gcd( ∮(N) , e) = 1임을 알 수 있다. 여기서 확장 유클리드호제법에 의하여 

⇒ ∮(N)*X + e*Y = 1  

⇒ (∮(N)*X + e*Y) mod ∮(N) = 1 mod ∮(N)

⇒ ( (∮(N)*X mod ∮(N) + e*Y mod ∮(N) ) mod ∮(N) = 1    ∵ (a+b) mod n = ((a mod n) + (b mod n)) mod n

⇒ ( ( 0 + e*Y mod ∮(N) ) mod ∮(N) = 1

⇒ e*Y mod ∮(N) = 1

∴ Y는 ∮(N)에 대해서 e의 역원이다. 그리고 Y는 d와 같음.

 

M을 평문, C를 암호문이고 e는 공개키, d는 개인키라고 하자.

암호화 방법의 의하여 M^e mod N = C 이다. 

그리고 키 생성과정에 의하여 e와 d는 다음과 같은 등식이 성립된다. 

e*d  ≡ 1 mod ∮(N) ⇔ e*d mod N = 1 // e와 d는 역원 관계.

   ⇔ e*d = k*∮(N) + 1

C^d mod N 

= (M^e mod N)^d mod N     ∵ M^e mod N = C

= (M^(e*d) mod N) mod N     ∵ x^a mod n = (x mod n)^a mod n 모듈러 연산 성질 

= M^(1 + k * φ (N)) mod N    ∵ e*d = k*∮(N) + 1

= M * (M^φ (N))^k mod N  

= (M mod N * (1)^k ) mod N    ∵ 오일러 정리에 의해  M^φ ( N) mod N = 1

= M mod N    ∵ M<N

= M   

∴ C^d mod N = M

이것을 다시 생각해보면 

M^e mod N = C

C^d mod N = M

두 식이 성립되기 위해서  e*d = k*∮(N) + 1 식이 성립되어야 한다고 볼 수 있다.

해킹하려는 사람입장에서 생각해보자.

공개되는 값은 N과 e 뿐이고 복호화하는 데에 필요한 개인키로 N과 d가 필요하는데, e*d ≡ 1 mod ∮(N) 임을 알고 있다. 그니까  ∮(N)을 알면  e*d ≡ 1 mod ∮(N) 식을 통해 개인키를 구하면 된다.

 ∮(N)를 알기 위해서는 ∮(N) = (p-1)*(q-1) 이므로 n을 소인수분해하면 되는데 N의 값이 작으면 바로 풀릴 수 있지만,

적당히 큰 수이면 엄청난 시간이 필요하여 거의 소인수분해를 성공시키기 불가능하다고 보면 된다. 이러한 점을 RSA의 안전성이라 볼 수 있다!! 

하지만 요즘 컴퓨터속도가 빨라진 만큼 키값도 1024미트 이상이 되어야 안전성에 문제가 없다고 한다. 

큰 숫자의 소인수분해의 획기적인 알고리즘이 개발된다면, 문제가 되는 알고리즘이기도 하다. 

다음 그림은 이해를 돕기 위한 RSA를 적용한 로그인 프로세스 예시이다. 

(참고한 사이트 :  http://daitso.kds.co.kr/27632/)

RSA 키교환을 이해하는 쉬운 강의 : https://rsec.kr/?p=476