Cryptography provides techniques, mechanisms, and tools for private and authenticated communication, and for performing secure and authenticated transactions over the Internet as well as other open networks. It is highly probable that each bit of information flowing through our networks will have to be either encrypted and decrypted or signed and authenticated in a few years from now. This infrastructure is needed to carry over the legal and contractual certainty from our paper-based offices to our virtual offices existing in the cyberspace. In such an environment, server and client computers as well as handheld, portable, and wireless devices will have to be capable of encrypting or decrypting and signing or verifying messages. That is to say, without exception, all networked computers and devices must have cryptographic layers implemented, and must be able to access to cryptographic functions in order to provide security features. In this context, efficient (in terms of time, area, and power consumption) hardware structures will have to be designed, implemented, and deployed. Furthermore, general-purpose (platform-independent) as well as special-purpose software implementing cryptographic functions on embedded devices are needed. An additional challenge is that these implementations should be done in such a way to resist cryptanalytic attacks launched against them by adversaries having access to primary (communication) and secondary (power, electromagnetic, acoustic) channels.

This book, among only a few on the subject, is a fruit of an international collaboration to design and implement cryptographic functions. The authors, who now seem to be scattered over the globe, were once together as students and professors in North America. In Oregon and Mexico City, we worked on subjects of mutual interest, designing efficient realizations of cryptographic functions in hardware and software.

Cryptographic realizations in software platforms can be used for those security applications where the data traffic is not too large and thus low encryption rate is acceptable. On the other hand, hardware methods offer high speed and bandwidth, providing real-time encryption if needed. VLSI (also known as ASIC) and FPGAs are two distinct alternatives for implementing XXVI cryptographic algorithms in hardware. FPGAs offer several benefits for cryptographic algorithm implementations over VLSI, as they offer flexibility and fast time-to-market. Because they are reconfigurable, internal architectures, system parameters, lookup tables, and keys can be changed in FPGAs without much effort. Moreover, these features come with low cost and without sacrificing efficiency.

This book covers computational methods, computer arithmetic algorithms, and design improvement techniques needed to obtain efficient implementations of cryptographic algorithms in FPGA reconfigurable hardware platforms. The concepts and techniques introduced in this book pay special attention to the practical aspects of reconfigurable hardware design, explain the fundamental mathematics behind the algorithms, and give comprehensive descriptions of the state-of-the-art implementation techniques. The main goal pursued in this book is to show how one can obtain high-speed cryptographic implementations on reconfigurable hardware devices without requiring prohibitive amount of hardware resources.

Every book attempts to take a still picture of a moving subject and will soon need to be updated, nevertheless, it is our hope that engineers, scientists, and students will appreciate our efforts to give a glimpse of this deep and exciting world of cryptographic engineering.

You can order this book from Springer or Amazon.

• 1. INTRODUCTION

  • 1.1 Main Goals

  • 1.2 Monograph Organization

  • 1.3 Acknowledgments

• 2. A BRIEF INTRODUCTION TO MODERM CRYPTOGRAPHY

  • 2.1 Introduction

  • 2.2 Secret Key Cryptography

  • 2.3 Hash Functions

  • 2.4 Public Key Cryptography

  • 2.5 Digital Signature Schemes

    • 2.5.1 RSA Digital Signature

    • 2.5.2 RSA Standards

    • 2.5.3 DSA Digital Signature

    • 2.5.4 Digital Signature with Elliptic Curves

    • 2.5.5 Key Exchange

  • 2.6 A Comparison of Public Key Cryptosystems

  • 2.7 Cryptographic Security Strength

  • 2.8 Potential Cryptographic Applications

  • 2.9 Fundamental Operations for Cryptographic Algorithms

  • 2.10 Design Alternatives for Implementing Cryptographic Algorithms

  • 2.11 Conclusions

• 3. RECONFIGURABLE HARDWARE TECHNOLOGY

  • 3.1 Antecedents

  • 3.2 Field Programmable Gate Arrays

    • 3.2.1 Case of Study I: Xilinx FPGAs

    • 3.2.2 Case of Study II: Altera FPGAs

  • 3.3 FPGA Platforms versus ASIC and General-Purpose Processor Platforms

    • 3.3.1 FPGAs versus ASICs

    • 3.3.2 FPGAs versus General-Purpose Processors

  • 3.4 Reconfigurable Computing Paradigm

    • 3.4.1 FPGA Programming

    • 3.4.2 VHSIC Hardware Descruption Language (VHDL)

    • 3.4.3 Other Programming Models for FPGAs

  • 3.5 Implementation Aspects for Reconfigurable Hardware Designs

    • 3.5.1 Design Flow

    • 3.5.2 Design Techniques

    • 3.5.3 Strategies for Exploiting FPGA Parallelism

  • 3.6 FPGA Architecture Statics

  • 3.7 Security in Reconfigurable Hardware Devices

  • 3.8 Conclusions

