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 Algorithm (Rivest-Shamir-Adleman)
The RSA algorithm is one of the most widely used public-key encryption systems in modern cryptography. It was invented by Ron Rivest, Adi Shamir, and Leonard Adleman in 1977 and named after their initials (RSA). It is primarily used for secure data transmission, digital signatures, and key exchange.
RSA is based on the mathematical properties of large prime numbers and their ability to provide a one-way function, which is easy to compute in one direction but very difficult to reverse without a key.
RSA Algorithm - Key Concepts
RSA operates on two keys:
Public Key: This key is distributed openly and can be used to encrypt data or verify a signature. It consists of two numbers, ( n ) and ( e ).
- n is the modulus, a product of two large prime numbers, ( p ) and ( q ).
- e is the public exponent, which is generally a small integer like 3 or 65537.
Private Key: This key is kept secret and is used to decrypt data or create a signature. It consists of the modulus ( n ) (same as the public key) and the private exponent ( d ).
- d is calculated in such a way that it is the multiplicative inverse of ( e ) modulo $( \phi(n) )$, where $( \phi(n) )$ is Euler's totient function.
Steps to Generate RSA Keys
Choose Two Large Prime Numbers: Select two large prime numbers, ( p ) and ( q ).
- Example: $( p = 61 ), ( q = 53 )$ (for simplicity, actual primes used in RSA are much larger).
Compute ( n ):
- $( n = p \times q )$
- This modulus $( n )$ is used for both the public and private keys. The size of $( n )$ determines the strength of the encryption (larger ( n ) means stronger encryption).
Compute Euler's Totient Function ( \phi(n) ):
- $( \phi(n) = (p-1)(q-1) )$
- This value is important for determining the private key exponent ( d ).
Choose Public Exponent ( e ):
- Choose a value for $( e )$ such that $( 1 < e < \phi(n) )$ and $( e )$ is coprime with $( \phi(n) )$ $(i.e., ( \text{gcd}(e, \phi(n)) = 1 ))$.
- Commonly used values for $( e )$ are 3 and 65537.
Calculate Private Exponent ( d ):
- ( d ) is the modular multiplicative inverse of ( e ) modulo ( \phi(n) ). In other words, find $( d )$ such that: $[ d \times e \equiv 1 \ (\text{mod} \ \phi(n)) ]$
- This means $( d )$ is the number that, when multiplied by $( e )$, gives a remainder of 1 when divided by $( \phi(n) )$.
Public and Private Keys:
- The public key is the pair $( (n, e) )$.
- The private key is the pair $( (n, d) )$.
RSA Encryption and Decryption Process
Encryption:
- To encrypt a plaintext message $( M )$, the sender uses the recipient's public key $( (n, e) )$.
- The message $( M )$ must be represented as a number less than $( n )$, so it might need to be converted into an integer (using some standard encoding scheme like ASCII).
- The ciphertext $( C )$ is calculated as: $[ C = M^e \ (\text{mod} \ n) ]$
- The encrypted message $( C )$ is sent to the recipient.
Decryption:
- The recipient uses their private key $( (n, d) )$ to decrypt the ciphertext $( C )$.
- The original message $( M )$ is recovered by computing: $[ M = C^d \ (\text{mod} \ n) ]$
- The decrypted message $( M )$ is the same as the original plaintext message.
RSA Example
Let's walk through a simple example of RSA encryption and decryption with small numbers for illustration purposes.
Choose Two Primes:
- $( p = 61 )$
- $( q = 53 )$
Compute ( n ) and ( \phi(n) ):
- $( n = p \times q = 61 \times 53 = 3233 )$
- $( \phi(n) = (p-1)(q-1) = 60 \times 52 = 3120 )$
Choose Public Exponent ( e ):
- Let $( e = 17 )$ (a commonly used value that is coprime with $( \phi(n) ))$.
Calculate Private Exponent ( d ):
- Find $( d )$ such that $( 17 \times d \equiv 1 \ (\text{mod} \ 3120) )$.
- Using the Extended Euclidean Algorithm, we find $( d = 2753 )$.
Public Key: $( (n, e) = (3233, 17) )$
- Private Key: $( (n, d) = (3233, 2753) )$
Encryption:
- Suppose the plaintext message $( M = 65 )$ (we'll use the number 65 for simplicity).
- The ciphertext $( C )$ is: $[ C = M^e \ (\text{mod} \ n) = 65^{17} \ (\text{mod} \ 3233) = 2790 ]$
Decryption:
- The recipient uses their private key to decrypt: $[ M = C^d \ (\text{mod} \ n) = 2790^{2753} \ (\text{mod} \ 3233) = 65 ]$
- The decrypted message is the original plaintext $( M = 65 )$.
Security of RSA
RSA's security is based on the difficulty of factoring large numbers. Specifically, it is believed to be computationally infeasible to factor the product of two large prime numbers. This is known as the factoring problem. As the key length increases (e.g., 2048 bits or more), the difficulty of factoring ( n ) increases, making the encryption more secure.
Key Size: RSA key sizes of 2048 bits or higher are considered secure for most applications today. However, smaller key sizes like 512 or 1024 bits are vulnerable to factorization attacks with modern computing power.
RSA's Vulnerability: While RSA is highly secure, it is not without risks. Quantum computers could theoretically break RSA by using Shor’s algorithm, which can factor large numbers exponentially faster than classical algorithms. However, as of now, quantum computers are not yet powerful enough to break RSA encryption used in practice.
Applications of RSA
Digital Signatures: RSA is widely used for digital signatures, where the sender signs a message using their private key, and the recipient verifies the signature using the sender's public key.
Secure Key Exchange: RSA can be used to securely exchange symmetric keys over an insecure channel, such as in the SSL/TLS protocols used in web browsers.
Data Encryption: Although RSA can be used for encrypting small amounts of data, it is generally slower than symmetric-key algorithms like AES. Therefore, RSA is often used to encrypt a symmetric key, which is then used for the actual data encryption.
PKI (Public Key Infrastructure): RSA is widely used in PKI systems for managing and issuing digital certificates to verify the identities of users and devices.
Conclusion
The RSA algorithm is a powerful and widely used asymmetric encryption scheme that allows secure communication and digital signatures. It is based on the mathematical problem of factoring large numbers and provides strong security when large key sizes are used. Despite its robustness, RSA faces potential risks from quantum computing, which has led to research into post-quantum cryptographic systems.