Optimizing the RSA Cryptographic Algorithm with Intel’s Integrated Performance Primitives (IPP)

Get Intel® Performance Libraries for free today!

Intel® Integrated Performance Primitives (Intel^® IPP) Intel IPP Cryptography is a software library add-on to Intel’s extensive IPP library. It is an API that provides a comprehensive set of highly optimized cryptographic functions to use in building robust, efficient, and secured cryptographic models and other domain application software that provides maximum performance and speed.

In this article, I will introduce you to Intel’s Cryptographic API by walking you through how to optimize the popular RSA cryptographic algorithm. We will briefly go through how to integrate the API with Microsoft Visual Studio, and get started with using functions in the library. After the setup, we will then proceed to use the functions provided in the API to implement and create an RSA cryptosystem. I will try to explain how the RSA algorithm works before proceeding to the implementation. But first, let's set up the library in our development environment. (We will use Microsoft Visual Studio as our development environment throughout this tutorial).

Getting Started with Intel IPP Cryptography

I will briefly show how to integrate your development environment with Intel IPP Cryptography. Intel IPP is available as part of Intel® Parallel Studio XE, Intel system Studio or as a stand-alone version. The cryptography functions are provided as the stand-alone packages that do not require installation of the main Intel® IPP packages. To obtain the Intel IPP Cryptography libraries, you can follow this article: Where do I download the Intel® IPP cryptography libraries? The Intel^® IPP Cryptography library is also available through open source. Visit the Intel® IPP cryptography open source page on GitHub to access the library source code. We will use the standalone Intel IPP crypto package in this article — I will assume that your development environment, Microsoft Visual Studio, is already downloaded and installed.

We will then download the stand-alone version of Intel IPP Cryptography.

After downloading, click on the downloaded executable to install Intel IPP Cryptography.

Once Visual Studio is ready and your Intel IPP installation is completed, proceed to create your c/c++ project. After creating your project, we will link IPP Cryptography to the project. In Visual Studio’s file explorer, right-click on your project and follow the navigation to the drop-down on this path:

Properties>vc++ directories

From there, do the following:

1. Type in the directory for the Intel IPP executable files (the default is <install_dir>\redist\<arch>\ippcp\ ), the Executable Directories.

My executable files are in the following location:

c:\Program
  Files(x86)\IntelSWTools\compilers_and_libraries_2019.1.144\windows\redist\ia32_win\ippcp

By default, <install_dir> is at C:\Program files(x86)\IntelSWTools\compilers_and_libraries_2019.x.xxx\<target_os>

2. Type in the directory for the Intel IPP library files (the default is <ipp directory>\lib), in Library Directories.

My IPP library files are in the following location:

c:\Program
  Files(x86)\IntelSWTools\compilers_and_libraries_2019.1.144\windows\ippcp\include

3. Type in the directory for the Intel IPP include files (the default is <ipp directory>\include), in include Directories.

My IPP include files are in the following location:

c:\Program
  Files(x86)\IntelSWTools\compilers_and_libraries_2019.1.144\windows\ippcp\lib

Once you are done configuring your project, to link Intel IPP Cryptography, add a C/C++ file to your project, and copy the following code here into the file and build. After successfully building your code, run it, and you should produce the following output:

At this stage, we are set to proceed with the implementation of our RSA algorithm.

But before that, let’s take a few minutes to understand how the RSA algorithm works.

The RSA Cryptographic Algorithm

RSA is an asymmetric cryptographic algorithm. This means that it uses separate keys for encryption and decryption. The encryption key is called a public key and the decryption key is called a private key. The recipient publishes their public key, and the sender can encrypt the message with this public key to produce a ciphertext. The ciphertext is sent over to the recipient and can be decrypted with the private key.

At its core, cryptography is pure mathematics. Basically, I only need two functions to build a cryptographic algorithm. One function will be the inverse of the other. This implies that if I were to compute a value with one function, I can get back the input value with the inverse function. Let’s explore the basic mathematical concept employed in the RSA algorithm.

RSA works by encrypting plaintext (m) into ciphertext (c) with a function. This ciphertext can then be decrypted with an inverse function to obtain the original plaintext message.

Encrypt function: m^e mod n = c

Decrypt function: c^d mod n = m

The (e, n) parameters constitute the public key, while (d, n) constitutes the private keys.

