SIT192 Discrete Mathematics Assignment 3: RSA Encryption

This presentation explains the RSA encryption algorithm, a fundamental concept in public-key cryptography. The assignment demonstrates the RSA algorithm through a step-by-step example. It begins by selecting two prime numbers, p and q, to calculate n and m. It then explains the selection of a public key exponent, e, and the calculation of the private key exponent, d. The core of the presentation involves encrypting a message using the public key and decrypting it using the private key, showcasing the mathematical operations involved, including modular exponentiation. The calculations are presented in detail, illustrating how the original message is recovered after decryption, effectively demonstrating the encryption and decryption process using a public-private key pair. This assignment is part of the SIT192 Discrete Mathematics course at Deakin University, focusing on the student's ability to explain mathematical concepts in an oral presentation.

Project 1
RSA Encryption

The RSA Algorithm
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.
Anyone can encrypt a message using the public key of the receiver and the
receiver can decrypt the message using his private key,

Step 1
Choose two numbers p and q between 6 and 20.
We choose p=17 and q=11.
We get n = p*q = 17 * 11 = 187.

Step 2
Calculate m as a product of (p-1)*(q-1) , we get
m= (p-1)*(q-1) = 16 * 10 = 160.
Choose a number e that is relatively prime to m and less than m ,
We choose e = 7.

Step 3
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.

Step 4
Determine d such that de = 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.

Step 5
Encrypt message 12 using public keys (7,187) .
To encrypt the message , we calculate
c= 12^7 mod 187. = 177
This is the encoded message.

Calculations (To calculate c)
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.

Step 6
Decrypt your message using the private key (d,n) or (23,187)
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.

Calculations (To calculate message)
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.