Cryptography

A toy RSA public key is $(n, e) = (33, 3)$, where $33 = 3 \cdot 11$. Encrypt the message $m = 5$: compute $c = m^e \bmod n$.

For the toy key $p = 5$, $q = 11$, $n = 55$ and $e = 3$, find the private exponent $d$ with $0 < d < 40$ and $ed \equiv 1 \pmod{(p - 1)(q - 1)}$.

With the key $n = 55$, $e = 3$, $d = 27$, a ciphertext $c = 13$ arrives. Decrypt it: find $m = c^d \bmod 55$. (Hint: you can check your answer by encrypting it.)

Ama and Bolat use Diffie–Hellman with $p = 29$ and $g = 2$. Ama's secret is $a = 5$, Bolat's is $b = 12$. Ama sends $A = 2^5 \bmod 29 = 3$ and Bolat sends $B = 2^{12} \bmod 29 = 7$. What shared key do they compute?

An attacker knows the public key $(n, e)$ of an RSA user. Which additional pieces of information would let the attacker compute the private exponent $d$ efficiently, with known methods? (Choose all that apply.)

Textbook RSA with $e = 3$ and a 2048-bit modulus $n$ is used to send a 100-bit number $m$, as $c = m^3 \bmod n$. What can an eavesdropper do?

Which Lean statement is a true formalisation of RSA correctness, as proved in the lesson?

Implement pow_mod(b, e, n) by repeated squaring without using Python's three-argument pow: return $b^e \bmod n$. It must handle exponents with hundreds of digits instantly.