정보보호론-(13) 공개키 암호화, RSA 알고리즘, Diffie-Hellman 알고리즘 원리

정보보호론-(13) 공개키 암호화

<그림 1: 공개키 암호화>

대칭키 암호화의 장단점
- 강력하고 효과적인 암호화 서비스를 제공
- 그러나, 통신 당사자간 최초 비밀키를 분배하는 문제가 있음

공개키 암호화의 장점
- 한 개의 공개키(Public key)와 한 개의 개인키(Private key)로 구성되는 한 쌍의 키를 사용함으로써 대칭키 암호화의 문제점을 해소함

대칭키 암호화의 원리
- 바이트 또는 블록 단위의 평문을 전치(Transposition)와 치환(Substitution)에 기초하여 암호화

공개키 암호화의 원리
- 숫자로 표현되는 평문을 수학적 함수를 응용하여 다른 숫자로 변환에 기초하여 암호화
- 암호화에 사용된 함수의 역함수를 계산하는 것이 매우 어려운 수학적 특성을 이용함
- 비밀키(Trapdoor)가 주어지면 쉽게 역함수 계산 가능

공개키 암호화에 사용되는 대표적인 수학 원리
- 모듈로 연산(Modular Arithmetic)
- 지수 모듈로 연산
- 이산 대수(Discrete Logarithm) 연산

모듈로 연산(Modular Arithmetic)
- 정수(a)를 양의 정수(n)로 나누어 나머지(r)을 계산하는 연산
- a mod n = r

모듈로 연산의 성질
(1) (a + b) mod n = [(a mod n) + (b mod n)] mod n
(2) (a - b) mod n = [(a mod n) - (b mod n)] mod n
(3) (a * b) mod n = [(a mod n) * (b mod n)] mod n

공개키 암호화에 사용되는 모듈로 성질은 "모듈로 곱셈 연산(3)"

모듈로 곱셈 연산의 항등원?
* 항등원? 연산 결과가 자기 자신이 나오게하는 피연산자 -> 모듈로 곱셈 연산에선 1
* 역원? 연산 결과가 항등원이 나오게하는 피연산자 -> a * b = 1(mod n)

정수 a가 모듈로 곱셈에 대한 역원을 갖게하는 필요충분조건은?
- a와 n은 서로소(ⓑ)
- gcd(a,n) = 1 (mod n)
- gcd(a.n) = a * n

오일러의 Φ(n) 함수
- n보다 작으면서 n과 서로소인 정수의 개수

오일러의 Φ(n) 함수의 특징
(1) Φ(1) = 0
(2) Φ(p) = p-1, p is prime number
(3) Φ(m * n) = Φ(m) * Φ(n), m과 n이 서로소인 경우(ⓐ)

오일러 함수의 응용
- N = P * Q, P와 Q는 소수
- Φ(N) = Q(P*Q) = Q(P) * Q(Q) = (P-1)(Q-1)
- N이 큰 소수 P와 Q의 곱으로 계산된 사실을 모르는 경우 Φ(N) 값을 구하기 위해서는 N을 소인수 분해 해야함
- 그러나 N의 크기가 매우 큰경우(1024bit) 현재 컴퓨터 성능으로 Φ(N) 값을 구할 수 없음

오일러의 1차 정리
- a^Φ(n) = 1(mod n), a와 n이 서로소

오일러의 2차 정리
- a^Φ(n) = 1(mod n), a<n

RSA 공개키 암호화
- 지수 모듈로 연산, 오일러 정리에 기초하여 공개키(Public key)와 개인키(Private key)를 생성하는 방법과 이들을 사용한 암호화 및 복호화 방법을 제시
(1) RSA 키 생성 알고리즘
(2) RSA 암호화, 복호화 알고리즘

모듈로 곱셈 연산의 항등원 : 1
모듈로 곱셈 연산의 역원은 서로소인 수가 있어야 존재

RSA 키 생성 알고리즘
1. 두 개의 서로 다른 큰 소수 p, q를 선택한다.(ⓐ특징을 이용하기 위함)
2. n = p * q를 구한다.
3. Φ(n) = Φ(p*q) = Φ(p) * Φ(q) = (p-1)(q-1)
4. 1< e < Φ(n)의 관계를 만족하고 Φ(n)과 서로소의 관계인 소수 e를 선택한다.(ⓑ특징을 이용하기 위함)
5. ⓑ특징에 의하여 e는 mod Φ(n) 곱셈 연산에 대해 역원(d)를 가지므로 de = 1 mod Φ(n) 연산을 통해 역원(d)를 구할 수 있다. de - 1 = 0 mod Φ(n)
6. 가능한 역원(d)값의 후보 중 d < Φ(n) 을 만족하는 가장 큰 수가 선택된다.
7. (n, e)는 RSA 공개키이다.
8. (n, d)는 RSA 개인키이다. 

