3
$\begingroup$

Consider the following the following RSA public key $pk = (N, e) = (1457, 1307)$.

(a) Knowing that $187^2 \equiv 1 \pmod {1457}$ find the factorization of $N$.

(b) Given the factorization of $N$ computed above, use the CRT to decrypt the following ciphertext $c = E_{pk}(m) = 3$.

For part a) I am not sure which property of modular arithmetic can be used? I know $187$ has a multiplicative inverse $187$. I also know the Euler function. But I think I am missing how to calculate $\phi$ from this information.

| improve this question | |
$\endgroup$
  • 3
    $\begingroup$ If you know that $x^2 = 1 \pmod N$ that can be rewritten as $x^2 -1 = 0 \pmod N$, on the left hand side of the equation you have a well know identity... Try to rewrite it differently. And then remember what $\equiv 0 \pmod N$ means ... $\endgroup$ – ddddavidee Dec 6 '15 at 10:45
  • 2
    $\begingroup$ additional hint: when you have divisor $u$ of some positive multiple of $N$, $\gcd(u,N)$ will often be a factor of $N$. $\endgroup$ – fgrieu Dec 6 '15 at 16:21
2
$\begingroup$

For part a) of your question: In this case 2 would be the order of 187 in the multiplicative group modulo 1457. This means you could retrieve the factors of 1457 using the formula gcd($187^{2/2}-1$, 1457) and gcd($187^{2/2}+1$, 1457).

Having the factors of 1457, you can compute $\phi$ with ease.

@fgrieu: The calculation is taken from the non-quantum part of Shor's Algorithm. Basically it's the same as what you mentioned in the comments of the question. Thanks for pointing out my mistake. I mixed up some numbers in my gcd calculation...

| improve this answer | |
$\endgroup$
  • $\begingroup$ $\gcd(187^2-1,1457)=1457$, and $\gcd(187^2+1,1457)=1$. $\endgroup$ – fgrieu Dec 8 '15 at 16:32
  • $\begingroup$ My mistake. My answer followed the non-quantum part of Shor's Algorithm for factoring integers. It should be $187^{2/2}$. Yet it still does not work as gcd(186, 1457) is obviously 1. I will delete my answer as it is misleading in this case. $\endgroup$ – Kevin__ Dec 8 '15 at 16:59
  • $\begingroup$ Glad that you got it fixed. The origin of the to the $2/2$ th power evades me, but we can do without it :-) $\endgroup$ – fgrieu Dec 11 '15 at 14:32
  • $\begingroup$ $x^r = 1 \bmod n \rightarrow x^r - 1 = 0 \bmod n \rightarrow (x^{r/2} - 1)(x^{r/2} + 1) = 0 \bmod n$ $\endgroup$ – Kevin__ Dec 11 '15 at 15:38

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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