Cryptography Reference
In-Depth Information
In this chapter we have investigated public-key encryption. We looked at the general
problem of designing a public-key cryptosystem and then studied two public-key
cryptosystems in some detail. We have also looked at how the properties of public-
key cryptosystems are most effectively harnessed in applications.
The main issues that we covered were:
• Public-key cryptosystems provide the potential for two entities who do not
share a symmetric key to employ cryptography to secure data that they
exchange.
• Public-key encryption requires the use of a trapdoor one-way function.
• RSA is a well-respected and widely-deployed public-key cryptosystem whose
security is based on the belief that factoring large numbers is difficult.
• ElGamal is a public-key cryptosystemwhose security is based on the belief that
solving the discrete logarithm problem is difficult.
• Variants of ElGamal that are based on elliptic curves offer the significant benefit
that keys are shorter than in either RSA or basic ElGamal.
• Public-key cryptosystems are less efficient to operate than most symmetric
cryptosystems. As a result public-key encryption is usually employed in a
process called hybrid encryption, which exchanges a symmetric key that is
then used for bulk data encryption.
The significant advantages to applications opened up by public-key cryptosystems
led to a revolution in cryptography in the mid-1970s, with a further boom in interest
following the development of the Internet in the 1990s. Public-key cryptosystems
are only likely to grow in importance in the coming years.
Public-key cryptography, to an extent, 'solves' the problem of symmetric key
establishment. However, as we indicate in more detail in Section 10.1.3, it 'replaces'
this problem with one of authenticating public keys. None of the advantages of
public-key cryptosystems can be fully exploited unless we have some level of
assurance that public keys are indeed associated with the entities to which we
believe they belong. This is a subject that we will discuss in detail in Chapter 11.
The history of the development of public-key cryptography is fascinating and, as
well as providing further motivation for this chapter, is well worth learning more
about. Good accounts can be found in Levy [117, 118] and Singh [176]. Also well
worth a read is the account by Ellis of the earlier British discovery of public-key
cryptography [69].
We have tried to be self-contained with respect to the minimum background
mathematics required for understanding the public-key cryptosystems in this
