Image reproduced from Ref. [9].
In this post, i will note down my learning and understanding for the RSA algorithm. This will not go into deep details about RSA. Instead, only basics will be covered. In fact, most of the discussion presented here has already been covered in the relevant Wiki page: Click Me! Basically, I will just follow the Wiki page and put in my understanding along the way. Specially, when we go into the working example of RSA algorithm, detailed explanation about how the algorithm is realized in practice will be presented, with reference to some outstanding external resources. Finally, a bit understanding will be presented for why encryption and decryption through RSA algorithm is difficult or even impossible to decipher in practice and thus considered to be secure enough nowadays.
☝Keys generation
1. Select two prime numbers \(p\) and \(q\).
2. Calculate \(n = pq\).
3. Calculate \(\phi(n) = (p-1)(q-1)\).
4. Select an integer \(e\) satisfying 1) \(1 < e < \phi(n)\) and 2) \(e\) is co-prime to \(\phi(n)\).
5. Calculate \(d\) to satisfy the congruence relation \(de \equiv 1 (mod(\phi(n)))\).
The congruence relation here reads, \(de\) and \(1\) are equivalent in terms of the remainder when divided by \(\phi(n)\). In this sense, it does not matter that much whether \(de\) or \(1\) sits on the left-hand side.
\(n\) and \(e\) here are the public key that can be shared. \(d\) is the private key which should be kept securely. There is a question here: what we are generating is actually numbers, but that’s not what we usually see in public or private key file. For example, the example shows a demo for public key, where we actually do not see numbers but rather text. What is the trick here?
ssh-rsa AAAAB3NzaC1yc2EAAAADAQABAAABgQC+Z2085MxeBuiQ77giIgwAjYWID4ze7pUk+Z+ANcWgX479KJPHROjuY7fH6bJ9KoRGqyc3vu72nC6WdLMD6i/p+dTUmAuXyFVlgJNFUeejyRZTWnglNnGxAvB9y5F0LsNHj+fumhKSk8zY+cs8/5JkKyNSCp6VzI7DNjPOQmuMdja9Km2CeLk963aUEvx+bfYB0sPvuQnhOwCmw0bAp68QW048IjKWfZPDZC6gKZBE6udeu+rGLVVsMVCjmMyllfVIajrwAVvevIhSaUVcr02j7Rq9jRDAxbqI6BWXxD7D2oi+eYXic6yE67qbxoYflC2eBHGVgvZRcctDe682aioYBHDXl22f+160KSm6gawYBJmymM7WotOsKpBCyM9d9ghw+U+pkAJXOSqqtuGypGMG3DXJQfO44DyETiL99OgC9g4+cioPxVbXsK/txUoXim1QOG+e91V31TxisSVcZL6JfD2KGAhz5Nuhrgw9fiw37VB8r1fRrwAIh7ztOa/Sakk= y8z@mac117849
In fact, the number generated from the RSA algorithm is stored in the so-called PEM file format, which involves obviously some encoding scheme turning those generated numbers into text for storage. In this following post, there is introduced some other available format for storing public key: Click Me!
☝Encryption
First, the sender Bob needs to turn message M into a number m using some pre-agreed-upon protocol. Then Bob calculate the ciphered message c to send to the receiver following,
☝Decryption
When the receiver Alice receives the ciphered message c from Bob, she then needs to decode the original message m from c following,
☝Derivation
Given the way a certain message is encrypted and decrypted mentioned above, we only need to show,
Here, we need to remind ourselves again about the meaning of the congruence relation - see introduction above.
Back to the step of key generation, the values of \(e\) and \(d\) were chosen so that,
\[ed \equiv 1\ (mod\ \phi(n))\]Therefore, there exists some integer \(k\) so that,
\[ed = k\times\phi(n) + 1\]Following that, we have,
\[\begin{equation}\begin{aligned}m^{ed} & \equiv m^{k\phi(n) + 1}\\ & \equiv m\times m^{k\phi(n)}\\ & \equiv m\times(m^{\phi(n)})^k\ (mod\ n)\end{aligned}\nonumber\end{equation}\]According to Wiki page, we can apply Euler’s theorem here,
\[m^{\phi(n)}\equiv 1\ (mod\ n)\]to arrive at,
\[m\times (1)^k\equiv m\ (mod\ n)\]
However, Euler’s theorem actually applies to the situation where we have \(m\) and \(n\) involved here should be coprime. But in fact, it seems that \(m\) and \(n\) here may not be coprime - since \(m\) is generated from the message to be sent, which can be arbitrary. Concerning this confusion, here is a good reference for explanation: https://math.stackexchange.com/a/87720.
☝A Working Example
A working example demonstrating the RSA algorithm is practice is presented in the PDF doc below,
When trying to decrypt the original message \(m\) from the encrypted message \(c\), the calculation we need to conduct, as shown in the PDF doc above, \(c^{d}\ mod\ n\) is usually quite computationally expensive, since the numbers involved in the calculation could be very large in practice. To speed up the calculation speed, the Chinese remainder theorem can be used here. The theorem says,
Suppose \(p\) and \(q\) are relatively prime, then \(x \equiv a\ (mod\ pq)\) if and only if \(x\equiv a\ (mod\ p)\) and \(x\equiv a\ (mod\ q)\).
To demonstrate how the theorem can be used for message decryption, it is better to go with an example. We take the one given in Ref. [1] - \(c = 17639\), \(d = 11613\) and \(n = 21829\). We are going to calculate \(m \equiv 17639^{11613}\ mod\ 21819\). If we hold private key, then we know exactly \(21829 = 83 \times 263\). Therefore, according to the theorem,
\[m\equiv 17639^{11613}\ mod\ 83,\ \ m\equiv 17639^{11613}\ mod\ 263\]Simplifying the first congruence,
\[\begin{equation}\begin{aligned}m & \equiv 17639^{11613}\ mod\ 83\\ & \equiv 43^{11613}\ mod\ 83\end{aligned}\nonumber\end{equation}\]where the second line of the simplification comes from the fact that \(17639\equiv 43\ mod\ 83\). Furthermore, according to Euler’s theorem mentioned above, the calculation can be further simplified,
\[\begin{equation}\begin{aligned}m & \equiv 43^{51}\ mod\ 83\\ & \equiv 58\ mod\ 83\end{aligned}\nonumber\end{equation}\]Just to remind ourselves with Euler’s theorem,
’’’ For \(a\), \(N\) coprime, \(a^{\phi(N)}\equiv 1\ mod\ N\). ‘’’
Here we have \(N = 83\) itself is just a prime, and therefore \(\phi(83) = 82\), where \(\phi(N)\) is the number of positive integers smaller than \(N\) and coprime to \(N\). Therefore, if \(N\) is a prime, we know for sure
\[\phi(N) = N - 1\]Then we have,
\[43^{11613}\ mod\ 83 = (43^{82})^{141}\times43^{51}\ mod\ 83 \equiv 1^{141}\times 43^{51}\ mod\ 83\]
As for how we go from the first line to the second one in the calculation presented above, refer to Ref. [2] for a YouTube demo for a general method.
Following the same procedure, we can arrive at the following equation from the other congruent equation mentioned above,
Assuming \(m\) can be written as \(m = 263x + 44\), then we want to find \(x\) to satisfy,
\[263x + 44 \equiv 58\ mod\ 83\]
which can be further simplified to \(14x \equiv 14\ mod\ 83\). Then we can easily inspect the solution as \(x = 1\). For general situation of solving the congruent equations, refer to Ref. [3, 4].
☝RSA for SSH connection
Introduction about the application of RSA in SSH connection (the so-called ‘asymmetric encryption’) is beyond the topic of current blog. Detailed explanation/introduction can be found in Refs. [5-8].
☝In brief, why RSA is difficult to hack?
From the calculation presented above, we can see that to decrypt the encrypted message by the public key (\(n\) and \(e\)), one needs to know \(d\). To obtain \(d\), we actually start from \(n\) - however, knowing \(n\) is not enough, since it is beyond the capability of modern computer to calculate the two prime factors \(p\) and \(q\) from \(n\). This is the fundamental reason for why RSA algorithm is regarded as being safe enough for encryption and communication between client and server.
References
[1] https://www.youtube.com/watch?v=NcPdiPrY_g8
[2] https://www.youtube.com/watch?v=tTuWmcikE0Q
[3] https://www.expii.com/t/solving-linear-congruence-ax-b-mod-n-3389
[4] Evernote link to [3].
[5] https://www.hostinger.com/tutorials/ssh-tutorial-how-does-ssh-work