Skip to main content

​
RSA Encryption Algorithm

An RSA key pair consists of a Private Key and a Public Key. The RSA algorithm is commonly used for digital signature verification and key exchange problems. The Public Key is used to encrypt data, while the Private Key is used to decrypt encrypted data. The RSA Public Key generation algorithm is based on the difficulty of integer factorization computations. The general problem is to find all prime factors of a given number nn. When nn is sufficiently large and is the product of a few large prime numbers, these computations are considered hard to solve. For RSA, nn typically has at least 512 bits and is the product of two large prime numbers. Locker uses RSA-2048, which has 617 decimal digits (2,048 bits) and is the largest among RSA numbers. RSA-2048 is likely to remain unfactorable for many years to come, unless there are significant advances in integer factorization or computational power in the near future. The RSA key pair is generated through the following steps:
  1. Choose 2 prime numbers pp and qq.
    1. pp and qq should be of similar magnitude and length to resist brute-force attacks.
  2. Compute n=p×qn = p \times q
  3. Compute the Carmichael function λ(n)\lambda(n). However, since pp and qq are prime,
    1. λ(n)=lcm(p−1,q−1)\lambda(n) = \text{lcm}(p-1, q-1)
    2. where lcm()\text{lcm}() is the least common multiple of two numbers.
  4. Choose an integer ee such that 1<e<λ(n)1 < e < \lambda(n) and gcd⁡(e,λ(n))=1\gcd(e, \lambda(n)) = 1, where gcd⁡()\gcd() is the greatest common divisor of two numbers.
  5. Find dd as the modular inverse of ee modulo λ(n)\lambda(n), i.e., d⋅e≡1(modλ)(n)d \cdot e \equiv 1 \pmod\lambda(n)
  6. The Public Key is the pair (n,e)(n, e), and the Private Key is dd.