Paper, Order, or Assignment Requirements

Could you please answer the following questions. It will be better if you could refer to this book “Understanding Cryptography” by Christof Paar & Jan Pelzl.

Q1 – Carry out the steps of the RSA scheme as follows. The two primes to be used for the modulus N are p = 5 and 1 = 7.

• What is φ (N)?
• What is the smallest encryption key e that will work?
• What is the corresponding decryption key d?
• Encrypt the message x = 12 using your smallest encryption key?
• Decrypt the resulting ciphertext using your decryption key, that thus checking your results.
• What are the main properties required of good cryptographic hash functions?
• Explain what is the birthday attach on cryptographic hashes?
• Up to a multiplicative constant, about how many candidate values need to be tried before a collision is found for an n-bit cryptographic hash function?
• Briefly explain the difference between a hash and a MAC?

Q2 – How  many possible keys are there for monoalphabetic substitution cipher over and alphabet with 10 letters if the ciphertext alphabet is a permutation of the plaintext alphabet?  Why is it important for the cipher to have a large number of potential keys?

Q3 – In  an alphabet with k letters, how many possible monoalphabetic substitution ciphers are there? How can such a cipher be cryptanalyzed?

Q4 – Consider a  block cipher that uses k-bit keys and operates on n-bit blocks (n > k). You  have intercepted a block of ciphertext encrypted with this cipher.

• Assume that encrypting one n-bit block of plaintext takes 1-time unit (t.u.). Using a brute force attack, how long will you need to fined the plaintext with probability 50%? Briefly justify your response. What happens if the block size doubles from n to 2n?
• Assume that every plaintext block that is sent starts with a fixed 10-bit pattern that is known to both sender and receiver, but not to you (n > 10). The receive checks this 10-bit pattern to make sure that the plaintext has not been tampered with.
  • If you modify 1 bit in the intercepted ciphertext, what is the probability that the receiver will not realise that it was tampered with?
  • If you want to have a 50% probability of passing the integrity check with a fake ciphertext, how many fake ciphertext do you need to send?
    

Q5 – A banking application uses AES128 in CTR mode to encrypt messages of the form <fromAccount, toAccount, amount> with the meaning that amount pounds should be transferred from account number fromAccount to account number  toAccount. Each of the three parts of the message is 16 bytes long. The attacker has an account in this bank. For a particular message that he has been able to intercept, he happens to know the destination account number toAccount. Analyse the encryption scheme to determine whether (and how) the attacker can appropriately modify the intercepted message in order to redirect the money to his own account.

Q6 – Show how the sender of the message can use RSA by itself (i.e. without hashing) to digitally sign a message M. Assume the sender’s private key is d, and the RSA modulus is n. Calculate the signatures for M = 3, d = 5, n = 77.

Q7 – A function is multiplicatively homomorphic if the following is true: if M1 and M2 are two inputs with corresponding outputs C1 = f(M1) and C2 = f(M2), then the output f(M1xM2) for the product M1 x M2 is the product C1 x C2.

• Show that RSA signing, as above, is multiplicatively homomorphic?
• How can this property of RSA signing be used to break the security of signatures? What can be done to strengthen the scheme?