Energy-Efficient Modular Exponential Techniques for Public-Key Cryptography: Efficient Modular Exponential Techniques

✍ Scribed by Satyanarayana Vollala, N. Ramasubramanian, Utkarsh Tiwari

• Publisher: Springer
• Year: 2021
• Tongue: English
• Leaves: 265
• Edition: 1st ed. 2021
• Category: Library

✦ Synopsis

Cryptographic applications, such as RSA algorithm, ElGamal cryptography, elliptic curve cryptography, Rabin cryptosystem, Diffie -Hellmann key exchange algorithm, and the Digital Signature Standard, use modular exponentiation extensively. The performance of all these applications strongly depends on the efficient implementation of modular exponentiation and modular multiplication. Since 1984, when Montgomery first introduced a method to evaluate modular multiplications, many algorithmic modifications have been done for improving the efficiency of modular multiplication, but very less work has been done on the modular exponentiation to improve the efficiency. This research monograph addresses the question- how can the performance of modular exponentiation, which is the crucial operation of many public-key cryptographic techniques, be improved? 

The book focuses on Energy Efficient Modular Exponentiations for Cryptographic hardware. Spread across five chapters, this well-researched text focuses in detail on the Bit Forwarding Techniques and the corresponding hardware realizations. Readers will also discover advanced performance improvement techniques based on high radix multiplication and Cryptographic hardware based on multi-core architectures.

✦ Table of Contents

