6
Recursively Paired Arithmetic Technique (RPAT): An FPGA-Based Block Cipher Simulation and Its Cryptanalysis

Rajdeep Chakraborty1* and J.K. Mandal2†

1 Department of CSE, Netaji Subhash Engineering College, Kolkata, India

2 Department of CSE, FETM, University of Kalyani, Kalyani, India

Abstract

In this chapter a novel and yet simple cipher is proposed, which is fit for track Cryptography and Computer Science and Statistics Journal. Recursively Paired Arithmetic Technique (RPAT), which is an FPGA-based block cipher simulation and its cryptanalysis, is being done with Pearsonian Chi-Square test for non-homogeneity between plaintext with ciphertext and Avalanche ratio test. This cipher is a bit level cryptography where a source stream is considered into a block and RPAT is applied to get the target stream, this cipher has four different types of encryption/decryption processes. So, TB = RPAT (SB, OP), Target Block (TB) is the output of the function Recursively Paired Arithmetic Technique (RPAT) with input parameters, Source Block (SB) and encryption/decryption Options (OP). This cipher has been implemented in IEEE VHDL and simulated for FPGA in Xilinx ISE 8.1i. A good and comparable cryptanalysis result has been found against widely used RSA and TDES.

Keywords: Avalanche ratio test, pearsonian chi-square test, IEEE VHDL, FPGA, XilinX ISE 8.1i

6.1 Introduction

In this era of information and communication technology the digital security has become inevitable [1, 2, 6]. This proposed cipher provides the primary goal of confidentiality [1, 2], though it is a simple scheme but a good result found against widely used RSA and TDES [1, 2]. Cryptography [1, 2] is of two types, symmetric cipher and asymmetric cipher. Symmetric cipher are those types of cipher where key used is same for both encrypting and decrypting the plaintext and cipher-text, if there are two keys then one can be easily derived from the other. Symmetric cipher has the following advantages over asymmetric:

  • Symmetric ciphers are as good as asymmetric ciphers in terms of cryptographic strength.
  • Symmetric ciphers have much less encryption/decryption throughput time than that of asymmetric ciphers.
  • Symmetric ciphers can be easily embedded in small hardware devices, like mobile phones.

This proposed cipher has been designed for the implementation in FPGA-based simulation [3, 4] and for this it has been coded in IEEE VHDL [5, 6]. Philosophies behind FPGA-based design are:

  • Creating new products and lowering the cost of existing “successful” products with fewer people and resources in less time.
  • Creating power-less component yet optimal computing for “green” environment.
  • Less throughput time and fewer design area.

So, driven by the motivation to work in this new technology, RPAT, which is an FPGA-based symmetric cryptography [1, 2], has been proposed.

Section 6.2 describes RPAT and Session Key generation, Section 6.3 illustrates the implementation details, Section 6.4 does the cryptanalysis, Section 6.5 illustrates simulation based results, Section 6.6 points out some application issues, and Section 6.7 draws the conclusion.

6.2 Recursively Paired Arithmetic Technique (RPAT)

The plaintext to be transmitted is divided and mapped into blocks and RPAT is used to get cipher-text after encryption, same RPAT is used in ciphertext-text for decryption. Figure 6.1 shows the RPAT encryption and decryption, for encryption xor and modulo 2n/2 are the operations and for decryption xor and modulo 2n/2 subtraction are the operations. In the following paragraphs we will discuss the RPAT encryption process. The RPAT has two types of iterations, first is the xor iterations and then the modulo 2n/2 addition iterations.

Image described by caption and surrounding text.

Figure 6.1 Block diagram of recursively paired arithmetic technique (RPAT).

Consider a block, which is source [7, 8],

c06_Inline_3_10.jpg

Now, S00 is exored with S01 and the resultant will be S11, then S11 is exored with S02 and the resultant will be S12. Similarly this process will be performed for all the bits of n-bit block (0 to n − 1). This whole process is the first iteration. Here it will be noted that Sij is the representation, where “i” is the resultant bit-number after “ith” operation of the whole RPAT encryption/decryption processes, where “j” is the “jth” number of bit in the n-bit block of stream and it is from 0 to n − 1.

This same xor operation is performed “m” number of times, by observing the figure these xor operations are performed from 0 to m − 1.

After that the whole n-bits are broken down into two parts of n/2 bits each. These two blocks are now added with modulo 2n/2 add operation. The resultant is replacing the second block. This is the iteration number “m”.

