0
$\begingroup$

Let's assume that I have key pair generated using the following curves: brainpoolP256r1, brainpoolP320r1, brainpoolP384r1 or brainpoolP512r1. Do I need information which curve was used to decrypt message? Can I infer which curve was used based on the private key?

$\endgroup$
2
  • $\begingroup$ You cannot see from a decrypted message what was used to decrypt it. Could you update your question with the actual scheme used and if you maybe meant to test what curve is needed to decrypt the message? $\endgroup$ – Maarten Bodewes Sep 25 '18 at 13:33
  • $\begingroup$ Do you need the modulus and/or the curve equation when applying the decryption algorithm? Both of those will already identify the curve $\endgroup$ – tylo Sep 25 '18 at 15:45
6
$\begingroup$

This awfully looks like homework, but hey, here we go. Each curve has an order, which is the number of points on the curve (specifically, the number of points into a subgroup of prime order of the curve, but in the case of the Brainpool curves, the subgroup is the whole curve). A private key is a non-zero integer modulo the curve order; i.e. if the order is $n$, then the private key is a number between $1$ and $n-1$. In practice, the size of the private key, expressed in bits, will be close to the size of $n$ (the size in bits of an integer $x$ is the integer $k$ such that $2^{k-1} \leq x \lt 2^k$).

Curves brainpoolP256r1, brainpoolP320r1, brainpoolP384r1 and brainpoolP512r1 have orders of size 256, 320, 384 and 512 bits, respectively. Thus, look at the size of your private key; this should allow you to infer which curves you are talking about.

(Technically, a 255-bit integer, for instance, could be a valid private key for all four curves, since it would be in the accepted range for all four curves; however, probability that a private key, chosen uniformly in the range for brainpoolP320r1, ends up being a 255-bit integer, while it had a whole 320-bit range to chose from, is less than $2^{-35}$, so it won't happen often. In that sense, your answer won't be absolutely guaranteed to be correct in a mathematical sense, but it can be a good guess nonetheless.)

$\endgroup$
2
  • $\begingroup$ Often the number is encoded as a statically sized integer (in an OCTET STRING), so the issue in the last section doesn't arise. I had to look this up for somebody and I at least came to this conclusion given some RFC. Now which RFC I have to look up. $\endgroup$ – Maarten Bodewes Sep 25 '18 at 10:17
  • 2
    $\begingroup$ @MaartenBodewes The encoding is described in ANSI X9.62, and this has been imported into RFC 5915. I did not bring it up in my answer because chances are that it is some homework with the integer spelled out as an integer, not encoded. Indeed, if the private key is encoded as per X9.62, then it will be part of a structure that also include an OID for the curve, and the question is moot. $\endgroup$ – Thomas Pornin Sep 25 '18 at 13:20
0
$\begingroup$

Do I need information which curve was used to decrypt message?

ECIES (the algorithm indicated in the tags) uses hybrid encryption. The message for hybrid encryption can have any size and value. It is therefore impossible to see what algorithm has been used to decrypt the message. Information about the decryption is required to determine the curve used.


The key length can be determined from the public key that is part of the ECIES ciphertext message. From that it should be possible to iterate over all known standardized curves with that same size and find the curve by performing the decryption. You would need the private key for that of course.

If it is a brainpool prime curve - as in the question - then there will really just be one candidate (e.g. brainpoolP256r1 for 256 bit public key). So it is possible to determine the curve without involving the private key.

So it is possible to determine which standard curve is used for encryption / required for decryption.

---

Can I infer which curve was used based on the private key?

Generally the curve is considered part of the private key and encoded with the other information (such as secret $S$) about the private key. A common encoding format is X9.62 which contains either the curve parameters or an OID indicating which curve is used.


If you just have secret value $S$ then you should be able to determine the size of the curve by the encoding: generally the private key is encoded in as many bytes as required to encode the order of the curve (using the minimum number of bytes) - left padded with zero bytes.


Generally the private key will have approximately the same size as the order of the curve - which determines the key size. The chance that the private key is of a size that fits a smaller curve is really small. As indicated by the answer of Thomas, the chance that a brainpoolP256r1 bit private key fits a brainpoolP224r1 key is about one in $2^{32}$ when encoded using the minimal number of bits. This chance decreases to one in $2^{64}$ for the larger 320, 384 and 512 brainpool prime curves.

So even if a non-standard, minimal encoding of the secret $S$ is used then the curve size and therefore the curve should be easy to determine with a high level of certainty.

---

You would be out of luck for unpublished proprietary curves of course; it is not possible to determine the domain parameters from just the secret $S$, the public point $W$ and/or the ciphertext message.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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