2
$\begingroup$

I looked into the math behind RSA and seem to understand the basic encryption and decryption scheme.

Let's say there are two parties, Alice and Bob, who wish to communicate and secure their conversation using RSA.

Alice generates two prime numbers ($p$ and $q$), uses those to compute $n = p q$, and $\phi(n) = (p-1) (q-1)$. Then she computes two values, $e$ and $d$ which are relatively prime to $n$. She sends over the publicly accessible values $n$ and $e$ to Bob, who encrypts his message $m$ by computing a value $c = m^e \bmod n$. He sends this publicly accessible value to Alice who then uses $d$ to compute $m = c^d \bmod n$.

If an eavesdropper intercepts their conversation and gets the value of $c = m^e \bmod n$ and knows $e$ and $n$, could he not just brute-force different values of $m$ to see which works?

$\endgroup$
  • $\begingroup$ This question has been asked here (and elsewhere) numerous times. Try to search by "RSA brute force" and read the answers. Briefly: yes, he could try but if the length of 'n' is decent and RSA is used correctly (I omit the details) - he's got no chance. $\endgroup$ – tum_ Jun 9 at 19:37
  • $\begingroup$ @tum_ Why would the length of n matter though? Since mod is just an operation, regardless of the value of n could you not just brute-force m if m is small enough? $\endgroup$ – Samvit Agarwal Jun 9 at 19:42
  • $\begingroup$ What you have in mind falls into "incorrect use of RSA". Please read the existing answers. It's all explained already, no point answering again. $\endgroup$ – tum_ Jun 9 at 19:45
  • $\begingroup$ @tum_ Perhaps you could specify which answers already address this? The first relevant question I see when searching for rsa brute force is, in fact, this question; the next one after that is crypto.stackexchange.com/q/58147, but it's not clear on what RSA-based encryption scheme it's referring to, and the answers don't really explain how real RSA-based encryption is related to the function $x \mapsto x^e \bmod n$, or how randomization is essential to public-key encryption. $\endgroup$ – Squeamish Ossifrage Jun 9 at 20:03
  • $\begingroup$ @SqueamishOssifrage My "no point answering.."comment is not addressed to you. Yes, the one under your link is a good place to start. The question and the further comment from the OP does not imply (as far as I can read) that the OP asks for an explanation of encryption schemes, he simply asks about textbook RSA brute forcing for a small message 'm'. In my opinion the question does not demonstrate any previous research and I commented on this. (And upvoted your answer, btw). $\endgroup$ – tum_ Jun 9 at 20:28
5
$\begingroup$

If an eavesdropper intercepts their conversation and gets the value of $c$ (namely, $m^e \bmod n$) and knows $e$ and $n$, could he not just brute-force different values of $m$ to see which works?

Yes!

This is part of why we do not use the function $x \mapsto x^e \bmod n$ to encrypt messages directly. Instead, a sensible sender will pick $x$ uniformly at random from all positive integers below $n$, use $k = H(x)$ to encrypt a message $m$ with their favorite symmetric-key authenticated cipher like NaCl crypto_secretbox_xsalsa20poly1305 or AES-GCM, and then transmit $x^e \bmod n$ alongside the ciphertext, so that the receiver can recover $x$ and derive $k$ to decrypt the ciphertext.

This system is called RSA-KEM. There are also more complicated systems like RSAES-PKCS1-v1_5 and RSAES-OAEP, where we pick $k$ up front and then shoehorn it into something that's close to a uniform random positive integer below $n$, but invariably we use a symmetric-key authenticated cipher to encrypt the actual message.


A little more generally, this goes beyond RSA: any public-key encryption scheme is necessarily randomized, because otherwise anyone could verify a guess about what plaintext is concealed in a ciphertext $c$ is simply by testing whether $c \stackrel?= E(m)$ for a candidate message $m$ where $E$ is the public-key encryption function.

$\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.