Public Key Cryptosystems, Digital Signatures, and Key Exchange Algos

Question 1

What are the drawbacks of private key cryptosystems

Answer 1

They only offer confidentiality and no other security goals
Have to trust sender and receiver to keep key secret
Requires n(n-1)/2 keys for n nodes and 1-1 communication

Question 2

Describe public key cryptosystems (as a concept)

Answer 2

• There are 2 keys, one for encryption and another for decryption
• Also known as aymmetric key encryption or double key encryption
• PT is encrypted using public keys and decrypted using private keys

Question 3

Describe the steps in the RSA algorithm

Answer 3

• Choose two large prime numbers p and q
• find the product n = pq
• choose an integer e that is less than n and relatively prime to (p-1)(q-1)
• Find integer d such that e*dmod(p-1)(q-1) = 1

Public key: e,n
Private key: d, n

Encryption formula: c = m^emodn
Decryption formula: m = d^dmodn

Question 4

How is RSA secure?

Answer 4

• The only way for the hacker to get d is by factoring n into p and q
• Factoring large prime numbers is computationally intractable

Question 5

What is the concept of a digital signature?

Answer 5

Digital signature = Decrypt(Public key, Encrypt(Private key, M))

Question 6

What security goals do digital signatures provide in combination with a public key cryptosystem?

Answer 6

Authentication, Integrity, non-repudiation, confidentiality

Question 7

Describe the digital signature process

Answer 7

• A hash function takes a variable length message and generates a small fixed sized message called the message digest
• MD-> M is computationally infeasible

Alice can decrypt the message using her private key, and “decrypt” the digital signature using Bob’s public key. She can then hash the unencrypted message to see if it matches the hashed message included as the digital signature.

Question 8

What is certification?

Answer 8

• The concept of digital signatures can be extended to provide certification
• A certificate is like a drivers license, it is assigned by a third party called the Certificate Authority (CA)

Question 9

Describe the creation of a server certificate, and the validation of a server certificate

Answer 9

Creation:
- Server info is hashed and encrypted using a CA private key
Validation:
- When a site is trying to validate a server certificate, it can hash the server info, then decrypt the EMD from the site using the CA public key. If the two MD’s match, then the certificate is valid

Question 10

Describe the steps in a 3-way handshake

Answer 10

• Client (C) sends a connect request encrypted with the public key of the server (C)
• X sends challenge1 encrypted with the public key of C
• C decrypts challenger 1 and sends it back to X. It also sends challenge 2 to X
• X decrypts challenge 1 and thus authenticates C, X decrypts challenger 2 and sends it back to C. It also sends the secret session key sk
• C decrypts the challenge 2 and thus authenticates X. The rest of the data in the session is encrypted with sk (private key encryption)

Question 11

Describe the steps in a trusted third party key exchange

Answer 11

Involves client A and B, and trusted server S

• A sends connect request to S identifying itself and B
• S sends a two part message to A, k = secret session key, T = timestamp, L = lifetime of the session
• A decrypts second part and gets KTL, it sends a two part message to B
• B decrypts section part and gets KTL, Uses K to decrypt the first part, Verifies T and L, Thus A is authenticated
• B sends TLA encrypted with K and decrypts it and thus authenticates B
• To prevent replay attacks, the reply from B must be different (TLA and not TLB)

Question 12

What is the Diffie-Hellman Exchange?

Answer 12

A key exchange algorithm that predates public key encryption

- Designed for use when two parties want to exchange a secret message in a hostile environment

Question 13

Describe the diffie-hellman exchange algorithm

Answer 13

• Alice sends two numbers, p and g to Bob
• Alice picks a secret number SA, Bob picks a secret number SB
• Alice computes TA = g^sa mod p and Bob computes TB = g^sb mod p
• TA and TB are exchanged
• Alice computes TB^sa modp and Bob computes TA^sb mod p
• – thus they arrive at the same number – the secret key!!

Question 14

What is a hash function?

Answer 14

Basically, a hash function takes a variable length message as input and generates a small, fixed length block as output. This output is the fingerprint of the input message.

Hash functions chosen to generate MDs are mathematical one-way functions. This means it must not be computationally feasible to determine which M generated a given MD.

Question 15

What are the requirements of a good hash function?

Answer 15

A hash function h = H(x) should satisfy the following properties:

• H(x) should be applicable to any size message x
• the output should be a fixed-length
• Should be easy to compute
• x = H’(h) must be computationally infeasible
• The hacker must not be able to produce another message that gives the same message digest (collision resistance)

Question 16

What is collision resistance?

Answer 16

It must be computationally infeasible for the hacker to generate two messages that generate the same MD

Question 17

What should be the minimum length of MD to make it infeasible for the hacker?

Answer 17

Choose m (length of MD) so that 2^m/2 is a large number. m = 128 bits or 256 bits

Question 18

Describe the hash algorithm Simple XOR with rotate

Answer 18

• Divide the data block into n-bit sub-blocks, where n is the size of the message digest
• Initially, set the n-bit hash value to zero
• Process each successive n-bit sub block of data as follows:
• • Rotate the current hash value to the left by one bit
• • The final n-bit hash value is the message digest
• The final n-bit hash value is the message digest