Introduction to Cryptography with Open-Source Software

Chapter 5

Public-key cryptosystems based on

factoring

This chapter will contain investigations of

• The RSA cryptosystem: its definition, and its strengths and weaknesses.

• The Rabin cr yptosystem, which counters one possible weakness of the

RSA cryptosystem.

• Methods of attack on these cryptosystems.

• General notions of security on public-key cryptosys tems.

• Some a pproaches to factoring.

5.1 Introduction

Recall that a public-key cryptosystem is a cryptosystem with two distinct,

but related keys. Each us e r of the crypto system has a public key, which he or

she makes public, so that anyone else can use it to encrypt message s to the

user. The user