Public-Key Cryptography

Asymmetric (public-key) cryptography

Public-key cryptography works quite differently than symmetric cryptography since there is not just one key that Bob and Alice share, but rather a pair of complementary keys that are mathematically related: a private key $k_{\text {priv }}$ that’s only known to its owner (Alice) and a public key $k_{\text {pub }}$, which she makes publicly available to everyone in order to serve as identification of her account. Thus, any person can encrypt and send a message against Alice’s public key, whereas only Alice is able to decrypt the encrypted ciphertext because she is the only one who is in possession of the matching private key $k_{\text {priv }}$.

However, all actual public-key cryptography systems depend heavily on cryptographic algorithms where no efficient solution is known. As we’ll see, this kind of algorithm relies on so-called one-way functions. This means that the security of a cryptosystem is based on the belief that specific number-theoretic functions are very hard to invert, whereas, we should notice that there’s no mathematical proof that these problems are intractablethis means that there’s no proof that these problems aren’t solvable in polynomial time. However, we can assume that the computation of these problems is infeasible as long as no one can propose an algorithm that has polynomial time.. In practice, there are actually only three major families of public-key schemes that are commonly used (Darrel Hankerson et al. (2006)Darrel Hankerson, Alfred J. Menezes, and Scott Vanstone. Guide to Elliptic Curve Cryptography. Springer Professional Computing. New York, 2006. Springer. and Christoph Paar et al. (2009)Christoph Paar and Jan Pelzl. Understanding Cryptography: A Textbook for Students and Practitioners. Springer Berlin Heidelberg, 2009.):

• Integer factorization schemes, which base themselves on the hardness of factorization of large integers, such as the RSA public-key encryption and signature scheme ( Ronald L. Rivest et al. (1978)Ronald L. Rivest, Adi Shamir, and Leonard Adleman. A method for obtaining digital signatures and public-key cryptosystems. Commun. ACM, 21(2): 120-126, February 1978.).
• Discrete logarithm schemes, which rely on the difficulty of the discrete logarithm problem (DLP), such as the ElGamal public-key encryption and signature scheme or the Digital Signature Algorithm (DSA), which is essentially an extension of the ElGamal scheme.
• Elliptic curve schemes, which rely on the hardness of the elliptic curve discrete logarithm problem (ECDLP), such as the Elliptic Curve Digital Signature Algorithm (ECDSA) scheme.