Public Key Cryptosystems

This book is a short book about public key cryptosystems, digital signature algorithms, and their basic cryptanalysis which are provided at a basic level so that it can be easy to understand for the undergraduate engineering students who can be defined as the core audience. To provide the necessary background, Chapters 1 and 2 are devoted to the selected fundamental concepts in cryptography mathematics and selected fundamental concepts in cryptography. Chapter 3 is devoted to discrete logarithm problem (DLP), DLP-related public key cryptosystems, digital signature algorithms, and their cryptanalysis. In this chapter, the elliptic curve counterparts of the algorithms and the basic algorithms for the solution of DLP are also given. In Chapter 4, RSA public key cryptosystem, RSA digital signature algorithm, the basic cryptanalysis approaches, and the integer factorization methods are provided. Chapter 5 is devoted to GGH and NTRU public key cryptosystems, GGH and NTRU digital signature algorithms, and the basic cryptanalysis approaches, whereas Chapter 6 covers other topics including knapsack cryptosystems, identity-based public key cryptosystems, identity-based digital signature algorithms, Goldwasser-Micali probabilistic public key cryptosystem, and their cryptanalysis. The book’s distinctive features: The book provides some fundamental mathematical and conceptual preliminaries required to understand the core parts of the book. The book comprises the selected public key cryptosystems, digital signature algorithms, and the basic cryptanalysis approaches for these cryptosystems and algorithms. The cryptographic algorithms and most of the solutions of the examples are provided in a structured table format to support easy learning. The concepts and algorithms are illustrated with examples, some of which are revisited multiple times to present alternative approaches. The details of the topics covered in the book are intentionally not presented; however, several references are provided at the end of each chapter so that the reader can read those references for more details. Cover Half Title Series Page Title Page Copyright Page Contents 1. Selected fundamental concepts in cryptography mathematics 1.1. Introduction 1.2. Modular arithmetic and related topics 1.2.1. Modular arithmetic 1.2.2. Basic properties in modular arithmetic 1.2.3. Fast powering algorithm (fast exponentiation algorithm, square-and-multiply algorithm) 1.2.4. Chinese remainder theorem (CRT) 1.2.5. Quadratic residue and quadratic non-residue 1.3. Rings, groups, fields 1.3.1. Ring of integers modulo m and multiplicative group of units modulo m Primitive root (element) of Fp (generator of F*p) 1.3.3. Ring of convolution polynomials and selected properties 1.4. Divisibility, greatest common divisors, and prime numbers 1.4.1. Fermat’s little theorem 1.4.2. Euclidean algorithm 1.4.3. Extended Euclidean algorithm 1.5. Euclidean algorithm and extended Euclidean algorithm for polynomials 1.5.1. Euclidean algorithm for polynomials 1.5.2. Extended Euclidean algorithm for polynomials 1.6. Integer factorization related selected mathematical fundamentals 1.6.1. Fundamental theorem of arithmetic 1.6.2. B-smooth number 1.7. Elliptic curves and related topics 1.7.1. Elliptic curve 1.7.2. An elliptic curve as an Abelian group 1.7.3. Point addition in elliptic curves 1.7.4. Elliptic curves over finite fields 1.7.5. Bilinear pairings, Weil pairings, distortion maps, and modified Weil pairings on elliptic curves 1.8. Vector spaces and lattices 1.8.1. Vector spaces 1.8.2. Lattices 1.9. Selected basics of probability 1.9.1. Random experiment and the basic principle of counting 1.9.2. Random variables 1.10. Conclusions 2. Fundamental concepts related to cryptography and public key cryptosystems 2.1. Introduction 2.2. Plaintext vs. ciphertext 2.3. Encryption function vs. decryption function 2.4. Public key vs. private (secret) key 2.5. Deterministic encryption vs. probabilistic encryption 2.6. Encoding/decoding vs. encryption/decryption 2.7. Private key cryptosystems vs. public key cryptosystems 2.8. Homomorphic encryption 2.9. Primality testing 2.9.1. Primality testing based on the Fermat’s little theorem 2.9.2. Miller-Rabin probabilistic primality testing 2.9.3. Agrawal-Kayal-Saxena (AKS) primality testing 2.10. Cryptographic hash functions 2.10.1. Basic terms regarding hash functions 2.10.2. Basic properties of cryptographic hash functions 2.10.3. Random oracle model 2.11. Digital signatures 2.12. Cryptanalysis 2.12.1. Basic types of cryptanalysis 2.12.2. Classification of cryptographic attacks based on the knowledge of ciphertexts or plaintext/ciphertext pairs 2.12.3. Basic terms regarding the attacks on digital signature algorithms 2.13. Conclusions 3. Discrete logarithm problem, elliptic curve discrete logarithm problem, and the related public key cryptosystems and digital signature algorithms 3.1. Introduction 3.2. Basic discrete logarithm problem and the related public key cryptosystems 3.2.1. Basic discrete logarithm problem (DLP) 3.2.2. Basic Diffie-Hellman key exchange and its cryptanalysis 3.2.3. Basic ElGamal public key cryptosystem, basic ElGamal digital signature algorithm, basic digital signature algorithm (DSA), and their cryptanalysis 3.3. Elliptic curve discrete logarithm problem (ECDLP) and the related public key cryptosystems 3.3.1. ECDLP 3.3.2. Elliptic curve Diffie-Hellman key exchange 3.3.3. Elliptic curve ElGamal public key cryptosystem 3.3.4. Elliptic curve DSA (ECDSA) 3.3.5. Cryptanalysis of the elliptic curve Diffie-Hellman key exchange, elliptic curve ElGamal public key cryptosystem, and ECDSA 3.4. Basic algorithms for the solution of the DLP and ECDLP 3.4.1. Shanks’ baby-step giant-step algorithm for the basic DLP and ECDLP 3.4.2. Pohlig-Hellman algorithm for the basic DLP 3.4.3. Index calculus method for the basic DLP 3.5. Conclusions 4. RSA public key cryptosystem, RSA digital signature algorithm, and integer factorization 4.1. Introduction 4.2. RSA public key cryptosystem and RSA digital signature algorithm 4.2.1. RSA public key cryptosystem 4.2.2. RSA digital signature algorithm 4.3. Cryptanalysis of RSA public key cryptosystem and RSA digital signature algorithm 4.3.1. Attacks related to factoring the modulus N 4.3.2. Attacks due to the low public encryption key 4.3.3. Wiener’s attack, Boneh-Durfee attack, and May’s attack 4.3.4. Homomorphic attack 4.3.5. Chosen ciphertext attack of Davida and chosen ciphertext attack of Bleichenbacher 4.3.6. Implementation attacks 4.4. Basic approaches and algorithms for factoring an integer number into two prime numbers 4.4.1. Trial division 4.4.2. Factorization via difference of squares 4.4.3. Three-step factorization procedure 4.4.4. Continued fraction factorization algorithm (CFRAC), quadratic sieve (QS), and the number field sieve (NFS) 4.4.5. Pollard’s p − 1 factorization algorithm 4.4.6. Lenstra’s elliptic curve factorization algorithm 4.4.7. Pollard’s p (rho) algorithm 4.4.8. Shor’s algorithm 4.5. Conclusions 5. Goldreich, Goldwasser, Halevi (GGH) public key cryptosystem, GGH digital signature algorithm, NTRU public key cryptosystem, and NTRU signature scheme 5.1. Introduction 5.2. GGH public key cryptosystem, GGH digital signature algorithm, and cryptanalysis 5.2.1. GGH public key cryptosystem 5.2.2. GGH digital signature algorithm 5.2.3. Cryptanalysis of the GGH public key cryptosystem and GGH digital signature algorithm 5.3. NTRU public key cryptosystem (NTRUEncrypt), NTRU signature scheme (NSS), and cryptanalysis 5.3.1. NTRU public key cryptosystem 5.3.2. NTRU digital signature algorithm 5.3.3. Cryptanalysis of the NTRU public key cryptosystem and NTRU digital signature algorithm 5.4. Conclusions 6. Other selected public key cryptosystems and digital signature algorithms 6.1. Introduction 6.2. Knapsack cryptosystems (Subset-sum cryptosystems) 6.2.1. Subset-sum problem (SSP) 6.2.2. Superincreasing sequence of integers 6.2.3. Additive knapsack cryptosystems 6.2.4. Single-iterated Merkle–Hellman knapsack cryptosystem 6.2.5. Multiplicative knapsack cryptosystem 6.3. Identity-based (ID-based) public key cryptosystems, ID-based digital signature algorithms, and cryptanalysis 6.3.1. Basic idea of the ID-based public key cryptosystems 6.3.2. Basic idea of the ID-based digital signature algorithm 6.3.3. Cryptanalysis of the ID-based public key cryptosystems and ID-based digital signature algorithms 6.4. Goldwasser-Micali probabilistic public key cryptosystem and its cryptanalysis 6.4.1. Goldwasser–Micali probabilistic public key cryptosystem 6.4.2. Cryptanalysis of Goldwasser–Micali probabilistic public key cryptosystem 6.5. Conclusions