We are given a number of distinct RSA public keys $(e_i,N_i)$ sharing the same unknown decryption exponent $d$. The $e_i$ were computed from $d$ drawn first, so we have different public keys. Can we recover $d$ in any manner?

(Edit) We also know $d$ is 333-bit. $N$ is the product of $p$ and $q$ which both are 512-bit prime numbers, making $N$ 1024-bit. The $e_i$ have been calculated from $d$ by making use of the equation: $e_i \cdot d \cong 1\mod \phi(N_i)$. So we have 3 sets of public keys $(N_i,e_i)$. I was asking if it possible, any way, to recover the value of $d$ if the maximum value of $i = 57$ (Means we can have at most 57 sets of public keys).

  • 1
    $\begingroup$ Welcome to crypto-SE! For 1024-bit $N_i$, a 333-bit $d$ is slightly above the 299-bit bound of Dan Boneh & Glenn Durfee's Cryptanalysis of RSA with Private Key $d$ Less than $N^{0.292}$. therefore that or M. Wiener's Cryptanalysis of short RSA secret exponents would need an extension. [Update: I do not know such extension, nor immediately found one!] $\endgroup$
    – fgrieu
    Feb 11 at 11:28
  • $\begingroup$ Can you show Wiener's attack extension for this set? $\endgroup$
    – Pyp
    Feb 11 at 11:45
  • 1
    $\begingroup$ This can be solved with a generalization of the lattice version of Wiener's attack. There's an explicit writeup here. $\endgroup$ Feb 12 at 2:59
  • $\begingroup$ @SamuelNeves thank you, the paper works and seems to be the idea I want. The issue is I don't know how to fully place the answer here. For someone who is good at reading papers, please assist the community. $\endgroup$
    – Pyp
    Feb 12 at 4:41
  • $\begingroup$ @Pyp: You should be able to answer your own question by typing text in "Your Answer" below then clicking "Post Your Answer" at the bottom. You need to be logged-in. You'll even get rep points if the answer is upvoted. $\endgroup$
    – fgrieu
    Feb 12 at 9:55


Your Answer

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

Browse other questions tagged or ask your own question.