0
$\begingroup$

Suppose for any given typical Bob, Eve and Alice encryption example where Bob and Alice exchange information using RSA. Bob encrypts his message using Eve's public key and sends his message off to Alice.

If I was Eve, suppose I attempted to brute force the private key, and kept doing it mathematically by computing the encrypted message to the power of x, where x is the private key I am trying to find.

When brute forcing the message, how do I know what I have successfully found it?

For any given number x, there is an output, by how do we know that we have found the private key? Does it just check that the output is an english based sentence, what if the output is just something that is another encoding and the output is jibberish again, how would Eve know?

Improve this question
$\endgroup$
3
  • $\begingroup$ In practice RSA is not used to encrypt sentences in English or any other language, which in any case aren't the only things people want to communicate securely. Generally a hybrid scheme, see wikipedia, uses RSA to encrypt a nonce key used to symmetrically encrypt the data. But unlike the 'naive' version used as an exercise in math classes and copied to billions of websites by uninformed people, in practice RSA encryption uses padding which makes it easy to check if a decryption is valid, again see wikipedia and tens if not hundreds of existing Qs. ... $\endgroup$
    – dave_thompson_085
    Commented Nov 11, 2018 at 3:40
  • $\begingroup$ ... But for RSA as currently practiced (mostly 1024-bit or 2048-bit) using all the energy in the universe for your bruteforce attempt won't make even a metaphorical dent. Have you seen the classic movie Forbidden Planet where there's a whole room full of meters, each one ten times the previous, for the great Krell machine? If this were recalibrated for RSA you wouldn't even move the needle on the leftmost (smallest) one by a single atom. $\endgroup$
    – dave_thompson_085
    Commented Nov 11, 2018 at 3:44
  • $\begingroup$ Possible duplicate of How can a decryption program tell me that a private key is incorrect for RSA and ECC? $\endgroup$
    – e-sushi
    Commented Nov 12, 2018 at 3:00

1 Answer 1

Reset to default
1
$\begingroup$

Given $d$ we can factor $n$ as follows;

  • compute $k=de-1$
  • choose random integer $g$ $1 < g< n$
  • $k$ is even with $k=2^tr$ with odd $r$ and $t\geq 1$
  • compute $x = g^{k/2}, g^{k/4}, \ldots,g^{k/2^t} \pmod n$ until $x>1$ and $y=\gcd(x-1,n)>1$

the either $p$ or $q$ is equal to $y$.

If there is no solution find another random $g$.

Looking for all possible $d'$s by this way will be costlier than factorization methods. However, if there is a non-gibberish that you found, you can try to factorize with your $d'$ to see that it is actually $d$.

Improve this answer
$\endgroup$
0

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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