Asymmetric Cryptography

Question 1

Distributing secret keys is hard and expensive

Answer 1

Key distribution issues

Question 2

Find y such that b^y mod p = x given x

Answer 2

Discrete log problem

Question 3

$p$, $g < p$ group generator

Answer 3

public parameters of DH

Question 4

1. Pick a from [0, p-1)
2. Pick b from [0, p-1)
3. A -> B: g^a mod p
4. B -> A: g^b mod p
5. k = g^ab mod p

Answer 4

Diffie Hellman protocol

Question 5

Insecure to active eavesdropper

Answer 5

Issues with diffie hellman

Question 6

Can modify transmitted messages during key negotiation to attacker-controlled secret key

Answer 6

Active eavesdropper in DH

Question 7

Cannot do signatures or authentication

Answer 7

Diffie Hellman

Question 8

Can do signatures, asymmetric encryption / decryption, and key exchange

Answer 8

RSA

Question 9

Computing x^y mod N

Answer 9

Easy problem in RSA

Question 10

Inverting elements. Finding x^-1 such that xx^-1 = 1 mod N

Answer 10

Easy problems in RSA

Question 11

Factoring N

Answer 11

Hard problems in RSA

Question 12

Given x^y mod N, compute y such that gcd(y, phi(n)) = 1

Answer 12

Hard problems in RSA

Question 13

Find two large primes $p$ and $q$

Answer 13

RSA key generation step 1

Question 14

Let $n$ = p * q, compute phi(n) = (p - 1)(q - 1)

Answer 14

RSA key generation step 2

Question 15

Choose an e that is relatively prime to phi(n) (gcd(e, phi(n)) = 1)

Answer 15

RSA key generation step 3

Question 16

Public key = <e, n>

Answer 16

RSA key generation step 3

Question 17

Find d = multiplicative inverse of e mod phi(n)

Answer 17

RSA key generation step 4

Question 18

Private key = <d, n>

Answer 18

RSA key generation step 4

Question 19

c = m^e mod n

Answer 19

Encryption in RSA

Question 20

m = c^d mod n

Answer 20

Decryption in RSA

Question 21

s = m^d mod n

Answer 21

Signing in RSA

Question 22

m = s^e mod n

Answer 22

Verification in RSA

Question 23

What keys can be made public

Answer 23

Either the private key or public key can be use interchangably, but MUST be consistently used