RSA algorithm

Here's how RSA works

1 Generate the public and private keys

1. We generate 2 random, large prime numbers p and p. Here, we're using numbers with a length of 1024 bits (128 bytes), that will combine to a key-size of 1024 bits (128 bytes)2048 bits (256 bytes)3072 bits (384 bytes)4096 bits (512 bytes). These prime numbers stay secret and are only used to generate the public and private keys.
   • The first prime number (p) is
     Prime number 1 (p)
   • The second prime number (q) is
     Prime number 2 (q)
2. Based on these 2 prime numbers we are able to calcuate a lambda value (λ).
   • The lambda (λ) is the least common multiple of our 2 prime numbers, with 1 subtracted.
   • Just like our prime number, we keep this value secret.
   lcm(p -1, q -1) = λ

   lcm(

   Prime number 1 (p)

   - 1,

   Prime number 2 (q)

   -1) =

   Lambda (λ)
3. Once we've calculated all secret values, we can generate the values for our public and private keys. Once again, we can use the 2 prime numbers to calcuate the modulus (n).
   • This value is calculated by multiplying the first prime number (p) by the second prime number (q).
   • The modulus is used for both the public and private key.
   p * q = n

   Prime number 1 (p)

   *

   Prime number 2 (q)

   =

   Modulus (n)
4. Next to the modulus, the public key also contains a public exponent (e). To calculate the public exponent. This will be a smaller, co-prime number of our lambda.
   • The public exponent needs to be bigger than 1.
   • It needs to be smaller than the lambda (λ).
   • The greates common divider of our public exponent and our lambda (λ) should be 1.
   • Our newly calculated public exponent and our lambda (λ) should be coprime numbers.
   1 < e < λ AND gcd(e, λ) = 1

     e = randomPrime() =

   Public exponent (e)

   
     1 <

   Public exponent (e)

   <

   Lambda (λ)

   AND gcd(

   Public exponent (e)

   ,

   Lambda (λ)

   ) = 1
   
5. The private key also contains a private exponent (d). We can determine this private exponent by finding the modular multiplicative inverse of our public exponent (e) and the lambda (λ).
   e^-1 (mod λ) = d

   Public exponent (e)

   ^-1 (mod

   Lambda (λ)

   ) =

   Private exponent (d)

2 We can encrypt a message using our public key

1. Encrypting a message (m) will make use of a mathematical algorithm in combination with the public key information we determined earlier. In order to do these calculations, we need to convert our message (m) to an integer.
2. Once we have the message (m) as an integer, we can find the Modular exponentiation of our message (m), raised to the power of our public exponent (e), divided by our modulus (n).
   m^e (mod n) = cipher (c)

   Please enter a message to encrypt on the top of the page...

3 Decrypting a message can be done by leveraging our private key

1. We will have to convert our cipher (c) to a number again, if it's transmitted in another format
2. To decrypt a cipher (c) we need to find the Modular exponentiation of our cipher (c), raised to the power of our private exponent (d), divided by our modulus (n).
   c^d (mod n) = message (m)

   Please enter a message to encrypt on the top of the page...
3. The output (m) of the decryption algorithm is going to be an integer. The last task left to do is convert this integer to binary so we can convert it back to an ASCII string.
   Please enter a message to encrypt on the top of the page...
   ^*Pseudo-code