Диплом, курсовая, контрольная работа
Помощь в написании студенческих работ

КНФ представления для задач факторизации, дискретного логарифмирования и логарифмирования на эллиптической кривой

Диссертация: КНФ представления для задач факторизации, дискретного логарифмирования и логарифмирования на эллиптической кривой
ДиссертацияПомощь в написанииУзнать стоимостьмоей работы

Таким образом, актуальность данной диссертационной работы определяется необходимостью построения подхода для сведения задач дискретного логарифмирования и логарифмирования в группе точек эллиптической кривой к задаче «ВЫПОЛНИМОСТЬ», что предоставит возможность качественного анализа стойкости этих задач против методов логического криптоанализа. Подстановка открытого pi шифрованного текстов в эту… Читать ещё >

Содержание

  • Введение «
  • ГЛАВА 1. Обзор
    • 1. 1. Логический криптоанализ
    • 1. 2. Методы теории чисел
      • 1. 2. 1. Задача факторизации
      • 1. 2. 2. Задача дискретного логарифмирования
      • 1. 2. 3. Задача логарифмирования на эллиптической кривой
  • ГЛАВА 2. Генерация эквивалентных КНФ
    • 2. 1. КНФ представления для задачи факторизации
      • 2. 1. 1. КНФ представление операции умножения двух чисел
      • 2. 1. 2. Обеспечение консервативности преобразований
      • 2. 1. 3. Сведение задачи факторизации к задаче „ВЫПОЛНИМОСТЬ“
      • 2. 1. 4. Эквивалентные КНФ представления операции умножения двух чисел
      • 2. 1. 5. Сведение задачи факторизации к набору эквивалентных задач
  • ВЫПОЛНИМОСТЬ»
    • 2. 1. 6. 3-КНФ представление операции умножения двух чисел
    • 2. 2. КНФ представление задачи дискретного логарифмирования
    • 2. 2. 1. Кодирование базовых операций
    • 2. 2. 2. Сведение задачи дискретного логарифмирования к задаче «ВЫПОЛНИМОСТЬ»
    • 2. 3. КНФ представление задачи логарифмирования на эллиптической кривой
    • 2. 3. 1. Базовые операции
    • 2. 3. 2. Сложение точек эллиптической группы
    • 2. 3. 3. Корректировка результатов суммирования точек кривой с учетом их возможного равенства точке
    • 2. 3. 4. Сведение задачи логарифмирования на эллиптической кривой к задаче «ВЫПОЛНИМОСТЬ»
    • 2. 4. Проекция вещественного вектора приближений на пространство булевых переменных
    • 2. 5. КНФ представления для отношения неделимости на малые простые числа
  • ГЛАВА 3. Вычислительные эксперименты
    • 3. 1. Генерация КНФ для задач практически значимых размерностей
    • 3. 2. Решение полученных экземпляров задачи «ВЫПОЛНИМОСТЬ»
    • 3. 3. Определение наиболее вероятных значений битов сомножителей для задачи факторизации
    • 3. 4. Исследование стойкости рассматриваемых задач к восстановлению полного ключа по его известным фрагментам

КНФ представления для задач факторизации, дискретного логарифмирования и логарифмирования на эллиптической кривой (реферат, курсовая, диплом, контрольная)

Задача поиска выполнимого набора логической формулы — одна из наиболее важных задач математической логики и теории вычислений. Она имеет фундаментальное значение для решения прикладных задач в области искусственного интеллекта, проектирования компьютерных систем, роботостроения, криптографии и других. В настоящее время наблюдается бурное развитие в области сведения задач из различных областей прикладной математики к задаче «ВЫПОЛНИМОСТЬ». В России этому посвящены работы Семенова A.A., Буранова Е. В., и др. [51, 67], за рубежом известны работы Kautz Н. Selman В. [19, 41]. Одна из причин этого — возможность решать задачи, возникающие в самых различных областях, единым алгоритмом решения задачи «ВЫПОЛНИМОСТЬ».

Но, несмотря на столь высокое внимание к этой проблеме, имеется еще достаточно большое количество задач, для которых вопрос их сведения к задаче «ВЫПОЛНИМОСТЬ"до сих пор остается открытым. И это при том, что еще в 1971 году Кук С. в своей работе [2] показал принципиальную возможность такого сведения.

Цель работы.

