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?
4
-
2$\begingroup$ $120=2^3\cdot 3\cdot 5$ so this is indeed multi-prime RSA. $\endgroup$– SEJPMCommented Sep 22, 2018 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$– baxbearCommented Sep 22, 2018 at 15:59
-
$\begingroup$ does multi-prime RSA make any sense in practical use? $\endgroup$– baxbearCommented Sep 22, 2018 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 MaorCommented Sep 22, 2018 at 20:21
Add a comment
|
1 Answer
$\begingroup$
$\endgroup$
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.
