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.
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:
- Ciphertext: The encrypted message ( C ) (ciphertext) that was generated by encrypting the plaintext ( M ) with the recipient’s public key.
- 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) ))$.
- 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
Choose two prime numbers:
- $( p = 61 )$
- $( q = 53 )$
Compute modulus ( n ):
- $( n = p \times q = 61 \times 53 = 3233 )$
Compute the totient $( \phi(n) )$:
- $( \phi(n) = (p - 1)(q - 1) = 60 \times 52 = 3120 )$
Choose the public exponent ( e ):
- Commonly, $( e = 17 )$, which is coprime with $( \phi(n) = 3120 )$.
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
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.
Decryption:
- The
decrypt()function decrypts the ciphertext using the private key $( (n, d) )$. - The
pow()function in Python is used for modular exponentiation, andchr()converts the decrypted numbers back into characters.
- The
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.