Сравнение эффективности CPU и GPU реализаций некоторых комбинаторных алгоритмов на задачах обращения криптографических функций

Сравнение эффективности CPU и GPU реализаций некоторых комбинаторных алгоритмов на задачах обращения криптографических функций

Автор: Булавинцев Вадим Германович

Журнал: Вестник Южно-Уральского государственного университета. Серия: Вычислительная математика и информатика @vestnik-susu-cmi

Рубрика: Вычислительная математика

Статья в выпуске: 3 т.4, 2015 года.

Бесплатный доступ

Проводится сравнение эффективности CPU и GPU реализаций некоторых комбинаторных алгоритмов, используемых в криптоанализе. В частности, анализируются причины, по которым не удается эффективно реализовать на GPU алгоритмы, осуществляющие «интеллектуальный перебор». Показывается, что применение специальных техник трансформации потока управления позволяет существенно компенсировать потери производительности, возникающие из-за неэффективного исполнения условных переходов на SIMD-устройстве. Однако ограничения, которые накладывают механизмы работы с памятью, применяемые в современных GPU, для рассматриваемых алгоритмов оказываются непреодолимыми. В качестве тестовых задач рассматриваются задачи обращения криптографических функций DES и A5/1.

Еще

Криптоанализ

Короткий адрес: https://sciup.org/147160572

IDR: 147160572   |   DOI: 10.14529/cmse150306

Список литературы Сравнение эффективности CPU и GPU реализаций некоторых комбинаторных алгоритмов на задачах обращения криптографических функций

  • TOP500 Supercomputer Site URL: http://www.top500.org (дата обращения: 01.01.2015)
  • Lee, V.W. Debunking the 100X GPU vs. CPU myth: an evaluation of throughput computing on CPU and GPU/V.W. Lee et al.//ACM SIGARCH Computer Architecture News. -ACM, 2010. -Vol. 38, No. 3. -P. 451-460. DOI: DOI: 10.1145/1816038.1816021
  • Flynn, M. Some computer organizations and their effectiveness/M. Flynn//Computers, IEEE Transactions on. -1972. -Vol. 100, No. 9. -P. 948-960. DOI: DOI: 10.1109/tc.1972.5009071
  • CUDA C Best Practices Guide -CUDA SDK v.6.0 -NVIDIA corp. -2014. URL: http://docs.nvidia.com/cuda (дата обращения: 15.07.2014).
  • Percival, C. The scrypt Password-Based Key Derivation Function. -IETF Draft -2012/C. Percival, S. Josefsson URL: http://tools.ietf.org/html/josefsson-scrypt-kdf-00.txt (дата обращения: 30.11.2012).
  • Nohl, K. Attacking phone privacy/K. Nohl//Black Hat USA. -2010. URL: https://srlabs.de/blog/wp-content/uploads/2010/07/Attacking.Phone_.Privacy_Karsten.Nohl_1.pdf (дата обращения: 01.01.2015).
  • Mironov, I. Applications of SAT solvers to cryptanalysis of hash functions/I. Mironov, L. Zhang//Theory and Applications of Satisfiability Testing-SAT 2006. -Springer, 2006. -P. 102-115. DOI: DOI: 10.1007/11814948_13
  • Semenov, A. Parallel logical cryptanalysis of the generator A5/1 in BNB-Grid system/A. Semenov et al.//Parallel Computing Technologies. -Springer, 2011. -P. 473-483. DOI: DOI: 10.1007/978-3-642-23178-0_43
  • Biryukov, A. Real Time Cryptanalysis of A5/1 on a PC/A. Biryukov, A. Shamir, D. Wagner//Fast Software Encryption. -Springer, 2001. -P. 1-18. DOI: 10.1007/3-540-44706-7_1.
  • Goliс, J.D. Cryptanalysis of alleged A5 stream cipher/J.D. Goliс//Advances in Cryptology-EUROCRYPT’97. -Springer, 1997. -P. 239-255. DOI: 0_17 DOI: 10.1007/3-540-69053-
  • Kumar, S. Breaking ciphers with COPACOBANA -a cost-optimized parallel code breaker/S. Kumar et al.//Cryptographic Hardware and Embedded Systems-CHES 2006. -Springer, 2006. -P. 101-118. DOI: DOI: 10.1007/11894063_9
  • Kwan, M. Reducing the Gate Count of Bitslice DES/M. Kwan//IACR Cryptology ePrint Archive. -2000. -Vol. 2000. -P. 51.
  • John the Ripper password cracker -2013 URL: http://www.openwall.com/john (дата обращения: 02.07.2014).
  • Davis, M. A machine program for theorem-proving/M. Davis, G. Logemann, D. Loveland//Communications of the ACM. -1962. -Vol. 5, No. 7. -P. 394-397. DOI: DOI: 10.1145/368273.368557
  • Moskewicz, M.W. Chaff: Engineering an efficient SAT solver/M.W. Moskewicz et al.//Proceedings of the 38th annual Design Automation Conference. -ACM, 2001. -P. 530-535. DOI: DOI: 10.1109/dac.2001.935565
  • Marques-Silva, J.P. GRASP: A search algorithm for propositional satisfiability/J.P Marques-Silva, K.A. Sakallah//Computers, IEEE Transactions on. -1999. -Vol. 48, No. 5. -P. 506-521. DOI: DOI: 10.1109/12.769433
  • Blumofe, R.D. Scheduling multithreaded computations by work stealing/R.D. Blumofe, C.E. Leiserson//Journal of the ACM (JACM). -1999. -Vol. 46, No. 5. -P. 720-748. DOI: DOI: 10.1145/324133.324234
  • Backus, J. Can programming be liberated from the von Neumann style?: a functional style and its algebra of programs/J. Backus//Communications of the ACM. -1978. -Vol. 21, No. 8. -P. 613-641. DOI: DOI: 10.1145/359576.359579
  • Molka, D. Memory performance and cache coherency effects on an Intel Nehalem multiprocessor system/D. Molka et al.//PACT'09. 18th International Conference on Parallel Architectures and Compilation Techniques. -IEEE, 2009. -P. 261-270. DOI: DOI: 10.1109/pact.2009.22
  • Een, N. MiniSat: A SAT solver with conflict-clause minimization/N. Een, N. Sörensson//Proceedings of the International Symposium on the Theory and Applications of Satisfiability Testing (2005). -2005. -Vol. 5. -P. 55.
Еще
Статья научная
QR-код для установки приложения SciUp Наведите камеру и скачайте бесплатное приложение SciUp