Diffie-Hellman Key Exchange

1. Diffie-Hellman Key Exchange

- 서로 멀리 떨어져 있는 두 사람이 공개 채널을 통해도 shared secret key를 안전하게 만들 수 있게 해주는 방법

- 사용 전 준비(공개 파라미터): Zp*에서의 큰 소수 p, 생성자 g

 

- Alice의 단계: 

  1) 비밀키 a 생성

  2) 공개키 A = g^a (mod p) 계산

  3) 이 A를 Bob에게 보냄

  4) Bob이 보내준 B를 받아 KAB = B^a (mod p) 공유 비밀키 완성

 

- Bob의 단계: 

  1) 비밀키 b 생성

  2) 공개키 B = g^b (mod p) 계산

  3) 이 B를 Alice에게 보냄

  4) Alice가 보내준 A를 받아 KBA = A^b (mod p) 공유 비밀키 완성

 

 

2. Security of Diffie-Hellman Key Exchange

- 목표: Eve(공격자)가 공유 비밀 키 KAB​를 얻는 것을 막는 것

- Eve가 볼 수 있는 정보: p, g, A=g^a, B=g^b

- 만약 Eve가 a 또는 b를 알게 된다면 보안 실패

- 따라서 이산 로그 문제(DLP)가 풀기 어려워야 안전함

- Computational Diffie-Hellman Problem(CDH 문제): 주어진 (g,g^a,g^b)로부터 g^ab를 계산하는 문제

- Eve는 이 문제를 풀 수 있어야 키 g^ab를 얻을 수 있음

- DLP를 풀 수 있으면 CDH도 풀 수 있음

- 하지만 CDH를 푼다고 반드시 DLP를 풀 수 있는건 아님

- 특히 군의 차수가 소수일 때 두 문제는 어려움

 

 

3. Man-in-the-Middle Attack(중간자 공격)

- Eve가 Alice와 Bob 사이를 가로채서 각자에게 다른 공개키를 보내면 어떻게 될까?

  1) Eve가 자신의 비밀키 e 생성 후 E = g^e (mod p)를 계산

  2) Alice가 A를 보내려는 순간, Bob이 B를 보내려는 순간 Eve가 가로채고 대신 자신의 E를 보냄

  3) Alice는 Bob이 E를 보냈다고 착각 -> 공유키 KAE = E^a = g^ea

  4) Bob은 Alice가 E를 보냈다고 착각 -> 공유키 KBE = E^b = g^eb

  5) Alice가 메세지 M을 암호화해서 보냄 -> Bob은 KBE로 해독하려하지만 키가 달라서 실패

  6) 반면 Eve는 양쪽 메세지를 모두 해독 가능

- 해결책 : 상대방이 보낸 공개키가 진짜 그 사람의 것인지 확인하면 됨(Signature)

 

 

4. ElGamal Encryption

- 같은 메세지를 여러번 암호화해도 암호문이 매번 다르게 나옴

- DDH(결정형 디피-헬만 문제)가 어려우면 안전함 : IND-CPA 보장

- DDH Problem: 주어진 (g, g^a, g^b, X)에 대해 X = g^(ab)인지, 혹은 X = g^c (무작위 c)인지 구별하는 문제

- Homomorphic: Enc(M) × Enc(M′) = Enc(M × M′) -> IND-CCA2에 약함

- IND-CCA2 가능: Generic transformation을 사용하면 CCA2까지 방어 가능

 

- Key Generation

  1) 큰 소수 p 선택

  2) Zp* 안에서 차수 q인 부분군 G의 생성자 g 선택

  3) 비밀키 x∈Zq​ 임의 선택

  4) 공개키 = (p,q,g,X), X = g^x (mod p), 비밀키 = x

 

- Encryption : r이 랜덤이기 때문에 매번 암호문이 달라짐

  1) 임의의 난수 r∈Zq​ 선택

  2) C1 = g^r (mod p)

  3) C2 = M⋅X^r (mod p)

  4) 암호문 CT = (C1, C2)

 

- Decryption : C2/C1^x = M⋅g^xr / g^xr = M

 

- Generic Transformation 적용: 해시함수 H를 사용해 공유키 X^r을 길이 l짜리 비트열로 바꿔줌

  1) 암호화 할 때 C2 = M ⊕ H(X^r)

  2) 복호화 할 때 C2 ⊕ H(C1^x) = M