RSA Encryption

In this assignment we will write a $32$ bit, non$-$optimized version of the asymmetric public$-$private key encryption

algorithm RSA. It is a simplified version of the algorithm that is currently being used with SSH$,$ FTPS$,$ and https$.$

You wouldn't be able to use PayPal without it$.$ There is high level theory behind this algorithm, and you are not

required to understand all of it$.$ Our goal is to implement the steps and get it to work.

The goal of asymmetric encryption is to allow anyone on the outside, a client, to send an encrypted message to a

host, usually a web server, such that only the web server can decrypt the message. This allows the client and

server to set up private communication. The public key allows any client to encrypt. No clients can decrypt. The

private key is needed to decrypt, which only the server has. This makes it so only the server can decrypt the

messages sent from clients requesting communication. Once the server receives and decrypts the request for

communication, a symmetric encryption algorithm such as AES, where both the client and server can encrypt and

decrypt, is used from then on$.$

The RSA algorithm is implemented as follows:

Assume the message to be sent is an integer. For a message $m,$ find integers e$,d,$ and $n$ such that:

@$((m^e{)}^d)\%n=m$

In other words, find a mod value and two exponents such that raising a number to the product of

those exponents and then modding it gives you the original number back

Once these three numbers are found, asymmetric encryption is possible.

To create an encrypted message c$,$ also known as a cipher, use e and $n$ :

$-c=(m^e)\%n$

To decrypt, use $d$ and $n$ on the encrypted message:

$-(c^d)\%n=(((m^e)\%n{)}^d)\%n=((m^e{)}^d)\%n=m$

Thus, the public key, which allows encryption of a message $m,$ consists of:

e and $n.$

The private key, which allows decryption of a cipher c$,$ consists of:

$d$ and $n$

Note that since everything is being modded with $n,m$ must be less than $n$ in order to avoid duplicate ciphers

To raise to an exponent and then mod is called modular exponentiation.

We will write a function for this.