This paper is a continuation of a series of papers devoted to problems of reversing of discrete functions belonging to class that has intersections with different areas of mathematical cybernetics. In particular the functions used in modern cryptosystems as ciphering transformations belong to the given class. In the paper some distinctive moments concerning the solving of considered functions reversing problems on multiprocessing computing systems are discussed
Download file
Counter downloads: 70
- Title ANALYSIS OF SOME CRYPTOGRAPHIC PRIMITIVES ON COMPUTER CLUSTERS
- Headline ANALYSIS OF SOME CRYPTOGRAPHIC PRIMITIVES ON COMPUTER CLUSTERS
- Publesher
Tomsk State University - Issue Prikladnaya Diskretnaya Matematika - Applied Discrete Mathematics 2(2)
- Date:
- DOI
Keywords
обращение дискретных функций , преобразования Цейтина , многопроцессорный кластер Authors
References
Гэри М., Джонсон Д. Вычислительные машины и труднорешаемые задачи. М.: Мир, 1982. 416 с.
Simon J. On Some Central Problems in Computational Complexity: Doctoral Thesis, Dept. of Computer Science, Cornel University, Ithaca, NY, 1975.
Семенов А.А. О сложности обращения дискретных функций из одного класса // Дискретный анализ и исследование операций. 2004. Т. 11. № 4. С. 44 - 55.
Семенов А.А., Буранов Е.В. Погружение задачи криптоанализа симметричных шифров в пропозициональную логику // Вычислительные технологии (совместный выпуск с журналом «Региональный вестник Востока»). 2003. Т. 8. С. 118-126.
Tseitin G. On the complexity of derivation in propositional calculus // In Studies in Constructive Mathematics and Mathematical Logic, part 2. 1968. P. 115 - 125. Reprinted in J. Siekmann and G. Wrightson (editors). Automation of reasoning. Berlin: Springer Verlag, 1983. V. 2. P. 466 - 483.
Haken A. The intractability of resolution // Theoretical Computer Science. 1985. V. 39. P. 297 - 308. [Перевод: Хакен А. Труднорешаемость резолюций //Кибернетический сборник. Новая серия. М.: Мир, 1991. Вып. 28. С. 179 - 194.]
Robinson J.A. A machine-oriented logic based on the resolution principle // J. ACM. 1965. V. 12. No. 1. P. 23 - 41. [Перевод: Робинсон Дж.А. Машинно-ориентированная логика, основанная на принципе резолюций // Кибернетический сборник. Новая серия. М.: Мир, 1970. Вып. 7. С. 194 - 218.]
Заикин О.С., Семенов А.А., Сидоров И.А., Феоктистов А.Г. Параллельная технология решения SAT-задач с применением пакета прикладных программ D-SAT // Вестник ТГУ. Приложение. 2007. № 23. С. 83-95.
Заикин О.С., Семенов А.А. Технология крупноблочного параллелизма в SAT-задачах // Проблемы управления. 2008. № 1.С. 43-50.
Цейтин Г.С. О сложности вывода в исчислении высказываний // Зап. научн. семинаров ЛОМИ АН СССР. 1968. Т. 8. С. 234-259.
Семенов А.А. Логико-эвристический подход в криптоанализе генераторов двоичных последовательностей // Труды Междунар. науч. конф. ПАВТ'07. Челябинск: ЮУрГУ, 2007. Т. 1. С. 170 - 180.
Cook S.A. The complexity of theorem-proving procedures // Proc. 3rd Ann. ACM Symp. on Theory of Computing, Association for Computing Machinery, Ohio, 1971. P. 151 - 159. [Перевод: Кук С.А. Сложность процедур вывода теорем //Кибернетический сборник. Новая серия. М.: Мир, 1975. Вып. 12. С. 5 - 15.]
Буранов Е.В. Программная трансляция процедур логического криптоанализа симметричных шифров // Вестник ТГУ. Приложение. 2004. № 9 (1). С. 60 - 65.
Буров П.С., Игнатьев А.С., Отпущенников И.В. Программная трансляция алгоритмов в логические выражения в задачах диагностирования дискретных систем // Материалы IX школы-семинара «Математическое моделирование и информационные технологии». Иркутск, 2007. С. 33 - 35.
Семенов А.А., Заикин О. С. Неполные алгоритмы в крупноблочном параллелизме комбинаторных задач // Труды Междунар. науч. конф. ПАВТ'08. СПб., 2008. С. 232 - 244.
Заикин О.С. Пакет прикладных программ Distributed-SAT. Свидетельство об официальной регистрации программы ЭВМ № 2008610423, опубл. 23.01.2008.
Феоктистов А.Г., Сидоров И.А. Языковые средства описания распределенных вычислений в инструментальном комплексе DISCOMP // Труды Междунар. науч. конф. ПАВТ'08. СПб., 2008. С. 488 - 493.
MiniSat [<http://minisat.se/MiniSat.html>]
Biryukov A., Shamir A., Wagner D. Real Time Cryptanalysis of A5/1 on a PC. Fast Software Encryption Workshop 2000. April 10 - 12, 2000. New-York City.
Суперкомпьютерный центр ИДСТУ СО РАН [http://www.mvs.icc.ru]
Научно-исследовательский вычислительный центр МГУ им. М.В. Ломоносова [http://parallel.ru/cluster/]
Список суперкомпьютеров топ-50 [http://supercomputers.ru/]
Межрегиональный вычислительный центр ТГУ [http://skif.tsu.ru]
ANALYSIS OF SOME CRYPTOGRAPHIC PRIMITIVES ON COMPUTER CLUSTERS | Prikladnaya Diskretnaya Matematika - Applied Discrete Mathematics. 2008. № 2(2).
Download full-text version
Download fileCounter downloads: 410