Сведение задач факторизации, дискретного логарифмирования и логарифмирования на эллиптической кривой к решению ассоциированных задач «Выполнимость»

Дулькейт В.И.

Аннотация:
В работе предлагаются алгоритмы консервативного сведения задач факторизации, дискретного логарифмирования и логарифмирования на эллиптической кривой к задаче «ВЫПОЛНИМОСТЬ», проводится анализ работы современных алгоритмов решения задачи «ВЫПОЛНИМОСТЬ» (SAT - решателей) на полученных КНФ. Исследуется стойкость рассматриваемых задач к восстановлению полного ключа по его известным фрагментам.

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.

Литература:

  1. 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.
  2. 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.
  3. 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/ (дата обращения: 12.10.2009).
  4. Семенов А. А. Логико-эвристический подход в криптоанализе генераторов двоичных последовательностей // Труды международной научной конференции ПАВТ‘07. - 2007. - Т. 1. - С. 170-180.
  5. Беспалов Д. В., Семёнов А. А. О логических выражениях для задачи 2-ФАКТОРИЗАЦИЯ // Вычислительные технологии. - 2002. - Т. 7.
  6. 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 (дата обращения: 06.07.2009).
  7. Дулькейт В. И., Файзуллин Р. Т., Хныкин И. Г. Непрерывные аппроксимации решения задачи ВЫПОЛНИМОСТЬ применительно к криптографическому анализу асимметричных шифров // Компьютерная оптика. - 2009. - Т. 33, № 1. - С. 86-91.
  8. Дулькейт В. И., Файзуллин Р. Т., Хныкин И. Г. Алгоритм минимизации функционала, ассоциированного с задачей 3-sat и его практические применения // Компьютерная оптика. - 2008. - Т. 32, № 1. - С. 68-73.
  9. Салаев Е. В., Файзуллин Р. Т. Применение метода последовательных приближений с инерцией к решению задачи Выполнимость // Вестник Томского Государственного Университета. - 2006. - Т. 17.
  10. Столингс В. Криптография и защита сетей: принципы и практика. - М.: Вильямс, 2001.
  11. Jurisic A., Menezes A. Elliptic curves and cryptography. // Dr. Dobb’s Journal. - April, 1997.
  12. Sat competition [Сайт].
    URL: http://www.satcompetition.org (дата обращения: 10.08.2009).

References:

  1. 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.
  2. 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.
  3. 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/
  4. 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).
  5. Bespalov D.V., Semjonov A.A. About logical statements for 2-FACTORIZATION problem // Calculation technologies. - 2002. - V. 7. - (in Russian).
  6. 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
  7. 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).
  8. 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).
  9. 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).
  10. Stallings W. Cryptography and network Security. - Moscow: Williams, 2001 - (in Russian).
  11. Jurisic A., Menezes A. Elliptic curves and cryptography. // Dr. Dobb’s Journal. - April, 1997.
  12. 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