1
$\begingroup$

I have a string whose size is < 32 characters from the following limited character set.

  • uppercase and lowercase Latin letters: A to Z and a to z
  • digits: 0 to 9
  • special characters: !#$%&'*+-/=?^_`{|}~

I am looking to encrypt this string with a public key where the resulting message is < 64 characters.

I understand there will be a trade-off between size and security.

$\endgroup$
1

1 Answer 1

2
$\begingroup$

I am looking to encrypt this string with a public key where the resulting message is < 64 characters.

Actually, it appears you can, if you trim back the security just a little bit.

One approach would be to use ECIES with, say, P-192. (EC-Elgamal would also be workable - I think this is a superior approach)

In this scheme, the private key is a random value $r$, and the public key is a value $P = rG$, where $G$ is the generator point. To encrypt, we pick a random value $s$, and compute both $sG$ and $sP$; we send the point $sP$ (or, in your case, just the x coordinate) through a Key Derivation Function, which generates a key that we use to encrypt the actual message. The ciphertext consists of the value $sG$ (in your case, just the x coordinate) and the symmetric encryption.

Now, if we use the curve P-192, the x-coordinate of $sG$ can be expressed in 192 bits; using the alphabet we've been given (which has 81 symbols), that would take 31 characters (for example, by converting the value from 0 to circa $2^{192}$ into base 81).

As for the symmetric encryption of the message, we can use a Format Preserving Encryption method [1]; this can convert a message consisting of an alphabet of 81 symbols into a ciphertext of the same alphabet and length.

So, an encryption of 31 symbols (the largest you said you're interested in) would encrypt as a message of 31+31 = 62 symbols - within your requirements.

The security costs:

  • P-192 has "96 bit security"; that's somewhat less than we normally use - however, it's still pretty good.

  • We do leak the length of the message (because the Format Preserving Encryption method preserves the length); if that is an additional requirement, you can always pad the message to 32 bytes (with the last character indicating the actual length of the message) - with this, we still meet the length requirement


[1]: Normally, with ECIES, we use an explicit integrity transform in the symmetric encryption. I would argue that's not needed in this case - any modification of the FPE would decrypt as something random, and the adversary can always replace the ciphertext with something that decrypts to something random (by the simple expedient of picking a random plaintext, and encrypting it with the public key).

$\endgroup$
8
  • $\begingroup$ It sounds like ElGamal can be used with P-192 (Not prime maybe P-191?) to encrypt my message which I can later decrypt with a private key. I am looking at this example cryptographyacademy.com/elgamal Why is only the x coordinate needed as you say? Also where does the symmetrical Format Preserving Encryption come into play here? $\endgroup$
    – Xavier
    Dec 10, 2021 at 22:26
  • $\begingroup$ @Xavier: I looked at ElGamal; making everything fit within the restrictions you have is tricky (the curve size needs to be big enough that you can encode the string, plus the necessary variability to get to a valid coordinate; on the other hand, it can't be too big, or the ciphertext size goes over the limit. $\endgroup$
    – poncho
    Dec 10, 2021 at 22:30
  • $\begingroup$ As for where the symmetric cipher comes in, well, that is used to encrypt the actual plaintext message (while the $sG$ value is used to communicate the symmetric cipher text). So, what the decryptor does it extract the $sG$ value (picking one of the two $y$ coordinates arbitrarily), computing $r(sG)$ (which has the same $x$ coordinate as the encryptor's $rP$ value; converting that into a symmetric key (using the kdf), and then doing a symmetric decryption. I suggest an FPE symmetric algorithm, to reduce the ciphertext size... $\endgroup$
    – poncho
    Dec 10, 2021 at 22:37
  • $\begingroup$ As for why you need only the x coordinate, well, the x-coordinate of $r(sG)$ depends only on the x-coordinate of $sG$; hence to decrypt, we can convert the x-coordinate within the ciphertext back into the full $P$ (by arbitrarily picking one of the two possibilities - it doesn't matter if the one we picked was the same as the one the encryptor had). I suppose you could use point compression to pass the entire $sG$ value - however, there's no need (and that's an entire bit - we're running close enough to the size limit that that's a nontrivial concern) $\endgroup$
    – poncho
    Dec 10, 2021 at 22:38
  • $\begingroup$ @Xavier: Also, when we say "P-192", I'm talking about a specific elliptic curve which has a field size (and group order) of around $2^{192}$ - it uses a prime field and so it doesn't matter whether 192 is prime or not. It's also known as secp192r1 (as defined in secg.org/SEC2-Ver-1.0.pdf) $\endgroup$
    – poncho
    Dec 10, 2021 at 22:41

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.