RSA 키 생성 알고리즘 예시
1. p =5 , q=7을 선택한다.
2. n = p* q = 35를 구한다.
3. Φ(n)=Φ(35)=Φ(5)*Φ(7) = 4 *6 = 24
4. 1 < e < 24(=Φ(n))의 관계를 만족하는 소수 e=5를 선택한다.
5. de -1 = 0 mod 24 <=> 5d -1 = 0 mod 24를 만족하는 가장 큰 d를 구한다.
6. d = 5
7. 공개키(n,e) = (35,5)
8. 개인키(n,d) = (35,5)

RSA 암호화/복호화
- 암호화 : C = P^e mod n
- 복호화 : P = C^d mod n

개인키를 알고있는 사용자는 (n,d)값을 이용해 복호화 연산을 쉽게 수행할 수 있지만 개인키를 알고 있지 않은 공격자는 d값을 알아내기 위해 de -1 = 0 mod Φ(n)을 풀어내야 한다. 즉, Φ(n)값을 구해내기 위해 큰 정수 n을 소인수 분해해야 하는데 n값이 크면 수학적으로 구해낼 수 없다.

공개키에 의한 암호문의 복호화 과정
- 평문 P는 n보다 작은 수
P = C^d mod n
= (P^e mod n)^d mod n
= (P^de mod n) mod n (ⓐ)
= (P^(kΦ(n)+1) mod n) mod n (de = 1 mod Φ(n))
= (P^Φ(n) mod n)^k(P mod n)(ⓐ)
= 1 * (P mod n) // 오일러의 2차 정리
= P

Diffie-Hellman 키 교환 알고리즘
- 1976년 Diffie와 Hellman에 의해 통신 당사간 보안이 유지되지 않는 통신 환경에서 비밀 세션키(대칭키)를 교환할 수 있는 알고리즘이 개발됨
- 이산 대수 문제 계산의 어려움을 활용한 트랩도어 함수 활용
- 중간자 공격에 취약함
- IPsec, TLS(SSL) 프로토콜이 중간자 공격 취약점을 보완한 Diffe-Hellman 키 교환 알고리즘을 사용함

Diffie-Hellman 키 교환 알고리즘 절차
(1) 사용자A와 사용자B는 두 개의 임의의 큰 수 p, g를 교환한다.(p는 소수이고 1024bit의 큰 수 이다)
(2) 사용자 A는 1<= x <= p-1 범위 내의 큰 수 x를 자신의 개인키로 선택하고 사용자A의 공개키 K+(A) = R(A) = g^x mod p를 생성한다.
(3) 사용자 A의 공개키 K(A) = g^x mod p를 사용자B에게 전송한다.
(4) 사용자 B는 1<= y <= p-1 범위 내의 큰 수 y를 자신의 개인키로 선택하고 사용자B의 공개키 K+(B) = R(B) = g^y mod p를 생성한다.
(5) 사용자 B는 사용자A의 공캐키와 자신의 개인키를 결합시켜 세션키 S = R(A)^y mod p 를 생성한다.
(6) 사용자 B는 공개키 K(B) = g^y mod p를 사용자A에게 전송한다
(7) 사용자 A는 사용자B의 공개키와 자신의 개인키를 결합시켜 세션키 S = R(B)^x mod p를 생성한다.

Diffie-Hellman 키 교환 알고리즘 예시
p=11, g=3, A의 개인키 = 3, B의 개인키 = 4 인 경우 세션키를 구하시오.
사용자 A의 공개키 = R(A) = g^x mod p = 3^3 mod 11 = 5
사용자 B의 공개키 = R(B) = g^y mod p = 3^4 mod 11 = 4
사용자 A의 세션키 = S = R(B)^x mod p = 4^3 mod 11 = 9
사용자 B의 세션키 = S = R(A)^y mod p = 5^4 mod 11 = 9

Diffie-Hellman 키 교환 알고리즘은 공격자가 사용자(A)와 사용자(B) 사이에서 중간자 공격을 통해 세션키를 획득할 수 있다. 즉, 공격자는 자신의 개인키(z)를 사용해서 만든 공격자의 공개키 R(Z) = g^z mod p를 마치 사용자(A)와 사용자(B)의 공개키인 것처럼 위조해 사용자들에게 전달하여 사용자(A)와 사용자(B)가 세션키(S)=R(Z)^x mod p를 사용하게 할 수 있다. 그런데, R(Z)=g^z mod p이고 S=R(Z)^z mod p로 공격자가 세션키를 구해낼 수 있으므로 사용자간 통신이 공격자에게 노출된다.

기타 공개키 암호화 알고리즘
- ElGamal 알고리즘
- Rabin 알고리즘
- 타원 곡선 암호(ECC - Elliptic Curve Cryptosystem) : RSA 보다 상대적으로 적은 키 길이(160비트)를 갖는 장점

Reference
1. 

제13강+공개키암호화.pdf

0.58MB

2. https://www.youtube.com/watch?v=_5sMsWU7ajs