Learning and Experiencing Cryptography with CrypTool and SageMath

This book provides a broad overview of cryptography and enables cryptography for trying out. It emphasizes the connections between theory and practice, focuses on RSA for introducing number theory and PKI, and links the theory to the most current recommendations from NIST and BSI. The book also enables readers to directly try out the results with existing tools available as open source. It is different from all existing books because it shows very concretely how to execute many procedures with different tools. The target group could be self-learners, pupils and students, but also developers and users in companies. All code written with these open-source tools is available. The appendix describes in detail how to use these tools. The main chapters are independent from one another. At the end of most chapters, you will find references and web links. The sections have been enriched with many footnotes. Within the footnotes you can see where the described functions can be called and tried within the different CrypTool versions, within SageMath or within OpenSSL. Learning and ExperiencingCryptography with CrypTooland SageMath Contents Preface Acknowledgments Introduction The CrypTool Book The Programs CrypTool 1, CrypTool 2, and JCrypTool The Programs on CrypTool-Online (CTO) MysteryTwister The SageMath Computer-Algebra System Chapter 1Ciphers and Attacks Against Them 1.1 Importance of Cryptology 1.2 Symmetric Encryption 1.2.1 AES 1.2.2 Current Status of Brute-Force Attacks on Symmetric Algorithms 1.3 Asymmetric Encryption 1.4 Hybrid Procedures 1.5 Kerckhoffs’ Principle 1.6 Key Spaces: A Theoretical and Practical View 1.6.1 Key Spaces of Historic Cipher Devices 1.6.2 Which Key Space Assumptions Should Be Used 1.6.3 Conclusion of Key Spaces of Historic Cipher Devices 1.7 Best Known Attacks on Given Ciphers 1.7.1 Best Known Attacks Against Classical Ciphers 1.7.2 Best Known Attacks Against Modern Ciphers 1.8 Attack Types and Security Definitions 1.8.1 Attack Parameters 1.8.2 Indistinguishability Security Definitions 1.8.3 Security Definitions 1.9 Algorithm Types and Self-Made Ciphers 1.9.1 Types of Algorithms 1.9.2 New Algorithms 1.10 Further References and Recommended Resources 1.11 AES Visualizations/Implementations 1.11.1 AES Animation in CTO 1.11.2 AES in CT2 1.11.3 AES with OpenSSL at the Command Line of the Operating System 1.11.4 AES with OpenSSL within CTO 1.12 Educational Examples for Symmetric Ciphers UsingSageMath 1.12.1 Mini-AES 1.12.2 Symmetric Ciphers for Educational Purposes References Chapter 2 Paper-and-Pencil and PrecomputerCiphers 2.1 Transposition Ciphers 2.1.1 Introductory Samples of Different Transposition Ciphers 2.1.2 Column and Row Transposition 2.1.3 Further Transposition Algorithm Ciphers 2.2 Substitution Ciphers 2.2.1 Monoalphabetic Substitution 2.2.2 Homophonic Substitution 2.2.3 Polygraphic Substitution 2.2.4 Polyalphabetic Substitution 2.3 Combining Substitution and Transposition 2.4 Further P&P Methods 2.5 Hagelin Machines as Models for Precomputer Ciphers 2.5.1 Overview of Early Hagelin Cipher Machines 2.5.2 Hagelin C-52/CX-52 Models 2.5.3 Hagelin Component in CT2 2.5.4 Recap on C(X)-52: Evolution and Influence 2.6 Ciphers Defined by the American CryptogramAssociation 2.7 Examples of Open-Access Publications on Cracking Classical Ciphers 2.8 Examples Using SageMath 2.8.1 Transposition Ciphers 2.8.2 Substitution Ciphers 2.8.3 Cryptanalysis of Classical Ciphers with SageMath References Chapter 3Historical Cryptology 3.1 Introduction 3.2 Analyzing Historical Ciphers: From Collection toInterpretation 3.3 Collection of Manuscripts and Creation of Metadata 3.4 Transcription 3.4.1 Manual Transcription 3.4.2 CTTS: Offline Tool for Manual Transcription 3.4.3 Automatic Transcription 3.4.4 The Future of Automatic Transcription 3.5 Cryptanalysis 3.5.1 Tokenization 3.5.2 Heuristic Algorithms for Cryptanalysis 3.5.3 Cost Functions 3.6 Contextualization and Interpretation: Historical andPhilological Analysis 3.6.1 Analysis of Historical Languages (Linguistic Analysis) 3.6.2 Historical Analysis and Different Research Approaches 3.7 Conclusion References Chapter 4Prime Numbers 4.1 What Are Prime Numbers? 4.2 Prime Numbers in Mathematics 4.3 How Many Prime Numbers Are There? 4.4 The Search for Extremely Large Primes 4.4.1 The 20+ Largest Known Primes 4.4.2 Special Number Types: Mersenne Numbers and Mersenne Primes 4.5 Prime Number Tests 4.5.1 Special Properties of Primes for Tests 4.5.2 Pseudoprime Numbers 4.6 Special Types of Numbers and the Search for a Formula for Primes 4.6.1 Mersenne Numbers f (n) = 2n 􀀀 1 for n Prime 4.6.2 Generalized Mersenne Numbers f (k; n) = k
2n  1 for n Prime and kSmall Prime/Proth Numbers 4.6.3 Generalized Mersenne Numbers f (b; n) = bn  1 / The CunninghamProject 4.6.4 Fermat Numbers Fn = f (n) = 22n+1 4.6.5 Generalized Fermat Numbers f (b; n) = b2n+1 4.6.6 Idea Based on Euclid’s Proof: p1
p2
: : :
pn +1 4.6.7 As Above but 􀀀1 except +1: p1
p2
: : :
pn 􀀀 1 4.6.8 Euclid Numbers en = e0
e1
: : :
en􀀀1 +1 with n  1 and e0 := 1 4.6.9 f (n) = n2 +n +41 4.6.10 f (n) = n2 􀀀 79n +1601 and Heegner Numbers 4.6.11 Polynomial Functions f (x) = an xn +an􀀀1xn􀀀1 +