Целью данной диссертационной работы является построение и исследование алгоритмов сведения задач 2-факторизации, дискретного логарифмирования и логарифмирования на эллиптической кривой к задаче «ВЫПОЛНИМОСТЬ».

Актуальность работы.

В современной информатике огромную роль играют надежные и гарантировано стойкие алгоритмы шифрования, обеспечивающие безопасность каналов связи в телекоммуникационных, финансовых и многих других информационных системах. Это обуславливает громадное практическое значение такой области науки, как криптографический анализ. Прогресс в области криптографического анализа в свою очередь сопровождается бурным развитием смежных областей математики: алгебры, теории чисел, дискретной математики.

Одним из ключевых направлений криптографического анализа является проверка криптографической стойкости алгоритмов асимметричного шифрования, поскольку на базе этих алгоритмов работает подавляющее большинство криптографических протоколов обмена ключами, цифровой подписи и другие. В настоящее время для проверки криптографической стойкости асимметричных шифров применяются в основном методы решета в поле чисел общего вида [21] и различные модификации ри Лметодов Полларда, базирующиеся на псевдослучайном блуждании по группе [20]. Последние достижения в этой области свидетельствуют о стойкости известных алгоритмов, поскольку для решения задач «рабочих» размерностей (т.е. регламентированных требованиями безопасности) требуется на несколько месяцев задействовать вычислительный кластер категории самых верхних позиций списка «Топ-500». Таким образом, увеличение длины ключа в полтора или два раза принципиально решает вопрос криптографической стойкости шифров.

Однако, относительно недавно возникло и получило развитие совершено новое, альтернативное алгебраическому подходу, направление криптоанализа — логический криптоанализ. Суть подхода заключается в рассмотрении криптографического алгоритма как программы для машины Тьюринга.

Подстановка открытого pi шифрованного текстов в эту программу естественным образом приводит к задаче «ВЫПОЛНИМОСТЬ» для конъюнктивной нормальной формы, часть выполняющего набора которой является ключом шифра. Идея такого подхода была впервые предложена Куком С. в 1997 году при поиске сложных задач для тестирования решателей КНФ [3].

В последующих работах по логическому криптоанализу (Massacci F., Marraro L., Srebrny M., Семенова A.A., Беспалова Д. В., Ушакова A.A. и др.) основное внимание исследователей было сосредоточено на криптоанализе блочных и потоковых шифров, генераторов двоичных последовательностей, а так же некоторых аспектах криптоанализа RSA (криптостойкость основана на сложности задачи факторизации). При этом за границами исследований остались такие важные задачи как дискретное логарифмирование и логарифмирование в группе точек эллиптической кривой, на основе которых строятся современные системы шифрования, протоколы обмена ключами и цифровой подписи (DSA, ECDSA и другие). В вопросе применения логического криптоанализа для задачи факторизации недостаточно полно освещены такие аспекты, как использование параллельных алгоритмов для поиска выполняющего набора КНФ, кодирующей исходную задачу, и адаптация алгоритмов кодирования под требования современных алгоритмов поиска выполняющего набора КНФ.

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

Сведение к задаче «ВЫПОЛНИМОСТЬ» позволяет не только применять для решения изначально алгебраических задач алгоритмы решения задачи.

ВЫПОЛНИМОСТЬ", но и получать качественно новые результаты, недоступные для алгебраических методов. Так, например, выделять наиболее вероятные биты ключа, распознавать определенные последовательности бит и полностью восстанавливать ключ по некоторым известным его фрагментам.

Содержание работы.

Диссертационная работа состоит из введения, трех глав, заключения и библиографии.

ЗАКЛЮЧЕНИЕ

.

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

1. Разработаны полиномиальные алгоритмы консервативного сведения задач факторизации, дискретного логарифмирования и логарифмирования па эллиптической кривой к задаче «ВЫПОЛНИМОСТЬ».

2. Для построенных алгоритмов приведены теоретические оценки трудоемкости и параметров полученных КНФ.

3. Проведены экспериментальные исследования практической сложности решения полученных КНФ с использованием современных алгоритмов решения задачи «ВЫПОЛНИМОСТЬ».

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

