ECE 646, HI-3 1 RC6 Implementation including key scheduling using FPGA (ECE 646 Project, December 2006) Fouad Ramia, Hunar Qadir, GMU Abstract—with today's great demand for secure communications systems, there is a growing demand for real-time implementation of cryptographic algorithms. In this paper we present a hardware implementation of the RC6 algorithm using VHDL Hardware Description Language. We also investigate the efficiency of RC6 from the hardware implementation perspective with Field Programmable Gate Arrays (FPGAs) as the target technology. FPGAs are highly attractive options for hardware implementations of encryption algorithms as they provide cryptographic algorithm agility, physical security, and potentially much higher performance than software solutions. Our analysis and synthesis studies of the ciphers will suggest that it would be desirable for FPGA implementations to have a simple cipher design that makes use of simple operations that not only possess good cryptographic properties, but also make the overall cipher design efficient from the hardware implementation perspective. —————————— —————————— 1 INTRODUCTIONRC6 is a symmetric key block cipher derived from RC5. It was designed by Ron Rivest, Matt Robshaw, Ray Sidney, and Yiqun Lisa Yin to meet the requirements of the Advanced Encryption Standard (AES) competition by the National Insti-tute of Standards and Technology (NIST). The algorithm was one of the five finalists, and was also submitted to the NESSIE and CRYPTREC projects. Though the algorithm was not eventually selected, RC6 remains a good choice for security applications. It is proprietary of RSA Security. RC6 is more exactly specified as RC6-w/r/b, where the pa-rameters w, r, and b respectively express the word size (in bits), the number of rounds, and the size of the encryption key (in bytes). Since the AES submission is targeted at w = 32 and r = 20, we implemented this version of RC6 algorithm, using a 32 bits word size, 20 rounds and 16 bytes (128 bits) encryp-tion key lengths. A key schedule generates 2r + 4 words (w bits each) from the b-bytes key provided by the user. These values (called round keys) are stored in an array S [0, 2r+3] and are used in both encryption and decryption. RC6 works on a block size of 128 bits and it is very similar to RC5 in structure, using data-dependent rotations, modular addition and XOR operations; in fact, RC6 could be viewed as interweaving two parallel RC5 encryption processes. However, RC6 does use an extra multiplication operation not present in RC5 in order to make the rotation dependent on every bit in a word, and not just the least significant few bits. The computation of f(X) = (X(2X + 1)) mod 2w is the most critical arithmetic operation of this block cipher. The goal of this paper is to implement the RC6 Cipher with FPGA as the target technology and then study the efficiency and performance of our design. Fig.1 - RC6 Cipher block diagram 2 MOTIVATION - WHY RC6? 2.1 Security To attack RC6 the best approach available to the cryptana-lyst is that of exhaustive search for the b-byte encryption key. The more advanced attacks of differential and linear cryptana-lysis, while being feasible on small-round versions of the ci-pher, do not extend well to attacking the full 20-round RC6 cipher. The RC6 key schedule is secure through mixing, one way function and no key separation. Therefore, RC6 provides a solid, well tuned margin for security. 2.2 Simplicity RC6 facilitates and encourages analysis by allowing rapid understanding of security and making direct analysis straight-forward. It also enables easy implementation by allowing compilers to produce high quality code for software imple-mentations, and by preventing complicated optimizations and providing good performance with minimal effort for hardware implementations. 2.3 Performance RC6 is known to have good performance on 8, 16 and 32-bit platforms. In this paper we will evaluate its performance in FPGAs. Cipher 128 128 128 Key Encryption/Decryption Circuit Plain2 ECE 646, HI-3 3 STRUCTURE OF THE RC6 CIPHER ALGORITHM 3.1 BASIC OPERATIONS RC6-w/r/b operates on units of four w-bit words using the following six basic operations. The base-two logarithm of w will be denoted by lg w. • a + b integer addition modulo 2w • a - b integer subtraction modulo 2w • a ⊕b bitwise exclusive-or of w-bit words • a X b integer multiplication modulo 2w • a<<<b rotate the w-bit word a to the left by the amount given by the least significant lg w bits of b • a>>>b rotate the w-bit word a to the right by the amount given by the least significant lg w bits of b 3.2 KEY SCHEDULE The user supplies a key of b bytes. From this key, 2r + 4 words (w bits each) are derived and stored in the array S [0, 2r + 3]. This array is used in both encryption and decryption. 3.3 ENCRYPTION Input: • Plain text stored in four w-bit input registers A, B, C, D • Number r of rounds • w-bit round keys S[0, … ,2r + 3] Output: • Cipher text stored in A, B, C, D Procedure: B = B + S [0] D = D + S [1] for i = 1 to r do { t = (B X (2B + 1)) <<< lg w u = (D X (2D + 1)) <<< lg w A = ((A ⊕ t) <<< u) + S [2i] C = ((C ⊕ u) <<< t) + S [2i+ 1] (A, B, C, D) = (B, C, D, A) } A = A + S [2r + 2] C = C + S [2r + 3] Fig. 2 - Encryption with RC6-w/r/b Here f(X) = (X (2X + 1)) mod 2w Figure taken from [1] 3.4 DECRYPTION Input: • Cipher text stored in four w-bit input registers A, B, C, D • Number r of rounds • w-bit round keys S[0; … ; 2r + 3] Output: • Plaintext stored in A, B, C, D Procedure: C = C – S [2r + 3] A = A – S [2r + 2] for i = r downto 1 do { (A, B, C, D) = (D, A, B, C) u = (D X (2D + 1)) <<< lg w t = (B X (2B + 1)) <<< lg w C = ((C – S [2i + 1]) >>> t) ⊕u A = ((A – S [2i]) >>> u) ⊕ t } D = D – S [1] B = B – S [0]ECE 646, HI-3 3 3.4 KEY SCHEDULE – REVISITED The user supplies a key of b bytes. Sufficient zero bytes are appended to give a key length equal to a non-zero integral number of words; these key bytes are then loaded in little-endian fashion into an array of c w-bit (w = 32 bits in our case) words L [0], … , L [c - 1]. Thus the first byte of key is stored as the low-order byte of L [0], etc., and L [c - 1] is
View Full Document
Unlocking...