The RSA Encryption Algorithm—Notes and Video Example

Need help understanding the RSA Encryption Algorithm? The two videos below give one of the best explanations on Youtube.

As a note, you should familiarize yourself with the modulus operation before learning the RSA encryption algorithm.

Introduction to RSA Encryption

Suppose that Alice would like to send an encrypted message to Bob, she would need to use the public keys provided publicly by Bob to transform her plaintext to an integer that is in the domain ZN and is not a multiple of p and q.

Converting a message to an integer is a requirement of the RSA Encryption Algorithm. That means that the message “Transfer complete” would first need to be converted into a number representation of the message. Look into number representation on Google for more details on how to convert messages to binary, decimal, or a different format.

P and Q are random integers chosen by Bob

Public keys are denoted as N and e

Private Key is denoted as d

Plaintext is the unencrypted message

Ciphertext is the encrypted message

Before Alice can send an encrypted message to BOB, she must encrypt the plaintext message using the public keys (N and e) made publicly by Bob.

The encryption function for RSA is:
ciphertext = me mod N

When Bob receives the encrypted message, he uses his private key (d) to decrypt the ciphertext using the following decryption formula.

The decryption function for RSA is:
plaintext = md mod N

How to compute the public keys N and e

Bob computes N using N = p * q

He then determines e by finding a number such that gcd(e, ϕ) = 1
where φ = (p−1)(q−1)

How to calculate the private key

The private key (d) must satisfy the following equation:
d⋅e mod φ = 1
where φ = (p−1)(q−1)

The following videos will walk you through calculating N, e, and d and run through a couple of examples on using The RSA Encryption Algorithm.

The RSA Encryption Algorithm
(Part 1 Video)

The RSA Encryption Algorithm
(Part 2 Video)