Cryptography, Cryptology, Cryptanalysis, Crypto
Cryptography: making secret codes
Cryptology: Making and Breaking secret codes
Cryptanalysis: Breaking secret codes
Crypto: all of the above, a black box
Caesar Cipher
- extremely easy to break by shifting 3 letters left, Simple substitution
- mono alphabetic encryption
-classical cipher
-ve: small key space of 25 keys
Hardening Caesar Cipher + 1-ve
- scramble 26 letters into other random permutations: 26!
- encrypt and decrypt with same scrambled key
- not necessarily alphabetic shift
BUT
English letter frequencies unbalanced, DO NOT use substitution ciphers
cipher/cryptosystem, encryption result, decryption result, symmetric key, public key, private key
- cipher: encrypt plaintext
- encryption result: ciphertext
- decryption result: plaintext
- symmetric key: same key to encrypt and decrypt
- public key: to encrypt
- private key: to decrypt
Secure cryptosystem & Broken cryptosystem
- Secure cryptosystem: best attack is brute force, exhaustive key search
- Broken cryptosystem: shortcut attack known without trying all keys
Vigenere Cipher
- letters shifted by values defined by a key, letters that represent numbers based on position in alphabet
eg. A:0, D: 3 - Stronger: longer keyword(less observable pattern in ciphertext, more frequency tables), shorter message(stat analysis not accurate)
- same letter to different letters
- different letters to single letter
- polyalphabetic substitution, more secure, classical cipher
- Not good today
Vigenere Cipher decryption
- Find length of key by looking at intervals between repeated text patterns. Same word encrypted with same shift values
- Key length either whole interval and repeated text or a factor of it
One Time Pad
- perfect encryption
- can only learn length of plaintext
- plaintext, random key and ciphertext all same length
- C = P XOR K
- XOR: instant encryption and decryption, XOR key twice encrypts and decrypts
OTP encryption & decryption
Encryption: Add each letter by cipher until cipher ends then repeat until sequence ends
Decryption: Minus each letter by cipher until cipher ends then repeat until sequence ends
- mod26 for both. A=1, Z=26
One Time Pad properties(3)
- Random
- Used only once
- Known only to sender and receiver
Problems with One Time Pad(5)
- Hard to generate truly random long One Time Pad
- Need to ensure OTP stored securely
- Need to ensure secure encryption and decryption
- Both parties need to sync portions of pad used
- Need to agree on new OTP when old OTP used up or compromised
Randomness
- found everywhere
1. equally likely to get 0 or 1 bit
2. Successive bits independent of each other - non randomness = insecurity
- crypto randomness more strict than random used in RNG and simulations
Errors in identifying randomness
- Mistaking random for not random
- Mistaking non random for random
Birthday paradox
- only need 23 ppl to get >50% where 2 ppl same birthday
-> 364! / 342! x 365^23 = 49.2
-> 100 - 49.2 = 50.8%
Crude Shannon
- founder of Info Theory
1. Confusion: obscure relationship between plaintext and ciphertext
2. Diffusion: spread plaintext statistics through ciphertext - One Time Pad: confusion
- Double Transposition: Diffusion
Symmetric cryptography
- symmetric key: same key to encrypt and decrypt
1. Stream ciphers
2. Block ciphers
- Stream cipher overview
- short key stretched to periodic infinite keystream
- XOR keystream with plaintext bit by bit
eg. GRAIN: NSFR, secure non linear feedback register - most common: Feedback Shift Registers(FSR)
Feedback Shift Registers(FSR)
- LFSR based: initialise k bit seed
- Successive bits: XOR previous bits: si+1 = si-1 XOR si-2
Stream cipher 1 +ve, 1-ve, Solution,
-ve of Solution
+ve: Efficient in hardware
-ve: Speed needed
Solution: fast processors today
-ve: death of linear stream ciphers due to linear lagebra
- Block ciphers
- encrypting more than one block requires padding as NOT all messages same size as block
- AES block
–Key length: Number of rounds
128:10
192:12
256:14
1. Electronic codebook
2. Cipher Block Chaining
3. CTR counter mode
ECB, Electronic codebook overview
- every block of plaintext encrypted independently and identically with same key k
Encryption: C = E(k,P) = Ek(P)
Decryption: P = D(k,C) = Dk(C)
ECB 3 +ve, 5 -ves
+ves:
1. Parallel Encryption
2. Parallel Decryption
3. Random Read
-ves: Ek fixed function for fixed k so Simple Substitution
1. Fixed map for symbols
2. Patterns preserved
3. Repetition seen
4. Frequency found
5. Ciphertext leaks plaintext information
* Same issues facing deterministic cipher with fixed key
CBC, Cipher Block Chaining + 1 -ve
- each block of plaintext XOR with previous block of ciphertext before encrypted using Ek
Encryption: C0 = IV, C i = Ek(P i XOR C i-1)
-ve: No Parallel Encryption
CTR, Counter mode + 2 +ves
- use block cipher as stream cipher
- input to block cipher computes new keystream block
- Plaintext encrypted by XOR with combination of E, key and counter CTR
Encryption: C i = P i XOR Ek(CTR i)
Decryption: P i = C i XOR Ek(CTR i)
+ves:
1. Parallel Encryption
2. Parallel Decryption
