In the previous blog we have seen what is encryption and what are the various types of encryption and also have defined what RSA encryption is. In this blog let us understand how exactly RSA encryption works?
What is RSA encryption?
RSA(Rivest Shamir Adleman) is a public key cryptosystem used to secure the data transmission.
In a public key cryptosystem the encryption key is public whereas the decrypted key is distinct.
Let us try taking a real time example and understand RSA encryption much more better.
So let us take an example of a company Pascal where 5 people are working on a project where they are trying to make the bank system much more secure so that it will be less prone to hackers.
Now on the other hand one guy from the same company is manipulated with a money offer he receives from their opponent company Cascade.
The first version was completed and ready to be submitted to a company which would fund them for their project but the guy from Pascal company leaks their first version to the opponent company Cascade and gets paid for that.
On the other hand the team which made the first version of the software were not able to figure out why was the version made public.
Then they started working on the second version and this time they decided to make it as confidential as possible. So the second version was ready and was submitted to the sponsor then after looking into the software he was impressed and was ready to fund for the project.
Why was the guy from Pascal not able to leak the second version?
This time the people who were working on the project used RSA encryption let us see how did they integrated it with their project.
They first generated two prime numbers of 2048 bits multiplied them and stored it in a variable n.
Then they took the totient of the prime numbers.
Wait what is totient ?
Totient or totient function is nothing but the multiplicative function where the two prime numbers which we pick are subtracted by one and are multiplied the form looks like this:
φ(n) = (p-1)*(q-1)
The prime numbers which we pick are relative primes or co-primes meaning that there are no factors except 1 or n.
Now after computing the totient they pick an e from the interval [1,m] such that the gcd of e,m is 1 that is gcd(e,m) = 1.
What is the variable e?
e is the public exponent in RSA which satisfies the coprimality, efficiency and security.
Now what is coprimality?
In RSA encryption, it is imperative to choose a public key example e that’s coprime with φ(n) (or m).
This coprimality necessity is particular to the open type, whereas the prime numbers p and q utilized in RSA don’t ought to be coprime with each other.
By choosing a coprime open example, the RSA encryption plot accomplishes the vital conditions for secure private key calculation and generally cryptographic quality.
m is nothing but the totient function φ(n).
Now after computing the totient function and picking the e from interval [1,m] they get the public key which is gcd(n,e).
Now this public key is visible to everyone so the guy who want to leak the details have passed this information the fact he did not know is that there was another key which is the private key where they hid the software information.
Now after generating the public key what they do is take the multiplicative inverse of the e(mod m).
now here d is the multiplicative inverse of e(mod m).
what is d?
In the previous scenario we have used an alphabet e which is the public exponent now in the same way d is the private exponent used to decrypt the information.
The math:
e.d = 1 (mod m)
gcd(e,m) = 1 (where e and m are the co-primes)
1 = xe+ym (using the extended euclid algorithm)
xe – 1 = -ym
m|xe -1
xe ≡ 1(mod m) (here x is nothing but our d which is used to decrypt the information)
Now in this way we are going to generate the private key(n,d).
Now it is the time for the company to decrypt the message and explore the software so how is it done?
The software which they have sent the company is stored in some variable say S so the software is decrypted in this way:
The Math:
(S^e)^d = S^e.d ≡ S(mod n)
e.d ≡ 1(mod m)
m|e.d -1
e.d – 1 = m.k
e.d = 1 + mk => φ(n).
(S^e)^d = (S^1+φ(n) k)
(S^e.d) % n
S^(1+φ(n) k ) ≡ S(mod m) . (S^φ(n).(mod n)^k) ≡ S(mod n)
Let us put it in words the math is confusing:
The expression (S^e)^d in RSA encryption simplifies to just S. In other words, encrypting the message S with the public key exponent e and then decrypting it with the private key exponent d will result in the original message.
This property is a fundamental characteristic of the RSA encryption algorithm and ensures that the encryption and decryption processes are inverse operations of each other.
It allows for secure communication, as only the recipient with the correct private key can successfully decrypt the message and retrieve the original content.
Now let us understand what stopped the guy from leaking the private information.
The fact is that he did not know what are the prime numbers which are chosen to encrypt the private message and also the main part is that he cannot compute the totient function so this is the wall which will stop him from leaking the original information to the Cascade company.