Elgamal 암호 방법 [컴퓨터보안]

오늘은 RSA 다음으로 Elgamal 방법을 알아보려고 한다.

 

 

이산 대수를 구하는 것이 어려운 것을 이용한다.

영어로는 (Discrete Logarithm Problem, DLP)

 

암호문의 길이가 2배가 되어버린다는 결점을 가지고 있는 암호이다.

 

 

어디서 많이 본 식이네??

암호화 할 때 이 식을 사용할 것이다.

 

P가 소수이고, g 가 원시근일 때,  y,g,p를 알고 x를 구하는 것으로 계산한다.

P가 큰 소수일 때 x를 구하는 것은 시간상으로 불가능에 가깝다.

Elgamal 암호에서는 x가 개인키, y가 공개키로 사용된다.

 

 

---

그 전에 알아야 할 것이 몇 개 있다.

 

++간단하게 설명하겠다.

원시근(primitive root)란

(n)집합 A가 있고 원소로는 {a,b,c,d}를 포함하고 있을 때, a부터 d까지 차레로 원소 값 하나씩 거듭제곱하여(a,a^2,a^3,…) 양의 정수 n으로 나눴을 때, 나머지가 집합 A의 원소 값{a,b,c,d}를 전부 포함하고 있는 원소 값을 찾습니다. 만약 원소 b가 집합A의 값을 다 가진다면 b는 n의 원시근이 된다.

 

5를 예로 들자면

2와 3만이 원시근이다

 

2,4,8,16,32,.. mod5를 하면 2,4,3,1, …. {1,2,3,4}를 가진다.

3,9,27,81,… mod5를 하면 3,4,2,1,….. {1,2,3,4}를 가진다.

 

++위수란

예를 들자면

1이 되는 최소의 자연수가 2나 5가 6으로 제일 크다.

 

하지만 Elgamal 암호에서는 a는 소수가 된다. 그래서 위에 식에서

X가 키의 개수가 되고 사용할 수 있는 키의 개수는 x-1개가 된다.

 

 

 

 

---

 

 

 

그래서 실제로 어떻게 암호를 하느냐??

 

 

 

1. BOB이 개인키와 공개키를 만든다. 

 

**2와 p-2 사이의 정수를 고르는 이유

실제로 사용할 수 있는 키의 개수는 1 ~ p - 1까지 사용할 수 있지만 다음과 같은 이유 때문에 제외된다.

​

개인키가 1일 경우 : 공개키가 원시원소가 되고 이를 통해 개인키를 유추할 수 때문에 안전성에 문제가 있다.(원시원소는 공개되기 때문)

개인키가 p - 1일 경우 : p - 1을 제곱할 경우 나머지가 1이 되기 때문이다. 즉, 공개키가 1이 되고 위와 마찬가지로 개인키를 유추할 수 있다.

​

2. ALICE가 BOB에게 받은 공개키로 K를 만든다.

r는 0부터 p-1 사이의 랜덤 수이다.

r이 랜덤 수이기 때문에 암호화를 할 때마다 다른 K 값이 나와 같은 평문이라도 다른 암호문이 나오게 된다.

​

3. ALICE는 최종 암호문인 C를 생성한다.

C1 : BOB이 K 값을 BOB의 개인키로 알 수 있게 하는 암호문이며 r을 공개할 수 없기 때문에 이와 같은 암호문으로 보낸다.

C2 : 실질적인 암호문. 평문과 K를 곱해 p로 나눈 나머지 값이다.

​

4. BOB이 자신의 개인키로 K를 얻고 암호문을 복호화 한다.

자신의 개인키로 C1을 복호화 하여 K를 얻는다.

K로 C1을 나눠 p로 나눈 나머지 값을 구하여 암호문으로부터 평문을 얻는다.

 

※ K 값을 얻을 수 있는 이유

 

 

예를 들어서 숫자를 넣어보면

 

M이 평문 p는 소수 a가 원시근이라 보면 되겠다.

1

2

3

4

 

 

**이러한 mod 를 쓸 때 오일러 법칙이 정말 도움된다.

 

 

취약점을 살짝 말하자면 2가지 정도??

 

 1) 작은 모듈러스 공격(Low-Modulus Attack)
   - p의 값이 충분히 크지 않을 경우 전수 조사나 이산대수의 성질 을 이용한 효율적인 알고리즘을 통하여 개인키 d나 임의의 값 r을 찾아낼 수 있다. p는 적어도 2048 비트

 2) 알려진 평문 공격(Known-Plaintext Attack)
   - 평문 m에 대응하는 암호문