Week 15

Question 1

Compute square roots modulo 𝒑, where 𝒑 is 𝒂 prime congruent to 3 modulo 4

For example, find the square roots of 2 in ℤ₇ - what check to perform first?

Answer 1

First, check that 𝒂 is a quadratic residue in ℤ_𝒑 by computing Legendre symbol (𝒂|𝒑) = 𝒂^(𝒑-1)/2

i.e. 2^(7-1)/2 = 8 ≡ 1 (mod 7) [CONFIRM THIS IS CORRECT WORKING] so 2 is a quadratic residue in ℤ₇.

Then use ±𝒂^(p+1)/2

i.e. ±2^(7+1)/2 gives +4 and -4, which are congruent to 4 and 3 (mod 7), respectively.

Thus 4 and 3 are the square roots of 2 in ℤ₇.

Question 2

Prove that for 𝒂 coprime to 𝒑, with 𝒑 congruent to 3 (mod 4), raising 𝒂 to the exponent (𝒑+1)/4 gives a square root of 𝒂

Question 3

Describe the key generation, encryption, and decryption processes for the Rabin encryption scheme

Question 4

Perform encryption and decryption of messages and ciphertexts respectively using the Rabin encryption scheme

Question 5

Appreciate that attacking the One-Way security of the Rabin encryption scheme under chosen plaintext attacks is at least as hard as factoring integers that are the product of two primes that are congruent to 3 modulo 4

Question 6

Describe how to use a chosen ciphertext attack to factor a Rabin encryption key 𝒏