9
$\begingroup$

Suppose RSA is considered a "secure" method for encryption. RSA is meant to encode a sequence of integers base $27$. If we use an $n=pq$ that is hard to factor, Is it still secure if we encode every integer (letter) separately rather than the whole phrase once?

Edit: I didn't expect to get such great answers. Thanks everyone!

$\endgroup$
2
  • 4
    $\begingroup$ This is, in fact, such a common beginner's mistake, that breaking it is one of the classic easy-level challenges you may find in CTFs or introductory courses. $\endgroup$
    – b0fh
    Dec 10, 2021 at 11:47
  • 2
    $\begingroup$ xkcd.com/257 is a comic that shows a nice example $\endgroup$
    – Jonas
    Dec 11, 2021 at 18:55

4 Answers 4

17
$\begingroup$

Textbook / Plain RSA should not be used to encrypt messages directly. This is because the ciphertext is deterministic based on the message. Given an eavesdropped ciphertext $c_i$. An effective attack against your scheme would be:

  1. Obtain ciphertexts $c_0, ..., c_{26}$ by encrypting integers 0-26 using the public modulus $n$ and exponent $e$.
  2. For $j$ in [0,26], check if $c_i=c_j$. If we find such a $j$, then your original message was $j$.
$\endgroup$
7
$\begingroup$

With appropriate padding (such as OAEP), using RSA to encrypt individual bytes or characters or even bits is indeed secure*. Of course it's also incredibly wasteful, as you're turning every 8 bits of plaintext into something like 2048 or more bits of ciphertext, and spending a lot of CPU time in the process, but inefficiency is not (usually) a security issue.

Without padding, however, using RSA to encrypt either single characters or short messages is insecure, as such "textbook RSA" encryption is vulnerable to several attacks allowing messages to be decrypted without the private key. Some of these attacks include:

  • The guessing attack: generate a list of a few hundred (or a few trillion) more or less plausible plaintexts and encrypt each of them with the public key. Check if the result matches the message you want to decrypt. If it does, you've just found the correct plaintext.

    This attack will completely break any scheme using textbook RSA to encrypt single characters or bytes, as it's easy to encrypt every single character or byte with the public key, and thus obtain a complete dictionary of all possible ciphertexts. But it also works any time the plaintext space is small enough (or the attacker can guess that the plaintext likely belongs to some sufficiently small set) that it can be enumerated on a computer (or a cluster of computers).

  • The $e$-th root attack: If the public modulus $e$ is small (such as $e = 3$) and the plaintext $m$ (after being encoded as a number) is also small enough that $m^e < n$, then textbook RSA encryption can be defeated simply by calculating the $e$-th root of the ciphertext $c = m^e \bmod n$. Variations of this attack can also be made to work if $m^e < kn$ for some small integer $k$ (say, less than a trillion), simply by brute force testing if the $e$-th root of $c + jn$ is an integer for all $j$ from $0$ up to $k$. While this attack is easy to avoid (e.g. by using proper encryption padding and/or by using a larger public exponent, like the common $e = 2^{16} + 1 = 65537$), surprisingly many naïve RSA schemes devised by amateurs (or designed to be deliberately broken e.g. in a CTF) can fall to it.


*) In the sense of providing confidentiality and semantic security against a passive eavesdropping attacker, assuming that the RSA key is properly generated and long enough to withstand factoring attacks, that the random number generator used for OAEP isn't compromised and that no other obvious implementation mistakes have been made, and that the existence and the length of the message are not confidential. Even then, any "ECB" style scheme encrypting text one character at a time is of course highly malleable and thus vulnerable to manipulation by an active attacker.

$\endgroup$
1
  • 1
    $\begingroup$ I'm simply in love with that footnote. $\endgroup$
    – D. Kovács
    Dec 11, 2021 at 12:50
6
$\begingroup$

If each character is encrypted independently, then every time the character 'a' appears in the plaintext, it maps to the same unique token of whatever length (e.g. 0x157a05c8). And conversely, any time you see 0x157a05c8 in the ciphertext, it must map to 'a' in the plaintext. Finally, no matter how long the output tokens are, if the input is encrypted one (8-bit) byte at a time, there are only 256 possible output tokens, same as the number of possible input tokens.

That isn't RSA anymore. It's a substitution cipher, and those are trivially breakable using a number of simple techniques. You aren't using RSA as the encryption algorithm, but rather as a key derivation function. But that doesn't make the substitution cipher itself any stronger.

$\endgroup$
6
$\begingroup$

Although RSA is not meant for encryption one can use RSA for encryption. If one uses TextBook RSA then it will be insecure since the encryption is free then any attacker can check the values. We call this the encryption oracle and it is free on public-key systems


A simple RSA encryption oracle game...

def Ind_CPA_RSA(adversary, target):
    (e,n,d,...) = generate_RSA_key()                  //keygen part

    def RSA_encryption_oracle_PKCS#1_v1.5(plaintext): //Encryption oracle
        EM = PKCS#1_v1.5_padding(plaintext)
        ciphertext = EM^e mod n
        return ciphertext

    for each m in possible_message_space:                  //queries
        c = RSA_encryption_oracle_PKCS#1_v1.5(m)
        if c == target
            print(target)
            return succcess
    return failure

So, the adversary tries all possible messages as long as they can, to see the equality to win.

In textbook RSA if public exponent $e=3$ then cube-root attack works for all messages suche that $len(m) < \sqrt[3]{n}$.

For all other attacks the Dan Boneh's article is a good starting point;


$$\textbf{Never use Text Book RSA as long as you know what you do!}$$


To be secure one has to use RSA encryption with proper paddings PKCS#1 v1.5 (RSAES-PKCS1-v1_5) or OAEP (RSAES-OAEP) padding. These paddings add randomization to achieve probabilistic encryption.

Each uses special encodings to achieve this like PKCS#1 v1.5 padding;

EM = 0x00 || 0x02 || PS || 0x00 || M.

M is the message. The PS consist of the randomization part

Generate an octet string PS of length k - mLen - 3 consisting of pseudo-randomly generated nonzero octets. The length of PS will be at least eight octets.

For example for 2048-bit RSA; $k = 256$, $mLen=4$ then PS length is 249 bytes of randomness for one letter-sized message. Therefore the attacker cannot test the values with the encryption oracle. The rest is attacking the RSA problem.

Similarly, OAEP has randomness and OAEP has proven to have IND-CCA1 security. Prefer OAEP to PKCS#1 v1.5 since it has many attacks due to improper implementations.


If anyone wants an academic article about metrics of RSA encryption here is the paywalled article;

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