Rivest–Shamir–Adleman (RSA)

Table of contents

  1. Definition
  2. Reference
  3. Terminology
  4. Deep Dive
  5. What if?
  6. Limitation

Definition

RSA Crypto Algorithm is invented by Rivest, Shamir, and Adleman, which is the abbreviation of their name. RSA is based on the principle that multiplying two large numbers is easy, but factorization of the large number is very difficult, especially the prime number. For example, it is easy to check if multiplying 187 and 323 is 92,701 or not, but finding the two prime factors of 92,701 will take a much longer time. RSA is public-key cryptography system, which is firstly introduced in the cybersecurity world. It means that RSA needs private and public key, and also it can be utilized in Digital Signature. For RSA Encryption/Decryption, it has several steps. 1) Key Generation, 2) Key Distribution, 3) Encryption, 4) Decryption. Let’s take a look at these steps in detail.

Reference

Please refer to the listed reference below. That help you understand what is RSA.

Terminology

  • Prime Factorization
    • A way of expressing a number as a product of its prime factors.
  • Prime Number
    • A integer number that has exactly two factors, 1 and the number itself.
  • Euler’s Phi(totient) Function
    • It counts the positive integers up to a given integer n that are relatively prime to n. That is. do not contain any factor in common with n, where 1 is counted as being relatively prime to all numbers.
    • Totative is the number which is less than or equal to and relatively prime to a given number n.
    • The totient function phi(n) can be simply defined as the number of totatives of n. For example, there are eight totatives of 24 (1, 5, 7, 11, 13, 17, 19, and 23), so phi(24)=8.
  • Euler’s Theorem

Deep Dive

  1. Time Complexity
    • RSA is based on Prime Number Factorization. Euclidean shows that every number has excatly 1 prime factorization.
    • For example, one of the prime factorization of 92,701 shall be 187x323. Each prime number can be converted into another prime factorization like (11x17)x(17x19). For the number of combination of the prime factorization of 92,701 should be 4.
    • Assume that if the prime number is very large, figuring out all of the prime factors would be tedious work. That is, the bigger the prime number is, the longer the time when attackers find out a exact one prime factorization is. In [Pic.1], it takes 198 years. RSA is exactly utilizing this property in order to prevent attackers from hijacking data.


    [Pic.1] Time Complexity of finding the prime factorization of large prime number

  2. Key Generation
    • RSA modulus N
      • RSA Modulus ‘N’ is the key of this algorithm. It is a positive integer which equals the product of two distinct prime numbers ‘p’ and ‘q’.
      • N = pxq (e.g., N= 5x7 = 35)
      • When you choose the two prime number, pick them which are greater than 1024-bit for the reason of security.
      • N will be the part of private and public key. Normally, when it comes to the size of RSK key, N is referred.
      • The picked two prime number should not be revealed to public.
    • Euler’s Phi(totient) Function
      • As we saw the Euler’s Phi(totient) Function as terminology, Finding out result of Phi functio is very difficult.
      • However, when it comes to the prime number, The phi function shows an interesting pattern as shonw in [Pic.2], which is Phi (prime number) = prinmumber -1 always. For exampe, Phi(5) = 4 (1, 2, 3, 4).


      [Pic.2] Phi function property for the prime number

      • So, we calculate Phi (pxq) = Phi (p) x Phi (q) (p and q is the prime number). In this example, Phi (35) = Phi (5x7) = Phi (5) x Phi (7) = (5-1) x (6-1) = 24.
    • Pick encoding exponent ‘e’ which is compliant with gcd (e, phi (pxq)) = gcd (e, (p-1)x(q-1)) = 1.
      • gcd stands for ‘Greatest Common Divisor’. If you mull over the equation above, the applicants of ‘e’ shall be a prime number except the prime numbers which are included in phi(pxq) factorization.
      • In this example, we calculate gcd (e, phi (5x7)) = 1. Then, e shall be 5, 7, 11, 13, 15, 17, 19.
      • Let’s see the factorization of phi (5x7) = 24. It shall be 1, 2, 3, 4, 6, 7, 12, 24. The prime number of this result should be 1, 2, 3.
      • Thus, e shall be the prime numbers that are less than 24 except for the prime numbers which are included in 24 factorization.
      • In this example, we pick ‘e’ = 5.
    • Euler’s Theorem
      • As shown in [Pic.3], Euler’s Theorem is that, if ‘a’ and ‘n’ are relatively prime, the result of moduls ‘n’ of the left term will be always 1. So, if you multiply phi (n) by ‘k’ constant, the result will alwasy be 1.
      • Based on this, if you mutiply the left term by ‘a’, the the result will be ‘a’.
      • This is the breakthrough. We make the resulting power correspond to ‘e’ x ‘d’. Since RSA is based on the assumption that it is almost impossible to find out the result of Phi (n) and the private key d, if the ‘n’ is much longer enough.


      [Pic.3] Euler's Theorem

    • [Pic.4] shows the proof of RSA Encryption and Decryption with ‘e’ and ‘d’


      [Pic.4] RSA Encryption and Decryption Proof

  3. Hands on RSA
    • [Pic.5] shows an hands on example of RSA encryption and decryption.


    [Pic.5] Hands on example

What if?

  1. What if am attackers steal the RSA public key with small N?
    • In this case, you and your intended opposites will be exposed to Man-in-the-middle-attack, Data interception, Phishing attacks, and Identity theft. RSA encryption and decryption is based on an assumption that the intended recipient can decrypt with the publisehd RSA public key, which means that attackers can obtain your public key also.
    • Additionaly, RSA is based on an important assumption that finding the prime factorization of N and calculating Phi (N) will take a huge amount of time in terms of computation. So the ‘N’ should be super longer enough.
    • Although attackers fail to find out your private key, they can encrypt malicious message and send you with the purpose of attack.
    • This is kind of attestation problem, and it should be solved in terms of out of band vericiation.

Limitation

  1. No efficient way has been found on modern computers to do prime factorization. Compared to ECC, it will take much longer time.
  2. If the quantum machines become widely spread out, RSA will not be up and running anymore.