Are 8 letter blocks for ciphertext needed?

Question

I solved an RSA question which had enciphering key of (n, e) = (8369428283, 1234567), and encrypted message AFTHVVNJ ARCSTZFZ that consisted of 7-letter blocks in the 26-letter alphabet, (integers between 0 and 26^{7}−1), with a ciphertext of 8-letter blocks in the same alphabet.

I was then asked if 8 letter blocks for the ciphertext are needed, and to give an example of a number whos ciphertext uses 8 blocks, but I wasnt sure what to say.

For the given question 7 letter blocks would have been sufficient becuase of the presence of the letter A's at the beginning of each of the size 8 blocks.

Can someone please explain the importance of 8 letter blocks here.

Thank you

Answer 1

In base $10$, using $3$ digits we can express numbers from $000$ to $999$ so up to $10^3 -1$. So in base $26$, with 8 "digits" A-Z we can express $0$ to $26^8-1 = 208827064575$, which is larger than $n$, so in practice (as all ciphertexts will have a value $< n$) not all first digits can appear. The smallest possible value not starting with A is of course BAAAAAAA which corresponds to $26^7=8031810176$, which is indeed smaller than $n$ still, but not by much, and C as a first value would correspond to numbers at least $2\cdot 26^7 > n$.

Conclusion: all ciphertexts are writable in a unique way as 8 letter strings, the first of which is A and sometimes B. If you can decrypt with your $n$ (so if you have $d$) you can decrypt BAAAAAAA to get a (probably nonsensical) plaintext whose ciphertext really needs a block of 8 long. And it makes sense, for ease of parsing, to always send 8 letter blocks, even if most blocks start with 'A'.

This way of encoding text is actually purely theoretical and never done. A similar question I answered here, where we also got extra A's at the start of the block in the plain text; maybe that was a sort of padding to make full blocks too?

BTW, practical systems use hybrid forms of encryption: we send a (AES)-key in a randomised and padded RSA-message together with a symmetrically encrypted (with that plain key) message. This base 26 encoding is inefficient and deterministic.