1
$\begingroup$

I have the homework to find to the public key (120, 3) the private key. I guess 120 is n and 3 will be e. So that $\lfloor\sqrt{120}\rfloor=10$ I can't find a matching prime number. So it gets more complicated. I also know $\phi(n)=(p-1)(q-1)$ and $3\cdot d\equiv 1\mod (p-1)(q-1)$ But here I stuck, could somebody help me from this point on?

$\endgroup$
  • 2
    $\begingroup$ $120=2^3\cdot 3\cdot 5$ so this is indeed multi-prime RSA. $\endgroup$ – SEJPM Sep 22 '18 at 15:56
  • $\begingroup$ so do I need to compute $\phi(n)=(2-1)^3\cdot(3-1)\cdot(5-1)$ and then $3\cdot d\equiv 1\mod 8$ with $d = e = 3$? $\endgroup$ – baxbear Sep 22 '18 at 15:59
  • $\begingroup$ does multi-prime RSA make any sense in practical use? $\endgroup$ – baxbear Sep 22 '18 at 16:01
  • $\begingroup$ Multi prime RSA can be usefull as long as you keep all primes large. I read a while ago a proposal to use multiprime RSA for post quantom encryption relying on a large polynomial advantage for honest user over attacker. I liked not requiring expononetial advantage as usuall. $\endgroup$ – Meir Maor Sep 22 '18 at 20:21
3
$\begingroup$

I also know $\phi(n)=(p-1)(q-1)$

This actually only holds if $n=pq$ and if $p$ and $q$ are both primes.

When $n$ doesn't factor as nicely you'll need the more general definition of $\phi(n)$ which can be computed from the following three axioms (given the prime factorization of $n$):

  • If $\gcd(n,m)=1$ for any $n,m$ then $\phi(n\cdot m)=\phi(n)\phi(m)$
  • If $p$ is prime and $k\geq 1$ then $\phi(p^k)=p^{k-1}(p-1)$

So in your case $$\phi(120)=\phi(2^3\cdot 3\cdot 5)=\phi(2^3)\phi(3)\phi(5)=(2^2\cdot1)\cdot2\cdot4=32$$

does multi-prime RSA make any sense in practical use?

Yes, using more than two primes can make sense if you use the chinese remainder theorem (CRT) which yields a speed-up of $k^2/4$ for $k$ primes compared to using only $k=2$. See fgrieu's excellent answer for a discussion of why one wants that and what one has to look out for when actually deploying multi-prime RSA and the table in DW's answer to the same question for an overview of how many primes to use for each modulus size.

$\endgroup$

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.