1. $f(x)= y^x\:mod\:p$ is a one way function. Assume an attacker knows the value of $f(x)$ and he guesses a value of $x$. What is the probability that the guess is correct? Explain your answer.

The probability is $\frac{1}{(p-1)}$. Modular exponentiation is a one-way function iff $y$ is the primitive root $mod\:p$. In that case, $k$ is distributed uniformly in the range $[1, p-1]$, hence our answer is one of $p-1$ possible results.

2. Explain why look up table attack is more efficient than brute force or dictionary attack.

Look-Up table attacks, like dictionary attacks, use common words and phrases to guess the password, which is much more likely to yield the correct result faster than the inefficient brute force approach of checking every possible password. However, lookup tables contain precomputed hashes, so they are also more efficient than dictionary attacks, which calculate the hash of each password before guessing.

3. Explain the difference between the biometric authentication and the password-based authentication.

Unlike password authentication, there are probabilities associated with biometric authentication – i.e. there can be false positives and false negatives. As the sensitivity of the biometric authentication method increases, the false negative rate will increase and the false positive rate will decrease.

4. Explain what Steganography is and the advantage of steganography over encryption.

Steganography is a means of hiding an encrypted message such that it does not appear suspicious (e.g. LSB steganography with an image). This allows the message to remain unsuspicious, unlike traditional encryption for which it is often obvious that a message has been encrypted.

5. Explain the flaw of the monoalphabetic substitution

Monoalphabetic substitution always maps the a given letter in the plaintext to the same ciphertext letter. This makes it vulnerable to frequency analysis, since the distribution of each plaintext character will carry over to the associated ciphertext character.

6. Management of an encryption scheme must be feasible and cost-effective. Give an example of an encryption scheme that is very secure in theory, but is not cost-effective and hence not applicable in practice. Explain why the encryption scheme you give is the case.

(Not sure)

7. Is 17 the primitive root of 5? Show your reasoning.

17 is the primitive root of 5 since successive exponents of 17 loop all numbers in the range $[1, 4]$:

17 mod 5 = 2
17^2 mod 5 = 4
17^3 mod 5 = 3
17^4 mod 5 = 1
17^5 mod 5 = 2

8. Discuss the advantages and disadvantages of the public key cryptography and the secret key cryptography.

Secret key encryption is fast (e.g. DES is 3-4 orders of magnitude faster than RSA), but its security is highly dependent on the safety of the key transfer, which can require a lot of effort. Public Key encryption allows for easy key distribution, but its strength relies on the key length and is slower.

9. Similar to digital signature, Message Authentication Code (MAC) can also guarantee the message integrity. Discuss the advantages and disadvantages of MAC, with digital signature.

MAC verifies the integrity of the message while being much less computationally expensive. However, the key is shared by more than one party so we don’t have authentication or non-repudiation, unlike Digital Signatures, which do as the private key used to encrypt the message is only known by a single party.

10. A Virtual Machine (VM) is transient in a physical machine. Namely, a VM is switched on only when it is needed. Discuss the positive and negative impacts that the transience feature has on the security of virtualized systems.

The transience of VMs mitigates security risks as only an active machine can be infected. However, once infected, the VM may turn off, making it more difficult to identify and eradicate infections. This may make it easier for viruses to persist undetected for long periods of time.

11.

12. Alice creates an RSA public key pair. She chooses $p=37$ and $q=61$ as the two prime numbers to generate the public key and $29$ as the other publicly-known value $e$.

i) What is the value of the public key? Show your workings.

The private key $d$ is the multiplicative inverse of $e\:\:mod\:(p - 1)(q - 1)$

e mod (p - 1)(q - 1) 
= 29 mod (36 * 60) = 29
=> d = 1/29 

13.

(a) Assume the following is the cipher text generated by the Vigenere cipher. Work out the possible length of the encryption key. Note that the punctuation marks are not encrypted.

(b) PGP (Pretty Good Privacy) uses both shared-key encryption and public-key encryption when encrypting a message. Explain what is encrypted by shared-key encryption and what is encrypted by public-key encryption in PGP. Also discuss why both types of encryption are used.

Shared-key encryption (i.e. secret key encryption) is the use of a single shared key to both encrypt and decrypt a message. Key-generation is fast, but secure key exchange is difficult. Hence, PGP uses public-key encryption to encrypt and transfer a secret key, which is then used to perform secret key encryption for the remainder of the communication.

(c) In the web of trust authentication, a user can create its own certificate. There are two attributes in the certificate: validity and trust.

(c)(i) Assume user A signs user B’s certificate and sets both validity and trust in B’s certificate to be “full”. Also assume that user B signs user C’s certificate and sets validity in C’s certificate to be “full” and trust to be “marginal”. Should user A trust C?

C’s certificate has been signed by 1 user in whom A has full trust and the distance between the users is 2 (which is within any reasonable threshold), so A should trust C.

(c)(ii) Assume user A signs user B’s certificate and sets validity in B’s certificate to be “full” and trust to be “marginal”. Also assume that user B signs user C’s certificate and sets both validity and trust of C’s certificate to be “full”. Then should user A trust C?

We require at least 1 user with full trust to sign C’s certificate, or n users with (at least) marginal trust. N is determined by the specific web of trust model, but assuming this is higher than 1, A should not trust C.