Cryptography Reference
In-Depth Information
The remainder of this chapter states some fundamental definitions in public key cryp-
tography and illustrates them using the RSA cryptosystem.
1.1 Public key cryptography
Two fundamental goals of cryptography are to provide privacy of communication between
two entities and to provide authentication of one entity to another. Both goals can be achieved
with symmetric cryptography. However, symmetric cryptography is not convenient in some
applications for the following reasons. First, each pair of communicating entities needs to
have a shared key. Second, these keys must be transmitted securely. Third, it is difficult to
obtain signatures with non-repudiation (e.g., suitable for signing contracts).
In the mid 1970s Merkle, Diffie and Hellman proposed the idea of
public key cryptog-
raphy
(also sometimes called
asymmetric cryptography
). This idea was also proposed
by Ellis at GCHQ, under the name “non-secret encryption”. One of the earliest and most
important public key cryptosystems is RSA, invented by Adleman, Rivest and Shamir in
1977 (essentially the same scheme was also invented by Cocks at GCHQ in 1973).
As noted above, a major application of public key cryptography is to provide authenti-
cation. An extremely important example of this in the real world is digital signatures for
authenticating automatic software updates. The public key of the software developer is
stored in the application or operating system, and the software update is only performed
if the digital signature on the update is verified for that public key (see Section 11.1 of
Katz and Lindell [
300
] for more details). Signature schemes also provide message integrity,
message authentication and non-repudiation (see Section 9.2 of Smart [
513
]). Other impor-
tant applications of public key cryptography are key exchange and key transport for secure
communication (e.g., in SSL or TLS).
1.2 The textbook RSA cryptosystem
We briefly describe the “textbook” RSA cryptosystem. The word “textbook” indicates that,
although the RSA cryptosystem as presented below appears in many papers and books, this
is definitely not how it should be used in the real world. In particular, public key encryption
is most commonly used to transmit keys (the functionality is often called key transport or
key encapsulation) rather than to encrypt data. Chapter
24
gives many more details about
RSA including, in Section
24.7
, a very brief discussion of padding schemes for use in real
applications.
Alice chooses two large primes
p
and
q
of similar size and computes
N
=
pq
. Alice
also chooses
e
∈ N
coprime to
ϕ
(
N
)
=
(
p
−
1)(
q
−
1) and computes
d
∈ N
such that
ed
≡
1(mod
ϕ
(
N
))
.
Alice's
public key
is the pair of integers (
N,e
) and her
private key
is the integer
d
.To
encrypt
a message to Alice, Bob does the following:
