TABLE OF CONTENTS We now turn our attention to asymmetric cryptosystems. We review basic concepts of public key encryption, digital signatures, the necessary mathematical background, and the adversarial model.
Confidentiality of transmitted data cannot be guaranteed by the sole use of symmetric schemes. Users must share a common key for the utilization of a symmetric key encryption scheme. If the users cannot securely carry out their key establishment, an eavesdropper may illegally obtain the key, hence, revealing the transmitted message. One of the most practical solutions to this problem is to use public key encryption in which a sender encrypts a message (or a session key) by using only the receiver's public information.
The idea of public-key encryption (using asymmetric algorithms) was proposed by Diffie and Hellman in their pioneering paper in 1976, where the keys for encryption and decryption were called public and private key, respectively. Their revolutionary idea was to enable secure message exchange between sender and receiver, without ever having to meet in advance to agree on a common secret key. Public key encryption can be (roughly) modeled as follows:
In a situation where Bob intends to send a message to Alice, she first generates a public key which is published under her name in a public directory accessible for everyone to read and a private-key, which is known only to her. To send a secret message to Alice, Bob looks up Alice's public key from the public directory, and then...
