[컴퓨터보안] El Gamal (엘가말) 과 Diffie - Hellman (디피헬만) 프로토콜

El Gamal (엘 가말) 

RSA 알고리즘은 소인수분해가 어렵다는 점을 이용하였고 El Gamal은 이산대수의 어려움을 이용하였다.

큰 소수 p를 정하고 p보다 작은 임의의 g,x를 선택한다.

방법 :

1. Y = g^x mod p 를 계산한다. 
2. 공개키 : Y, p, g 가 되고 비밀키 : x 가 된다.
3. p-1과 relative prime 한 임의의 k를 정한다.
4. 암호화는 a = g^k mod p , b = M*Y^k mod p 인 (a,b)를 정한다. (M은 암호화할 값)
5. 복호화는 b/a^x mod p = y^k*M/a^x mod p = M

특징은 k를 임의로 설정하기 때문에 동일한 M에 대해 매번 다르게 암호화 된다. (RSA와의 차이점) 그리고 Ciphertext는 원래 M 길이의 2배가 된다.

Diffie - Hellman 프로토콜

• 송/수신자를 위한 1회용 secret/shared session key agreement protocol 
• 보안성 없는 매체(Internet)을 통해 비밀키를 교환
• IPSEC과 상용sw에 많이 사용

방법 : 

1. p,g : 큰 정수 (1 < p < g) 모든 사용자에게 공개
2. Alice는 임의로 a 생성 , A = g^a mod p를 계산
3. Bob은 임의로 b 생성, B = g^b mod p를 계산
4. A,B를 서로 교환
5. Alice와 Bob은 K = g^ab mod p를 계산 (K를 대칭키로 사용)

문제점 :

중간자 공격 (man in the middle attack) 

해커가 a,b 값을 몰라도 중간에 가로채서 Bob과 Alice를 속일 수 있다. 해커가 Ailce가 보내는 값을 가로채서 임의로 c를 생성해 C = g^c mod p를 Bob에게 전송한다. 마찬가지로 Bob이 보내는 것을 가로채서 똑같은 방법으로 Alice를 속인다. 그러면 Alice와 Bob은 해커와 공유한 키를 서로간의 공유한 키로 생각하게 된다.

이 문제는 사용자 인증을 하지 않아서 생기는 문제이다. 전자서명과 인증으로 보안을 한다.