3
$\begingroup$

I am gonna write down formulas that I know and use to generate RSA keys.

  1. we choose $p$, $q$
  2. $N = p\cdot q$
  3. $\varphi(n) = (p-1)\cdot(q-1)$
  4. choose $e$ such as
    • $1 < e < \varphi(N)$
    • $e$ is coprime with $N$, $\varphi(n)$
  5. choose $d$ so that $d\cdot e\bmod\varphi(n)=1$

That's it. With these, if we have $p=2$ and $q=7$, I successfully get $d=11$ and $e=5$ which is correct.

Now Imagine, that I only have private key which is $(11,14)$ (that is $d=11$, $N=14$). How do I get $e=5$. I understand that with $d$ and $N$, you can't directly get $e$, but as RSA works, it tries different variants of $e$ , then checks and if it's valid, that's how you get public key from private key.

Can anyone explain to me what steps should I take here to figure out what $e$ could be and then from those, which $e$ should I choose ?

$\endgroup$
4
  • $\begingroup$ Note: You forgot $p\ne q$, which is necessary if you define $\varphi(n) = (p-1)\cdot(q-1)$, or want encryption/decryption to always work. The requirement that $e$ is coprime with $N$ is unusual. The requirement that $1<e<\varphi(n)$ is also slightly unusual for RSA as practiced, it's more usual to have $1<e<N$ (PKCS#1) or $2^{16}<e<2^{256}$ (FIPS 186-4). $\endgroup$
    – fgrieu
    Jul 10, 2021 at 8:52
  • $\begingroup$ If you've got a signature you can just test your guess by verifying it. That wont work for ciphertext though, at least not if you use a randomized padding scheme. With textbook RSA that might still work. I'm not sure if you can calculate $e$ if you've got nothing to verify against and if $e$ is chosen randomly. It might be possible to do something if it is chosen deterministically given this answer: guess $e$, calculate $p$ and $q$, check if it matches the deterministic algorithm. $\endgroup$
    – Maarten Bodewes
    Jul 10, 2021 at 9:10
  • $\begingroup$ What formula do I use so that at least I can start gessing e if I have d and N ? In my above formulas, it still doesn't make sense how I write a program that guesses e.. $\endgroup$ Jul 10, 2021 at 9:15
  • $\begingroup$ In practice, the private key consists of (at least) $p,q,$ and $e$. $d$ and $N$ can easily be computed from these, and are often stored along with $p,q,$ and $e$; but they are not essential. If all you have is $d$ and $N$, then you can't compute $e$ without factorising $N$. $\endgroup$
    – TonyK
    Jul 11, 2021 at 0:09

1 Answer 1

4
$\begingroup$

It's asked how, in RSA, one finds $e$ given $d$ and $N$. I'll ignore the question's requirement that $e$ is coprime with $N$, which is highly unusual and has no mathematical relevance. I'll also assume $p\ne q$, because it's necessary for the stated $\varphi(N)=(p-1)\cdot(q-1)$ to hold.

With the question's definition of RSA, the method to find $e$ goes

  • Factor $N$ to find $p$ and $q$
  • Compute $\varphi=(p-1)\cdot(q-1)$
  • Compute $e$ knowing $e\cdot d\bmod\varphi=1$ and $1<e<\varphi$. That $e$ is uniquely defined, and the modular inverse of $d$ in the multiplicative group of integer modulo $\varphi$. For small numbers, a working method is trial and error of small odd $e>1$. A more constructive method is the (half)-extended Euclidean algorithm, which computes $e=d^{-1}\bmod \varphi$ directly. For a practical algorithm that uses only non-negative integers:
    1. $a\gets d\bmod \varphi$ , $b\gets \varphi$ , $x\gets0$ and $y\gets1$
      Note: $a\cdot x+b\cdot y=\varphi$ will keep holding
    2. if $a=1$, then output "the desired inverse $e$ of $d$ modulo $\varphi$ is $y$" and stop
    3. If $a=0$, then output "the desired inverse $e$ of $d$ modulo $\varphi$ does not exist" and stop
    4. $r\gets\lfloor b/a\rfloor$
    5. $b\gets b-a\cdot r$ and $x\gets x+r\cdot y$
    6. if $b=1$, then output "the desired inverse $e$ of $d$ modulo $\varphi$ is $\varphi-x$" and stop
    7. If $b=0$, then output "the desired inverse $e$ of $d$ modulo $\varphi$ does not exist" and stop
    8. $r\gets\lfloor a/b\rfloor$
    9. $a\gets a-b\cdot r$ and $y\gets y+r\cdot x$
    10. Continue at 2

