Reduction of factorization, discreet logarithm and elliptic curve logarithm problems to solving associated satisfiability problems

V.I. Dulkeyt## F.M. Dostoevsky Omsk State University

V.I. Dulkeyt

Full text of article: Russian language.

Abstract:

The algorithms of conservative reduction of factorization, discreet logarithm and elliptic curve logarithm problems to satisfiability problem (SAT) were proposed. The capabilities of modern SAT-solvers for solving produced SAT instances were investigated. The resistance to whole key repairing by its fragments was investigated for considered problems.

Key words: CNF, factorization, discreet logarithm, elliptic curve logarithm, SAT.

References:

- Cook S.A., Mitchel D.G. Finding hard instances for the satis?ability problem // A survey. DIMACS series in discrete mathematics and theoretical computer science. - 1997. - V. 5. - P. 151.

- Massacci F., Marraro L. Towards the formal veri?cation of ciphers: Logical cryptanalysis of DES // Proc. Third LICS Workshop on Formal Methods and Security Protocols, Federated Logic Conferences. - 1999.

- Susem M., Janicic P. Uniform reduction of cryptographic problems to SAT // Faculty of Mathematics, University of Belgrade, Serbia; 2009.

URL: http://argo.matf.bg.ac.yu/events/2009/slides/

- Semenov A.A. Logical and heuristically approach in cryptanalysis of binary sequences generators // Proc. international scientific conference PAVT‘07. - 2007. - V. 1. - P. 170-180. - (in Russian).

- Bespalov D.V., Semjonov A.A. About logical statements for 2-FACTORIZATION problem // Calculation technologies. - 2002. - V. 7. - (in Russian).

- Srebrny M. Factorization with sat - classical propositional calculus as a programming environment // Faculty of Mathematics Informatics and Mechanics at the University of Warsaw. 2004.

URL: http://www.mimuw.edu.pl/~mati/fsat-20040420.pdf

- Dulkeyt V.I., Faizullin R.T., Khnykin I.G. Continuous approximation of SAT decision as applied to cryptographic analysis of asymmetric ciphers // Computer Optics. - 2009. - V. 33, N 1. - P. 86-91. - (in Russian).

- Dulkeyt V.I., Faizullin R.T., Khnykin I.G. Algorithm for minimization of functional associated with 3-SAT problem and its practical usage // Computer Optics. - 2008. - V. 32, N 1. - P. 68-73. - (in Russian).

- Salaev E.V., Faizullin R.T. Using the method of sequential approximations with inertia for solving SAT problems // Herald of Tomsk State University. - 2006. - V. 17. - (in Russian).

- Stallings W. Cryptography and network Security. - Moscow: Williams, 2001 - (in Russian).

- Jurisic A., Menezes A. Elliptic curves and cryptography. // Dr. Dobb’s Journal. - April, 1997.

- Sat competition. URL: http://www.satcompetition.org.

© 2009, ИСОИ РАН

Россия, 443001, Самара, ул. Молодогвардейская, 151; электронная почта: ko@smr.ru ; тел: +7 (846 2) 332-56-22, факс: +7 (846 2) 332-56-20