# How to figure out a 615 digits long decryption key given these RSA properties?

I have

• a public key $$(n,e)$$ where modulus $$n$$ has 615 decimal digits.
• a decryption exponent $$d$$ with 8 decimal digits currupted with known positions.
• a plaintext-ciphertext pair $$c_1 = m_1^e \bmod n$$
• just a ciphertext c_2 encrypted with the public key $$(n,e)$$

I want to decrypt $$c_2$$.

I'm sorta lost on what I can do with these information. My main focus is trying to get D1. It is 615 char. long, with 8 digits randomly missing throughout it. Trying to bruteforce it would be going through 10$$^8$$ possibilities. Even if I can somehow do that, what would I even do with all of them? decrypt the ciphertext and see which D1 matches the plaintext? I dont know if that possible on a laptop.

I tried computing the euler phi function of N, but being a large number, I dont know if i can compute it. I had it running for 20min before I interrupted the calculation.

What else can I do with all this information?

Thank you

• $10^8 \approx 2^{27}$ that is quite easy to reach with a laptop. With a ciphertext-plaintext pair, you can test each for $d_1$. – kelalaka Apr 8 at 10:54
• @kelalaka what would I use to/how would I compute them? – Rob Bor Apr 9 at 6:16
• @kelalaka its like "1242x246235x623523..." where each x is a missing number, and the entire value is 615 char long. Sorry if i am unclear – Rob Bor Apr 9 at 11:01
• @kelalaka I do know the location of the missing digits – Rob Bor Apr 9 at 11:31
• @kelalaka im sorry, I do not quite understand. I have both a plaintext-ciphertext pair, and also a ciphertext which I want to decrypt. $d$ is a number which is 615 characters long and is missing 8 digits. Which part am I failing to explain? – Rob Bor Apr 9 at 11:59

The easiest way is the brute-force the corrupted digits on $$d$$. Since you have 8-digit corrupted with known positions iteration on them will cost $$10^8 \approx 2^{27}$$ which is quite easily accessible today home computers. What supercomputer can reach please see this post from Cryptography.
Calculating the $$\varphi(n)$$ form $$(n,e)$$
If you were able to calculate the $$\varphi(n)$$ easily, there will be a problem for RSA;
Assume that there is an Oracle $$O$$ that given $$n$$ outputs $$\varphi(n)$$. Since the attacker knows the public key $$(n,e)$$ then he will ask the $$O$$ for $$\varphi(n)$$. Once the $$O$$ outputs the $$\varphi(n)$$ then by using the relation $$e \cdot d \equiv 1 \pmod \varphi(n)$$ the attacker will be able to find the private exponent $$d$$. Therefore, an efficient way to find the $$\varphi(n)$$ without factoring is equal to breaking RSA.