question about private and public keys
 

Hello

I'd like to know how public and private keys are working.
It would be the best if someone would explain it in example.

I downloaded kernel from www.kernel.org and there
was *.sign file next to it. Was it private key?.
I tried to verify kernel file in gpg and there was error:
no public key. I downloaded public key and imported it.
It worked. But how it works?. Why do I need public and
private key to verify file?.

I understand md5 verification:
someone generates md5 number (sequence of letters and numbers) on one computer and posts it on the web site with
file to be verified. Person who downloads file and number
can check if the number is correct.

But I can't fathom the idea of public and private keys.
Is this somehow similar?.

Cheers

Wikipedia explains this very well.

As the article explains ... keys come in pairs: a message encrypted by one can only be decrypted by the other, and vice-versa.

When you want to verify a signed file, you download the public key: the file's signature block is encrypted using the private key, so if it can be successfully decrypted by the public key, and it (the MD5 hash that it contains) matches the message, then it is considered "valid."

when you sign a message , it signs with your private key then the recipient verifies it with your public key

But when I verified kernel source I needed both public and private key. So I didn't need only public key but both.
So it seems that to verify file I need
both private and public key?.

Please look at www.kernel.org/signature.html

If you look at that web site, you will see only the public key. If you had access to the private key the packages were signed with, you would be able to sign packages as authentic - that is, coming from the official distribution. You can have your own private key, but you need someone else's public key to authenticate their signature. Read the Wikipedia article.

So what do I have to import?. And what are the .sign files that can
be found in a directory in which kernel sources are?.
I guess that I have to import public key ID 517D0F0E
and to do

gpg --verify linux-2.3.9.tar.gz.sign linux-2.3.9.tar.gz

I have to have .sign file which is (another guess) private key.

So I need both public and private key, need I?.

You import public keys, to add them to your keyring. A signed file (the extension doesn't mean anything), contains an encrypted hash of the data. You need a public key to decrypt and validate the data against the hash. Doing so authenticates the data - that it was signed by the person with the matching private key, and that it was not tampered with (no data was changed).

You can never have someone elses private key. Ever. That's why it's called a private key. The private key must be guarded like the key to a safe deposit box. Having the private key lets anyone prove they are the owner associated with a public key.

You can have your own private key. You would use your key to sign files and to encrypt files for others.

But in case of this kernel example I don't decrypt data. I validate it only. So I import public key, yes?. OK I know what is public
key in this case. So this .sign file is not private key?.
So how is it called?. Is this signature?.

Let's return to MD5 authentication, there is one file to be downloaded and one which contains sequence of letters and numbers.
But such file with sequence is only one!!!.
I compare what md5 program prints out (refering to the file downloaded) and I know if the file is corrupted or not.

In case of "kernel" authentication there are two files. Why?.

Has private and public key the same format?.

Yes, you are decrypting the hash to validate the signed file.

Yes, you import public keys for decrypting and validation of signed data.

No, it is not a private key. It is a signed file (the file+the signature) or the signature of a file (just the signature associated with a separate file).

The kernel developers have chosen to use a separate data file and signature:

linux-2.6.16.2.tar.bz2 - the linux kernel (the data file)

linux-2.6.16.2.tar.bz2.sign - signature (for the data file,linux-2.6.16.2.tar.bz2)

Validating the file with the signature means that the signature file will be decrypted using the kernel.org public key. This will yield a hash. The hash will be compared to the calculated value for the the data file (the kernel); if they match, the file has been validated. If they do not match, then either:

1. The data or signature file have been changed after the signature was made,

2. The private key used to sign the file is not the one associated with the public key used to validate it.

Regarding the format of the public/private keys, they can both be in the same format, but usually are not.

The private key, since it is never sent to anyone, is usually stored in binary.

The public key is also stored in a binary format, but is also exported into an ASCII format suitable for transfer via email and web browser. It is this exported ASCII format that you import, returning it to its binary stored format.

So there is connection between private and public key?.
So you have generate your public and private key on your box,
you send public key to recipient and then what?. He can decrypt
data with your public key?. Either I got it wrong or it doesn't make
sense. Everyone who can get public key can decrypt such file?.
(I thing I've got it wrong...)

Yes, you have it wrong. Again, I'd like to stress that this is explained more clearly in the Wikipedia article mentioned above.

Public and private keys are related mathematically; they constitute a key-pair.

When encrypting a file for someone, you use your private key and their public key. The receipient will then use their private key and your public key. As a result, only the intended recipient (the person with the private key matching the public key you used) can decode the file. In addition, since the senders public key is used, it validates that the file actually originated with that individual.

So, for example, I create public and private key, send public key
to another person, this person encrypts some file with his
private key, using my public key, and then sends encrypted file to me and I can
decrypt the file with my private key?. So public key must
contain information about private key?.

I can encrypt a message using your public key, and nobody other than the person who has the matching private key can decrypt it. so when you receive the decrypted message and apply your private key to decrypt it, the only way it will properly decrypt is if it was encrypted with your public key

You can decrypt the file with your private key and the other person's public key.

The public key contains no information about the private key, and no amount of processing can derive the private key from the public key (or the public key from the private key). The key pair is created by an algorithm that causes the two to be halves of a one-way symetrical operation.

For the details on the algorithm, see Wikipedia's RSA and DSA pages. However, unless your degree is in mathematics, you will have to take it as an act of faith that these algorithms have been subjected to public scrutiny, and have been found secure, for now.

Let's try another way. In Wikipedia is this postal example:
Alice sends message to Bob. She asks for padlock (public key?).
So Bob creates padlock (public key) and key (private key), right?.
He sends his public key to Alice. So now Alice has only Bob's public key?. So she encrypts the message with this public key and I wonder... so what exactly she does?. Is this some kind of "latch"
padlock?. Does this mean that she can't decrypt her message(open
the padlock)?. She can only send back the message to Bob?.
And only Bob can open it?.

That's correct. Once encrypted for someone else (your private key, their public key), even the originator cannot decrypt the file.

So I need only someone's public key to encrypt message and
this person must have this public key and his private key to decrypt it?.

But what about this kernel source authentication?.
I have public key and hashed signature and it seems that I
decrypt this signature with public key. I don't need and have private key, have I?.

That's why I asked question about whether public and private key
of one person are connected. I think it is like in this postal example public key is a padlock and private key is a key to this padlock, so can't someone cut the key to the padlock having this
padlock?. I think it's possible.

Again, you need the other person's public key, and your private key to encrypt. The other person needs your public key and their private key to decrypt.

That's a signature, not an encrypted file. The algorithms and process is different.

No, it is not possible. If you can "solve" the problem without using hundreds of thousands of CPUs in a reasonable time (decades of processing), you will be forever famous. :)

