Our world would be a very different place if tech giants or banks couldn't guard passwords. If you think about it, keeping secrets is fundamental to how we organize societies.
RSA algorithm is the workhorse technique which enables this secret keeping. We can understand how this public cryptography works with elementary number theory. Understanding why it works is a whole another topic.
An analogy
One way to send a secret (lets say password) is to mail a sealed envelope to your banker. But this is problematic because the envelope can be sealed and unsealed by anybody with access (like the mailman). This is not secure.
Instead, RSA algorithm is similar to this analogy: Your banker builds a public mailbox available to the entire world. Anybody can drop envelopes into it. But, only the banker has a private key to open this public mailbox.
In short, the Bank publishes a public key to encrypt messages and will keep secret the private key to decrypt those messages.
Before you read further, this note is Important
- Modulus is the remainder after a number is divided by a divisor.
- Since \(11 = 2 · 5 + 1\), you can write
- \(11 mod (5) = 1 \)
- \(11 mod (2) = 1 \)
- because 1 is the remainder resulting from \(11/5\) or \(11/2\)
Encryption & Decryption with an example
The RSA algorithm needs 3 elements to work:
- A public modulus
n - A public encryption key
e - A private decryption key
d
Lets say our message is m and the encrypted message is c. When c is decrypted, we must end back with the original message m.
- To illustrate RSA mechanics, I'll use
- \(n=33\)
- \(e=7\)
- \(d=3\)
- \(m=31\)
Encryption
- The message
mis encrypted with the function:- \(m^e mod (n) \)
- Its the same as the remainder of \(31^7/33\) which is \(4\)
- So, \(c=4\)
\(31^7 = 27512614111 = 833715579 · 33 + 4 \)
Decryption
- The message
cis decrypted with the function:- \(c^d mod(n) \)
- Its the same as the remainder of \(4^3/33\) which is \(31\)
- Therefore, \(m=31\)
\(4^3 = 64 = 1 · 33 + 31 \)
Rules of RSA algorithm
Above, we encrypted the message m to c and then decrypted c back to the original message m. If we join the encryption and decryption function, this is what we end up with:
\[(m^e \hspace{.2cm} mod(n))^d \hspace{.2cm} mod(n) = m\]
But, this function holds true only if \(n\), \(e\), \(d\) and \(m\) satisfy four conditions.
Lets verify if \(n=33 \hspace{.2cm} , e=7 \hspace{.2cm} , d=3 \hspace{.2cm} and \hspace{.2cm} m=31\) satisfy those conditions:
- \(n\) should be \(p · q\) where both \(p\) and \(q\) are prime numbers.
- \(n=33\) satisfies the condition because
- \(33=3·11\), where both \(3\) and \(11\) are primes
- \(n=33\) satisfies the condition because
- \(e\) must be \(>1\) and \(<(p-1)·(q-1)\) and a co-prime of \((p-1)·(q-1)\)
- \(e=7\) satisfies the condition because
- \((p-1)·(q-1) = (3-1)·(11-1) = 20\)
- \(1<7<20\)
- \(7\) and \(20\) are co-primes since their greatest common divisor is \(1\)
- \(e=7\) satisfies the condition because
- \(d\) must be such that \((d·e) \hspace{.2cm} mod ((p-1)·(q-1)) = 1\)
- \(d=3\) satisfies the condition because
- \((3·7) \hspace{.2cm} mod \hspace{.2cm} ((3-1)·(11-1)) = 21 \hspace{.2cm} mod \hspace{.2cm} 20 = 1\)
- \(d=3\) satisfies the condition because
- \(m\) must be less than \(n\)
- \(m=31\) satisfies the condition because it is less than \(33\)