knowledge/technology/cryptography/RSA.md
2024-02-06 08:12:49 +01:00

2.8 KiB

obj
concept

RSA

RSA (Rivest-Shamir-Adleman) is a widely used asymmetric encryption algorithm that enables secure communication and digital signatures. Named after its inventors, Ron Rivest, Adi Shamir, and Leonard Adleman, RSA relies on the mathematical properties of large prime numbers for its security.

Key Concepts

1. Asymmetric Encryption

RSA is an asymmetric algorithm, meaning it uses a pair of keys: a public key for encryption and a private key for decryption. The public key is widely distributed, while the private key is kept secret.

2. Key Generation

  • Key Pair: The RSA key pair consists of a public key and a corresponding private key.
  • Public Key: Composed of a modulus N and an exponent e.
  • Private Key: Composed of the same modulus N and a private exponent d.
  • Key Generation Process:
    1. Select two large prime numbers, p and q.
    2. Compute N = pq.
    3. Compute ϕ(N) = (p - 1)(q - 1).
    4. Choose e such that 1 < e < ϕ(N) and e is coprime to ϕ(N).
    5. Calculate d as the modular multiplicative inverse of e modulo ϕ(N).
    6. The public key is (N, e) and the private key is (N, d).

3. Encryption and Decryption

  • Encryption: Given the public key (N,e), a plaintext message M is encrypted as C = M^e \mod N.
  • Decryption: Using the private key (N,d), the ciphertext C is decrypted as M = C^d \mod N.

4. Digital Signatures

RSA is commonly used for digital signatures to verify the authenticity and integrity of messages. The sender signs a message with their private key, and the recipient can verify the signature using the sender's public key.

Security Considerations

  • The security of RSA relies on the difficulty of factoring the product of two large prime numbers (N = porque).
  • The key length is crucial for security; longer keys provide higher security but may be computationally more expensive.

Using RSA in Practice

Using RSA can be done either with OpenSSL or GPG.

1. Key Generation:

# Generate a 2048-bit RSA private key
openssl genpkey -algorithm RSA -out private_key.pem -aes256

# Derive the corresponding public key
openssl rsa -pubout -in private_key.pem -out public_key.pem

2. Encryption and Decryption:

# Encrypt a message with the public key
openssl rsautl -encrypt -in plaintext.txt -out ciphertext.enc -pubin -inkey public_key.pem

# Decrypt the ciphertext with the private key
openssl rsautl -decrypt -in ciphertext.enc -out decrypted.txt -inkey private_key.pem

3. Digital Signatures:

# Sign a message with the private key
openssl dgst -sha256 -sign private_key.pem -out signature.bin message.txt

# Verify the signature with the public key
openssl dgst -sha256 -verify public_key.pem -signature signature.bin message.txt