Parallel implementations of cryptographic algorithms on GPU

Abstract

그래픽 처리 장치(GPU)의 컴퓨팅 파워는 급속도로 증가하고 있으며, RSA, ECC, NTRU, 그리고 AES와 같은 암호 알고리즘의 GPU에서의 범용 컴퓨팅(GPGPU)에 대한 광범위한 연구가 진행되어 왔다. GPGPU의 등장으로 상용 컴퓨터는 복잡한 이기종 GPU+CPU 시스템이 되었다. 이 새로운 아키텍처는 새로운 도전과 고성능 컴퓨팅의 기회를 우리에게 안겨주고 있다.

이 논문에서 우리는 암호 알고리즘의 GPU를 이용한 병렬 구현에 대한 두 가지 연구 결과를 제시한다. 첫째, 우리는 이기종 GPU+CPU 시스템에서 가장 효율적인 시간-메모리 절충 암호분석 방법으로 알려진 Rainbow 방법의 고속 병렬 구현 방법을 제시한다. 또한 오경보(false alarm) 비용의 절감을 위한 checkpoint 기법을 분석하고, 이를 GPU와 CPU 사이의 부하조절(load balancing)을 위해 활용한다. 우리의 구현 방법이 GPU를 이용한 다른 구현인 RainbowCrack과 Cryptohaze에 비해 각각 1.36배와 2.18배 빠르다.

둘째, 우리는 NTRU 암호시스템의 효율적인 구현들과 그것들의 병렬화에 대한 연구 결과를 제시한다. 합성곱은 NTRU에서 가장 많은 시간이 소요되는 연산이며, 우리는 NTRU 다항식 계수의 반복되는 패턴이 나타나는 특징을 이용하여 합성곱 연산의 속도를 빠르게 할 수 있다. 우리는 이를 이용한 합성곱의 효율적인 알고리즘을 제시하고, 새 알고리즘의 성능을 마코프 체인을 이용하여 분석한다. 또한 우리는 이를 CPU와 GPU 상에서 구현한다. 분석과 실험 결과에 따르면, 우리가 제시한 새 알고리즘은 기존의 합성곱 연산에 비해 41%까지 빠른 성능을 보인다. 그리고 GPU를 이용한 구현은 CPU를 이용한 구현에 비해 23배 이상 나은 성능을 보인다.

The computing power of graphics processing units (GPU) has increased rapidly, and there has been extensive research on general-purpose computing on GPU (GPGPU) for cryptographic algorithms such as RSA, ECC, and AES. With the rise of GPGPU, commodity computers have become complex heterogeneous GPU+CPU systems. This new architecture poses new challenges and opportunities in high-performance computing.

In this thesis, we study parallel implementations of two cryptographic algorithms using GPU. First, we present high-speed parallel implementations of the rainbow method, which is known as the most efficient time-memory tradeoff, in the heterogeneous GPU+CPU system. We give a complete analysis of the effect of multiple checkpoints on reducing the cost of false alarms, and take advantage of it for load balancing between GPU and CPU. Our implementation is about 1.36 and 2.18 times faster than other GPU-accelerated implementations, RainbowCrack and Cryptohaze, respectively.

Second, we present efficient implementations for NTRU Cryptosystem and their parallel ones. Convolution product is a dominant operation of NTRU, and we can speed up the convolution product computation based on the fact that repeating patterns in coefficients of an NTRU polynomial can be used for construction of look-up tables. We provide efficient convolution algorithms to implement this idea, and we analyze the complexity of the new algorithms using Markov chains. Also, we implemented the new algorithms over a CPU and a GPU. According to our analyses and experimental results, the new algorithms speed up the convolution product by up to 41\%, and our GPU-accelerated implementations are more than 23 times faster than the implementations on CPU.