Going backwards after decrypting a message using RSA

Question

I am trying to learn how RSA cryptography work. I think I have figured out everything, except getting back the characters I started with.

For example, lets say I have a base of 26 (Eng alphabet) and sections of 4 characters at a time. I have a string "ABCD" I want to encrypt. What I do is assign each character to a number, starting from 0. So $$"ABCD" \implies (0,1,2,3)$$ After that I add the base $$0*26^{0}+1*26^{1}+2*26^{2}+3*26^{3} \implies 54106 := M$$ So $M$ is my unencrypted string. Lets just stop here, lets say I cryptate it and send it over to a buddy, he decrypts it and end up with $54106$, how should he go from there?

I have to end up with $0*26^{0}+1*26^{1}+2*26^{2}+3*26^{3}$ again so I can pick out the letters otherwise it makes no sense. Anyone who know?

Answer 1

This is only remotely related to RSA or cryptography. What you want is just a base conversion between base 10 and base 26. You have already done the direction $10\rightarrow 26$. The inverse is a repeated application of the Euclidian division:

Suppose you want to convert the number $n$ to base $B.$ Then perform

$$q_{k+1} = \lfloor q_k / B\rfloor, \;r_{k+1} = q_k \bmod B$$

with $q_0 = n$ until a $q_k$ becomes zero. The base-B representation is the reverse concatenation of the remainders. For you example

q_k    r_k
54106   -
2081    0
80      1
3       2
0       3

So $59106_{10} = 3210_{26} = 3\cdot 26^3 + 2\cdot 26^2 + 1\cdot 26^1 + 0\cdot 26^0$

For more info see e.g. https://en.wikipedia.org/wiki/Positional_number_system#Base_conversion

Answer 2

The other anwer by gammatester is quite to the point. I just want to add that normally people do not encrypt actual text with RSA itself, they send a pair: first a 16 or 32 byte key $K$, encrypted with RSA, using a form of padding. And then the actual text encrypted with $K$, using a standard algorithm like AES in, say GCM mode. The receiver decrypts the key, and then decrypts the text.

Usually the see the RSA modulus (128 bytes, so 1028 bits, is pretty common) in base 256 (so as a sequence of bytes) and then the keydata is encoded as a number of the same size as the modulus by a sequence of bytes (assuming 128 bytes an a 32 byte key:)

00 02 r[0] r[1] ... (random non-zero bytes) 00 32 key bytes

if we use the common PKCS1.5 standard.

Sending the key under RSA ensures that it always fits into any reasonable modulus (and has a fixed size and is a different number every time, even for the same key, because of the random bytes), and minimises the number of (expensive) RSA operations trading them in for cheap AES operations.

So the base 26 example is purely academic and never occurs in practice, and has many insecurities.