This document contains a set of problems exploring concepts in symmetric key cryptography such as one-way functions, trapdoor one-way functions, substitution and transposition ciphers, analyzing cipher security, and stream cipher design. Example problems include constructing mathematical examples of one-way and trapdoor one-way functions, distinguishing between substitution and transposition ciphers, analyzing the security of nested encryption schemes, and analyzing the period and linear complexity of stream ciphers.
This document contains a set of problems exploring concepts in symmetric key cryptography such as one-way functions, trapdoor one-way functions, substitution and transposition ciphers, analyzing cipher security, and stream cipher design. Example problems include constructing mathematical examples of one-way and trapdoor one-way functions, distinguishing between substitution and transposition ciphers, analyzing the security of nested encryption schemes, and analyzing the period and linear complexity of stream ciphers.
This document contains a set of problems exploring concepts in symmetric key cryptography such as one-way functions, trapdoor one-way functions, substitution and transposition ciphers, analyzing cipher security, and stream cipher design. Example problems include constructing mathematical examples of one-way and trapdoor one-way functions, distinguishing between substitution and transposition ciphers, analyzing the security of nested encryption schemes, and analyzing the period and linear complexity of stream ciphers.
This document contains a set of problems exploring concepts in symmetric key cryptography such as one-way functions, trapdoor one-way functions, substitution and transposition ciphers, analyzing cipher security, and stream cipher design. Example problems include constructing mathematical examples of one-way and trapdoor one-way functions, distinguishing between substitution and transposition ciphers, analyzing the security of nested encryption schemes, and analyzing the period and linear complexity of stream ciphers.
(Note: This is a set of problems and questions relevant to exploring basic
questions on symmetric key Cryptography. Problems and question in test and exam shall be of similar nature except may be with lesser lengthy answers than required for the present set). 1. Construct as many examples of One Way (OWF) and Trapdoor One Way Functions (TOWF). A mathematical representation of the these is OWF y = F (x) TOWF y = F (k, x) Trapdoor k The input x, output y and trapdoor (key) k are strings over alphabets or just symbols. Properties required to be satisfied by F for OWF and TOWF are discussed in the Introductory notes. The examples should give a relative difficulty and ease of computation in the definition of these functions. (A mechanical analogy of a TOWF is a box with a lock which has two keys. Message x is put in the box by sender and the box is locked. The locked box is denoted by y. The box is delivered to the sender by a trusted courier who does the job of delivering the box faithfully. The receiver has the same key exchanged a priori. It is relatively much difficult to open the box without opening the lock). Which of the following can be considered TOWFs justify giving mathematical arguments. (a) p is large size prime. y = xk mod p. (b) p is large size prime. y = k x mod p. (c) p is large size prime. y = (x + k)−1 mod p. The number x + k 6= 0 mod p. For any number a 6= 0 mod p the inverse b can be found such that ab = 1 mod p. (d) y = k1 x1 + k2 x2 + k3 mod p. (e) How will you build TOWFs using Vigenere, Diana and Rotor ciphers which may be practically useful? Largeness of prime in these problems refers to difficulty of computation in relation to the length of the prime (number of bits in its binary expansion). Hint: Already given. Think of more examples mathematical or from phys- ical sciences.
1 2. A substitution cipher is defined by substituting alphabets uniquely to other alphabets. A transposition cipher is defined by permuting the po- sitions of alphabets in the plaintext. How will you recognise whether a ciphertext is created by substitution or transposition? Hint: Distinguish between monoalphabetic and polyalphabetic transfor- mation of the plaintext due to either substituition or permutation. The frequencies of letters will be unaltered in mono and permutations. 3. If a plaintext stream is given as input to the three rotor cipher and ci- phertext collected from other two rotors alternatively, how will you break this cipher to find plaintext from ciphertext? Hint: Consider two letter frequencies. 4. Develop computational tests to measure the relative OWF and TOWF properties. You can assume that X, Y and K are finite sets defined by strings of bits or finite fields of integers modulo a prime number. Given F (x) or F (k, x) construct computational conditions to define and how to test, computing y given x is easy and computing x given y is difficult. Similarly for the conditions of the TOWF. Hint: You can check the randomness of y as a value of F (x) by either variation in x, small bit change should lead to large bits change. Also check whether probability of a linear expression being satisfied by relations y = F (x) is close to 1/2. Think of more such expaeriments.
5. Think of ways in which you can exchange the key k securely. Banks still exchange the initial (random) PIN numbers of your account login or card securely by creating the sealed double paper slip in a machine. You dont accept an unsealed slip. Hint: Practical issue.
6. Suppose y = F (x) is a relatively practical OWF. How can you construct
a TOWF using F ? Hint: Think. 7. If y = F (k, x) is a practical TOWF. If you construct a new TOWF as follows, z = G((k1 , k2 ), x) = F (k2 , F (k1 , x)) Is G stronger TOWF (more secure) than F ? Justify. Let y = E(k, x) be an encryption function whose decryption function is x = D(k, y). Is the function y = E(k1 , D(k2 , E(k1 , x))) stronger TOWF than E? Hint: Think of storage of all x, y pairs by search over k. Show that effort required to search key from one x, y pair by brite force remains same.
2 8. Construct the TOWF as in the above problem for using E defined by TWOFs of examples in problem 1. Hint: Just use the TOWF of problem 1. 9. Fibbonacci sequences modulo a number. A sequence of numbers an for n = 1, 2, . . . generated by the recurrence an = an−1 + an−2 and initial condition a1 = a2 = 1 is called a Fibonacci sequence. The sequence grows very fast to large numbers hence we can define Fibonacci sequences modulo a number N . Construct Fibonacci sequences modulo primes N = 3, 5, 7, 19, 31, 43 defined by recurrence
an = an−1 + an−2 mod N
with a1 = a2 = 1. Prove that such sequences are ultimately periodic for
any initial condition, i.e. there exits m and a period r such that an+r = an for n > m. For an arbitrary initial condition a1 and a2 in numbers modulo N , find the period r of the sequence. Hint: Straightforward. 10. Determine the linear complexities of the sequences generated by following stream ciphers for different initial loading of registers. Find the periods of these sequences if they are periodic and the index m after which the sequence is periodic.
(a) L[1, 0, 1, 0] with sequence defined by the output function y(k) =
x1 (k) ⊕ x2 (k)x3 (k). (b) Two LFSRs with an output sequence. L1[1, 1, 0, 1], L2[1, 0, 0, 1] with outputs y1 , y2 respectively (the leftmost bit). The output sequence defined by y = y1 ⊕ y2 ⊕ y1 y2 . (c) Two LFSRs as L1, L2 of previous problem with L3[1, 0, 1, 1] with output y3 . Output sequence defined by MSB of the integer y = y1 + y2 + y3 (the integer sum of three outputs). (d) FSR defined by L[1, 1, 0, 1] with recurrence rule x4 = MSB (x0 + x1 + x3 ) which is the ingteger sum.
Hint: set up Hankel matrices and compute maximal ranks.
11. Consider an encryption function y = E(k, x) defined by y = xk mod p where the symmetric key is 0 < k ≤ p − 1 and the gcd (k, p − 1) = 1 i.e. k has no common factor with p − 1. Then show that the decryption function is x = D(l, y) defined by x = y l mod p such that kl = 1 mod p − 1.
(a) Verify the encryption decryption formulas for different primes p.
(b) For a prime p let the set of alphabets be [0, p − 1]. Consider the encryption function E as a block cipher with block length 1 (sin- gle alphabet) denoted as (a1)(a2) . . . (am). For different cases of p,
3 plaintexts P , ciphertexts C, keys k, modes of operations indicated in the table below find the missing items. p P C k Mode IV ,X0 37 (10)(2)(4)(11) ? 15 CBC 2 11 ? (10)(9)(8)(7) 3 CBC 3 31 (21)(7)(9)(11) ? 7 CTR 2 57 ? (2)(11)(3)(3) 3 CTR 2
12. Consider the stream cipher of problem 8(b). Assume the key K = (1, 0, 1, 1) as the initial state of L1 and IV = (1, 1, 0, 1) the initial state of L2. Let the key stream be chosen from k0 = 8. Encryption is as ci = pi ⊕ kk0 +i for i = 0, 1, 2, . . .. Decrypt the sequence 1, 1, 0, 1, 0, 1, 0, 0, 0, 1, 1, 0, 1, 1, 1.
The Quality or State of Agreeing or Corresponding.a Relation Between Two Numbers Indicatin Gthat The Numbers Give The Same Remainder When Divided by Some Given Number. Compare Residue
The Quality or State of Agreeing or Corresponding.a Relation Between Two Numbers Indicatin Gthat The Numbers Give The Same Remainder When Divided by Some Given Number. Compare Residue
