Timeline for Finding public exponent e
Current License: CC BY-SA 3.0
14 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| Apr 13, 2017 at 12:48 | history | edited | CommunityBot |
replaced http://crypto.stackexchange.com/ with https://crypto.stackexchange.com/
|
|
| May 25, 2015 at 21:28 | vote | accept | Maarten Bodewes♦ | ||
| May 25, 2015 at 17:04 | comment | added | SEJPM | I've no idea what you're talking about :) I just provided the reference. I hope wikipedia and the original paper will eliminate all problems. | |
| May 25, 2015 at 17:01 | answer | added | SEJPM | timeline score: 3 | |
| May 25, 2015 at 16:35 | comment | added | SEJPM | You don't know $p,q$. If you would, you could calculate $e$ in poly-time. (If that wasn't what you meant with the above comment, then idk what you meant) The "check" algorithm I had in mind was to "decrypt" a message using your $d$ and then "re-encrypt" using the above mentioned order, maybe even in a "clever" way like $m \equiv m$? No? Use the previous $m, m^2, m^3$ and multiply by $m$ for the next check..., poncho was faster :( | |
| May 25, 2015 at 16:33 | comment | added | poncho | We know that for the correct $e, d$, we have $z^{ed} = z$. The obvious way to validate a $e$ is to select a random $z$, compute $z^d$, and then compare $(z^d)^e$ to $z$. This makes the brute-forcing of all $e < 2^{32}$ not too horribly expensive (as checking the next $e$ is just a modular multiplication and compare). If you want to put in the effort, using the big-step/little-step makes it practical to test this for all $e < 2^{64}$. However, if we know that $e> 2^{32}$, going directly to Weiner's may make more sense | |
| May 25, 2015 at 16:29 | comment | added | Maarten Bodewes♦ | Yep, that's about the gist of it I guess. Would the best way of validating the most used ones to calculate $n$ from $p$ and $q$ and then compare? That seems slow, just performing modular exponentiation seems faster. | |
| May 25, 2015 at 16:24 | comment | added | SEJPM | So you're in the exact same situation as if you would know $(e,n)$ and you would know that $d$ probably is rather small. There's no known algorithm to solve this problem fast in every circumstance, as this would mean you'd be able to break RSA. IMO the best route would be to try the most used $e$, like $3,17,2^{16}+1$, then brute-force the first $\approx 2^{32}$ ones and then try to apply Wieners's attack, if $log_2(e)<160$ | |
| May 25, 2015 at 16:06 | history | edited | Maarten Bodewes♦ | CC BY-SA 3.0 |
added 32 characters in body
|
| May 25, 2015 at 16:04 | comment | added | Maarten Bodewes♦ | @SOJPM Right, that's the problem. I've got $n$ and $d$. Note that $n$ and $d$ are supposed to have been correctly calculated. If I could calculate $p$ and $q$ then my problems would disappear, but $p$ and $q$ calculation from $n$ and $d$ seems to rely on $e$ being available. | |
| May 25, 2015 at 16:02 | comment | added | SEJPM | As calculating $e\equiv d^{-1} \pmod {\varphi(n)}$ would be too easy I guess a plain (non-CRT) private key consists solely of $(d,n)$. In this case all standard attacks against weak RSA private exponents would apply. | |
| May 25, 2015 at 15:47 | comment | added | SEJPM | so does one know $n$, does one know $p,q$, does one know $\varphi(n)=(p-1)(q-1)$ or is it supposed to be "without modulus"? | |
| May 25, 2015 at 15:37 | comment | added | Maarten Bodewes♦ | yes, I've got some ideas like checking the often used ones first and then check a simple encrypt/decrypt, but I would like the answers not to be influenced by my non-optimal ideas :) And yes, I am aware that this may be hard to do if the public exponent is very large, but this is not commonly the case. | |
| May 25, 2015 at 15:35 | history | asked | Maarten Bodewes♦ | CC BY-SA 3.0 |