Implementation of RSA without dynamic allocation

Question

A typical RSA implementation incorporates a multi-precision integer library. A typical multi-precision integer library uses dynamic allocation to represent large integers as arrays of machine words just the right size.

I expect there must be a bound on the mathematical integers one may encounter when using the multi-precision integers only to encrypt or decrypt messages of known length (typically, symmetric encryption keys) with, say, RSA-2048, and that it would be possible to implement the algorithm by allocating space for all necessary intermediate results either statically or on the stack.

I found this forum thread suggesting this is possible. It does not indicate maximum integer sizes. Perhaps it is obvious (“you need 2048 bits for all integers, duh!”). In any case, I would be more interested in an already existing implementation, if there is one.

As a side-question that does not deserve its own entry, do typical implementations of elliptic curve cryptography require dynamic allocation?

Answer 1

Is it possible to implement a multi-precision integer class without dynamic allocation

Yes.

I'm aware of a similar implementation in C# BigInteger Class. (And not withstanding what the underlying clr runtime does).

I'm not aware of any static-sized buffers in C/C++. But I'm only familiar with Botan, Crypto++, and OpenSSL.

From what I've seen of implementations, the public exponent e sometimes gets an optimization of making it an int or long. But n and d are multi-precision. (And I'd like to see how that blows up some day).

Finally, routers and other low powered equipment often take this optimization on send and receive buffers (I used to work with a guy who was an electrical engineer and designed routers). They simply reserve a chunk of memory and the software uses an index to access the static buffer. So its not hard to believe they have taken the optimization you speak of.

---

RSA-2048, and that it would be possible to implement the algorithm by allocating space for all necessary intermediate results either statically or on the stack.

Yes, you could do that with a sign magnitude scheme using fixed sized buffers if you accepted to limit the maximum RSA modulus size or EC prime field size.

An RSA public key is (e,n). Notwithstanding the warning on small e's, you would need two buffers of 2048/8 = 256 byes or octets.

A RSA private key without the precomputation tricks is simply (e,d,n). So you would need three buffers of 256 bytes or octets.

If you were working on a PDP-8 with 12-bit bytes, then you would need fewer bytes.

---

It does not indicate maximum integer sizes.

The devil in the detail is probably multiplication. So you would need a scratch buffer to perform the multiplication. That means you will need a ~2*2048-bit sized buffer (multiplying 2 m sized buffers creates a result of size 2m -1 ). The result of the multiplication would then have to be reduced. Their may be further optimizations, but I don't usually concern myself with those details.

Related, the maximum message size and maximum cipher text size is related to n. In Crpyto++, they can be retrieved with MaxPreImageSize (for the plain text) and MaxImageSize (for the cipher text). MaxPreImageSize and MaxImageSize return n - 1.

---

As a side-question that does not deserve its own entry, do typical implementations of elliptic curve cryptography require dynamic allocation?

It depends on the underlying implementation. A curve over a prime field is defined by domain parameters (from Certicom's SEC1, Elliptic Curve Domain Parameters, Section 3, page 16):

Elliptic curve domain parameters over F_p are a sextuple:

   T = (p, a, b, G, n, h)

• p is a large prime and it needs a multi-precision integer

• a and b are coefficients that define the curve. The usually are 'small' (for example, a = 3), but they could require multi-precision integers for non-standard curves. For example, DJB's ed25519 curve is y^2 = x^3 - 102314837768112 x + 398341948620716521344.

• G is the base point, so its really an element (or point) on the curve. That means is a (X, Y) coordinate and probably requires multi-precision integer.

• n is a prime of order G which means its nealry as large as n

• h is the cofactor and its usually very small: 4 or 2, or 1.

When you create a key pair for the curve, you need a random private exponent d (or x), and that creates an element (point on the curve) after the exponentiation. That is, Public Key (X, Y) = G^x. So you have three more multi-precision integers.

A curve over a binary filed needs a way to express the polynomial. So you would probably still need the multi-precision integer (used for p in the prime field).

So, most of the 'things' on an elliptic curve need a multi-precision integer.

You can see examples of the domain parameters at, for example, Elliptic Curve Cryptography (ECC) Brainpool Standard Curves and Curve Generation.

Answer 2

This RSA implementation, inside BearSSL, by Thomas Pornin, has exactly the properties I was asking about. From BearSSL's webpage:

No dynamic allocation whatsoever. There is not a single malloc() call in all the library.

…

On big desktop and server OS, this feature still offers an interesting characteristic: immunity to memory leaks and memory-based DoS attacks. Outsiders cannot make BearSSL allocate megabytes of RAM since BearSSL does not actually know how to allocate RAM at all.