Tuesday, November 15, 2016

How asymmetric signature works

In our daily life, when we say we sign a document, it means we put a signature on a document, and the signature is a drawing which the signer is the only one in the world who can re-create the same signature.  Same idea is applied in the digital world.  When we generate a digital signature, it means only the signer can generate this signature.  By verifying the singature, one can verify that the document is truly generated by the originator(not modified, not a fake from other source).

I'm trying to put this in simple English.  If you're looking for detail scientific equations, you can easily search elsewhere on the web. (https://en.wikipedia.org/wiki/Digital_signature)

Let me present a scenario.  I'm a FBI head and I'm sending a message to my FBI agent.  Say the message has nothing to encrypt, since it's already a code like "How's Billy?" and it means take action.  Say everybody can send this message to my FBI agent, but how can he know it's from me?  So we use asymmetric cryptograph(aka public key algorithm) for the digital signature.  Here is how it works:

First, I'll have to generate a pair of keys - public and private key. They're not the same key that's why we call it asymmetric cryptography.  If we're using the same key for encryption/decryption, or signature/verification, then it's called symmetric cryptography.  I will keep my private key private, as the definition of "private key".   If I lost my private key, my FBI agent dies.  So keeping private key private is very very VERY important.   I'll have to share my public key to my FBI agent.  How to share and make sure my FBI agent has my public key is another story.   The public key can be public, there is no secret in it, everybody can has it.  The only concern is that the key is legitimate. We don't want our FBI agent to has a wrong key.

Once the above step is setle, then I calculate a hash from my message; we usually call the hash result  a "digest".  It's called digest because a hash is taking any number of bits but always yields the same length of output, as if it doesn't matter how much we eat we always have a digest of same shxt.  Let's pick sha256 for this hash example, the has of the string "How's Billy?" is: b9f36ce69b818c46b23feea7f0b437c9f45bbf009cab333a4cc129a69fb7854a , then I use my private key to encrypt the above hash digest, and it's called a signature.  I'll send my message along with my signature.  My FBI agent receive the message and my signature.  He'll then first do the same sha256 has of my message "How's Billy?".  It should be b9f36ce69b818c46b23feea7f0b437c9f45bbf009cab333a4cc129a69fb7854a .
Then my FBI agent use his public key to decrypt(verify) the signature.  If the encrypted "signature" is the same as the has that he just calculated, then he verified that the message is truely from me.  Otherwise, the message must be from someone else because someone couldn't generate the signature properly(he couldn't generate the same "signature" without my private key, and guessing or hacking my private key is mathematically impractical/impossible).

Same scheme is used for software download.  Softwares are often mirrored or stored in different repositories.  Some can be corrupted or has virus(malware).   The above signature scheme is widely used in open source world to ensure authenticity of the software and also verify integrity(due to the nature of hash algorithm is integrity checking)




No comments: