RSA How to find the private key to a given public key when n doesn't consist of two primes?
Clash Royale CLAN TAG#URR8PPP
up vote
1
down vote
favorite
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 $lfloorsqrt120rfloor=10$ I can't find a matching prime number. So it gets more complicated. I also know $phi(n)=(p-1)(q-1)$ and $3cdot dequiv 1mod (p-1)(q-1)$
But here I stuck, could somebody help me from this point on?
rsa
asked Sep 22 at 15:34
baxbear
83
add a comment |Â
up vote
1
down vote
favorite
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 $lfloorsqrt120rfloor=10$ I can't find a matching prime number. So it gets more complicated. I also know $phi(n)=(p-1)(q-1)$ and $3cdot dequiv 1mod (p-1)(q-1)$
But here I stuck, could somebody help me from this point on?
rsa
asked Sep 22 at 15:34
baxbear
83
2
$120=2^3cdot 3cdot 5$ so this is indeed multi-prime RSA.
– SEJPM♦
Sep 22 at 15:56
so do I need to compute $phi(n)=(2-1)^3cdot(3-1)cdot(5-1)$ and then $3cdot dequiv 1mod 8$ with $d = e = 3$?
– baxbear
Sep 22 at 15:59
does multi-prime RSA make any sense in practical use?
– baxbear
Sep 22 at 16:01
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.
– Meir Maor
Sep 22 at 20:21
add a comment |Â
up vote
1
down vote
favorite
up vote
1
down vote
favorite
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 $lfloorsqrt120rfloor=10$ I can't find a matching prime number. So it gets more complicated. I also know $phi(n)=(p-1)(q-1)$ and $3cdot dequiv 1mod (p-1)(q-1)$
But here I stuck, could somebody help me from this point on?
rsa
asked Sep 22 at 15:34
baxbear
83
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 $lfloorsqrt120rfloor=10$ I can't find a matching prime number. So it gets more complicated. I also know $phi(n)=(p-1)(q-1)$ and $3cdot dequiv 1mod (p-1)(q-1)$
But here I stuck, could somebody help me from this point on?
rsa
rsa
asked Sep 22 at 15:34
baxbear
83
asked Sep 22 at 15:34
baxbear
83
asked Sep 22 at 15:34
baxbear
83
asked Sep 22 at 15:34
baxbear
83
asked Sep 22 at 15:34
baxbear
83
83
2
$120=2^3cdot 3cdot 5$ so this is indeed multi-prime RSA.
– SEJPM♦
Sep 22 at 15:56
so do I need to compute $phi(n)=(2-1)^3cdot(3-1)cdot(5-1)$ and then $3cdot dequiv 1mod 8$ with $d = e = 3$?
– baxbear
Sep 22 at 15:59
does multi-prime RSA make any sense in practical use?
– baxbear
Sep 22 at 16:01
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.
– Meir Maor
Sep 22 at 20:21
add a comment |Â
2
$120=2^3cdot 3cdot 5$ so this is indeed multi-prime RSA.
– SEJPM♦
Sep 22 at 15:56
so do I need to compute $phi(n)=(2-1)^3cdot(3-1)cdot(5-1)$ and then $3cdot dequiv 1mod 8$ with $d = e = 3$?
– baxbear
Sep 22 at 15:59
does multi-prime RSA make any sense in practical use?
– baxbear
Sep 22 at 16:01
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.
– Meir Maor
Sep 22 at 20:21
2
2
$120=2^3cdot 3cdot 5$ so this is indeed multi-prime RSA.
– SEJPM♦
Sep 22 at 15:56
$120=2^3cdot 3cdot 5$ so this is indeed multi-prime RSA.
– SEJPM♦
Sep 22 at 15:56
so do I need to compute $phi(n)=(2-1)^3cdot(3-1)cdot(5-1)$ and then $3cdot dequiv 1mod 8$ with $d = e = 3$?
– baxbear
Sep 22 at 15:59
so do I need to compute $phi(n)=(2-1)^3cdot(3-1)cdot(5-1)$ and then $3cdot dequiv 1mod 8$ with $d = e = 3$?
– baxbear
Sep 22 at 15:59
does multi-prime RSA make any sense in practical use?
– baxbear
Sep 22 at 16:01
does multi-prime RSA make any sense in practical use?
– baxbear
Sep 22 at 16:01
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.
– Meir Maor
Sep 22 at 20:21
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.
– Meir Maor
Sep 22 at 20:21
add a comment |Â
1 Answer
1
active
oldest
votes
up vote
3
down vote
accepted
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(ncdot m)=phi(n)phi(m)$
- If $p$ is prime and $kgeq 1$ then $phi(p^k)=p^k-1(p-1)$
So in your case $$phi(120)=phi(2^3cdot 3cdot 5)=phi(2^3)phi(3)phi(5)=(2^2cdot1)cdot2cdot4=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.
answered Sep 22 at 16:59
SEJPM♦
26.9k351129
add a comment |Â
1 Answer
1
active
oldest
votes
1 Answer
1
active
oldest
votes
active
oldest
votes
active
oldest
votes
up vote
3
down vote
accepted
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(ncdot m)=phi(n)phi(m)$
- If $p$ is prime and $kgeq 1$ then $phi(p^k)=p^k-1(p-1)$
So in your case $$phi(120)=phi(2^3cdot 3cdot 5)=phi(2^3)phi(3)phi(5)=(2^2cdot1)cdot2cdot4=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.
answered Sep 22 at 16:59
SEJPM♦
26.9k351129
add a comment |Â
up vote
3
down vote
accepted
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(ncdot m)=phi(n)phi(m)$
- If $p$ is prime and $kgeq 1$ then $phi(p^k)=p^k-1(p-1)$
So in your case $$phi(120)=phi(2^3cdot 3cdot 5)=phi(2^3)phi(3)phi(5)=(2^2cdot1)cdot2cdot4=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.
answered Sep 22 at 16:59
SEJPM♦
26.9k351129
add a comment |Â
up vote
3
down vote
accepted
up vote
3
down vote
accepted
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(ncdot m)=phi(n)phi(m)$
- If $p$ is prime and $kgeq 1$ then $phi(p^k)=p^k-1(p-1)$
So in your case $$phi(120)=phi(2^3cdot 3cdot 5)=phi(2^3)phi(3)phi(5)=(2^2cdot1)cdot2cdot4=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.
answered Sep 22 at 16:59
SEJPM♦
26.9k351129
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(ncdot m)=phi(n)phi(m)$
- If $p$ is prime and $kgeq 1$ then $phi(p^k)=p^k-1(p-1)$
So in your case $$phi(120)=phi(2^3cdot 3cdot 5)=phi(2^3)phi(3)phi(5)=(2^2cdot1)cdot2cdot4=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.
answered Sep 22 at 16:59
SEJPM♦
26.9k351129
edited Sep 22 at 17:06
answered Sep 22 at 16:59
SEJPM♦
26.9k351129
answered Sep 22 at 16:59
SEJPM♦
26.9k351129
answered Sep 22 at 16:59
SEJPM♦
26.9k351129
26.9k351129
add a comment |Â
add a comment |Â
Sign up or log in
StackExchange.ready(function ()
StackExchange.helpers.onClickDraftSave('#login-link');
);
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
StackExchange.ready(
function ()
StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2fcrypto.stackexchange.com%2fquestions%2f62567%2frsa-how-to-find-the-private-key-to-a-given-public-key-when-n-doesnt-consist-of%23new-answer', 'question_page');
);
Post as a guest
Sign up or log in
StackExchange.ready(function ()
StackExchange.helpers.onClickDraftSave('#login-link');
);
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Sign up or log in
StackExchange.ready(function ()
StackExchange.helpers.onClickDraftSave('#login-link');
);
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Sign up or log in
StackExchange.ready(function ()
StackExchange.helpers.onClickDraftSave('#login-link');
);
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
2
$120=2^3cdot 3cdot 5$ so this is indeed multi-prime RSA.
– SEJPM♦
Sep 22 at 15:56
so do I need to compute $phi(n)=(2-1)^3cdot(3-1)cdot(5-1)$ and then $3cdot dequiv 1mod 8$ with $d = e = 3$?
– baxbear
Sep 22 at 15:59
does multi-prime RSA make any sense in practical use?
– baxbear
Sep 22 at 16:01
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.
– Meir Maor
Sep 22 at 20:21