These addition operations are now performed “l − m” number of times. Moreover, the total iteration of this proposed cipher, RPAT, is “l”. So, by observing the figure we can see that the encryption iterations are from 0 to l − 1. Therefore we can say that the total iterations of this cipher, RPAT, is “l” times and where first “m” times are of xor operations and the remaining times are of modulo 2n/2 addition. The following paragraphs will describe the decryption operation.

The decryption operation will follow these points:

  • The number of xor operations needed for decryption is (block length) − (number of iterations required to do encryption). If the block length is 64-bits and the number of iterations required to do encryption is 30, then, number of xor iterations required for decryption is 64 − 30 = 34.
  • Then, n-bits are divided into two parts and modulo 2n/2 subtractions are performed. Here, the number of iterations required in decryption is the same number of iterations that are performed during encryption. Suppose, during encryption the number of modulo 2n/2 additions are 25 then during decryption the number of modulo 2n/2 subtraction will also be 25.

Section 6.2.1 will illustrate an example, Section 6.2.2 will give the four types of options available in this proposed cipher, RPAT, and Section 6.2.3 discuss session key generation process.

6.2.1 An Example of RPAT

Figure 6.2 illustrates RPAT encryption process. In this example the Source Block, SB = 10011010, an 8-bit block is considered. Then three iterations of XOR is performed, we get the sub-stream as, S = 11011010. Then two iterations of modulo 16 addition is performed. So, we get the encrypted block, that is Target block, TB = 11010000.

For decryption following points are to be considered:

Image described by caption and surrounding text.

Figure 6.2 RPAT encryption process of SB = 10011010.

  • The number of xor operations needed for decryption is (block length) – (number of iterations required to do encryption). The block length is 8-bits and the number of iterations required to do encryption is 3, then, number of xor iterations required for decryption is 8 − 3 = 5.
  • Then, n-bits are divided into two parts and modulo 2n/2 subtractions are performed. Here, the number of iterations required in decryption is the same number of iterations that are performed during encryption. Suppose, during encryption the number of modulo 24 additions are two then during decryption the number of modulo 24 subtractions will also be two.

6.2.2 Options of RPAT

This technique has four options. These options are given pictorially in Figure 6.3. The options are discussed as follows:

  • Option 00: XOR are performed in forward direction and MOD Additions are performed in forward direction. This is already illustrated in Section 6.2.1.
Diagram illustrating the four options of RPAT encryption and decryption, with arrows for XOR forward direction, XOR backward direction, MOD addition forward direction, and MOD arithmetic backward direction.

Figure 6.3 Four options of RPAT encryption and decryption.

  • Option 01: XOR are performed in forward direction and MOD Additions are performed in backward direction.
  • Option 10: XOR are performed in backward direction and MOD Additions are performed in forward direction.
  • Option 11: XOR are performed in backward direction and MOD Additions are performed in backward direction.

6.2.3 Session Key Generation

An 130-bit secret/session [1, 2] key is proposed, the key generation is one of the important part of any cipher, symmetric and asymmetric key cipher. In symmetric cipher keys are used for encryption and decrypting, in fact the same.

Table 6.1 illustrates the generation of 130-bit key [1, 2]. Here the plaintext file is encrypted using some block sizes 13-times. Say, in the first iteration block size is 128-bit and encrypted using the first option, in the second iteration block size is 112-bit and encrypted using the third option and so on. In the table this block sizes are considered in 8-bit length and options are coded in 2-bit length.

Table 6.1 Generation of secret key.

Iteration number Formation of 130-bit secret key
Decimal Binary
Block size Option Block size Option
01 128 1st 10000000 00
02 120 3rd 01111000 10
03 112 2nd 01110000 01
04 100 2nd 01100100 01
05 64 1st 01000000 00
06 60 4th 00111100 11
07 32 2nd 00100000 01
08 30 3rd 00011110 10
09 16 4th 00010000 11
10 10 1st 00001010 00
11 8 3rd 00001000 10
12 4 2nd 00000100 01
13 2 1st 00000010 00

So, in each iteration we get 10-bit code. Assembling all these 13 iterations we will get 130-bit secret/session key. All these values, block sizes and chosen options, are absolutely random.

These values may change from session to session and therefore in each session we will get unique 130-bit secret key for each session. Here, from this table we get the 130-bit session key as:

K=10000000000111100010011100000101100100010100000000001111 0011001000000100011110100001000011000010100000001000100000010 0010000001000.

6.3 Implementation and Simulation