This same method is typically used to compute $d$ from $e$, since $d$ and $e$ are symmetric in $e\cdot d\bmod\varphi=1$. That's however not how $d=11$ was computed in the question; for some strange reason the question requires $e<\varphi(N)$ but not $d<\varphi(N)$, or the more usual $d<N$ or $d<\operatorname{lcm}(p-1,q-1)$.


Serious problem with this approach for RSA as practiced (thus very large $N$, at least hundreds decimal digits): It won't work, because $N$ will be so large that it can't be factored, thus $\varphi$ can't be computed in this way.

Also, the question's condition $e\cdot d\bmod\varphi(N)=1$ is a sufficient, but not a necessary condition for textbook RSA encryption using $(e,N)$ to be undone by RSA decryption using $(d,N)$, and vice versa. The necessary condition is $e\cdot d\bmod\lambda(N)=1$, where $\lambda(N)=\operatorname{lcm}(p-1,q-1)$. That condition is often used in practice: it's allowed by PKCS#1, and mandated by FIPS 186-4. Artificially small example: $N=341$, $e=7$, $d=13$ works just fine for textbook RSA encryption/decryption, yet $e\cdot d\bmod\varphi(N)=1$ does not hold (in this example $p=11$, $q=31$, $\varphi(N)=300$, $\lambda(N)=30$ ).

However, in RSA as practiced, $e$ is small, often small enough that $e$ can be found by enumeration. Thus a method could be:

  • compute $c\gets2^d\bmod N$
  • compute $c_2\gets c^2\bmod N$
  • set $e\gets1$
  • repeat
    • set $e\gets e+2$
    • set $c\gets c\cdot c_2\bmod N$; notice $c=2^{d\cdot e}\bmod N$
    • if $c=2$
      • for $m$ the first hundred odd primes (note: for small $N$, we want to stop as soon as $m^2>N$ )
        • if $m^{e\cdot d}\bmod N\ne m$, continue at repeat above
      • output $e$ and stop.

It's almost certain that if an $e$ is output, it's valid in the sense that textbook RSA encryption using $(e,N)$ is undone by RSA decryption using $(d,N)$, and (equivalently) $e\cdot d\bmod\lambda(N)=1$. It's not quite sure $e\cdot d\bmod\varphi(N)=1$, but knowing $e\cdot d$ and $N$ it's possible to factor $N$ (using this algorithm), and then compute the $e$ with $e\cdot d\bmod\varphi(N)=1$ and $1<e<\varphi(N)$, if for some reason that's desired.


Addition: The above is far from optimal. When $\delta=\ln(e)/\ln(N)$ is below a certain threshold, in the order of $0.292$, there are ways to factor $N$ (and thus solve the problem by the first method discussed). Basically, we swap $d$ and $e$ in Dan Boneh and Glenn Durfee's Cryptanalysis of RSA with Private Key $d$ Less than $N^{0.292}$, in proceedings of Eurocrypt 1999. See there for more.

$\endgroup$
1
  • $\begingroup$ Of course, $p-1$ and $q-1$ should not have any big factor in common, or else your method of generating primes sucks and makes attacks undesiredly feasible (in fact, a lort more simple relations between $p,q$ must be avoided)). So preferably, $\lambda(p-1,q-1)$ is something like $\frac12\phi(N)$. - Moreover, in practice one often picks a nice (public) $e$ such as a smallish, but not too small prime near a power of $2$; this makes computing the encryption faster while at the same time it is not much of a problem to avoid primes $\equiv 1\pmod e$ in the very process of generating them $\endgroup$ Jul 10, 2021 at 17:50

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.