Vectorized Big Integer Operations for Cryptosystems on the Intel MIC Architecture

Cheng Chang, Shun Yao, Dantong Yu

Research output: Chapter in Book/Report/Conference proceedingConference contribution

7 Scopus citations

Abstract

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.

Original languageEnglish (US)
Title of host publicationProceedings - 22nd IEEE International Conference on High Performance Computing, HiPC 2015
PublisherInstitute of Electrical and Electronics Engineers Inc.
Pages194-203
Number of pages10
ISBN (Electronic)9781467384872
DOIs
StatePublished - Feb 2 2016
Externally publishedYes
Event22nd IEEE International Conference on High Performance Computing, HiPC 2015 - Bengaluru, India
Duration: Dec 16 2015Dec 19 2015

Publication series

NameProceedings - 22nd IEEE International Conference on High Performance Computing, HiPC 2015

Other

Other22nd IEEE International Conference on High Performance Computing, HiPC 2015
CountryIndia
CityBengaluru
Period12/16/1512/19/15

All Science Journal Classification (ASJC) codes

  • Theoretical Computer Science
  • Computational Theory and Mathematics

Keywords

  • Big Integer Operation
  • Many Integrated Core (MIC)
  • RSA Cryptography
  • SIMD
  • Vectorization

Fingerprint Dive into the research topics of 'Vectorized Big Integer Operations for Cryptosystems on the Intel MIC Architecture'. Together they form a unique fingerprint.

Cite this