- Contents
- Classical Encryption Techniques
- Simple-DES
- Block Ciphers
- Pseudo-Random Numbers and Stream Ciphers
- Fundamentals of Number Theory
- Public Key Cryptography
- Cryptographic Hash Functions
- Message Authentication Codes
graph LR
A[Message]-->|Plaintext<br>key|B[Encryption]
B[Encryption]--Ciphertext-->C[Decryption]
C[Decryption]-->|Plaintext<br>key|D[Message]
| Plaintext | Plaintextoriginal message |
| Ciphertext | encrypted or coded message |
| Encryption | convert from plaintext to ciphertext (enciphering) |
| Decryption | restore the plaintext from ciphertext (deciphering) |
| Key | information used in cipher known only to sender/receiver |
| Cipher | a particular algorithm (cryptographic system) |
| Cryptography | study of algorithms used for encryption |
| Cryptanalysis | study of techniques for decryption without knowledge of plaintext |
| Cryptology | areas of cryptography and cryptanalysis |
Alphabet Mod
letter mod a/A 0 b/B 1 c/C 2 d/D 3 e/E 4 f/F 5 g/G 6 h/H 7 i/I 8 j/J 9 k/K 10 l/L 11 m/M 12 n/N 13 o/O 14 p/P 15 q/Q 16 r/R 17 s/S 18 t/T 19 u/U 20 v/V 21 w/W 22 x/X 23 y/Y 24 z/Z 25
Generalized Caesar Cipher formal : $$ \begin{aligned} c=E(k,p)=(p+k)\rm {mod} 26 \ p=D(k,c)=(c−k)\rm {mod} 26 \end{aligned} $$
Initialization :
- Create 5x5 matrix and write keyword (row by row)
- Fill out remainder with alphabet, not repeating any letters
- Special: Treat I and J as same letter
Encryption:
-
Operate on pair of letters (diagram) at a time
-
if diagram with same letters, separate by special letter (e.g.x)
if the total number is odd, add special letter (e.g.x) into the end
-
Plaintext in same row: replace with letters to right Plaintext in same column: replace with letters below Else, replace by letter in same row as it and same column as other plaintext letter
Example :
- Plaintext:hello
- Keyword:thailand
To get key matrix : $$ \begin{matrix} t & h & a & i & l \ n & d & b & c & e \ f & g & k & m & o \ p & q & r & s & u \ v & w & x & y & z \end{matrix} $$ and the pair of plaintext : he lx lo matching ld az eu.
Finally, Ciphertext is ldazeu
- Set of 26 general Caesar ciphers
- Letter in key determines the Caesar cipher to use
Key must be as long as plaintext: repeat a keyword
Example:
- Plain: internettechnologies
- Key:sirindhorn(sirindhorn)
- Cipher:AVKMEQLHKRUPEWYRNWVF
- Plaintext letters written in diagonals over N rows (depth)
- Ciphertext obtained by readingrow-by-row
Example :
- plaintext: technologies
- depth:3
$$ \begin{matrix} t& & & &n & & & &g & & & \ &e & &h & &o & &o & &i & &s \ & &c & & & &l & & & &e & \end{matrix} $$ Finally, the ciphertext : tngehooiscle
- Plaintext letters written inrows
- Ciphertext obtained by reading column-by-column, but re-arranged
- Key determines order of columns to read
Example:
- plaintext: securityandcryptography
- key:315624 matrix : $$ \begin{matrix} 3 & 1 & 5 & 6 & 2 & 4\ s & e & c & u & r & i \ t & y & a & n & d & c\ r & y & p & t & o & g \ r & a & p & h & y \end{matrix} $$ Finally, the ciphertext : eyyardoystrricgcappunth.
-
Input (plaintext) block : 8-bits
-
Output (ciphertext) block : 8-bits
-
Key : 10-bits
-
Rounds : 2
Round keys generated using permutationsand and left shifts
The flowchart of Algorithm :
The flowchart of Key Generation :
The flowchart Encryption Details :
- P10
| Input | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 |
| Output | 3 | 5 | 2 | 7 | 4 | 10 | 1 | 9 | 8 | 6 |
- P8
| Input | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 |
| Output | 6 | 3 | 7 | 4 | 8 | 5 | 10 | 9 |
- P4
| Input | 1 | 2 | 3 | 4 |
| Output | 2 | 4 | 3 | 1 |
- EP(expand and permutation)
| Input | 1 | 2 | 3 | 4 | ||||
| Output | 4 | 1 | 2 | 3 | 2 | 3 | 4 | 1 |
- IP(initial permutation)
| Input | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 |
| Output | 2 | 6 | 3 | 1 | 4 | 8 | 5 | 7 |
-
$\rm{IP^{-1}}$ (inverse of IP) - LS-1(left shift 1 position with Loop)
- LS-2(left shift 2 positions with Loop)
S-DES (and DES) perform substitutions using S-Boxes, which considered as a matrix and used to select row/column.
- 4-bit input:
$\rm{bit_1, bit_2, bit_3,bit_4}$ -
$\rm{bit_1 bit_4}$ specify row(0, 1, 2 or 3 in decimal) -
$\rm{bit_2 bit_3}$ specify column
-
- 2-bit output
| 0 | 1 | 2 | 3 | |
|---|---|---|---|---|
| 0 | 01 | 00 | 11 | 10 |
| 1 | 11 | 10 | 01 | 00 |
| 2 | 00 | 10 | 01 | 11 |
| 3 | 11 | 01 | 11 | 10 |
| 0 | 1 | 2 | 3 | |
|---|---|---|---|---|
| 0 | 00 | 01 | 10 | 11 |
| 1 | 10 | 00 | 01 | 11 |
| 2 | 11 | 00 | 01 | 00 |
| 3 | 10 | 01 | 00 | 11 |
Example
- Plaintext:01110010
- Key:1010000010
- Ciphertext:01110111
Process:
- Key :1010000010
left right key 10100 00010 a key $P_{10}$ 10000 01100 b a LS-1 00001 11000 c(key1) b $P_8$ 1010 0100 d b LS-2 00100 00011 e(key2) d $P_8$ 0100 0011
- Plaintext:01110010
left right round1 plaintext 0111 0010 a plaintext IP 1010 1001 b a right EP 1010 0100 c b$\oplus$key1 0110 0111 c $S_0$ 00 0row 11 3col c $S_1$ 01 1row 11 3col d after $S_0,S_1$ 10 11 e d $P_4$ 01 11 f e $\oplus$a left and joint a right 1101 1001 g SW e and a right 1001 1101 round2 h g right EP 1110 1011 i h$\oplus$ key2 0111 1001 i $S_0$ 10 2row 01 1col i $S_1$ 10 2row 00 0col j after $S_0,S_1$ 10 11 k j $P_4$ 01 11 l k $\oplus$ g left and joint g right1110 1101 m l $IP^{-1}$ 0111 0111 Hence: Ciphertext:01110111
Specifically algorithm and flow chart of S-DES can referred to Section Simple-DES above, in this part we only summary the realization of 64 bits DES.
| S-DES | DES |
|---|---|
| 8-bit blocks | 64-bit blocks |
| 10-bit key: 2 x 8-bit round keys | 56-bit key: 16 x 48-bit round keys |
| IP:8-bits | IP: 64bits |
| F operates on 4bits | F operates on 32bits |
| 2 S-Boxes | 8 S-Boxes |
| 2 rounds | 16 rounds |
S-DES functional expression
-
${\rm ciphertext}={\rm IP}^{-1}(f_{k2}({\rm SW}(f_{k1}({\rm IP}(\rm {plaintext})))))$ -
${\rm plaintext}={\rm IP}^{-1}(f_{k1}({\rm SW}(f_{K2}({\rm IP}(\rm {ciphertext})))))$
Security of S-DES
| Block Ciphers | Stream Ciphers |
|---|---|
| Encrypt a block of plaintext as a whole to produce same sized ciphertext | Encrypts a digital data stream one bit or one byte at a time |
| Typical block sizes are 64or 128 bits | One time pad is example; but practical limitations |
 |
 |
