[이산수학] RSA 암호화

암호화의 종류

• 대칭키 암호 시스템 : 송신자와 수신자가 같은 비밀키를 사용하여 데이터를 암호화하고 복호화 하는 방식
• 공개키 암호 시스템 : 송신자와 수신자가 각각 다른 키 사용, 송신자는 수신자의 공개키로 메시지 암호화, 수신자는 자신의 개인키로 복호화

RSA 알고리즘

1. Bob이 Alice에게 평문을 보내려 한다.
2. Bob은 자신이 가지고 있는 Alice의 공개키를 통해 암호화한다.
3. 암호문을 Alice에게 보낸다.
4. Alice는 자신만 가지고 있는 개인키를 가지고 복호화 한다.

암호화 방법

1. 서로 다른 두 소수 p와 q를 선택한다. 두 소수를 곱해서 n을 계산한다. (n = pq) r은 $\mathbf{\phi(n)}$ 이 된다.
   
   • r이 공개키의 모듈이 된다.
   • r은 $\phi(n) = \phi(p) * \phi(q) = (p-1)(q-1)$
2. r과 서로소인 e를 선택한다 (gcd(e, r) = 1), 그리고 $e \cdot d \equiv 1 \ (mod \ r) $ 를 만족하는 d(e의 역원)를 만든다.
3. 공개키는 (n, e) 개인키는 (n, d) 이다
4. 평문 B를 암호화하기 위해 $\mathbf{{\color{Blue} E(B) = B^e \ (mod \ n)}}$
5. 암호문 C를 복호화 하기 위해 $\mathbf{{\color{Red} D(C) = C^d \ (mod \ n)}}$

예시 (p = 61, q = 127)

1. n = 61 * 127 = 774, r = 7560 (7747과 서로소인 원소의 개수)
2. e = 17 (r과 서로소)
3. d = 3113 , $e \cdot d \equiv 1 \ (mod \ r)$
4. 평문 2104를 암호화 = $2104^{17} \ mod \ 7747 = 628$
5. 암호문 628을 복호화 $ 628^{3113} \ mod \ 7747 = 2104$

RSA의 정확성 

암호문이 복호화 되는 과정

 

 

경우의 수가 여러개기 때문에 암호문을 유추하기 어렵다.