RSA Public-Key Encryption Algorithm
RSA 공개키 암호화 알고리즘
- 1977년 MIT의 Ron Rivest, Adi Shamir, Len Adleman에 의해 개발된 암호화 알고리즘이다.
RSA Algorithm Overview (간략한 RSA 암호화 알고리즘)
\(C = M^e \; \mathrm{mod} \; n\)
\(M = C^d \; \mathrm{mod} \; n = (M^e)^d \; \mathrm{mod} \; n = M^{ed} \; \mathrm{mod} \; n\)
| Legend | Description |
| \(C\) | Ciphertext |
| \(M\) | Message (Plaintext) |
| \(\{e, n\}\) | Public Key |
| \(\{d, n\}\) | Private Key |
Requirements (요구사항)
- 모든 \(M < n\)에 대해, \(M^{ed} \; \mathrm{mod} \; n = M\) 을 만족하는 \(e, d, n\)을 찾는 것이 가능하다.
- 모든 \(M < n\)을 만족하는 값에 대해, \(M^e, M^d\)를 계산하는 것이 상대적으로 쉽다.
- 주어진 \(e, n\) (Public Key)으로부터 \(d\) (Private Key)를 도출하는 것이 Infeasible하다.
- \(e\)와 \(n\)이 충분히 큰 값이어야 한다.
RSA Key Generation Mechanism (RSA 키 생성 메커니즘)
- 두 개의 큰 소수 \(p\)와 \(q\)를 정한다. (\(p \neq q\))
- 두 소수를 곱하여 \(n\)을 만든다.
\(n = p\cdot q\)
이때, \(n\)을 Modulus라 부른다. - \(e\)를 정한다.
\(e\)는 \((p-1)(q-1)\) 값과 Coprime(서로소)인 수 중 하나여야 한다. - 아래 수식을 통해 \(d\)를 정한다.
\(ed = 1 \; \mathrm{mod} \; (p-1)(q-1)\) - 공개키와 개인키가 완성되었다.
Public Key = \(\{e, n\}\)
Private Key = \(\{d, n\}\)
RSA Encryption and Decryption Mechanism (RSA 암호화·복호화 메커니즘)
RSA Encryption (RSA 암호화)
- 전송하고자 하는 메시지 \(M\)을 숫자로 다룬다. (\(M < n\))
\(M\)을 Encryption하여 Ciphertext \(C\)로 암호화한다.
\(C = M^e \; \mathrm{mod} \; n\)
RSA Decryption (RSA 복호화)
- \(C\)를 Decryption하여 Plaintext \(M\)으로 복호화한다.
복호화시에 개인키 \(d\)가 사용된다.
\(M = C^d \; \mathrm{mod} \; n\)
Example. RSA Encryption and Decryption
1. \(p = 11, q = 3\) 으로 정하자.
2. \(N = p\cdot q = 33\) 으로 결정된다.
3. \((p-1)(q-1) = 20\) 이므로, \(20\)과 서로소인 \(3\)을 \(e\)값으로 결정하자.
즉, \(e = 3\)
4. \(ed = 1 \; \mathrm{mod} \; (p1)(q-1)\) 에서 \(3d = 1 \; \mathrm{mod} \; 20\) 이므로,
\(d = 7\) 이라 하자.
5. 보내고자 하는 메시지 \(M\)을 숫자로 간주했을 때 \(8\)이라 하자. 즉, \(M = 8\) 이며 \(8 < 33\) 이다. (\(M < N\))
6. \(M\)을 암호화한 암호문 \(C = M^e \; \mathrm{mod} \; N = 8^3 = 512 \; \mathrm{mod} \; 33 = 17\) 이다.
7. \(C\)를 복호화한 평문 \(M = C^d \; \mathrm{mod} \; N = 17^7 \; \mathrm{mod} \; 33 = 410,338,673 \; \mathrm{mod} \; 33 = 8\)
Attacks on RSA (RSA 암호 체계에 대한 공격방법)
- 공격자는 \(n\)을 인수분해하여 \(p\)와 \(q\)의 Pair를 찾아내는 것이 관건이다.
* Modulo Exponential Process
- Modulo 연산 계산과정에서, 지수식의 값이 큰 경우 그 값을 전부 계산한 다음 Modulo 연산을 진행하는 것이 아니라,
Iteration을 통해 값의 크기를 낮춘 다음 Modulo 연산을 수행한다.
Example. Modulo Exponential Process for \(5^{20} = 25 \; (\mathrm{mod} \; 35)\)
\(5^1 = 5 \; (\mathrm{mod} \; 35)\)
\(5^2 = (5^1)^2 = 5^2 = 25 \; (\mathrm{mod} \; 35)\)
\(5^5 = (5^2)^2 \cdot 5^1 = 25^2 \cdot 5 = 3125 = 10 \; (\mathrm{mod} \; 35)\)
\(5^{10} = (5^5)^2 = 10^2 = 100 = 30 \; (\mathrm{mod} \; 35)\)
\(5^{20} = (5^{10})^2 = 30^2 = 900 = 25 \; (\mathrm{mod} \; 35)\)
Verification of RSA (RSA 알고리즘 검증)
- Euler's Theorem을 이용하거나 Fermat's Little Theorem을 이용하여 검증한다.
1. using Euler's Theorem
평문 \(M\)을 암호화하여 \(C\)를 만들고, \(C\)를 복호화한 값을 \(M'\)이라 하자.
여기서, \(M = M'\) 임을 증명한다.
\(C = M^e \; \mathrm{mod} \; N\)
\(M = C^d \; \mathrm{mod} \; N\)
이다.
\(M = (M^e \; \mathrm{mod} \; N)^d \; \mathrm{mod} \; N\)
\(\qquad = (M^e)^d \; \mathrm{mod} \; N\)
\(\qquad = M^{ed} \; \mathrm{mod} \; N\)
이다.
\(ed = 1 \; \mathrm{mod} \; (p-1)(q-1)\) 이므로 나머지 정리에 의해,
\(ed = k(p-1)(q-1) + 1\) 이다.
(\(k > 0, k \in \; \mathbb{Z}\))
Euler's Phi(\(\Phi\)) Function
\(\Phi(n) = |k \in \{1, \cdots, n\}:\mathrm{gcd}\{n, k\} = 1|\)
즉, \(Phi(n)\)은 1부터 \(n\)까지의 정수 가운데 \(n\)과 서로소인 것들의 개수이다.
즉, \(\Phi(N) = (p-1)(q-1)\) 이므로,
\(ed = k\Phi(N) + 1\)
\(\iff ed - 1 = k\Phi(N)\)
따라서,
\(M^{ed} = M^{(ed-1)+1} = M\cdot M^{ed-1} = M\cdot M^{k\Phi(N)}\)
\(\qquad= M\cdot (M^{\Phi(N)})^k \; \mathrm{mod} \; N = M\cdot 1^k \; \mathrm{mod} \; N\)
\(\qquad= M \; \mathrm{mod} \; N\)
\(\qquad= M (\because M < N)\)
2. using Fermat's Little Theorem
* Fermat's Little Theorem
\(x^{p-1} = 1 \; \mathrm{mod} \; p (\forall x, \forall \; \mathrm{prime} \; p)\)
[Observation]
\(a = b \; \mathrm{mod} \; p\)
\(a = b \; \mathrm{mod} \; q \to a = b \; \mathrm{mod} \; p\cdot q\)
\(M^{ed} = M^{(ed-1)+1} = M^{k(p-1)(q-1)}\cdot M = (M^{(p-1)})^{k(q-1)}\cdot M\)
\(\qquad = 1^{k(q-1)}\cdot M = M mod p\)
위와 같은 방법으로
\(M^{ed} = M \; \mathrm{mod} \; q\)
임도 알아낼 수 있다.
즉, \(M^{ed} = M \; \mathrm{mod} \; pq = M \; \mathrm{mod} \; N = M (\because M < N)\)
Vulnerability of RSA Public-Key Encryption Algorithm (RSA 공개키 암호화 알고리즘의 취약점)
- RSA 알고리즘은 Cube Root Attack에 취약하다 알려져 있다.
Cube Root Attack (세제곱근 공격)
많은 경우, System Burden을 줄이기 위해 \(e = 3\) 으로 비교적 작게 설정한다.
이렇게 될 경우, \(C = M^3 \; \mathrm{mod} \; N\) 에서 \(M^e\) 값이 \(N\)보다도 작아서
\(C = M^3\)가 되는 수가 있고,
공격자는 이를 예상하여 세제곱근 연산을 취해 평문을 그대로 얻어낼 수 있는 취약점이 생겨버린다.
또한, Chinese Remainder Theorem에 의해
\(M^3 \; \mathrm{mod} \; n_1 = C_1\)
\(M^3 \; \mathrm{mod} \; n_2 = C_2\)
\(M^3 \; \mathrm{mod} \; n_3 = C_3\)
이면
\(M^3 = C \; (\mathrm{mod} \; n_1\cdot n_2\cdot n_3)\)
이다.
이것이 의미하는 바는, 공격자가 3건(\(C_1, C_2, C_3\))의 메시지 도청에만 성공하면
Modulo 연산의 값이 커져(\(n_1\cdot n_2 \cdot n_3\))
\(M^3\)값에 Modulo 연산이 취해지지 않아 세제곱근 공격으로 Break될 수 있음을 시사한다.
* Chinese Remainder Theorem (CRT) (중국인의 나머지 정리) (URL)
[Discrete Mathematics] Chinese Remainder Theorem (CRT) | 중국인의 나머지 정리
Chinese Remainder Theorem (CRT) 중국인의 나머지 정리 \(x \equiv 1\; \mathrm{(mod \; 3)},\\ x \equiv 2 \; \mathrm{(mod \; 5)},\\ x \equiv 3 \; \mathrm{(mod \; 7)}\) 을 만족하는 \(x\)를 구하는 문제에..
dad-rock.tistory.com
Reference: Information Security: Principles and Practice 2nd Edition
(Mark Stamp 저, Pearson,f 2011)
Reference: Computer Security: Principles and Practice 3rd Edition
(William Stallings, Lawrie Brown, Pearson, 2014)
Reference: 2022학년도 1학기 홍익대학교 네트워크 보안 강의, 이윤규 교수님
