MISSION CONTROL
TRAINING DUEL RANKS

LOGBOOK

  • No tags found
Scanning...
  • Type at least 2 characters to search...

HELP

1 / 20
Other keys: show • Space: good • 1-4: rate • 0: skip • 5: flag • 6: invert

Question

What key principle classifies asymmetric algorithms by whether their one-way function has a trapdoor?

Answer

"Some asymmetric algorithms rely on one-way functions WITH trapdoor, others on one-way functions WITHOUT trapdoor."

RSA has a trapdoor (knowing p, q); DH, ElGamal and ECC do not

* With a trapdoor, a secret shortcut makes the inverse easy for its owner; without one, the inverse is hard for everyone. *

This fundamental distinction divides all public-key cryptography:

Type Trapdoor? Example Hard Problem
RSA Yes — knowing $p, q$ Encryption + Signatures e-th root mod N (factoring)
Diffie-Hellman No Key exchange only Discrete logarithm mod p
ElGamal No Encryption + Signatures Discrete logarithm mod p
ECC No Encryption + Signatures Discrete logarithm on curves

With trapdoor means: there exists a secret (the factorization $N = p \cdot q$) that makes the inverse computation easy. Without it, the inverse is infeasible.

Without trapdoor means: the inverse is hard for everyone — there is no shortcut. Security relies on the mathematical structure, not a secret shortcut.

Go deeper:

The idea of trapdoor function. A trapdoor function f with its trapdoor t can be generated by an algorithm Gen. f can be efficiently computed, i.e., in probabilistic polynomial time. However, the computation of the inverse of f is generally hard, unless the trapdoor t is given.[1]
The idea of trapdoor function. A trapdoor function f with its trapdoor t can be generated by an algorithm Gen. f can be efficiently computed, i.e., in probabilistic polynomial time. However, the computation of the inverse of f is generally hard, unless the trapdoor t is given.[1]
IkamusumeFan · CC BY-SA 4.0 · Wikimedia Commons
or press any other key