With a math background we can now describe
some of the most widely used public key algorithms.
The first is RSA.
Named after its inventors.
R backup RSA is
the most widely used public key algorithm and one of the very first.
RSA supports both public key encryption and digital signature.
The security strength of RSA is based on the hypothesis that,
factoring a very large number into two primes is a very hard problem.
This is, given a large number
it is computationally very hard to factor it into two primes.
RSA can support variable key lengths.
In practice, most people use a key length of 1,024 bits,
or 2,048 bits, or even 4,096 bits.
The plaintext length can also be variable.
In RSA, every data is treated as an integer
because we can interpret any data with bits of one and zero as an integer.
And the requirement here is that the plaintext input has to be smaller in
integer value than the key.
The size of ciphertext is the same as the key length.
This summarizes the RSA algorithm.
The first step is key generation.
First we select two prime numbers, p and q.
Say each of them are at least 512 bits long.
And then we compute p times q.
The result's n.
And while we have p and q we also compute totient n.
Which is p minus one times q minus one because both p and q are prime numbers.
Then we select an integer e that is relatively prime to totient n.
After we have selected e,
we find the multiplicative inverse of e marked totient n.
Having computed n, e and d, now we can forget about p and
q and forget about totient n.
The public key is e and n.
The private key, which we have to keep to ourself and secure it, is d and n.
Now for encryption, suppose Alice has published her public key.
And Bob wishes to send a message, M, to Alice.
And he wants only Alice to be able to read M.
So Bob obtains Alice's public key and to encrypt message M,
Bob computes M raised to the power of e (mod n).
For decryption on receipt of this ciphertext, C,
Alice will use her own private key, D, and
compute C raised to the power of d (mod n).
And this would result in the original plaintext M.
The property of RSA guarantees that only Alice Can decrypt this
message because only she has the private key
that's paired with the public key that was used to encrypt the message.
Again, every user can publish his or her own public key and
keep his or her own private key securely to himself or herself.
To encrypt message to a user say, Alice, Bob would obtain Alice's public key and
compute the ciphertext by raising the plaintext to the power of e mod n.
To decrypt, Alice would use her own private key
to raise the ciphertext to the power of d and then mod n.
What about creating digital signature?
Alice will use her own private key
to raise the message m to a power of d mod n.
To verify,
Bob would get Alice's public key, raise the signature to a power of e and mod n,
and this will produce the original message m and verify the signature.
Again here the property of RSA guarantees that
Bob will know that the signature was created by Alice,
because only she has the private key that is paired with the public key
that Bob was able to use to verify the signature.