In a public-key cryptosystem, the sender and receiver have their own public and private key. The sender uses the receivers public key to encrypt the message. The receiver can then decrypt the message by using his own private key. What’s stopping an eavesdropper from decrypting the ciphertext with the public key is the fact that the decryption function is hard to evaluate by using the public key. Decrypting the ciphertext with the private key is an easy task.

In the worst case scenario where Bob is sending something to Alice and Eve is an eavesdropper, Eve just like Alice might have access to the encryption function as well as he encrypted message, but since Eve doesn’t have the decryption key she has to go through very hard calculations. However there are some possible security issues with the method. Eve could for example encrypt a message with the public key and then send a message to Bob pretending to be Alice.

To make sure that a message comes from Alice the message can be signed. In order to sign it, Alice can first decrypt the plaintext with her own private key. Then Alice sign it and encrypt everything with Bob’s public key. Bob can decrypt the message with his private key and then he can use Alice’s public key to “encrypt” the rest of the message to get plaintext.

Author

2020-06-15

An introduction to the ElGamal cryptosystem

Introduction to the knapsack problem

Introduction to the Merkle-Hellman Knapsack Cipher