We cannot deny the importance of the asymmetric cryptograpfic schemes due the fact of rendering this page requires it. In the next paragraphs we are going to discuss about the “what”, “how” and “why” of assymmetric cryptographic schemes.
What the heck is asymmetric cryptography?
We can start with an interesting concept equalization between the public-key encryption and asymmetric mentioned in the introduction of the chapter 8 from Handbook of applied Cryptography: “This chapter considers various techniques for public-key encryption, also referred to as asymmetric encryption”. That means that there are two names for the same cryptography system. Now, let’s explain it:
Each entity \(A\) (Alice, Bob, etc) of the public-key/asymmetric encryption system has a public key \(e\) and a corresponding private key \(d\). Before going futher, we need to make the difference between private key and secret key crystal clear. A secret key is intended to be shared, a private key is not.
Now going back to the public-key encryption system, if we want a secure encryption system then the effort of computing the private key \(d\) given the public key \(e\) should be computationally infeasible. Trivially speaking, the public key supports an encryption transformation \(E_e\), meanwhile the private key supports the decryption transformation \(D_d\)
Let’s suppose that an entity \(B\) wishes to send the message \(m\) to \(A\), then \(B\) must obtain an authentic copy of \(A\)‘s public key \(e\). Next, the entity \(B\) applies the encryption transformation using \(e\) to obtain the ciphertext or mathematically speaking \(c = E_e (m)\). In order to decrypt \(c\), \(A\) will apply the decryption transformation to obtain the original message \(m = D_d (c)\)
In simplier terms, the asymmetric or public-key encryption system requires two key per entity which only one requieres to be visible to the other entities in order to cipher the message, it may be widely available. However, the public key’s authencity is the only requirement to guarantee that \(A\) is indeed the only party who knows the respective private key. However, the encryption system by itself cannot provide authentication for the public keys because the main objective of the system is to provide confidentiality.
We should mention that public-key encryption schemes are way slower than their symmetric-key counterparts. That’s why public-key encryption is used in practice for keys exchanging. Subsequently, those keys will be used to encrypt bulk data through symmetric algorithms.
Next, I present some public-key encryption schemes that are
Scheme Name | Computational problem |
RSA | integer factorization problem |
Elliptic-curve | algebraic structure of elliptic curves over finite fields |
Rabin | integer factorization problem square roots modulo composite n |
ElGamal | discrete logarithm problem |
generalized ElGamal | generalized discrete logarithm problem |
McEliece | linear code decoding problem |
Merkle-Hellman knapsack | subset sum problem |
Chor-Rivest knapsack | subset sum problem |
Goldwasser-Micali probabilistic | quadratic residuosity problem |
Blum-Goldwasser probabilistic | integer factorization problem Rabin problem |
References
Menezes, A. J., van Oorschot, P. C., & Vanstone, S. A. (1996). Handbook of applied cryptography. CRC Press. Retrieved from https://doc.lagout.org/network/3_Cryptography/CRC%20Press%20-%20Handbook%20of%20applied%20Cryptography.pdf