Reduction of factorization, discreet logarithm and elliptic curve logarithm problems to solving associated satisfiability problems
F.M. Dostoevsky Omsk State University
Full text of article: Russian language.
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.
- 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.
- 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.
- 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; электронная почта: firstname.lastname@example.org ; тел: +7 (846 2) 332-56-22, факс: +7 (846 2) 332-56-20