Is there an asymmetric encryption algorithm that maintains the length of the plaintext?

Question

I want to protect some registers by encrypting them without providing additional memory space. Is there a encryption algorithm that will maintain the length of the data to be encrypted? (i.e. plaintext.length=ciphertext.length)

Answer 1

Basically, you're asking for an asymmetric cipher that can have a block size either equal to your message, or to the character size of your message encoding (8 bits for ASCII/UTF8, 16 and 32 for UTF-16 and -32 respectively).

Vanilla RSA can technically do this; you must simply limit the bitsize of the unsigned integer N, produced by choosing two random primes p and q (p must thus be less than sqrt(N), and the domain of possible q values is reduced the closer p is to sqrt(N)). The maximum N can either be of the same order of magnitude as the concatenated message, or some even divisor of it (down to 1 byte/character)

There are however two serious problems with this:

• RSA is only secure for very large key sizes; its difficulty is inherent in finding the p and q that produce N, and so the security of any encryption including RSA is in having a literally out-of-this-universe number of possible keys to choose from**. So, tailoring key size to message length would only be secure from a key size perspective if the message were at least 256 ASCII characters (producing a 2048-bit message allowing a securely-large key). Small message sizes (key lengths of 8-32 bits) are trivially broken; worst-case (for an attacker), a 32-bit key requires finding a prime integer p < sqrt(2³²) = 65536 that evenly divides N; by the prime number theorem there are only 5900 possibilities. You could almost feasibly crack such a key "by hand" with a calculator.
• In addition, and more serious, RSA without the proper encryption padding is vulnerable to known-plaintext attacks and in cases that reduce to trivial examples. OAEP, the gold standard RSA padding scheme, uses two hash functions, one of which must have a bit length at least the bit size of the plaintext message, and the length of the full padded message is equal to the sum of both functions' hash message lengths, so the padded message will always be greater than the unpadded message.

Therefore, the approach of plain RSA with a tailored key size should be regarded as fundamentally flawed. Every other public-key system I can find, such as elliptic-curve encryption, has similar limitations based on the math used for the encryption.

**2048 bits is the smallest recommended key size for X.509 digital certificates. 2²⁰⁴⁸ ~= 3.2317e616. Putting this number in perspective, a Planck volume is 4.22419e−105 m³; this unit is, in theory, the granular "resolution" of the universe, based on the Planck length being the smallest distance that any instrument could ever measure. The observable universe is at least on the order of 1e27 m in radius (13.7 billion light years), so the sphere of our observable universe is ~ 4.189e79 m³ ~= 1.7e185 Pl³. That means that if we could not only "count the stars and call them by name", but assign an ordinal to every granular piece of our observable universe, the number of numbers we'd need is 400 decimal digits shorter than the number of numbers inherent in the RSA keyspace.

Answer 2

Strictly speaking, no secure asymmetric encryption can maintain the plaintext length. The problem is that the public key, being public, is known to everybody. Therefore, everybody can "try" potential plaintexts and encrypt them, to see if the result matches the encrypted text. That's exhaustive search on the plaintext instead of the key, and it works because plaintext has some "meaning" and thus a structure. For instance, if encrypting bank orders, there are only a few billions of possible combinations of amount and destination account, and this is amenable to exhaustive search.

To prevent this issue, a secure asymmetric encryption algorithm MUST NOT be deterministic: the encryption process MUST include some randomness, so that a given plaintext, encrypted with a given public key, may result in a large set of possible ciphertexts. This is what happens, e.g., in RSA, as defined by PKCS#1: the plaintext is first padded with random bytes. Upon decryption, the padding is unambiguously detected and removed, of course.

Not being deterministic necessarily implies that the set of possible ciphertexts is much larger than the set of possible plaintexts; in other words, the ciphertext is necessarily larger than the plaintext.

At least, the size overhead can be kept constant (a fixed increment, rather than a size increase proportional to the input message length) by the usual method of hybrid encryption: you asymmetrically encrypt a sequence of random bytes K, which you then use for symmetric encryption of the plaintext. For that matter, you may replace the asymmetric encryption with a key exchange mechanism; if you are on a size budget, I suggest having a look at elliptic-curve Diffie-Hellman: with the standard P-256 curve, you can keep the per-message overhead to 32 bytes.

With RSA, assuming that the message to encrypt is longer than the key, you could go a bit lower (PKCS#1 v1.5 padding implies at least 11 bytes of overhead; with a 2048-bit RSA key, you could encrypt with RSA the first 229 bytes of message, and a 16-byte symmetric key, and then use that key for the rest of the message with AES-CTR; that would be a 27-byte overhead).

Answer 3

It sounds like you're looking for "Format Preserving Encryption", if you haven't looked at FPE before, have a look at the wiki article on it. It has a lot of good references.

http://en.wikipedia.org/wiki/Format-preserving_encryption

I'm not sure such a thing as Asymmetric Format Preserving Encryption exists... there's lots of discussion around it when you search on that term though.

Answer 4

I suspect there is a typo in your title line. If "asymmetric" is "symmetric", then my answer is: All typical block ciphers satisfy your contidtion. If block length is a problem for your application, you can use a stream encryption. (I am not aware of any asymmetric encryption algorithm satisfying your condition. I even surmise that's impossible.)

Answer 5

If it's a software-defined algorithm, you'd just have to use another register to store the temporary steps as you decrypted it.

You'd be better off looking at something like AES-NI.