RSA 알고리즘 - 공개키 암호화 방식

# RSA 알고리즘

- 동작 과정 

       1) 공개키 = (n, e), 개인키 = (n, d)

> 이 두 가지를 만들어야 한다

       2) n 구하기

- 두 수 p, q 를 갖고있다고 하자

- n = p x q 이다

       3) theta( n ) = (p-1) x (q-1)  를 만든다

> e 를 구하기 위한 과정

       4) 1< e < theta( n ) , e 와 theta 는 서로소  

> 이걸 만족하는 e 를 구해서, n 과 함께 공개키를 만들때 활용한다

       5) (e x d) mod theta( n ) = 1 을 만족하는 d 를 구한다

> 이걸 만족하는 d 를 구해서, n 과 함께 개인키를 만들때 활용한다

- 실제 암호화 과정 

       1) 원래 정보 = M 이라 하자 

       2) 공개키인 (n, e) 를 이용해서 암호화 하자

> C = M^e mod n 인 C 를 구한다

> 이때, C 는 M 이 암호화된 문서라고 볼 수 있다

       **이처럼, 공개키인 (n, e) 를 갖고 있어야지만 암호화가 가능하다

- 실제 복호화 과정 

       1) 암호화된 문서 C 가 있다고 하자

       2) 페르마의 소정리를 이용한다 -> 이를 이용하면, 원래 문서인 M 을 구하는게 가능하다

1> C = M^e mod n

2> M = C^d mod n

# 왜 RSA 알고리즘이 안전한걸까?

- 논리 흐름 : 

    1) 해커 입장에서 주어지는 것 : (n, e) 두 가지

> 공개키

> 공개키의 경우, 거의 대부분 아주 구하기 쉽다

    2) 그러나, 해커가 원하는건 개인키

> 결국엔 암호화된 문서를 복호화하기 위해서는 개인키가 반드시 필요하기 때문

    3) 개인키를 구하기 위해선 (n, d) 중에서 n 은 이미 주어져있으므로, d 만 구하면 된다

> (e x d) mod theta( n ) = 1

> 위 식을 만족해야하는 d 이므로, d 를 구하기 위해선 theta( n ) 값을 우선 구해야 한다

    4) 근데 theta( n ) 를 구하기 위해 활용 가능한 조건은 두 가지가 있다.

        1> theta( n ) = (p-1) x (q-1)

        2> 1< e < theta( n )

    5) 이때, 2 번 조건은 딱히 수를 구하는데에 유의미한 도움이 되진 않으므로 반드시 1번 조건을 활용해야 한다

    6) 1번 방식을 활용하려면, 결국 p x q = n 임을 이용해야 하는데, 즉 n 을 소인수분해 해야 한다는 것이다

    7) 그러나 수학적으로 봤을때, 큰 수를 소인수분해하는 것은 엄청나게 긴 시간이 소요되므로, 다항 시간 내에 찾는 것이 거의 불가능하다

    8) 따라서, n 을 p, q 로 소인수분해 할 수 없으므로 theta( n ) 을 구하는건 거의 불가능하다

    9) 결과적으로, 개인키를 구하는 방식인 (e x d) mod theta( n ) = 1 를 활용할 수 없다

    10) 뿐만 아니라, 설령 내가 theta( n ) 을 구해냈다고 하더라도, 위의 식을 만족할 수 있을 d 의 값은 무수히 많다

> 이 과정에서도 엄청나게 많은 시간이 필요하다

- 정리 :

     1) 큰 수의 소인수분해 어려움

     2) 나머지 연산의 역연산의 어려움

> 이 두 가지가 RSA 알고리즘의 안정성 원리