Public-Key Cryptography - Codes: The Guide to Secrecy from Ancient to Modern Times - page 169

pragmatic ones, that serve us well. Moreover, we now have “candidate” one-
way functions such as the DLP and the IFP, discussed on page 165 — see also
Appendix C on page 509. The reader interested in a deeper analysis of this
issue may consult topics on complexity theory that go well beyond the basics
covered in Appendix A (see [101] for instance).
The reader may wonder at this point how it is that we could devise a cryp-
tosystem using one-way functions. The recipient of a message enciphered with
a one-way function would ostensibly be no better off than a cryptanalyst at
finding the plaintext since computing the inverse is computationally infeasible.
This is correct, so the recipient needs more information, the idea for which is
contained in the next notion.

Trapdoor One-Way Functions
A trapdoor one-way function or public-key enciphering function is a one-way
function,

,
satisfying the additional property that there exists information, called trapdoor
information , or simply trapdoor , that makes it feasible to find m

f : M → C

∈ M for a given

c img( f ) such that f ( m )= c , but without the trapdoor this task becomes

infeasible.

∈

Diagram 4.3 Trapdoor One-Way Function

f : computationally easy
−−−−−−−−−−−−−−−−−−→
f − 1 : computationally easy
←−−−−−−−−−−−−−−−−−−−−

✞ f ( m ) ∈ C

m ∈ M

trapdoor ❐

✝ ✆

The essential idea behind the Di8e-Hellman key exchange is the use of trap-
door one-way functions. The Di8e-Hellman Protocol, discussed earlier in this
section, allows for entities who have never met or exchanged information to es-
tablish a shared secret key by exchanging messages over an unsecured channel.
Since exponentiation modulo p is polynomial time, then enciphering is easy.
However, finding the inverse, solving the DLP, is computationally infeasible,
without the trapdoor, namely, one of the secret pair ( x, y ). This can be made
to work in a more general context, using the IFP, that is most germane to our
discussion of RSA in the next section, and will provide a nice motivator.

x e (mod n ) where n = pq with p

Example 4.4 Let f ( x ) ≡ = q primes, and

suppose that

de ≡ 1 (mod ( p − 1)( q − 1)) .

Then applying f is computationally, easy but finding

f − 1 ( x e ) f − 1 ( f ( x )) x ed

≡ ≡ ≡ x (mod n ) (4.3)

is computationally infeasible without the trapdoor d .