Cryptographic Algorithms on Reconfigurable Hardware

by Rodriguez-henriquez, Francisco; Saqib, N. A.; Diaz-Perez, A.; Koc, Cetin K.

• ISBN13: 9780387338835
• ISBN10: 0387338837
• Format: Hardcover
• Copyright: 2006-11-01
• Publisher: Springer-Verlag New York Inc

Summary

Cryptographic solutions using software methods can be used for those security applications where data traffic is not too large and low encryption rate is tolerable. On the other hand, hardware methods offer high-speed solutions making them highly suitable for applications where data traffic is fast and large data is required to be encrypted in real time. VLSI (also known as ASIC), and FPGAs (Field Programmable Gate Arrays) are two alternatives for implementing cryptographic algorithms in hardware. FPGAs offer several benefits for cryptographic algorithm implementations over VLSI as they offer high flexibility. Due to its reconfigurable property, keys can be changed rapidly. Moreover, basic primitives in most cryptographic algorithms can efficiently be implemented in FPGAs.Since the invention of the Data Encryption Standard (DES), some 40 years ago, a considerable amount of cryptographic algorithm implementation literature has been produced both, for software and hardware platforms. Unfortunately, virtually there exists no book explaining how the main cryptographic algorithms can be implemented on reconfigurable hardware devices.This book will cover the study of computational methods, computer arithmetic algorithms, and design improvement techniques needed to implement efficient cryptographic algorithms in FPGA reconfigurable hardware platforms. The concepts and techniques to be reviewed in this book will make special emphasis on the practical aspects of reconfigurable hardware design, explaining the basic mathematics related and giving a comprehensive description of state-of-the-art implementation techniques. Thus, the main goal of this monograph is to show how high-speed cryptographic algorithms implementations can be achieved on reconfigurable hardware devices without posing prohibited high requirements for hardware resources.

Table of Contents

