Illustration of RSA Algorithm: p,q=7,19

This section provides a tutorial example to illustrate how RSA public key encryption algorithm works with 2 small prime numbers 7 and 19.

As the second example to illustrate how RSA public key encryption algorithm works, let's take prime numbers of 7 and 19 as presented by Paul Johnston at http://pajhome.org.uk/crypt/rsa/rsa.html.

Generation the public key and private key with prime numbers of 7 and 19 can be illustrated as:

```Given p as 7
Given q as 19
Compute n = p*q: n = 7*19 = 133
Compute m = (p-1)*(q-1): m = 6*18 = 108
Select e, such that e and m are coprime numbers: e = 5
Compute d, such that d*e mod m = 1: d = 65
The public key {n,e} is = {133,5}
The private key {n,d} is = {133,65}
```

With the public key of {133,5}, encryption of a cleartext M represented as number 6 can be illustrated as:

```Given public key {n,e} as {133,5}
Given cleartext M represented in number as 6
Divide M into blocks: 1 block is enough
Compute encrypted block C = M**e mod n:
C = 6**5 mod 133 = 7776 mod 133 = 62
The ciphertext c represented in number is 62
```

With the private key of {133,65}, decryption of the ciphertext represented as number 62 can be illustrated as:

```Given private key {n,e} as {133,65}
Given ciphertext C represented in number as 62
Divide C into blocks: 1 block is enough
Compute encrypted block M = C**d mod n:
M = 62**65 mod 133
= 62*62**64 mod 133
= 62*(62**4)**16 mod 133
= 62*(14776336)**16 mode 133
= 62*(14776336 mod 133)**16 mod 133
= 62*(36)**16 mod 133
= 62*(36**4 mod 133)**4 mod 133
= 62*(92)**4 mod 133
= 4441636352 mod 133
= 6
The cleartext M represented in number is 6
```

Very nice. We are getting the original cleartext 6 back with no problem with the private key.