9

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?

Pascal Cuoq
  • 79,187
  • 7
  • 161
  • 281
  • I think the space of all elliptic curves is a stack, so no? – Kerrek SB Sep 06 '13 at 08:46
  • Not convinced this is on topic. It's both a question for mathematicians/cryptographers (off topic) and a request for an existing library or resource (off topic). – Duncan Jones Sep 10 '13 at 18:35
  • @DuncanJones As a question to mathematicians, this question is a non-question. The mathematics of RSA are done. The number of intermediate results and their sizes are implementation details. I admit that my call for an existing implementation makes it off-topic that way. Would it help if I said “I don't understand anything to PolarSSL's {bignum,rsa}.{c,h}, please help me to hard-code static allocations of appropriate sizes”? Probably not, then it would not demonstrate minimal understanding of the problem being solved. Which I certainly don't have. I am doomed. – Pascal Cuoq Sep 10 '13 at 19:40
  • @DuncanJones I think that the rationale for making recommendation for external resources off-topic off-topic is that questions such as “What is the best programming language to write games in?” aren't constructive; they “attract opinionated answers and spam”. This hasn't happened with this question so far. – Pascal Cuoq Sep 10 '13 at 19:49
  • 1
    I'm pretty sure that the standard implementation of Curve25519/Ed25519 doesn't use any memory on the heap. Take a look at [LibSodium](https://github.com/jedisct1/libsodium) for an easy to compile version. Since ECC implementations are often curve specific they often don't require dynamic allocation. – CodesInChaos Sep 11 '13 at 19:07
  • Are you married to PolarSSL? Although not exactly what you asked for, you can change OpenSSL's default allocation functions with a call to `CRYPTO_set_mem_functions()` (there is also a matching `CRYPTO_get_mem_functions()`). This means just before you perform cryptographic calls with OpenSSL's crypto library, you can swap out the old allocation functions, and put in yours that uses statically allocated memory, then when the call returns, swap the functions back with the original. – jxh Sep 20 '13 at 19:28
  • @jxh PolarSSL has callbacks for anything you might want to configure, similar to what you describe for OpenSSL. My question was more about statically determining good bounds for the number and size of the blocks that the library would request, knowing only the lengths of the key and message. PolarSSL's multi-precision integers are by default allocated snugly in blocks of just the right size, even if that means resizing later: this seems to make the change I would need nontrivial. I will take a look at how OpenSSL does it. – Pascal Cuoq Sep 20 '13 at 19:36
  • You can certainly implement RSA without dynamic allocations (why not?). My own implementation (for fun) used only stack allocations internally. Most numbers only need to be as wide as the key size, with some intermediate numbers being a bit wider or sometimes twice as wide -- assuming modular arithmetic is used throughout. – Dmitri Oct 03 '13 at 00:17

2 Answers2

3

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.

Community
  • 1
  • 1
jww
  • 97,681
  • 90
  • 411
  • 885
1

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.

Pascal Cuoq
  • 79,187
  • 7
  • 161
  • 281