Cryptography

Question 1

goals of crypto?

Answer 1

Confidentiality, Integrity, Composability

Question 2

Kerckhoffs’s Principle

Answer 2

the security of crypto system lies in the secure hex and not the algorithm.

Question 3

On Time Pad

Answer 3

c := m xor k

m

Question 4

Pseudorandom Permutation

Answer 4

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

Question 5

Advanced Encryption with Block Ciphers

Answer 5

• 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

Question 6

AES: Advanced Encryption Standard

Answer 6

4 steps:

1. Octet-for-Octet substitution with fixed Box
2. Rearrangment of Octets with rotation of row/column
3. MixColum; replace 4B columns by another
4. AddRoundKey operation; e.g. xor

Question 7

Electronic Code Book (ECB) Mode

Answer 7

• 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

Question 8

Cipher Block Chaining (CBC) Mode

Answer 8

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

Question 9

Message Authentication Code (MAC)

Answer 9

• 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

Question 10

Hash Functions

Answer 10

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:

1. Collision resistance - Find any m, m’ such that H(m) = H(m’)
2. Preimage resistance - Given H(m) finding m
3. Second preimage resistance - given H(m) and m hard to find m’ so that H(m) = H(m’), m != m’

Question 11

Merkle–Damgård Construction

Answer 11

• 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

Question 12

SHA - 1

Answer 12

• 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

Question 13

Hash + MAC

Answer 13

HMAC(k, m) = H((k’ xor opad) | H((k’ xor ipad) | m))
k’ = padded k
opad = 36 in hexadecimal
ipad = 5C in hexadecimal

Question 14

Diffie-Hellman Key Exchange

Answer 14

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

Question 15

Man-in-the-Middle Attack Against DH

Answer 15

• 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

Question 16

RSA – Encryption and Decryption

Answer 16

• 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

Question 17

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.

Answer 17

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

Question 18

p = 47 and q = 73
sk = (N,d = 2341) and pk = (N,e = 2125)
Encrypt the message m = 1611
Decrypt the ciphertext c = 3430

Answer 18

c = me = 1611^2125 ≡ 3207 (mod N)
m = cd = 3430^2125 ≡ 3430 (mod N)

Question 19

Hybrid Encryption

Answer 19

• public key to exchange private key

- then use private key encryption to communicate

Question 20

RSA – Digital Signatures

Answer 20

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