Public-key Cryptography is asymmetric meaning the key used for encryption cannot be used for decryption. There is a pair of keys, if the message is encrypted with one key, then the other is required for decryption.
How Public-key Cryptography works conceptually?
Let’s say Alice and Bob want to exchange messages in a secure way. To do it using Public key cryptography, each party needs to have a public key and a private key. Keys are just big numbers. The public key is shared openly, known to everyone, while the private key is kept a secret. The two keys are linked in the sense that message encrypted with one key can only be decrypted with the other, but it is almost impossible to work out the private key from the public key.
To send a message across to Bob, Alice will encrypt the message with his private key. Upon receiving the message Bob will decrypt it with Alice’s public key. This will confirm that the message has really come from Alice. It solves the authenticity problem and is also called Digital Signature. For efficiency purposes, a digital signature is created by encrypting the hash of the message with the private key rather than the whole text.
But as Alice’s public key is available to everyone, the communication is not confidential. Anyone can decrypt the message and read it. To make it confidential, Alice can first sign the message using Digital Signature with his private key and then encrypt it with Bob’s public key. This will ensure that the message can only be decrypted by Bob with his private key and then the digital signature can be verified with Alice’s public key. This assures both confidentiality and authenticity.
How it works technically or mathematically?
To demonstrate the working of Public Key Cryptography using RSA algorithm, I have created a page that generates the public and private keys using given prime numbers and encrypts/decrypts the message. It shows all the formulas and steps involved.
Why does it work?
I will address two separate questions here. Please go through the workings of RSA here before going further.
Why private key cannot be worked out from the public and decrypted message?
The public key is actually a pair of two numbers: E and N, the same goes for the private key: D and N. N is common between the two keys, while E and D are unique to the public and private keys respectively. As the formulas show, there is no way to figure out D from E directly. The only way is to factorize N into two prime numbers and then calculate D. Because the factorization of a very large number into its prime factors takes a very long time to compute, it is not possible to break the encryption in a reasonable amount of time.
Why do asymmetric keys to give desired results?
To understand why RSA gives us correct results, why asymmetric keys work, I will direct you to an excellent article here.
Links
Hi,
Thanks for your excellent demo of RSA.
There is a small mistake in the text. Private Key should be (D, N) and Public Key (E, N).
Regards,
–Ali