Introduction

RSA is public-key cryptosystem which can be used for encryption and digital signatures developed by Ron Rivest, Adi Shamir, and Leonard Adleman. Security is based on complex number factorization problem.

Subsoil of RSA

Correctness Proof of RSA

Preparation of RSA parameters

This process has three steps: generation of private and public key, encryption, decryption

Key generation

1. Draw dwo random distinct prime numbers p and q (The best way to increse security if prime numbers have similar bits length but with distant values from each other)
2. Compute N = pq
3. Compute
4. Draw an integer e such that , e and phi(N) must be coprime
5. Designate d from (The easiest way is to use Extended Euclides Algorithm - xgcd)
6. Lets define private key - (d, N) which one we keep in secret and public key - (e, N) which we can share.

Encryption

Let's choose message m an integer to encrypt such that , now we can use public key - (e,N) and this formula where c is ciphertext

Now ciphered message c is ready to send.

Decryption

Let's revover m from c by using private key - (d,N) and this formula

Now we can read the message where m is original message

Security of keys

NIST recommends 2048-bits keys(the size of the modulus N ) for RSA since 2015 and it will remain secure until 2030.Below is a summary of two tables to comparable strengths for Algorithms from NIST publication

Run time analysis and statement of results

Using the functions of the emulator_rsa, I created a test module that illustrates the time needed to compute key generation, encryption and decryption with a size module N in bits.

Summary of result in the table. For each bits length the numer of tests is 100

Sample output

bibliography

1. Neal Koblitz - A Course in Number Theory and Cryptography
2. https://en.wikipedia.org/wiki/RSA_(cryptosystem)
3. https://nvlpubs.nist.gov/nistpubs/Legacy/SP/nistspecialpublication800-57p1r3.pdf