RSA Explained in Depth

THE CONCEPT:

Bear with me, this article is the longest one I have ever written, but I am sure it will be useful to you in some way or another.

• RSA algorithm is an asymmetric cryptography algorithm. Asymmetric means that it works on two different keys: Public Key and Private Key. As the name describes, the Public Key is given to everyone, and the Private key is kept private.
• You might be wondering what R, S, and A stand for in the abbreviation. It is nothing but the names of the mathematicians (Rivest–Shamir–Adleman) who developed a mathematical model for this algorithm.

Below is an example of asymmetric cryptography:

1. A client (for example, a browser) sends its public key to the server and requests some data.
2. The server encrypts the data using the client’s public key and sends the encrypted data.
3. The client receives this data and decrypts it.

Since this is asymmetric, nobody else except the browser can decrypt the data even if a third party has the public key of the browser.

The Mathematics Behind it:

• The idea of RSA is based on the fact that it is difficult to factorize a large integer. The public key consists of two numbers where one number is a multiplication of two large prime numbers.
• The private key is also derived from the same two prime numbers. So if somebody can factorize the large number, the private key is compromised. Therefore, encryption strength totally relies on the key size, and if we double or triple the key size, the strength of encryption increases exponentially.
• RSA keys can be typically 1024 or 2048 bits long, but experts believe that 1024-bit keys could be broken in the near future. But till now, it seems to be an infeasible task.

Below is the mechanism of working of the RSA Model:

1. Generating Public Key:

   • Select two prime no’s. Suppose P = 53 and Q = 59.
   • Now First part of the Public key : n = P*Q = 3127.
   • We also need a small exponent say e :
   • But e Must be An integer.
   • Not be a factor of Φ(n). 1 < e < Φ(n) [Φ(n) is discussed below],
   • Let us now consider it to be equal to 3. Our Public Key is made of n and e

2. Generating Private Key:

   • We need to calculate Φ(n) :
   • Such that Φ(n) = (P-1)(Q-1)
     so, Φ(n) = 3016 Now calculate Private Key, d : d = (k*Φ(n) + 1) / e for some integer k For k = 2, value of d is 2011.

3. Working:

   • Now we are ready with our – Public Key ( n = 3127 and e = 3) and Private Key(d = 2011) Now we will encrypt “HI”:

     • Convert letters to numbers : H = 8 and I = 9
     • Thus Encrypted Data c = (89e)mod n
     • Thus our Encrypted Data comes out to be 1394
     • Now we will decrypt 1394 :
       • Decrypted Data = (cd)mod n
     • Thus our Encrypted Data comes out to be 89 8 = H and I = 9 i.e. “HI”.

Implentation of a simple RSA Model:

• Now, we will be implementing a simple RSA Model using Python. Before that,we have to first learn about its methodology of working.

  1. Generating Keys:

  • To start, we need to generate two large prime numbers, p and q. These primes should be of roughly equal length and their product should be much larger than the message we want to encrypt.

  • We can generate the primes using any primality testing algorithm, such as the Miller-Rabin test. Once we have the two primes, we can compute their product n = p*q, which will be the modulus for our RSA system.

  • Next, we need to choose an integer e such that 1 < e < phi(n) and gcd(e, phi(n)) = 1, where phi(n) = (p-1)*(q-1) is Euler’s totient function. This value of e will be the public key exponent.

  • To compute the private key exponent d, we need to find an integer d such that d*e = 1 (mod phi(n)). This can be done using the extended Euclidean algorithm.

  • Our public key is (n, e) and our private key is (n, d).

1. Encryption:

   • To encrypt a message m, we need to convert it to an integer between 0 and n-1. This can be done using a reversible encoding scheme, such as ASCII or UTF-8.

   • Once we have the integer representation of the message, we compute the ciphertext c as c = m^e (mod n). This can be done efficiently using modular exponentiation algorithms, such as binary exponentiation.

2. Decryption:

   • To decrypt the ciphertext c, we compute the plaintext m as m = c^d (mod n). Again, we can use modular exponentiation algorithms to do this efficiently.

3. Example:

   • Let’s walk through an example using small values to illustrate how the RSA cryptosystem works.

• Suppose we choose p = 11 and q = 13, giving us n = 143 and phi(n) = 120. We can choose e = 7, since gcd(7, 120) = 1. Using the extended Euclidean algorithm, we can compute d = 103, since 7*103 = 1 (mod 120).

• Our public key is (143, 7) and our private key is (143, 103).

