[CRYPTO]Other_PublicKey_Cryptosystems

 

Diffie-Hellman Key Exchange

• 역사:
  • 1976년에 Whitfield Diffie와 Martin Hellman이 처음 발표한 키 교환 방식.
  • 그러나 이보다 몇 년 전 GCHQ(영국 정부 통신본부)에서 독립적으로 개발되었으나 기밀로 유지되었음.
• 키 교환:
  • Diffie-Hellman 키 교환 방식은 서로를 모르는 두 당사자가 안전하지 않은 채널을 통해 공통된 비밀 키를 생성할 수 있도록 함.
  • 이 키는 이후 암호화 통신에 사용될 수 있음.
• (계산적) Diffie-Hellman 문제:
  • g: 특정 그룹 G의 생성자(기준 값).
  • x, y: 무작위로 선택된 정수.
  • 주어진 g, g^x, g^y 값으로부터 g^{xy}를 계산하는 것이 매우 어려움.
  • 대부분의 그룹에서 이 문제는 이산 로그 문제(DLP, Discrete Logarithm Problem)와 거의 비슷한 난이도를 가짐.

Diffie-Hellman 키 교환 절차

1. 공통 값 합의:
   • Alice와 Bob은 순환 군 G(주로 소수 차수 q를 가지는 군)와 생성자 g를 사전에 공유한다.
   • G는 소수 차수의 순환 군을 사용하는 것이 권장된다.
2. Alice의 단계:
   • Alice는 임의의 정수 a를 선택 (1≤a<q).
   • pkA= g^a를 계산하고, Bob에게 전송한다.
3. Bob의 단계:
   • Bob도 임의의 정수 bbb를 선택 (1≤b<q).
   • pkB=g^b를 계산하고, Alice에게 전송합니다.
4. Alice의 키 계산:
   • Alice는 Bob으로부터 받은 pkB​를 자신의 a 값으로 거듭 제곱하여 (pkB)^a=(g^b)^a=g^ab 계산한다.
5. Bob의 키 계산:
   • Bob도 Alice로부터 받은 pkA​를 자신의 b 값으로 거듭 제곱하여 (pkA)^b=(g^a)^b=g^ab 를 계산한다.

ElGamal 암호화 과정

1. 키 생성 (Key Generation):

• Alice는 다음을 수행합니다:
  1. 순환 군 G와 차수 q 및 생성자 g를 선택한다.
  2. 비밀 키 x를 무작위로 선택 (1≤x≤q−1).
  3. 공개 키 y = g^x를 계산합니다.
     • x: 비밀 키
     • y: 공개 키

2. 암호화 (Encryption):

• Bob은 다음을 수행합니다:
  1. 무작위 값 r을 선택 (1≤r≤q−1).
  2. c1=g^r를 계산합니다.
  3. 메시지 mmm을 암호화하여 c2=m⋅y^r(=m⋅g^(xr))를 계산합니다.
  4. 암호문 (c1,c2)를 Alice에게 보낸다.

3. 복호화 (Decryption):

• Alice는 다음을 수행합니다:
  1. 암호문 (c1,c2)를 받는다.

---

4. Decisional Diffie-Hellman 가정 (DDH Assumption):

• DDH 가정은

• 와

• 가 계산적으로 구별할 수 없다고 가정.
  • 여기서 a,b,c는 Zq​에서 무작위로 선택된 값.

 

---

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

1. 정의:
   • 암호학과 컴퓨터 보안에서 중간자 공격은 두 당사자가 서로 직접 통신한다고 믿는 상황에서 공격자가 비밀리에 그 통신을 가로채거나 수정하는 공격 방식.
   • 줄여서 MITM, MitM, MiM 또는 MITMA라고 불리기도 한다.
2. 작동 방식:
   • A와 B가 통신하려고 시도할 때, 공격자가 두 당사자 사이에 끼어든다.
   • 공격자는 A와 B의 메시지를 각각 가로채서 수정하거나 다른 정보를 전달할 수 있.
   • 이 과정에서 A와 B는 자신들이 직접 통신하고 있다고 착각한다.