RSA find public exponentRSA calculate public exponentHow can we find Public key have only 8 or 16bits? How many messages does Eve need to know the Public key in RSA?Calculating RSA private exponent when given public exponent and the modulus factors using extended euclidLow Public Exponent Attack for RSAlow-exponent RSAFinding Private Key $d$ using RSADeduce modulus N from public exponent and encrypted dataWhy is RSA private exponent much larger than RSA public exponent?RSA: large private exponent often yields large public exponentRSA decryption with small exponent - no “public keys”How to calculate Public Key exponent if I have p, q, Dp, Dq, QInv?
Are Boeing 737-800’s grounded?
Fizzy, soft, pop and still drinks
What makes accurate emulation of old systems a difficult task?
How to get a plain text file version of a CP/M .BAS (M-BASIC) program?
Error message with tabularx
How could Tony Stark make this in Endgame?
Combinable filters
Why do Computer Science majors learn Calculus?
Who is the Umpire in this picture?
Packing rectangles: Does rotation ever help?
Why do games have consumables?
How come there are so many candidates for the 2020 Democratic party presidential nomination?
What's the polite way to say "I need to urinate"?
Is there any limitation with Arduino Nano serial communication distance?
What happened to Captain America in Endgame?
How can Republicans who favour free markets, consistently express anger when they don't like the outcome of that choice?
US visa is under administrative processing, I need the passport back ASAP
A Note on N!
Why does nature favour the Laplacian?
Will a top journal at least read my introduction?
How to stop co-workers from teasing me because I know Russian?
Apply MapThread to all but one variable
Was there a shared-world project before "Thieves World"?
Mac Pro install disk keeps ejecting itself
RSA find public exponent
RSA calculate public exponentHow can we find Public key have only 8 or 16bits? How many messages does Eve need to know the Public key in RSA?Calculating RSA private exponent when given public exponent and the modulus factors using extended euclidLow Public Exponent Attack for RSAlow-exponent RSAFinding Private Key $d$ using RSADeduce modulus N from public exponent and encrypted dataWhy is RSA private exponent much larger than RSA public exponent?RSA: large private exponent often yields large public exponentRSA decryption with small exponent - no “public keys”How to calculate Public Key exponent if I have p, q, Dp, Dq, QInv?
$begingroup$
Suppose I have an encryption oracle which can encrypt $m^e mod n$ for any $m$. I know $n$ and I know $varphi(n)$. However the public exponent $e$ is secret. Is it possible to figure out it's value when $e$ is not bruteforce-able?
rsa
asked Apr 20 at 14:20
Jannes BraetJannes Braet
1183
$endgroup$
add a comment |
$begingroup$
Suppose I have an encryption oracle which can encrypt $m^e mod n$ for any $m$. I know $n$ and I know $varphi(n)$. However the public exponent $e$ is secret. Is it possible to figure out it's value when $e$ is not bruteforce-able?
rsa
asked Apr 20 at 14:20
Jannes BraetJannes Braet
1183
$endgroup$
add a comment |
$begingroup$
Suppose I have an encryption oracle which can encrypt $m^e mod n$ for any $m$. I know $n$ and I know $varphi(n)$. However the public exponent $e$ is secret. Is it possible to figure out it's value when $e$ is not bruteforce-able?
rsa
asked Apr 20 at 14:20
Jannes BraetJannes Braet
1183
$endgroup$
Suppose I have an encryption oracle which can encrypt $m^e mod n$ for any $m$. I know $n$ and I know $varphi(n)$. However the public exponent $e$ is secret. Is it possible to figure out it's value when $e$ is not bruteforce-able?
rsa
rsa
asked Apr 20 at 14:20
Jannes BraetJannes Braet
1183
asked Apr 20 at 14:20
Jannes BraetJannes Braet
1183
asked Apr 20 at 14:20
Jannes BraetJannes Braet
1183
asked Apr 20 at 14:20
Jannes BraetJannes Braet
1183
asked Apr 20 at 14:20
Jannes BraetJannes Braet
1183
1183
add a comment |
add a comment |
2 Answers
2
active
oldest
votes
$begingroup$
Is it possible to figure out it's value when $e$ is not bruteforce-able?
It depends.
First note that knowing you can easily factor $n$ given that you also know $varphi(n)$ (2-prime case).
Next note that $mathbb Z_n^*congmathbb Z_p^*times mathbb Z_q^*$ (by the CRT), this means that doing component-wise operations on the pairs from the latter groups is a different way of writing an operation in the former group. Finally note that the bit-length of $p,q$ is about half of that of $n$ (usually).
Now that the preparation is through, the first thing to realize is that the given scenario is a standard discrete-logarithm problem with a composite modulus. Also note that the power of being able to choose the base shouldn't make the attacker stronger. Next thanks to the congruence and us knowing $p,q$ we can just map the problem to two smaller problems, finding $e$ given $xmapsto x^ebmod p$ and the same for $bmod q$. Assuming the factors are reasonably small, a standard GNFS attack may work out, but with a standard RSA modulus of two primes of similar length resulting in a 2048-bit modulus this doesn't work.
Otherwise, this is a hard problem because it essentially constitutes a key-recovery attack on the Pohlig-Hellman cipher in a chosen-plaintext scenario.
answered Apr 20 at 14:50
SEJPM♦SEJPM
29.8k659142
$endgroup$
add a comment |
$begingroup$
Assuming you don’t know the private exponent as well; you have to treat $e$ as a random variable, as it can potentially be any number from a very large domain.
Please note that: If the implementation of RSA you’re using is a standard implementation; your encryption exponent is a fixed value, you can try the standard public exponents.
answered Apr 20 at 14:39
zetaprimezetaprime
386215
$endgroup$
1
$begingroup$
The note is somewhat unnecessary as the fixed values would be easy to find through brute force, and the question states that brute force is not feasible.
$endgroup$
– Maarten Bodewes♦
Apr 20 at 16:33
add a comment |
Your Answer
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%2f68916%2frsa-find-public-exponent%23new-answer', 'question_page');
);
Post as a guest
Required, but never shown
2 Answers
2
active
oldest
votes
2 Answers
2
active
oldest
votes
active
oldest
votes
active
oldest
votes
$begingroup$
Is it possible to figure out it's value when $e$ is not bruteforce-able?
It depends.
First note that knowing you can easily factor $n$ given that you also know $varphi(n)$ (2-prime case).
Next note that $mathbb Z_n^*congmathbb Z_p^*times mathbb Z_q^*$ (by the CRT), this means that doing component-wise operations on the pairs from the latter groups is a different way of writing an operation in the former group. Finally note that the bit-length of $p,q$ is about half of that of $n$ (usually).
Now that the preparation is through, the first thing to realize is that the given scenario is a standard discrete-logarithm problem with a composite modulus. Also note that the power of being able to choose the base shouldn't make the attacker stronger. Next thanks to the congruence and us knowing $p,q$ we can just map the problem to two smaller problems, finding $e$ given $xmapsto x^ebmod p$ and the same for $bmod q$. Assuming the factors are reasonably small, a standard GNFS attack may work out, but with a standard RSA modulus of two primes of similar length resulting in a 2048-bit modulus this doesn't work.
Otherwise, this is a hard problem because it essentially constitutes a key-recovery attack on the Pohlig-Hellman cipher in a chosen-plaintext scenario.
answered Apr 20 at 14:50
SEJPM♦SEJPM
29.8k659142
$endgroup$
add a comment |
$begingroup$
Is it possible to figure out it's value when $e$ is not bruteforce-able?
It depends.
First note that knowing you can easily factor $n$ given that you also know $varphi(n)$ (2-prime case).
Next note that $mathbb Z_n^*congmathbb Z_p^*times mathbb Z_q^*$ (by the CRT), this means that doing component-wise operations on the pairs from the latter groups is a different way of writing an operation in the former group. Finally note that the bit-length of $p,q$ is about half of that of $n$ (usually).
Now that the preparation is through, the first thing to realize is that the given scenario is a standard discrete-logarithm problem with a composite modulus. Also note that the power of being able to choose the base shouldn't make the attacker stronger. Next thanks to the congruence and us knowing $p,q$ we can just map the problem to two smaller problems, finding $e$ given $xmapsto x^ebmod p$ and the same for $bmod q$. Assuming the factors are reasonably small, a standard GNFS attack may work out, but with a standard RSA modulus of two primes of similar length resulting in a 2048-bit modulus this doesn't work.
Otherwise, this is a hard problem because it essentially constitutes a key-recovery attack on the Pohlig-Hellman cipher in a chosen-plaintext scenario.
answered Apr 20 at 14:50
SEJPM♦SEJPM
29.8k659142
$endgroup$
add a comment |
$begingroup$
Is it possible to figure out it's value when $e$ is not bruteforce-able?
It depends.
First note that knowing you can easily factor $n$ given that you also know $varphi(n)$ (2-prime case).
Next note that $mathbb Z_n^*congmathbb Z_p^*times mathbb Z_q^*$ (by the CRT), this means that doing component-wise operations on the pairs from the latter groups is a different way of writing an operation in the former group. Finally note that the bit-length of $p,q$ is about half of that of $n$ (usually).
Now that the preparation is through, the first thing to realize is that the given scenario is a standard discrete-logarithm problem with a composite modulus. Also note that the power of being able to choose the base shouldn't make the attacker stronger. Next thanks to the congruence and us knowing $p,q$ we can just map the problem to two smaller problems, finding $e$ given $xmapsto x^ebmod p$ and the same for $bmod q$. Assuming the factors are reasonably small, a standard GNFS attack may work out, but with a standard RSA modulus of two primes of similar length resulting in a 2048-bit modulus this doesn't work.
Otherwise, this is a hard problem because it essentially constitutes a key-recovery attack on the Pohlig-Hellman cipher in a chosen-plaintext scenario.
answered Apr 20 at 14:50
SEJPM♦SEJPM
29.8k659142
$endgroup$
Is it possible to figure out it's value when $e$ is not bruteforce-able?
It depends.
First note that knowing you can easily factor $n$ given that you also know $varphi(n)$ (2-prime case).
Next note that $mathbb Z_n^*congmathbb Z_p^*times mathbb Z_q^*$ (by the CRT), this means that doing component-wise operations on the pairs from the latter groups is a different way of writing an operation in the former group. Finally note that the bit-length of $p,q$ is about half of that of $n$ (usually).
Now that the preparation is through, the first thing to realize is that the given scenario is a standard discrete-logarithm problem with a composite modulus. Also note that the power of being able to choose the base shouldn't make the attacker stronger. Next thanks to the congruence and us knowing $p,q$ we can just map the problem to two smaller problems, finding $e$ given $xmapsto x^ebmod p$ and the same for $bmod q$. Assuming the factors are reasonably small, a standard GNFS attack may work out, but with a standard RSA modulus of two primes of similar length resulting in a 2048-bit modulus this doesn't work.
Otherwise, this is a hard problem because it essentially constitutes a key-recovery attack on the Pohlig-Hellman cipher in a chosen-plaintext scenario.
answered Apr 20 at 14:50
SEJPM♦SEJPM
29.8k659142
answered Apr 20 at 14:50
SEJPM♦SEJPM
29.8k659142
answered Apr 20 at 14:50
SEJPM♦SEJPM
29.8k659142
answered Apr 20 at 14:50
SEJPM♦SEJPM
29.8k659142
29.8k659142
add a comment |
add a comment |
$begingroup$
Assuming you don’t know the private exponent as well; you have to treat $e$ as a random variable, as it can potentially be any number from a very large domain.
Please note that: If the implementation of RSA you’re using is a standard implementation; your encryption exponent is a fixed value, you can try the standard public exponents.
answered Apr 20 at 14:39
zetaprimezetaprime
386215
$endgroup$
1
$begingroup$
The note is somewhat unnecessary as the fixed values would be easy to find through brute force, and the question states that brute force is not feasible.
$endgroup$
– Maarten Bodewes♦
Apr 20 at 16:33
add a comment |
$begingroup$
Assuming you don’t know the private exponent as well; you have to treat $e$ as a random variable, as it can potentially be any number from a very large domain.
Please note that: If the implementation of RSA you’re using is a standard implementation; your encryption exponent is a fixed value, you can try the standard public exponents.
answered Apr 20 at 14:39
zetaprimezetaprime
386215
$endgroup$
1
$begingroup$
The note is somewhat unnecessary as the fixed values would be easy to find through brute force, and the question states that brute force is not feasible.
$endgroup$
– Maarten Bodewes♦
Apr 20 at 16:33
add a comment |
$begingroup$
Assuming you don’t know the private exponent as well; you have to treat $e$ as a random variable, as it can potentially be any number from a very large domain.
Please note that: If the implementation of RSA you’re using is a standard implementation; your encryption exponent is a fixed value, you can try the standard public exponents.
answered Apr 20 at 14:39
zetaprimezetaprime
386215
$endgroup$
Assuming you don’t know the private exponent as well; you have to treat $e$ as a random variable, as it can potentially be any number from a very large domain.
Please note that: If the implementation of RSA you’re using is a standard implementation; your encryption exponent is a fixed value, you can try the standard public exponents.
answered Apr 20 at 14:39
zetaprimezetaprime
386215
answered Apr 20 at 14:39
zetaprimezetaprime
386215
answered Apr 20 at 14:39
zetaprimezetaprime
386215
answered Apr 20 at 14:39
zetaprimezetaprime
386215
386215
1
$begingroup$
The note is somewhat unnecessary as the fixed values would be easy to find through brute force, and the question states that brute force is not feasible.
$endgroup$
– Maarten Bodewes♦
Apr 20 at 16:33
add a comment |
1
$begingroup$
The note is somewhat unnecessary as the fixed values would be easy to find through brute force, and the question states that brute force is not feasible.
$endgroup$
– Maarten Bodewes♦
Apr 20 at 16:33
1
1
$begingroup$
The note is somewhat unnecessary as the fixed values would be easy to find through brute force, and the question states that brute force is not feasible.
$endgroup$
– Maarten Bodewes♦
Apr 20 at 16:33
$begingroup$
The note is somewhat unnecessary as the fixed values would be easy to find through brute force, and the question states that brute force is not feasible.
$endgroup$
– Maarten Bodewes♦
Apr 20 at 16:33
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%2f68916%2frsa-find-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
