One-Way Functions - Contemporary Cryptography - page 177

Z n −→ Z n RSA n,e :

x e x −→

is called the RSA function . It computes the e th ∈ Z n . To compute the

inverse function, it is required to compute e th roots. If the inverse d of e modulo
φ ( n ) is known, then the following RSA function can be used to compute the inverse
of RSA n,e :

power for x

Z n −→ Z n RSA n,d :

x d x −→

RSA n,e can be efficiently computed by modular exponentiation. In order to
compute RSA n,d , however, one must know either d or the prime factors of n (i.e.,
p and q ). As of this writing, no polynomial-time algorithm to compute RSA n,d is
known if p , q ,or d are not known. Hence, RSA n,d can only be computed if any of
these values is known, and hence these values represent trapdoors for RSA n,e .
If we want to turn the RSA function into a family of one-way functions, then
we must define an index set I . This can be done as follows:

I := {

( n, e )

| n = pq ; p, q ∈ P

; p = q ;0 <e<φ ( n ); ( e, φ ( n )) = 1

}

Using this index set, the family of RSA functions can be defined as follows:

Z n −→ Z n ,x x e

RSA := { RSA n,e : −→ } ( n,e ) ∈I

This family of RSA functions is called the RSA family . Because each RSA
function RSA n,e represents a permutation over Z n , the RSA family represents a

family of one-way (or trapdoor) permutations.
It is assumed and widely believed that the RSA family is a family of trapdoor
permutations, meaning that RSA n,e is hard to invert (for sufficiently large and
properly chosen n ). The RSA assumption formally expressed in Definition 7.8 makes
the one-way property of the RSA family explicit.