Vectorized Big Integer Operations for Cryptosystems on the Intel MIC Architecture

Cryptosystems play a vital role in cyber security. To accelerate their big integer operations without jeopardizing the security level has become one of the main objectives of the cryptography research. However, popular big integer libraries highly optimized for CPU and GPGPU perform poorly on the emerging Intel Xeon Phi coprocessor mainly because they cannot take advantage of the 512-bit Single Instruction Multiple Data (SIMD) vector parallelism on Intel Many Integrated Core (MIC) architecture. In this paper, we design and implement big integer algorithms of addition, multiplication, square and modular exponentiation for Intel MIC architecture. Our algorithms offer two key improvements over other big integer algorithms: 1) They explicitly and efficiently vectorize calculations via the 512-bit SIMD intrinsics, achieving a remarkable computing efficiency (vectorization), 2) They minimize memory footprints by restricting all operations within available registers and L1 cache once operands are loaded from the memory (memory-efficient). Furthermore, we apply our algorithms to implement a cryptography application, RSA private key decryption, to demonstrate their high performance. The benchmark results on Intel Phi confirm that our big integer algorithms consistently and unambiguously outperform the best available libraries (GNU MP, OpenSSL and MAPM) on Intel Phi in terms of both latency and throughput. Our exemplary RSA implementation achieves 4.3 to 5.9 times shorter latency and 5.4 to 9.1 times more throughput compared to that in OpenSSL.