RSA Encryption

Last modified Jun 19, 2022
RSA Encryption

An RSA key pair consists of a Private Key and a Public Key. The RSA algorithm is often used for digital signature verification and key exchange problems. The Public Key is used to encrypt the data and the Private Key is used to decrypt the encrypted data.

The RSA Public Key Generator algorithm is based on the difficulty in solving the ”factoring problem”. The factorization problem is to find all primes of a given number n. When n is large enough and is the product of several large primes, the problem is considered complicated. For RSA, n is usually at least 512-bit and is the product of two large primes.

Locker uses RSA-2048, which has 617 decimal digits (2,048 bits) and is the largest of the RSA numbers. RSA-2048 may not be factorizable for many years to come unless considerable advances are made in integer factorization or computational power in the near future.

An RSA key pair is generated with these steps:

1. Pick 2 prime numbers $p$ and $q$.
1. $p$ and $q$ should be equally large and of similar bit-lengths for extra resistance against brute-force attacks.

1. Calculate $n = p*q$
1. Calculate $λ(n)$, with $λ(n)$ being the Carmichael function. Furthermore, $p$ and $q$ are prime numbers so
1. $λ(n)=lcm(p-1,q-1)$

with $lcm()$ being the least common multiple of the 2 numbers.

1. Pick a prime number $e$ such that
1. $\begin{cases} 1

with $gcd()$ being the greatest common factor of 2 numbers.

1. Find $d$ such that
1. $d ≡ e^{−1}\;\;(mod λ(n))$

1. The public key is the tuple $(n,e)$ and the secret key is $d$.