# Different public keys $(e_i,N_i)$ but same decryption exponent $d$

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).

• 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!]
– fgrieu
Commented Feb 11 at 11:28
• Can you show Wiener's attack extension for this set?
– Pyp
Commented Feb 11 at 11:45
• This can be solved with a generalization of the lattice version of Wiener's attack. There's an explicit writeup here. Commented Feb 12 at 2:59
• @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.
– Pyp
Commented Feb 12 at 4:41
• @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.
– fgrieu
Commented Feb 12 at 9:55