Cryptography

Methodology

1. Description and hints/try to determine topic

Scripts

• RSA
• Padding Oracle

Tools

• Sage Math aka CoCalc
• quipquip
• Old school crypto tool
• FactorDB
• FactorDB-CLI
• RSATool
• Project Paranoid

Practice

• Cryptopals
• CryptoHack

Links

• Dealing with NACL in Python
• m13h CTF Writeups

Topics

Ciphers

• Cipher Identifier
  • Most ciphers can be found on this website
• Ciphey

Hashes

• Hash Identifier

SHA1

• SHA1 Collider 1/2

XOR

• XORtool
• XOR strings

Symmetric

ECB

• Block recovery script

CBC

• Padding Oracle

CTR

GCM

Asymmetric

Modular arithmetic

• Coprime: GCD(a, b) = 1
• Euclidean algorithm
• Extended Euclidean algorithm
• Multiplicative inverse: multinv(a, b) = x -- (a * x) % b = 1
• Fermat’s little theorem: pow(a, p, p) = a and pow(a, p - 1, p) = 1
• Legendre symbol
  • pow(q, (p - 1) // 2, p) == 1 means pow(a, 2, p) = q exists
  • if p % 4 == 3 then we can recover a with pow(q, (p + 1) // 4, p)
  • else p % 4 == 1, use Tonelli–Shanks algorithm
  • square_root_mod_prime(Mod(a, p))

RSA

• encrypt: c = pow(m, e, n)
• decrypt: m = pow(c, modinv(e, (p - 1) * (q - 1)), n)
• RSA Examples
• Featherduster
• RSACtfTool
• RSA Attacks
  • factorize primes (FactorDB)
  • weiner (d is small)
  • no padding
  • small primes
  • small e
  • multiple messages with same e
  • adjacent primes
• If N == p^2, the totient calculation is p(p - 1)

Broadcast attack

• Common variant: e == 3 and the same message is encrypted 3 times with 3 different values for N
• RSA Examples
• Writeup
• Another writeup

Chinese Remainder Theorem

• Notes

DSA

• Attacks

Rabin

• Wikipedia
• e = 2

Linear Congruential Generator (LCG)

• Wikipedia
• x_1 = (A * x_0 + B) % m
• Example problem

Keys

PEM

• ASN1

# Print values from PEM
from Crypto.PublicKey import RSA
print(RSA.importKey(open("a.pem", "rb").read()).d)

# ssh-keygen convert to PEM
ssh-keygen -f key.pub -e -m pem

OpenSSL

• Cheatsheet
• openssl rsa -in private.key -text -noout
• openssl rsa -pubin -noout -text < public.key