This proposed cipher has been implemented in IEEE VHDL using 64-bit block size. The block-size can be increased just by increasing the size of bit_vector type [5] variables, signals, and ports from 63 down to 0 to n − 1 down to 0 where “n” is the block size. The modular design approach is taken while coding this cipher. Figure 6.4 shows the top-level simulation of RPAT. The main features of the implementation are given below:

  • Triangular Encryption and Decryption using all options.
  • Coded using Behavioral model.
  • This program is implemented for text file input and output and also for RTL design and simulation for FPGA-chip.
  • All the four options are available for encryption/decryption, 00 → 1st option, 01 → 2nd option, 10 → 3rd option, and 11 → 4th option.
  • This top-level module has four ports, in_data, out_data, option_data, and EN_DN.
  • EN_DN = 0, means encryption is being done, EN_DN = 1, means decryption is being done.
  • The chip entity, in_data is the input bit stream; out_data is the output bit stream.
  • option_data selects encryption to be performed or decryption to be performed.

No alt text required.

Figure 6.4 Top level architecture of RPAT.

  • option_data also selects which of the four types of encryption/ decryption is to be performed.
  • EN_DN will tell the receiver side that encryption or decryption is being done.
  • There three types of TEXT files used in this implementation, “in.txt” for Source block (SB), “out.txt” for Target Block (TB) and “option.txt” for dual purpose of selecting option and encryption/decryption choice.
  • “option.txt” also contains the session key of the encryption and decryption.

The rest of the coding is done by defining the package which contains functions and procedures. The functions and procedures which are used to realize and simulate RPAT are noted below:

  • Function RPAC_enpdep: This is the main function which performs encryption/decryption using all options.
  • Function RPPT: This is the function which performs encryption and decryption using recursive xor operation and type of encryption and decryption from four alternatives.
  • Function mod32_bit_addition: Since this is a 64-bit block cipher implementation so, this is the function which performs modulo 32-bit addition.
  • Function mod32_bit_subtraction: This is a modulo 32-bit subtraction used in decryption.
  • Function binary_to_decimal: This function converts the binary bits to its equivalent decimal to perform required task as needed by RPPT.
  • Function power_of_two: This function calculates 2n, where “n” is the number of bits of a block.
  • Function twos complement: This function calculated twos complement as required by encryption and decryption simulation of RPAT.

Therefore, by using the modular design approach and behavioral approach this proposed cipher has been successfully realized and simulated in IEEE VHDL using XilinX ISE 8.1i. To perform the cryptanalysis, RPAT has also been coded in C-programming language through Cipher Block Chaining (CBC) mode [1, 2].

6.4 Cryptanalysis

Recursively Paired Arithmetic Technique (RPAT) is simple bit-level cryptography. So, all the cryptographic parameters may not be incorporated. In this section emphasis is given on Chi-Square test based cryptanalysis. It is a statistical measure that how far plaintext differs with ciphertext, in another word it is a test for heterogeneity or non-homogeneity.

Pearsonian Chi-Square generation test [7, 8], also known as the Chi-Square fitness test or Chi-Square independence.

(6.1)c06_Inline_10_20.jpg

where O is the Observed Frequency in groups of category

  1. E is the Expected Frequency in groups of category
  2. df is the “degree of freedom” (n − 1).
  3. χ2 is Chi-Square.

The steps in calculating the Chi-Square test value, summarized as below:

  • Tabulate the observed frequencies in column O.
  • Tabulate the expected frequencies in column E.
  • Use the above formula to calculate the Chi-Square value.
  • Find the degree of freedom as df. (N − 1).
  • Find the table entry value.
  • If your Chi-Square value is being found equal to or being found greater than the table calculated value then null hypothesis can be rejected: differences in these data are not appears to chance alone.

To perform Chi-Square test ten different files are selected, then these source files are encrypted with Conical Cipher, RSA and TDES, respectively. Then using Chi-Square test program these values are noted.

Text files (TXT), data file (XLS), image file (JPG), and video file (WMV) have been chosen for cryptanalysis as people used to send data/information using these files and our primary aim is to provide confidentiality.

Moreover, these source files are chosen in increasing file sizes, in categories of tiny (0–10 kilobytes), small (10–100 kilobytes), medium (100 kilo–bytes to 1 megabytes), large (1–16 megabytes), and huge (>16 megabytes) file types.

Table 6.2 gives the Chi-Square values of RPAT, RSA, and TDES. Figure 6.5 illustrates the same graphically in logarithm base 10 scale. Therefore, by observing table and graph we can say that Chi-Square values of this proposed cipher, RPAT, is greater than that of RSA, but, with respect to TDES, 50% of the source files encrypted with RPAT have greater Chi-Square values.

Table 6.2 Cryptanalysis of RPAT.

