The analysis of efficiency of application of four technologies of parallel programming for parallelization of algorithm of block encryption Advanced Encryption System is carried out in the work. The obtained results showed that the average execution time of this algorithm can be increased three times with a processor and thousands of times with a graphics processor. The advantages and disadvantages of each of the technologies are analyzed. But it is shown that each of them can be suitable for different scenarios. That is why it is important for a programmer to know OpenMP, Java Threads, Java ForkJoin, CUDA and other technologies that exist for parallelization. The software is developed and a number of numerical experiments are carried out. The reliability of the obtained encryption results is confirmed. To eliminate the influence of external factors on the reporting time, the algorithm was performed 10 times in a row and the average value was calculated. The largest increase in speed is obtained using CUDA to parallelize the Advanced Encryption System algorithm and is more than 300000, which is a very significant improvement. After that, we get an acceleration of three times for OpenMP and 2.8 on average for encryption and decryption using both Java technologies.
are developed that require more computing power. Until 2004, Moore's Law allowed the number of
transistors in a processor to automatically increase software performance [
architecture [
implementation of calculations on the central processing unit (CPU) to the calculations on the GPU
graphics processing unit (GPU). In particular, Nvidia proposed its solution by developing the CUDA
(Common Unified Device Architecture) parallel computing architecture. Nvidia offers examples of
practical application of CUDA to solve general-purpose problems [
is occupied by executable units, which gives an advantage in the speed of tasks related to parallel data processing, namely when the same sequence of operations is applied to a large amount of data and the number of instructions exceeds the number memory accesses. Thus, the GPU architecture allows to achieve greater efficiency in parallel computing.
on a GPU, the CPU remains less loaded and can be used to perform other tasks.
key 128/192/256 bits). As Selent found, Reindale's algorithm "uses a combination of exclusive OR (XOR) operations, replacing octets to rotate the rows of an S-box array" and a column and a mixture of columns. It was successful because it is easy to implement and can be run without much expense on a regular computer [10].
an input file, it receives a file divided into blocks of 128 bits (16 bytes) and a key of 128, 196 or 256 bits. This paper uses a 128-bit key [11]. For each block, there is another 128-bit block with encrypted data. Operations are performed on a 4x4 matrix that contains a corresponding block called a state.
Figure 1 shows a graphical representation of the algorithm, highlighting the main transformations that occur over the state. It is important to note that these transformations are applied several times in
● Key expansion: This is a common program used to expand the input key and get 16∗(Nr + 1) new bytes. Therefore, a different key is used in each round of the algorithm. The number of rounds depends on the length of the key, because a 16-byte key will be used, there will be 10 rounds, and the expanded key will be 176 bytes. Methods used to extend the key include cyclic permutations and arithmetic operations on Galois fields. See more on Figure 1 [11].
● Add Round Key: In this part of the process, the key is added to the state using an XOR operation. Part of the expanded key used depends on the integer number [11].
● Sub Bytes/Inverse Sub Bytes: This conversion uses a lookup table to perform byte substitution, ie the value of each byte is changed by another in the S-box matrix, or the inverse S-box for decryption. The matrix used was carefully selected for safety. Again, the values of the matrices are the result of modular arithmetic in Galois fields.
● Shift Rows/ Inverse Shift Rows: In this step, the last three status rows are shifted to the left for encryption or to the right for decryption. Line 1 is scrolled with an offset of 1, line 2 of 2, and line 3 of 3.
● Mix Columns/ Inverse Mix Columns: This process is really difficult to explain because it uses Galois field operations in each column of the state matrix. The arithmetic operations can be calculated in advance and saved in different search tables. Therefore, the process is reduced to performing multiplications and XOR operations with each status column and the corresponding search table [10].
To achieve the goal set in the work it is necessary: • • Explore the application of four different technologies: OpenMP, Java Threads, Java ForkJoin and CUDA, which implement different strategies to achieve the implementation of the AES encryption algorithm. • Develop software that works in parallel. • Analyze the advantages and disadvantages of each of these technologies, highlighting applications in which it is convenient to use each of the tools. Similarly, provide a performance analysis when performing the AES algorithm.
• Compare the speed and efficiency of parallel algorithms implemented on the CPU and GPU.
is divided. This is possible because the encryption process for each block is independent of the others.
AES parallelization using OpenMP
help of pre-processing directives that tell the compiler which sections of code will be executed in parallel. This makes it easy for the programmer to parallelize the code. It is important to note that shared and private data are key to OpenMP and should be defined in the directives, thus establishing communication and synchronization between threads.
The following is the main function of encryption in AES using OpenMP: void cipher_control(byte ∗file_in , byte ∗file_out , long long file_size , unsigned long blocks , byte ∗expanded_key) { unsigned long block ; int padding , res ; // Check if the size of the input file is multiple of 16 res = file_size % 16; #pragma omp parallel for shared(file_in , file_out , expanded_key) for ( block = 0; block < blocks ; block++) { // Check if it is necessary to add padding to the last block if(block == blocks − 1 && res != 0) { padding = 16 − res; for(int i = res;i < res + padding;i++) {
file_in[block ∗ 16 + i] = 0x00; } //Invoke the cipher process for the corresponding block cipher(file_in + block ∗ 16, expanded_key); //Copy the encrypted block to the output file memcpy(file_out + block ∗ 16, file_in + block ∗ 16, 16 ∗ sizeof(byte));
important part is the line where the encryption method is called, which performs the AES algorithm to encrypt the current block. There are no significant changes in the consistent implementation. Except for the line that specifies that the loop parallel will be used (#pragma omp parallel for shared(file_in, file_out, expanded_key)). Which can share in memory the input file, the output file and the encryption key. Here, in a simple way the algorithm is parallelized by means of OpenMP.
AES parallelization using CUDA
possible to control hundreds of threads and obtain large accelerations [
__global__ void cipher_control(byte *file_in , byte *file_out , long long * file_size , unsigned long *blocks , byte *expanded_key , byte *d_sbox , byte *d_m2, byte *d_m3) { byte state [16]; int block ; int padding, res; // Get the number of the block that the current thread is managing block = blockIdx . x * blockDim . x + threadIdx . x; // Check if the size of the input file is multiple of 16 res = *file_size % 16; // Verify the current block is not out of boundaries while(block < *blocks) { //Copy the corresponding input data to the state matrix memcpy(state, file_in + block ∗ 16, 16 ∗ sizeof(byte)); // Check if it is necessary to add padding to the last block if (block == ((*blocks) - 1) && res != 0) { padding = 16 - res; // Add padding only to the required spaces for (int i = res;i < res + padding;i++) { }
state[i] = 0x00; } // Invoke the cipher process for the corresponding block thread // Copy the encrypted block memcpy(file_out + block * 16, state , 16 * sizeof(byte)); // Update the current block moving to the next section of memory allowed for this block += gridDim . x * blockDim . x ;
that the method will be executed on the GPU, which means that the same segment of code will be copied and executed on multiple threads simultaneously. Instruction block block=blockIdx.x*blockDim.x+threadIdx.x; gets the block number that the current stream needs to encrypt. Because the program works with multiple blocks of threads, it is important to get the correct index to avoid racing.
Function cipher (state , expanded_key , d_sbox , d_m2, d_m3) calls the encryption method, this is where the AES algorithm is actually located and performs operations on the current state. Finally, the current block to be encrypted is updated by adding block += gridDim.x * blockDim.x. This operation ensures that the next block to be encrypted by the current stream is not encrypted by another.
during the encryption process. The number of bytes added is stored in the first byte of the source file.
cipher_control <<< 128, 128>>> (/*params*/);
This instruction suggests the GPU to use 128*128=16384 threads to perform the function. In this paper, the optimal number of threads should be equal to the size of the input file, but this size is variable.
AES parallelization using Java threads (Java Threads)
blocks to decrypt. For example, if you had 800 blocks and 8 threads, each thread must perform the task of decrypting 100 blocks. It is important to take care of the correct distribution of memory, because if one block is assigned more than one stream, race conditions may occur [15].
The following is a piece of code that is used to process the creation, initialization, and completion of each thread. Operator .start() indicates that the thread should start running in parallel. On the other hand, the operator .join() used to indicate that you need to wait for all threads to complete before continuing the program flow. //Instantiate the object to cipher ac = new AES_cipher( file_in , key) ; the runtime // Assign the work to the threads for(int thr = 0; thr < MAXTHREADS; thr++) { if ( thr < MAXTHREADS − 1 ) {
threads [ thr ] = new Thread(new AES_cipher( thr * thread_blocks , ( + 1) * thread_blocks ) ) ; } else {
threads [ thr ] = new Thread(new AES_cipher( thr * thread_blocks, aes_blocks )) ; } } } // Start the execution of the threads for(int thr = 0; thr < MAXTHREADS; thr++) {
threads[thr].start(); } // Wait for every thread to finish its work for(int thr = 0; thr < MAXTHREADS; thr++) { try { }
threads[thr].join(); } catch (InterruptedException e) {
e.printStackTrace () ; AES using Java ForkJoin
the administration and synchronization of threads, because they are created in the pool. This framework is called Java ForkJoin. This works by recursively dividing the initial working block into smaller ones, until the optimal size is assigned to any of the free threads. It works using a labor theft algorithm, which, if one of the threads finishes its work and is idle, it will take part of the work from another busy thread.
following is a snippet that separates tasks and causes new tasks to be created for threads. As you can see, if the task is small enough, it is processed by calling the decryption control method, which is similar to the one presented in the OpenMP section. Otherwise, the block is split in half and 2 new AES_decipher objects are created, each with half of the original work. New objects are assigned to the pool using the invokeAll method. Basically, all you have to do is create a pool and assign it an initial object that contains all the work.
public void compute() { if(this.end - this.start <= THRESHOLD) {
this.decipher_control(); } else { long mid = (this.start + this.end) / 2; invokeAll (new AES_decipher(this.start, mid), new AES_decipher(mid, this.end)); }
}
The same file was used to evaluate the effectiveness of the parallel algorithms used to encrypt (EC) the file and decrypt it (DC). In this way, the correctness of execution was checked, because the decrypted file corresponds to the same original file. Similarly, the execution time was measured to make appropriate comparisons. The algorithm was performed 10 times in a row, to subtract the average value, thereby eliminating the influence of external factors on the reporting time. The test file for encryption and decryption corresponds to a book in PDF format of 17.9 MB. The key used is read from the TXT file and was the same for all cases.
Table 1: Technical characteristics of the computer used in numerical experiments CPU GPU OS
algorithm and is more than 300,000, which is a very significant improvement. After that, we get an acceleration of three times for OpenMP and 2.8 on average for encryption and decryption using both Java technologies. In this sense, we can conclude that when using calculations in an 8-core processor, the acceleration obtained by AES optimization is close to 3. However, the use of GPUs for the AES algorithm leads to significantly higher performance. We can conclude that the best implementation of the parallel AES algorithm in the processor is obtained using OpenMP. However, Java execution time is less than C. This is due to how Java works and manages memory. Finally, in the case of a GPU, the best optimization is definitely when using CUDA. 6. Conclusions
for the final application. For example, in the case of AES, it can be used in different scenarios. In a high-level application that has contact with the user, a viable option would be Java Threads or ForkJoin.
convenient to use C and OpenMP. Finally, if you have dedicated hardware with a GPU, a definite option would be CUDA.
The main advantage of OpenMP is related to the simplicity with which the algorithm changes sequentially to become parallel, as it only requires specifying pre-processing directives. The disadvantage is that you do not have the versatility and flexibility to change the desired behavior in parallel. In the case of Java, the disadvantage is that it is necessary to administer the threads manually and solve synchronization problems. One of the advantages would be the ability to easily work with high-level applications. For example, processing images and files does not require a high level of complexity. Finally, CUDA has the advantage of very high acceleration due to the number of flows it provides, but the disadvantage is that it requires special equipment (GPU), which is expensive and requires more resources, such as more power and also heats up more. than a regular processor.
As a result of a series of numerical experiments, the efficiency of parallelization of the AES algorithm by various parallel programming technologies was proved. Obviously, sequential computing is no longer enough to meet the needs that users currently require. Concurrency needs to be integrated into software development to achieve the best results in terms of efficiency. In addition, the architecture of multi-core and multiprocessor systems is fully used in this way. Finally, it should be emphasized that before using technologies available for multiprocessor processing, it is necessary to conduct a thorough analysis of the algorithm to be implemented to avoid runtime problems such as race conditions or even try to parallelize an algorithm that is inherently impossible. Parallelism in software is a very powerful tool that needs to be used properly for optimal results and helps to create more efficient software.
[8] Fedushko, S., Mastykash, O., Syerov, Y., Peracek, T. Model of user data analysis complex for the management of diverse web projects during crises. Applied Sciences (Switzerland), 10(24), pp. 1– 12 (2020). [9] Pomogaeva, P.N. Cryptography: from the beginnings to the present day. Bulletin of young scientists of St. Petersburg State University of Technology and Design 4, 519-525 (2019). [10] Selent, Douglas. Advanced encryption standard. Rivier Academic Journal, 6(2), pp. 1-14 (2010). [11] Heron, S. Advanced Encryption Standard (AES). Network Security 2009, 12, pp. 8-12 (2009). [12] Mochurad, L., Boyko, N., Petryshyn, N., Potokij, M., Yatskiv, M. Parallelization of the Simplex
Lviv, Ukraine, April 23-24, 936-951 p. (2020). [13] Voss, M.J. OpenMP share memory parallel programming. Toronto, Kanada, 270 p. (2003). [14] Agarwal, N., Goyal, A., Maheshwari, G., Dugtal, A., Parallel Implementation of Scheduling
2, pp. 44–49 (2015). [15] Z. Hu, S. Gnatyuk, T. Okhrimenko, S. Tynymbayev, and M. Iavich, “High-Speed and Secure
10.5815/ijcnis.2020.03.01. [16] M. M. Hassan and G. M. Rather, “Centralized Relay Selection and Optical Filtering Based System
vol. 12, no. 1, pp. 27–42, Feb. 2020, doi: 10.5815/ijcnis.2020.01.04. [17] Java. The Java Tutorials. url: https://docs.oracle.com/javase/tutorial/ essential/concurrency /index.html (visitado 24-11-2018).