The Math Behin Crypto

**Renk** · 09.11.14, 00:45

Here is a link to a free document (translated from Finnish) explaining the mathematics of cryptography.

It might interest some hardcore geeks around here.

Code:

Contents
1 I INTRODUCTION
3 II NUMBER THEORY: PART 1
3 2.1 Divisibility, Factors, Primes
5 2.2 Representation of Integers in Different Bases
6 2.3 Greatest Common Divisor and Least Common Multiple
11 2.4 Congruence Calculus or Modular Arithmetic
13 2.5 Residue Class Rings and Prime Fields
14 2.6 Basic Arithmetic Operations for Large Integers
14 – Addition and subtraction
14 – Multiplication
16 – Division
18 – Powers
19 – Integral root
21 – Generating a random integer
23 III SOME CLASSICAL CRYPTOSYSTEMS AND
CRYPTANALYSES
23 3.1 AFFINE. CAESAR
24 3.2 HILL. PERMUTATION. AFFINE-HILL. VIGENÈRE
24 3.3 ONE-TIME-PAD
25 3.4 Cryptanalysis
27 IV ALGEBRA: RINGS AND FIELDS
27 4.1 Rings and Fields
28 4.2 Polynomial Rings
32 4.3 Finite Fields
34 V AES
34 5.1 Background
34 5.2 RIJNDAEL
35 5.2.1 Rounds
36 5.2.2 Transforming Bytes (SubBytes)
37 5.2.3 Shifting Rows (ShiftRows)
37 5.2.4 Mixing Columns (MixColumns)
38 5.2.5 Adding Round Keys (AddRoundKey)
38 5.2.6 Expanding the Key
39 5.2.7 A Variant of Decryption
40 5.3 RIJNDAEL’s Cryptanalysis
41 5.4 Operating Modes of AES
i
ii
42 VI PUBLIC-KEY ENCRYPTION
42 6.1 Complexity Theory of Algorithms
44 6.2 Public-Key Cryptosystems
46 6.3 Rise and Fall of Knapsack Cryptosystems
47 6.4 Problems Suitable for Public-Key Encryption
48 VII NUMBER THEORY: PART 2
48 7.1 Euler’s Function and Euler’s Theorem
49 7.2 Order and Discrete Logarithm
52 7.3 Chinese Remainder Theorem
53 7.4 Testing and Generating Primes
57 7.5 Factorization of Integers
59 7.6 Modular Square Root
62 7.7 Strong Random Numbers
63 7.8 Lattices. LLL Algorithm
65 VIII RSA
65 8.1 Defining RSA
66 8.2 Attacks and Defences
69 8.3 Cryptanalysis and Factorization
70 8.4 Obtaining Partial Information about Bits
72 8.5 Attack by LLL Algorithm
74 IX ALGEBRA: GROUPS
74 9.1 Groups
77 9.2 Discrete Logarithm
78 9.3 Elliptic Curves
85 X ELGAMAL. DIFFIE–HELLMAN
85 10.1 Elgamal’s Cryptosystem
86 10.2 Diffie–Hellman Key-Exchange
87 10.3 Cryptosystems Based on Elliptic Curves
88 10.4 XTR
89 XI NTRU
89 11.1 Definition
90 11.1 Encrypting and Decrypting
91 11.3 Setting up the System
92 11.4 Attack Using LLL Algorithm
94 XII HASH FUNCTIONS AND HASHES
94 12.1 Definitions
95 12.2 Birthday Attack
98 12.3 Chaum–van Heijst–Pfitzmann Hash
iii
100 XIII SIGNATURE
100 13.1 Signature System
101 13.2 RSA Signature
101 13.3 Elgamal’s Signature
102 13.4 Birthday Attack Against Signature
103 XIV TRANSFERRING SECRET INFORMATION
103 14.1 Bit-Flipping and Random Choices
105 14.2 Sharing Secrets
106 14.3 Oblivious Data Transfer
107 14.4 Zero-Knowledge Proofs
111 XV QUANTUM CRYPTOLOGY
111 15.1 Quantum Bit
112 15.2 Quantum Registers and Quantum Algorithms
114 15.3 Shor’s Algorithm
116 15.4 Grover’s Search Algorithm
118 15.5 No-Cloning Theorem
119 15.4 Quantum Key-Exchange
122 Appendix: DES
122 A.1 General Information
122 A.2 Defining DES
125 A.3 DES’ Cryptanalysis

math.tut.fi/~ruohonen/MC.pdf