Theory Homework Assignment 1 Solution

Description

[30] 1. Please answer the following questions.

5. (a) List and briefly define categories of passive and active security attacks.

5. (b) List and briefly define the basic security requirements in computer and network security.

5. (c) Describe the Kerckhoffs Principles.

5. (d) Describe the functions of confusion and diffusion in symmetric ciphers.

5. (e) Describe the Strict Avalanche Conditions in symmetric ciphers.

5. (f) Describe the key management problem in conventional cryptosystems.

[5] 2. A fundamental cryptographic principle states that all messages must have redundancy. But we also know that redundancy helps an intruder tell if a guessed key is correct. Consider two forms of redundancy. First, the initial n bits of the plaintext contain a known pattern. Second, the final n bits of the message contain a hash over the message. From a security point of view, are these two equivalent? Discuss your answer.

[5] 3. Suppose that a message has been encrypted using DES in ciphertext block chaining mode. One bit of ciphertext in block C_i is accidentally transformed from a 0 to a 1 during transmission. How much plaintext will be garbled as a result?

[10] 4. The following is a ciphertext with Caesar Cipher, please analyze it, and give the corresponding plaintext and the used key.

DRO MSDI LBSWC GSDR CEWWOB’C NOVSQRDC, GSDR MYVYBPEV ZBYNEMO SX DRO WKBUOD CDKXNC KXN RKGKSSKX WECSM CZSVVSXQ YXDY LOKMROC.

[6] 5. Please complete the following two tables, and describe why Z₁₁ and Z₁₁ are abelian groups.

						0	1	2	3	4	5		6		7	8	9	10
				0
				1
				2
				3
	ݕ			4
				5
				6
				7
				8
				9
				10

			1					1	2	3		4		5		6	7	8	9	10
					2
					3
					4
		ݕ			5
					6
					7
					8
					9
					10

[6] 6. Prove the following:

3. (a) [(a mod n) + (b mod n)] mod n = (a + b) mod n

3. (b) [(a mod n) (b mod n)] mod n = (a b) mod n

[12] 7. Prove the following:

[4] (a) Prove the One-time padding is provably secure.

[4] (b) Prove the Fermat’s Little Theorem a^{p 1} 1 mod p, where p is prime and gcd(a; p) = 1.

4. (c) Prove that there are infinitely many primes.

[6] 8. Using the extended Euclidean algorithm, find the multiplicative inverse of

3. (a) 1234 mod 4321

3. (b) 550 mod 1769

[20] 9. Suppose Alice and Bob share the common modulus n = p q = 35263, but have different public-private key pairs (e₁ = 17; d₁) and (e₂ = 23; d₂). If David wants to send a message M to Alice and Bob, he first computes the cipher text C₁ = M^e1 mod n for Alice, the value of C₁ is 28657, and also computes the cipher text C₂ = M^e2 mod n for Bob, the value of C₂ is 22520. Finally, David sends (C₁; C₂) to Alice and Bob, respectively. Now, suppose a passive adversary A eavesdrops the ciphertexts

(C₁; C₂). Can the adversary A recover message M just from (C₁; C₂) and the public keys (n; e₁; e₂)? If the adversary A can, please show what strategy that the adversary A would apply, and give the value of message M as well.

3