goals of crypto?
Confidentiality, Integrity, Composability
Kerckhoffs’s Principle
the security of crypto system lies in the secure hex and not the algorithm.
On Time Pad
c := m xor k
m
Pseudorandom Permutation
is a function that takes a key k and a message m of length n and holds the following:
- output is exactly n long
- output should look random
Advanced Encryption with Block Ciphers
- separate long text in several smaller blocks
- ciphertext shouldn’t be longer than plaintext
- decryption efficient (comparable to encryption)
- patterns of plain text not visible in cipher
- same key user several times
AES: Advanced Encryption Standard
4 steps:
- Octet-for-Octet substitution with fixed Box
- Rearrangment of Octets with rotation of row/column
- MixColum; replace 4B columns by another
- AddRoundKey operation; e.g. xor
Electronic Code Book (ECB) Mode
- separate text into blocks -> then use on each block same encryption function with same key
cons: - twice same block will result in same cipher output
- attacker can modify single blocks without rest affected (harder detection)
Encryption parallelizable: Yes
Decryption parallelizable: Yes
Cipher Block Chaining (CBC) Mode
c_i = F_k(m_i xor c_i-1)
->also: uses cipher block from before and xor’s it with input block before putting into encryption function; first uses Initialization Vector (IV)
m_i = c_i-1 xor F_k^-1(c_i)
-> also: uses on deception function on cipher then uses from previous block cipher and xor to get plain text; first uses IV
pros:
- some input block not same output twice
- bit flip affects whole message
Encryption parallelizable: No
Decryption parallelizable: Yes
Message Authentication Code (MAC)
- both have a secret key
- > send message and then add message encrypted with secret key
- > reciter can with a secret key verify if m correct
Hash Functions
H(m); m = message
hold following:
1. Compression - Output has fixed length
2. Collision resistant - hard to find m and m’ so that H(m)=H’(m)
3. one way - impossible for random m to finding m from H(m) (exception: trying all possibilities)
quality criteria:
- Collision resistance - Find any m, m’ such that H(m) = H(m’)
- Preimage resistance - Given H(m) finding m
- Second preimage resistance - given H(m) and m hard to find m’ so that H(m) = H(m’), m != m’
Merkle–Damgård Construction
- separate m into blocks w_0 … w_n
- have an IV
take IV and w_0 and put into a function
take above output and w_1 and put into a function
do this till last word and have the hash
SHA - 1
- need at least 512 bit block; if not pading with 1x’1’ and rest ‘0’
- separate into 80 words
- have IV
- put each word into compression function and rotate inside with each w
Hash + MAC
HMAC(k, m) = H((k’ xor opad) | H((k’ xor ipad) | m))
k’ = padded k
opad = 36 in hexadecimal
ipad = 5C in hexadecimal
Diffie-Hellman Key Exchange
X=g^x mod p
Y=g^y mod p
K(ey) = Y^x mod p = X^y mod p
publicly agree on g and p
choose secretly big x and y
calculate key and encrypt, decrypt
Man-in-the-Middle Attack Against DH
- intercept X and Y from both parties
- send both different Y’ and X’, so when the key is computed attacker know from x and y the key
- can now decrypt all incoming texts since he has both keys
RSA – Encryption and Decryption
- Public key is number pair (e, n)
- Private key is number pair (d, n)
en- & decryption via modular arithmetic:
m(essage) < n
c = m^e mod n m = c^d mod n
two large primes p and q
n = p * q; z =φ(n) = (p-1)*(q-1)
choose e < z -> no commentary factor with z
find d so that ed-1 exactly divisible by z
p=47 and q=73
e = 425
Show that e is a valid choice for a public RSA exponent and compute the corresponding private exponent d.
we want to show: gcd(e, φ(p · q)) = gcd(425, (47 − 1) · (73 − 1)) = gcd(425, 3312) = 1
3312 = 7·425+337 425 = 1·337+88 337 = 3·88+73 88 = 1·73+15 73 = 4·15+13 15 = 1·13+2 13 = 6·2+1 so gcd(e, φ(p · q)) = 1
1 = 13 − 6 · 2 = 13 − 6 · (15 − 1 · 13)
= 7 · 13 − 6 · 15 = 7 · (73 − 4 · 15) − 6 · 15
= 7 · 73 − 34 · 15 = 7 · 73 − 34 · (88 − 1 · 73)
= 41·73−34·88 = 41·(337−3·88)−34·88
= 41·337−157·88 = 41·337−157·(425−1·337)
= 198·337−157·425 = 198·(3312−7·425)−157·425
= 198·3312−1543·425
So, (−1543) · 425 = 1 mod 3312
d=(−1543)=1769 mod 3312
p = 47 and q = 73
sk = (N,d = 2341) and pk = (N,e = 2125)
Encrypt the message m = 1611
Decrypt the ciphertext c = 3430
c = me = 1611^2125 ≡ 3207 (mod N) m = cd = 3430^2125 ≡ 3430 (mod N)
Hybrid Encryption
- public key to exchange private key
- then use private key encryption to communicate
RSA – Digital Signatures
a to b: m, sig = (H(m))^d mod n
b can test via: H(m) = ? = sig^e mod n
e = public key alice d = private key alice