• 4. MATHEMATICAL BACKGROUND

  • 4.1 Basic Concepts of the Elementary Theory of Numbers

    • 4.1.1 Basic Notions

    • 4.1.2 Modular Arithmetic

  • 4.2 Finite Fields

    • 4.2.1 Rings

    • 4.2.2 Fields

    • 4.2.3 Finite Fields

    • 4.2.4 Binary Finite Fields

  • 4.3 Elliptic Curves

    • 4.3.1 Definition

    • 4.3.2 Elliptic Curve Operations

    • 4.3.3 Elliptic Curve Scalar Multiplication

  • 4.4 Elliptic Curves over GF(2^m)

    • 4.4.1 Point Addition

    • 4.4.2 Point Doubling

    • 4.4.3 Order of an Elliptic Curve

    • 4.4.4 Elliptic Curve Groups and the Discrete Logarithm Problem

    • 4.4.5 An example

  • 4.5 Point Representation

    • 4.5.1 Projective Coordinates

    • 4.5.2 López-Dahab Coordinates

  • 4.6 Scalar Representation

    • 4.6.1 Binary Representation

    • 4.6.2 Recoding Methods

    • 4.6.3 ω-NAF Representation

  • 4.7 Conclusions

• 5. PRIME FINITE FIELD ARITHMETIC

  • 5.1 Addition Operation

    • 5.1.1. Full-Adder and Half-Adder Cells

    • 5.1.2 Carry Propagate Adder

    • 5.1.3 Carry Completion Sensing Adder

    • 5.1.4 Carry Look-Ahead Adder

    • 5.1.5 Carry Save Adder

    • 5.1.6 Carry Delayed Adder

  • 5.2 Modular Addition Operation

    • 5.2.1 Omura's Method

  • 5.3 Modular Multiplication Operation

    • 5.3.1 Standard Multiplication Algorithm

    • 5.3.2 Squaring is Easier

    • 5.3.3 Modular Reduction

    • 5.3.4 Interleaving Multiplication and Reduction

    • 5.3.5 Utilization of Carry Save Adders

    • 5.3.6 Brickell's Method

    • 5.3.7 Montgomery's Method

    • 5.3.8 High-Radix Interleaving Method

    • 5.3.9 High-Radix Montgomery's Method

  • 5.4 Modular Exponentiation Operation

    • 5.4.1 Binary Strategies

    • 5.4.2 Window Strategies

    • 5.4.3 Adaptive Window Strategy

    • 5.4.4 RSA Exponentiation and the Chinese Remainder Theorem

    • 5.4.5 Recent Prime Finite Field Arithmetic Designs on FPGAs

  • 5.5 Conclusions

• 6. BINARY FINITE FIELD ARITHMETIC

  • 6.1 Field Multiplication

    • 6.1.1 Classical Multipliers and their Analysis

    • 6.1.2 Binary Karatsuba-Ofman Multipliers

    • 6.1.3 Squaring

    • 6.1.4 Reduction

    • 6.1.5 Modular Reduction with General Polynomials

    • 6.1.6 Interleaving Multiplication

    • 6.1.7 Matrix-Vector Multipliers

    • 6.1.8 Montgomery Multiplier

    • 6.1.9 A Comparison of Field Multiplier Designs

  • 6.2 Field Squaring and Field Square Root for Irreducible Trinomials

    • 6.2.1 Field Squaring Computation

    • 6.2.2 Field Square Root Computation

    • 6.2.3 Illustrative Examples

  • 6.3 Multiplicative Inverse

    • 6.3.1 Inversion Based on the Extended Euclidean Algorithm

    • 6.3.2 The Itoh-Tsujii Algorithm

    • 6.3.3 Addition Chains

    • 6.3.4 ITMIA Algorithm

    • 6.3.5 Square Root ITMIA

    • 6.3.6 Extended Euclidean Algorithm versus Itoh-Tsujii Algorithm

    • 6.3.7 Multiplicative Inverse FPGA Designs

  • 6.4 Other Arithmetic Operations

    • 6.4.1 Trace function

    • 6.4.2 Solving a Quadratic Equation over GF(2^m)

    • 6.4.3 Exponentiation over Binary Finite Fields

  • 6.5 Conclusion