5. Для задачи факторизации разработаны алгоритмы сведения к задаче «3-ВЫПОЛНИМОСТЬ" — проектирования вещественного вектора приближений на пространство булевых переменныхгенерации КНФ, кодирующей условие неделимости на малые простые числа, и генерации КНФ, кодирующей упорядочение сомножителей.

6. На основе КНФ, полученных с помощью разработанных алгоритмов, исследована стойкость задач факторизации, дискретного логарифмирования и логарифмирования на эллиптической кривой к восстановлению полного ключа по его известным фрагментам.

Показать весь текст

Список литературы

  1. Brillhart J., Morrison M. A. Method of factoring and factorization of F7 // Mathematics of Computation. — 1975. — Vol. 29, no. 129. — Pp. 183−205.
  2. Cook S. A. The complexity of theorem proving procedures // Proceedings Third Annual ACM Symposium on Theory of Computing. — 1971.
  3. Cook S. A., Mitchel D. G. Finding hard instances for the satisfiability problem // A survey. DIMACS series in discrete mathematics and theoretical computer science. — 1997. — Vol. 5. — P. 151.
  4. Coppersmith P., Odlyzko A., Schroeppel R. Discrete logarithms in GF (p).
  5. Dantzig G. B. On the significance of solving linear programming problems with some integer variables // Econometrica. — no. 28. — Pp. 30−44.
  6. G. В., Blattner W. P., Rao M. R. All shortest routes from a fixed origin in a graph // Theory of Graphs: International Symposium. — Gordon and Breach, NY, 1967. Pp. 85−90.
  7. National Institute of Standards and Technology. — Data encryption standard. FIPS PUB 46 2, 1997.
  8. Dixon J. D. Asymptotically fast factorization of integers // Math. Comput. — 1981. Vol. 36. — Pp. 255−260.
  9. Edmonds J. Covers and packings in a family of sets // Bull. Amer. Math Soc.- 1962. no. 68. — Pp. 494−499.
  10. Faizullin R., Khnykin I., Dulkeit V. Polynomial approximation for sat as applied to crypto ciphers // Polynomial Computer Algebra (April 8−12, 2009). — St. Petersburg, Russia: 2009. — Pp. 100−104.
  11. Galbraith S. P., Smart N. P. A cryptographic application of Weil descent // Codes and cryptography. (Lect. Notes in Comput. Sci.). — 1999. — Vol. 1746. Pp. 191−200.
  12. Garey M. R., Johnson D. S. Computers and Intractability: A Guide to the Theory of NP-Completeness. — New York: W. H. Freeman, 1979.
  13. Gordon D- Discrete logarithms in GF (p) using the number field sieve // SIAM J. Disc. Math. 1993. — Vol. 6.
  14. Joux A., Lercier R. Discrete logarithms in GF (p). ht t p: //list serv. nodak. edu/archives / nmbrthry. html.
  15. Joux A., Lercier R. Improvements to the general number field sieve for discrete logarithms in prime fields, http://www.medicis.polytechnique.fr/ lercier.
  16. Jovanovic P., Janicic P. Logical analysis of hash functions // FroCoS 2005 -5th International Workshop on Frontiers of Combining Systems. — Vienna: 2005.
  17. Jurisic A., Menezes A. Elliptic curves and cryptography. // Dr. Dobb’s Journal. — April 1997. — Vol. 22, no. 4.
  18. Karp R. Reducibility among combinatorial problems // Complexity of Computer Computations / Ed. by R. Miller, J. Thatcher. — Plenum Press, 1972. Pp. 85−103.
  19. Kautz H., Selman B. Pushing the envelope: Planning, propositional logic, and stochastic search // Proc. AAAI-96. — 1996. — Pp. 1194−1201.
  20. Koblitz N., Menezes A., Vanstone S. The state of elliptic curve cryptography // Designs Codes and Cryptography. — 2000. — Vol. 19. — Pp. 173−193.
  21. Lenstra A. K., Lenstra H. W. The development of the number field sieve // Lect. Notes in Math. — 1993. —Vol. 1554.
  22. Lenstra H. W. Factoring integers with elliptic curves // Ann, of Math. — 1987. Vol. 2, no. 126.
  23. Massacci F., Marraro L. Towards the formal verification of ciphers: Logical cryptanalysis of des // Proc. Third LICS Workshop on Formal Methods and Security Protocols, Federated Logic Conferences. — 1999.
  24. The number field sieve / A. K. Lenstra, H. W. Lenstra, M. S. Manasse, J. M. Pollard // Proc. 22nd ACM Symposium on Theory of Computing.— 1990. Pp. 564−572.
  25. Odlyzko A. M. Discrete logarithms in finite fields and their cryptographic significance // Advances in Cryptology: Proceedings of EuroCrypt'84. (Lect. Notes in Comput. Sci.). — 1984. — Vol. 209. Pp. 224−316.
  26. Pohlig S., Hellman M. An improved algorithm for computing logarithms over GF (p) and its cryptographic significance // IEEE Trans. Inform. Theory. — 1978. Vol. 24. — Pp. 106−110.
  27. Pollard J. Monte-carlo method for factorization // BIT. — 1974. — Vol. 15.
  28. Pollard J. M. Monte carlo methods for index computation (mod p) // Math. Comp. 1978.-Vol. 32.
  29. Pomerance C. The quadratic sieve factoring algorithm // Advances in cryptology-EUROCRIPT'84 (LNCS'209). 1985. — Pp. 169−183.
  30. The-function and the complexity of Dixon’s factoring algorithm (psi.pdf). http://www.math.ku.dk/~kiming/lecturenotes/2002-cryptography/psi.pdf.
  31. RSA Security, http://www.rsasecurity.com.
  32. Sat competition, http://www.satcompetition.org/.
  33. Sat4j. http://www.sat4j.org/.
  34. SATLIB Benchmark Problems, www.cs.ubc.ca/ hoos/SATLIB/benchm.html.
  35. Satlive. http://www.satlive.org/.
  36. Sato, http://www.cs.uiowa.edu/hzhang/sato/.
  37. Schirokauer 0. Discrete logarithms and local units. // Phil. Trans. R. Soc. Lond. A. 1993. — Vol. 345. — Pp. 409−423.
  38. Schirokauer P., Weber P., Denny T. Discrete logarithms: the effectiveness of the index calculus method // Proceedings of ANTS-II.(Lect. Notes in Comput. Sei.). — 1996. Vol. 1122. — P. 337−362.
  39. Semaev I. A. Evaluation of discrete logarithms in a group of p—torsion points of an elliptic curve in a charactristic p // Mathematics of Computation. — 1998. Vol. 67. — Pp. 353−356.
  40. Srebrny M. Factorization with sat classical propositional calculus as a programming environment.— 2004. http://www.mimuw.edu.pl/ mati/fsat-20 040 420.pdf.
  41. Stallman R., Sussman G. J. Forward reasoning and dependency directed backtracking // Artificial Intelligence. — 1977. — no. 9(2). — Pp. 135−196.
  42. Susem M., Janicic P. Uniform reduction of cryptographic problems to sat.— Faculty of Mathimatics, University of Belgrade, Serbia.— 2009. http://argo.matf.bg.ac.yu/events/2009/slides/.
  43. Weber D. An implementation of the general number field sieve to compute discrete logarithms mod p // Advances in Cryptology EuroCrypt'95 (Lecture Notes in Computer Science). — 1995. — Vol. 921. — P. 95—105.
  44. Weber D. On the computation of discrete logarithms in finite prime fields: Ph.D. thesis / Univ. des Saarlandes, Saarbrucken. — 1997.
  45. Weber D. Computing discrete logarithms with quadratic number rings // Advances in Cryptology EUROCRYPT^S. Springer-Verlag (Lect. Notes in Comput. Sei.). — 1998. — Vol. 1403. — Pp. 171−183.
  46. Weber P., Denny T. The solution of mccurley’s discrete log challenge // Advances in Cryptology CRYPTO'98. Springer-Verlag (Lect. Notes in Comput. Sei.). — 1998. — Vol. 1462. — P. 458−471.
  47. Wegener I. The Complexity of Boolean Functions. — Wiley and Teubner, 1987.
  48. Zchaff. http://www.princeton.edu/ chaff/zchaff.html.
  49. Д. В., Семёнов А. А. О логических выражениях для задачи 2-ФАКТОРИЗАЦИЯ // Вычислительные технологии. — 2002. — Т. 7.
  50. Е. В. Программная трансляция процедур логического криптоанализа симметричных шифров // Вестник Томского Государственного Университета. — 2004. — № 9(1).
  51. ВАСИЛЕНКО О. Н. ТЕОРЕТИКО-ЧИСЛОВЫЕ АЛГОРИТМЫ В КРИПТОГРАФИИ. 2003.
  52. В., Файзуллин Р. Т., Хныкин И. Г. Минимизация функционалов, ассоциированных с задачами криптографического анализа асимметричных шифров // Таврический вестник информатики и математики. —2008. — № 1. — С. 178−188.
  53. В. И. КНФ представления для задач факторизации и дискретного логарифмирования // Проблемы теоретической и прикладной математики: Труды 38-й Региональной молодежной конференции / УрО РАН. Екатеринбург: 2007, — С. 350−355.
  54. В. И. КНФ представления для задачи логарифмирования на эллиптической кривой // ПРОБЛЕМЫ ТЕОРЕТИЧЕСКОЙ И ПРИКЛАДНОЙ МАТЕМАТИКИ: Труды 39-й Всероссийской молодежной конференции. — Екатеринбург: УрО РАН: 2008. — С. 360−364.
  55. В. И., Файзуллин Р. Т. Алгоритм построения эквивалентных КНФ для задачи факторизации // Труды III всероссийской конференции: Проблемы оптимизации и экономические приложения. — Омск: 2006.
  56. В. И., Файзуллин Р. Т., Хныкин И. Г. Сведение задач криптоанализа асимметричных шифров к решению ассоциированных задач ВЫПОЛНИМОСТЬ. М.: МАКС Пресс, 2007.- С. 249−251.
  57. В. И., Файзуллин Р. Т., Хныкин И. Г. Алгоритм минимизации функционала, ассоциированного с задачей 3-sat и его практические применения // Компьютерная оптика. — 2008. — Т. 32, № 1. — С. 68−73.
  58. В. И., Файзуллин Р. Т., Хныкин И. Г. Минимизация функционалов, ассоциированных с задачами криптографического анализа. — Новосибирск: Институт математики СО РАН: 2008.— С. 484−485.
  59. В. И., Файзуллин Р. Т., Хныкин И. Г. Минимизация функционалов, ассоциированных с задачами криптографического анализа // Доклады Томского государственного университета систем управления и радиоэлектроники. — 2008. — № 2(18). — С. 54−56.
  60. В. И., Файзуллин Р. Т., Хныкин И. Г. Минимизация функционалов, ассоциированных с задачами криптографического анализа асимметричных шифров // Прикладная дискретная математика. — 2008. — № 2.- С. 113−119.'г
  61. В. И., Файзуллин Р. Т., Хныкин И. Г. Непрерывные аппроксимации решения задачи «ВЫПОЛНИМОСТЬ» применительно к криптографическому анализу асимметричных шифров // Компьютерная оптика. 2009. — Т. 33, № 1. — С. 86−91.
  62. Ю. Л., Палютин Е. А. Математическая логика. — М.: Наука, 1987.
  63. В. И. Элементы криптографии. — М.: Высшая школа, 1999.
  64. В. В., Соловьев Ю. П. Эллиптические кривые и алгебраические уравнения. — М.: Факториал, 1997.
  65. Е. В., Файзуллин Р. Т. Применение метода последовательных приближений с инерцией к решению задачи Выполнимость // Вестник Томского Государственного Университета. — 2006. — Т. 17.
  66. А. Трансляция алгоритмов вычисления дискретных функций в выражения пропозициональной логики // Дискретный анализ и информатика. — 2008. — № 2. — С. 70−98.
  67. А. Логико-эвристический подход в криптоанализе генераторов двоичных последовательностей // Труды международной научной конференции ПАВТ'07. — Т. 1. — Челябинск: ЮУрГУ, 2007. С. 170−180.
  68. В. Криптография и защита сетей: принципы и практика. — 2-пс! изд. — М.: Вильяме, 2001.
  69. И. Модификации КНФ, эквивалентным задачам криптоанализа асимметричных шифров методом резолюции // Информационные технологии моделирования и управления. — 2007. — № 2. — С. 328−337.
  70. Г. О сложности вывода в исчислении высказываний // Зап. научн. семинаров ЛОМИ АН СССР. 1968. — Т. 8. — С. 234−259.
  71. А. Лекции по арифметическим алгоритмам в криптографии. М.: МЦНМО, 2002.
Заполнить форму текущей работой

На отлично!