Introduction of RSA Algorithm

This chapter provides tutorial notes and example codes on RSA public key encryption algorithm. Topics include illustration of public key algorithm; proof of RSA encryption algorithm; security of public key; efficient way of calculating exponentiation and modulus; generating large prime numbers.

What Is Public Key Encryption?

RSA Public Key Encryption Algorithm

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

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

Proof of RSA Public Key Encryption

How Secure Is RSA Algorithm?

How to Calculate "M**e mod n"

Efficient RSA Encryption and Decryption Operations

Proof of RSA Encryption Operation Algorithm

Finding Large Prime Numbers

Conclusions:

• RSA (Rivest, Shamir and Adleman) uses public key and private key to encrypt and decrypt messages.
• RSA public keys are generated using 2 large prime numbers.
• RSA public key security is based the difficult level of factoring prime numbers. Given P and q to calculate n = p*q is easy. But given n to find p and q is very difficult.
• RSA encryption operation requires calculation of "C = M**e mod n", which can be done by loop of "C = C*C * M**e[i]".
• Most RSA tools are using public keys generated from large probable prime numbers, because generating large prime numbers is very expensive.