Symmetric & Asymmetric encryption
When it comes to encryption, most people may feel boring and complex. Inevitably, in most cases, I admit it is not as fascinating as 3D animations, neither comparable with AI computations, etc. However, it at least satisfies a basic requirement that we can whisper to someone.
Imaging a private channel between you and your friends that no outsider can eavesdrop, the encryption suddenly becomes more important. Furthermore, the encryption indeed plays a pretty vital role while the private channel is established to protect your credit card numbers as well as some sensitive private information from being tampered or sniffed. In this story, some essential concept of encryption will be chatted about. There will be not too much complex technical terms, symbols or professional computations. This story may be regarded as a history where the encryption comes from and a rough image what does it look like nowadays.
Symmetric encryption — shift and substitution
Again, when it comes to encryption, an intuitive way to make strings “unrecognizable” is to shift several digits, such as from “cat” to “ecv”. The sender make shift of the origin message and delivers it via an insecure public channel; if one receiver knows the secret 2 (or so called the key), he can roll back the original message. Definitely, it is not a strong encryption yet, there are only few possible keys if only shift is taken into consideration. Following, the substitution is also adopted. Assume a mapping table is set to map “c” into “Z”, “a” into “1” and “t” into “h”. The ciphertext “Z1h” comes out after computing encrypt(key, “cat”) where the key definitely indicates to the mapping table. If a receiver know the table, the decryption “cat” = decrypt(key, “Z1h”) is an inverse mapping using the same mapping table. The combination of two elements, shift and substitution, conceptually build up the symmetric encryption system where the term “symmetric” denotes that the encryption and decryption relies on the same key.
From the Caesar Cipher thousands of years ago to present, the symmetric encryption was kept progressing. A well-known cryptography-related movie, the imitation game, described how Alan Tuning broke the German cipher machine, Enigma, to help terminate the second-world war earlier; and Enigma is also an implementation of symmetric encryption. Until today, the modern symmetric encryption algorithms like advanced encryption standard (AES), triple data encryption standard (3-DES) and pretty good privacy (PGP) still work both robustly and efficiently. Whereas, some issues also occur along with the usage of symmetric encryption schemes.
Key distribution issues
To make the decryption success, the receiver has to learn the corresponding key of a ciphertext. How could the key be delivered in an insecure channel becomes a tough problem. The condition is depicted in above picture: the key should be transferred in a secure channel; however, to construct a secure channel, a key is necessary. It fails into a deadlock that each side is waiting for the other side. In case that two parties of the data transfer are not geographically close, the key distribution is quite tough.
Key storage issues
Another potencial problem of symmetric encryptions is the key storage. For each pair of sender and receiver, there should be one key for secure transfer. If there are n parties, the total key requirements is basically n(n-1)/2, that’s horrible. For example, there are totally 4950 keys among a group of 100 members. Shown in above picture as well, the key storage needs O(n²) space consumptions.
Asymmetric encryption — a pair of keys
There is a story that cryptographers occationaly found a “pair” idea from some mathmatical textbook. Then, the asymmetric encryption was born while the pair concept was adopted into cryptography. In brief, a pair of keys (say key a and key b) be generated in the key generation phase; then, the operation between the plaintext and key a can only be ”undone” by key b, and vise versa. Following, the key a is published as a public key, and key b is kept secret as a secret key. It is intuitive to build up an asymmetric encryption which the encryption could be constructed by the public key and the decryption is implemented by the related secret key. Illustrated in the picture below, it is how asymmetric encryption works.
Let (sk, pk) be the key pair of Alice, which stands for the secret key and the public key respectively, generated by algorithm key-generation. Bob encrypts message m into a ciphertext c=encrypt(pk, m) using Alice’s public key pk; and Alice obtains m=decrypt(sk, c) through decryption with her secret key sk after receiving. Due to the essentially difference from symmetric encryption, the asymmetric encryption is also called public key encryption.
Application — RSA encryption
As the first asymmetric encryption, RSA is a famous algorithm that perfectly illustartes the pair idea. Now, let’s quickly go through a simplified version of RSA to help understand the asymmetric encryption. All messages of RSA encryption is encoded as a number m between 2 and n-1, which are represented as m mod n. Operator mod denotes modular, such as 8 mod 3 = 2. Then, assume the public key is pk and the secret key is sk, it is easy to implement the encryption encrypt(pk, m) by computing c=m^pk mod n; and the related decryption decrypt(sk, c) is computed by m=c^sk mod n. Two keys sk and pk will be slashed while they’re puting together in the modular operation. In case that parameters sk and n are big enough, the RSA encryption will be computationally secure.
Hope that above scenario helps understand the architecture of asymmetric encryption. Due to that fact that the operation between the plaintext and the public key can only be “undone” by the secret key, it is designed that the public key could be shared to the world to make everybody able to encrypt; but only the secret key owner has the capability of decryption. After the architecture, let’s move forward to realize how does asymmetric encryptions deal with the problems that bother symmetric encryptions?
Key distribution issues
It is straightforward that the asymmetric encryptions easily solve the key distribution issues by hidding credentials to the secret key. Everyone knows the public key can encrypt, but only the secret key owner can decrypt. Obviously, no key distribution issue exist over asymmetric encryption.
Key storage issues
In the asymmetric case, everyone only has to remember their own part: the secret key, the public key, and a certificate signed by a trusted third party. The certificate is a proof that someone owns the public key provided by a trusted third party, which will be introduced soon.
Remark
It is emphasised that I’m not saying the asymmetric encryption is greater than the symmetric encryptions and the former should replace the latter. Both of them have some irreplaceable advantages. In general, the symmetric encryptions are much higher efficient and robust because it bases on bit-wise based operations; and the asymmetric encryptions do not suffer from the key distribution and storages issues. Besides, some special functionality like homomorphism over asymmetric encryptions make it more creative in some private-preserving services.
Digital signature
Digital signature is an interesting well-known appplication of the asymmetric key setting. In the same scenario that the public key is published and the secret key is kept secretly. Then,the secret key owner is able to convince others that a document is “encrypted by the secret key”. Following, we also take RSA for example to demonstrate how a digital signature work in a simplified manner.
Application — RSA signature
Let h() be a collision-resistant hash function, m stands for some message and n denotes the modular number, the RSA signature is computed as sig=h(m)^sk mod n; and the verification is testing the equality between h(m) and sig^pk mod n. Two keys sk and pk will be slashed while they’re puting together in the modular operation. This is an intuitive implementation of digital signature based on the asymmetric key setting.
Here we take term “sign” instead of “encrypt” for clear expression of sig=sign(sk, h(m)). Since only the secret key can make the signature as well as the operation between plaintext and the secret key can be “undone” by the related public key, everyone knowing the public key and message is able to verify the identity of the signer through algorithm verify(pk, h(m), sig). More detail about digital signature could be found in another story.
