RSA message encryption question

Question

I'm very new to cryptography, I wanted to know what exactly do I have to do to encrypt a three-letter message using RSA? for example if I wanted to encrypt this message $M= \text{HCP}, p=11 q=13$.

Do I have to change the letters into numbers? ($H = 7, C=2, P=15$) and then encrypt each letter alone? or add/multiply them and encrypt them all at once?

Answer 1

To encrypt a message, in RSA or other encryption schemes, we convert (encode) the messages into bits/bytes arrays that are dependent on the scheme in an invertible way!

If you consider only the English letters, with $A=0,\ldots, Z=25$ then you can make the encoding of a sequence of letters $m_0,m_1,\ldots,m_t$ with

$$m = \sum_{i=0}^t 26^i \cdot m_i$$ This method is common way to encode, remember the binary encoding? A similar idea applied here, and note that the decoding is unique. Numbers are easily converted into octets (bytes) in a computer and usually byte array is processed, some schemes use words, too.

You are going to have some problems now or future;

1. You cannot have $m \geq n$ where $n$ is the RSA modulus. If your messages are longer than the RSA modulus, then you need to split your message into parts.

   In your case, $p=11,q=13$ then $n = 143$. This can only encrypt one letter at a time. Use larger modulus, or encrypt one by one!.

2. We don't use RSA for encryption, we rather use it for signatures and for hybrid encryption like RSA-KEM.

3. RSA encryption needs proper padding like PKCS#1v.4 or OAEP to be secure against the attack, see Twenty Years of Attacks on the RSA Cryptosystem.

4. RSA Signing is Not RSA Decryption

5. For signature, one must use the Probabilistic Signature Scheme (PSS).

6. The padding, is not enough to be secure, one needs to have constant time implementation against the side-channel attacks.

7. To see how real RSA encodes see rfc8017