Once a plaintext has been encrypted, it's difficult to decipher the original message without knowing the modulus, n. The security of RSA models is based on the idea of prime factorization — that is, any existing number has a unique prime factorization, and prime factorization is considered difficult to do given that no systematic approach has been found. For instance, the prime factorization of 15 = 3 * 5, and this can be found only through a trial and error approach. When a number becomes very large, it becomes virtually impossible to find its prime factorization. Knowing the factors of the variable n is called the RSA problem, because if you do, you can decrypt a message encrypted with the public key.

How do we calculate e, n and d?

I. Choose two very large prime numbers (p and q).

II. Find n, where n=p*q. n becomes the modulus for both public and private encryption.

III. Compute phi, called the totient: phi(φ) = (p-1) (p-1).

IV. Choose e that satisfies the following conditions:

• 1 < e < phi(φ)
• e and phi(φ) are prime and do not share any divisor other than 1.

V. Compute d such that d*e mod phi = 1.

At this point, your cryptographic model is set with n = modulus, e = public exponent and d = private exponent.

VI. The encryption and decryption process can begin. It's important that n be a very large number (ideally 4,096 bits long), to be system robust. This is because as computers get faster, a small bit long n parameter provides a very limited permutation, which can be guessed.

The RSA Algorithm with Intel’s IPP Cryptography

Now that we understand the essentials of cryptography, let’s take a look at how Intel’s IPP can help to optimize the performance of an encryption algorithm. We’ll walk through the process step-by-step.

