In this lesson, we show how RSA asymmetric algorithm based on Euler Totient Theorem,

and we show how the public key and private key are generated,

and we also describe how the message is encrypted and then decrypted.

We apply the Euler Totient Theorem to prove that

the resulting operation recovers the original plaintext messages.

RSA is asymmetric crypto algorithm proposed at

1978 in a paper by Ron Rivest,

Adi Shamir, and Len Adleman at MIT.

The name of the algorithm is the initial of the last names of the three inventors.

It is an exponential cipher utilizing Euler's Totient Theorem.

It is also called public key cryptography where the public key is

given out to everyone to use and the private is kept by the creator of the key pair.

It is based on the fact that finding factors of a large integer is very difficult,

very hard and this is called the factoring problem.

For their work, they received a prestige 2002 ACM Turing Award,

considered the Nobel Prize of computer science.

RSA key generations is five-step process.

First, we choose two large random prime number,

p and q, they are different.

Compute n=pq.

n is called the modulus for the public key and the private key.

Third, we calculate the totient, ϕ(n)=(p-1)(q-1).

Fourth, we choose integer e, such that 1<e<ϕ(n),

a totient function of n. e is relative prime to ϕ(n) and then the e is released,

send out to everyone as a public key exponent.

And often the 65537 which is two to the power of two,

to the power of four plus one.

And here, we have as a formula to the power of n plus one where (n=4).

And this formula is called Fermat number and with (n=4),

we call Fermat number four or F4 in short.

And typically, we use this number as e. Compute d such that d*e

and one are congruence of ϕ(n)

or using the equal operator,

d*e is equal to one time some k mod ϕ(n).

d is kept as a private key exponent and the public key is,

in this case there are two type of,

e and n. The private key is the type of d and n.

Let's now show how I say to the encryption and to the decryption.

And here, we have a big message like M. We typically chop them into

a small message segment or chunk

written by little case m. And through the equation,

we can compute the c,

a little case c which is ciphertext and n is the modular here,

e is a public key exponent,

d is a private key exponent.

Let's look at the encryption process.

Let's say Alice like to give, in the first step,

give out the public key,

e and n type to Bob.

Bob then chopped his message or the message he tried to send to Alice into a small chunk.

Each of them is numbers smaller than n, n the modular.

And let's represent that small chunk as little case m.

Bob then compute the ciphertext c with m to the power of e,

modular n. The formula we use here is c

equal to small m to the power e modular n. And so,

what we are saying is c and m to the e is congruent modular n. And then,

with a c computed,

Bob sends c to Alice.

Now, let's look at the decryption process.

Alice will first receive c from Bob and he can recover m from c by

doing this formula which is c to the power of d

modular n. And because we know the little original message m,

lower case m, (e,n) and c to the power of d are congruent to modular n. Now,

let's try to prove why that's the formula.

Here is a proof

of RSA algorithm with the message applied to the power of public key exponent with

the modular n operation followed by a prime that,

to the power of private key exponent,

modular n will recover the original message.

Step one, let's prove it.

We use the fact that the formula ed and one are congruent modular of ϕ(n),

the totient function of n,

is all true based on the RSA key selection method,

how they select d. It is then extended to these two equations here,

thereto where e time d and one are congruent modular

of p-1 and modular of q-1,

since ϕ(n) is equal to p-1 time q-1.

Step two, we apply Fermat's little Theorem,

and m to the power of ed is then congruent with

m on modular p and modular q.

Step three, since p and q are distinct prime number,

apply the Chinese Remainder Theorem which we are going to cover in

specialization of Applied Cryptography teach by Dr. Sam Kwong.

To these two congruence, we can then derive n to

the power ed and m are congruent modular of p and q.

Therefore, c time d and m are congruent modular n. This concludes the proof.

Here, we illustrate with small number on using RSA for confidentiality purpose.

First, we show encryption using RSA public key.

Let p=7, q=11 and p time q is 77,

so the modulus n is 77.

And ϕ(n), the totient function of n is 60 because

based on the totient function property

is equal to seven minus one times 11 minus one, 60.

Alice then choose e, 17,

which have to be the relative prime number to

60 totient of 77 which is 60.

We then find the private key, d,

