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
Brute-Force
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.
Once you determined the correct value of the missing digit, you can decrypt the given ciphertext.
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.