SIT192 Discrete Mathematics Trimester 1: RSA Encryption Presentation

This presentation provides a comprehensive explanation of the RSA encryption algorithm, a fundamental concept in public-key cryptography. The presentation begins by introducing the RSA algorithm's origin and its widespread use. It then details the process, starting with the selection of two prime numbers (p and q) and the calculation of n, m, and e. The public key (e, n) and private key (d, n) are clearly defined, along with how they are derived. The core of the presentation demonstrates the encryption of a message using the public key and the subsequent decryption using the private key, illustrating the modular arithmetic involved. The presentation uses a numerical example, encrypting the number 12, and then decrypting it, to show how the algorithm works in practice. Finally, the presentation walks through the modular exponentiation calculations, showing how the original message is recovered, demonstrating the algorithm's ability to secure communication. This presentation is suitable for students studying discrete mathematics or computer science and looking for a detailed explanation of RSA encryption.

Project 1 - RSA Encryption
Slide 2
The RSA Algorithm was developed by Ron Rivest , Adil Shamir and Len Adleman at MIT in
1977 and first published in 1978.
It is the most widely accepted and implemented general purpose approach to public key
encryption.
Public Key Encryption means that one algorithm is used for encryption and decryption but
with a pair of keys. One for encryption and one for decryption.
Anyone can encrypt a message using the public key of the receiver and the receiver can
decrypt the message using his private key,
Slide 3
We need to choose two numbers p and q between 6 and 20.
So we choose p=17 and q=11. We can choose any number but it must be a prime number.
We get n = p*q = 17 * 11 = 187.
Slide 4
We calculate m as a product of (p-1)*(q-1) , we get
m= (p-1)*(q-1) = 16 * 10 = 160.
After that we choose a number e that is relatively prime to m and less than m ,
We choose e = 7.
Relatively prime number means that both the number have no other common factor except
1.
Slide 5
The resulting keys (e,n) is my public key.
We get public key , PU = {7,187}.
Public Key is a cryptographic key that is known to everyone and can be used by everyone to
encode and encrypt messages intended for a particular receiver.
The receiver can use its private key to decrypt the message since we use a public key -
private key pair.

Slide 6
We need to determine d such that d*e = 1(mod m ) = 1(mod 160) and d < 160.
The correct value of d is 23 since
d*e = 1 (mod 160) .
23 * 7 = 161 = (1*160)+1.
Therefore we get the value of d = 23.
(d,n) is the private key which is known only to the individual.
d can be calculated using the extended Euclidean Algorithm.
We take i = 1
We calculate d = ((m*i)+1)/e.
Keep increasing i by 1 and calculate d unless we get d as a whole number.
Slide 7
We need to encrypt message 12 using public keys (7,187) .
In order to encrypt the message , we calculate
c=message^e mod n
c= 12^7 mod 187. = 177
This is the encoded message.
Slide 8
We can calculate c=message^e mod n
c= 12^7 mod 187 = [(12^4 mod 187)*(12^2 mod 187)*(12^1 mod 187]mod 187
We get , 12^1 mod 187 = 12.
12^2 mod 187 = 144
12^4 mod 187 = 166.
c= (12 * 144 * 166 ) mod 187 = 177.
Slide 9
Decrypt your message using the private key (d,n) or (23,187)
In order to decrypt we calculate message = c^d mod n.
We calculate message = 177^23 mod 187.
We get message = 12.
Thus we get the original message back after decryption.
This is how we can demonstrate the encryption and decryption using a public key - private
key pair.
Slide 10
We can decrypt the message through this calculation ,
Message = 177^23 mod 187.
177^23 mod 187 = [(177^1 mod 187) * (177^2 mod 187) * (177^4 mod 187) * (177^8 mod
187) ^ (177^8 mod 187)] mod 187
(177^1 mod 187 = 177.) 177^2 mod 187 = 100
(177^4 mod 187 = 89. 177^8 mod 187 = 67.

We get message = (177 * 100 * 89 * 67 * 67) mod 187 = 12.
THANK YOU.