[이산수학] RSA 암호

 

 

RSA 암호

---

1. 공개키 암호화 시스템

공개키 암호화 시스템은 암/복호화에 공개 키(public key)와 개인 키(private key) 2개 종류 키를 사용하는 방식입니다. 공개 키는 문자를 암호화하는 데 사용되는 키로, 문자를 암호화하려는 모든 사람들에게 공개되는 키입니다. 반대로 개인 키는 공개 키로 암호화된 문자를 복호화하는 데 사용되는 키로, 복호화를 하는 사용자만 아는 비공개 키입니다.

 

2. RSA 암호

RSA 암호 시스템은 공개키 암호 시스템의 하나로, Rivest, Shamir, Adleman 3명에 의해 개발되었습니다. RSA 암호 시스템은 두 개의 큰 소수를 곱하여 만든 합성수는 소인수분해하기 어렵다는 성질을 이용하였습니다. RSA는 현시대에 인터넷 보안, 디지털 서명 등 영역에서 사용되고 있습니다.

 

2.1. RSA 암호화 원리

RSA 암호화의 동작 원리는 다음과 같습니다.

1. 공개키 생성
   ① 임의의 서로 다른 큰 소수 p, q를 선택합니다.
   ② p와 q를 곱하여 합성수 n을 만들고, n의 오일러 함수(∮(n) = (p - 1) * (q - 1))와 서로소인 임의의 정수 e를 만듭니다.
   ③ 공개키는 (n, e)로 정의합니다.
2. 개인키 생성
   ① de ≡ 1 (mod ∮(n))을 만족하는 e의 모듈러 역수 d를 정의합니다.
   ② 개인키는 (n, d)로 정의합니다.
3. 문자열 암호화
   ① 암호화하고자 하는 임의의 문자열을 M이라고 정의하고, 공개키의 n과 e를 사용합니다.
   ② M의 각 문자를 두 자리 숫자로 변환합니다. (ASCII 코드나 유니코드 사용)
   ③ 변환된 문자열을 n을 초과하지 않는 가장 큰 블록으로 나누어 준 뒤, 각 블록을 m_i로 정의합니다.
   ④ 각 블록에 대해 m_i^e (mod n)를 적용하여 나온 결과를 c_i로 정의합니다.
   ⑤ 각 블록을 연결하여 M의 암호화를 종료하고, 이 값을 C라고 정의합니다.
4. 문자열 복호화
   ① 복호화하고자 하는 임의의 문자열을 C라고 정의하고, 개인키의 n과 d를 사용합니다.
   ② C를 n을 초과하지 않는 가장 큰 블록으로 나누어 준 뒤, 각 블록을 ci로 정의합니다.
   ③ d는 e의 모듈로 역수로 정의하였으므로 아래 과정을 통해 간단하게 복호화가 가능합니다.

$$\begin{align}
c_i^d
& \equiv (m_i^e)^d \pmod{n} \\
& \equiv m^{1 + k(p - 1)(q - 1)} \pmod{n} \\
& \equiv m(m^{p - 1})^{(q - 1)k} \pmod{n} \equiv m \pmod{p} (\because 페르마의 작은 정리, m^{p - 1} \equiv 1 \pmod{p} \\
& \equiv m(m^{q - 1})^{(p - 1)k} \pmod{n} \equiv m \pmod{q} (\because 페르마의 작은 정리, m^{q - 1} \equiv 1 \pmod{q} \\
& \equiv m \pmod{pq} (∵ p, q는 서로소) \\
& \equiv m \pmod{n} (∵ n = pq) \\

& \therefore m \equiv c_i^d \pmod{n} \\
\end{align}$$

---

연관 게시글

[이산수학] 정수론

[이산수학] 정수론

---

참조

•