Solving the Discrete Logarithm Problem for Ephemeral Keys in Chang and Chang Password Key Exchange Protocol
1
조회
0
다운로드
0
인용
0
참고문헌
키워드
초록
The present study investigates the difficulty of solving the mathematical problem, namely the DLP (Discrete Logarithm Problem) for ephemeral keys. The DLP is the basis for many public key cryptosystems. The ephemeral keys are used in such systems to ensure security. The DLP defined on a prime field of random prime is considered in the present study. The most effective method to solve the DLP is the ICM (Index Calculus Method). In the present study, an efficient way of computing the DLP for ephemeral keys by using a new variant of the ICM when the factors of are known and small is proposed. The ICM has two steps, a pre-computation and an individual logarithm computation. The pre-computation step is to compute the logarithms of a subset of a group and the individual logarithm step is to find the DLP using the pre-computed logarithms. Since the ephemeral keys are dynamic and change for every session, once the logarithms of a subset of a group are known, the DLP for the ephemeral key can be obtained using the individual logarithm step. Therefore, an efficient way of solving the individual logarithm step based on the newly proposed pre-computation method is presented and the performance is analyzed using a comprehensive set of experiments. The ephemeral keys are also solved by using other methods, which are efficient on random primes, such as the Pohlig-Hellman method, the Van Oorschot method and the traditional individual logarithm step. The results are compared with the newly proposed individual logarithm step of the ICM. Also, the DLP of ephemeral keys used in a popular password key exchange protocol known as Chang and Chang are computed and reported to launch key recovery attack.
Abstract
The present study investigates the difficulty of solving the mathematical problem, namely the DLP (Discrete Logarithm Problem) for ephemeral keys. The DLP is the basis for many public key cryptosystems. The ephemeral keys are used in such systems to ensure security. The DLP defined on a prime field of random prime is considered in the present study. The most effective method to solve the DLP is the ICM (Index Calculus Method). In the present study, an efficient way of computing the DLP for ephemeral keys by using a new variant of the ICM when the factors of are known and small is proposed. The ICM has two steps, a pre-computation and an individual logarithm computation. The pre-computation step is to compute the logarithms of a subset of a group and the individual logarithm step is to find the DLP using the pre-computed logarithms. Since the ephemeral keys are dynamic and change for every session, once the logarithms of a subset of a group are known, the DLP for the ephemeral key can be obtained using the individual logarithm step. Therefore, an efficient way of solving the individual logarithm step based on the newly proposed pre-computation method is presented and the performance is analyzed using a comprehensive set of experiments. The ephemeral keys are also solved by using other methods, which are efficient on random primes, such as the Pohlig-Hellman method, the Van Oorschot method and the traditional individual logarithm step. The results are compared with the newly proposed individual logarithm step of the ICM. Also, the DLP of ephemeral keys used in a popular password key exchange protocol known as Chang and Chang are computed and reported to launch key recovery attack.
참고문헌 (19)
- Discrete Logarithms:Recent Progress, "J. Buchmann", ~, pp.no:T1-12, 98
- H. Cohen, "Handbook of Elliptic and Hyperelliptic Curve Cryptography" (2005), Discrete Mathematics and Applications, CRC Press
- D. Coppersmith, "Discrete logarithms in GF(p)", Algorithmica, 1, pp.1~15 (1986)
- CC. Chang, "A novel three party encrypted key exchange protocol", Computer Stan-dards and Interfaces, 26(5), pp.471~476 (2004)
- W. Diffie, "New Directions in cryptography", IEEE Transaction on Information The ory, 22(6), pp.644~654 (1976)
- D.M Gordon, "Discrete logarithms in GF(p) using the number field sieve", SIAM Journal of Dis-crete Mathematics, 6, pp.124~138 (1992)
- D. E Knuth, "The Art of computer programming", Sorting and Searching, 3 (1973), Addison-Wesley
- McCurely, "The Discrete logarithm problem", Cryptology and computational number theory pro-ceeding of symposia in Applied Mathematics, 42, pp.49~74
- A. Menezes, "On Reusing Ephemeral Keys in Diffie-Hellman Key Agreement Proto-cols", preprint, ~ (2008)
- R. Padmavathy, "A Key Recovery Attack on Chang and Chang Pass-word Key Exchange Protocol", International Conference on Computer and Network Technology (2009)
- J.M Pollard, "Monte Carlo methods for index computation(mod p)", Mathematics of Computation, 32(143), pp.106~110 (1978)
- S. Pohlig, "An improved algorithm for computing logarithms over GF(p) and its cryptographic significance", IEEE Transaction on Information Theory, 24, pp.106~110 (1978)
- J.Silverman, "The xedni calculus and the elliptic curve logarithm problem", Design Codes and Cryptography, 20, pp.5~40 (2000)
- O. Schirokauer, "Discrete logarithms the effectiveness of the index calculus method", Proceeding of ANTS II, 1122, pp.337~361 (1996)
- C. Studholme, "Discrete logarithm problem", 박사, pp.2002
- P.C,Van Oorschot, "On Diffie-Hellman Key agreement with short Exponents", Proceeding of Eurocrypt LNCS, 1070, pp.332~343 (1996)
- D.Weber, "Computing Discrete logarithms with the general number field sieve", Proceeding of ANTS II, LNCS, 1122, pp.99~114 (1996)
- D.Weber, "The solution of McCurleys discrete log challenge", Proceeding of Crypto98, LNCS, 1462, pp.458~471 (1998)
- EJ. Yoon, "Improving the novel three-party encrypted key exchange protocol", Com-puter Standards and Interfaces, 30, pp.309~314 (2008)