Построение и анализ эффективных комбинаторных алгоритмов решения систем булевых уравнений тема диссертации и автореферата по ВАК РФ 05.13.19, кандидат физико-математических наук Мелузов, Антон Сергеевич

• Мелузов, Антон Сергеевич
• кандидат физико-математических наук
• 2011

Оглавление диссертации кандидат физико-математических наук Мелузов, Антон Сергеевич

Введение

Глава 1. Обзор существующих подходов к решению систем уравнений над конечными полями.

1.1. О задаче решения систем булевых уравнений

1.2. Базисы Грёбнера.

1.3. Линеаризация, XL, XSL.

1.4. Использование SAT-решателей.

1.5. Алгоритмы согласования и склеивания.

Глава 2. Использование ассоциативных вычислителей для решения булевых систем уравнений

2.1. Параметры и характеристики модели ассоциативного вычислителя

2.2. Метод решения систем уравнений с использованием ассоциативных вычислителей на основе склеивания и согласования

2.3. Оценка трудоемкости алгоритма АОДР.

2.4. Использование ассоциативных вычислителей ограниченной емкости для решения булевых уравнений.

2.5. Экспериментальные исследования трудоемкости алгоритмов решения систем булевых уравнений.

Глава 3. Решение систем булевых полиномиальных уравнений с опробованием переменных и использованием промежуточных критериев истинности решений.

3.1. Опробование переменных в системе булевых полиномиальных уравнений и мономиальная совместность.

3.2. Метод ЧОМС решения систем булевых уравнений.

3.3. Теоретико-вероятностная модель для метода ЧОМС.

3.4. Ранг случайных систем линейных булевых уравнений и вероятность их совместности.

3.5. Оценка трудоемкости метода ЧОМС

Глава 4. Применение алгоритмов решения систем булевых уравнений для анализа потокового шифра ЫЫ-128.

4.1. Потоковый шифр ЫЫ-128.

4.2. Атака на основе открытого и шифрованного текстов.

4.3. Существующие методы криптоанализа ЫЫ-128.

4.4. Метод ЧОМС(Ь) для определения ключа шифра ЫЫ

4.5. Расчет трудоемкости метода ЧОМС(Ь).

Введение диссертации (часть автореферата) на тему «Построение и анализ эффективных комбинаторных алгоритмов решения систем булевых уравнений»

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

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

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

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

Цель диссертации состоит в разработке и исследовании эффективных алгоритмов решения систем булевых уравнений, а также в поиске классов систем булевых уравнений, допускающих сокращение трудоемкости их решения по сравнению с методом полного перебора. Это научное направление соответствует областям исследований, перечисленным в пи. 7, 9, 10 и 14 Паспорта специальности 05.13.19 — методы и системы защиты информации, информационная безопасность.

Для достижения поставленных целей были решены следующие новые задачи:

1. Разработка методов решения систем булевых уравнений с использованием ассоциативных принципов обработки информации.

2. Разработка методов решения систем булевых полиномиальных уравнений с использованием частичного опробования переменных и промежуточных критериев истинности решений.

3. Получение асимптотических оценок трудоемкости алгоритмов, реализующих разработанные методы, в общем случае и для систем специального вида.

4. Применение полученных результатов в криптографическом анализе потокового шифра ЫЫ-128.

5. Разработка программной библиотеки для эмуляции работы ассоциативных вычислителей и проведение экспериментальных исследований трудоемкости разработанного алгоритма решения систем булевых уравнений при различных параметрах систем.

В диссертации предложены новые подходы к решению систем булевых уравнений. Впервые для решения систем булевых уравнений предложено использовать специальные ассоциативные вычислители. Помимо адресной организации памяти вычислительных машин, возможна организация доступа к ячейкам памяти по их содержимому. Организованная таким образом память называется ассоциативной (Content-addressable memory, САМ), когда операции с ячейками памяти осуществляются в зависимости от записанной в них информации. Такой подход к организации памяти эффективен, например, в задачах поиска. Подобные устройства активно используются в современных информационных технологиях. Например, в сетевых коммутаторах, позволяя за одну операцию по IP-адресу определять физический порт, по которому следует передать пакет. Кроме того, ассоциативная память используются в диспетчерах кэша центрального процессора и ассоциативных буферах трансляции (TLB), базах данных, искусственных нейронных сетях, системах обнаружения вторжений и аппаратуре сжатия данных. Обзор современных подходов к технической реализации принципов ассоциативной памяти и некоторые примеры использования ассоциативных вычислителей приведены в работе [52].