Encrypt one byte at a time by XOR with pseudo-random byte
- n-bit block cipher takes n bit plaintext and produces n bit ciphertext.
- 2n possible different plaintext blocks.
- Encryption must be reversible(decryption possible).
- Each plaintext block must produce unique ciphertext block.
Electronic Code Book
- Each block of 64 plaintext bits is encoded independently using same key.
- Typical applications: secure transmission of single values (e.g. encryption key).
- Problem: with long message, repetition in plaintext may cause repetition in ciphertext.
Cipher Block Chaining Mode
- Input to encryption algorithm is XOR of next 64-bits plaintext and preceding 64-bits ciphertext
- Typical applications: General-purpose block-oriented transmission;authentication
- Initialisation Vector (IV) must be known by sender/receiver, but secret from attacker
- In particular, it must be impossible to predict the IV for any given plaintext;
- For maximum security, IV should be protected against unauthorized changes. E.g., send the IV using ECB encryption.
Cipher Feedback Mode
- Converts block cipher into stream cipher
- No need to pad message to integral number of blocks
- Operate in real-time: each character encrypted and transmitted immediately
- Input processed s bits at a time
- Preceding ciphertext used as input to cipher to produce pseudo-random output
- XOR output with plaintext to produce ciphertext
- Typical applications: General-purpose stream-oriented transmission, authentication
Output Feedback Mode
- Converts block cipher into stream cipher
- OFB has structure of a typical stream cipher
- Distinction from the stream cipher is OFB encrypts a full block at a time; while many stream ciphers encrypt one byte at a time.
- Similar to CFB, except input to encryption algorithm is preceding encryption output
- Typical applications: stream-oriented transmission over noisy channels (e.g. satellite communications)
- Advantage compared to CFB: bit errors do not propagate
- Disadvantage: more vulnerable to message stream modification attack
Counter Mode
- Converts block cipher into stream cipher
- Each block of plaintext XOR with encrypted counter
- Typical applications: General-purpose block-oriented transmission; useful for high speed requirements
- Efficient hardware and software implementations
- Simple and secure
CFB OFB CTR Convert block cipher into stream cipher
In this section we mainly discuss XTS-AES Encryption and decryption of single block
$$
PP=P_j \oplus T \
T=E(i,K_2) \oplus a^j\
CC=E(PP,K_1)\
C_j=T \oplus CC\
$$
$$
CC=C_j \oplus T\
PP=D(CC,K)\
P_j=PP \oplus T\
$$
Proof Decrypted P = Plaintext P $$ \begin{aligned} P_j&=D(CC,K_1) \oplus T\ &=D(E(PP,K_1),K1) \oplus T\quad (CC=E(PP,K_1))\ &=PP \oplus T\ &=T \oplus P_j \oplus T\ &=P_j \ \end{aligned} $$
Randomness
- Uniform distribution: frequency of occurrence of 1’s and 0’s approximately equal
- Independence: no sub-sequence can be inferred from others
0000000000 all no 0000011111 yes 0101010101 independence
- True Random Number Generator
- Non-deterministic source, physical environment
- Detect ionizing radiation events, leaky capacitors, thermal noise from resistors or audio inputs
- Mouse/keyboard activity, I/O operations,interrupts
- Inconvenient, small number of values
- Pseudo Random NumberGenerator
- Deterministic algorithms to calculate numbers in “relatively random”sequence
- Input seed
- Produces continuous stream of random bits
- Pseudo Random Function
- Same as PRNG but produces string of bits of some fixed length
-
$m$ , the modulus,$m >0$ -
$a$ , the multiplier,$0 < a <m$ -
$c$ , the increment,$0 \le c <m$ -
$X_0$ , the seed,$0 \le X_0 <m$
Example
Case 1:
$a = 1, c = 1, m = 100$ Seed:$X_0= 23$
- Generate the pseudo-random number sequence.
- Find the sequence period (how many different numbers in the generated stream).
$X_n ={23,24,25,26....22},\text{period} = 100$ Case 2:
$a = 5, c = 0, m = 32$ Seed:$X_0= 3$
$X_n={3,15,11,23,19,31,27,7},\text{period} = 8$
Parameters:
- p, q: largeprimenumbers such that
$p \equiv q \equiv 3 \pmod4$ $n = p \times q$ -
$s$ , random number relatively prime
Generate sequence of bits,
Use symmetric block ciphers (e.g. AES, DES) to produce pseudo-random bits
Cryptographically secure (one of the strongest) PRNG using Triple DES Parameters:
- Input 1:64-bit representation of the date& time,Dti
- Updated on each number generation.
- Input 2:64-bit seed value,Vi
- Initialized to arbitrary value, being updated.
- Keys:Pair of 56-bitDES keys, K1 andK2
Operation:
- Uses Triple DES three times
Output:
- 64-bitpseudo-random number,Ri
- 64-bitseed value, Vi+1
$\text{EDE}([K_1,K_2],X)$ : sequence encrypt-decrypt-encrypt using two-key triple DES for encryption.
For this section I try to realize a simple project of 256-bit RC4 Encryption, including a simply script written in Python, which supported by @KennardWang.
Two integers, a and b, are relatively prime if
$\text{gcd}(a,b)=1$ If$A = B⋅Q + R$ and$B\not ={}0$ then$\text{gcd}(A,B) = \text{gcd}(B,R)$ > where$Q$ is an integer,$R$ is an integer between$0$ and$B-1$
A program of gcd by bit operation :
int gcd(int a,int b){
if(a==0) return b;
if(b==0) return a;
if (!(a&1) && !(b&1)) return gcd((a>>1),(b>>1))<<1;
else if(!(a&1)) return gcd((a>>1),b);
else if(!(b&1)) return gcd(a,(b>>1));
else return gcd(abs(a-b),min(a,b));
}An integer
where
$p_1 < p_2 < . . . < p_n$ are prime numbers and where each ai is a positive integer. E.g.,$a=45=3^2\times5$
All integers have an additive inverse
$a$ is multiplicative inverse of$b$ if$a \times b \equiv 1 \pmod n$
- Not all integers have a multiplicative inverse
-
$a$ has a multiplicative inverse in$\pmod n$ if$a$ is relatively prime to$n$ - Division:
$a\div b \equiv a \times \text{MultInverse}(b)\pmod n$
E.g.,
$2^{-4}\mod 9=\text{MI}(16) \mod 9=4$
-
Fermat's Theorem (1): if
$p$ is prime and$a$ is a positive integer not divisible by$p$ ,then $$ a^{p-1} \equiv 1 \pmod p $$ -
Fermat's Theorem (2): if
$p$ is prime and$a$ is a positive integer ,then $$ a^p \equiv a \pmod p $$
E.g. $$ 3^5 \mod 5=3,\quad 3^4 \mod 5=1 $$
Euler's Totient Function,
$\varphi(1) =1$ - For prime
$p$ ,$\varphi(p) = p −1$ - For
$a$ relatively prime to$b$ , and$n =ab$ ,$\varphi(n)=\varphi(a)\times \varphi(b)$ - For different primes
$p$ and$q$ , and$n =pq$ ,$\varphi(n)=(p−1)\times (q−1)$
E.g. $$ \varphi(4)=2\quad, \varphi(9)=7 \ \varphi(143)=\varphi(13-1)\times \varphi(11-1) =12\times 10=120\ \varphi(30)=\varphi(5)\times \varphi(6)=4\times 2=8 $$
-
Euler's Theorem (1):For every
$a$ and$n$ that are relatively prime: $$ a^{\varphi(n)} \equiv 1 \pmod n $$ -
Euler's Theorem(2): For positive integers
$a$ and$n$ : $$ a^{\varphi(n)+1} \equiv a \pmod n $$
E.g. $$ \varphi(143)=\varphi(13)\times \varphi(11)=120 \quad 97^{121} \mod 143=97\ \varphi(161)=\varphi(7)\times \varphi(23)=132 \quad 149^{133} \mod 161=149 $$
Logarithms in modular arithmetic (discrete logarithm):
$$
b=a^i \pmod p\
i=\text{dlog}_{a,p}(b)
$$
A unique exponent
- If
$a$ is a primitive root of$p$ then$a$ ,$a_2$ ,$a_3$ ,...,$a_{p−1}$ are distinct$\pmod p$ - Only integers with primitive roots:
$2$ ,$4$ ,$p^\alpha$ ,$2p^\alpha$ where$p$ is any odd prime and$\alpha$ is positive integer
E.g. $$ \text{dlog}{3,7}(5) = x\ \quad 3^x\mod 7 = 5 \Rightarrow x=5\ \text{dlog}{2,7}(4) = x\ \quad 2^x\mod 7 = 4 \Rightarrow x=2\ $$
Find the primitive roots of n=7 as example.
All sequences in Table:
| 1 | 1 | 1 | 1 | 1 | 1 |
| 2 | 4 | 1 | 2 | 4 | 1 |
| 3 | 2 | 6 | 4 | 5 | 1 |
| 4 | 2 | 1 | 4 | 2 | 1 |
| 5 | 4 | 6 | 2 | 3 | 1 |
| 6 | 1 | 6 | 1 | 6 | 1 |
When sequences are of length
Each such integer, 3,5, is called a primitive root of the modulus 7.
Key Generation :
- Choose primes p and q(private, chosen) and calculate n = pq(public, calculated)
- Select
$e$ :$\text{gcd}(\phi(n), e ) = 1,; 1 < e < \phi(n)$ (public, chosen) - Find
$d \equiv e−1(\mod \phi(n))$ (private, calculated)
Key Exchange Algorithm : $$ \begin{aligned} Y_A&=\alpha^{X_A} \mod q \ Y_B&=\alpha^{X_B} \mod q \ K_A&={Y_B}^{X_A} \mod q \ K_A&={Y_A}^{X_B} \mod q \ \end{aligned} $$
Man-in-the-middle-attack (Security of Diffie-Hellman Key Exchange) :
graph LR
A[User A]-->|Y A|X[X Mat A]
X[X Mat A]-->|Y Mat A|B[User B]
graph RL
B[User B]-->|Y B|X[X Mat B]
X[X Mat A]-->|Y Mat B|A[User A]
$$
\begin{aligned}
K_{\text{mat}A}=Y_B^{X_{\text{mat}A}} \mod q\
Y_{\text{mat}A}=\alpha^{X_{\text{matA}}} \mod q\
K_{B}^ =Y_{\text{mat}A}^{X_B} \mod q\\ \\ K_{\text{mat}B}=Y_A^{X_{\text{mat}B}} \mod q\\ Y_{\text{mat}B}=\alpha^{X_{\text{matB}}} \mod q\\ K_{A}^ =Y_{\text{mat}B}^{X_A} \mod q\
\
\begin{cases}
K_{\text{mat}A}=K_{B}^\\ K_{\text{mat}B}=K_{A}^
\end{cases}
\end{aligned}
- Generate large prime
$q$ and generator$g$ of the multiplicative group of the integers modulo q. - Select a random integer
$a$ ,$1 \leq a \leq q−2$ ,$\text{gcd}(a , q) = 1$ , and compute$g^a \mod q$ . - A's Public key is
$(q, g, g^a \mod q)$ ; A's Private key is$a$ .
- Obtain A’s authentic public key
$(q, g,g^a)$ . - Represent the message as integers m in the range
${0,1,\ldots,q−1}$ . - Select a random integer
$k$ ,$1 \leq k \leq q−2$ . - Compute
$\gamma = g^k \mod q$ and$\delta = (m \times (g^a)^k) mod q$ . - Send ciphertext
$c =(\gamma, \delta)$ to A
- Use private key a to compute
$\gamma^{q-1-a} \mod q$ . Note$\gamma^{q-1-a}\equiv\gamma^{-a} \pmod q$ $$ \begin{aligned} \gamma^{q-1-a} \mod q\ &=\gamma^{q-1} \gamma^{-a} \mod q\ &=\gamma^{\varphi(q)} \gamma^{-a}\mod q \ &=\gamma^{\varphi(q)} \mod q \times \gamma^{-a}\mod q\ &=\gamma^{-a}\mod q \end{aligned}
$$
2. Recover m by computing
- Generate a random integer
$X_A$ ,$1<X_A<q-1$ - Compute
$Y_A=\alpha^{X_A} \mod q$ - Private key is
$X_A$ , public key is${q,\alpha,Y_A}$
Signature :
- Choose a random integer
$K$ ,$1 \leq K \leq q-1$ and$\text{gcd(K,q-1)=1}$ ,$K$ is relatively prime to$q-1$ . - Compute
$S_1=\alpha^K \mod q$ (Note this is same as the computation of ElDamal encryption) - Compute
$S_2=K^{-1}(m-X_A S_1)\mod (q-1)$ - The signature consists of the pair
$(S_1,S_2)$
Verification :
$$
\begin{aligned}
V_1=\alpha^m \mod q\
V_2=(Y_A)^{S_1}(S_1)^{S_2}
\end{aligned}
$$
Verify that
Generate public /private key :
- Choose primes
$p$ and$q$ , such that$q$ is a prime factor of$p-1$ . - Choose an integer
$\alpha$ , such that$\alpha^q\equiv 1 \mod p$ .The value$a$ ,$p$, and$q$ comprise a global public key. - Choose a random integer
$s$ with$0<s<q$ . Private key! - Calculate
$v=\alpha^{-s} \mod p$ . Public key!
Signature :
- Choose a random integer r with
$0<r<q$ and compute$x=\alpha^r \mod p$ . - Concatenate the message with
$x$ and hash the result to compute the value$e$ ,$e=H(M||x)$ . - Compute
$y=(r+se) \mod q$ . The signature consists of pair$(e,y)$ .
Verification :
- Compute
$x^`=\alpha^y v^e \mod p$ . - Verify that
$e=H(M||x^`)$