Mathematics: Cryptography Questions and Answers

Question 1: Vigenere` Cipher using Hexadecimal Numbers

Answer All The Questions.

(a) Compute 7³⁰mod 47 without a calculator, showing the details of all calculations.  [3 marks]

(b) Consider a Vigenere` cipher that instead of letters of the English alphabet is applied to hexadecimal numbers, i.e. base-16 numbers represented by one of 16 digits 0, 1, 2, ..., 9, A, B, C, D, E, F.

 

(i)If one denotes by P_ithe i-th digit of the plaintext, by C_i the i-th digit of the ciphertext, and by K_i the i-th digit of the key, write down equations for the encryption and decryption operations,

E(P_i; K_i) = C_i = [2 marks]

D(C_i; K_i) = P_i = [2 marks]

(ii) For P = 30A4BE6 and keyword K = 17E, what is C? [5 marks]

(iii) Explain why a poly-alphabetic cipher, such as this modified Vigenere` cipher, is more resistant against letter frequency analysis than a mono-alphabetic cipher, such as the Caesar cipher. [3 marks]

(iv) Can this modified Vigenere` cipher be used as a one-time pad? If not, then explain, why not. If yes, then explain how. [4 marks]

(c)  Consider a block cipher F that has a block length of n bits with the key of length k bits. Let us assume that both encryption and decryption operations with this block cipher take 1 second each.

• In the worst case scenario, how long would it take an attacker to recover the key (and the original plaintext) by means of a brute force attack against this block cipher? Explain your answer. [3 marks]

• Consider a block cipher DoubleF, which works by successively applying the block cipher F twice, i.e. the plaintext is encrypted using the block cipher F, and then the result is encrypted again using the same method, but possibly with a di erent k-bit key. In the worst case scenario, how long would it take an attacker to recover the full key by means of a brute force attack against the DoubleF block cipher? Explain your answer. [4 marks]
• If an attacked performed an intruder-in-the-middle attack against the DoubleF block cipher, how long would it take them to recover the key, approximately? Explain your answer. [4 marks]

(a) Consider a network of 50 users that are exchanging information with each other using three di erent types of network applications: messaging, file sharing, and video calling. Each of the applications for any user should be able to communicate with the same application for any other network user, e.g. video calling for user 1 with video calling for user 2, but not with messaging or file sharing for user 2.

(i) What is the maximum number of session keys needed to establish user-level  symmetric key security in this network? Provide a brief explanation. [3 marks]

(ii) If an application-level symmetric key security is required for this network (for the 3 applications), what is the maximum number of session keys needed?  Provide a brief explanation. [3 marks]

(b) Suppose two parties, A and B, are using the following scheme to confirm that they both possess the same secret key. A generates a random sequence of bits, which has the same length as the key, then XORs this random sequence with the key, and sends the result over the unsecure channel to B. B XORs the message they have received from A with their own copy of the key (which is supposed to be the same), and sends the result back to A. Finally, A compares the message they have received from B with the original random sequence they generated to determine if the two keys held by A and B are indeed the same. In this scheme, neither of the parties transmits the key over the unsecure channel.

Question 2: Symmetric Key Security and Shift Cipher Generalization

(i) Prove that this scheme works, i.e. that if the keys held by A and B are the same, then A can confirm this, and if the keys are di erent, A will detect this. [5 marks]

(ii) Show how an attacker can discover the secret key by taking advantage of this scheme. [5 marks]

(c) How many bits of security does a 120-bit hash function provide and why? [3 marks]

(d) Consider a generalisation of the shift cipher, where plaintext and ciphertext message are elements of Z₂₆, and the keys are given by pairs 

(a; b), with a; b 2 Z₂₆, and gcd(a; 26) = 1. Encryption of a message M using the key (a; b) works as follows,

To decrypt a ciphertext, the receiver computes aˆ = a -¹Â mod 26, and then recovers the plaintext by computing

(i) Encrypt the message M = 6 using this cipher with the key (7; 4). [3 marks]

(ii) Decrypt the ciphertext C = 3 under this cipher with the key (7; 4). Show the details of your work. [8 marks]

(a) Suppose Alice wants to send to Bob a sequence of encrypted messages, where each of the messages represents some decimal digit, i.e. a number from 0 to 9. Using the encryption function E_Kwith some some key K, Alice converts a sequence of decimal digits M₁, M₂,. . . , M_n 2 Z₁₀ to find the sequence of corresponding ciphertexts C₁, C₂,. . . , C_n 2 Z₁₀, where

For each of the following possible encryption functions,

• E_K(M) = M,

• E_K(M) = K,
• E_K(M) = M + K,
• E_K(M) = M  K,

• E_K(M) = M^K+1,

with M; K E Z₁₀ and all operations performed mod 10, determine whether the function can be used as a valid encryption function. [5 marks]

(b) One popular choice of encryption exponent for RSA algorithm is e = 3, because this makes the encryption very fast. At the same time, it can result in a vulnerability of the algorithm and make it prone to attacks. Suppose, we have an RSA algorithm that has a 128-bit modulus n with encryption exponent e = 3, and it is used to encrypt 32-bit messages. Explain, why this is completely insecure.

Illustrate this vulnerability by finding the plaintext that corresponds to the ciphertext

C = 33698267, when n = 119514971 and e = 3. [8 marks]

(c) Use the fact that

111567²Â = 1 mod 224971;

to factorise the RSA modulus n = 224971. [9 marks]

(d) Consider the following protocol based on on the idea of the Di e-Hellman scheme, which allows users to securely communicate with a server. Using common public parameters, a prime modulus p and the generator g of GF(p) , each party i generates their own private key x_i2 [1; p 1], and computes the corresponding public key X_i = g^xi mod p. To establish a session key, a user U and the server S execute the following protocol (with all operations done mod p)

where N_S and N_U are one-time random nonces generated, respectively, by the server and by the user. After this, the server S computes the following session key

whereas the user U computes the key as

Subsequently, the user and the server exchange information using the key K_{S U} . Show that this protocol is correct in the sense that S and M have the same value [8 marks]