Для поиска решений системы булевых уравнений с использованием пре-* имуществ ассоциативных вычислителей разработан алгоритм ассоциативного обхода дерева решений (АОДР). Предложена теоретико-вероятностная модель случайной системы булевых уравнений, характерная для систем, моделирующих работу блочных шифров. В рамках этой модели получена оценка математического ожидания трудоемкости решения систем булевых уравнений с использованием ассоциативных вычислителей, основанная на «связности» уравнений системы по переменным и зависящая от характера этой «связности». Найдены множества типов систем булевых уравнений на которых асимптотика математического ожидания трудоемкости решения систем булевых уравнений является субэкспоненциальной.

Разработан алгоритм частичного опробования и мономиальной совместности (ЧОМС) для решения систем булевых полиномиальных уравнений, основанный на опробовании части переменных системы и решении только тех систем булевых уравнений, полученных в результате опробования, которые удовлетворяют критерию мономиальной совместности. Предложена теоретико-вероятностная модель случайной системы булевых уравнений, характерная для систем, моделирующих работу потоковых шифров. В рамках данной модели для алгоритма ЧОМС получены оценки асимптотики математического ожидания трудоемкости решения систем булевых полиномиальных уравнений в общем виде и для квадратичных систем булевых уравнений.

Разработан метод восстановления ключа потокового шифра ЫЫ-128 по известной шифрующей последовательности, оценены его трудоемкость и другие параметры. Определенным преимуществом предложенного метода, по сравнению с известными ранее методами восстановления ключа потокового шифра ЫЫ-128, является возможность его применения в широком диапазоне длин известных шифрующих последовательностей.

Для проведения экспериментальных исследований поведения ассоциативных вычислителей при решении систем булевых уравнений с различны» I ми параметрами была разработана программная библиотека, эмулирующая работу ассоциативных вычислителей. По результатам проведенных экспериментов проведено статистическое исследование работы ассоциативных вычислителей при решении систем булевых уравнений с различными параметрами.

Диссертация состоит из введения, 4 глав, библиографии и 3 приложений. Объем диссертации 116 страниц, включая 14 рисунков. Объем приложений 48 страниц, включая 3 рисунка. Библиография включает 62 наименования.

Список литературы диссертационного исследования кандидат физико-математических наук Мелузов, Антон Сергеевич, 2011 год

1. Аржанцев И. В. Базисы Грёбиера и системы алгебраических уравнений. Москва: МЦНМО, 2003. С. 86.

2. Бабаш А. В., Шанкин Г. П. Криптография, Под ред. В. П. Шерстюка, Э. А. Применко. Москва: СОЛОН-ПРЕСС, 2007. С. 512.

3. Балакин Г. В. Системы случайных уравнений над конечным полем // Труды по дискретной математике. 1998. Т. 2. С. 21-37.

4. Горшков С. П. Применение теории УУР-полных задач для оценки сложности решения систем булевых уравнений // Обозрение прикладной и промышленной математики. 1995. Т. 2, № 3. С. 325-398.

5. Гэри М., Джонсон Д. Вычислительные машины и труднорешаемые задачи. Москва: Мир, 1982. С. 416.

6. Ильин В. А., Ким Г. Д. Линейная алгебра и аналитическая геометрия. Москва: Проспект, 2007. С. 400.

7. Кобзарь А. И. Прикладная математическая статистика: Справочник для инженеров и научных работников. Москва: Физматлит, 2006. С. 816.

8. Колчин В. Ф. Случайные графы. Москва: Физматлит, 2004. С. 256.

9. Леонтьев В. К., Тоноян Г. П. Приближенные методы решения систембулевых уравнений // Журнал вычислительной математики и математической физики. 1993. Т. 33, № 9. С. 1383-1390.

10. Лобанов М. С. Точное соотношение между нелинейностью и алгебраической иммунностью // Дискретная математика. 2006. Т. 18, № 3. С. 152-159.

11. Логачев О. А., Сальников А. А., Ященко В. В. Корреляционная иммунность и реальная секретность // Математика и безопасность информационных технологий. МЦНМО, 2004. С. 176-178.

12. Логачев О. А., Смышляев С. В. Логический криптоанализ потокового шифра ЫЫ-128 // Материалы 8-й Общероссийской конференции Ма-БИТ-09. МЦНМО, 2009.

