For academic purposes, assuming $n, p, q$ with $n\approx 2^{4096}$ and $p,q\approx 2^{2048}$.

I need to find ($e,d$) such that:

  • $e$ is smaller than $2^{64}$
  • $d\approx 2^{4096}$ and will have as much zeros as possible in binary form. ($d=$10000...0001 will be the best obviously, but I'm not greedy)

What will be the best way to find such a pair?

($n,p$ and $q$ are not fixed, if there is a way to find such $e,d$ by changing them then it is also a valid solution, as long as their lengths are as stated)

  • 1
    $\begingroup$ So you want $p$ and $q$ primes of about 2048-bit, odd $e$ at most 64-bit, with matching $d$ about 4096-bit and as sparse as feasible. Are $p$ and $q$ free-to-choose? Is $p\ne q$ required? And what private exponent $d$ is/are acceptable? A) any $d$ that works, that is $e\cdot d\equiv1\pmod{\operatorname{LCM}(p-1,q-1)}$ B) The smallest $d$ that works, that is $d=e^{-1}\bmod\operatorname{LCM}(p-1,q-1)$ C) That common one: $d=e^{-1}\bmod((p-1)(q-1))$ $\endgroup$ – fgrieu Oct 1 '17 at 15:48
  • $\begingroup$ p and q are free to choose, p≠q is required. and i'm looking for a d that match your (c) category. $\endgroup$ – apu Oct 1 '17 at 15:56
  • 1
    $\begingroup$ I guess that fixing d, brute-forcing e, factoring e*d-1 until you get prime p and q of the desired size is feasible. $\endgroup$ – CodesInChaos Oct 1 '17 at 15:57
  • 3
    $\begingroup$ Choosing $d$ to be a special form ("as many zeros as possible in the binary representation") is likely to be a bad idea, at least, if you care about security. Even if you pick from enough different $d$s to make a simple search infeasible, the special form is likely (in addition to the knowledge of $e$) to make factorization feasible. $\endgroup$ – poncho Oct 1 '17 at 17:14
  • 2
    $\begingroup$ Also, if the reason you are looking for a low-hamming-weight $d$ is to improve performance, well, you might consider a windowed exponentiation routine, which gives about the same performance, and handles arbitrary exponents... $\endgroup$ – poncho Oct 1 '17 at 20:12

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.