# Chapter 12

RSA

The RSA system is probably the most widely used public-key cryptosystem in the world. It is certainly the best known. It provides both digital signatures and public-key encryption, which makes it a very versatile tool, and it is based on the difficulty of factoring large numbers, a problem that has fascinated many people over the last few millennia and has been studied extensively.

## 12.1 Introduction

RSA is similar to, yet very different from, Diffie-Hellman (see Chapter 11). Diffie-Hellman (DH for short) is based on a one-way function: assuming *p* and *g* are publicly known, you can compute (*g*^{x} mod *p*) from *x*, but you cannot compute *x* given *g*^{x} mod *p*. RSA is based on a trapdoor one-way function. Given the publicly known information *n* and *e*, it is easy to compute *m*^{e} mod *n* from *m*, but not the other way around. However, if you know the factorization of *n*, then it is easy to do the inverse computation. The factorization of *n* is the trapdoor information. If you know it, you can...