13. Мелузов А. С. Оценка сложности применения символьных методов в криптоанализе алгоритма ГОСТ 28147-89 // Сборник работ молодых ученых факультета ВМК МГУ. 2007. № 4. С. 109-112.

14. Мелузов А. С. Использование ассоциативных принципов обработки информации для построения алгоритмов решения систем булевых уравнений // Журнал вычислительной математики и математической физики. 2010. Т. 50, № И. С. 2028-2044.

15. Мелузов А. С. Построение эффективных алгоритмов решения систем полиномиальных уравнений над полем СР(2) методом частичного опробования переменных // Научная конференция Тихоновские чтения. 2010. С. 12-13.

16. Мелузов А. С. О криптоанализе LILI-128, основанном на частичном опробовании и мономиальной совместности систем полиномиальных уравнений // Сборник работ молодых ученых факультета ВМК МГУ. 2011. № 8. С. 99-107.

17. Мелузов А. С. Построение эффективных алгоритмов решения систем полиномиальных булевых уравнений методом опробования части переменных // Дискретная математика. 2011. Т. 23, № 4. С. 66-79.

18. О'Ши Д., Кокс Д., Литтл Д. Идеалы, многообразия и алгоритмы. Москва: Мир, 2000. С. 687.

19. Сачков В. Н. Системы случайных уравнений над конечными полями // Труды по дискретной математике. 2004. Т. 8. С. 289-305.

20. Севастьянов Б. А. Курс теории вероятностей и математической статистики. Наука, 1982. С. 256.

21. Смирнов В. Г. Некоторые классы эффективно решаемых систем булевых уравнений // Труды по дискретной математике. 2000. Т. 3. С. 269-282.

22. Фостер К. Ассоциативные параллельные процессоры. Москва: Энергоиз-дат, 1981. С. 240.

23. Abdel А. К., Amr Y. М. Applications of SAT Solvers to AES key Recovery from Decayed Key Schedule Images // Cryptology ePrint Archive. 2010. Vol. 324. http://eprint.iacr.org/.

24. Armknecht F. On the existence of low-degree equations for algebraic attacks // Cryptology ePrint Archive. 2004. Vol. 185. URL: http : //eprint. iacr.org/2004/185 (дата обращения: 01.06.2011).

25. Babbage S. Cryptanalysis of LILI-128 // Proceedings of the 2nd NESSIE Workshop. 2001. P. 6.

26. Bard G. Algebraic Cryptanalysis. New York: Springer Science+Business Media, 2009. P. 356. ISBN: 978-0-387-88756-2.

27. Bardet M. T., Faugere J.-C., Salvy B. Complexity of Groebner bases computation for semi-regular overdetermined sequences over GF{2) // Institute National de Recherche en Informatique et en Automatique, Rapport de recherche. 2003. Vol. 5049.

28. Buchberger B. Grôbner-Bases: An Algorithmic Method in Polynomial Ideal Theory. Reidel Publishing Company, Dodrecht Boston - Lancaster, 1985. Pp. 184-232.

29. Burks A., H.H.Goldstine, J.Neumann. Preliminary Discussion of the Logical Design of an Electronic Computing Instrument // Papers of John von Neumann on Computing and Computer Theory. 1947. Pp. 97-142.

30. Chen J., Courtois N., Yang B. On Asymptotic Security Estimates in XL and Grôbner Bases-Related Algebraic Cryptanalysis // Lecture Notes in Computer Science. 2004. Vol. 3269. P. 401. URL: http ://dx. doi. org/10.1007/ Ы01042.t

31. Cid C., Leurent G. An Analysis of the XSL Algorithm // Advances in Cryp-tology ASIACRYPT 2005 / Ed. by B. Roy. Springer Berlin / Heidelberg, 2005. Vol. 3788 of Lecture Notes in Computer Science. Pp. 333-352. URL: http://dx.doi.org/10.1007/1159344718.

32. Courtois N., Klimov A., Patarin J., Shamir A. Efficient Algorithms for Solving Overdefined Systems of Multivariate Polynomial Equations // Advances in Cryptology, EUROCRYPT 2000 / Ed. by B. Preneel. Vol. 1807. Springer-Verlag, 2000. Pp. 392-407.

33. Courtois N., Meier W. Algebraic attacks on stream ciphers with linear feedback // Eurocrypt. Vol. 2656. Springer, 2003. Pp. 345-359.

