I'm trying to teach myself cryptography and I know that RSA is a large part of this topic and stumbled across the following question which I feel if clarified would help me understand a large part of RSA. If anyone could help I would really appreciate it. The question is as follows:

  1. Alice generates an RSA key pair, and publishes her public key $(N = 221, e = 5).$

(a) Find Alice’s chosen primes p and q.

(b) Find the exponent that Alice uses for decryption, d.

(c) Bob wants to send the message m = 2 to Alice. Find the ciphertext he sends.

(d) Would you consider Bob’s ciphertext to be secure? Say why.

(e) Bob gets the message m = 42 signed with σ = 144 in an e-mail from Alice. Using only her public key, check if Bob should believe Alice sent this message.

  • 1
    $\begingroup$ Some tips: (a) factor $N$ (b) find $e^{-1} \text{ mod } \phi(N)$ ($\phi(N) = (p-1)(q-1)$) (c) encryption is $m^e \text{ mod } N$ (e) verification involves comparing $m$ to $\sigma^e \text{ mod } N$ $\endgroup$ – puzzlepalace Apr 6 '17 at 19:08
  • 6
    $\begingroup$ Please provide some info about what you have tried and what you already know. $\endgroup$ – Elias Apr 6 '17 at 19:14

a. try all primes below $\sqrt{221} < 15$.

b. Compute $\phi(N) = (p-1)(q-1)$ for the primes $p,q$ with $N=pq = 221$. As $e = 5$, you need $d$ such that $5d \equiv 1 \pmod{\phi(N)}$.

c. $m^e \pmod{N}$ in general. Fill in the formula. Do you actually do any modular reduction? That should answer d.

e. To check a signature $s$ on a message $m$, check that $s^e \pmod{N} \equiv m$.

| improve this answer | |

Not the answer you're looking for? Browse other questions tagged or ask your own question.