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

Аннотация

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