WhatsApp introduced End to End Encryption, and online payment has grown to a massive extent. Data are encrypted to protect your credit cards and personal texts. So I thought of writing how my 3rd semester Mathematics helps in protecting all the data.
What is Encryption?
In simple words, Encryption makes your data unreadable before sending it over the Internet. And the data is decrypted at the other end.
Well, How do Encryption works?
In old style of encryption, both the sender and receiver choose an encryption key. In this method, both encryption and decryption can be done with the same key. For Example, if the key is 3, Let Siva wants to send a message "Hello" to Jeni. A simple Algorithm is to move all the characters 3 positions as the key is 3. H is encrypted to K (third letter from H). Likewise "Hello" becomes "Khoor". So now Siva can send "Khoor" to Jeni and since Jeni knows the key, she can get back the message by moving backward in the alphabets. Also, anyone trying to steal the message can't read it without knowing the key.
This old style encryption is called symmetric encryption since the message can be both encrypted and decrypted with the same key.
The biggest problem in this Encryption is to send the key to the receiver. When you are connecting to a Bank's website, How the bank can send you the key for you to encrypt your card details.
So they came up with an asymmetric type of encryption, in which they give a public key to everyone, including the hacker. so anyone who knows the public key can encrypt the message with that key. But only the bank knows the private key which is a secret. The message encrypted with a public key can be decrypted only with the private key. so only the bank can read your card details.
I found an interesting video about this, Here is the link
Now, it may be confusing that, the hacker knows the key with which the message is encrypted, but why can't he decrypt it?
The answer is Congruence. And also the difficulty in prime factorisation.
The most popular algorithm in this kind is RSA algorithm. The RSA algorithm is named after Ron Rivest, Adi Shamir, and Len Adleman, who invented it in 1977. RSA algorithm works by Number theory. I finally found an real life application of my classroom mathematics.
Mathematics Behind the RSA Encryption
1.Two large prime numbers are chosen. Let it be p and q. Let n = pq
2.Next is to calculate totient of n, ϕ(n):
ϕ(n) - totient of n denotes the no of integers <= n that are relatively prime to n.
Theorem: if p is prime, then ϕ(p) is p-1. (i.e) all the integers lesser than p are relatively prime to p.
By the above theorem, ϕ(n) = ϕ(pq) = (p-1)(q-1)
3. Let e be an integer such that 1<e<ϕ(n) and gcd(e,n) = 1.
4. Let d be an integer such that de ≅ 1 (mod ϕ(n)) i.e. de % ϕ(n) =1
5. Now, the public key is e and n.
6. The private key is d.
Let's start encrypting a message:
I found this simple example using small prime numbers which explains the RSA algorithm. Let me copy paste it.
Choose p = 3 and q = 11.
Computing n = p * q = 3 * 11 = 33.
Computing φ(n) = (p - 1) * (q - 1) = 2 * 10 = 20.
Let e = 7 (7 and 33 are coprime).
Compute a value for d such that 7d ≅ 1 (mod 20). which gives d=3.
Public key is (e, n) => (7, 33)
Private key is (d, n) => (3, 33)
Let the message to send is '2':
(Formula to encrypt msg) cipher = msg^e (mod n)
so, cipher = 2^7 % 33
cipher = 29
29 is sent over the network.
To decrypt 29:
(Formula to decrypt msg) msg = cipher^d % n.
msg = 29^3 % 33.
wow, we got back 2.
Thought of hacking the bank accounts
If the hacker was able to prime factorize n, then he can find p and q, from which he can calculate φ(n) and therefore can find d.
But prime factorization of such large number n (usually n is up to 128 bits to 256 bits) is nearly impossible.