Mixing
How can I break RSA if I know the private key?
$begingroup$
Given an RSA encryption with public key $(n,e)$. Let say I found out the private key $d$.
So I know $dcdot e = 1(mod (p-1)(q-1))$ for the primes $pneq q$ that generate $n$ by $pcdot q=n$
but from here, how can I efficiency find $p$ and $q$?
And on the other way, I assume the answer is similar. If I know $p$ and $q$, how can I generate $d$ to crack the encryption?
Thanks
prime-numbers computer-science cryptography
asked Jan 22 at 9:22
ShaqShaq
3049
$endgroup$
add a comment |
$begingroup$
Given an RSA encryption with public key $(n,e)$. Let say I found out the private key $d$.
So I know $dcdot e = 1(mod (p-1)(q-1))$ for the primes $pneq q$ that generate $n$ by $pcdot q=n$
but from here, how can I efficiency find $p$ and $q$?
And on the other way, I assume the answer is similar. If I know $p$ and $q$, how can I generate $d$ to crack the encryption?
Thanks
prime-numbers computer-science cryptography
asked Jan 22 at 9:22
ShaqShaq
3049
$endgroup$
$begingroup$
You never care about $p$ and $q$, because only $d$ is used in the decryption (which is $a longmapsto a^d mod, pq$). If you know about $p,q$, then you can compute $(p-1)(q-1)$ and deduce $d$ very easily.
$endgroup$
– Mindlack
Jan 22 at 9:27
$begingroup$
oh ok cause its mod (n) and not mod (p-1)(q-1) cool. And when I know p and q, I use Euclid's Algorithm to find d? Just like when you encrypt I guess?
$endgroup$
– Shaq
Jan 22 at 9:37
1
$begingroup$
math.stackexchange.com/questions/790714/rsa-finding-p-and-q math.stackexchange.com/questions/551744/…
$endgroup$
– Matthew Towers
Jan 22 at 9:57
$begingroup$
Knowing $d$ is what breaking RSA means! factoring $n$ is not needed: If you can decrypt you have broken the system.
$endgroup$
– Henno Brandsma
Jan 25 at 5:25
add a comment |
$begingroup$
Given an RSA encryption with public key $(n,e)$. Let say I found out the private key $d$.
So I know $dcdot e = 1(mod (p-1)(q-1))$ for the primes $pneq q$ that generate $n$ by $pcdot q=n$
but from here, how can I efficiency find $p$ and $q$?
And on the other way, I assume the answer is similar. If I know $p$ and $q$, how can I generate $d$ to crack the encryption?
Thanks
prime-numbers computer-science cryptography
asked Jan 22 at 9:22
ShaqShaq
3049
$endgroup$
Given an RSA encryption with public key $(n,e)$. Let say I found out the private key $d$.
So I know $dcdot e = 1(mod (p-1)(q-1))$ for the primes $pneq q$ that generate $n$ by $pcdot q=n$
but from here, how can I efficiency find $p$ and $q$?
And on the other way, I assume the answer is similar. If I know $p$ and $q$, how can I generate $d$ to crack the encryption?
Thanks
prime-numbers computer-science cryptography
prime-numbers computer-science cryptography
asked Jan 22 at 9:22
ShaqShaq
3049
asked Jan 22 at 9:22
ShaqShaq
3049
asked Jan 22 at 9:22
ShaqShaq
3049
asked Jan 22 at 9:22
ShaqShaq
3049
asked Jan 22 at 9:22
ShaqShaq
3049
3049
$begingroup$
You never care about $p$ and $q$, because only $d$ is used in the decryption (which is $a longmapsto a^d mod, pq$). If you know about $p,q$, then you can compute $(p-1)(q-1)$ and deduce $d$ very easily.
$endgroup$
– Mindlack
Jan 22 at 9:27
$begingroup$
oh ok cause its mod (n) and not mod (p-1)(q-1) cool. And when I know p and q, I use Euclid's Algorithm to find d? Just like when you encrypt I guess?
$endgroup$
– Shaq
Jan 22 at 9:37
1
$begingroup$
math.stackexchange.com/questions/790714/rsa-finding-p-and-q math.stackexchange.com/questions/551744/…
$endgroup$
– Matthew Towers
Jan 22 at 9:57
$begingroup$
Knowing $d$ is what breaking RSA means! factoring $n$ is not needed: If you can decrypt you have broken the system.
$endgroup$
– Henno Brandsma
Jan 25 at 5:25
add a comment |
$begingroup$
You never care about $p$ and $q$, because only $d$ is used in the decryption (which is $a longmapsto a^d mod, pq$). If you know about $p,q$, then you can compute $(p-1)(q-1)$ and deduce $d$ very easily.
$endgroup$
– Mindlack
Jan 22 at 9:27
$begingroup$
oh ok cause its mod (n) and not mod (p-1)(q-1) cool. And when I know p and q, I use Euclid's Algorithm to find d? Just like when you encrypt I guess?
$endgroup$
– Shaq
Jan 22 at 9:37
1
$begingroup$
math.stackexchange.com/questions/790714/rsa-finding-p-and-q math.stackexchange.com/questions/551744/…
$endgroup$
– Matthew Towers
Jan 22 at 9:57
$begingroup$
Knowing $d$ is what breaking RSA means! factoring $n$ is not needed: If you can decrypt you have broken the system.
$endgroup$
– Henno Brandsma
Jan 25 at 5:25
$begingroup$
You never care about $p$ and $q$, because only $d$ is used in the decryption (which is $a longmapsto a^d mod, pq$). If you know about $p,q$, then you can compute $(p-1)(q-1)$ and deduce $d$ very easily.
$endgroup$
– Mindlack
Jan 22 at 9:27
$begingroup$
You never care about $p$ and $q$, because only $d$ is used in the decryption (which is $a longmapsto a^d mod, pq$). If you know about $p,q$, then you can compute $(p-1)(q-1)$ and deduce $d$ very easily.
$endgroup$
– Mindlack
Jan 22 at 9:27
$begingroup$
oh ok cause its mod (n) and not mod (p-1)(q-1) cool. And when I know p and q, I use Euclid's Algorithm to find d? Just like when you encrypt I guess?
$endgroup$
– Shaq
Jan 22 at 9:37
$begingroup$
oh ok cause its mod (n) and not mod (p-1)(q-1) cool. And when I know p and q, I use Euclid's Algorithm to find d? Just like when you encrypt I guess?
$endgroup$
– Shaq
Jan 22 at 9:37
1
1
$begingroup$
math.stackexchange.com/questions/790714/rsa-finding-p-and-q math.stackexchange.com/questions/551744/…
$endgroup$
– Matthew Towers
Jan 22 at 9:57
$begingroup$
math.stackexchange.com/questions/790714/rsa-finding-p-and-q math.stackexchange.com/questions/551744/…
$endgroup$
– Matthew Towers
Jan 22 at 9:57
$begingroup$
Knowing $d$ is what breaking RSA means! factoring $n$ is not needed: If you can decrypt you have broken the system.
$endgroup$
– Henno Brandsma
Jan 25 at 5:25
$begingroup$
Knowing $d$ is what breaking RSA means! factoring $n$ is not needed: If you can decrypt you have broken the system.
$endgroup$
– Henno Brandsma
Jan 25 at 5:25
add a comment |
3 Answers
3
active
oldest
votes
$begingroup$
You know that $de = k(p-1)(q-1)+1$ for some integer $k$, and you know $n=pq$. Find the first multiple of $n$ that is greater then $de$ - this will be $kn$, and
$kn-de+1 = kpq - k(p-1)(q-1) = k(p+q-1) \ Rightarrow p+q=frac{kn-de+k+1}{k}$
Once you know $p+q$ then you also have
$p-q=sqrt{(p+q)^2-4n}$
and then you can find $p$ and $q$.
For example, if $n=187$, $d=37$ and $e=13$ then $k=lceilfrac{de}{n}rceil=3$ and
$p+q=frac{3times187 -481 + 4}{3}=28\p-q=sqrt{28^2-4times187}=6$
and so $p=17$, $q=11$.
answered Jan 22 at 10:03
gandalf61gandalf61
8,936725
$endgroup$
1
$begingroup$
You mean de <= k(p-1)(q-1) for some integer k? I dot get it: de = 1 mod(p-1)(q-1) so if de = 1+ (p-1)(q-1), how can you find a k such that de = k(p-1)(q-1)? You mean de-1 = k(p-1)(q-1)?
$endgroup$
– Shaq
Jan 22 at 11:23
$begingroup$
Yes, you are correct. I have fixed my answer.
$endgroup$
– gandalf61
Jan 22 at 11:53
$begingroup$
Ok it looks nice
$endgroup$
– Shaq
Jan 22 at 11:56
add a comment |
$begingroup$
Compute $de-1 = 2^r s$ such that $s$ is odd. Pick random $2leq a leq N-1$ so that
$$
b:=a^snotequiv 1pmod N
$$
If this fails, try another $a$. We also check that $gcd(a,N)=1$, otherwise we have found $p$ or $q$. Now try
$$
gcd(b-1,N),gcd(b^2-1,N),dots,gcd(b^{2^r}-1,N)
$$
(This can terminate early once $b^{2^i}equiv 1pmod N$.)
One of the $gcd$'s might give you $p$ or $q$ and you are done.
This procedure is expected to terminate fast, within a couple of tries.
We have
$$
deequiv 1 pmod{(p-1)(q-1)} implies de-1 = k(p-1)(q-1) = kcdot phi(N)
$$
where $phi(cdot)$ is the Euler Phi function. For any integers $a$ coprime to $N$, they must satisfy
$$
a^mequiv (a^{phi(N)})^k equiv 1^kequiv 1 pmod N
$$
We started with
$$
bequiv a^s pmod N
$$
As we square $b$ iteratively, at some point it must become $1$. This is because
$$
b^{2^r}equiv a^{2^rs} equiv a^m equiv 1 pmod N
$$
but it could happen earlier. Since the starting $b$ is not $1$, we have precisely
$$
b^{2^i}notequiv 1pmod N,quad b^{2^{i+1}}equiv 1 pmod N
$$
for some $i$. Now the RHS becomes
$$
(b^{2^i}+1)(b^{2^i}-1) equiv 0 pmod N
$$
This means $p,q$ divides $(b^{2^i}+1)(b^{2^i}-1)$. As long as they don't both divide the same factor,
$$
gcd(b^{2^i}-1,N)=p text{ or } q
$$
The condition $b^{2^i}notequiv 1pmod N$ ensures that $p,q$ cannot both divide $(b^{2^i}-1)$, so the only way to fail is if
$$
b^{2^i}+1 equiv 0 pmod N
$$
The chances of this happening is very low. (For some $N$ it might not even be possible.)
answered Jan 22 at 10:22
Yong Hao NgYong Hao Ng
3,5691222
$endgroup$
$begingroup$
Ok, I think I am not ready enough for it right now.. I get what you have done in the big picture but didn't really understand it fully for every step. I will get to read and study some more and will come back to your answer later :)
$endgroup$
– Shaq
Jan 22 at 11:15
$begingroup$
@Shaq No problem, just let me know if I can expand on some parts.
$endgroup$
– Yong Hao Ng
Jan 22 at 11:33
add a comment |
$begingroup$
To answer your second question:
Given an RSA encryption with public key $(n,e)$.
If I know $p$ and $q$, how can I generate $d$ to crack the encryption?
Knowing $p$ and $q$, we use Euler's totient function,
$$
varphi(n) = (p - 1)(q - 1).
$$
Then in order to compute $d$ in text-book RSA we need to use the following congruence relation:
$$
de equiv_{varphi(n)} 1
$$
Since we know $varphi(n)$ and $e$, all you need to do now is use the Extended Eucledian algorithm. First start by computing $gcd(varphi(n), e)$, then work your way back to find $d$.
answered Jan 22 at 17:53
EdOverflowEdOverflow
25119
$endgroup$
add a comment |
Your Answer
StackExchange.ifUsing("editor", function () {
return StackExchange.using("mathjaxEditing", function () {
StackExchange.MarkdownEditor.creationCallbacks.add(function (editor, postfix) {
StackExchange.mathjaxEditing.prepareWmdForMathJax(editor, postfix, [["$", "$"], ["\\(","\\)"]]);
});
});
}, "mathjax-editing");
StackExchange.ready(function() {
var channelOptions = {
tags: "".split(" "),
id: "69"
};
initTagRenderer("".split(" "), "".split(" "), channelOptions);
StackExchange.using("externalEditor", function() {
// Have to fire editor after snippets, if snippets enabled
if (StackExchange.settings.snippets.snippetsEnabled) {
StackExchange.using("snippets", function() {
createEditor();
});
}
else {
createEditor();
}
});
function createEditor() {
StackExchange.prepareEditor({
heartbeatType: 'answer',
autoActivateHeartbeat: false,
convertImagesToLinks: true,
noModals: true,
showLowRepImageUploadWarning: true,
reputationToPostImages: 10,
bindNavPrevention: true,
postfix: "",
imageUploader: {
brandingHtml: "Powered by u003ca class="icon-imgur-white" href="https://imgur.com/"u003eu003c/au003e",
contentPolicyHtml: "User contributions licensed under u003ca href="https://creativecommons.org/licenses/by-sa/3.0/"u003ecc by-sa 3.0 with attribution requiredu003c/au003e u003ca href="https://stackoverflow.com/legal/content-policy"u003e(content policy)u003c/au003e",
allowUrls: true
},
noCode: true, onDemand: true,
discardSelector: ".discard-answer"
,immediatelyShowMarkdownHelp:true
});
}
});
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
Required, but never shown
StackExchange.ready(
function () {
StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2fmath.stackexchange.com%2fquestions%2f3082920%2fhow-can-i-break-rsa-if-i-know-the-private-key%23new-answer', 'question_page');
}
);
Post as a guest
Required, but never shown
3 Answers
3
active
oldest
votes
3 Answers
3
active
oldest
votes
active
oldest
votes
active
oldest
votes
$begingroup$
You know that $de = k(p-1)(q-1)+1$ for some integer $k$, and you know $n=pq$. Find the first multiple of $n$ that is greater then $de$ - this will be $kn$, and
$kn-de+1 = kpq - k(p-1)(q-1) = k(p+q-1) \ Rightarrow p+q=frac{kn-de+k+1}{k}$
Once you know $p+q$ then you also have
$p-q=sqrt{(p+q)^2-4n}$
and then you can find $p$ and $q$.
For example, if $n=187$, $d=37$ and $e=13$ then $k=lceilfrac{de}{n}rceil=3$ and
$p+q=frac{3times187 -481 + 4}{3}=28\p-q=sqrt{28^2-4times187}=6$
and so $p=17$, $q=11$.
answered Jan 22 at 10:03
gandalf61gandalf61
8,936725
$endgroup$
1
$begingroup$
You mean de <= k(p-1)(q-1) for some integer k? I dot get it: de = 1 mod(p-1)(q-1) so if de = 1+ (p-1)(q-1), how can you find a k such that de = k(p-1)(q-1)? You mean de-1 = k(p-1)(q-1)?
$endgroup$
– Shaq
Jan 22 at 11:23
$begingroup$
Yes, you are correct. I have fixed my answer.
$endgroup$
– gandalf61
Jan 22 at 11:53
$begingroup$
Ok it looks nice
$endgroup$
– Shaq
Jan 22 at 11:56
add a comment |
$begingroup$
You know that $de = k(p-1)(q-1)+1$ for some integer $k$, and you know $n=pq$. Find the first multiple of $n$ that is greater then $de$ - this will be $kn$, and
$kn-de+1 = kpq - k(p-1)(q-1) = k(p+q-1) \ Rightarrow p+q=frac{kn-de+k+1}{k}$
Once you know $p+q$ then you also have
$p-q=sqrt{(p+q)^2-4n}$
and then you can find $p$ and $q$.
For example, if $n=187$, $d=37$ and $e=13$ then $k=lceilfrac{de}{n}rceil=3$ and
$p+q=frac{3times187 -481 + 4}{3}=28\p-q=sqrt{28^2-4times187}=6$
and so $p=17$, $q=11$.
answered Jan 22 at 10:03
gandalf61gandalf61
8,936725
$endgroup$
1
$begingroup$
You mean de <= k(p-1)(q-1) for some integer k? I dot get it: de = 1 mod(p-1)(q-1) so if de = 1+ (p-1)(q-1), how can you find a k such that de = k(p-1)(q-1)? You mean de-1 = k(p-1)(q-1)?
$endgroup$
– Shaq
Jan 22 at 11:23
$begingroup$
Yes, you are correct. I have fixed my answer.
$endgroup$
– gandalf61
Jan 22 at 11:53
$begingroup$
Ok it looks nice
$endgroup$
– Shaq
Jan 22 at 11:56
add a comment |
$begingroup$
You know that $de = k(p-1)(q-1)+1$ for some integer $k$, and you know $n=pq$. Find the first multiple of $n$ that is greater then $de$ - this will be $kn$, and
$kn-de+1 = kpq - k(p-1)(q-1) = k(p+q-1) \ Rightarrow p+q=frac{kn-de+k+1}{k}$
Once you know $p+q$ then you also have
$p-q=sqrt{(p+q)^2-4n}$
and then you can find $p$ and $q$.
For example, if $n=187$, $d=37$ and $e=13$ then $k=lceilfrac{de}{n}rceil=3$ and
$p+q=frac{3times187 -481 + 4}{3}=28\p-q=sqrt{28^2-4times187}=6$
and so $p=17$, $q=11$.
answered Jan 22 at 10:03
gandalf61gandalf61
8,936725
$endgroup$
You know that $de = k(p-1)(q-1)+1$ for some integer $k$, and you know $n=pq$. Find the first multiple of $n$ that is greater then $de$ - this will be $kn$, and
$kn-de+1 = kpq - k(p-1)(q-1) = k(p+q-1) \ Rightarrow p+q=frac{kn-de+k+1}{k}$
Once you know $p+q$ then you also have
$p-q=sqrt{(p+q)^2-4n}$
and then you can find $p$ and $q$.
For example, if $n=187$, $d=37$ and $e=13$ then $k=lceilfrac{de}{n}rceil=3$ and
$p+q=frac{3times187 -481 + 4}{3}=28\p-q=sqrt{28^2-4times187}=6$
and so $p=17$, $q=11$.
answered Jan 22 at 10:03
gandalf61gandalf61
8,936725
edited Jan 22 at 11:52
answered Jan 22 at 10:03
gandalf61gandalf61
8,936725
answered Jan 22 at 10:03
gandalf61gandalf61
8,936725
answered Jan 22 at 10:03
gandalf61gandalf61
8,936725
8,936725
1
$begingroup$
You mean de <= k(p-1)(q-1) for some integer k? I dot get it: de = 1 mod(p-1)(q-1) so if de = 1+ (p-1)(q-1), how can you find a k such that de = k(p-1)(q-1)? You mean de-1 = k(p-1)(q-1)?
$endgroup$
– Shaq
Jan 22 at 11:23
$begingroup$
Yes, you are correct. I have fixed my answer.
$endgroup$
– gandalf61
Jan 22 at 11:53
$begingroup$
Ok it looks nice
$endgroup$
– Shaq
Jan 22 at 11:56
add a comment |
1
$begingroup$
You mean de <= k(p-1)(q-1) for some integer k? I dot get it: de = 1 mod(p-1)(q-1) so if de = 1+ (p-1)(q-1), how can you find a k such that de = k(p-1)(q-1)? You mean de-1 = k(p-1)(q-1)?
$endgroup$
– Shaq
Jan 22 at 11:23
$begingroup$
Yes, you are correct. I have fixed my answer.
$endgroup$
– gandalf61
Jan 22 at 11:53
$begingroup$
Ok it looks nice
$endgroup$
– Shaq
Jan 22 at 11:56
1
1
$begingroup$
You mean de <= k(p-1)(q-1) for some integer k? I dot get it: de = 1 mod(p-1)(q-1) so if de = 1+ (p-1)(q-1), how can you find a k such that de = k(p-1)(q-1)? You mean de-1 = k(p-1)(q-1)?
$endgroup$
– Shaq
Jan 22 at 11:23
$begingroup$
You mean de <= k(p-1)(q-1) for some integer k? I dot get it: de = 1 mod(p-1)(q-1) so if de = 1+ (p-1)(q-1), how can you find a k such that de = k(p-1)(q-1)? You mean de-1 = k(p-1)(q-1)?
$endgroup$
– Shaq
Jan 22 at 11:23
$begingroup$
Yes, you are correct. I have fixed my answer.
$endgroup$
– gandalf61
Jan 22 at 11:53
$begingroup$
Yes, you are correct. I have fixed my answer.
$endgroup$
– gandalf61
Jan 22 at 11:53
$begingroup$
Ok it looks nice
$endgroup$
– Shaq
Jan 22 at 11:56
$begingroup$
Ok it looks nice
$endgroup$
– Shaq
Jan 22 at 11:56
add a comment |
$begingroup$
Compute $de-1 = 2^r s$ such that $s$ is odd. Pick random $2leq a leq N-1$ so that
$$
b:=a^snotequiv 1pmod N
$$
If this fails, try another $a$. We also check that $gcd(a,N)=1$, otherwise we have found $p$ or $q$. Now try
$$
gcd(b-1,N),gcd(b^2-1,N),dots,gcd(b^{2^r}-1,N)
$$
(This can terminate early once $b^{2^i}equiv 1pmod N$.)
One of the $gcd$'s might give you $p$ or $q$ and you are done.
This procedure is expected to terminate fast, within a couple of tries.
We have
$$
deequiv 1 pmod{(p-1)(q-1)} implies de-1 = k(p-1)(q-1) = kcdot phi(N)
$$
where $phi(cdot)$ is the Euler Phi function. For any integers $a$ coprime to $N$, they must satisfy
$$
a^mequiv (a^{phi(N)})^k equiv 1^kequiv 1 pmod N
$$
We started with
$$
bequiv a^s pmod N
$$
As we square $b$ iteratively, at some point it must become $1$. This is because
$$
b^{2^r}equiv a^{2^rs} equiv a^m equiv 1 pmod N
$$
but it could happen earlier. Since the starting $b$ is not $1$, we have precisely
$$
b^{2^i}notequiv 1pmod N,quad b^{2^{i+1}}equiv 1 pmod N
$$
for some $i$. Now the RHS becomes
$$
(b^{2^i}+1)(b^{2^i}-1) equiv 0 pmod N
$$
This means $p,q$ divides $(b^{2^i}+1)(b^{2^i}-1)$. As long as they don't both divide the same factor,
$$
gcd(b^{2^i}-1,N)=p text{ or } q
$$
The condition $b^{2^i}notequiv 1pmod N$ ensures that $p,q$ cannot both divide $(b^{2^i}-1)$, so the only way to fail is if
$$
b^{2^i}+1 equiv 0 pmod N
$$
The chances of this happening is very low. (For some $N$ it might not even be possible.)
answered Jan 22 at 10:22
Yong Hao NgYong Hao Ng
3,5691222
$endgroup$
$begingroup$
Ok, I think I am not ready enough for it right now.. I get what you have done in the big picture but didn't really understand it fully for every step. I will get to read and study some more and will come back to your answer later :)
$endgroup$
– Shaq
Jan 22 at 11:15
$begingroup$
@Shaq No problem, just let me know if I can expand on some parts.
$endgroup$
– Yong Hao Ng
Jan 22 at 11:33
add a comment |
$begingroup$
Compute $de-1 = 2^r s$ such that $s$ is odd. Pick random $2leq a leq N-1$ so that
$$
b:=a^snotequiv 1pmod N
$$
If this fails, try another $a$. We also check that $gcd(a,N)=1$, otherwise we have found $p$ or $q$. Now try
$$
gcd(b-1,N),gcd(b^2-1,N),dots,gcd(b^{2^r}-1,N)
$$
(This can terminate early once $b^{2^i}equiv 1pmod N$.)
One of the $gcd$'s might give you $p$ or $q$ and you are done.
This procedure is expected to terminate fast, within a couple of tries.
We have
$$
deequiv 1 pmod{(p-1)(q-1)} implies de-1 = k(p-1)(q-1) = kcdot phi(N)
$$
where $phi(cdot)$ is the Euler Phi function. For any integers $a$ coprime to $N$, they must satisfy
$$
a^mequiv (a^{phi(N)})^k equiv 1^kequiv 1 pmod N
$$
We started with
$$
bequiv a^s pmod N
$$
As we square $b$ iteratively, at some point it must become $1$. This is because
$$
b^{2^r}equiv a^{2^rs} equiv a^m equiv 1 pmod N
$$
but it could happen earlier. Since the starting $b$ is not $1$, we have precisely
$$
b^{2^i}notequiv 1pmod N,quad b^{2^{i+1}}equiv 1 pmod N
$$
for some $i$. Now the RHS becomes
$$
(b^{2^i}+1)(b^{2^i}-1) equiv 0 pmod N
$$
This means $p,q$ divides $(b^{2^i}+1)(b^{2^i}-1)$. As long as they don't both divide the same factor,
$$
gcd(b^{2^i}-1,N)=p text{ or } q
$$
The condition $b^{2^i}notequiv 1pmod N$ ensures that $p,q$ cannot both divide $(b^{2^i}-1)$, so the only way to fail is if
$$
b^{2^i}+1 equiv 0 pmod N
$$
The chances of this happening is very low. (For some $N$ it might not even be possible.)
answered Jan 22 at 10:22
Yong Hao NgYong Hao Ng
3,5691222
$endgroup$
$begingroup$
Ok, I think I am not ready enough for it right now.. I get what you have done in the big picture but didn't really understand it fully for every step. I will get to read and study some more and will come back to your answer later :)
$endgroup$
– Shaq
Jan 22 at 11:15
$begingroup$
@Shaq No problem, just let me know if I can expand on some parts.
$endgroup$
– Yong Hao Ng
Jan 22 at 11:33
add a comment |
$begingroup$
Compute $de-1 = 2^r s$ such that $s$ is odd. Pick random $2leq a leq N-1$ so that
$$
b:=a^snotequiv 1pmod N
$$
If this fails, try another $a$. We also check that $gcd(a,N)=1$, otherwise we have found $p$ or $q$. Now try
$$
gcd(b-1,N),gcd(b^2-1,N),dots,gcd(b^{2^r}-1,N)
$$
(This can terminate early once $b^{2^i}equiv 1pmod N$.)
One of the $gcd$'s might give you $p$ or $q$ and you are done.
This procedure is expected to terminate fast, within a couple of tries.
We have
$$
deequiv 1 pmod{(p-1)(q-1)} implies de-1 = k(p-1)(q-1) = kcdot phi(N)
$$
where $phi(cdot)$ is the Euler Phi function. For any integers $a$ coprime to $N$, they must satisfy
$$
a^mequiv (a^{phi(N)})^k equiv 1^kequiv 1 pmod N
$$
We started with
$$
bequiv a^s pmod N
$$
As we square $b$ iteratively, at some point it must become $1$. This is because
$$
b^{2^r}equiv a^{2^rs} equiv a^m equiv 1 pmod N
$$
but it could happen earlier. Since the starting $b$ is not $1$, we have precisely
$$
b^{2^i}notequiv 1pmod N,quad b^{2^{i+1}}equiv 1 pmod N
$$
for some $i$. Now the RHS becomes
$$
(b^{2^i}+1)(b^{2^i}-1) equiv 0 pmod N
$$
This means $p,q$ divides $(b^{2^i}+1)(b^{2^i}-1)$. As long as they don't both divide the same factor,
$$
gcd(b^{2^i}-1,N)=p text{ or } q
$$
The condition $b^{2^i}notequiv 1pmod N$ ensures that $p,q$ cannot both divide $(b^{2^i}-1)$, so the only way to fail is if
$$
b^{2^i}+1 equiv 0 pmod N
$$
The chances of this happening is very low. (For some $N$ it might not even be possible.)
answered Jan 22 at 10:22
Yong Hao NgYong Hao Ng
3,5691222
$endgroup$
Compute $de-1 = 2^r s$ such that $s$ is odd. Pick random $2leq a leq N-1$ so that
$$
b:=a^snotequiv 1pmod N
$$
If this fails, try another $a$. We also check that $gcd(a,N)=1$, otherwise we have found $p$ or $q$. Now try
$$
gcd(b-1,N),gcd(b^2-1,N),dots,gcd(b^{2^r}-1,N)
$$
(This can terminate early once $b^{2^i}equiv 1pmod N$.)
One of the $gcd$'s might give you $p$ or $q$ and you are done.
This procedure is expected to terminate fast, within a couple of tries.
We have
$$
deequiv 1 pmod{(p-1)(q-1)} implies de-1 = k(p-1)(q-1) = kcdot phi(N)
$$
where $phi(cdot)$ is the Euler Phi function. For any integers $a$ coprime to $N$, they must satisfy
$$
a^mequiv (a^{phi(N)})^k equiv 1^kequiv 1 pmod N
$$
We started with
$$
bequiv a^s pmod N
$$
As we square $b$ iteratively, at some point it must become $1$. This is because
$$
b^{2^r}equiv a^{2^rs} equiv a^m equiv 1 pmod N
$$
but it could happen earlier. Since the starting $b$ is not $1$, we have precisely
$$
b^{2^i}notequiv 1pmod N,quad b^{2^{i+1}}equiv 1 pmod N
$$
for some $i$. Now the RHS becomes
$$
(b^{2^i}+1)(b^{2^i}-1) equiv 0 pmod N
$$
This means $p,q$ divides $(b^{2^i}+1)(b^{2^i}-1)$. As long as they don't both divide the same factor,
$$
gcd(b^{2^i}-1,N)=p text{ or } q
$$
The condition $b^{2^i}notequiv 1pmod N$ ensures that $p,q$ cannot both divide $(b^{2^i}-1)$, so the only way to fail is if
$$
b^{2^i}+1 equiv 0 pmod N
$$
The chances of this happening is very low. (For some $N$ it might not even be possible.)
answered Jan 22 at 10:22
Yong Hao NgYong Hao Ng
3,5691222
answered Jan 22 at 10:22
Yong Hao NgYong Hao Ng
3,5691222
answered Jan 22 at 10:22
Yong Hao NgYong Hao Ng
3,5691222
answered Jan 22 at 10:22
Yong Hao NgYong Hao Ng
3,5691222
3,5691222
$begingroup$
Ok, I think I am not ready enough for it right now.. I get what you have done in the big picture but didn't really understand it fully for every step. I will get to read and study some more and will come back to your answer later :)
$endgroup$
– Shaq
Jan 22 at 11:15
$begingroup$
@Shaq No problem, just let me know if I can expand on some parts.
$endgroup$
– Yong Hao Ng
Jan 22 at 11:33
add a comment |
$begingroup$
Ok, I think I am not ready enough for it right now.. I get what you have done in the big picture but didn't really understand it fully for every step. I will get to read and study some more and will come back to your answer later :)
$endgroup$
– Shaq
Jan 22 at 11:15
$begingroup$
@Shaq No problem, just let me know if I can expand on some parts.
$endgroup$
– Yong Hao Ng
Jan 22 at 11:33
$begingroup$
Ok, I think I am not ready enough for it right now.. I get what you have done in the big picture but didn't really understand it fully for every step. I will get to read and study some more and will come back to your answer later :)
$endgroup$
– Shaq
Jan 22 at 11:15
$begingroup$
Ok, I think I am not ready enough for it right now.. I get what you have done in the big picture but didn't really understand it fully for every step. I will get to read and study some more and will come back to your answer later :)
$endgroup$
– Shaq
Jan 22 at 11:15
$begingroup$
@Shaq No problem, just let me know if I can expand on some parts.
$endgroup$
– Yong Hao Ng
Jan 22 at 11:33
$begingroup$
@Shaq No problem, just let me know if I can expand on some parts.
$endgroup$
– Yong Hao Ng
Jan 22 at 11:33
add a comment |
$begingroup$
To answer your second question:
Given an RSA encryption with public key $(n,e)$.
If I know $p$ and $q$, how can I generate $d$ to crack the encryption?
Knowing $p$ and $q$, we use Euler's totient function,
$$
varphi(n) = (p - 1)(q - 1).
$$
Then in order to compute $d$ in text-book RSA we need to use the following congruence relation:
$$
de equiv_{varphi(n)} 1
$$
Since we know $varphi(n)$ and $e$, all you need to do now is use the Extended Eucledian algorithm. First start by computing $gcd(varphi(n), e)$, then work your way back to find $d$.
answered Jan 22 at 17:53
EdOverflowEdOverflow
25119
$endgroup$
add a comment |
$begingroup$
To answer your second question:
Given an RSA encryption with public key $(n,e)$.
If I know $p$ and $q$, how can I generate $d$ to crack the encryption?
Knowing $p$ and $q$, we use Euler's totient function,
$$
varphi(n) = (p - 1)(q - 1).
$$
Then in order to compute $d$ in text-book RSA we need to use the following congruence relation:
$$
de equiv_{varphi(n)} 1
$$
Since we know $varphi(n)$ and $e$, all you need to do now is use the Extended Eucledian algorithm. First start by computing $gcd(varphi(n), e)$, then work your way back to find $d$.
answered Jan 22 at 17:53
EdOverflowEdOverflow
25119
$endgroup$
add a comment |
$begingroup$
To answer your second question:
Given an RSA encryption with public key $(n,e)$.
If I know $p$ and $q$, how can I generate $d$ to crack the encryption?
Knowing $p$ and $q$, we use Euler's totient function,
$$
varphi(n) = (p - 1)(q - 1).
$$
Then in order to compute $d$ in text-book RSA we need to use the following congruence relation:
$$
de equiv_{varphi(n)} 1
$$
Since we know $varphi(n)$ and $e$, all you need to do now is use the Extended Eucledian algorithm. First start by computing $gcd(varphi(n), e)$, then work your way back to find $d$.
answered Jan 22 at 17:53
EdOverflowEdOverflow
25119
$endgroup$
To answer your second question:
Given an RSA encryption with public key $(n,e)$.
If I know $p$ and $q$, how can I generate $d$ to crack the encryption?
Knowing $p$ and $q$, we use Euler's totient function,
$$
varphi(n) = (p - 1)(q - 1).
$$
Then in order to compute $d$ in text-book RSA we need to use the following congruence relation:
$$
de equiv_{varphi(n)} 1
$$
Since we know $varphi(n)$ and $e$, all you need to do now is use the Extended Eucledian algorithm. First start by computing $gcd(varphi(n), e)$, then work your way back to find $d$.
answered Jan 22 at 17:53
EdOverflowEdOverflow
25119
answered Jan 22 at 17:53
EdOverflowEdOverflow
25119
answered Jan 22 at 17:53
EdOverflowEdOverflow
25119
answered Jan 22 at 17:53
EdOverflowEdOverflow
25119
25119
add a comment |
add a comment |
Thanks for contributing an answer to Mathematics Stack Exchange!
- Please be sure to answer the question. Provide details and share your research!
But avoid …
- Asking for help, clarification, or responding to other answers.
- Making statements based on opinion; back them up with references or personal experience.
Use MathJax to format equations. MathJax reference.
To learn more, see our tips on writing great answers.
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
Required, but never shown
StackExchange.ready(
function () {
StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2fmath.stackexchange.com%2fquestions%2f3082920%2fhow-can-i-break-rsa-if-i-know-the-private-key%23new-answer', 'question_page');
}
);
Post as a guest
Required, but never shown
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
Required, but never shown
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
Required, but never shown
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
Post as a guest
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
$begingroup$
You never care about $p$ and $q$, because only $d$ is used in the decryption (which is $a longmapsto a^d mod, pq$). If you know about $p,q$, then you can compute $(p-1)(q-1)$ and deduce $d$ very easily.
$endgroup$
– Mindlack
Jan 22 at 9:27
$begingroup$
oh ok cause its mod (n) and not mod (p-1)(q-1) cool. And when I know p and q, I use Euclid's Algorithm to find d? Just like when you encrypt I guess?
$endgroup$
– Shaq
Jan 22 at 9:37
1
$begingroup$
math.stackexchange.com/questions/790714/rsa-finding-p-and-q math.stackexchange.com/questions/551744/…
$endgroup$
– Matthew Towers
Jan 22 at 9:57
$begingroup$
Knowing $d$ is what breaking RSA means! factoring $n$ is not needed: If you can decrypt you have broken the system.
$endgroup$
– Henno Brandsma
Jan 25 at 5:25