## Public Key Cryptography and the RSA Cryptosystem

Cryptography is sometimes confused with the related but distinct

field of coding theory that deals with reliability of communication

over noisy channels. See the author’s earlier book titled “An

introduction to coding theory via Hamming codes” for an

introduction to coding theory.

There are two basic methods in cryptography: classical cryptography

and public key cryptography. The latter is a more recent idea and this

book will focus on that method through one of its best known and

widely used examples: RSA cryptosystem. Proposed in 1977, the

RSA cryptosystem has survived many attacks and is still commonly

used.

Ideas from computational complexity play a very fundamental role in

cryptography. A formal prerequisite for this book is familiarity with

basic concepts of algorithm analysis and computational complexity,

including the big-O notation. Students are also assumed to be able to

do basic programming in a language such as C, C++ or Java.

Necessary material from elementary number theory is covered in the

book, though familiarity with modular arithmetic and some very

basic logic (such as proof by contradiction) will be useful. Since

mostly number theoretical algorithms are discussed in this book, it is

very important for an instructor to emphasize that if the input to such

an algorithm is an integer n, then the size of the input is taken to be

2 log (n) +1, number of bits needed to store n, not the magnitude

of n. This is a point that is easy for students to forget, therefore it is

worth repeating. While providing necessary background in

elementary number theory, students will be given a gentle

introduction to some fundamental notions in abstract algebra such as

groups, rings, and fields. Students who already have this background

may skip that part. (Even if they saw the material before, a quick

review would not hurt). If the mathematical maturity of the students

is not at the right level, some of the proofs could be optional. The

software used in this book is Maple 12, though it should also work

with earlier versions of Maple. There are several projects to choose

from at the end. Given the nature of the subject some of these

projects are research oriented and not completely prescribed. Others

are of hands-on type and also not completely prescribed, some of the

details need to be determined by the instructor. The exercises

inserted throughout the book and the projects at the end can be used

as an assessment tool.