Problem Solving Guide

Cryptography · Axiom Academy

SUMMARY Cryptography Problem-Solving Guide Comprehensive strategies and step-by-step approaches for tackling cryptography problems across all major topics. Encryption/Decryption Approach: Identify cipher type, note alphabet size, apply transformation systematically Frequency Analysis: Count letter frequencies, compare to expected distribution, identify most common patterns Breaking Substitution: Start with single letters (E, T, A), look for common digraphs (TH, HE), verify with context Common Pitfall: Forgetting to preserve case or punctuation when specified Modular Inverses: Use Extended Euclidean Algorithm: gcd(a,n)=1 required, work backwards to find coefficients Linear Congruences: Reduce to ax ≡ b (mod n), find inverse of a, multiply both sides Chinese Remainder Theorem: Verify moduli are coprime, compute M and Mi values, find inverses, combine solutions Common Pitfall: Not checking gcd = 1 before attempting inverse calculation Key Generation Checklist: Choose primes p,q → compute n = pq → calculate φ(n) = (p-1)(q-1) → select e with gcd(e,φ)=1 → find d = e -1 mod φ Encryption/Decryption: Encrypt: C = M e mod n; Decrypt: M = C d mod n (use fast exponentiation) Attack Recognition: Small e with small message → try e-th roots; d too small → Wiener's attack; common modulus → exploit Common Pitfall: Confusing public (e,n) and private (d,n) key components

This is the written version of the interactive lesson above. See the full Cryptography course.