Table of Contents:

Public-Key Encryption

Contents in Brief

  • 8.1 Introduction.............................283
  • 8.2 RSA public-key encryption.....................285
  • 8.3 Rabin public-key encryption....................292
  • 8.4 ElGamal public-key encryption...................294
  • 8.5 McEliece public-key encryption ..................298
  • 8.6 Knapsack public-key encryption..................300
  • 8.7 Probabilistic public-key encryption.................306
  • 8.8 Notes and further references....................312


This chapter considers various techniques for public-key encryption, also referred to as asymmetric encryption. As introduced previously (§1.8.1), in public-key encryption systems each entity A has a public key e and a corresponding private key d. In secure systems, the task of computing d given e is computationally infeasible. The public key defines an encryption transformation Ee, while the private key defines the associated decryption transformation Dd■ Any entity В wishing to send a message m to /1 obtains an authentic copy of A’s public key e, uses the encryption transformation to obtain the ciphertext c = Ee (m), and transmits c to A. To decrypt c, A applies the decryption transformation to obtain the original message m = Dd(c).

The public key need not be kept secret, and, in fact, may be widely available - only its authenticity is required to guarantee that A is indeed the only party who knows the corresponding private key. A primary' advantage of such systems is that providing authentic public keys is generally easier than distributing secret keys securely, as required in symmetric- key systems.

The mam objective of public-key encryption is to provide privacy or confidentiality. Since A’s encryption transformation is public knowledge, public-key encryption alone does not provide data origin authentication (Definition 9.76) or data integrity' (Definition 9.75). Such assurances must be provided through use of additional techniques (see §9.6), including message authentication codes and digital signatures.

Public-key encryption schemes are typically substantially slower than symmetric-key encryption algorithms such as DES (§7.4). For this reason, public-key encryption is most commonly used in practice for the transport of keys subsequently used for bulk data encryption by symmetric algorithms and other applications including data integrity and authentication, and for encrypting small data items such as credit card numbers and PINs.

Public-key decryption may also provide authentication guarantees in entity authentication and authenticated key establishment protocols.

Chapter outline

The remainder of the chapter is organized as follows. §8.1.1 provides introductory material. The RSA public-key encryption scheme is presented in §8.2; related security and implementation issues are also discussed. Rabin’s public-key encryption scheme, which is provably as secure as factoring, is the topic of §8.3. §8.4 considers the ElGamal encryption scheme; related security and implementation issues are also discussed. The McEliece public-key encryption scheme, based on error-correcting codes, is examined in §8.5. Although known to be insecure, the Merkle-Heilman knapsack public-key encryption scheme is presented in §8.6 for historical reasons - it was the first concrete realization of a public-key encryption scheme. Chor-Rivest encryption is also presented (§8.6.2) as an example of an as-yet unbroken public-key encryption scheme based on the subset sum (knapsack) problem. §8.7 introduces the notion of probabilistic public-key encryption, designed to meet especially stringent security requirements. §8.8 concludes with Chapter notes and references.

The number-theoretic computational problems which form the security basis for the public-key encryption schemes discussed in this chapter are listed in Table 8.1.

public-key encryption scheme

computational problem


integer factorization problem (§3.2) RSA problem (§3.3)


integer factorization problem (§3.2) square roots modulo composite n (§3.5.2)


discrete logarithm problem (§3.6) Diffie-Hellnran problem (§3.7)

generalized ElGamal

generalized discrete logarithm problem (§3.6) generalized Diffie-Hellnran problem (§3.7)


linear code decoding problem

Merkle-Helhnan knapsack

subset sum problem (§3.10)

Chor-Rivest knapsack

subset sum problem (§3.10)

Goldwasser-Micali probabilistic

quadratic residuosity problem (§3.4)

Blunr-Goldwasser probabilistic

integer factorization problem (§3.2) Rabin problem (§3.9.3)

Table 8.1: Public-key encryption schemes discussed in this chapter, and the related computational problems upon which their security is based.

< Prev   CONTENTS   Source   Next >