Walk Through of RSA Public-key Encryption for Beginners - Part I : An Introduction


Let us assume the class scenario: Alice wants to send a secret message x to Bob. Eve is the eavesdropper who wants to know x. To prevent Eve from getting x, Alice applies an encryption function E, so instead of sending x, she send E(x) to Bob. Upon receiving E(x), Bob applies a decryption function D to E(x), and get the message x where D(E(x))=x.

How do we find such functions E and D such that Eve is not able to know the message x by seeing E(x) and not knowing D? An easy solution would be for Alice to arrange a private meeting with Bob beforehand. They can figure out an encryption and decryption function only know to them, and encrypt and decrypt the secret message x hence.  This is called a private-key protocol become Alice and bob holds a private key.

But what if such a private meeting is not available? It almost seems impossible because in this case,  what is the difference between Bob and Eve? When Alice send just x, they can both see them. When Alice send E(x), they both do not know D and cannot decrypt it. 

 This problem can be solved with Public Key Cryptography. In this scenario, Bob would like to have a public key available to the whole world and a private key only to himself. When people send him a message, they encrypt it with the public key, to which only Bob can decrypt with his private key. 

In part II we will dive into the mathematical details of finding the right public and private keys. 

« Walk through of RSA public-key encryption for beginners - Part III:Bijection functions Walk through of RSA public-key encryption for beginners - Part IV: The RSA Function »