# Week 3 Flashcards

What is Public Key Encryption?

Two keys - one for encryption (public), one for decryption (private).

Can derive public from private, but not the other way around.

Explain m^-1 mod n?

Multiplicative inverse mod n.

Denotes number mâ€™ such that m * mâ€™ = 1 mod n.

m^-1 exists if m and n share no common factors.

How does Diffie-Hellman work?

Uses two public parameters: generator g (often 160 bits long) and prime p (often 1024 bits long).

Two random numbers picked and find:

tA = g^rA mod p, tB = g^rB mod p

Exchange these numbers and key = g^rArB = tB^rA = tA^rB mod p

What are the benefits and drawbacks of Diffie-Hellman?

Benefit: Cannot work out rA and rB from tA and tB.

No keys shared at the start.

Drawback: Additional authentication required.

What is Elgamal?

Diffie-Hellman as a public key scheme, with fixed g and p.

rA picked as private key, tA = g^rA mod p as public key.

Message encrypted by choosing rB and sending (g^rB mod p, M * tA^rB mod p).

What is RSA?

Public key system, which carefully generates e, d and n.

n is the product of two large primes, have (m^e)^d = m mod n for every m.

Public key is (e,n) and private key is (d,n).

How does encryption and decryption work in RSA?

Encrypt m: c = m^e mod n

Decrypt c: m = c^d mod n

Security depends on difficulty of finding prime factors of n.

How does Public Key Crypto work?

Ekp(KS), {M}ks

Make new symmetric key.

Encrypt that with the public key.

Encrypt message with the symmetric key.

Explain signatures?

Using RSA: Epub(Dpriv(M)) = M

Sign message with private key, can be verified with public key.

What is a hash?

Short string generated from a message.

Any small change makes hash different.

What are hashes used for?

Verification of message download.

Tying parts of a message together.

Signatures.

Protect passwords.

What is a Preimage attack?

Find a message with a given hash - very hard.

What is a Collision attack?

Finding two messages with the same hash.

What is a Prefix Collision attack?

Attacker picks a message prefix?

Name an attack on MAC?

Add data without knowing key.