← Hall of Foundations Exhibit 146 · easy → · hard ←
The Conceptual Keystone

Easy one way,
hard the other

Many computational cryptographic constructions depend on functions that are easy to evaluate and difficult to invert on properly sampled inputs. Their security is conjectured, not proved merely by drawing an arrow. Information-theoretic systems such as the one-time pad do not require this computational assumption.

An assumption, not a proof. We believe these functions are hard to reverse; we cannot prove it. All of public-key cryptography is a bet that certain problems have no fast solution. So far, the bet has held.
§1

Multiply, then try to undo it

Multiplying suitably chosen large primes and attempting to recover them illustrates a candidate one-way relationship. For the tiny values shown, factoring is easy. The plot compares multiplication with a trial-division estimate, not with the fastest known general factoring algorithms.

—
The bar estimates trial division up to √n. The Factor button counts actual trial divisions for this tiny sample. More advanced factoring algorithms are substantially faster at large sizes; do not extrapolate this bar into an RSA security estimate.
§2

The trapdoor twist

Some public-key constructions add a trapdoor. RSA's relevant operation is modular exponentiation: knowing the prime factors lets the owner compute a private exponent and invert that operation. Decryption is not division of the ciphertext by a prime.

public: n = p·q  ·  trapdoor: the pair (p, q)

Trapdoor functions are one design pattern, not a description of every public-key scheme. Diffie–Hellman key agreement, for example, has a different structure.

Where this touches your keys

The bet under everything

Factoring breaks RSA, and solving discrete logs breaks classical DH and ECC. Post-quantum designs use several families, including lattice, code and hash-based assumptions. Security claims must name the particular construction and problem, rather than treating all these as the same trapdoor.

A cryptographic hash is intended to resist preimage search without a secret inversion trapdoor. This does not mean an attacker cannot recover a low-entropy input by guessing. No proof establishes that a concrete hash such as SHA-256 is a one-way function against every efficient attacker.

Next: Reduction & Proof — how we argue one wall is at least as tall as another.

Continue with RSA or explore security reductions.