• Suppose we want to encrypt the message “HELLO”. We can convert this to the integer 726564766, using ASCII encoding. Using the public key, we compute the ciphertext as c = 726564766^7 (mod 143) = 32.

• To decrypt the ciphertext, we use the private key to compute m = 32^103 (mod 143) = 726564766, which is the original message.

The CODE:

• Below is the python code for implemnetation:

         import math
          
        # calculate phi(n) for a given number n
        def phi(n):
            result = n
            for i in range(2, int(math.sqrt(n)) + 1):
                if n % i == 0:
                    while n % i == 0:
                        n //= i
                    result -= result // i
            if n > 1:
                result -= result // n
            return result
          
        # calculate gcd(a, b) using the Euclidean algorithm
        def gcd(a, b):
            if b == 0:
                return a
            return gcd(b, a % b)
          
        # calculate a^b mod m using modular exponentiation
        def modpow(a, b, m):
            result = 1
            while b > 0:
                if b & 1:
                    result = (result * a) % m
                a = (a * a) % m
                b >>= 1
            return result
          
        # generate a random primitive root modulo n
        def generatePrimitiveRoot(n):
            phiN = phi(n)
            factors = []
            temp = phiN
            # get all prime factors of phi(n)
            for i in range(2, int(math.sqrt(temp)) + 1):
                if temp % i == 0:
                    factors.append(i)
                    while temp % i == 0:
                        temp //= i
            if temp > 1:
                factors.append(temp)
            # test possible primitive roots
            for i in range(2, n + 1):
                isRoot = True
                for factor in factors:
                    if modpow(i, phiN // factor, n) == 1:
                        isRoot = False
                        break
                if isRoot:
                    return i
            return -1
          
        # extended Euclidean algorithm to find the modular inverse of e mod phiN
        def modinv(e, phiN):
            g, x, y = egcd(e, phiN)
            if g != 1:
                raise Exception('Modular inverse does not exist')
            else:
                return x % phiN
          
        def egcd(a, b):
            if a == 0:
                return b, 0, 1
            g, y, x = egcd(b % a, a)
            return g, x - (b // a) * y, y
          
        def main():
            p = 61
            q = 53
            n = p * q
            phiN = (p - 1) * (q - 1)
            e = generatePrimitiveRoot(phiN)
            d = modinv(e, phiN)
            print(f"Public key: ({e}, {n})")
            print(f"Private key: ({d}, {n})")
            m = 123456
            c = modpow(m, e, n)
            decrypted = modpow(c, d, n)
            print(f"Original message: {m}")
            print(f"Encrypted message: {c}")
            print(f"Decrypted message: {decrypted}")
          
        if __name__ == "__main__":
            main()
          
  
  

OUTPUT:

• Public key: {3, 3233}
• Private key: {2011, 3233}
• Original message: 123456
• Encrypted message: 855
• Decrypted message: 123456

Advantages of RSA:

1. Security and Reliability: The RSA algorithm is renowned for its robust security, making it a preferred choice for secure data transmission.

2. Public-Key Cryptography: RSA employs a public-key cryptography system, using a public key for encryption and a private key for decryption.

3. Key Exchange: RSA facilitates secure key exchanges, allowing two parties to share a secret key without transmitting it over the network.

4. Digital Signatures: RSA supports digital signatures, enabling a sender to sign a message with their private key and allowing the receiver to verify the signature with the sender’s public key.

5. Widespread Use: RSA is extensively utilized in online banking, e-commerce, and secure communications due to its speed, efficiency, and reliability in real-time applications.

Disadvantages of RSA:

1. Slow Processing Speed: RSA is slower compared to other encryption algorithms, particularly with large datasets.

2. Large Key Size: To maintain security, RSA requires large key sizes, which demand more computational resources and storage.

3. Vulnerability to Side-Channel Attacks: RSA can be compromised through side-channel attacks, where attackers exploit leaks in power consumption, electromagnetic radiation, or timing.

4. Limited Application Use: RSA is unsuitable for applications needing constant encryption and decryption of large data volumes due to its slower speed.

5. Key Management and Complexity: Managing RSA’s private key securely can be challenging, and the algorithm’s sophisticated mathematics can be difficult for some to understand and implement.

6. Quantum Computing Threat(Wont happen in Near Future) : Future quantum computers could potentially break RSA encryption, posing a significant risk to its security.

So,This is how RSA Actually Works.If you are interested in the mathematics behind it and want to know about it in depth,do checkout the articles available on web.(It is actually Interesting!!)