[SOLVED] Am I getting this right about the public/private keys?

Hello there,

First time posting for me so apologies ahead of time if I may come off as "stupid".

But I do have a knackering question that's been bothering me for a while. It's the kind of question that you can't easily google an answer for(unless you want to read through a hundred pages of a standard).

It may be in plain sight generally but I wanted to ask here for a definitive quick solution.

The question?

I understand that in cryptography, public key cryptography, there is the public and private portions of what is referred to, as a key. The key is in itself a single logical entity, comprised of the 2 components(public & private) which coincidentally are also called keys? Correct? (This is often already the first bit of confusion).

The second bit is that I want to know in example cases, which portion can do exactly what operation.
As in.
If the public key is used to "sign" (Talking specifically about RSASHA256 in this example) some sort of data. It is first ran through the hash algorithm of SHA256, correct? Then after that, the result is taken and thrown into the RSA algorithm to produce the random string of symbols(characters, whatever, base64 usually?) that can then be validated ONLY by the private portion of the key/private key?

And vice versa, if the operation is done again using the private key. Is that only verifiable by the public portion of the key/public key?

My main question is. Is it possible to "decrypt"/"verify" data ran through the cyptographic function using either side of the key, verifiable/decryptable or something something checkable with the same side of the key aswell?


Data X > public key > result Y ?

Result Y > public key > Data X/or verifiability ?

Or is it 'exactly' as the name proposes, asymmetric, meaning if one was used to operate then it itself can no longer really turn it back, but the other component of the key is needed?

I don't know why, but that has always been a place of confusion for me, especially regarding public keys, since they are used to decrypt data coming from the private key owner and also used to sign data and then I think I've heard that they can also be used to check their own signed data somehow? I'm guessing this bit is where I've either misunderstood it or gotten it wrong entirely.

Many thanks for whoever cares to answer.

Thanks for reading.

Originally Posted by NadEFurY I understand that in cryptography, public key cryptography, there is the public and private portions of what is referred to, as a key. The key is in itself a single logical entity, comprised of the 2 components(public & private) which coincidentally are also called keys? Correct? (This is often already the first bit of confusion).

Often, this is referred to as a key pair, consisting of a private and an associated public key. You never share the private key, but your public key can be used by anybody.

If the public key is used to "sign" (Talking specifically about RSASHA256 in this example) some sort of data. It is first ran through the hash algorithm of SHA256, correct? Then after that, the result is taken and thrown into the RSA algorithm to produce the random string of symbols(characters, whatever, base64 usually?) that can then be validated ONLY by the private portion of the key/private key?

You sign something (a document, an email, a software package, ...) with your private key. People then use your public key to decrypt the encrypted signature.

