RSA using 2 as a public exponent
$begingroup$
I'm failing to see why 2 can never be used and what weaknesses would be associated with doing so.
There's a similar question asking why it has to be in the form of $2^n$+1 but why not $2^n$
rsa public-key
asked Dec 19 '18 at 12:40
S. L.S. L.
706
$endgroup$
|
show 2 more comments
$begingroup$
I'm failing to see why 2 can never be used and what weaknesses would be associated with doing so.
There's a similar question asking why it has to be in the form of $2^n$+1 but why not $2^n$
rsa public-key
asked Dec 19 '18 at 12:40
S. L.S. L.
706
$endgroup$
3
$begingroup$
$gcd(2,(p-1)(q-1)) =$?
$endgroup$
– kelalaka
Dec 19 '18 at 12:41
$begingroup$
if p is odd a q is even it will be 1. if both are odd/both are even it will be 2?
$endgroup$
– S. L.
Dec 19 '18 at 12:46
$begingroup$
$p$ and $q$ are prime >2 implies both odd.
$endgroup$
– kelalaka
Dec 19 '18 at 12:46
$begingroup$
right of course! facepalm OK so what weakness would that bring? Edit: scratch that, it would lead to any ct no being uniquely decryptable
$endgroup$
– S. L.
Dec 19 '18 at 12:50
5
$begingroup$
en.wikipedia.org/wiki/Rabin_cryptosystem
$endgroup$
– Maeher
Dec 19 '18 at 12:52
|
show 2 more comments
$begingroup$
I'm failing to see why 2 can never be used and what weaknesses would be associated with doing so.
There's a similar question asking why it has to be in the form of $2^n$+1 but why not $2^n$
rsa public-key
asked Dec 19 '18 at 12:40
S. L.S. L.
706
$endgroup$
I'm failing to see why 2 can never be used and what weaknesses would be associated with doing so.
There's a similar question asking why it has to be in the form of $2^n$+1 but why not $2^n$
rsa public-key
rsa public-key
asked Dec 19 '18 at 12:40
S. L.S. L.
706
asked Dec 19 '18 at 12:40
S. L.S. L.
706
asked Dec 19 '18 at 12:40
S. L.S. L.
706
asked Dec 19 '18 at 12:40
S. L.S. L.
706
asked Dec 19 '18 at 12:40
S. L.S. L.
706
706
3
$begingroup$
$gcd(2,(p-1)(q-1)) =$?
$endgroup$
– kelalaka
Dec 19 '18 at 12:41
$begingroup$
if p is odd a q is even it will be 1. if both are odd/both are even it will be 2?
$endgroup$
– S. L.
Dec 19 '18 at 12:46
$begingroup$
$p$ and $q$ are prime >2 implies both odd.
$endgroup$
– kelalaka
Dec 19 '18 at 12:46
$begingroup$
right of course! facepalm OK so what weakness would that bring? Edit: scratch that, it would lead to any ct no being uniquely decryptable
$endgroup$
– S. L.
Dec 19 '18 at 12:50
5
$begingroup$
en.wikipedia.org/wiki/Rabin_cryptosystem
$endgroup$
– Maeher
Dec 19 '18 at 12:52
|
show 2 more comments
3
$begingroup$
$gcd(2,(p-1)(q-1)) =$?
$endgroup$
– kelalaka
Dec 19 '18 at 12:41
$begingroup$
if p is odd a q is even it will be 1. if both are odd/both are even it will be 2?
$endgroup$
– S. L.
Dec 19 '18 at 12:46
$begingroup$
$p$ and $q$ are prime >2 implies both odd.
$endgroup$
– kelalaka
Dec 19 '18 at 12:46
$begingroup$
right of course! facepalm OK so what weakness would that bring? Edit: scratch that, it would lead to any ct no being uniquely decryptable
$endgroup$
– S. L.
Dec 19 '18 at 12:50
5
$begingroup$
en.wikipedia.org/wiki/Rabin_cryptosystem
$endgroup$
– Maeher
Dec 19 '18 at 12:52
3
3
$begingroup$
$gcd(2,(p-1)(q-1)) =$?
$endgroup$
– kelalaka
Dec 19 '18 at 12:41
$begingroup$
$gcd(2,(p-1)(q-1)) =$?
$endgroup$
– kelalaka
Dec 19 '18 at 12:41
$begingroup$
if p is odd a q is even it will be 1. if both are odd/both are even it will be 2?
$endgroup$
– S. L.
Dec 19 '18 at 12:46
$begingroup$
if p is odd a q is even it will be 1. if both are odd/both are even it will be 2?
$endgroup$
– S. L.
Dec 19 '18 at 12:46
$begingroup$
$p$ and $q$ are prime >2 implies both odd.
$endgroup$
– kelalaka
Dec 19 '18 at 12:46
$begingroup$
$p$ and $q$ are prime >2 implies both odd.
$endgroup$
– kelalaka
Dec 19 '18 at 12:46
$begingroup$
right of course! facepalm OK so what weakness would that bring? Edit: scratch that, it would lead to any ct no being uniquely decryptable
$endgroup$
– S. L.
Dec 19 '18 at 12:50
$begingroup$
right of course! facepalm OK so what weakness would that bring? Edit: scratch that, it would lead to any ct no being uniquely decryptable
$endgroup$
– S. L.
Dec 19 '18 at 12:50
5
5
$begingroup$
en.wikipedia.org/wiki/Rabin_cryptosystem
$endgroup$
– Maeher
Dec 19 '18 at 12:52
$begingroup$
en.wikipedia.org/wiki/Rabin_cryptosystem
$endgroup$
– Maeher
Dec 19 '18 at 12:52
|
show 2 more comments
1 Answer
1
active
oldest
votes
$begingroup$
It is not that RSA becomes insecure when used with public exponent $2$. (In fact, the Rabin Cryptosystem does exactly that.) It's that it doesn't actually work.
The problem is that for $N = pq$ for two primes $p$ and $q$, the function $f : x mapsto x^2 bmod N$ is not injective. So it is impossible to invert uniquely. In fact, most elements of the function's range (the set of perfect squares) have $4$ preimages under $f$. (As pointed out by Thomas Pornin, the multiples of $p$ and $q$ have $2$, while $0$ has only one.)
We can get around this problem by choosing $pequiv qequiv 3 bmod 4$ and restricting the domain to the set of quadratic residues. In this case, the function is a trapdoor permutation over the set of quadratic residues if factoring is hard.
One might note, that this is actually a better guarantee than the one we have for the RSA trapdoor permutation, where the security is not known to be implied by the hardness of factoring.
answered Dec 19 '18 at 13:19
MaeherMaeher
3,60411830
$endgroup$
5
$begingroup$
Technically, most elements have 4 square roots, but some have only two, and zero has only one. The elements that have only two square roots are the non-zero elements that happen to be a multiple of either $p$ or $q$. Of course, it is extremely improbable to hit one such element out of (bad) luck.
$endgroup$
– Thomas Pornin
Dec 19 '18 at 13:37
$begingroup$
@ThomasPornin You are of course correct.
$endgroup$
– Maeher
Dec 19 '18 at 13:44
1
$begingroup$
The last sentence might be worth emphasizing: unlike RSA, the Rabin cryptosystem is provably as hard as factoring (i.e. breaking it provides efficient factoring as a side effect).
$endgroup$
– R..
Dec 19 '18 at 16:25
$begingroup$
@R.. I left that out because it did not seem particularly relevant to the question being asked, but I added a comment about it now.
$endgroup$
– Maeher
Dec 19 '18 at 16:35
$begingroup$
@Maeher: Thanks. I think it's nice because it confirms whatever suspicion the OP had that 2 is actually an interesting and productive choice of exponent.
$endgroup$
– R..
Dec 19 '18 at 16:45
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: "281"
};
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: false,
noModals: true,
showLowRepImageUploadWarning: true,
reputationToPostImages: null,
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%2fcrypto.stackexchange.com%2fquestions%2f65983%2frsa-using-2-as-a-public-exponent%23new-answer', 'question_page');
}
);
Post as a guest
Required, but never shown
1 Answer
1
active
oldest
votes
1 Answer
1
active
oldest
votes
active
oldest
votes
active
oldest
votes
$begingroup$
It is not that RSA becomes insecure when used with public exponent $2$. (In fact, the Rabin Cryptosystem does exactly that.) It's that it doesn't actually work.
The problem is that for $N = pq$ for two primes $p$ and $q$, the function $f : x mapsto x^2 bmod N$ is not injective. So it is impossible to invert uniquely. In fact, most elements of the function's range (the set of perfect squares) have $4$ preimages under $f$. (As pointed out by Thomas Pornin, the multiples of $p$ and $q$ have $2$, while $0$ has only one.)
We can get around this problem by choosing $pequiv qequiv 3 bmod 4$ and restricting the domain to the set of quadratic residues. In this case, the function is a trapdoor permutation over the set of quadratic residues if factoring is hard.
One might note, that this is actually a better guarantee than the one we have for the RSA trapdoor permutation, where the security is not known to be implied by the hardness of factoring.
answered Dec 19 '18 at 13:19
MaeherMaeher
3,60411830
$endgroup$
5
$begingroup$
Technically, most elements have 4 square roots, but some have only two, and zero has only one. The elements that have only two square roots are the non-zero elements that happen to be a multiple of either $p$ or $q$. Of course, it is extremely improbable to hit one such element out of (bad) luck.
$endgroup$
– Thomas Pornin
Dec 19 '18 at 13:37
$begingroup$
@ThomasPornin You are of course correct.
$endgroup$
– Maeher
Dec 19 '18 at 13:44
1
$begingroup$
The last sentence might be worth emphasizing: unlike RSA, the Rabin cryptosystem is provably as hard as factoring (i.e. breaking it provides efficient factoring as a side effect).
$endgroup$
– R..
Dec 19 '18 at 16:25
$begingroup$
@R.. I left that out because it did not seem particularly relevant to the question being asked, but I added a comment about it now.
$endgroup$
– Maeher
Dec 19 '18 at 16:35
$begingroup$
@Maeher: Thanks. I think it's nice because it confirms whatever suspicion the OP had that 2 is actually an interesting and productive choice of exponent.
$endgroup$
– R..
Dec 19 '18 at 16:45
add a comment |
$begingroup$
It is not that RSA becomes insecure when used with public exponent $2$. (In fact, the Rabin Cryptosystem does exactly that.) It's that it doesn't actually work.
The problem is that for $N = pq$ for two primes $p$ and $q$, the function $f : x mapsto x^2 bmod N$ is not injective. So it is impossible to invert uniquely. In fact, most elements of the function's range (the set of perfect squares) have $4$ preimages under $f$. (As pointed out by Thomas Pornin, the multiples of $p$ and $q$ have $2$, while $0$ has only one.)
We can get around this problem by choosing $pequiv qequiv 3 bmod 4$ and restricting the domain to the set of quadratic residues. In this case, the function is a trapdoor permutation over the set of quadratic residues if factoring is hard.
One might note, that this is actually a better guarantee than the one we have for the RSA trapdoor permutation, where the security is not known to be implied by the hardness of factoring.
answered Dec 19 '18 at 13:19
MaeherMaeher
3,60411830
$endgroup$
5
$begingroup$
Technically, most elements have 4 square roots, but some have only two, and zero has only one. The elements that have only two square roots are the non-zero elements that happen to be a multiple of either $p$ or $q$. Of course, it is extremely improbable to hit one such element out of (bad) luck.
$endgroup$
– Thomas Pornin
Dec 19 '18 at 13:37
$begingroup$
@ThomasPornin You are of course correct.
$endgroup$
– Maeher
Dec 19 '18 at 13:44
1
$begingroup$
The last sentence might be worth emphasizing: unlike RSA, the Rabin cryptosystem is provably as hard as factoring (i.e. breaking it provides efficient factoring as a side effect).
$endgroup$
– R..
Dec 19 '18 at 16:25
$begingroup$
@R.. I left that out because it did not seem particularly relevant to the question being asked, but I added a comment about it now.
$endgroup$
– Maeher
Dec 19 '18 at 16:35
$begingroup$
@Maeher: Thanks. I think it's nice because it confirms whatever suspicion the OP had that 2 is actually an interesting and productive choice of exponent.
$endgroup$
– R..
Dec 19 '18 at 16:45
add a comment |
$begingroup$
It is not that RSA becomes insecure when used with public exponent $2$. (In fact, the Rabin Cryptosystem does exactly that.) It's that it doesn't actually work.
The problem is that for $N = pq$ for two primes $p$ and $q$, the function $f : x mapsto x^2 bmod N$ is not injective. So it is impossible to invert uniquely. In fact, most elements of the function's range (the set of perfect squares) have $4$ preimages under $f$. (As pointed out by Thomas Pornin, the multiples of $p$ and $q$ have $2$, while $0$ has only one.)
We can get around this problem by choosing $pequiv qequiv 3 bmod 4$ and restricting the domain to the set of quadratic residues. In this case, the function is a trapdoor permutation over the set of quadratic residues if factoring is hard.
One might note, that this is actually a better guarantee than the one we have for the RSA trapdoor permutation, where the security is not known to be implied by the hardness of factoring.
answered Dec 19 '18 at 13:19
MaeherMaeher
3,60411830
$endgroup$
It is not that RSA becomes insecure when used with public exponent $2$. (In fact, the Rabin Cryptosystem does exactly that.) It's that it doesn't actually work.
The problem is that for $N = pq$ for two primes $p$ and $q$, the function $f : x mapsto x^2 bmod N$ is not injective. So it is impossible to invert uniquely. In fact, most elements of the function's range (the set of perfect squares) have $4$ preimages under $f$. (As pointed out by Thomas Pornin, the multiples of $p$ and $q$ have $2$, while $0$ has only one.)
We can get around this problem by choosing $pequiv qequiv 3 bmod 4$ and restricting the domain to the set of quadratic residues. In this case, the function is a trapdoor permutation over the set of quadratic residues if factoring is hard.
One might note, that this is actually a better guarantee than the one we have for the RSA trapdoor permutation, where the security is not known to be implied by the hardness of factoring.
answered Dec 19 '18 at 13:19
MaeherMaeher
3,60411830
edited Dec 19 '18 at 16:28
answered Dec 19 '18 at 13:19
MaeherMaeher
3,60411830
answered Dec 19 '18 at 13:19
MaeherMaeher
3,60411830
answered Dec 19 '18 at 13:19
MaeherMaeher
3,60411830
3,60411830
5
$begingroup$
Technically, most elements have 4 square roots, but some have only two, and zero has only one. The elements that have only two square roots are the non-zero elements that happen to be a multiple of either $p$ or $q$. Of course, it is extremely improbable to hit one such element out of (bad) luck.
$endgroup$
– Thomas Pornin
Dec 19 '18 at 13:37
$begingroup$
@ThomasPornin You are of course correct.
$endgroup$
– Maeher
Dec 19 '18 at 13:44
1
$begingroup$
The last sentence might be worth emphasizing: unlike RSA, the Rabin cryptosystem is provably as hard as factoring (i.e. breaking it provides efficient factoring as a side effect).
$endgroup$
– R..
Dec 19 '18 at 16:25
$begingroup$
@R.. I left that out because it did not seem particularly relevant to the question being asked, but I added a comment about it now.
$endgroup$
– Maeher
Dec 19 '18 at 16:35
$begingroup$
@Maeher: Thanks. I think it's nice because it confirms whatever suspicion the OP had that 2 is actually an interesting and productive choice of exponent.
$endgroup$
– R..
Dec 19 '18 at 16:45
add a comment |
5
$begingroup$
Technically, most elements have 4 square roots, but some have only two, and zero has only one. The elements that have only two square roots are the non-zero elements that happen to be a multiple of either $p$ or $q$. Of course, it is extremely improbable to hit one such element out of (bad) luck.
$endgroup$
– Thomas Pornin
Dec 19 '18 at 13:37
$begingroup$
@ThomasPornin You are of course correct.
$endgroup$
– Maeher
Dec 19 '18 at 13:44
1
$begingroup$
The last sentence might be worth emphasizing: unlike RSA, the Rabin cryptosystem is provably as hard as factoring (i.e. breaking it provides efficient factoring as a side effect).
$endgroup$
– R..
Dec 19 '18 at 16:25
$begingroup$
@R.. I left that out because it did not seem particularly relevant to the question being asked, but I added a comment about it now.
$endgroup$
– Maeher
Dec 19 '18 at 16:35
$begingroup$
@Maeher: Thanks. I think it's nice because it confirms whatever suspicion the OP had that 2 is actually an interesting and productive choice of exponent.
$endgroup$
– R..
Dec 19 '18 at 16:45
5
5
$begingroup$
Technically, most elements have 4 square roots, but some have only two, and zero has only one. The elements that have only two square roots are the non-zero elements that happen to be a multiple of either $p$ or $q$. Of course, it is extremely improbable to hit one such element out of (bad) luck.
$endgroup$
– Thomas Pornin
Dec 19 '18 at 13:37
$begingroup$
Technically, most elements have 4 square roots, but some have only two, and zero has only one. The elements that have only two square roots are the non-zero elements that happen to be a multiple of either $p$ or $q$. Of course, it is extremely improbable to hit one such element out of (bad) luck.
$endgroup$
– Thomas Pornin
Dec 19 '18 at 13:37
$begingroup$
@ThomasPornin You are of course correct.
$endgroup$
– Maeher
Dec 19 '18 at 13:44
$begingroup$
@ThomasPornin You are of course correct.
$endgroup$
– Maeher
Dec 19 '18 at 13:44
1
1
$begingroup$
The last sentence might be worth emphasizing: unlike RSA, the Rabin cryptosystem is provably as hard as factoring (i.e. breaking it provides efficient factoring as a side effect).
$endgroup$
– R..
Dec 19 '18 at 16:25
$begingroup$
The last sentence might be worth emphasizing: unlike RSA, the Rabin cryptosystem is provably as hard as factoring (i.e. breaking it provides efficient factoring as a side effect).
$endgroup$
– R..
Dec 19 '18 at 16:25
$begingroup$
@R.. I left that out because it did not seem particularly relevant to the question being asked, but I added a comment about it now.
$endgroup$
– Maeher
Dec 19 '18 at 16:35
$begingroup$
@R.. I left that out because it did not seem particularly relevant to the question being asked, but I added a comment about it now.
$endgroup$
– Maeher
Dec 19 '18 at 16:35
$begingroup$
@Maeher: Thanks. I think it's nice because it confirms whatever suspicion the OP had that 2 is actually an interesting and productive choice of exponent.
$endgroup$
– R..
Dec 19 '18 at 16:45
$begingroup$
@Maeher: Thanks. I think it's nice because it confirms whatever suspicion the OP had that 2 is actually an interesting and productive choice of exponent.
$endgroup$
– R..
Dec 19 '18 at 16:45
add a comment |
Thanks for contributing an answer to Cryptography 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%2fcrypto.stackexchange.com%2fquestions%2f65983%2frsa-using-2-as-a-public-exponent%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
3
$begingroup$
$gcd(2,(p-1)(q-1)) =$?
$endgroup$
– kelalaka
Dec 19 '18 at 12:41
$begingroup$
if p is odd a q is even it will be 1. if both are odd/both are even it will be 2?
$endgroup$
– S. L.
Dec 19 '18 at 12:46
$begingroup$
$p$ and $q$ are prime >2 implies both odd.
$endgroup$
– kelalaka
Dec 19 '18 at 12:46
$begingroup$
right of course! facepalm OK so what weakness would that bring? Edit: scratch that, it would lead to any ct no being uniquely decryptable
$endgroup$
– S. L.
Dec 19 '18 at 12:50
5
$begingroup$
en.wikipedia.org/wiki/Rabin_cryptosystem
$endgroup$
– Maeher
Dec 19 '18 at 12:52