RSA Question- max number of ascii characters encrypted at one time

Question

I'm a student new to cryptography and have a fairly straight forward RSA question that I'm struggling to wrap my head around.

"Alice's RSA public key [N:e] is stored in binary as a 16bit integer &: 8bit integer.

What is the maximum number of ASCII letters that can be encrypted at once and sent to Alice if assuming no padding?"

My initial thought was 1 ASCII character at a time because M < N. Therefore it couldn't be 2 characters (2 x 8 bits) because M would = N.

From my understanding of modular arithmetic: 5¹ mod 5 = 0 But 4¹ mod 5 = 4

So I kind of understand that if M is equal or greater than N, I will only decrypt an equivalent message but not identical.

Could somebody explain this to me in more detail?

Answer 1

Don't do it! It's a trap! Applying the arcane mathemagical spell that is RSA trapdoor permutation to ASCII does not an encryption scheme make! The RSA trapdoor permutation conceals uniform random elements of $\mathbb Z/n\mathbb Z$; to use it for anything else is a mistake, and a fool's errand clothed in naive textbook idealism.

It's like telling your class that modern aviation is built out of paper airplanes, except unlike the obscure mathematics of RSA, paper airplanes self-evidently cannot function like an Airbus A380 or even a Cessna C-34. If this is how you are taught aeronautical engineering, I exhort you to find another instructor!

Real encryption schemes based on RSA use the fancy mathematics to conceal a 256-bit secret key for symmetric-key authenticated encryption such as AES-GCM, and use that to encrypt the message.

That preface said, taking your question at face value:

The space of ‘messages’ $M$ is set of the integers between $0$ and $N$. Any other integer is equivalent, as far as RSA is concerned, to one between $0$ and $N$, because all arithmetic is modulo $N$; for example, $N + 1$ is equivalent to $1$, because they differ by a multiple of $N$.

So, for a modulus $N$ between $2^{15}$ and $2^{16}$, there are at least $2^{15}$ distinct messages. How many ASCII characters are there? How many pairs of ASCII characters are there?

Answer 2

For RSA, the modulus - which is the largest number - specifies the capacity of the modular exponentiation. In your case the modulus N is 16 bits. You are correct in finding that M must be smaller than N, so not all 16 bit messages can be encrypted. As the most significant bit of N must be set to be a 16 bit number, we do know that 15 bits messages are always acceptable.

US-ASCII is a seven bit - not eight bit - encoding. These 7 bits can contain both printable and non-printable characters (and a single reserved value, 0x7F). These 7 bits are usually stored in a single 8 bit byte because 8 bit bytes are the norm. For standard ASCII the most significant bit of the byte is always set to zero.

We can encode the message two ways: two 7 bit characters totalling 14 bits or two 8 bit characters totalling 16 bits, of which we know that the most significant bit is always set to zero. At least if you consider the leftmost bit the most significant bit as we normally do.

So, the answer is two ASCII characters.

---

We're of course only discussing raw RSA here. If RSA (OAEP) padding needs to be applied then you should remove the padding overhead. So this doesn't directly translate to secure, real life implementations of RSA.