The signature is a hash of the content of the thing you are signing. You use a cipher e.g. RSA to encrypt it with the private key. To check the signature, the hash is decrypted with the public key (the cipher that should used is included in the public key's data). Then the hash of the content is created and compared to the decrypted hash.

My main question is. Is it possible to "decrypt"/"verify" data ran through the cyptographic function using either side of the key, verifiable/decryptable or something something checkable with the same side of the key aswell?

I don't know, but this is not normally how it's done.

Data X > public key > result Y ? Result Y > public key > Data X/or verifiability ?

You would use the private key in the second step. Although I am not sure if the public key works as well.

Data X > public key > result Y ? Result Y > public key > Data X/or verifiability ?

I'm aware the intended operation is to use the opposite key, but is what I proposed also possible?

If that answer is a definitive NO, then that would clear the whole topic up quite a bit for me.

Thanks.

Originally Posted by NadEFurY I'm aware the intended operation is to use the opposite key, but is what I proposed also possible? If that answer is a definitive NO, then that would clear the whole topic up quite a bit for me.

NO, you always need the other key for the opposite operation.
So if someone sends you a message, encrypted with your public key, YOU are the only one that can DEcrypt by using your private key (as you never share that one).

In fact, if you want to send a very private message to someone, you first encrypt it with his public key. then encrypt the result again with your private one (optionally you could just put an encrypted signature under it).
Now, to read the message the receiver needs your public key (to be sure that the message is from you) but next needs his own private key to make the text readable (so no one else can read it, they could do step one, but not step 2 to really decrypt it)

Aha, ok that clears it up. That logic actually explains the whole PGP methodology aswell. Thank you.

On another note though.

I've heard that deriving a public portion of the key from the private key is possible. Why is that so?
Along with it, is likely associated the fact that the private key is often much larger in size than the public portion of it. Is this simply because of how the concept of asymmetric cryptography works?

I mean, from a bystanders point of view who has dwelled a bit into the topic but not deep enough to understand it in its entirety it feels as if they should be sort of similar, one doing one operation and the other the opposite and thus it feels as if they should also be the same size. But alas, that isn't so.

Originally Posted by NadEFurY Originally Posted by NadEFurY Data X > public key > result Y ? Result Y > public key > Data X/or verifiability ? I'm aware the intended operation is to use the opposite key, but is what I proposed also possible? If that answer is a definitive NO, then that would clear the whole topic up quite a bit for me. Thanks.

In addition to the nice ehartman's answer, keep in mind that all of this is called asymmetric cryptography. Public & private keys are not interchangeable, otherwise no security could be guaranteed (authentication, privacy...).
When the key can either encrypt or decrypt, it is called a secret key and it's about symmetric cryptography then.

I've always found this to be a nice layperson's explanation of public key cryptography:

https://blog.vrypan.net/2013/08/28/p...for-non-geeks/

Originally Posted by berndbausch You sign something (a document, an email, a software package, ...) with your private key. People then use your public key to decrypt the encrypted signature. The signature is a hash of the content of the thing you are signing. You use a cipher e.g. RSA to encrypt it with the private key. To check the signature, the hash is decrypted with the public key (the cipher that should used is included in the public key's data). Then the hash of the content is created and compared to the decrypted hash.

Originally Posted by ehartman then encrypt the result again with your private one (optionally you could just put an encrypted signature under it).

I would note that signing with your private key is not the same as encrypting; for RSA the underlying math is similar (although padding is different), but for e.g., ECDSA it's quite different.

Originally Posted by NadEFurY I've heard that deriving a public portion of the key from the private key is possible. Why is that so? Along with it, is likely associated the fact that the private key is often much larger in size than the public portion of it. Is this simply because of how the concept of asymmetric cryptography works? I mean, from a bystanders point of view who has dwelled a bit into the topic but not deep enough to understand it in its entirety it feels as if they should be sort of similar, one doing one operation and the other the opposite and thus it feels as if they should also be the same size. But alas, that isn't so.

It has to do with the specifics of the underlying math. For example, ECDSA public keys are twice the size of private keys.

Interesting.

I was basing that assumption on RSA keys, ok. I haven't yet noticed it with Elliptic Curve keys as I simply haven't yet utilized them.

But what about deriving the public portion of the key from the private key? Is this also 'simply'(well, so to speak) because of mathematical peculiarities that it's possible? Or is it perhaps possible with 1 algorithm and yet not with another?


Outside of that, the topic has been essentially answered, as the question I had in the beginning has already been dealt with .

Originally Posted by NadEFurY But what about deriving the public portion of the key from the private key? Is this also 'simply'(well, so to speak) because of mathematical peculiarities that it's possible? Or is it perhaps possible with 1 algorithm and yet not with another?

I don't know of any algorithm where it's not possible. Typically, the way to generate a keypair is by first generating a random private key, and then computing the corresponding public key. If you can't compute the public key, then it would be difficult to produce a keypair in the first place...

Originally Posted by NadEFurY But what about deriving the public portion of the key from the private key? Is this also 'simply'(well, so to speak) because of mathematical peculiarities that it's possible? Or is it perhaps possible with 1 algorithm and yet not with another?

It's what's called a trapdoor algorithm. Think of a medieval oubliette. You walk across a hidden spring, a trapdoor opens and you fall through it into an underground dungeon. But now the trapdoor is in the ceiling, not the floor, and there is no other exit. And of course there's no table or ladder for you to stand on to reach that trapdoor.

A trapdoor algorithm is easy in one direction (easy for a computer anyway) but impossibly difficult the other way around. I believe the private key to public key transition involves multiplying two huge prime numbers together. To get back from the public key to the private one, you would need to factorise the resultant humongous number into its constituent primes. Can't be done!

To be fair I sort of thought up an example in my own head after making the last post that how would it be theoretically possible for the keys to work together if they were both generated at random. Which makes sense.

You generate 1 randomly but then the other bit has to have some sort of association with the first to be able to interact with it. Otherwise 2 random keys both generated completely out of the blue, what would be the odds for them to be able to interactively operate with one another. Realistically nill. The other bit has to have some input from the first.

I suppose that is another great example to illustrate a situation that answers my own question.

Anyhoo, many thanks for everybody who chimed in, I really appreciate it. Gave me a quick answer to a somewhat complicated question to ask from google-fu.

Thank you all .

Originally Posted by ntubski It has to do with the specifics of the underlying math. For example, ECDSA public keys are twice the size of private keys.

Not always twice (mine only has a 25% difference in size) and it always depends on which one of the two keys you call the "private" one too.
On my system the (openssh generated) private key is always larger then the public one:

-rw------- 1 root root  672 2010-10-05 08:50:00 /etc/ssh/ssh_host_dsa_key
-rw-r--r-- 1 root root  603 2010-10-05 08:50:00 /etc/ssh/ssh_host_dsa_key.pub
-rw------- 1 root root  227 2014-03-27 23:30:00 /etc/ssh/ssh_host_ecdsa_key
-rw-r--r-- 1 root root  172 2014-03-27 23:30:00 /etc/ssh/ssh_host_ecdsa_key.pub
-rw------- 1 root root  399 2016-01-15 01:30:00 /etc/ssh/ssh_host_ed25519_key
-rw-r--r-- 1 root root   92 2016-01-15 01:30:00 /etc/ssh/ssh_host_ed25519_key.pub
-rw------- 1 root root 1679 2010-10-05 08:50:00 /etc/ssh/ssh_host_rsa_key
-rw-r--r-- 1 root root  395 2010-10-05 08:50:00 /etc/ssh/ssh_host_rsa_key.pub

and only the dsa keypair is about the same size.

Note also the year, all these key pairs got generated whenever openssh has been updated with a new encryption algorithm. For ed25519 the private key is more then 4 times the size of the public one. Probably openssh always calls the smallest one the public one because that should be the hardest one to break.

Originally Posted by ehartman Not always twice (mine only has a 25% difference in size)

I think the file includes common curve parameters, and additional formatting info. I was just counting the actual point value which is a pair of (x,y) co-ordinates, and private value which is a single scalar (so half size of the point).

-rw------- 1 root root 399 2016-01-15 01:30:00 /etc/ssh/ssh_host_ed25519_key -rw-r--r-- 1 root root 92 2016-01-15 01:30:00 /etc/ssh/ssh_host_ed25519_key.pub -rw------- 1 root root 1679 2010-10-05 08:50:00 /etc/ssh/ssh_host_rsa_key -rw-r--r-- 1 root root 395 2010-10-05 08:50:00 /etc/ssh/ssh_host_rsa_key.pub ...For ed25519 the private key is more then 4 times the size of the public one.

For ed25519, the private key is twice the size of the public one. The ssh files have extra info, see https://ed25519.cr.yp.to/

Small keys. Public keys consume only 32 bytes.

Originally Posted by ehartman ... and it always depends on which one of the two keys you call the "private" one too. On my system the (openssh generated) private key is always larger then the public one:... Probably openssh always calls the smallest one the public one because that should be the hardest one to break.

No, the choice of public vs private is not that arbitrary. I think the main reason the ssh private key files are so much bigger is because they contain a some extra parameters to speed up operations (e.g., for RSA, I guess they have all 5 CRT params, even though they could all be computed from just p, q, and e).