Is RSA provably secure in the sense of Douglas Stinson's ``provable security''?
up vote
3
down vote
favorite
Here's a quote from Douglas Stinson:
“[i]f a cryptosystem can be ‘broken’ in some specific way, then it
would be possible to efficiently solve some well-studied problem that
is thought to be difficult. For example, it may be possible to prove a
statement of the type “a given cryptosystem is secure if a given
integer n cannot be factored.” [...] [B]ut it must be understood that
this approach only provides a proof of security relative to some other
problem, not an absolute proof of security. This is a similar
situation to proving that a problem is NP-complete [...].”
Source: Stinson, D. R. (2006). Cryptography, Theory and Practice. Chapman
and Hall, CRC, 3rd edition. Chapter 2, section 2.1, page 45.
Does this apply to RSA? Suppose I find the private exponent by some other way other than factoring $n$. Then I would have broken RSA without factoring.
So although Stinson's example mentions factoring, we can't immediately think of RSA here because there's no proof that factoring is the only way to recover a private key. What do you say?
rsa provable-security
asked Dec 8 at 18:31
user45491
595
|
show 2 more comments
up vote
3
down vote
favorite
Here's a quote from Douglas Stinson:
“[i]f a cryptosystem can be ‘broken’ in some specific way, then it
would be possible to efficiently solve some well-studied problem that
is thought to be difficult. For example, it may be possible to prove a
statement of the type “a given cryptosystem is secure if a given
integer n cannot be factored.” [...] [B]ut it must be understood that
this approach only provides a proof of security relative to some other
problem, not an absolute proof of security. This is a similar
situation to proving that a problem is NP-complete [...].”
Source: Stinson, D. R. (2006). Cryptography, Theory and Practice. Chapman
and Hall, CRC, 3rd edition. Chapter 2, section 2.1, page 45.
Does this apply to RSA? Suppose I find the private exponent by some other way other than factoring $n$. Then I would have broken RSA without factoring.
So although Stinson's example mentions factoring, we can't immediately think of RSA here because there's no proof that factoring is the only way to recover a private key. What do you say?
rsa provable-security
asked Dec 8 at 18:31
user45491
595
1
Well, the security of RSA (with a secure padding scheme) is provably reducible to the RSA problem. But I'm not sure if that's really the kind of answer you're looking for.
– Ilmari Karonen
Dec 8 at 18:40
1
@IlmariKaronen Technically the RSA problem is a "well-studied problem that is thought to be difficult".
– Maeher
Dec 8 at 18:42
@IlmariKaronen Perhaps I could put my question this way: if I have $n$, the composite, $e$ the public exponent and $d$, the private exponent, is there a known method to find $phi(n)$ (or to factor $n$)?
– user45491
Dec 8 at 18:48
4
Yes, there is.
– Ilmari Karonen
Dec 8 at 18:53
2
@user45491 no, finding a private key ($d$) is not the necessary condition for broking PKE scheme. E.g., if an attacker is able to find just a forgery - a signature of some message, the scheme is already broken, although the attacker can't find the private key.
– Mihas Koypish
Dec 8 at 20:02
|
show 2 more comments
up vote
3
down vote
favorite
up vote
3
down vote
favorite
Here's a quote from Douglas Stinson:
“[i]f a cryptosystem can be ‘broken’ in some specific way, then it
would be possible to efficiently solve some well-studied problem that
is thought to be difficult. For example, it may be possible to prove a
statement of the type “a given cryptosystem is secure if a given
integer n cannot be factored.” [...] [B]ut it must be understood that
this approach only provides a proof of security relative to some other
problem, not an absolute proof of security. This is a similar
situation to proving that a problem is NP-complete [...].”
Source: Stinson, D. R. (2006). Cryptography, Theory and Practice. Chapman
and Hall, CRC, 3rd edition. Chapter 2, section 2.1, page 45.
Does this apply to RSA? Suppose I find the private exponent by some other way other than factoring $n$. Then I would have broken RSA without factoring.
So although Stinson's example mentions factoring, we can't immediately think of RSA here because there's no proof that factoring is the only way to recover a private key. What do you say?
rsa provable-security
asked Dec 8 at 18:31
user45491
595
Here's a quote from Douglas Stinson:
“[i]f a cryptosystem can be ‘broken’ in some specific way, then it
would be possible to efficiently solve some well-studied problem that
is thought to be difficult. For example, it may be possible to prove a
statement of the type “a given cryptosystem is secure if a given
integer n cannot be factored.” [...] [B]ut it must be understood that
this approach only provides a proof of security relative to some other
problem, not an absolute proof of security. This is a similar
situation to proving that a problem is NP-complete [...].”
Source: Stinson, D. R. (2006). Cryptography, Theory and Practice. Chapman
and Hall, CRC, 3rd edition. Chapter 2, section 2.1, page 45.
Does this apply to RSA? Suppose I find the private exponent by some other way other than factoring $n$. Then I would have broken RSA without factoring.
So although Stinson's example mentions factoring, we can't immediately think of RSA here because there's no proof that factoring is the only way to recover a private key. What do you say?
rsa provable-security
rsa provable-security
asked Dec 8 at 18:31
user45491
595
asked Dec 8 at 18:31
user45491
595
asked Dec 8 at 18:31
user45491
595
asked Dec 8 at 18:31
user45491
595
asked Dec 8 at 18:31
user45491
595
595
1
Well, the security of RSA (with a secure padding scheme) is provably reducible to the RSA problem. But I'm not sure if that's really the kind of answer you're looking for.
– Ilmari Karonen
Dec 8 at 18:40
1
@IlmariKaronen Technically the RSA problem is a "well-studied problem that is thought to be difficult".
– Maeher
Dec 8 at 18:42
@IlmariKaronen Perhaps I could put my question this way: if I have $n$, the composite, $e$ the public exponent and $d$, the private exponent, is there a known method to find $phi(n)$ (or to factor $n$)?
– user45491
Dec 8 at 18:48
4
Yes, there is.
– Ilmari Karonen
Dec 8 at 18:53
2
@user45491 no, finding a private key ($d$) is not the necessary condition for broking PKE scheme. E.g., if an attacker is able to find just a forgery - a signature of some message, the scheme is already broken, although the attacker can't find the private key.
– Mihas Koypish
Dec 8 at 20:02
|
show 2 more comments
1
Well, the security of RSA (with a secure padding scheme) is provably reducible to the RSA problem. But I'm not sure if that's really the kind of answer you're looking for.
– Ilmari Karonen
Dec 8 at 18:40
1
@IlmariKaronen Technically the RSA problem is a "well-studied problem that is thought to be difficult".
– Maeher
Dec 8 at 18:42
@IlmariKaronen Perhaps I could put my question this way: if I have $n$, the composite, $e$ the public exponent and $d$, the private exponent, is there a known method to find $phi(n)$ (or to factor $n$)?
– user45491
Dec 8 at 18:48
4
Yes, there is.
– Ilmari Karonen
Dec 8 at 18:53
2
@user45491 no, finding a private key ($d$) is not the necessary condition for broking PKE scheme. E.g., if an attacker is able to find just a forgery - a signature of some message, the scheme is already broken, although the attacker can't find the private key.
– Mihas Koypish
Dec 8 at 20:02
1
1
Well, the security of RSA (with a secure padding scheme) is provably reducible to the RSA problem. But I'm not sure if that's really the kind of answer you're looking for.
– Ilmari Karonen
Dec 8 at 18:40
Well, the security of RSA (with a secure padding scheme) is provably reducible to the RSA problem. But I'm not sure if that's really the kind of answer you're looking for.
– Ilmari Karonen
Dec 8 at 18:40
1
1
@IlmariKaronen Technically the RSA problem is a "well-studied problem that is thought to be difficult".
– Maeher
Dec 8 at 18:42
@IlmariKaronen Technically the RSA problem is a "well-studied problem that is thought to be difficult".
– Maeher
Dec 8 at 18:42
@IlmariKaronen Perhaps I could put my question this way: if I have $n$, the composite, $e$ the public exponent and $d$, the private exponent, is there a known method to find $phi(n)$ (or to factor $n$)?
– user45491
Dec 8 at 18:48
@IlmariKaronen Perhaps I could put my question this way: if I have $n$, the composite, $e$ the public exponent and $d$, the private exponent, is there a known method to find $phi(n)$ (or to factor $n$)?
– user45491
Dec 8 at 18:48
4
4
Yes, there is.
– Ilmari Karonen
Dec 8 at 18:53
Yes, there is.
– Ilmari Karonen
Dec 8 at 18:53
2
2
@user45491 no, finding a private key ($d$) is not the necessary condition for broking PKE scheme. E.g., if an attacker is able to find just a forgery - a signature of some message, the scheme is already broken, although the attacker can't find the private key.
– Mihas Koypish
Dec 8 at 20:02
@user45491 no, finding a private key ($d$) is not the necessary condition for broking PKE scheme. E.g., if an attacker is able to find just a forgery - a signature of some message, the scheme is already broken, although the attacker can't find the private key.
– Mihas Koypish
Dec 8 at 20:02
|
show 2 more comments
1 Answer
1
active
oldest
votes
up vote
13
down vote
accepted
Every cryptosystem is "provably secure" under at least one hardness assumption: the assumption that it cannot be broken. Hence, the only question which matters is whether a cryptosystem is provably secure under a well-known and well-studied assumption.
This is kind of the case for RSA, but in a somewhat unsatisfying way: the IND-CPA security of RSA with appropriate padding can be reduced to the RSA problem (extracting $e$-th roots mod $n$), which is a well-studied assumption... But only because this is the one underlying the RSA cryptosystem, and we have been using the cryptosystem a lot in the past decades.
Something much more satisfying would be to reduce it to a problem which had long been studied before, in different context; the most natural such candidate is indeed factoring. Unfortunately, we do not know of a reduction from RSA to the hardness of factoring integers - in fact, we even have proofs that it will be hard to find such a reduction (in a well defined sense).
We have, however, many other cryptosystems which can be reduced to factoring; the earliest example of this kind is the cryptosystem of Rabin.
answered Dec 8 at 18:48
Geoffroy Couteau
7,82011532
The RSA problem asks us to recover the plain text m from (N, e). If I find a way to get d without factoring, I'll be able to recover any m. If I get d, I also factor N. This is not a reduction of RSA to factoring because there may some way to get m without getting d (and so without factoring N).
– user45491
Dec 10 at 23:46
Your first paragraph is very well put. Thank you. Your second paragraph is equally good. Your third paragraph I'm still grasping --- but I think I understood it, as expressed in my previous comment. Your last paragraph makes your answer the best thing I could get --- although I had to think about the whole thing for a couple of days. Thank you so much for sharing your very insightful knowledge. Very grateful.
– user45491
Dec 10 at 23:47
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',
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%2f64684%2fis-rsa-provably-secure-in-the-sense-of-douglas-stinsons-provable-security%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
up vote
13
down vote
accepted
Every cryptosystem is "provably secure" under at least one hardness assumption: the assumption that it cannot be broken. Hence, the only question which matters is whether a cryptosystem is provably secure under a well-known and well-studied assumption.
This is kind of the case for RSA, but in a somewhat unsatisfying way: the IND-CPA security of RSA with appropriate padding can be reduced to the RSA problem (extracting $e$-th roots mod $n$), which is a well-studied assumption... But only because this is the one underlying the RSA cryptosystem, and we have been using the cryptosystem a lot in the past decades.
Something much more satisfying would be to reduce it to a problem which had long been studied before, in different context; the most natural such candidate is indeed factoring. Unfortunately, we do not know of a reduction from RSA to the hardness of factoring integers - in fact, we even have proofs that it will be hard to find such a reduction (in a well defined sense).
We have, however, many other cryptosystems which can be reduced to factoring; the earliest example of this kind is the cryptosystem of Rabin.
answered Dec 8 at 18:48
Geoffroy Couteau
7,82011532
The RSA problem asks us to recover the plain text m from (N, e). If I find a way to get d without factoring, I'll be able to recover any m. If I get d, I also factor N. This is not a reduction of RSA to factoring because there may some way to get m without getting d (and so without factoring N).
– user45491
Dec 10 at 23:46
Your first paragraph is very well put. Thank you. Your second paragraph is equally good. Your third paragraph I'm still grasping --- but I think I understood it, as expressed in my previous comment. Your last paragraph makes your answer the best thing I could get --- although I had to think about the whole thing for a couple of days. Thank you so much for sharing your very insightful knowledge. Very grateful.
– user45491
Dec 10 at 23:47
add a comment |
up vote
13
down vote
accepted
Every cryptosystem is "provably secure" under at least one hardness assumption: the assumption that it cannot be broken. Hence, the only question which matters is whether a cryptosystem is provably secure under a well-known and well-studied assumption.
This is kind of the case for RSA, but in a somewhat unsatisfying way: the IND-CPA security of RSA with appropriate padding can be reduced to the RSA problem (extracting $e$-th roots mod $n$), which is a well-studied assumption... But only because this is the one underlying the RSA cryptosystem, and we have been using the cryptosystem a lot in the past decades.
Something much more satisfying would be to reduce it to a problem which had long been studied before, in different context; the most natural such candidate is indeed factoring. Unfortunately, we do not know of a reduction from RSA to the hardness of factoring integers - in fact, we even have proofs that it will be hard to find such a reduction (in a well defined sense).
We have, however, many other cryptosystems which can be reduced to factoring; the earliest example of this kind is the cryptosystem of Rabin.
answered Dec 8 at 18:48
Geoffroy Couteau
7,82011532
The RSA problem asks us to recover the plain text m from (N, e). If I find a way to get d without factoring, I'll be able to recover any m. If I get d, I also factor N. This is not a reduction of RSA to factoring because there may some way to get m without getting d (and so without factoring N).
– user45491
Dec 10 at 23:46
Your first paragraph is very well put. Thank you. Your second paragraph is equally good. Your third paragraph I'm still grasping --- but I think I understood it, as expressed in my previous comment. Your last paragraph makes your answer the best thing I could get --- although I had to think about the whole thing for a couple of days. Thank you so much for sharing your very insightful knowledge. Very grateful.
– user45491
Dec 10 at 23:47
add a comment |
up vote
13
down vote
accepted
up vote
13
down vote
accepted
Every cryptosystem is "provably secure" under at least one hardness assumption: the assumption that it cannot be broken. Hence, the only question which matters is whether a cryptosystem is provably secure under a well-known and well-studied assumption.
This is kind of the case for RSA, but in a somewhat unsatisfying way: the IND-CPA security of RSA with appropriate padding can be reduced to the RSA problem (extracting $e$-th roots mod $n$), which is a well-studied assumption... But only because this is the one underlying the RSA cryptosystem, and we have been using the cryptosystem a lot in the past decades.
Something much more satisfying would be to reduce it to a problem which had long been studied before, in different context; the most natural such candidate is indeed factoring. Unfortunately, we do not know of a reduction from RSA to the hardness of factoring integers - in fact, we even have proofs that it will be hard to find such a reduction (in a well defined sense).
We have, however, many other cryptosystems which can be reduced to factoring; the earliest example of this kind is the cryptosystem of Rabin.
answered Dec 8 at 18:48
Geoffroy Couteau
7,82011532
Every cryptosystem is "provably secure" under at least one hardness assumption: the assumption that it cannot be broken. Hence, the only question which matters is whether a cryptosystem is provably secure under a well-known and well-studied assumption.
This is kind of the case for RSA, but in a somewhat unsatisfying way: the IND-CPA security of RSA with appropriate padding can be reduced to the RSA problem (extracting $e$-th roots mod $n$), which is a well-studied assumption... But only because this is the one underlying the RSA cryptosystem, and we have been using the cryptosystem a lot in the past decades.
Something much more satisfying would be to reduce it to a problem which had long been studied before, in different context; the most natural such candidate is indeed factoring. Unfortunately, we do not know of a reduction from RSA to the hardness of factoring integers - in fact, we even have proofs that it will be hard to find such a reduction (in a well defined sense).
We have, however, many other cryptosystems which can be reduced to factoring; the earliest example of this kind is the cryptosystem of Rabin.
answered Dec 8 at 18:48
Geoffroy Couteau
7,82011532
answered Dec 8 at 18:48
Geoffroy Couteau
7,82011532
answered Dec 8 at 18:48
Geoffroy Couteau
7,82011532
answered Dec 8 at 18:48
Geoffroy Couteau
7,82011532
7,82011532
The RSA problem asks us to recover the plain text m from (N, e). If I find a way to get d without factoring, I'll be able to recover any m. If I get d, I also factor N. This is not a reduction of RSA to factoring because there may some way to get m without getting d (and so without factoring N).
– user45491
Dec 10 at 23:46
Your first paragraph is very well put. Thank you. Your second paragraph is equally good. Your third paragraph I'm still grasping --- but I think I understood it, as expressed in my previous comment. Your last paragraph makes your answer the best thing I could get --- although I had to think about the whole thing for a couple of days. Thank you so much for sharing your very insightful knowledge. Very grateful.
– user45491
Dec 10 at 23:47
add a comment |
The RSA problem asks us to recover the plain text m from (N, e). If I find a way to get d without factoring, I'll be able to recover any m. If I get d, I also factor N. This is not a reduction of RSA to factoring because there may some way to get m without getting d (and so without factoring N).
– user45491
Dec 10 at 23:46
Your first paragraph is very well put. Thank you. Your second paragraph is equally good. Your third paragraph I'm still grasping --- but I think I understood it, as expressed in my previous comment. Your last paragraph makes your answer the best thing I could get --- although I had to think about the whole thing for a couple of days. Thank you so much for sharing your very insightful knowledge. Very grateful.
– user45491
Dec 10 at 23:47
The RSA problem asks us to recover the plain text m from (N, e). If I find a way to get d without factoring, I'll be able to recover any m. If I get d, I also factor N. This is not a reduction of RSA to factoring because there may some way to get m without getting d (and so without factoring N).
– user45491
Dec 10 at 23:46
The RSA problem asks us to recover the plain text m from (N, e). If I find a way to get d without factoring, I'll be able to recover any m. If I get d, I also factor N. This is not a reduction of RSA to factoring because there may some way to get m without getting d (and so without factoring N).
– user45491
Dec 10 at 23:46
Your first paragraph is very well put. Thank you. Your second paragraph is equally good. Your third paragraph I'm still grasping --- but I think I understood it, as expressed in my previous comment. Your last paragraph makes your answer the best thing I could get --- although I had to think about the whole thing for a couple of days. Thank you so much for sharing your very insightful knowledge. Very grateful.
– user45491
Dec 10 at 23:47
Your first paragraph is very well put. Thank you. Your second paragraph is equally good. Your third paragraph I'm still grasping --- but I think I understood it, as expressed in my previous comment. Your last paragraph makes your answer the best thing I could get --- although I had to think about the whole thing for a couple of days. Thank you so much for sharing your very insightful knowledge. Very grateful.
– user45491
Dec 10 at 23:47
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.
Some of your past answers have not been well-received, and you're in danger of being blocked from answering.
Please pay close attention to the following guidance:
- 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.
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%2f64684%2fis-rsa-provably-secure-in-the-sense-of-douglas-stinsons-provable-security%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
1
Well, the security of RSA (with a secure padding scheme) is provably reducible to the RSA problem. But I'm not sure if that's really the kind of answer you're looking for.
– Ilmari Karonen
Dec 8 at 18:40
1
@IlmariKaronen Technically the RSA problem is a "well-studied problem that is thought to be difficult".
– Maeher
Dec 8 at 18:42
@IlmariKaronen Perhaps I could put my question this way: if I have $n$, the composite, $e$ the public exponent and $d$, the private exponent, is there a known method to find $phi(n)$ (or to factor $n$)?
– user45491
Dec 8 at 18:48
4
Yes, there is.
– Ilmari Karonen
Dec 8 at 18:53
2
@user45491 no, finding a private key ($d$) is not the necessary condition for broking PKE scheme. E.g., if an attacker is able to find just a forgery - a signature of some message, the scheme is already broken, although the attacker can't find the private key.
– Mihas Koypish
Dec 8 at 20:02