Join Log in
Score:1
avatar Crypto

Asymmetrically encrypt a short message into a short string

cn flag
Xavier

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.

163
0 + 0
kelalaka avatar
in flag
kelalaka
[ECC Elgamal encryption](https://crypto.stackexchange.com/a/9990/18298) if you can bear with [the message encoding](https://crypto.stackexchange.com/q/76340/18298)
0
Reply
Score:2
poncho avatar Crypto
my flag
poncho

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).

0 + 0
cn flag
Xavier
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 https://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?
0
Reply
poncho avatar
my flag
poncho
@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.
0
Reply
poncho avatar
my flag
poncho
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...
0
Reply
poncho avatar
my flag
poncho
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)
0
Reply
poncho avatar
my flag
poncho
@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 https://www.secg.org/SEC2-Ver-1.0.pdf)
0
Reply
cn flag
Xavier
Thank you for the clarification to be honest this is all a bit over my head. Do you know of a good example implementation of ECIES using the secp192r1 curve?
0
Reply
poncho avatar
my flag
poncho
@Xavier: a quick google finds https://github.com/insanum/ecies - it uses OpenSSL (and while it's not specific to P-192, OpenSSL supports that curve). Note that your requirements are fairly specific - it'll take a bit of work to convert that code to something that meets your requirements
0
Reply
cn flag
Xavier
thanks for all of the help, I have a working implementation following your design. I found this [example](https://asecuritysite.com/ecc/ecc3) helpful in grasping ECIES. My only problem now is figuring out how to only pass the x value and solving for the entire point when decrypting. My understanding is given x I would solve for y in the elliptic curve fromula `y^2 = x^3 + ax + b`. Looking at the curve [secp192r1](https://neuromancer.sk/std/secg/secp192r1) when I solve for `y` the above example implementation asserts that the point is not on the curve.
0
Reply
ธงชาติไทย
Elon Musk
I sit in a Tesla and translated this thread with Ai:

mangohost

Post an answer

Most people don’t grasp that asking a lot of questions unlocks learning and improves interpersonal bonding. In Alison’s studies, for example, though people could accurately recall how many questions had been asked in their conversations, they didn’t intuit the link between questions and liking. Across four studies, in which participants were engaged in conversations themselves or read transcripts of others’ conversations, people tended not to realize that question asking would influence—or had influenced—the level of amity between the conversationalists.