0
$\begingroup$

I'm trying to implement a very basic RSA with functions that should generate RSA keys and cipher some text. GenKey function returns a tuple (p,q,n,e,d) like the following.

p,q large prime numbers with 1024bits each
n = p*q
phi(n)=(p-1)(q-1)
e as gcd(phi(n),e)=1 and 1 < e < phi(n)
d = e⁻1 (mod phi(n))

At the end I'll get a public key like kp={e,n} and a private one ks={d,n}. So far everything is working as expected.

Now suppose that cipher function receives a string of binary data as the plaintext to cipher and outputs a ciphered text in ECB mode(a binary string aswell). I Know that in order to cipher I can do the following: C = M^e (mod n) if M is an integer. If it's not I think I have to break my binary string into say 32bit length substrings, calculate it's integer value, apply C = M^e (mod n), get the new integer and last represent it back into binary. Please correct me If I'm wrong at this point.Am I thinking it right?

So my question is, when calculating C is it possible that returned value is too bigger for representing (as binary) on my block size decision (those 32bit). How block size should be picked?

$\endgroup$
  • 1
    $\begingroup$ If you're tempted to do something about ECB mode, consider asking what tempts you to do that in the first place in order to resist the temptation? What you are asking to do is essentially nonsense cryptography, and although there is a literally correct answer to your question at face value, to take that answer and run with it will invariably lead you down a path to madness. $\endgroup$ – Squeamish Ossifrage Dec 15 '17 at 3:43
  • $\begingroup$ @SqueamishOssifrage I intend to implement various block cipher modes, that's the reason why. Just happened to start with this one... $\endgroup$ – fish202 Dec 15 '17 at 3:50
  • $\begingroup$ Don't think of things in terms of modes of operation. Think of application-meaningful concepts, like symmetric nonce-based authenticated encryption (two peers share a key, agree on message sequence numbers, and get antiforgery and secrecy of messages), or public-key message encryption (sender knowing recipient's public key anonymously sends message that can be opened only by recipient). There is no sensible application-meaningful concept that comes out of the conceptually garbled notion of ‘RSA in ECB mode’. $\endgroup$ – Squeamish Ossifrage Dec 15 '17 at 4:53
  • 2
    $\begingroup$ In other words, this sounds like a prime example of an XY problem. You're obviously trying to solve some problem in front of you, and in your attempt to solve it you have written a plan that involves implementing various block cipher modes, and down that path you've come to RSA in ECB mode, and unless you back up and work out what you were trying to solve in the first place, you're digging yourself into a hole of madness. $\endgroup$ – Squeamish Ossifrage Dec 15 '17 at 4:59
  • 2
    $\begingroup$ RSA is no blockcipher, don't treat it like one. Use hybrid-encryption instead (and either use OAEP or KEM, not textbook RSA). $\endgroup$ – CodesInChaos Dec 15 '17 at 8:58
5
$\begingroup$

Securely enciphering text with RSA is typically done in one of three ways:

  1. The most usual one is with the help of a symmetric cipher: RSA is used to establish a symmetric key, and the text itself is enciphered with the symmetric cipher. That's a hybrid cryptosystem. One way is that the sender generates a uniformly random $x$ in range $[0..N)$, enciphers it with the textbook RSA public-key function $x\to x^e\bmod N$ and sends the results (of 256 octets) which the receiver can decipher; then both extract the (say) 192 low-order bits of $x$ and use it as key for AES-CTR, which enciphers the text.
  2. RSA-ECB with random padding: the text is broken into pieces significantly smaller than the public modulus (e.g. 190 octets pieces for 2048-bit RSA); each block associated with some randomness and redundancy (e.g. 32+34 octets) into a padded block, by some algorithm (e.g. RSA(ES)-OAEP) typically involving a hash (e.g. SHA-256); each result $x_i$ is enciphered with the textbook RSA public-key function $x_i\to{x_i}^e\bmod N$; the results are concatenated. Decryption undoes that and discards the randomness. This option has huge drawbacks when more than one block is involved: slow decryption, sizable ciphertext expansion (e.g. +15% for large text). In practice, it is thus used only for small amount of data (e.g. the secret PIN number of a credit card).
  3. RSA is used (possibly multiple times) to establish a shared secret random keystream as long as the plaintext, then used to encipher the plaintext with XOR (or other equivalent information-thoretically perfect cipher). E.g the sender generates uniformly random $x_i$ in range $[0..2^{2040})$ (enough that the 255-octet $x_i$ concatenated are at least as long as the plaintext), enciphers them with the textbook RSA public-key function $x_i\to{x_i}^e\bmod N$; the results are concatenated and sent, as well as the plaintext XORed with the keystream. This is nearly as slow as 2 (there are almost as many RSA decryption to perform), has significantly worse ciphertext expansion (ciphertext is over twice as large as plaintext), but requires no keyed cipher (as 1 does) or padding function (as 2 does).

