v. Cryptography Fundamentals

Why certain number-theoretic problems are treated as “hard” in complexity theory, and why hashing has an adversarial-input problem on judges like Codeforces: both come from the same handful of cryptographic primitives. Nothing here is a contest algorithm to implement from scratch; the value is knowing why factoring, discrete log and hash collisions are believed hard, since that belief is what several other notes lean on.

RSA

Public key $(n,e)$ with $n=pq$ ($p,q$ distinct large primes), private key $d$ with $ed\equiv 1(\mathrm{mod}\phi (n))$. Encrypt $c=m^e\mathrm{mod}n$; decrypt $m=c^d\mathrm{mod}n$ (fast modular exponentiation).

Proof: RSA decryption recovers the message

By construction $ed=1+k\phi (n)$ for some integer $k$. If $\gcd (m,n)=1$: $c^d=m^{ed}=m^{1+k\phi (n)}=m\cdot (m^{\phi (n)}{)}^k\equiv m\cdot 1^k=m(\mathrm{mod}n)$ by Euler’s theorem ($m^{\phi (n)}\equiv 1(\mathrm{mod}n)$ when $\gcd (m,n)=1$, see Euler’s theorem). If $\gcd (m,n)\ne 1$ (i.e. $p\mid m$ or $q\mid m$, astronomically unlikely for random $m<n$ but provable directly): WLOG $p\mid m$, so $c^d\equiv m\equiv 0(\mathrm{mod}p)$ trivially; mod $q$, $\gcd (m,q)=1$ so Euler’s theorem applies mod $q$ giving $c^d\equiv m(\mathrm{mod}q)$; combining both via CRT gives $c^d\equiv m(\mathrm{mod}pq)$. $■$

Why it’s believed secure: recovering $d$ from the public $(n,e)$ is believed to require factoring $n$ (known equivalent: computing $\phi (n)=(p-1)(q-1)$ lets you solve for $d$ directly, and $\phi (n)$ together with $n$ lets you recover $p+q$ and $pq$, hence $p,q$ via the quadratic formula). Pollard’s rho / Pollard’s p-1 factor $n$ in $O(n^{1/4})$-ish time for an $n$-bit number — far too slow for 2048-bit RSA primes, but exactly the technique this repo already implements for factoring numbers small enough for a contest. Shor’s algorithm (quantum, see Quantum Computing Basics) factors in polynomial time, which is the reason RSA is considered broken once large fault-tolerant quantum computers exist.

Diffie–Hellman key exchange

Public: a prime $p$ and a primitive root $g$ (Primitive Roots). Alice picks secret $a$, sends $A=g^a\mathrm{mod}p$; Bob picks secret $b$, sends $B=g^b\mathrm{mod}p$. Shared secret: $A^b\equiv g^{ab}\equiv B^a(\mathrm{mod}p)$ — both sides compute the same value without ever transmitting $a$ or $b$.

Why it’s believed secure: an eavesdropper sees $g,p,A,B$ and must recover $g^{ab}$ — the computational Diffie–Hellman problem, believed as hard as the discrete logarithm problem (recover $a$ from $g^a$). Baby-step giant-step solves discrete log in $O(\sqrt{p})$ — fine for the small moduli a contest uses, catastrophically slow for the 2048+-bit primes real Diffie–Hellman uses. Shor’s algorithm also solves discrete log in polynomial time on a quantum computer, by the same kind of period-finding it uses against factoring.

What makes a hash function cryptographically safe

Property	Means	Why judges care
Preimage resistance	given $h$, hard to find any $m$ with $H(m)=h$	prevents forging an input for a known hash
Second-preimage resistance	given $m_1$, hard to find $m_2\ne m_1$ with $H(m_1)=H(m_2)$	—
Collision resistance	hard to find any $m_1\ne m_2$ with $H(m_1)=H(m_2)$	the one that matters for CP string hashing

Polynomial string hashing mod a fixed, small, known modulus has none of these properties against an adversary who knows the modulus — anti-hash tests on Codeforces construct deliberate collisions by solving a linear system over the known modulus. The fixes used in practice (random base chosen at runtime, double hashing with two random moduli, or a modulus large and secret enough that it can’t be inverted offline) don’t make the hash cryptographic, they just make the specific collision-construction attack infeasible for that submission — a genuinely different and much weaker guarantee than what SHA-256 provides. Real cryptographic hashes (SHA-2, SHA-3/Keccak) are collision-resistant against anyone, with no secret parameter at all; they’re irrelevant for CP performance reasons (far slower per byte) but are the thing “hash function” means outside of CP.

The complexity assumptions underneath all of this

Assumption	Believed true?	What breaks if false
Integer factorization is hard (no polynomial classical algorithm)	yes, unproven	RSA
Discrete log (and Diffie–Hellman) is hard	yes, unproven	Diffie–Hellman, ElGamal
SHA-2/SHA-3 are collision-resistant	yes (no known attack better than generic birthday bound), unproven	digital signatures, blockchains, anything hash-committed
$\mathrm{P}\ne \mathrm{NP}$	widely believed, unproven	if false, breaks essentially all of modern cryptography at once, see [[24-beyond-cp/01-complexity-theory

None of these are theorems — they’re the strongest conjectures complexity theory has, and essentially all of applied cryptography rests on believing them.

Related notes

• Primality and Factorization, Primitive Roots and Discrete Log — the actual algorithms referenced above.
• Hashing, Hashing and Verification — the CP side of hash-function (in)security.
• Quantum Computing Basics — why quantum computers specifically threaten RSA and Diffie–Hellman.