Discrete Logarithm Based Problem

0. 시작하기전에

이 문제를 이해하기 전에 알아야할 것이 있다.

문제 A(하위)를 풀 수 없으면 다른 문제 B(상위)도 풀 수 없다. -> 안전 (명제)

다른 문제 B를 풀 수 있으면 문제 A를 풀 수 있다. -> 안전 (대우)

예를들어 RSA(B)를 깨는 공격자가 그 알고리즘을 이용해 Factorization문제(A)를 깨는 것을 보여주면 이 문제는 안전하다고 말할 수 있다.

어렵게 들릴지 모르겠지만 다음 내용만 이해하면된다.

어떠한 난제가 안전함을 보여주기 위해선 polynomial time reduction을 보여주면 된다.

이는 한문제를 다항식 시간 안에 다른 문제로 바꾸고 그 문제의 해를 다른 문제의 해로 바꾸는 방법이나 과정을 말한다. 

Discrete Logarithm Based Problem이 Polynomial time안에 풀리지 않는다는 직접적인 증명은 존재하지 않는다.

우리가 공부할 다음문제들은 아래와 같은 난이도를 지녔다.

DDH (decisional Diffie Helman) <= CDH (Computotional Diffie Helman) <= DLP (Discrete Logarithm Problem)

DLP보다 낮은 문제인 DDH와 CDH는 훗날 DLP가 풀리게 되면 CDH, DDH 또한 자동으로 풀리게 된다.

1. DLP

DLP는 하나의 로그문제이다. 로그값을 구하는 것은 binary search 기법으로 쉽게 찾을 수 있다.

범위를 크게 잡고 반 씩 줄여나가면서 찾으면 되기 때문이다.

하지만 modulus 연산이 있을 경우 찾을 수 없다. 이 점을 이용한 것이 DLP (Discrete Logarithm Problem)이다

2. CDH (computotional Diffie Helman)

다음과 같은 CDH는 DLP 보다 쉬운문제이다.

3. DDH (Decisional Diffie Helman)

DDH는 CDH보다도 더 쉬운문제이다.

4. ElGamal

1. ElGamal 키 생성 (Key Generation)

1) 소수 p를 선택한다.

2) p보다 작은 소수 alpha를 선택한다.

3) 개인키 : 0보단 크고 p-1 보다 작은 수

4) 공개키 : y = alpha ^ x mod p 를성립할 때 (y, alpha, p)

2. ElGamal 암호화 (encryption)

개인키를 k라 할 때 여기서 난수 k를 재사용한다면 어떤 문제가 발생할까?

3. ElGamal 복호화 (decryption)

4. 만약 CDH 문제가 풀린다면?

CDH문제가 물린다면 ElGamal 문제 또한 풀 수있다.

난이도 : ElGamal = DDH -> CDH -> DLP

4. ElGamal 을 이용한 서명

1) 서명 및 인증 방법

Verification이 맞는지 확인은 다음과 같이 하면 된다.

2) 여기서도 K가 재사용된다면??