 ## 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.