Walk Through of RSA Public-key Encryption for Beginners - Part IV: The RSA Function


The RSA function is a particularly practicaly family of bijections.

E(x)=xe mod N,  E:{0,…,N-1}->{0,…,N-1}

Where N=pq, p and q are two large prime numbers.

e is relatively prime to (p-1)(q-1)

The inverse of the RSA function is 

D(x)=xd mod N

d is the inverse of e mod (p-1)(q-1)

or d=e^-1 mod (p-1)(q-1)

Let us put this formular into our original scenario:

Alice wants to transmit a message x to Bob. She uses the enryption function E(x)=xe mod N where (N,e) is the public key Bob provides. Upon receiving the encrypted message, Bob uses his private key d to decrypt it.  The idea is that Eve does not know d and hence is not able to decrypt the message. 

Here is an example of RSA. Note that the numbers are very small for our convenience, in real life the numbers are much much larger.

Let p=5,q=11. N=pq=55. Now we need to choose a number relative prime to (p-1)(q-1)=40, let’s say it is 3.

This is our public key (N,e)=(55,3)

The private key is computed as 3^-1 mod 40 = 27. Thus the private key is 27.

Now suppose alice want to send x=7 to Bob, she encrypts it as 73 mod 55 = 13.

And Bob decrypts it as 1327 mod 55 = 7

 

But how do we make sure that such a protocol is secure? In other words, how do you ensure that Eve cannnot guess d from what she sees? The RSA relies on the following assumption:

Give N, e and y = xe mod N, there is no efficient algorithm to determine x. 

Why? Let’s say Eve tries to guess x by checking xe = y mod N for all possible values of x. She would have to try an order of N values of x. If N is 512 bits. then N is approximately 2512. This number is bigger then the age of universive in fermatoseconds. She could also try to factor N into p and q and tries to find d. But this requires her to factor a large number into its prime factors. A problem that is believed to be impossible to efficienlty solved for large N.  

But can Bob and Alice efficiently implement RSA? In order to do so, 

1.Bob needs to find prime number p and q. 

  1. Bob and Alice need to compute exponential modular N. 

For 1, it has been proven that there is an effient algorithm to determine if a number is prime. It is based on a basic fact from number theroy called Prime Number Theory. We will look into more details of this in the next note.

For 2, there is an recursive algorithm making use of repeated squaring. Again, we will look into more details of this in the next note. 

In conlusion, we have shown that Alice and Bob could efficiently encrypt and decrypt the message, whereas there is no efficient way for Eve to guess x.  Note that the security of RSA has not been formally proven and it largely depends on the fact that factoring is hard. 

« Walk through of RSA public-key encryption for beginners - Part I : An introduction Modal Sign-In Form With Twitter Bootstrap 3 and JQuery Validation »