Public Key Systems

Gesucht sind zwei Funktionen $enc, ~dec: \mathbb{N}\to \mathbb{N}$ mit folgender Eigenschaft:

1. $dec((enc(x))=x$
2. effizient zu berechnen
3. aus der Kenntnis von $enc$ läßt sich $dec$ nicht effizient bestimmen

Unter Verwendung dieser Funktionen könnte die Kommunikation zwischen den Partner Alice und Bob wie folgt verlaufen:

1. Alice möchte Bob eine Nachricht schicken.
2. Bob veröffentlicht sein $enc_B$.
3. Alice bildet $y:=enc_B(x)$ und schickt es an Bob.
4. Bob bildet $x:=dec_B(y)$.