2
$\begingroup$

$K_{pub} = (n, e)$

$K_{pvt} = d$

Then

$E_{K_{pub}}(x) \equiv x^e \mod n$

Practically, when RSA is used to encrypt strings, what is the $x$ here? You cannot take it byte by byte because $\mod n$ will result in values larger than a byte. So what is done?

$\endgroup$
16
  • 1
    $\begingroup$ Practically RSA is not used to encrypt strings. $\endgroup$
    – Maeher
    Jan 14 at 9:40
  • $\begingroup$ @Maeher - but it can be, right? So in case it needs to be done, how will it be done? $\endgroup$
    – user93353
    Jan 14 at 9:43
  • $\begingroup$ @Maeher - and even if it's used to encrypt an AES key - the AES key will be a 256 bit - i.e. 32 bytes. So how will it be encrypted - it can't be done byte by byte because mod n will result in values larger than a byte $\endgroup$
    – user93353
    Jan 14 at 9:49
  • $\begingroup$ What? Almost all encryption algorithms can be considered encrypting bit and bytes. Computationally, a string is a sequence of bytes. RSA keys are at least 1024 bits that make 256 bytes. What is your actual problem? $\endgroup$
    – kelalaka
    Jan 14 at 10:13
  • $\begingroup$ @kelalaka - I want to encrypt "ABCD". What would I raise to e to encrypt this? If I raise A (65) to the power e mod n, then the result wouldn't fit in a byte - so A encrypted may take more than 1 byte. It may take upto n/8 bytes. So do I chop the string "ABCD" into n bit size blocks & then iteratively raise each block to power e? $\endgroup$
    – user93353
    Jan 14 at 10:46
5
$\begingroup$

Practically, when RSA is used to encrypt strings, what is the $x$ in $x^e\bmod n$?

