-1
$\begingroup$

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.

$\endgroup$

closed as unclear what you're asking by Maarten Bodewes, yyyyyyy, otus, Biv, Gilles Apr 8 '17 at 20:59

Please clarify your specific problem or add additional details to highlight exactly what you need. As it's currently written, it’s hard to tell exactly what you're asking. See the How to Ask page for help clarifying this question. If this question can be reworded to fit the rules in the help center, please edit the question.

  • 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
1
$\begingroup$

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$.

$\endgroup$

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