# 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

## Introduction

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 E _{e},* 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 =

*E*(m), and transmits c to

_{e}*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 |

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

Rabin |
integer factorization problem (§3.2) square roots modulo composite |

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

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

McEliece |
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.*