ANALYSIS OF POSSIBLE PRE-COMPUTATION AIDED DLP SOLVING ALGORITHMS
3
조회
0
다운로드
0
인용
0
참고문헌
키워드
초록
A trapdoor discrete logarithm group is a cryptographic prim- itive with many applications, and an algorithm that allows discrete loga- rithm problems to be solved faster using a pre-computed table increases the practicality of using this primitive. Currently, the distinguished point method and one extension to this algorithm are the only pre-computation aided discrete logarithm problem solving algorithms appearing in the related literature. This work investigates the possibility of adopting other pre-computation matrix structures that were originally designed for used with cryptanalytic time memory tradeoff algorithms to work as pre-computation aided discrete logarithm problem solving algorithms. We find that the classical Hellman matrix structure leads to an algorithm that has performance advantages over the two existing algorithms.
Abstract
A trapdoor discrete logarithm group is a cryptographic primitive with many applications, and an algorithm that allows discrete logarithm problems to be solved faster using a pre-computed table increases the practicality of using this primitive. Currently, the distinguished point method and one extension to this algorithm are the only pre-computation aided discrete logarithm problem solving algorithms appearing in the related literature. This work investigates the possibility of adopting other pre-computation matrix structures that were originally designed for used with cryptanalytic time memory tradeoff algorithms to work as pre-computation aided discrete logarithm problem solving algorithms. We find that the classical Hellman matrix structure leads to an algorithm that has performance advantages over the two existing algorithms.
참고문헌 (18)
- "GPU Rainbow Cracker"[URL]
- "Distributed Rainbow Table Project"[URL]
- "Windows Password Cracker"[URL]
- "RainbowCrack Project"[URL]
- E. P. Barkan, "Cryptanalysis of ciphers and protocols", Ph.D., pp.2006
- E. Barkan, "Rigorous bounds on cryptanalytic time", memory tradeoffs, 2006, pp.4117, 1~21[DOI]
- D. J. Bernstein, "Computing small discrete logarithms faster, in: IN-DOCRYPT 2012", LNCS, 7668, pp.317~338 (2012), Springer
- D. J. Bernstein, "Non-uniform cracks in the concrete: the power of free precomputation, in: ASI-ACRYPT 2013", LNCS, 8270, pp.321~340 (2013), Springer
- A. Biryukov, S, "Improved time-memory trade-offs with multiple data, in: SAC 2005", LNCS, 3897, pp.110~127 (2006), Springer
- A. Biryukov, "Cryptanalytic time", memory, LNCS, pp.2000, 1976[DOI]
- C. Calik, "How to invert one-way functions: time-memory trade-off method", 석사, pp.2007
- A. E. Escott, "Attacking elliptic curve cryptosystems using the parallel Pollard rho method", CryptoBytes, 4, pp.15~19 (1999)
- M. E. Hellman, "A cryptanalytic time-memory trade-off", IEEE Trans. Inform. Theory, 26(4), pp.401~406 (1980)
- R. Henry, "Making a nymbler Nymble using VERBS, in:PETS 2010", LNCS, 6205, pp.111~129 (2010), Springer
- Y. Hitchcock, "The efficiency of solving multiple discrete logarithm problems and the implications for the security of fixed elliptic curves", Int. J. Inf. Secur, 3, pp.86~98 (2004)
- J. Hong, "The cost of false alarms in Hellman and rainbow tradeoffs", Des. Codes Cryp-togr, 57(3), pp.293~327 (2010)
- J. Hong, "A comparison of cryptanalytic tradeoff algorithms", J. Cryptology, 26(4), pp.559~637 (2013)
- D. Huhnlein, "Towards practical non-interactive public-key cryptosystems using non-maximal imaginary quadratic orders", Des. Codes Cryptogr, 39(3), pp.281~299 (2003)