RSA
>>RSA
RSA is an algorithm for asymmetric cryptography. The algorithm was publicly described in 1977 by Ron Rivest, Adi Shamir, and Leonard Adleman at MIT. The RSA algorithm involves three steps, key generation, encryption and decryption.
Mathematics behind RSA
Suppose g(x) is the inverse function of f(x), then g(f(x))=x and f(g(x))=x.
Not all functions are invertible. For example, f(x)=0*x
There are some functions that are simple to understand, simple to calculate, but difficult to do its inverse unless its secret parameters are known. These functions are called trapdoor functions.
Modulus Arithmetic
The operator % gives the remainder of an integer division.
59 % 13 = 7
In modulus arithmetic, it is expressed as 59 = 7 (mod 13)
Then, 59 = 46 = 33 = 20 = 7 (mod 13)
For addition, 15+33 = 2+7 = 9 (mod 13)
For multiplication, 51*33 = 1683 = 12*7 = 84 = 6 (mod 13)
In modulus arithmetic, values can be reduced to their remainders before doing the calculation. This is very important for a program to handle huge numbers with limited processing power.
1937 (mod 55) = 1932+4+1 (mod 55) = 1932*194*19 (mod 55) = 192*2*2*2*2*192*2*19 (mod 55)
= 3612*2*2*2*3612*19 (mod 55) = 312*2*2*2*312*19 (mod 55) = 9612*2*2*961*19 (mod 55)
= 262*2*2*961*19 (mod 55) = 6762*2*961*19 (mod 55) = 162*2*961*19 (mod 55)
= 2562*961*19 (mod 55) = 362*961*19 (mod 55) = 1296*961*19 (mod 55) = 31*26*19 (mod 55) = 15314 (mod 55) = 24 (mod 55)
Relatively Prime
Two numbers are said to be relatively prime (coprime) if they have no common factors. Their HCF is 1.
e.g., 14=2*7 and 15=3*5, therefore 14 and 15 are relatively prime.
Euler's Totient Function
In number theory, the totient phi(N) of a positive integer N is defined to be the number of positive integers less than or equal to N that are coprime to N.
phi(8)=4 (1,3,5,7 are coprime to 8)
phi(12)=4 (1,5,7,11 are coprime to 12)
If N is prime, then phi(N)=N-1
IF P and Q are different primes, then phi(P*Q)=(P-1)*(Q-1)
This is given by PQ-1-(Q-1)-(P-1)=PQ-Q-P+1
phi(5*7)=phi(35)=4*6=24
If N=P*Q, then phi(N)=phi(P*Q)=(P-1)*(Q-1)
Euler's Totient Theorem
If X and N are relatively prime and X<N, then
Xphi(N) = 1 (mod N)
e.g., 3phi(4) = 32 = 9 = 1 (mod 4)
e.g., 7phi(5) = 74 = 2401 = 1 (mod 5)
RSA
From Euler's Totient Theorem,
Xphi(N) = 1 (mod N), X and N are relatively prime and X<N
It leads to:
Xphi(N) * Xphi(N) * Xphi(N) * ...... * Xphi(N) = 1 * 1 * 1 * ...... * 1 (mod N) = 1 (mod N)
XW*phi(N) = 1 (mod N) where W can be any number
XS = 1 (mod N) where S=0 (mod(phi(N)), S is any multiple of phi(N)
XS * X = 1 * X (mod N)
XS+1 = X (mod N)
Let E*D = S+1 = 1 (mod phi(N)), (It can be proved that E and D are both relatively prime to phi(N))
Then XE*D = X (mod N)
Therefore, (XE)D = X (mod N)
Finally, this is divided into 2 steps:
Encryption of X to Y: XE = Y (mod N), E and N form the public key
Decryption of Y to X: YD = X (mod N), D and N form the private key
Summary
Choose two large different prime numbers P and Q
N=P*Q, P and Q are large primes, therefore, it is difficult to find them from N
phi(N)=phi(P*Q)=(P-1)*(Q-1), it is also difficult to find phi(N) without knowing P and Q
Choose E and D such that E*D = 1 (mod phi(N)), E and D are different and are relatively prime to phi(N). Ideally, E and D are preferred to be relatively prime to each other.
E and N form the public key
D and N form the private key
Encrypt X to Y: XE = Y (mod N), where X and N are relatively prime and X<N
Decrypt Y to X: YD = X (mod N)
Note that X and N are relatively prime, X should not be P and Q, also X should not be 0, 1 and N-1 for encryption.
| variable | function | public/private | prime/composite | note |
| P | prime factor of modulus used to generate N | private | prime | P is different from Q, its bit length is about half the required bit length of N |
| Q | prime factor of modulus used to generate N | private | prime | Q is different from P, its bit length is about half the required bit length of N |
| N | modulus N=P*Q | public | composite | practical bit length = 1024 |
| phi(N) | phi(N)=(P-1)*(Q-1) | private | composite | |
| E | public exponent encryption exponent | public | E and D are different and are relatively prime to phi(N). common choices 3, 17 and 65537 | |
| D | private exponent decryption exponent | private | E and D are different and are relatively prime to phi(N). unlike E, D is a large number |
Public key = modulus and public exponent
Private key = modulus and private exponent
Simple demonstration
Applications
Digital envelope
The content to be enveloped is first encrypted with a one-time key K of a symmetric encryption algorithm (such as DES or AES).
This one-time key K is encrypted with the RSA public key E of the recipient (key wrapping).
The digital envelope containing the encrypted content and the encrypted one-time key are sent to the recipient.
The recipient uses his own private key D to decrypt and get the one-time key K.
The recipient uses this one-time key K to decrypt and get the original content.
Digital signature
The sender (signer) uses a message digest algorithm (such as MD5 or SHA) to calculate the message digest M1 of the message.
The message digest M1 is encrypted with the RSA private key D of the sender (signer). This is the digital signature DS.
The message and the digital signature DS are sent to the recipient.
The recipient uses the same message digest algorithm to calculate the message digest M2 of the received message.
The recipient gets the sender's public key E to decrypt the digital signature DS to get the message digest M1.
If M1 is equal to M2, it can be believed that the message is not altered and the message comes from the sender.
Cracking RSA
Though the RSA algorithm is quite simple, it is computationally infeasible to crack it if P and Q are big primes (each 512 bits).
Also, the message is added with random padding bytes before encryption to make it even more difficult to crack.