Foreword
Preface
Acknowledgements
Scope of the Book
Contents
Acronyms
Part I Introduction
1 Cryptographic Techniques
1.1 Cryptography
1.2 Information Security Objectives
1.3 Techniques of Cryptography
1.3.1 Symmetric Key Cryptography
1.3.2 Asymmetric Key Cryptography
1.3.3 Difference between Symmetric and Asymmetric Key Cryptography
1.4 Software Versus Hardware Implementation
1.5 Multi-core Architectures
1.5.1 Homogeneous Architecture
1.5.2 Heterogeneous Architecture
1.5.3 Software Defined Radio (SDR)
1.6 Scheduler for Multi-core Architectures
1.7 Organization of the Book
References
2 Public Key Cryptography
2.1 Introduction
2.1.1 Public Key Cryptosystem Domain
2.1.2 Euler's Theorem
2.1.3 Steps in PKC
2.2 RSA
2.3 Elgamal
2.3.1 Classic Elgamal
2.3.2 Semi-classic Elgamal
2.4 Rabin
2.4.1 Draw-Back of Rabin PKC
2.5 Elliptic Curve Cryptography
2.5.1 Finite Fields
2.5.2 Elliptic Curve
2.5.3 Elliptic Curve Public-Key Cryptography
2.6 PKC in Wireless-Sensor-Networks (WSN)
2.7 Possible Attacks on PKC
References
Part II Modular Exponentiation
3 Modular Exponential Techniques
3.1 Binary Modular Exponential Technique
3.1.1 Left-to-Right Binary Exponential Technique
3.1.2 Right-to-Left Binary Exponential Technique
3.1.3 Applying Modulus Operation in Exponential Technique
3.2 Sliding Window Technique
3.2.1 M-Ary Method
3.2.2 Use of M-Ary in Sliding Window Technique
3.2.3 Attacks on Sliding Window Exponential Technique
3.3 Bit Forwarding Techniques
3.3.1 Bit Forwarding 1-Bit Algorithm
3.3.2 Bit Forwarding 2-Bits Algorithm
3.3.3 Bit Forwarding 3-Bits Algorithm
References
4 Review of Algorithmic Techniques for Improving the Performance of Modular Exponentiation
4.1 Montgomery Multiplication
4.2 High-Radix Modular Multiplication
4.2.1 Radix-4 Modular Multiplication
4.2.2 Modular Exponentiation Using Radix-4 Montgomery Multiplication
4.3 Chinese Remainder Theorem (CRT)
4.4 Enhancement in the Montgomery Multiplication
4.4.1 Residue Number System in Montgomery Multiplication
4.4.2 Adaptable Montgomery Multiplication for Radix-2 (AMM)
4.4.3 Adaptable High-Radix Montgomery Multiplication (AHRMM)
References
5 Review of Hardware Techniques for Improving Performance of Modular Exponentiation
5.1 Pipeline
5.2 Carry Save Adder (CSA)
5.2.1 Five-to-Two CSA
5.2.2 Four-to-Two CSA
5.3 Field-Programmable Gate Array (FPGA)
5.4 Application Specific Integrated Circuits (ASIC)
5.5 Systolic Array
5.6 Transport Triggered Architecture (TTA)
5.7 Cox-Rower Architecture
References
Part III Modular Multiplication
6 Introduction to Montgomery Multiplication
6.1 Montgomery Multiplication
6.1.1 Independent Operand Scanning (IOS)
6.1.2 Less Switching Operand Scanning (LSOS)
6.1.3 High Switching Operand Scanning (HSOS)
6.1.4 High Switching Product Scanning (HSPS)
6.1.5 Less Switching Hybrid Scanning (LSHS)
6.2 An RNS Montgomery Multiplication Algorithm
6.3 Pipelining Architectures for Modular Multiplication
6.4 Parallel Modular Multiplication on Multi-core Processors
References
7 Hardware Realization of Montgomery Multiplication with Radix-2
7.1 Simple Radix-2 Montgomery Multiplication
7.2 The Tenca–Koc Algorithm
7.3 Hardware Optimization for Multiple Word Radix-2 Montgomery Multiplication
7.4 VLSI Based Montgomery Multiplication
7.4.1 SCS-Based Montgomery Multiplication
7.4.2 FCS-Based Montgomery Multiplication
7.5 Bit-Serial and Bit-Parallel Montgomery Multiplication and Squaring
7.5.1 MSB-First Bit-Serial Modular Multiplication
7.5.2 LSB-First Bit-Serial Modular Multiplication
7.5.3 Bit-Parallel Montgomery Multiplication
7.6 Parallelization of Radix-2 Montgomery Multiplication
References
8 High Radix Montgomery Multiplication
8.1 High Radix Montgomery Multiplication by Miyamoto
8.2 Multiple—Word Montgomery Multiplication
8.3 Hardware Implementation of Radix-4 Montgomery Multiplication
8.4 Hardware Implementation of Radix-16 Montgomery Multiplication
8.5 High-Radix Systolic Architectures of Montgomery Multiplication
8.5.1 Systolic Architecture Based on DSP
8.6 Finely Pipelined Modular Multipliers
8.7 Montgomery Ladder Modular Multiplication
8.8 Digit-Digit Computation Approach Scalable Montgomery Multiplier
References
Part IV Modular Exponentiation Based on Bit Forwarding Techniques
9 Bit Forwarding Techniques for Efficient Modular Exponentiation
9.1 Introduction
9.2 Bit Forwarding Techniques for Evaluating Modular Exponentiation
9.2.1 BFW-1: Bit Forwarding 1-Bit Algorithm
9.2.2 BFW-2: Bit Forwarding 2-Bits Algorithm
9.2.3 BFW-3: Bit Forwarding 3-Bits Algorithm
9.2.4 AMM: Adaptable Montgomery Multiplication
9.2.5 AHRMM: Adaptable High-Radix Montgomery Multiplication
9.2.6 Correctness of BFW Techniques
9.2.7 Completeness of BFW Algorithms
9.3 Analysis of BFW Algorithms
9.3.1 BFW-1
9.3.2 BFW-2
9.3.3 BFW-3
9.4 Comparative Study of Sliding Window Techniques and BFW Techniques
9.4.1 Bit Forwarding Techniques
9.4.2 Sliding Window Techniques
9.4.3 Comparison Between Sliding Window Techniques and BFW Techniques
References
10 Hardware Implementation of Bit Forwarding Techniques
10.1 Introduction
10.2 Hardware Design of Bit Forwarding Algorithms
10.3 AMM: Adaptable Montgomery Multiplication
10.4 MSM: Modified Square and Multiply
10.5 BFW-1: Bit Forwarding 1-Bit Algorithm
10.6 BFW-2: Bit Forwarding 2-Bits Algorithm
10.7 BFW-3: Bit Forwarding 3-Bits Algorithm
10.8 Analysis of Hardware Realization of BFW Algorithms
10.8.1 Adaptable Montgomery Multiplication
10.8.2 Modified Square and Multiply Algorithm
10.8.3 BFW-1: Bit Forwarding 1-Bit Algorithm
10.8.4 BFW-2: Bit Forwarding 2-Bits Algorithm
10.8.5 BFW-3: Bit Forwarding 3-Bit Algorithm
10.9 Analysis of the BFW Techniques
10.10 Selection Criteria of BFW-j
References
Part V Multi-core Environment for Modular Exponentiation
11 RSA Processor for Concurrent Cryptographic Transformations
11.1 Introduction
11.2 RSA Processor by Vollala et al.
11.2.1 Controller
11.2.2 Hardware Scheduler
11.2.3 BRAM Controller
11.2.4 RSA Core
11.3 Hardware Implementation of the Architecture
11.3.1 AMM
11.3.2 Dual Core RSA Processor
11.4 Comparative Analysis
11.5 Quad-Core RSA Processor
11.6 Security Analysis
References
12 Implementation of Modular Exponentiation in Dual-Core
12.1 Introduction
12.2 High-Radix Montgomery Multiplication
12.3 Right-to-Left Modular Exponentiation for Dual-Core Processor
12.3.1 The Enhanced Right-to-Left Binary Exponentiation
12.3.2 Modified High-Radix Montgomery Multiplication (MHRM)
12.4 Performance Analysis and Comparison
12.4.1 Modified High-Radix Montgomery Multiplication
12.4.2 Right-to-Left Binary Exponentiation
References
Appendix Index
Index