Hashing and Public Key Cryptography for Beginners

This article aims to educate beginners about hashing and public key cryptography. If you are involved in blockchain technology, knowledge of public key cryptography is crucial. It becomes even more significant once the proposed Web Authentication API becomes widespread.

Before we delve into the main topic, the article starts with an overview of “functions” to warm you up.

Functions

1. A function (in math or computer science) is like a machine. It takes an input and produces an output.
2. An input is generally part of a whole. For example, the part can be a few numbers, whereas the whole in this case would be the entire integer set.
3. The whole is also called the “domain”. Some common examples of domains are : integers, UTF-8 character set, all prime numbers.
4. If you feed N inputs to a function and if it produces N outputs, then the function is called a map function. Example : square(1,2,3,4) = (1,4,9,16)
5. If you feed N inputs to a function and if it produces exactly 1 output, then the function is called a reduce function. Example : sum(1,2,3,4) = 10

Hashing

1. Hashing is basically the act of using a hash function in order to produce a hash output. Examples of popular hash functions are SHA256, MD5, Bcyrpt, RIPEMD
2. A hash function takes an input of any size (eg : your email password, the full text of the Illiad, or a blu-ray video of Inception)
3. The output of a hash function is of fixed size ( say, a 64-character text). The output is also called a digest.
4. Real example: sha256sum(“Meet me at 180 10th Ave. New York, NY 10011”) = 8D4364AFA2A79D46DDDA74361F9DF1EE939D84DC81E31FC53FAB221CA54E5E31
5. In hashing, given an input, it is easy to compute the output. But it is practically impossible to reverse engineer a hash output and derive the input. Hence a hash function is also called a one-way function.
6. Corollary : you cannot use hashing for encryption and decryption (as decryption is impossible due to the one-way nature). Technically, encryption/decryption functions are map functions(N to N). A hash function is a reduce function (N to 1). So fundamentally, cryptography and hashing are different beasts, though they may be combined for certain applications(such as public key cryptography).
7. A hash output is useful to represent an input. This representation is called a fingerprint. This is useful if you want to make sure your data is not tampered or corrupted when it travels in a network. The hash of “sent data” should always equal the hash of “received data”. Basically, comparison of data is the most common use of hashing.
8. In theory, it is possible that 2 different inputs can produce the same hash output. This is called collision. But in practice, a good hash function makes it real hard (time consuming) to find collisions.

Public Key Cryptography

1. When you receive a package from Amazon, you want to make sure that : a) Indeed Amazon has sent the package and not some bio-terrorist (signing) b) While in transit, nobody else knows what’s in the package (confidentiality) c) The package is not tampered while in transit (tamper-proofing)
2. A network transaction involves : a sender, the network pipe and a receiver. A network transaction happens when a unit of data is moved at a particular point of time. Securing a transaction is of high importance. By securing, we mean that confidentiality and tamper-proofing is taken care of.
3. Public key cryptography solves the problem of signing, confidentiality and tamper-proofing of network transactions. All in one neat package.
4. Confidentiality is achieved by garbling (mixing up) the data in motion.
5. A key is a number or a function that can be used to garble a piece of data. This is called encryption. A key can be used to reconstruct the original data from the garbled data. This is called decryption.
6. If you use the same key for both encryption and decryption, then it is called symmetric cryptography. These key is private and is held only by the sender and the receiver.
7. With symmetric keys, the data can be encrypted. But how would the sender transfer the key to the receiver? There is no practical/scalable way to do this on the network. Thus, key-sharing is a fundamental drawback of symmetric key encryption and it is not used widely.
8. Asymmetric cryptography was established to fix the key-sharing problem in cryptography. Here, you use one key for encryption and a different key for decryption.
9. Public key cryptography is basically asymmetric encryption with some additional steps.
10. In public key cryptography, there are 5 elements : the actual data, sender’s public key, sender’s private key, receiver’s public key and receiver’s private key.
11. A public key is announced and known to the world. A private key is stored in the owner’s mind or in a physical/digital safety locker. Private key is otherwise called a secret key.
12. At a given point, a sender can make use of 3 keys : sender’s private key, sender’s public key and the receiver’s public key. Similarly, a receiver can make use of receiver’s private key, receiver’s public key, and the sender’s public key. Needless to say, one party can never know another party’s private key.
13. The combination of public & private keys is called a key-pair. This pair can be generated on your computer’s command line program. Some prime-number mathematics goes behind the key-pair generation(the details are beyond the scope of this write-up). In a nutshell, it is real hard (time consuming) to know someone’s private key using their public key (through guess work and other means)
14. It does not matter the order in which you use the keys. You can encrypt a piece of data with a public key, but the decryption can be done only with its corresponding private key. The reverse is also true. You can encrypt data with your private key. But it can be decrypted only with your public key.
15. A sender would always start with the receiver’s public key for encryption. The receiver would use its own (receiver) private key for decryption. This fulfills the goal of confidentiality (data scrambling & reconstruction). So confidentiality is achieved by using the receiver’s key-pair.
16. But the receiver still does not know who sent the data. It could have been sent by a hacker. So the sender needs to let the receiver know that the data is indeed sent by the sender. This process is called signing. Signing is done by attaching a small piece of additional data called the signature. (Note that a signature without data is useless). The next few steps might overwhelm a bit(as the topic itself cannot be oversimplified). Please feel free to read with a paper and pencil.
17. A signature is created by using the sender’s key-pair. In this process, the sender first encrypts the data with sender’s private key. Lets call the result sender-privkey-encrypted-data (this is the signature). Now sender combines the signature and the data. Let’s call this “data + sender-privkey-encrypted-data”.
18. The sender will again encrypt the “data + sender-privkey-encrypted-data” with the receiver’s public key. Lets call this result receiver-pubkey-encrypted-data. This “wrapped and encrypted” data is sent over the network (note that message in transit is twice the intended size, and this problem is “fixed” later at point 22). No intruder can decipher this message as only the receiver’s private key can decrypt receiver-pubkey-encrypted-data.
19. The receiver would now take the receiver-pubkey-encrypted-data and decrypt it (for the first time) with the receiver’s private key. The result would be “data + sender-privkey-encrypted-data”. Receiver alone can see the “data”, hence confidentiality is achieved.
20. The receiver would now decrypt (for the second time) only the “sender-key-encrypted-data” using the sender’s public key. Let’s call this “data2”.
21. If the “data2” matches with “data”, then receiver is sure that the message was indeed sent by the sender (because only sender’s private key could have encrypted “data” to create “data2”).
22. Data matching also ensures that message is not corrupted. Hence, tamper-proofing is also taken care of.
23. Overall, a double-encryption process is used. The sender needs to sign (with sender’s private key ) and sender needs to encrypt (with receiver’s public key).
24. Note that at point 16 we mentioned that the message in transit is twice the size of the intended message. This is because of the signature “sender-privkey-encrypted-data”. The size of the signature can be compressed by hashing the actual data and then encrypting only the hash. Hence, instead of encrypting a huge “data + sender-privkey-encrypted-data”, we can encrypt only the “data + sender-privkey-encrypted-hash”.
25. This concludes public key cryptography.