RSA 알고리즘 암호화 과정 - RSA algolijeum amhohwa gwajeong

# 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 알고리즘의 안정성 원리

4 분 소요

RSA는 큰 숫자를 소인수 분해하는 것이 어렵다는 것에 기반한 공개키 방식의 암호 알고리즘이다. 이론을 체계화한 3인(Ron Rivest, Adi Shamir, Leonard Adleman)의 성 첫글자를 따서 명명되었다.

RSA 알고리즘 개요

RSA는 개략적으로 다음과 같은 순서의 과정으로 나누어 볼수 있다.

1. 공개키와 개인키 생성
2. 공개키를 사용한 암호화
3. 개인키를 사용한 복호화

공개키와 개인키를 생성하기

공개키는 (n,e) 라는 두개의 수로 이루어지고, 개인키는 (n,d) 라는 두개의 수로 이루어진다. 결국 공개키와 개인키를 만드는 것은 3개의 숫자 n, e, d 를 구하는 과정이다.

n 값 구하기

먼저, 두 소수 p와 q를 임의로 정한다. (p ≠ q 이어야 한다.)

n을 다음과 같이 구한다.

Φ(n) 값 구하기

p와 q를 다음과 같이 다음식에 대입하여 Φ(n)를 구한다.

e 값 구하기

e는 다음 두가지 조건을 모두 만족하는 값이다.

1 < e < Φ(n)
e는 Φ(n)와 서로소

서로소: 1 이외에 공약수를 갖지 않는 둘 이상의 양의 정수

d 값 구하기

아래 식을 만족하는 d를 구해야 한다. (mod는 나머지 연산자를 뜻한다.)

풀어서 말하면, e * d 값을 Φ(n)로 나누었을때 나머지가 1인 d를 구하는 것이다.

여기까지 n, e, d를 모두 구하여, 공개키(n, e)와 개인키(n, d)가 완성된다.

공개키를 사용하여 평문을 암호화

공개키(n, e)를 사용하여 암호화 한다.

먼저, 암호화하기 전의 값을 평문 M이라 하고 암호화한 값을 암호문 C라고 하자.

암호문 C는 다음과 같이 구한다. (^는 제곱연산자를 뜻한다.)

개인키를 사용하여 암호문을 복호화

개인키(n, d)를 사용하여 암호문 C를 평문 M으로 복호화 한다.

예제

위에 설명한 알고리즘의 순서대로 실제값을 대입하여 계산해 보자.

<1단계> 임의 소수 p, q 정하기

p = 2, q = 7 로 정하자.

<2단계> n값 구하기

n = 14

<3단계> Φ(n)

Φ(n) = 6

<4단계> e값 구하기

5가 가능한 값이다. (2, 3, 4, 5 숫자 하나씩 조건에 맞는지 확인해 보았다.)

e = 5

<5단계> d값 구하기

5 또는 11이 가능한 값이다. (1, 2, 3, …, 11 역시 하나씩 확인해 보았다.)

5는 e와 동일한 값이므로 11로 정하자.

d = 11

<6단계> 공개키 완성

공개키는 (14, 5)이며, 개인키는 (14, 11) 이다.

<7단계> 암호화

평문 M 을 3 이라고 하자.

암호문 C는 다음과 같이 계산된다.

계산기를 두드려 계산해보자.

C = 5

<8단계> 복호화

다시 암호문 5 를 통해 평문 M은 다음과 같이 계산된다.

상당히 큰 숫자이다. 역시 계산기를 두드려 계산해보자.

M = 3

지금까지 RSA의 전체 과정을 개략적으로 설명하였다. 하지만, 실제 적용을 위해서는 추가적으로 몇가지 알고리즘이 더 필요하다. 이어지는 포스트에서는 조금더 세부적인 설명을 해보겠다.