TSIT03 Cryptology Exam - Linköpings Universitet - October 25, 2024 PDF

Written exam in TSIT03 Cryptology 14:00–18:00, October 25, 2024 Onur Günlü Institutionen för Systemteknik, Linköpings Universitet Permitted equipment: General-purp...

Written exam in TSIT03 Cryptology 14:00–18:00, October 25, 2024 Onur Günlü Institutionen för Systemteknik, Linköpings Universitet Permitted equipment: General-purpose dictionaries for translations into English with- out personal notes. (Thus, no specific scientific dictionaries with or without formu- las and no other external help.) Solutions: Solutions will be posted on Lisam after the exam. Grading: Minimum points to achieve the grades (3, 4, 5) are (13, 19, 27), respectively, out of total 39 points. We use the university standard translation from numeric to ECTS grades. Examiner Visit: Examiner will come to the examination rooms to answer your ques- tions (around 3pm). Other information: Answers can be in English. Where appropriate, the quality of your explanations will also be used for grading purposes, i.e., a good explanation will not bring fewer points than a bad explanation. Please keep your answers concise. 1. Questions About Lecture 1 (with the title Principles and History) (a) (2 points) Describe an affine cipher and give the number of possible key values for it. Solution: The Affine cipher uses a second key integer j and encrypts using c = jm + k modulo n. Caesar has 26 possible keys, the affine cipher has 312 = 26 · 12 key values. (b) (2 points) What should be the key length of Vigenère cipher for the English language? Give two answers, first as a description in words, and also as a rough estimate in bits. Hint: Consider the number of words in a language. Solution: The key is an English word, so the number of words in the English language. Depending on source, 30-100 000 words, or around 15-16 bits (c) (3 points) How do you break the normal Vigenère? Give a step-by-step precise algorithm. Solution: Obtain the keyword length as the gcd of the distances between the repeated cryptoletter pairs, and then identify the Caesar alphabet (i.e., substitution key) used for each letter by finding reasonable single letter statis- tics. 2. Questions About Lectures 2 and 3 (with the titles Foundations and Basic Theory and Stream ciphers, RNGs) (a) (2 points) ASCII representation of letters in, e.g., English is known to be re- dundant. How do we measure redundancy of a language in written texts? Solution: Measured as the average entropy over long sequences of English text, which is approximately 1 bit/letter. (b) (1 point) Stream ciphers try to imitate some of the good properties of one time padding. How is the main drawback of one time padding (OTP) avoided in a stream cipher? Solution: A short secret key is shared between the users, and this is then expanded using a (publicly known) key expansion procedure. This makes the transmission on the secure channel much shorter than the message length. (c) (1 point) What is perfect secrecy for a cryptosystem? Define it mathematically and explain it in detail. Solution: Such a system has perfect secrecy if H(M |C) = H(M ), where M is the plaintext and C is the ciphertext. (d) (2 points) Real-world pseudo-random number generator outputs are periodic. Give two main reasons for why this is the case. Solution: PRNGs must be deterministic, as the sender and receiver must generate the same key stream. Moreover, real-world number generators must be finite due to complexity. Therefore, they are periodic. 3. Questions About Lecture 4 (with the title Block Ciphers) (a) (4 points) Consider a generic block cipher, which is a generalization of the sub- stitution cipher, that encrypts n-bit blocks, for n ≥ 1. What is the size |K| of the set K that corresponds to the set of all possible keys k ∈ K as a parameter of n? Based on this information, why are generic block ciphers not practical? Hint: Consider the number of possible permutations. Solution: (2n )!, which is huge, so they are not practical to implement due to storage and communication costs. 4. Questions About Lectures 6 and 7 (with the titles Public key principles, one-way functions, RSA & Knapsack, Diffie-Hellman, ElGamal) (a) (3 points) Compare the computational hardness of solving for x, given c, e, and n = pq (where p and q are large prime numbers) in xe = c mod n with the computational hardness of factoring n = pq? Which theorem was used in class to compare their computational hardness and why? Solution: They are equally hard, proved by using the Chinese Remainder Theorem because it provides unique solutions that result in factoring n. (b) (2 points) How do you choose the Rivest–Shamir–Adleman (RSA) parameters p, q, n, e, and d? (no need to consider the factorization methods for this part.) Solution: The parameters p and q are random very large primes, and n = pq. An important number here is φ(n) = (p − 1)(q − 1), and e is chosen so that gcd(e, (p − 1)(q − 1)) = 1. The final parameter d is chosen so that ed = 1 mod (p − 1)(q − 1). (c) (2 points) The knapsack problem is an NP-complete problem, but it is not se- cure. Why? Briefly explain your answer. Solution: The knapsack problem is NP-complete, but (as it turns out) if the knapsack is constructed from a superincreasing one, the problem is much simpler (as another (u, s) pair that maps to another superincreasing knapsack can help in decryption) 5. Questions About Lecture 8 (part on Message authentication and digital signatures) (a) (1 point) What is the technical difference between a Message Authentication Code and a digital signature? Solution: A MAC system is a symmetric-key system, while a digital signa- ture uses an asymmetric-key system. (b) (1 point) What is a “blind signature”?  Solution: A signature created for a message whose content is unknown to the signing part. (c) (2 points) Describe mathematically how a blind signature can be created using RSA. Solution: Bob wants to prove that he has created a document at a certain time, but keep it secret, and Alice agrees to help him. She sets up standard RSA, keeping d for herself. Bob chooses a random integer k, and gives Alice the message t = k e m mod n. The number t is random to Alice, but she signs the message and gives the signature to Bob, where s = td = k ed md = kmd mod n. Bob can now divide by k and retrieve md, Alice’s signature for m. 6. Questions About Lecture 11 (with the title Bit commitment, zero knowledge, secret sharing, games over the phone) (a) (2 points) What is the main difference between bit commitment and zero knowl- edge schemes? Solution: The former uses one-way functions and the latter a random com- mitment and a random challenge. (b) (1 point) Fill in the missing part in “Coin tossing or poker over the phone uses bit (or card) commitment to convince participants that......” Solution: it is a fair game (c) (2 points) Why are digital signatures not zero-knowledge? Solution: There is no random challenge and random commitment in digital signatures. 7. Questions About Lecture 12 (with the title Post-quantum crypto) (a) (2 points) Why is cryptography based on, e.g., lattice problems called “Post- quantum”? Why is RSA not called ”Post-quantum”? Solution: There is no quantum algorithm that solves a lattice problem more efficiently than a classical algorithm. RSA is based on factorization and a quantum computer can factor in polynomial time. (b) (1 point) What does the abbreviation SIS stand for? Solution: Short Integer Solution. (c) (1 point) Define the SIS hash function  Solution: h(x) = Hx (mod q), where q is a prime number, H is a random matrix, and x is a vector. (d) (2 points) Compare Learning with errors (LWE) with McEliece code-based cryp- tography in terms of the source of security and the requirements for the choice of code family. Solution: Security rests on hardness of decoding general linear code for both. Choice of code family is crucial for McEliece security, whereas LWE uses random general linear codes.