List of Figures	xiii
List of Tables	xix
List of Algorithms	xx
Acronyms	xxiii
Preface	xxv
Introduction	1	(6)
Main goals	1	(2)
Monograph Organization	3	(1)
Acknowledgments	4	(3)
A Brief Introduction to Modern Cryptography	7	(28)
Introduction	8	(1)
Secret Key Cryptography	9	(2)
Hash Functions	11	(1)
Public Key Cryptography	12	(3)
Digital Signature Schemes	15	(9)
RSA Digital Signature	16	(1)
RSA Standards	17	(1)
DSA Digital Signature	18	(1)
Digital Signature with Elliptic Curves	19	(4)
Key Exchange	23	(1)
A Comparison of Public Key Cryptosystem	24	(2)
Cryptographic Security Strength	26	(1)
Potential Cryptographic Applications	27	(2)
Fundamental Operations for Cryptographic Algorithms	29	(2)
Design Alternatives for Implementing Cryptographic Algorithms	31	(1)
Conclusions	32	(3)
Reconfigurable Hardware Technology	35	(28)
Antecedents	36	(2)
Field Programmable Gate Arrays	38	(10)
Case of Study I: Xilinx FPGAs	39	(5)
Case of Study II: Altera FPGAs	44	(4)
FPGA Platforms versus ASIC and General-Purpose Processor Platforms	48	(2)
FPGAs versus ASICs	48	(1)
FPGAs versus General-Purpose Processors	49	(1)
Reconfigurable Computing Paradigm	50	(3)
FPGA Programming	52	(1)
VHSIC Hardware Description Language (VHDL)	52	(1)
Other Programming Models for FPGAs	53	(1)
Implementation Aspects for Reconfigurable Hardware Designs	53	(6)
Design Flow	53	(2)
Design Techniques	55	(3)
Strategies for Exploiting FPGA Parallelism	58	(1)
FPGA Architecture Statistics	59	(2)
Security in Reconfigurable Hardware Devices	61	(1)
Conclusions	62	(1)
Mathematical Background	63	(26)
Basic Concepts of the Elementary Theory of Numbers	63	(7)
Basic Notions	64	(3)
Modular Arithmetic	67	(3)
Finite Fields	70	(3)
Rings	70	(1)
Fields	70	(1)
Finite Fields	70	(1)
Binary Finite Fields	71	(2)
Elliptic curves	73	(4)
Definition	73	(1)
Elliptic Curve Operations	74	(2)
Elliptic Curve Scalar Multiplication	76	(1)
Elliptic Curves over GF(2m)	77	(5)
Point Addition	78	(1)
Point Doubling	78	(1)
Order of an Elliptic Curve	79	(1)
Elliptic Curve Groups and the Discrete Logarithm Problem	79	(1)
An Example	79	(3)
Point Representation	82	(3)
Projective Coordinates	83	(1)
Lopez-Dahab Coordinates	84	(1)
Scalar Representation	85	(3)
Binary Representation	85	(1)
Recoding Methods	85	(2)
ω-NAF Representation	87	(1)
Conclusions	88	(1)
Prime Finite Field Arithmetic	89	(50)
Addition Operation	90	(8)
Full-Adder and Half-Adder Cells	90	(1)
Carry Propagate Adder	91	(1)
Carry Completion Sensing Adder	92	(2)
Carry Look-Ahead Adder	94	(2)
Carry Save Adder	96	(1)
Carry Delayed Adder	97	(1)
Modular Addition Operation	98	(2)
Omura's Method	99	(1)
Modular Multiplication Operation	100	(24)
Standard Multiplication Algorithm	101	(3)
Squaring is Easier	104	(1)
Modular Reduction	105	(3)
Interleaving Multiplication and Reduction	108	(2)
Utilization of Carry Save Adders	110	(4)
Brickell's Method	114	(2)
Montgomery's Method	116	(7)
High-Radix Interleaving Method	123	(1)
High-Radix Montgomery's Method	124	(1)
Modular Exponentiation Operation	124	(14)
Binary Strategies	125	(1)
Window Strategies	126	(3)
Adaptive Window Strategy	129	(3)
RSA Exponentiation and the Chinese Remainder Theorem	132	(4)
Recent Prime Finite Field Arithmetic Designs on FPGAs	136	(2)
Conclusions	138	(1)
Binary Finite Field Arithmetic	139	(50)
Field Multiplication	139	(27)
Classical Multipliers and their Analysis	141	(1)
Binary Karatsuba-Ofman Multipliers	142	(9)
Squaring	151	(1)
Reduction	152	(4)
Modular Reduction with General Polynomials	156	(3)
Interleaving Multiplication	159	(2)
Matrix-Vector Multipliers	161	(3)
Montgomery Multiplier	164	(1)
A Comparison of Field Multiplier Designs	165	(1)
Field Squaring and Field Square Root for Irreducible Trinomials	166	(7)
Field Squaring Computation	167	(1)
Field Square Root Computation	168	(3)
Illustrative Examples	171	(2)
Multiplicative Inverse	173	(10)
Inversion Based on the Extended Euclidean Algorithm	175	(1)
The IToh-Tsujii Algorithm	176	(2)
Addition Chains	178	(1)
ITMIA Algorithm	178	(1)
Square Root ITMIA	179	(2)
Extended Euclidean Algorithm versus Itoh-Tsujii Algorithm	181	(2)
Multiplicative Inverse FPGA Designs	183	(1)
Other Arithmetic Operations	183	(3)
Trace function	183	(1)
Solving a Quadratic Equation over GF(2m)	184	(1)
Exponentiation over Binary Finite Fields	185	(1)
Conclusions	186	(3)
Reconfigurable Hardware Implementation of Hash Functions	189	(32)
Introduction	189	(2)
Some Famous Hash Functions	191	(2)
MD5	193	(8)
Message Preprocessing	194	(2)
MD Buffer Initialization	196	(1)
Main Loop	197	(1)
Final Transformation	198	(3)
SHA-1, SHA-256, SHA-384 and SHA-512	201	(9)
Message Preprocessing	202	(2)
Functions	204	(1)
SHA-1	205	(1)
Constants	206	(1)
Hash Computation	207	(3)
Hardware Architectures	210	(3)
Iterative Design	211	(1)
Pipelined Design	212	(1)
Unrolled Design	212	(1)
A Mixed Approach	213	(1)
Recent Hardware Implementations of Hash Functions	213	(7)
Conclusions	220	(1)
General Guidelines for Implementing Block Ciphers in FPGAs	221	(24)
Introduction	221	(1)
Block Ciphers	222	(10)
General Structure of a Block Cipher	223	(1)
Design Principles for a Block Cipher	224	(3)
Useful Properties for Implementing Block Ciphers in FPGAs	227	(5)
The Data Encryption Standard	232	(6)
The Initial Permutation (IP--1)	233	(1)
Structure of the Function fk	234	(3)
Key Schedule	237	(1)
FPGA Implementation of DES Algorithm	238	(2)
DES Implementation on FPGAs	238	(2)
Design Testing and Verification	240	(1)
Performance Results	240	(1)
Other DES Designs	240	(4)
Conclusions	244	(1)
Architectural Designs For the Advanced Encryption Standard	245	(46)
Introduction	245	(2)
The Rijndael Algorithm	247	(7)
Difference Between AES and Rijndael	247	(1)
Structure of the AES Algorithm	248	(1)
The Round Transformation	249	(1)
ByteSubstitution (BS)	249	(2)
ShiftRows (SR)	251	(1)
MixColumns (MC)	252	(1)
AddRoundKey (ARK)	253	(1)
Key Schedule	254	(1)
AES in Different Modes	254	(5)
CTR Mode	255	(1)
CCM Mode	256	(3)
Implementing AES Round Basic Transformations on FPGAs	259	(9)
S-Box/Inverse S-Box Implementations on FPGAs	260	(4)
MC/IMC Implementations on FPGA	264	(3)
Key Schedule Optimization	267	(1)
AES Implementations on FPGAs	268	(17)
Architectural Alternatives for Implementing AES	269	(4)
Key Schedule Algorithm Implementations	273	(3)
AES Encryptor Cores - Iterative and Pipeline Approaches	276	(2)
AES Encryptor/Decryptor Cores - Using Look-Up Table and Composite Field Approaches for S-Box	278	(3)
AES Encryptor/Decryptor, Encryptor, and Decryptor Cores Based on Modified MC/IMC	281	(3)
Review of This Chapter Designs	284	(1)
Performance	285	(3)
Other Designs	285	(3)
Conclusions	288	(3)
Elliptic Curve Cryptography	291	(38)
Introduction	291	(3)
Hessian Form	294	(2)
Weierstrass Non-Singular Form	296	(4)
Projective Coordinates	296	(1)
The Montgomery Method	297	(3)
Parallel Strategies for Scalar Point Multiplication	300	(2)
Implementing scalar multiplication on Reconfigurable Hardware	302	(6)
Arithmetic-Logic Unit for Scalar Multiplication	303	(1)
Scalar multiplication in Hessian Form	304	(2)
Montgomery Point Multiplication	306	(1)
Implementation Summary	306	(2)
Koblitz Curves	308	(9)
The τ and τ-1 Frobenius Operators	309	(3)
ωNAF Scalar Multiplication in Two Phases	312	(1)
Hardware Implementation Considerations	313	(4)
Half-and-Add Algorithm for Scalar Multiplication	317	(9)
Efficient Elliptic Curve Arithmetic	318	(3)
Implementation	321	(3)
Performance Estimation	324	(2)
Performance Comparison	326	(2)
Conclusions	328	(1)
References	329	(30)
Index	359