How can I avoid calculating with huge numbers when implementing the RSA algorithm

Question

There is 26-letter English alphabet.

There is the plain text: TRYAGAINLATER. I need to encrypt it by RSA algorithm with the public key 53. What is the ciphertext?

Therefore: M = TRYAGAINLATER, M=19 17 24 0 6 0 8 13 11 0 19 4 17.

Encryption: $c = m^e \pmod n = m^{53} \pmod{26}$

The problem is that $m^{53}$ is huge number. How can I avoid this?

Answer 1

$\def\Z{\mathbb Z}$Usual (i.e. real life) RSA works with huge numbers, not with small numbers like 53 and 26. (The numbers there are, for example, 1024-bit numbers for the lowest acceptable security level nowadays.)

But anyway, the core mathematic operation behind RSA is modular exponentiation - you exponentiate not in the ring of integers $\Z$, but in the modular ring $\Z/_{n·\Z}$ (where $n$ is the modulus). You get the same result by exponentiating in $\Z$ and then reducing, or by reducing after each multiplication step ... and the latter avoids the overhead of really huge numbers.

So, you calculate $c = (…((m · m \bmod n) · m \bmod n ) · … · m \bmod n)$, such that each intermediary result is a number smaller than $n$, instead of calculating the huge number $m^e$ directly.

(This is the naive exponentiation, which takes $e$ steps - there are faster algorithms which only need around $\log_2 e$ steps, like square-and-multiply.)

But your example is faulty, too - the public exponent is normally a number smaller than the modulus (which is a part of the public key, too, and actually the more important part).

Answer 2

In addition to the valid points that Paŭlo brings up (and to highlight, you really don't want to use naive exponentiation by multiplying $e-1$ times, but you want a $O(\log e)$ solution such as square-and-multiply), there is another issue with how RSA is used.

You're encrypting the message by splitting up the message into pieces, and performing the RSA encryption on each piece. In practice, we never do this. Instead, to encrypt a message using an RSA public key, we either:

• Select a random symmetric key (for example, an AES key), and send both the message encrypted with the symmetric key, and also the symmetric key encrypted using RSA and the RSA public key.

• If the message you want to send is guaranteed to be small enough (that is, after random padding, it will always be smaller than the RSA modulus), we can simply use RSA to encrypt the message.

The first option is by far the most common (as we don't have to worry about the message being too long).

While I'm on the topic of using RSA properly, there's one additional point: to encrypt a message using RSA, you always need to add a random padding. This is for two reasons:

• RSA has the following homeomorphic property: $E(A) \times E(B) = E(A \times B)$; if you give small integers to the RSA primitive, an attacker can use the above property to deduce the encryption of other values. Padding makes all (or almost all) values to give to RSA large, and hence this property cannot be exploited.

• If you do RSA (or any public key encryption primitive) determanistically, then an attacker can check to see if an encrypted message corresponds to a specific value $V$ simply by computing $E(V)$ and seeing if he gets the encrypted messsage. By adding nondetermanism (randonmess) to the padding, then the attacker cannot do this; even if he guesses $V$ properly, his $E(V)$ will be different with high probability (because he will likely use different values for the padding bits).

Answer 3

As Paŭlo and Poncho cover, you don't avoid large numbers.

In real life cryptographic implementations (where RSA is concerned) you need a bignum library or bignum implementation even to store numbers of the magnitude required; as you've no doubt noticed, practically handling large numbers with what a programming language usually provides you isn't easy. These libraries take the ideas presented in Knuth's Seminumerical Algorithms and implement them - basically chain together a series of integers. Note there are more algorithms around now than were known then - modern computer arithmetic is a compendium of algorithms for doing "bigint" efficiently. Look in "modular arithmetic and the FFT" then "Modular exponentiation".

In terms of software, GMP is I think the most well known. LibTomMath also deserves a mention. OpenSSL has its own. To a very small degree I've been involved in a couple of efforts you can no doubt find. It's slightly off topic, but a lot of effort goes into optimising this work to the point that it is as fast as possible on a given architecture.

Another point worthy of mention is the space requirement. In GMP, a signed integer is represented by a structure which contains two elements: a pointer to an array of integers, and a signed integer representing the size. That puts the overall cost, assuming 32-bit fields, of representing a 2048-bit prime at $(2048+32+32)/8=264$ bytes, including the size of the pointer. You may lose some space to alignment by your compiler, but the memory-cost is negligible.