34. Courtois N., Pieprzyk J. Cryptanalysis of block chiphers with overdefined systems of equations // Cryptology ePrint Archive. 2002. Vol. 044. URL: http://eprint.iacr.org/2002/044 (дата обращения: 01.06.2011).

35. Courtois N., Pieprzyk J. Cryptanalysis of block chiphers with overdefined systems of equations // Proc. 8th Int. Conf. on the Theory and Application ofCryptology and Information Security / Ed. by Y. Zheng. Vol. 2501. Springer,2002. Pp. 267-287.

36. Faugère J.-C. A new efficient algorithm for computation Groebner bases (F4) // Journal of pure and applied algebra. 1999. Vol. 139(1). Pp. 61-88.

37. Faugère J.-C. A new efficient algorithm for computation Groebner bases without reduction to zero (F5) // Proceedings of the 2002 international symposium on Symbolic and algebraic computation. 2002. Pp. 75-83.

38. Faugère J.-C., Ars G. An Algebraic Cryptanalysis of Nonlinear Filter Generators using Grôbner bases: Rapport de recherche RR-4739: INRIA, 2003. URL: http : //hal. inria. f r/inria-00071848/en/.

39. Fiorini C., Martinelli E., Massacci F. How to fake an RSA signature by encoding modular root finding as a SAT problem // Discrete Applied Mathematics.2003. Vol. 130, no. 2. Pp. 101 127.

40. Giusti M. Some effectivity problems in polynomial ideal theory // EUROSAMi 84 / Ed. by J. Fitch. Springer Berlin / Heidelberg, 1984. Vol. 174 of Lecture Notes in Computer Science. Pp. 159-171. URL: http://dx.doi.org/10. 1007/BFb0032839.3 *

41. Handbook of Satisfiability: Volume 185 Frontiers in Artificial Intelligence and Applications, Ed. by A. Biere, A. Biere, M. Heule ét al. Amsterdam, The Netherlands: IOS Press, 2009. P. 966. ISBN: 978-1-58603-929-5.

42. Jonsson F., Johansson T. A fast correlation attack on LILI-128 // Information Processing Letters. 2002. Vol. 81, no. 3. Pp. 127- 132. URL: http://www. sciencedirect.com/science/article/pii/S0020019001002083.

43. Massacci F., Marraro L. Logical Cryptanalysis as a SAT Problem // Journal of Automated Reasoning. 2000. Vol. 24. Pp. 165-203. 10.1023/A:1006326723002. URL: http: //dx.doi. org/10.1023/A: 1006326723002.

44. Meier W., Pasalic E., Carlet C. Algebraic attacks and decompozition of boolean functions // Eurocrypt. Vol. 3027. Springer, 1968. Pp. 474-491.

45. Mironov I., Zhang L. Applications of SAT Solvers to Cryptanalysis of Hash Functions. 2006. http://eprint.iacr.org/.

46. Pagiamtzis K., Sheikholeslami A. Content-addressable memory (CAM) circuits and architectures: A tutorial and survey // IEEE Journal of Solid-State Circuits. 2006.-March. Vol. 41, no. 3. Pp. 712-727.

47. Raddum H., Semaev I. New technique for Solving Sparse Equation Systems // Cryptology ePrint Archive. 2006. Vol. 475. URL: http: //eprint. iacr. org/ 2006/475 (дата обращения: 01.06.2011).

48. Robshaw M. New Stream Cipher Design. The eSTREAM Finalist, LNCS 4986, Ed. by O. Billet. Berlin Heidelberg: Springer-Verlag, 2008. P. 302.

49. Semaev I. On solving sparse algebraic equations over finite fields I // Proceedings of WCC'07. INRIA, 2007. Pp. 361-370.

50. Semaev I. On solving sparse algebraic equations over finite fields II // Cryp-tology ePrint Archive. 2007. Vol.280. URL: http://eprint.iacr.org/ 2007/280 (дата обращения: 01.06.2011).

51. Semaev I. Improved Agreeing-Gluing algorithm // Proceedings of SCC'10. Royal Holloway, University of London, 2010. Pp. 73-88.

52. Semaev I. Sparse Boolean equations and circuit lattices // Designs, Codes and Cryptography. 2011. Vol. 59. Pp. 349-364. 10.1007/sl0623-010-9465-x. URL: http : //dx. doi. org/10.1007/sl0623-010-9465-x.

53. Strassen V. Gaussian elimination is not optimal // Numerische Mathematik. 1969. Vol. 13. Pp. 354-356.