To get started, we’ll first create our RSA cryptosystem, which will enable us to generate the various parameters (e, n, d), needed to encrypt and decrypt our messages. Fortunately, Intel IPP has already taken care of important tasks that we would have implemented ourselves through the functions provided by the Cryptographic API. It provides an efficient implementation to handle Big Integers in our cryptosystem. (Read about Intel IPP Big Numbers and their arithmetic operations https://software.intel.com/en-us/ipp-crypto-reference.) We won’t really be using Big Number arithmetic since the available functions in the API will do the work for us; however, understanding Big Numbers will help you in this implementation process.

Setting our Cryptosystem

1.We will first specify the context size of our key components (e, n, d) as IppsBigNumState.

// specify the context of key components to contain generated key // data
IppsBigNumState* pModulus = newBN(1024 / 32, NULL);
IppsBigNumState* pPublicExp = newBN(1024 / 32, NULL);
IppsBigNumState* pPrivateExp = newBN(1024 / 32, NULL);

The context of our key components are created with the newBN() function. Once we initialize our cryptosystem, and call ippsRSA_GenerateKeys(), we can then retrieve our keys from these IppsBigNumState state variables.

2. We then specify the length in bits of the various parameters in our cryptosystem.

// (bit) size of key components
int bitsN = 1024; // Length of RSA system in bits(the modulus. size of                           // our modulus, must be large(4096 standard), but we will 1024

int bitsE = 512; // Length of the RSA public exponent in bits(the e //component
int bitsP = 512; //Length in bits of the p factors of the modulus(that //is, the p in the equation: n = p*q
int bitsQ = 512;//Length in bits of the q factors of the modulus(that //is, the q in the equation: n = p*q

int keyCtxSize; //Available size of memory buffer being initialized

3. We will define and set up our public key component with the steps below:

1. Calculate the size of our public key using ippsRSA_GetSizePublicKey().
2. Allocate sufficiently large memory space for public key context.
3. Initialize public key context.

// setup public key

// calculate size of public keys context
ippsRSA_GetSizePublicKey(bitsN, bitsE, &keyCtxSize);

//public key context allocated with generated buffer size
IppsRSAPublicKeyState* pPub = (IppsRSAPublicKeyState*)(new Ipp8u[keyCtxSize]); 
//context initialized in memory
ippsRSA_InitPublicKey(bitsN, bitsE, pPub, keyCtxSize);

4. We will also define and set up our private key component, with the same steps as we followed for the private key components.

1. Calculate the size of our public key ippsRSA_GetSizePrivateKeyType2().
2. Allocate sufficiently large memory space for private key context.
3. Initialize private key context.

// setup (type2) private key

//calculate size of private keys context
ippsRSA_GetSizePrivateKeyType2(bitsP, bitsQ, &keyCtxSize);
//private key context allocated with generated buffer size
IppsRSAPrivateKeyState* pPrv = (IppsRSAPrivateKeyState*)(new Ipp8u[keyCtxSize]);
//context initialized in memory
ippsRSA_InitPrivateKeyType2(bitsP, bitsQ, pPrv, keyCtxSize);

5. We will create scratch buffers to aid in RSA operations.

To do this, I will retrieve the generated private or public key buffer size, and use this to allocate the size for my scratch buffer.

int buffSizePrivate; // create variable to reference retrieved size
ippsRSA_GetBufferSizePrivateKey(&buffSizePrivate, pPrv); //retrieve //buffer size for private key

Ipp8u * scratchBuffer = NULL; //initialize scratch buffer as ipp8u //(usigned char equivalent)
scratchBuffer = new Ipp8u[buffSizePrivate]; //allocate memory for //scratch buffer

Check function input parameters to the ippsRSA_GetBufferSizePrivateKey() https://software.intel.com/en-us/ipp-crypto-reference

6. We will need two things here:

1. We need a random number generator to ensure that different sets of keys are generated each time in the cryptosystem.
2. A prime number generator to generate prime numbers for our p,q variables (in our n=p*q equation).

// random generator
IppsPRNGState* pRand = newPRNG();

// prime generator
IppsPrimeState* pPrimeG = newPrimeGen(512);

With this, our cryptosystem is set up and ready for use. But we need to validate our system to ensure that our generated keys are valid, and everything is working.

7. To validate keys, we’ll use the ippsRSA_ValidateKeys() function. We will use the created context above in our validation function.

Check function inputs to ippsRSA_ValidateKeys() here

int validateRes = IS_VALID_KEY; // IS_VALID_KEY is the success code
// validate keys
ippsRSA_ValidateKeys(&validateRes,
	pPub, pPrv, NULL, scratchBuffer,
	10, pPrimeG, ippsPRNGen, pRand);
// check that success code hasn’t changed, and print message on //successful
if (IS_VALID_KEY == validateRes) {
	cout << "validation successful \n" << endl;
}

8. After we have successfully set up our RSA cryptosystem, we will proceed to generate our keys. The ippsRSA_GenerateKeys() function generates the key components for our cryptosystem.

Read more about ippsRSA_GenerateKeys() here

// Pointer to IppsBigNumState context for searching an RSA public //exponent
Ipp32u E = { 0x11 }; 
IppsBigNumState* pSrcPublicExp = newBN(1, &E);

IppStatus status; // reference to generated message code

// keys generator
status = ippsRSA_GenerateKeys(pSrcPublicExp, pModulus, pPublicExp, pPrivateExp, pPrv, scratchBuffer, 10, pPrimeG, ippsPRNGen, pRand);

// check for successful generation of keys
// ippStsNoErr signals success
if (status == ippStsNoErr) {
	cout << "keys generation successful \n" << endl;
}

9. Let’s display our generated key components (n, e, d) onscreen.

Once we have called the ippsRSA_GenerateKeys() function, our generated keys will be stored in the IppsBigNumState variables we created at the beginning. Therefore, we will create instances of BigNumber objects with these variables, and use the tBN() BigNumber method to display the data in each object.

// get modulus generated
BigNumber modN(pModulus); // create BigNumber instance of modulus 
modN.tBN("Modulus (n): "); // display key data

cout << "\n" << endl; // print empty line

// get public key generated 
BigNumber Pk(pPublicExp); // create BigNumber instance of public key
Pk.tBN("Public Key Exponent (e): "); // display key data

cout << "\n" << endl; // print empty line

//get private key generated
BigNumber Pvk(pPrivateExp); //create BigNumber instance of private key
Pvk.tBN("Private Key Exponent (d): "); // display key data

At this stage, the cryptosystem is set up, and keys can be generated. Let’s see how the encryption and decryption process is done.

10. In order to start the encryption and decryption process, we first set our public key and private key in our already existing RSA context with the above-generated keys.

// set public key with generated public key
ippsRSA_SetPublicKey(pModulus, pPublicExp, pPub);

// set up type1 private key component with generated private key
ippsRSA_SetPrivateKeyType1(pModulus, pPrivateExp, pPrv);

Check function input parameters to ippsRSA_SetPublicKey() and ippsRSA_SetPrivateKeyType1() here

11. Assuming that we have a message that we want to encrypt, we will first convert it to a value using some defined scheme. Let’s assume the converted format is Ipp32u format dataM below, and let's encrypt it.

Ipp32u dataM[] = { // plain text to be encrypted
		0x12345678,0xabcde123,0x87654321,
		0x111aaaa2,0xbbbbbbbb,0xcccccccc,
		0x12237777,0x82234587,0x1ef392c9,
		0x43581159,0xb5024121,0xa48D2869,
		0x2abababa,0x1a2b3c22,0xa47728B4,
		0x54321123,0xaaaaaaaa,0xbbbbbbbb,
		0xcccccccc,0xdddddddd,0x34667666,
		0xa46a3aaa,0xe4251e84,0xf31f2Eff,
		0xfec55267,0x11111111,0x98765432,
		0x54376511,0x21323111,0x85433abc,0xcaa44322,0x001234ef };

// we will create ciphertext context with size of dataN
Ipp32u dataN[] = { // data for ciphertext context creation
		0x03cccb37,0x6acadded,0xdf4f20d0,0x2458257d,
		0xda3b7886,0x5c1b1a4c,0xea6f676b,0x59f51e09,
		0xc0691195,0x8076c61f,0x4221d059,0xd021673a,
		0x139bd5ef,0x95189046,0x10eb90ea,0x127af4e5,
		0x14f5dcb8,0x1e13510f,0x6e2e0558,0xa650fce0,
		0xff0bcd51,0xe218e43d,0xad045536,0xdc4a21d7,
		0x74edee68,0xb474ad57,0x79514004,0xa65a27a3,
		0x9e5259c1,0xe78e89eb,0xb34ed292,0x99197f0d };


// create contexts for  message and ciphertext, this allocate the //appropriate memory size for storing message and ciphertext

// create message context
IppsBigNumState* Msg = newBN(sizeof(dataM) / sizeof(dataM[0]), dataM); 
//create ciphertext context
IppsBigNumState* C = newBN(sizeof(dataN) / sizeof(dataN[0])); 


// encrypt  message, and return status code for verification
IppStatus status1;
status1 = ippsRSA_Encrypt(Msg, C, pPub, scratchBuffer);

// check for successful encryption of msg
if (status1 == ippStsNoErr) {
	cout << "message encryption successful \n" << endl;
}

12. We will then create our de-ciphertext context and proceed to decrypt the encrypted message (ciphertext).

// create de-ciphertext context
IppsBigNumState* Z = newBN(sizeof(dataN) / sizeof(dataN[0]));

// de-crypt  message, and return status code for verification
IppStatus status2;
status2 = ippsRSA_Decrypt(C, Z, pPrv, scratchBuffer);

// check for successful decryption of ciphertext
if (status2 == ippStsNoErr) {
	cout << "message decryption successful \n" << endl;
}

13. Now that we are sure that our encryption and decryption process was successful, our final step is to verify that our decrypted ciphertext was indeed the same as our plaintext message.

We’ll do this by comparing the plaintext message to the decrypted message with IPP’s ippsCmp_BN() function.

// compare plaintext and decrypted message
Ipp32u Result; // reference to generated status code
ippsCmp_BN(Msg, Z, &Result); // plain text and decrypted cipher text

cout << Result << endl; // comparison 0 --> OK

// remove sensitive data and free resources used
ippsRSA_InitPrivateKeyType2(bitsP, bitsQ, pPrv, keyCtxSize);

// delete generators
deletePrimeGen(pPrimeG);
deletePRNG(pRand);

// release resource
delete[] scratchBuffer;
delete[](Ipp8u*) pPub;
delete[](Ipp8u*) pPrv;

return 0; // finish program

You can access the full code (including Intel’s source code used in this implementation) on GitHub.

Conclusion

Striking the right balance between performance and security is difficult in any IT-related situation, but it’s especially tricky when it comes to encryption algorithms. Fortunately, with the help of tools like Intel’s IPP, it’s easy to maximize cryptography performance without compromising the robustness of your algorithm, or spending a fortune on infrastructure to execute it.

Good Resources for Understanding Intel IPP Cryptography and the RSA Algorithm

• Intel® IPP Cryptography Developer Guides: HTML
  Intel® IPP Cryptography Developer References: HTML

  https://www.researchgate.net/publication/280923792_Intel_Integrated_Performance_Primitives_Cryptography_Guide_IPP_71

• https://www.garykessler.net/library/crypto.html#intro
• https://www.edureka.co/blog/what-is-cryptography/#Encrypt