So we exchange public keys?. I send my public key to someone and
someone encrypts message with it and sends the message back with his public key so I can decrypt it?.

Well, it doesn't fit into this postal analogy. Because how can I
lock padlock which is not mine with my key?.

Well, so encrypting message and signing message are two different things?.

Could you explain what I have to do to sign message (theory - not how it's done in particular program). And what the other person
has to do to verify signature (well, this part I guess I know from
kernel source example). I use public key and decrypt signature with it and this signature is compared with sequence of letters and numbers derived from signed file. The sequence is created on my computer locally, as it is done in md5 verification. Am I right?.

At this point, we are not covering new ground, but simply reiterating the same points over and over. I understand that you find the material confusing, but asking the same questions and getting the same answers will not enlighten you.

I suggest that you set up two login accounts on your Linux system. Generate a key pair for each account. Exchange files, sign files, and orbserve how the software operates. Attempt to defeat the process by any means you see fit. You have the environment to empirically validate the process and understand the operation yourself.

Document what you find, and present it in a way that makes sense to you, so that others may benefit.

Yes, I think this is the best way. Thank you for patience.

I created two accounts as you suggested. I used KGpg GUI
And here are the results:
1. Receiver produces pair of keys
2. Sender produces pair of keys
3. Receiver sends his public key to sender
4. Sender imports receiver's public key
5. Sender signs receiver's public key with sender's private key (must enter password referring to sender's pair of keys)
6. Sender encrypts file with receiver's public key (signed with
sender's private key)
7. Sender sends encrypted message
8. Receiver decrypts file with his pair of keys (must enter password
for his pair of keys).

I have one question: why is point 5 needed?.

This is really like this "latch" padlock concept.

Step 5 is not needed. By signing someone else's public key, you are assigning a level of trust to that key. It's somewhat like like using a certificate authority on the web, but with more shades of gray:

unknown

Nothing is known about the owner's judgment in key signing. Keys on your public keyring that you do not own initially have this trust level.

none

The owner is known to improperly sign other keys.

marginal

The owner understands the implications of key signing and properly validates keys before signing them.

full

The owner has an excellent understanding of key signing, and his signature on a key would be as good as your own.

More details here.

Well, is it not needed?. But without signing someone's public key with my private key I can't encrypt file. There is not even
such key to choose from in menu of KGpg. Level of trust is set to
0. When I sign public key level is 100%. And only then I can
encrypt file. Does KGpg - GUI give only 0% and 100% level of security available?. Do I have to use command-line gpg to
set other levels?.