That depends on the variant of RSA. Among the most common:

  1. Toy-sized textbook RSA, where the public modulus $n$ is small: it is customary to encrypt letter by letter (or pair of letters, as in the original RSA article's small example) and concatenate the RSA cryptograms. Thus $x$ is the rank of the letters in the encoding used (or $x=x_0\,b+x_1$ where $x_0$ and $x_1$ are the ranks of two letters, with $b$ a public constant greater than the maximum value of $x_i$, e.g. $b=100$ in said article). There is no security for small $n$: a toy hammer won't actually nail. Small $n$ is anything up to like a hundred decimal digits. That can be factored quickly, which allows decryption. See this for records.

  2. Textbook RSA with large $n$: it is customary to transform the string into bytes (e.g. per UTF-8, the modern compatible superset of ASCII), then from bytestring to integer $x$ (usually per OS2IP). In Python

    int.from_bytes(bytes('François wears a 😷!', 'UTF-8'), byteorder='big', signed=False)
    

    There is a size limitation to $k-1$ bytes, where $2^{8(k-1)}<n<2^{8k}$, which insures $0\le x<n$. On decryption, leading zero bytes are ignored/removed (due to the simplistic conversion from string to bytestring). Variations abound (some encoding of size to allow any bytestring, padding on the right so that $x$ is large even for small strings, endianness…).

    Caution: Textbook RSA in not secure under Choosen Plaintext Attack:

    • An attacker can trivially verify a guess of the plaintext: just encrypt the guess and check against the cryptogram. That attack is devastating for names on the class roll, credit card number…
    • When short strings encode to small integers $x$, several other attacks apply, including
      • when $x$ happens to we writable as $x=x_a\cdot x_b$ for integers $x_a$ and $x_b$ small enough to be found by enumeration, there's a meet-in-the-middle attack
      • when $e<\log_2(N)/\log_2(x)$, it stands $x^e\bmod N\,=\,x^e$, and thus it's trivial to find $x$ by $e\text{th}$ root extraction.
  3. RSAES-PKCS1-v1_5: similar to 2 plus random padding, and means to remove it on decryption. $x$ is a combination of the string to encode, 3 constant bytes, and at least 8 random (non-zero) bytes. The string is thus limited to $k-11$ bytes (per §7.2.1 step 1). This method is better, but still has serious defects:

    • Implementations of decryption are difficult to protect against side-channel attacks. The first was Daniel Bleichenbacher's Chosen ciphertext attacks against protocols based on the RSA encryption standard PKCS #1, in proceedings of Crypto 1998, and there are many variations.
    • Unless we lower the $k-11$ limit, encryption is inherently vulnerable to an attack under CPA costing $2^{63}$ encryptions.

    For these reasons, RSAES-PKCS1-v1_5 should not be used in any new design.

  4. RSAES-OAEP: this is a major improvement of the above, using a hash. The string is transformed by the padding process into integer $x$ that is sort of random with $0\le x<2^{8(k-1)}$, and that's undone in decryption. Secure implementations of decryption are easier than for RSAES-PKCS1-v1_5. Security is theoretically reducible to that of the hash and of the RSA problem (finding a random $x$ given $x^e\bmod n$). The size limitation becomes $k-2h-2$ bytes (per §7.1.1 step 1.b) where $h$ is the size of the hash (e.g. $h=32$ bytes for SHA-256).

  5. Hybrid encryption, e.g. RSA-KEM. A random value $x$ with $0\le x<N$ is RSA-encrypted with no padding, a symmetric encryption key is derived from that, and that key is used to encrypt(-and-MAC) the string to encrypt. Some avenues of implementation mistakes on decryption that still exist in RSAES-OAEP are gone. Security is theoretically reducible to that of the encryption and the RSA problem, with a simpler proof and/or quantitatively better assurance than for RSAES-OAEP. There is no size limitation. However the size of the cryptogram is slightly increased, and we need a Key Derivation Function and an authenticated cipher, when that's built into RSAES-OAEP.

$\endgroup$
2
  • $\begingroup$ (cough) using the 8-bit bytes (formally octets) used by PKCS1 (and nearly everyone since about 1980) SHA256 is 32 bytes $\endgroup$ Jan 16 at 3:36
  • $\begingroup$ @dave_thompson_085: thanks, sharp-eyed! Yes I no longer bother distinguishing a byte and an octet; I'm even sometime assuming a C char is a byte, and occasionally that INT_MAX is at least $2^{31}-1$. Where's that emphasis on portability that I once had? $\endgroup$
    – fgrieu
    Jan 16 at 11:52
0
$\begingroup$

Composed the answer I was looking for from the different comments in response to the question

  • Input is considered as an array of bytes/octets (8 bit).
  • k is the octet length of the RSA modulus (n)
  • Maximum number of octets which can be encrypted with RSA is k - 11
  • The array of octets after padding is considered to be a Big Integer - x
  • The Big Integer x is encrypted using the public key - $E_{K_{pub}}(x) \equiv x^e \mod n$

For more info, look at OS2IP and PKCS1

$\endgroup$
3
  • 1
    $\begingroup$ The method discussed in this answer is RSAES-PKCS1-v1_5, which has serious defects: implementations of decryption are difficult to protect against side-channel attacks; and (unless we change the $k-11$ limit) encryption is inherently vulnerable to an attack costing $2^{63}$ encryption under Choosen Plaintext Attack. For this reason the modern options are RSAES-OAEP (same ref), or hybrid encryption, e.g. RSA-KEM. $\endgroup$
    – fgrieu
    Jan 15 at 8:12
  • $\begingroup$ @fgrieu - your comment is only as regards the padding, right? Overall, the encryption happens as said in the answer - except for the padding details? $\endgroup$
    – user93353
    Jan 15 at 8:14
  • $\begingroup$ What I had to say no longer fits a comment, so I made an answer. $\endgroup$
    – fgrieu
    Jan 15 at 10:03

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.