+a1x1 +a0(ai 2 Z, n  1) 4.6.12 Catalan’s Mersenne Conjecture 4.6.13 Double Mersenne Primes 4.7 Density and Distribution of the Primes 4.8 Outlook 4.9 Notes about Primes 4.9.1 Proven Statements and Theorems about Primes 4.9.2 Arithmetic Prime Sequences 4.9.3 Unproven Statements, Conjectures, and Open Questions about Primes 4.9.4 The Goldbach Conjecture 4.9.5 Open Questions about Twin Primes 4.9.6 Prime Gaps 4.9.7 Peculiar and Interesting Things about Primes 4.10 Number of Prime Numbers in Various Intervals 4.11 Indexing Prime Numbers: nth Prime Number 4.12 Orders of Magnitude and Dimensions in Reality 4.13 Special Values of the Binary and Decimal Systems 4.14 Visualization of the Quantity of Primes in Higher Ranges 4.14.1 The Distribution of Primes 4.15 Examples Using SageMath 4.15.1 Some Basic Functions about Primes Using SageMath 4.15.2 Check Primality of Integers Generated by Quadratic Functions References Chapter 5 Introduction to Elementary NumberTheory with Examples 5.1 Mathematics and Cryptography 5.2 Introduction to Number Theory 5.2.1 Convention and Notation 5.3 Prime Numbers and the First Fundamental Theorem ofElementary Number Theory 5.4 Divisibility, Modulus and Remainder Classes 5.4.1 Divisibility 5.4.2 The Modulo Operation: Working with Congruences 5.5 Calculations with Finite Sets 5.5.1 Laws of Modular Calculations 5.5.2 Patterns and Structures (Part 1) 5.6 Examples of Modular Calculations 5.6.1 Addition and Multiplication 5.6.2 Additive and Multiplicative Inverses 5.6.3 Raising to the Power 5.6.4 Fast Calculation of High Powers (Square and Multiply) 5.6.5 Roots and Logarithms 5.7 Groups and Modular Arithmetic in Zn and Z 5.7.1 Addition in a Group 5.7.2 Multiplication in a Group 5.8 Euler Function, Fermat’s Little Theorem, and Euler-Fermat 5.8.1 Patterns and Structures (Part 2) 5.8.3 The Theorem of Euler-Fermat 5.8.4 Calculation of the Multiplicative Inverse 5.8.5 How Many Private RSA Keys d Are There Modulo 26 5.9 Multiplicative Order and Primitive Roots 5.10 Proof of the RSA Procedure with Euler-Fermat 5.10.1 Basic Idea of Public-Key Cryptography and Requirements forEncryption Systems 5.10.2 How the RSA Procedure Works 5.10.3 Proof that RSA Fulfills Requirement 1 (Invertibility) 5.11 Regarding the Security of RSA Implementations 5.12 Regarding the Security of the RSA Algorithm 5.12.1 Complexity 5.12.2 Security Parameters Because of New Algorithms 5.12.3 Forecasts about Factorization of Large Integers 5.12.4 Status Regarding Factorization of Specific Large Numbers 5.12.5 Further Research Results about Factorization and Prime NumberTests 5.13 Applications of Asymmetric Cryptography Using Numerical Examples 5.13.1 Problem Description for Nonmathematicians 5.13.2 The Diffie-Hellman Key-Exchange Protocol 5.14 The RSA Procedure with Specific Numbers 5.14.1 RSA with Small Prime Numbers and with a Number as Message 5.14.2 RSA with Slightly Larger Primes and a Text of Uppercase Letters 5.14.3 RSA with Even Larger Primes and a Text Made up of ASCII Characters 5.14.4 A Small RSA Cipher Challenge, Part 1 5.14.5 A Small RSA Cipher Challenge, Part 2 5.15 Didactic Comments on Modulo Subtraction 5.16 Base Representation and Base Transformation of Numbers and Estimation of Length of Digits 5.16.1 b-adic Sum Representation of Positive Integers 5.16.2 Number of Digits to Represent a Positive Integer 5.16.3 Algorithm to Compute the Base Representation 5.17 Examples Using SageMath 5.17.1 Addition and Multiplication Tables Modulo m 5.17.2 Fast Exponentiation 5.17.3 Multiplicative Order 5.17.4 Primitive Roots 5.17.5 RSA Examples with SageMath 5.17.6 How Many Private RSA Keys d Exist within a Given Modulo Range? 5.17.7 RSA Fixed Points m 2 f1; :::; n 􀀀 1g with me = m mod n References Chapter 6 The Mathematical Ideas Behind Modern Asymmetric Cryptography 6.1 One-Way Functions with Trapdoor and ComplexityClasses 6.2 Knapsack Problem as a Basis for Public-Key Procedures 6.2.1 Knapsack Problem 6.2.2 Merkle-Hellman Knapsack Encryption 6.3 Decomposition into Prime Factors as a Basis forPublic-Key Procedures 6.3.1 The RSA Procedure 6.3.2 Rabin Public-Key Procedure 1979 6.4 The Discrete Logarithm as a Basis for Public-KeyProcedures 6.4.1 The Discrete Logarithm in Zp 6.4.2 Diffie-Hellman Key Agreement 6.4.3 ElGamal Public-Key Encryption Procedure in Zp 6.4.4 Generalized ElGamal Public-Key Encryption Procedure 6.5 The RSA Plane 6.5.1 Definition of the RSA Plane 6.5.2 Finite Planes 6.5.3 Lines in a Finite Plane 6.5.4 Lines in the RSA Plane 6.5.5 Alternative Choice of Representatives 6.5.6 Points on the Axes and Inner Points 6.5.7 The Action of the Map z 7! zk 6.5.8 Orbits 6.5.9 Projections 6.5.10 Reflections 6.5.11 The Pollard p 􀀀 1 Algorithm for RSA in the 2D Model 6.5.12 Final Remarks about the RSA Plane 6.6 Outlook References Chapter 7Hash Functions, Digital Signatures, and Public-Key Infrastructures 7.1 Hash Functions 7.1.1 Requirements for Hash Functions 7.1.2 Generic Collision Attacks 7.1.3 Attacks Against Hash Functions Drive the Standardization Process 7.1.4 Attacks on Password Hashes 7.2 Digital Signatures 7.2.1 Signing the Hash Value of the Message 7.3 RSA Signatures 7.4 DSA Signatures 7.5 Public-Key Certification 7.5.1 Impersonation Attacks 7.5.2 X.509 Certificate 7.5.3 Signature Validation and Validity Models References Chapter 8Elliptic-Curve Cryptography 8.1 Elliptic-Curve Cryptography: A High-Performance Substitute for RSA? 8.2 The History of Elliptic Curves 8.3 Elliptic Curves: Mathematical Basics 8.3.1 Groups 8.3.2 Fields 8.4 Elliptic Curves in Cryptography 8.5 Operating on the Elliptic Curve 8.5.1 Web Programs with Animations to Add Points on an Elliptic Curve 8.6 Security of Elliptic-Curve Cryptography: The ECDLP 8.7 Encryption and Signing with Elliptic Curves 8.7.1 Encryption 8.8 Factorization Using Elliptic Curves 8.9 Implementing Elliptic Curves for Educational Purposes 8.9.1 CrypTool 8.10 Patent Aspects 8.11 Elliptic Curves in Use References Chapter 9Foundations of Modern Symmetric Encryption 9.1 Boolean Functions 9.1.1 Bits and Their Composition 9.1.2 Description of Boolean Functions 9.1.3 The Number of Boolean Functions 9.1.4 Bitblocks and Boolean Functions 9.1.5 Logical Expressions and Conjunctive Normal Form 9.1.6 Polynomial Expressions and Algebraic Normal Form 9.1.7 Boolean Functions of Two Variables 9.1.8 Boolean Maps 9.1.9 Linear Forms and Linear Maps 9.1.10 Systems of Boolean Linear Equations 9.1.11 The Representation of Boolean Functions and Maps 9.2 Block Ciphers 9.2.1 General Description 9.2.2 Algebraic Cryptanalysis 9.2.3 The Structure of Block Ciphers 9.2.4 Modes of Operation 9.2.5 Statistical Analyses 9.2.6 Security Criteria for Block Ciphers 9.2.7 AES 9.2.8 Outlook on Block Ciphers 9.3 Stream Ciphers 9.3.1 XOR Encryption 9.3.2 Generating the Key Stream 9.3.3 Pseudorandom Generators 9.3.4 Algebraic Attack on LFSRs 9.3.5 Approaches to Nonlinearity for Feedback Shift Registers 9.3.6 Implementation of a Nonlinear Combiner with the Class LFSR 9.3.7 Design Criteria for Nonlinear Combiners 9.3.8 Perfect (Pseudo)Random Generators 9.3.9 The BBS Generator 9.3.10 Perfectness and the Factorization Conjecture 9.3.11 Examples and Practical Considerations 9.3.12 The Micali-Schnorr Generator 9.4 Table of SageMath Examples in This Chapter References Chapter 10Homomorphic Ciphers 10.1 Origin of the Term Homomorphic 10.2 Decryption Function Is a Homomorphism 10.3 Classification of Homomorphic Methods 10.4 Examples of Homomorphic Pre-FHE Ciphers 10.4.1 Paillier Cryptosystem 10.4.2 Other Cryptosystems 10.5 Applications 10.6 Homomorphic Methods in CrypTool 10.6.1 CrypTool 2 with Paillier and DGK 10.6.2 JCrypTool with RSA, Paillier, and Gentry/Halevi 10.6.3 Poll Demo in CTO Using Homomorphic Encryption References Chapter 11 Lightweight Introduction to Lattices 11.1 Preliminaries 11.2 Equations 11.3 Systems of Linear Equations 11.4 Matrices 11.5 Vectors 11.6 Equations Revisited 11.7 Vector Spaces 11.8 Lattices 11.9 Lattices and RSA 11.9.1 Textbook RSA 11.9.2 Lattices versus RSA 11.10 Lattice Basis Reduction 11.10.1 Breaking Knapsack Cryptosystems Using Lattice Basis Reduction Algorithms 11.10.2 Factoring 11.10.3 Usage of Lattice Algorithms in Post-Quantum Cryptography andNew Developments (Eurocrypt 2019) 11.11 PQC Standardization 11.12 Screenshots and Related Plugins in the CrypToolPrograms 11.12.1 Dialogs in CrypTool 1 (CT1) 11.12.2 Lattice Tutorial in CrypTool 2 (CT2) 11.12.3 Plugin in JCrypTool (JCT) References Chapter 12Solving Discrete Logarithms and Factoring 12.1 Generic Algorithms for the Discrete Logarithm Problemin Any Group 12.1.1 Pollard Rho Method 12.1.2 Silver-Pohlig-Hellman Algorithm 12.1.3 How to Measure Running Times 12.1.4 Insecurity in the Presence of Quantum Computers 12.2 Best Algorithms for Prime Fields Fp 12.2.1 An Introduction to Index Calculus Algorithms 12.2.2 The Number Field Sieve for Calculating the Dlog 12.3 Best Known Algorithms for Extension Fields Fpn andRecent Advances 12.3.1 The Joux-Lercier Function Field Sieve 12.3.2 Recent Improvements for the Function Field Sieve 12.3.3 Quasi-Polynomial Dlog Computation of Joux et al. 12.3.4 Conclusions for Finite Fields of Small Characteristic 12.3.5 Do These Results Transfer to Other Index Calculus Type Algorithms? 12.4 Best Known Algorithms for Factoring Integers 12.4.1 The Number Field Sieve for Factorization 12.4.2 Relation to the Index Calculus Algorithm for Dlogs in Fp 12.4.3 Integer Factorization in Practice 12.4.4 Relation of Key Size versus Security for Dlog in Fp and Factoring 12.5 Best Known Algorithms for Elliptic Curves E 12.5.1 The GHS Approach for Elliptic Curves E[pn] 12.5.2 The Gaudry-Semaev Algorithm for Elliptic Curves E[pn] 12.5.3 Best Known Algorithms for Elliptic Curves E[p] Over Prime Fields 12.5.4 Relation of Key Size versus Security for Elliptic Curves E[p] 12.5.5 How to Securely Choose Elliptic Curve Parameters 12.6 Possibility of Embedded Backdoors inCryptographic Keys 12.7 Conclusion: Advice for Cryptographic Infrastructure 12.7.1 Suggestions for Choice of Scheme 12.7.2 Year 2023: Conclusion Remarks References Chapter 13 Future Use of Cryptography 13.1 Widely Used Schemes 13.2 Preparing for Tomorrow 13.3 New Mathematical Problems 13.4 New Signatures 13.5 Quantum Cryptography: A Way Out of the Dead End? 13.6 Post-Quantum Cryptography 13.7 Conclusion References Appendix A: Software A.1 CrypTool 1 Menus A.2 CrypTool 2 Templates and the WorkspaceManager A.3 JCrypTool Functions A.4 CrypTool-Online Functions Appendix B Miscellaneous B.1 Movies and Fictional Literature with Relation toCryptography B.1.1 For Grownups and Teenagers B.1.2 For Kids and Teenagers B.1.3 Code for the Light Fiction Books B.2 Recommended Spelling within the CrypTool Book References About the Author Contributors Index