• 7. RECONFIGURABLE HARDWARE IMPLEMENTATION OF HASH FUNCTIONS

  • 7.1 Introduction

  • 7.2 Some Famous Hash Functions

  • 7.3 MD5

    • 7.3.1 Message Preprocessing

    • 7.3.2 MD Buffer Initialization

    • 7.3.3 Main Loop

    • 7.3.4 Final Transformation

  • 7.4 SHA-1, SHA-256, SHA-384 and SHA-512

    • 7.4.1 Message Preprocessing

    • 7.4.2 Functions

    • 7.4.3 SHA-1

    • 7.4.4 Constants

    • 7.4.5 Hash Computation

  • 7.5 Hardware Architectures

    • 7.5.1 Iterative Design

    • 7.5.2 Pipelined Design

    • 7.5.3 Unrolled Design

    • 7.5.4 A Mixed Approach

  • 7.6 Recent Hardware Implementations of Hash Functions

  • 7.7 Conclusions

• 8. GENERAL GUIDELINES FOR IMPLEMENTING BLOCK CIPHERS IN FPGAS

  • 8.1 Introduction

  • 8.2 Block Ciphers

    • 8.2.1 General Structure of a Block Cipher

    • 8.2.2 Design Principles for a Block Cipher

    • 8.2.3 Useful Properties for Implementing Block Ciphers in FPGAs

  • 8.3 The Data Encryption Standard

    • 8.3.1 The Initial Permutation (IP^-1)

    • 8.3.2 Structure of the Function fk

    • 8.3.3 Key Schedule

  • 8.4 FPGA Implementation of DES Algorithm

    • 8.4.1 DES Implementation on FPGAs

    • 8.4.2 Design Testing and Verification

    • 8.4.3 Performance Results

  • 8.5 Other DES Designs

  • 8.6 Conclusions

• 9. ARCHITECTURAL DESIGNS FOR THE ADVANCED ENCRYPTION STANDARD

  • 9.1 Introduction

  • 9.2 The Rijndael Algorithm

    • 9.2.1 Difference Between AES and Rijndael

    • 9.2.2 Structure of the AES Algorithm

    • 9.2.3 The Round Transformation

    • 9.2.4 ByteSubstitution (BS)

    • 9.2.5 ShiftRows (SR)

    • 9.2.6 MixColumns (MC)

    • 9.2.7 AddRoundKey (ARK)

    • 9.2.8 Key Schedule

  • 9.3 AES in Different Modes

    • 9.3.1 CTR Mode

    • 9.3.2 CCM Mode

  • 9.4 Implementing AES Round Basic Transformations on FPGAs

    • 9.4.1 S-Box/Inverse S-Box Implementations on FPGAs

    • 9.4.2 MC/IMC Implementations on FPGA

    • 9.4.3 Key Schedule Optimization

  • 9.5 AES Implementations on FPGAs

    • 9.5.1 Architectural Alternatives for Implementing AEs

    • 9.5.2 Key Schedule Algorithm Implementations

    • 9.5.3 AES Encryptor Cores - Iterative and Pipeline Approaches

    • 9.5.4 AES Encryptor/Decryptor Cores - Using Look-Up Table and Composite Field Approaches for S-Box

    • 9.5.5 AES Encryptor/Decryptor Cores Based on Modified MC/IMC

    • 9.5.6 Review of This Chapter Designs

  • 9.6 Performance

    • 9.6.1 Other Designs

  • 9.7 Conclusions

• 10. ELLIPTIC CURVE CRYPTOGRAPHY

  • 10.1 Introduction

  • 10.2 Hessian Form

  • 10.3 Weierstrass Non-Singular Form

    • 10.3.1 Projective Coordinates

    • 10.3.2 The Montgomery Method

  • 10.4 Parallel Strategies for Scalar Point Multiplication

  • 10.5Implementing scalar multiplication on Reconfigurable Hardware

    • 10.5.1 Arithmetic-Logic Unit for Scalar Multiplication

    • 10.5.2 Scalar multiplication in Hessian Form

    • 10.5.3 Montgomery Point Multiplication

    • 10.5.4 Implementation Summary

  • 10.6 Koblitz Curves

    • 10.6.1 The τ and τ^-1 Frobenius Operators

    • 10.6.2 ωτNAF Scalar Multiplication in Two Phases

    • 10.6.3 Hardware Implementations Considerations

  • 10.7 Half-and-Add Algorithm for Scalar Multiplication

    • 10.7.1 Efficient Elliptic Curve Arithmetic

    • 10.7.2 Implementation

    • 10.7.3 Performance Estimation

  • 10.8 Performance Comparison

  • 10.9 Conclusions