Say Alice publishes her public key and then disappears from public view.

Bob then needs to send a message to her that's either "OK" or ":(" so he takes her public key, encrypts his message and then publishes it publicly on the Internet.

What's to stop Eve from taking the publicly encrypted message, and then brute force encrypting every two letter combo with Alice's public key until she finds a match?


Not with "textbook" RSA, where you encode your message as a large number and directly compute the ciphertext c from the message text m and public key (e,n) with c = m^e mod n and decrypt using the secret key (d,n) like m = c^d mod n.

But with real RSA, most definitely yes as randomness is introduced.

One common scheme (RSA ISO standard - which is a hybrid encryption) is to first create a long random number (e.g., if using 2048-bit RSA that is n is 2048 bits, choose a random number (up to 2048-bits long), which will become your RSA message mrsa. This RSA message is then asymmetrically encrypted. You then create a cryptographic hash (e.g., SHA-256) of this random value to create a 256-bit symmetric key. Your real message will then be encrypted with the symmetric key (using say AES-256-CBC) and these two ciphertexts are appended together.

Granted in practice the encryption scheme is slightly more complicated; e.g., a protocol like OAEP is used to additionally provide message authentication to prevent more sophisticated adaptive chosen ciphertext attacks against a decrypting oracle (that HTTPS servers provide). In fact as CodesInChaos pointed out, using a good padding scheme (like OAEP) directly for a short message allows you to apply RSA directly to the short padded message.

Aside into Optimal Asymmetric Encryption Padding (OAEP)

OAEP works as shown in the diagram below. For concreteness, let's assume 2048-bit RSA (meaning n=2048 bits) and let H be the SHA-256 hash function and G be a mask generation function based off of a hash function (that essentially creates a hash of the desired length of N-k0 bits starting with SHA-256). The choice of hash function means that the length of r (and Y) is k0 = 256 bits. Also note the red ⊕ (circles with plus) means XOR.

So we have a short message m (of length n-k0-k1 which is shorter than n-k0=2048-256=1792 bits) that we want to RSA encrypt directly. We create a padded version mpad to be exactly n-k0 bits long (the pad will be k1 bits long and start with a 1 followed all zeros). We create a random k0=256 bit number and call it r. We compute G(r) and XOR this value with the padded message and that becomes X. You then take X and compute H(X) and XOR this with r to provide Y. Then with your OAEP padded message (the concatenation of X and Y), you can directly apply RSA encryption to it.

OAEP diagram

Or to summarize X = mpad ⊕ G(r) and Y = H(X) ⊕ r, with the OAEP message going into RSA being the concatenation (X,Y). For decryption, first the RSA message is decrypted to recover (X,Y). The decryptor calculates H(X) and xors it with Y, to find r, that is r = Y ⊕ H(X). Then the decryptor calculates G(r) and xors it with X to recover the original padded message (and the pad can be truncated off by dropping everything starting from the last 1 followed by all zeros).

| improve this answer | |
  • 1
    You don't need hybrid encryption with properly padded RSA. You can encrypt the message directly if it's short. – CodesInChaos Jun 15 '13 at 15:54
  • @CodesInChaos - Agreed RSA with a good random padding scheme (RSA-OAEP - resistant to Adaptive Chosen Ciphertext Attacks) can encrypt small messages directly. Granted, in practice when you use RSA (e.g., in TLS ) you will use encrypt a symmetric key as asymmetric encryption is slow and expensive and can only encrypt short messages on the order of the length of the RSA modulus (n). – dr jimbob Jun 15 '13 at 18:47

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