Skip to content

This Repository is a collection of different ethical hacking tools and malware's for penetration testing and research purpose written in python, ruby, rust, c++, go and c.

5.4 KB
Raw Blame

RSA Decryption

RSA is an asymmetric encryption algorithm, which means that it uses a pair of keys: a public key for encryption and a private key for decryption. The RSA decryption process is used to convert the ciphertext (which was encrypted using the public key) back into its original plaintext using the private key.

RSA Decryption Process

Given the public key for encryption and the private key for decryption, the process of decryption in RSA involves:

  1. Ciphertext: The encrypted message ( C ) (ciphertext) that was generated by encrypting the plaintext ( M ) with the recipient’s public key.
  2. Private Key: The private key ( (n, d) ), where:
    • ( n ) is the modulus (product of two large primes ( p ) and ( q ))
    • ( d ) is the private exponent (calculated using the public exponent ( e ) and $( \phi(n) ))$.
  3. Decryption Formula: To decrypt the ciphertext ( C ), the recipient uses the private key ( d ) to compute: $[ M = C^d \ (\text{mod} \ n) ]$ where ( M ) is the original plaintext message.

Detailed Explanation of RSA Decryption

Let’s break down the decryption process with an example.

Key Generation Recap

  1. Choose two prime numbers:

    • $( p = 61 )$
    • $( q = 53 )$
  2. Compute modulus ( n ):

    • $( n = p \times q = 61 \times 53 = 3233 )$
  3. Compute the totient $( \phi(n) )$:

    • $( \phi(n) = (p - 1)(q - 1) = 60 \times 52 = 3120 )$
  4. Choose the public exponent ( e ):

    • Commonly, $( e = 17 )$, which is coprime with $( \phi(n) = 3120 )$.
  5. Compute the private exponent ( d ):

    • The private exponent $( d )$ is calculated as the modular inverse of $( e )$ modulo $( \phi(n) )$.
    • Using the extended Euclidean algorithm, we find that $( d = 2753 )$.

Thus, the public key is $( (n, e) = (3233, 17) )$, and the private key is $( (n, d) = (3233, 2753) )$.

Encryption Example

Let’s encrypt the message 65 using the public key.

  • The plaintext $( M = 65 )$.
  • To encrypt the message, the ciphertext ( C ) is calculated using the formula: $[ C = M^e \ (\text{mod} \ n) = 65^{17} \ (\text{mod} \ 3233) = 2790 ]$ So, the ciphertext is 2790.

Decryption Example

Now, let’s decrypt the ciphertext 2790 using the private key.

  • The ciphertext $( C = 2790 )$.
  • Using the private key $( (n, d) = (3233, 2753) )$, we decrypt the ciphertext by computing: $[ M = C^d \ (\text{mod} \ n) = 2790^{2753} \ (\text{mod} \ 3233) = 65 ]$ Thus, the decrypted plaintext is 65, which matches the original message.

RSA Decryption Code in Python

Here’s a Python implementation of RSA decryption:

# Function to compute gcd of two numbers
def gcd(a, b):
    while b:
        a, b = b, a % b
    return a

# Function to find modular inverse
def mod_inverse(a, m):
    m0, x0, x1 = m, 0, 1
    if m == 1:
        return 0
    while a > 1:
        q = a // m
        m, a = a % m, m
        x0, x1 = x1 - q * x0, x0
    if x1 < 0:
        x1 += m0
    return x1

# RSA Key Generation
def generate_keys():
    # Select two prime numbers
    p = 61
    q = 53
    n = p * q
    phi_n = (p - 1) * (q - 1)

    # Choose public exponent e
    e = 17  # Commonly used value

    # Compute private exponent d
    d = mod_inverse(e, phi_n)

    return ((n, e), (n, d))

# RSA Decryption
def decrypt(ciphertext, private_key):
    n, d = private_key
    return ''.join([chr(pow(char, d, n)) for char in ciphertext])

# Example usage
public_key, private_key = generate_keys()

# Encrypted message (ciphertext)
ciphertext = [2790]

# Decrypt the message
decrypted_message = decrypt(ciphertext, private_key)
print(f"Decrypted: {decrypted_message}")

Explanation of the Code

  1. Key Generation:

    • generate_keys() generates the public and private key pairs.
    • $( p = 61 )$, $( q = 53 )$ are the prime numbers chosen, and $( e = 17 )$ is the public exponent.
    • The private exponent $( d )$ is computed using the mod_inverse() function.
  2. Decryption:

    • The decrypt() function decrypts the ciphertext using the private key $( (n, d) )$.
    • The pow() function in Python is used for modular exponentiation, and chr() converts the decrypted numbers back into characters.

Applications of RSA Decryption

  • Secure Communication: RSA is widely used in protocols such as SSL/TLS to establish secure communication channels over the internet. In these protocols, RSA encryption is often used to securely exchange symmetric keys, which are then used for fast data encryption.

  • Digital Signatures: RSA is used to verify the authenticity and integrity of messages. A message can be signed using the sender's private key, and the signature can be verified by the recipient using the sender's public key.

  • Public Key Infrastructure (PKI): RSA is a fundamental part of the public key infrastructure, enabling secure key exchange, digital certificates, and authentication.

Conclusion

RSA decryption is an essential operation in the RSA cryptosystem, ensuring that only the holder of the private key can decrypt a message encrypted with the corresponding public key. By relying on the mathematical challenge of factoring large numbers, RSA provides robust security for data transmission, although it is becoming vulnerable in the age of quantum computing. Nonetheless, RSA remains a cornerstone in cryptography and secure communication.