7. Cryptography: asymmetric encryption

Question 1

What is a generator?

Answer 1

If p is prime, g is a generator and x is any integer g^x mod p is equally likely to be any number between 0 and p-1

Question 2

What does Z_p (integers subscript p) mean?

Answer 2

integers mod p, i.e 0 … p - 1

Question 3

What does TTP stand for?

Answer 3

Online Trusted Third Party

Question 4

How does TTP work?

Answer 4

Question 5

What are the components of a public-key encryption algorithm?

Answer 5

Question 6

What is the Euler function?

Answer 6

Question 7

What is phi(p) where phi is the Euler function and p is a prime number?

Answer 7

p - 1

Question 8

What is phi(pq) where phi is the Euler function and p, q are prime numbers?

Answer 8

(p - 1)(q - 1)

Question 9

What is Z_n star (Z subscript n superscript star)

Answer 9

Question 10

What is eulers theorem?

Answer 10

Question 11

What are the 4 intractable problems (for this course)?

Answer 11

• Factoring
• RSAP
• Discrete Log
• DHP

Question 12

What is the factoring problem?

Answer 12

Question 13

What is the RSAP problem?

Answer 13

Question 14

What is the discrete log problem?

Answer 14

Question 15

What is the DHP problem?

Answer 15

Question 16

What is the public key for ElGamel?

Answer 16

g^d (mod p)

Where p is a prime, g is a generator for p and d is random between 1 and p - 2

Question 17

What is the private key for ElGamel?

Answer 17

d

Where d is a random value between 1 and p - 2

Question 18

How do you encrypt with ElGamel?

Answer 18

E(pk, m) = (g^r mod p, m * (g^d) ^r mod p)

Where r is a random integer, g^d mod p is the public key and m is the message

Question 19

How do you decrypt with ElGamel?

Answer 19

D(sk, x) = e^-d * c

Where x is the cipher text, x = (e, c) and d is the secret key

Question 20

Show the ElGamel is consistent

Answer 20

Note that x should be m