0
$\begingroup$

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

$\endgroup$
  • $\begingroup$ $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$. $\endgroup$ – kelalaka Apr 8 at 10:54
  • $\begingroup$ @kelalaka what would I use to/how would I compute them? $\endgroup$ – Rob Bor Apr 9 at 6:16
  • $\begingroup$ @kelalaka its like "1242x246235x623523..." where each x is a missing number, and the entire value is 615 char long. Sorry if i am unclear $\endgroup$ – Rob Bor Apr 9 at 11:01
  • $\begingroup$ @kelalaka I do know the location of the missing digits $\endgroup$ – Rob Bor Apr 9 at 11:31
  • $\begingroup$ @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? $\endgroup$ – Rob Bor Apr 9 at 11:59
0
$\begingroup$

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.

$\endgroup$

Your Answer

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

Not the answer you're looking for? Browse other questions tagged or ask your own question.