by: Hacking

RSA is an asymmetric cryptosystem that uses public and private key pairs.

  • Key Terms
  • Encrypt / Decrypt
  • Popular Tools
  • Known Vulnerabilities
    • Common Modulus

Key terms for crypto:

  • Ciphertext – the encrypted data.
  • Cipher – method of encrypting or decrypting data.
  • Plaintext – the data before encryption.
  • Encoding – a form of data representation, not encryption.
  • Key – a piece of information needed to decrypt.
  • Passphrase/Password – used to protect a key.
  • Cryptanalysis – attacking cryptography with math.
  • Elliptic Curve Cryptography (ECC) – a more efficient encryption method than RSA.

Encrypt:Decrypt:

Note:

  • n is the modulus, shared by both the public and private keys.
  • The public key is e and n.
    • e is the public exponent or encryption exponent.
  • The private key is d and n.
    • d is the private exponent or decryption exponent.

Where:

  • n = p * q
    • p and q are large prime numbers.
    • n is their product.
  • m is the message (plaintext, not encrypted).
  • c is the ciphertext (encrypted data).

The inverse also holds: the public key can decrypt data that was encrypted with the private key.

Additionally, in a mod b = c, the value c is the remainder of dividing a by b.

Popular tools for solving RSA crypto challenges in CTFs:

  • RsaCtfTool [Link].
  • RSATool [Link].
  • Pem2John [Link] from JohnTheRipper [Link].
  • Ssh2John [Link] from JohnTheRipper.

Cracking the password/passphrase of an SSH private key with RSA encryption:

wget https://raw.githubusercontent.com/openwall/john/bleeding-jumbo/run/ssh2john.py
python3 ssh2john.py id_rsa > id_rsa.hash
john --wordlist=/usr/share/wordlists/rockyou.txt id_rsa.hash

COMMONLY KNOWN WEAKNESSES AND VULNERABILITIES

  • Common Modulus – Rare in the real world, but common in CTFs and useful for understanding RSA concepts [Link].

It requires knowing:

  • n
  • c1 and e1
  • c2 and e2
git clone https://github.com/Ganapati/RsaCtfTool.git
python3 RsaCtfTool/RsaCtfTool.py --createpub -n MODULUS -e E1 > key1.pub
python3 RsaCtfTool/RsaCtfTool.py --createpub -n MODULUS -e E2 > key2.pub
sed -i '1d' key1.pub
sed -i '1d' key2.pub

# From Hex to Base64
echo C1 | xxd -r -p | base64 > ct1.b64
echo C2 | xxd -r -p | base64 > ct2.b64

wget "https://raw.githubusercontent.com/HexPandaa/RSA-Common-Modulus-Attack/master/rsa-cm.py"
python3 rsa-cm.py -h
python3 rsa-cm.py -c1 ct1.b64 -c2 ct2.b64 -k1 key1.pub -k2 key2.pub