and we find out when d is equal to 53 it certify the equation e*d

mod ϕ(n) =1 and we can pluck in 17*53 is 901,

and if we do a mod of 60,

it happen to be one.

If we represent the alphabet,

all upper cases and a blank with,

a number zero represent eight,

seven represent H, 25 represent Z, 26 represent blank.

Then, the "HELLO WORLD" can be encoded with a single digit

like 07 04 11 11 14 26 22 14 17 11 and 03.

And Alice then announce it's public key, the two type e and n,

which in this case is 17 for e,

77 for n, send it to Bob in public channel.

Using Alice public key,

Bob can generate the following ciphertext,

07 which is H to the power of 17 which is the public key of Alice and then mod 77,

which is a modular, equal to 28.

And same thing here,

four to the power of 17 mod 77 is 16.

And so, until the last number,

three to the power of 17 mod 77 is 75.

Bob then send all these encrypted number 28 16 44 all the way to 75 to Alice.

Only Alice has a private key.

Only he can decipher messages.

Now, let's look at the decryption process.

First, Alice public key is e and n,

which is 17 and 77.

The private key corresponding to that is d and n which is 53 to be d,

and n is 77.

We have this e*d mod ϕ(n) =1

and 17*53 mod 60 =1.

Since Alice received this encrypted number from Bob, 28, 16, 44,...,

75, we are going to use the private key 53 and 77 to decrypt that.

28, first number to the power of private key d,

53 mod 77 is 07,

indeed we recover 07 which is H. 16^53 mod 77, we can compute already,

that happen to be 04 which is E. 44*53 mod 77 is 11,

that happened to be L. And so on until

75^53 mod 77 we got 03 that happen to be D. So,

Alice was able to recover "HELLO WORLD" messages.

On the Mac or on Linux machine you can actually use

utility code PC to compute these values.

It is shown in the light green box how the

computation result using the PC or all these calculation, decrypt calculation.

I say, now we try to apply that for authenticate origin.

Alice computes the message using Alice private key.

Alice public key is 17 and 77,

private key is 53 and 77.

Here, Alice would like to send a message to Bob,

actually for anyone, let him know this message is sent indeed by her.

And so, the purpose of authentication,

we are not intending to hide the messages,

no need to encrypt here.

Alice uses her private key to compute the messages and anyone can use

her public key to prove the message was indeed sent by her.

Let's use her HELLO WORLD to encrypt the code.

07 to the power of,

private key of Alice is 53,

mod 77 is 35,

04 to the power of 53 and mod 77 is 09,

and so on until 03 to the power of 53 mod 77 is 05.

Alice will send 35, 09,

44,..., 05 send it to Bob.

Bob can apply her public key and recover exactly the messages,

and notice this cannot be sent by anyone but her because only she own the private key,

her own private key.

Here, we show the scenario where the message is encrypted and authenticated, both.

In this case, Alice encrypt using Alice private key first and the order matter here.

And then, the result is encrypted using the recipient,

the Bob's public key.

And Bob's public key is 37

and the modular n is 77 and the private key is 13 and 77.

Alice public key is 17, the modular n is 77,

and private key 53,

and with a modular n, 77.

Let's look at how Alice do the encryption.

First, you take the original message data 07^53 mod 77 and

the result applied to the power of 37 which

is Bob's public key exponent and mod 77,

the result is 07.

And then, same thing for 04 and 11.

And finally, (03^53 mod 77)^37 mod 77 is 47.

Alright. All this number is sent to the Bob.

Let's look at how Bob do the decryption, decipherment.

And he is going to use his own private key because the last step Alice do is

using the Bob's public key to encrypt so we need to reverse the process.

We received 07 take to the power of Bob's private key which is 13 mod 77,

and the result was then applied to the power of

the Alice public key exponent which is 17 mod 77 and we recover the result is 07.

And same thing for 37,

goes to the same formula we get 04.

And 47, we apply the same formula we get 03.

And indeed, we have this received message that is both

encrypted and we can provide authentication based on the other size of public key.

Only the sender can do the encryption using their private key.

Only Bob can decrypt his private key and recover these encrypted messages.

And Bob can then apply Alice public key to ensure

the message indeed sent by him using Alice private key for authentication purpose inside.