L18 - Public Key Cryptography

Question 1

What does Public Key Cryptography enable?

Answer 1

The secure transmission of data over unsecured networks.

Question 2

What issue with Symmetric Key Cryptography did Public Cryptography solve?

Answer 2

The issue of sharing an encryption key. For example, in Symmetric, all parties need to know a mutual shared secret. However, it’s hard to send all parties this secret whilst maintaining confidentiality.

Question 3

Explain the Diffie Hellman Key Exchange…

Answer 3

• An asymmetric algorithm to securely exchange information publicly to obtain a shared secret.
• More specifically, key exchange in symmetric cryptography
• No third party can feasibly deduce the shared secret

Question 4

Give the steps of the DHE…

Answer 4

1. Alice and Bob choose a unique private variable each (A,B) as well as a public variable (G) and a public function (F).
2. Alice and Bob operate the public function and public variable on their private variables { F(AG), F(BG) } to create new variables to be sent { AG, BG }.
3. Send new variables over public network
   
   1. Alice sends AG to Bob
   2. Bob sends BG to Alice
   3. Attacker can’t deduce since variables in public space are G, AG, BG → No combination of these variables in the public space can create the final secret key (seen below).
4. Alice and Bob operate their private variables onto the new received variables resulting in them both having the same value
   
   1. Alice received BG → Becomes ABG
   2. Bob received AG → Becomes ABG

Question 5

What is a One Way Function?

Answer 5

A function that is easy to compute, but extremely hard to reverse compute.

Question 6

What are 2 well known 1-way functions?

Answer 6

1. Multiplication of 2 prime numbers - considered a one-way function due to the difficulty of factoring the product if it’s extremely big.
2. Modulo exponentiation - Given a number a and prime number n, the below function is considered one-way

F(b) = a^b mod N

Question 7

What are the assumptions that the RSA algorithm is based on?

Answer 7

• Based on Diffie Hellman Exchange
• No secure channel exists
• Encryption algorithm is known to everyone without compromise to security.
• Public key is known to everyone

Question 8

What are the 3 steps of the RSA algorithm…

Answer 8

1. Generate a public key
2. Generate a private key
3. Perform encryption and decryption

Question 9

Explain how a public key is generated in RSA…

Answer 9

1. Choose 2 large prime numbers P and Q
2. Generate N → N = PQ
3. Choose and E such that…
   
   1. 1 < E < (p-1)(q-1)
   2. E and (p-1)(q-1) are co-primes → Only mutual divisor is 1.
4. Public key is (N,E) and can be published.

Question 10

Explain how a private key is generated in RSA…

Answer 10

• Calculate D via the multiplicative inverse of E
• ED mod (p-1)(q-1) = 1
• D = E^-1 mod (p-1)(q-1)
• (D,N) if the private key

Question 11

Explain how encryption and decryption is performed in RSA…

Answer 11

• To encrypt CipherText = (PlainText^E ) mod N
• To decrypt PlainText = (CipherText^D) mod N