First, let us recall the RSA algorithm. Again, p and q are big different primes. P doesn't equal to q, and n is their product. Then, for any number a less than N, and co prime to it. We can postulate this identity which is known as Euler's theorem, and phi of N here is Euler's phi function, which equals to the amount of numbers less than N, and co prime to it, and one is included. So, for prime numbers like p and q. Phi of p will be equal to p minus one since all the numbers less than p are co prime to it, and the same is with q. It is q minus one. For their product, for N, Euler's phi function equals to p minus one multiplied by q minus one because this function is multiplicative function. Now, having all these, we can choose some random number e less than N and co prime both to n and to phi of N. Since it is co prime to phi of N, it is invertible in the rink z modulo phi of n, and its inverse element we will call d. So, it is inverse of e, so e multiplied by d equals to one and in the rink z phi of N. Z modulo phi of n. Also, this e is the part of linear representation of the greatest common divisor of phi of N and e and this greatest common divisor is one since they are co prime, relatively prime and g and k are coefficients of this linear representation known as Bézout identity. The linear representation here can be built by the the extended Euclidean algorithm. Okay. Now, these numbers e and n, we will call the public key and the numbers d and N, we will call a private key. It is obvious that public key, we share widely and the private key, we keep in secret and don't share with anyone. Time to use these keys. Okay. To encode something, we need the message to be encoded. Luckily, we can choose it on our own. So, we choose some message m and the only restriction here is that this m has to be co prime with N with N big. This is very likely to be true for any randomly chosen message. We are going to encode it with the public key which is these two numbers. So, how we do it? We raise m in power e modulo M. So, we compute this number which is itself less than n since it is modular n here and this is our encrypted message. To decode this message we need this private key introduced on the previous slide and we decode in the same way, we raise this number M power e where is it in our d. Again, modulo N and this equals to m e multiplied by d modulo N and because of this identity here since d is the inverse element of e, we will have this. So, phi of n here is multiplied by some integer k because this identity we can rewrite like this. Phi of n here multiplied by some integer. Again, all these we have modulo n. Now, this thing here equals to one because let's recall the Euler's theorem. All we have left is message m, modular n and it is exactly m since m is less than n. So, we have encoded and here's our encoded message and we decoded it back and here's our decoded message. The idea is that you can't easily invert the separation of exponentiation modulo n. We will see it right now on some example like this number here when we raise it in some power N to calculate this power modulo m. We can't easily revert it. To revert it, we need this number d, and to find this number d we have to know the earliest function of N big and to know the Euler's function, we have to know the factors of N big and as I already told you, it is hard if N big is really big and the factors are unknown. Let's see an example. In real encryption, we have to choose really big prime numbers p and q but for the purpose of training, we can avoid that and we will choose p equal to 11 and q equal to 13. So, now let's compute our keys. N is 11 by 13. It is 143 and phi of n is 10 by 12. This 120. Now I have to choose number e, which is the prime both to n and two phi of n and I choose it to be 70. Now, we have to choose some message which is the prime number n. For example, let it be seven. Like, if you asked somebody how many teeth you have left and this person wants to answer seven, but he does not want it to go public and he encrypts it. We are ready to encrypt it right now. Okay. So, we have this public key which is 17,143 and because to encode message which is seven. So we have to raise seven in the power of 17, modulo 143. Okay, seven in the power of 17 is seven multiplied by 49 in the power eight, all this modulo of 143. Let's square 49. Forty-nine is 50 minus one, so it's easy to compute the square. This is 2,500 minus 100, plus one which is 2,401 and we're going to compute it modulo 143, which equals to 113 modulo of 143. So, instead of 49 here, we can multiply seven by 113 in the power four modulo of 143. Now, this 113 I'm lazy enough to compute it's square. So I noticed that in this modulo 113 equals to minus 30 modulo 143 and minus 30 is easier to square. So it is 900 and 900 is 40 to modulo 143. So, this transform to seven multiplied by 42 squared 143. Now 42 squared and if we square 42 and take the modulo, you can do it yourself, you will have seven multiplied by 49 and again everything is 143 and all this equals to 50. So, seven in the power of 17 modulo of 143 is 15 and this is the message. You ask somebody how many teeth etc. and he replies 15 and you understand that you need to decode this message. Okay. We have this public key 17,143 and we have a message encrypted by this key, write it like this, and we have this number 15. Now from this number 15, we have to extract the original message. So, we have to compute the private key and the private key d satisfies these equation so we write it down like 17d equals to one plus, if your [inaudible] is 120, so 120 multiplied by some integer k. So, actually we have to find both these coefficients, k and d and we are interested in d. Now, we can employ the extended Euclidean algorithm or we can notice that if we take d equal to seven, then we will have here 119, which is very close to 120. If we take k equal to minus one, we will have exactly minus 119. So, we have two instead of seven, we have to choose minus seven to get minus 119 in the left part of this equation. So, here's our private key and in the ring that modulo 120 minus seven equals to 113. So, to decode the message, we have to raise 50 in the power 113 modulo 143. For those of you who are not lazy enough, I would recommend it as a good exercise to prove by your own head hence that it equals to seven, our original message.