6
$\begingroup$

Is there a known 'non-brute force' method of determining a private key in an RSA system when all other parameters are know?

I found the values of a ciphertext ($C$), its corresponding plaintext ($P$) and the values of the public key ($e$,$N$) are known.

We know that: $$P = C^d \mod N$$

Here, the value of $P$ is known (the cipher text has been decrypted) and the values of $C$ and $N$. Given these parameters, is it possible to find $d$?

Also, how do I find an integer $k$ such that $(k\cdot N - P) = C^d$ ?

Any suggestions/discussions are welcome.

|improve this question
$\endgroup$
  • 3
    $\begingroup$ RSA, when used properly, is safe against known plaintext attacks. No secure cipher leaks the secret or private key unless the cipher is broken. $\endgroup$ – Maarten - reinstate Monica♦ Mar 19 '16 at 1:11
  • $\begingroup$ @MaartenBodewes Yes, that is true. But in this case, the system is not being used properly. The public key is very small (e=3) and the message is not being padded. This makes it easy to retrieve the message from the ciphertext. In an ideal scenario, I will not have the plain text without knowing the private key d. Is it possible to work backwards from the plain text and ciphertext? $\endgroup$ – cobbs Mar 19 '16 at 1:14
  • $\begingroup$ cseweb.ucsd.edu/~mihir/papers/blindsigs.pdf ​ ​ $\endgroup$ – user991 Mar 19 '16 at 1:25
  • $\begingroup$ As to that part of the question asking for an integer $k$ such that $(k\cdot N-P) = C^d$, is there a typo in that equation, like a minus where plus is thought? If not, what's wrong with the obvious: reduce that equation modulo $N$, combine with $P = C^d\bmod N$, and get to the conclusion that there is a solution only if $P\bmod N=0$, assuming only that $N$ is odd. $\endgroup$ – fgrieu Mar 20 '16 at 13:58
  • $\begingroup$ I do not know the value of C^d. I arrived at this equation from the definition of the RSA private key decryption. P = (C^d) mod N. I am not sure if I'm missing something, but how do I reduce that equation with having two unknowns? C^d and k? $\endgroup$ – cobbs Mar 20 '16 at 14:48
9
$\begingroup$

No, there is no known efficient method to find an RSA private key from public key, ciphertext and plaintext, including when no padding is used and $e=3$. The best known method is factoring the public modulus, which then trivially allows to find a working private key. Factoring is considered brute force, or tantamount to that. The best known factoring method for a public modulus of cryptographic interest in RSA is GNFS.

We can prove the assertion in the first two sentences, modified by adding that the ciphertext was not chosen by an adversary, and that the hypothetical method works including for small public exponents $e$. The idea is that any such method could be turned into a factorization algorithm for any $N$ suitable as RSA key: we chose a small odd $e$, which with fair odds is coprime with $\varphi(N)$; we choose some plaintext, and compute ciphertext by whatever method is normaly used in the RSA variant considered; we can now apply our hypothetical efficient method that finds a private exponent $d$; we compute $f=d\cdot e$, which is such that $f\bmod(p-1)=1$ for any prime $p$ dividing $N$, and that's enough to efficiently factor $N$ (see this answer).

|improve this answer
$\endgroup$
2
$\begingroup$

In order to find private exponent D we need to calculate the factors of N.
e.g
Finding the factors of a 64bit N ↷ 9D73032BDEDCD671 takes almost a second.
Prime 1: 10ECD8623
Prime 2: 94D7B85B
Knowing that we can calculate the private exponent D.
D:59683910DF25978D
Since C is: C=M^E MOD N we can decrypt any given ciphertext now.

Number factorization is an extremely hard task by the way. Big N's are extremely hard to factorize.

Certain methods exist in order to factor big numbers.
Brent's Factorization Method
Williams' p + 1 algorithm
Pollard's p − 1 algorithm
Lenstra elliptic curve factorization

Interesting read, FACTHACKS- RSA factorization in the real world

|improve this answer
$\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.