File name Size in KB Chi-Square values
RPAT RSA TDES
Version.txt 1 66 55 62
Ukraine.txt 5 99994 75194 118879
Content.txt 10 483321 454996 460630
Removdrv.txt 21 681325 662409 797476
PropList.txt 53 633312 633725 640814
Python_25_License.txt 101 6841343 6711218 7428782
Result_analysis_ IT_ODD_2011.xls 286 1066115 608316 984520
Metconv.txt 1156 2831418 2786042 2817232
Photo0139.jpg 1272 87889 83015 84719
Wildlife.wmv 25631 956816 951329 953431
Graphical data of Chi-Square value of RPAT in logarithmic scale, displaying 10 sets of three bars. Each set consists of bars for Chi-square values RPAT, Chi-square values RSA, and Chi-square values TDES.

Figure 6.5 Graphical data of Chi-Square value of RPAT in logarithmic scale.

Table 6.3 Simulation based results.

Calculated device utilization summary (estimated values)
Logic utilization Used Available Utilization
Number of slices 782 960 81%
Number of 4 input LUTs 1369 1920 71%
Number of bonded IOBs 131 66 198%

6.5 Simulation-Based Results

Table 6.3 illustrates the simulation based results. Number of slices used in this proposed cipher, RPAT, is 782 out of 960 which 81%. Number of 4-input Look-Up-Tables used is 1369 out of 1920 and it is 71%. Number of Input Output Blocks is 131 that means two IOBs are required for the implementation of this proposed cipher, RPAT. Therefore, it is proved in this section that this proposed cipher, RPAT, is successfully simulated for FPGA-based systems.

6.6 Applications

Some of the applications of RPAT are listed below:

  • Since, we get the requirement of simple cryptographic solution, so, it can be implemented for security in various embedded systems like mobiles.
  • This technique can also be implemented to develop protocol for confidentiality, integrity and availability.
  • This technique can also be implemented to develop electronic code books.
  • It can also be implemented to develop a private network system and using master-key-based application security.
  • This can also be implemented in hardware applications security such as switches, gateways and routers.

6.7 Conclusion

Therefore in this chapter we have successfully proposed and simulated a 64-bit block cipher. Its cryptanalysis with RSA and TDES using Chi-Square values yields good and comparable result. This cipher, RPAT, is more heterogeneous than that of RSA and TDES. Moreover, by simulation based results we got this cipher occupying almost all resources than that of available resources, thus we can say here that RPAT will have effective throughput time and design area. Keeping in view of these outcomes we can now use RPAT in various applications.

Acknowledgment

The authors express their deepest gratitude toward the Department of Computer Science and Engineering (CSE), Netaji Subhash Engineering College, Kolkata, India, and the Department of Computer Science and Engineering (CSE), University of Kalyani, Kalyani, India.

References

  1. 1. Stallings, W., Cryptography and Network Security: Principle and Practice, Second Edition, Sixth Indian Reprint, Pearson Education Asia, India, 2002.
  2. 2. Forouzan, B.A., Cryptography and Network Security, Special Indian Edition, Tata Mc-Graw-Hill, India, 2007.
  3. 3. Wolf, W., FPGA-Based System Design, First Impression, Pearson Education, India, 2009.
  4. 4. Navabi, Z., Embedded Core Design with FPGA(s), Edition, Tata Mc-Graw Hill, India, 2008.
  5. 5. Bhasker, J., A VHDL Primer, Thirteen Indian Reprint, Pearson Education, India, 2004.
  6. 6. Kaur, K., Digital System Design, Scitech Publications (India) Pvt. Ltd., India, Copyright © 2009.
  7. 7. Chakraborty, R. and Mandal, J.K., A Microprocessor-Based Block Cipher through Rotational Addition Technique (RAT), 9th International Conference on Information Technology (ICIT 2006), 18–21 December 2006, IEEE Computer Society, IEEE, Orissa Information Technology Society (OITS), Institute of Technical Education and Research (ITER), New Jersey Institute of Technology (NJIT), Satyam Computers Ltd. and IEEE New Jersey Section, and published by IEEE Computer Society Conference Publishing Services, Bhubaneswar, India, pp. 155–159, 2006.
  8. 8. Chakraborty, R. and Mandal, J.K., FPGA Based Cipher Design & Implementation of Recursive Oriented Block Arithmetic and Substitution Technique (ROBAST). (IJACSA) Int. J. Adv. Comput. Sci. Appl., 2, 4, 54–59, April 2011.

Notes

  1. * Corresponding author: [email protected]
  2. † Corresponding author: [email protected]
..................Content has been hidden....................

You can't read the all page of ebook, please click here login for view all page.
Reset
18.117.184.189