RSA Cryptography and grouping integers

cryptographynumber theory

I know that for RSA cryptography, you need a public key which is a semi-prime $n$.

I am trying to do a question involving the key $n=187=11 \times 17$ (I know in reality one would use a much, much larger prime, but I need to do this by hand).

I have been told that we need to map integers $A \rightarrow 00; B \rightarrow 01; …; Z \rightarrow 25$ and that the message needs to be grouped in blocks so that no block is larger than $n$.

I should be able to use $e=7$ since $GCD(7,187)=1$.

Say I want to code the letter $E=04$,
– If I group in blocks of two, I have $4^7 \equiv 115 \text{ mod } 187$, meaning that the ciphertext will need to be in blocks of three.
– If I group integers in blocks of three, then I may get numbers more than $187$. For example, $ERS \rightarrow 041 \text{ }718$, clearly the second block is more than $187$, which will cause a problem when trying to decrypt.

Does this mean that I can't use $187$ as a key? If so, is there a rule that allows us to determine which semi-primes can be used and which can't?

If $187$ is valid for $n$, how would I group the integers so that they can be encrypted?

Thanks for any help!

Best Answer

You can use $e=7$ if $\gcd(7,\phi(n))=1$ and $\phi(n) = 10 \times 16= 160$. So indeed it's OK to use.

The "messages" $m$ should be $1 \le m < n$ (they need not be relatively prime with $n$, the encryption/decryption works in either case). Of course $0$ is pointless (and $m=1$ too), as these will be fixpoints of the RSA encryption. Which is why RSA is always used with large numbers and random padding etc.

As you are told to use an encoding of letters to two-digit "blocks", this is already ambiguous: AA (rare in English, not so much in Dutch, German or Finnish) would be 0000, so the integer (class mod $n$ really) $0$, but apart from the fact that the encryption stays $0$ regardless (and so everybody will know this, without "breaking" the RSA), upon reception one also cannot determine whether a single or a double A block had been sent... AB would be 0001 or $1$ but cannot be distinguished from plain B etc. It's a truly miserable encoding. ERS could be sent as 04 17 or $m=417$ as one number and 18 (and $m=18$) in the next, (anything that follows would be make it two digits larger and surely above $n$ which is never allowed). A received plain message $417$ could also be construed as coming from AER (the initial 00 would probably have been left off) so we can still have decryption problems. So I'd go left to right, ignoring initial $0$'s in numbers, grabbing an extra two digits from the next letter if the total result fits within $n$, otherwise start a new group/number there. In many cases we'll have single letters as messages. RSA as a mono-alphabetic, essentially.

It's far from optimal, but these exercises are meant for understanding a bit of the maths of RSA, not on how it's actually being used in practice. (2048 bit numbers and random padding, and typically AES-keys (to encrypt text messages) are sent via RSA, not the text messages themselves).

Related Question