In 2, cutting corners on randomness would allow an adversary to check a guess of a plaintext (that's a disaster for a PIN number, or the name of someone on the public class roll). Cutting corners on the padding function leads to other, more subtle security issues. Some introductory material uses 2, cuts corners on both randomness and padding, and uses very small $p$ and $q$. That's justifiable only for teaching purposes and with ample warnings (sadly often skipped or/and forgotten).

For large $p$ and $q$, the only recommendable options are 1; 2 exclusively limited to short plaintext and with decent randomness and padding function; or 3 for something which for some reason (e.g. pedagogical, conceptual simplicity, code size..) must use neither a keyed cipher nor a hash.

Note: none of these options provide message integrity of any kind. Since the public key is known to attackers, they can generate messages with any deciphered content they will. Upgrading option 1 with authenticated symmetric encryption does not satisfactory solve that issue (it only ensures that an adversary can not alter part of a message while leaving some unknown portion unchanged).


I know that in order to cipher I can do the following: C = M^e (mod n) if M is an integer.

That's textbook RSA, is cutting on both randomness and padding, and thus is unsafe. For a start, any guess of M can be checked, and that's an unwanted property in encryption.

As an aside, I read C = M^e (mod n) as $C\equiv M^e\pmod N$ which means that $N$ divides $M^e-C$, and that is not satisfactory (in particular it allows $C=M^e$ which allows recovery of $M$ from $C$ as $M=\sqrt[e]C$ ). The proper equation is $C=M^e\bmod N$ , additionally meaning that $0\le C<N$ ; notice there is no opening parenthesis before $\bmod$ , making it an operator similar to the % operator of C, Java, Go, rather than implying that the previous equality is modulo $N$ (which is the case with an opening parenthesis before $\bmod$ ).

If it's not I think I have to break my binary string into say 32bit length substrings, calculate it's integer value, apply C = M^e (mod n), get the new integer and last represent it back into binary.

The general idea of cutting in blocks is right if choosing option 2, but doing so in the manner stated is very unsafe due to the lack of added randomness, allowing to find each 32-bit integer by trial and error. Further, if $e<{2048/32}=64$, there is an attack without trial and error due to lack of padding (computing $\sqrt[e]C$ will always reveal $M$ ). Further, the ciphertext expansion is by a factor of ${2048/32}=64$, which is wasteful; and decryption will be dead slow. Larger blocks somewhat improve things, but what's really needed is randomness and proper padding; or better, getting rid of option 2 / RSA-ECB altogether.

How should block size be picked?

If using RSA-ECB (which again is reasonable only for short messages, needing a single block), the choice is dictated by the padding algorithm used. In all such algorithms, that can be at most $\lfloor\log_2N\rfloor-r$ bits, where $r$ is the number of random bits added, which determines the security level against confirming a guess of $M$; $r\ge128$ is recommandable. For $N$ of $8b$ bits, a hash of $8h$ bits, RSAES-OAEP allows block size up to $b-2h-2$ octets. For $8b=2048$ and $8h=256$, that's $190$ octets. It is a tad wasteful, but RSAES-OAEP (also known as PKCS#1v2 encryption padding) is the only RSA encryption padding with both a security proof and good support in common crypto libraries.

$\endgroup$
1
$\begingroup$

For RSA there is usually a difference between input size and output size.

  1. for the textbook RSA the maximum value is identical to the modulus, the input size if taken as integral bits is $n - 1$, where $n$ is the size of the modulus in bits;

  2. for RSA in PKCS#1 mode it is 11 bytes smaller than the modulus size in bytes;

  3. for RSA in OAEP mode it is at least 42 bytes smaller, depending on the hash function used for the internal MGF1 function.

The output maxes out on the modulus size of course, so the size is $n$ bits. Usually this is already on a byte boundary.

Of course 2048 is pretty far from the 32 bit block size that you've indicated. You can not create a 32 bit block cipher out of RSA as the output size cannot be compressed to 32 bit.


Hence the use of hybrid cryptography where RSA is paired with a symmetric cipher. For symmetric ciphers the size of the ciphertext is linear with the size of the message, usually plus a certain overhead of 16-32 bytes for IV and authentication tag + of course the size of the RSA operation: the key size in bytes (in this case 256 bytes for a 2048 bit key).

$\endgroup$
  • $\begingroup$ Unless I err (as I did in a former version of my answer), the width of the hash used by MGF1 is immaterial to the maximum capacity of RSAES-OAEP. What matters is the width of the other hash. $\endgroup$ – fgrieu Dec 16 '17 at 6:44
  • $\begingroup$ Hmm, you could be right here, although for OAEP there is no other hash :) $\endgroup$ – Maarten - reinstate Monica Dec 16 '17 at 13:46
  • $\begingroup$ In the specification, the hash used for OAEP is a given independent of MGF, thus in principle when we use MGF1 as the MGF, MGF1 could use a different hash from the one in OAEP (like MGF1 using its default SHA-1, even though the label of OAEP might be hashed with SHA-256, and the seed 256-bit). Are you saying that in all the cryptoapis around that perform RSAES-OAEP with MGF1, there is no way to specify the use of two different hashes (has happens often unwillingly for RSASSA-PSS)? $\endgroup$ – fgrieu Dec 16 '17 at 14:29

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.