Diffie-Hellman 문제는, 다음과 같은 풀리지 않은 문제가 남아있다.
1. Computational Diffie-Hellman Problem
Prime Number p가 주어지고, α를 mod p에 대한 Primitive Root라고 하자. 이때, α^x (mod p), α^y (mod p)가 주어졌을 때, a^(xy) (mod p)를 찾을 수 있는가? 이것은, discrete logarithm 문제를 해결하는 것보다 쉬운지, 어려운지조차 아직 알려져 있지 않다.
2. Decision Diffie-Hellman Problem
Prime Number p가 주어지고, α를 mod p에 대한 Primitive Root라고 하자. 이때 α^x (mod p), α^y (mod p)이고, c !≡ 0 (mod p)일 때, c ≡ α^(xy) (mod p)인지 아닌지를 결정하라.
만약, 이브가 c ≡ α^(xy) (mod p)를 만족하는 c를 찾아냈다고 주장한다고 하자. 그렇다면 이것이 사실인지 아닌지 어떻게 검증할 수 있는가? 만약, Computational Diffie-Hellman 문제를 해결하는 방법을 알고 있다면, 간단히 이것을 계산해서 이 주장이 사실인지 아닌지 검증할 수 있다. 그렇다면, Desicion Diffie-Hellman 문제를 해결하는 방법은 Computational Diffie-Hellman 문제에 대한 해결 방법이 있다는 것을 증명하는 것인가? 이것은 현재까지 알려져 있지 않다.
한가지 명백한 사실은, c를 결정하기 위해서 무작위 수를 계속 대입하여 c ≡ α^(xy) (mod p)가 맞을 때까지 계산해보는 것이다. 그러나 이것은 엄청난 계산량을 필요로 한다. 현 단계에서는, Desicion Diffie-Hellman 문제를 해결하는데 빠른 해결 방법은 알려져 있지만, Computational Diffie-Hellman 문제를 해결하는 빠른 방법은 아직까지 알려져 있지 않다.
Reference
Wade Trappe, Lawrence Washington, Introduction to Cryptograhphy with Coding Theory, Second Edition, PEARSON Education
1. Computational Diffie-Hellman Problem
Prime Number p가 주어지고, α를 mod p에 대한 Primitive Root라고 하자. 이때, α^x (mod p), α^y (mod p)가 주어졌을 때, a^(xy) (mod p)를 찾을 수 있는가? 이것은, discrete logarithm 문제를 해결하는 것보다 쉬운지, 어려운지조차 아직 알려져 있지 않다.
2. Decision Diffie-Hellman Problem
Prime Number p가 주어지고, α를 mod p에 대한 Primitive Root라고 하자. 이때 α^x (mod p), α^y (mod p)이고, c !≡ 0 (mod p)일 때, c ≡ α^(xy) (mod p)인지 아닌지를 결정하라.
만약, 이브가 c ≡ α^(xy) (mod p)를 만족하는 c를 찾아냈다고 주장한다고 하자. 그렇다면 이것이 사실인지 아닌지 어떻게 검증할 수 있는가? 만약, Computational Diffie-Hellman 문제를 해결하는 방법을 알고 있다면, 간단히 이것을 계산해서 이 주장이 사실인지 아닌지 검증할 수 있다. 그렇다면, Desicion Diffie-Hellman 문제를 해결하는 방법은 Computational Diffie-Hellman 문제에 대한 해결 방법이 있다는 것을 증명하는 것인가? 이것은 현재까지 알려져 있지 않다.
한가지 명백한 사실은, c를 결정하기 위해서 무작위 수를 계속 대입하여 c ≡ α^(xy) (mod p)가 맞을 때까지 계산해보는 것이다. 그러나 이것은 엄청난 계산량을 필요로 한다. 현 단계에서는, Desicion Diffie-Hellman 문제를 해결하는데 빠른 해결 방법은 알려져 있지만, Computational Diffie-Hellman 문제를 해결하는 빠른 방법은 아직까지 알려져 있지 않다.
Reference
Wade Trappe, Lawrence Washington, Introduction to Cryptograhphy with Coding Theory, Second Edition, PEARSON Education