9.11 Coursework Sheet 10
Hand in your solutions in the appropriate way by Monday, 08 January 2024, 19:00.
Exercise 3*
Let \(d\) and \(n\) be positive integers. Show that if \(d|n\) then \(\phi(d)|\phi(n)\).
Exercise 4
We will consider Diffie-Hellman key exchange. Alice and Bob have agreed to use the one-way function \(x\mapsto 9^x\) (mod \(17\)) which they will use to set up a key which only they know. Alice chooses the secret number \(5\), and Bob’s secret number is \(7\). Use the rules of modular arithmetic to compute the key from this data, showing your working.
Exercise 5
A discrete log cipher is defined by the function \(x\rightarrow x^e\) where \(e=7\) and \(n=103\). Write down the corresponding decryption function, computing its exponent.
Exercise 6
Alice picks the two prime numbers \(p=31, q=47\) as her secret numbers for an RSA cipher, and publishes the public key \(N,e\) with \(e=11\).
- What is \(N\)?
- Bob wishes to send an enciphered kiss to Alice, so decides to transmit the ASCII code for X (\(88\) in decimal notation) using Alice’s public key cipher. Using the fact that \(88^{11}=88^{8}\times 88^{2}\times 88\) compute \(C\).
- On receiving Bob’s message Alice computes the private key \(d\) in order to decipher it. The number \(f\) is defined by the linear congruence \(11f\equiv 1\) mod \((p-1)\times(q-1)\). Compute \(p-1\), \(q-1\) and solve the congruence to find \(f\).