0

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

kelalaka
  • 1,637
Rob Bor
  • 147
  • 1
  • 6
  • $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 08 '19 at 10:54
  • @kelalaka what would I use to/how would I compute them? – Rob Bor Apr 09 '19 at 06: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 09 '19 at 11:01
  • @kelalaka I do know the location of the missing digits – Rob Bor Apr 09 '19 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 09 '19 at 11:59
  • @kelalaka sorry, I did not mean character as in that. I meant that $d$ is 615 char long. For e.g. the number 1527 is 4 char. long. So $d$ is 615 char long in the same way. And yes, they are all digits. – Rob Bor Apr 09 '19 at 12:50
  • Then for each missing digit, apply brute force; construct the candidate $d$ and decrypt ciphertext to see that it matches its corresponding plaintext. Once the key is found, decrypt the ciphertext to obtain its plaintext. – kelalaka Apr 09 '19 at 12:53
  • My, last comment is your way, calculation phi is hard. – kelalaka Apr 09 '19 at 13:30

1 Answers1

1

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.

kelalaka
  • 1,637