4
$\begingroup$

Total Crypto Noob here.

I was wondering why in ECDSA the Signing Key is so much (half of) shorter than the Verifying key?

Lets look at some python code:

import ecdsa
import binascii
signing_key = ecdsa.SigningKey.generate(curve=ecdsa.SECP256k1)
verifying_key = signing_key.get_verifying_key()
print(binascii.hexlify(signing_key.to_string()) 
print(binascii.hexlify(verifying_key.to_string())

b'662ab496304f2d99aca32d813dbcba3c3ae10ab2b3359fbe43b05ee40b458cec'
b'6632feae645469c16cb31d7e1364cae247bd4322040d7089476614399bcf59b2fccf5060686ab09ee64e1b768ba037184e9a87001a4897a745721f99000b44ee'

lets assume I send verifying keys over the network or store them someware, it would be nice if they were not so long. Is there a way to compress them?

I assume it would be really bad to use the keys vice versa, but I don't understand why.

| improve this question | |
$\endgroup$
  • $\begingroup$ Normally, one should at least check for some cases. This is just compression as Maarten showed. $\endgroup$ – kelalaka Jul 29 '19 at 17:28
  • 1
    $\begingroup$ You are using SECP256k1 which means curve P-256. The private key is just a 256 bits (32 bytes) number. The public key is actually a coordinate (256 bits X, 256 bits Y). $\endgroup$ – Bao Hoa Aug 2 '19 at 9:47
3
$\begingroup$

In ECDSA, the private key is an integer $n$ between $0$ and $q$ where $q$ is the number of points of the curve. In the case of secp256k1, it is a $256$-bit integer.

From the base point $G$ of the curve, we can compute $P = nG$ (which is $G + G + \ldots + G$ where $G$ appears $n$ times) and it is the public key. A point has two coordinates of the same size of the private key, so in this case the point $P$ can be stored as two $256$-bit integers.

So, $(n, P)$ is a key pair, the first part is used to sign, the second is used to verify a signature.

[Completing the answer about point compression]

The point $P=(x_0,y_0)$ satisfies the curve equation is $y^2 = x^3 + Ax + B$. So $y_0$ is a solution of $y^2 = x_0^3 + Ax + B$. There are two solutions : $$ \sqrt{x_0^3 + Ax_0 + B} \quad\text{and}\quad -\sqrt{x_0^3 + Ax_0 + B} $$ Only one bit of information is needed to know which one of the solution is $y_0$. This can be done for example by keeping the least significant bit.

| improve this answer | |
$\endgroup$
  • $\begingroup$ are you sure there is no typo in "q and q where q"? If I am right then there is no way of shortening P without having to store n, which is bad? $\endgroup$ – SimonSchuler Jul 29 '19 at 13:54
  • $\begingroup$ "Between $0$ and $q$", sorry for the mistake. There are ways to store the point $P = (x,y)$ with less bits: we can keep only one bit of $y$ so the point can be stored as $256+1$ bit (it is called point compression). The right coordinate $y$ can be recovered with the curve equation the extra bit. $\endgroup$ – corpsfini Jul 29 '19 at 14:43
7
$\begingroup$

The secret $s$ in ECDSA is a value in the range 1 and the order of the group (exclusive). Some parameters are chosen in such a way that you can simply generate any value within the amount of bits as the chance that you're outside of the range or choose 0 is very small indeed. The public key is a point on the curve, calculated by performing $w = s \cdot G$ - using (modular) point multiplication as $G$ is the base point of the curve.

Generally the value $s$ is just encoded as an unsigned statically sized, big endian integer of the same size as it takes to encode the order of the group in bytes. The public point $w$ however can be encoded in different ways. You've shown a simple concatenation of two unsigned statically sized big endian x,y coordinates. That means of course that it is two times the size of the secret $s$. To get the values of x and y you first have to split the public point encoding exactly in half and then decode the separated values of x and y.

Usually this "flat" encoding (i.e. without structure) is preceded by a byte with value 04 to indicate that it is an uncompressed point. It is however possible to create a compressed point, which is just a single bit larger than the x value. Unfortunately that bit is not available in the encoding of x, so generally the point x is prefixed by a byte with either value 02 or 03 (depending on the value of x and y). Then the value of y can be retrieved by uncompressing the point. So yes, you can "shrink" the public key.

Bitcoin is even sneakier and allows you to recreate the public key out of the signature. That's probably worth a separate question though.

Note that you must first trust the public key before you can use it to verify any signature. If you don't know who's public key you're using, then you do not know who's signature you're verifying either.

| improve this answer | |
$\endgroup$
  • $\begingroup$ If the this is the lib you're using, I don't see any support for point compression unfortunately. Better switch to e.g. an OpenSSL wrapper lib for Python. $\endgroup$ – Maarten Bodewes♦ Jul 29 '19 at 15:38
  • $\begingroup$ Thank you for your Comment, This answers my questions. The library you are linking is exactly what I am using, still, the pyBitcoin implementation uses this aswell. I will have to look at their code to see how they do compression of the keys then. Thanks again $\endgroup$ – SimonSchuler Jul 30 '19 at 7:27

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.