Chapter 8. 공개 키 암호 시스템(Public Key Cryptosystems)
1절. Diffie-Hellman Key
디피-헬먼 키 교환(Diffie-Hellman Key Exchange)
역사
1976년 Whitfield Diffie와 Martin Hellman에 의해 처음 발표
몇 년 전 영국 정부 통신 본부(GCHQ)에서 별도로 개발되었으나 기밀로 유지
키 교환
- 사전 정보가 없는 두 당사자가 안전하지 않은 통신 채널에서 공동으로 공유 비밀 키를 설정
디피-헬만 문제 계산
- $g$를 어떤 그룹 $G$의 생성자로 설정
임의로 선택된 정수 $x$와 $y$에 대해, DHP는 아래처럼 정의
- 주어진 요소 $g$와 값 $g^x$, $g^y$ 로부터 $g^{xy}$ 의 값 계산
- 이산 로그 문제(DLP)만큼 어려운 난이도
공식(Scheme)
앨리스와 밥은 순환 그룹 소수 차수 $q$의 $G$와 생성자 $g∈G$에 합의
(소수 차수의 순환 그룹이 권장)앨리스는 $1 ≤ a < q$ 범위의 랜덤 정수 $a$ 선택 후 $pk_A = g^a$를 밥에게 전송
밥은 $1 ≤ b < q$ 범위의 랜덤 정수 $b$ 선택 후 $pk_B=g^b$를 앨리스에게 전송
- 앨리스는 $(pk_B)^a = (g^b)^a=g^{ab}$ 계산
- 밥은 $(pk_A)^b = (g^a)^b=g^{ab}$ 계산
예시
앨리스와 밥은 $G=Z_{23}^∗$ $(p=23, q=22)$및 $g=5$에 동의
앨리스는 $a = 6$을 선택하고 $pk_A = 5^6$ $mod$ $23$ $=$ $8$을 밥에게 전송
밥은 $b = 15$를 선택하고 $pk_B = 5^{15}$ $mod$ $23 = 19$를 앨리스에게 전송
앨리스는 $(pk_B)^a = 19^6$ $mod$ $23 = 2$를 계산
밥은 $(pk_A)^b = 8^{15}$ $mod$ $23 = 2$를 계산
2절. ElGamal Encryption
엘가말 암호(EIGamal Encryption)
키 생성
- 앨리스는 소수 차수 $q$를 가진 순환군 $G$와 생성자 $g ∈ G$ 선택
- 앨리스는 개인 키 $x ∈ {1,…,q−1}$를 임의로 선택
- 공개 키 $y = g^x$계산
암호(Encryption)
- 밥은 임의의 정수 $r ∈ {1,…,q−1}$를 선택
- $c_1 = g^r$ 을 계산
- 메시지 $m ∈ G$ 암호화를 위해 밥은 $c_2=my^r(=mg^{xr})$을 계산
- 밥은 암호문 $(c_1, c_2)$를 앨리스에게 전송
복호화
- 앨리스는 $c_2(c_1^x)^{−1} = mg^{xr}(g^{rx})^{−1} = m$ 계산 후 메시지 복호화
결정적 디피-헬만 가정 (Decisional Diffie-Hellman assumption)
DDH 가정에 따르면, $(g^a, g^b, g^{ab})$와 $(g^a, g^b, g^c)$의 확률 분포가 계산적으로 구분 불가능하다고 가정
$a, b, c$는 $Z_q$ 에서 임의로 선택된 값
예시
키 생성
앨리스는 $G=Z_{19}^∗ (p=19, q=18)$와 $g=10$ 선택
앨리스는 개인 키 $x=5$ 선택 후 공개 키 $y = g^x = 10^5$ $mod$ $19 = 3$ 계산
암호화
밥은 $r = 6$을 선택 후 $c_1 = g^r = 10^6$ $mod$ $19 = 11$ 계산
메시지 $m = 17$ 암호화를 위해 밥은 $c_2 = my^r = 17⋅3^6$ $mod$ $19 = 5$ 계산
밥은 암호문 $(c_1, c_2) = (11,5)$를 앨리스에게 전송
복호화
- 앨리스는 $5⋅(11^5)^{−1} ≡ 5⋅(7)^{−1} ≡ 5⋅11 ≡ 17$ ($mod$ $19$)일 때 $m = c_2(c_1^x)^{−1} = 5⋅(11^5)^{−1}$ $mod$ $19 = 17$ 계산 후 메시지 복호화
3절. Man-in-the-Middle Attack
중간자 공격(Man-in-the-Middle Attack)
- MITM, MitM, MIM, MiM, MITMA로 축약
- 공격자가 두 당사자 간의 통신을 몰래 중계하고 경우에 따라 통신 내용을 변경하는 공격
- 통신 당사자들은 서로 소통하고 있다고 생각