Page 315 - Discrete Mathematics and Its Applications

294 4 / Number Theory and Cryptography
4.6
Cryptography
Introduction
Number theory plays a key role in cryptography, the subject of transforming information so that
it cannot be easily recovered without special knowledge. Number theory is the basis of many
classical ciphers, first used thousands of years ago, and used extensively until the 20th century.
These ciphers encrypt messages by changing each letter to a different letter, or each block of
letters to a different block of letters. We will discuss some classical ciphers, including shift
ciphers, which replace each letter by the letter a fixed number of positions later in the alphabet,
wrapping around to the beginning of the alphabet when necessary. The classical ciphers we will
discuss are examples of private key ciphers where knowing how to encrypt allows someone to
also decrypt messages. With a private key cipher, two parties who wish to communicate in secret
must share a secret key.The classical ciphers we will discuss are also vulnerable to cryptanalysis,
which seeks to recover encrypted information without access to the secret information used to
encrypt the message. We will show how to cryptanalyze messages sent using shift ciphers.
Number theory is also important in public key cryptography, a type of cryptography invented
in the 1970s. In public key cryptography, knowing how to encrypt does not also tell someone
how to decrypt. The most widely used public key system, called the RSA cryptosystem, encrypts
messages using modular exponentiation, where the modulus is the product of two large primes.
Knowing how to encrypt requires that someone know the modulus and an exponent. (It does
not require that the two prime factors of the modulus be known.) As far as it is known, knowing
how to decrypt requires someone to know how to invert the encryption function, which can only
be done in a practical amount of time when someone knows these two large prime factors. In
this chapter we will explain how the RSA cryptosystem works, including how to encrypt and
decrypt messages.
The subject of cryptography also includes the subject of cryptographic protocols, which are
exchanges of messages carried out by two or more parties to achieve a specific security goal. We
will discuss two important protocols in this chapter. One allows two people to share a common
secret key. The other can be used to send signed messages so that a recipient can be sure that
they were sent by the purported sender.
Classical Cryptography
One of the earliest known uses of cryptography was by Julius Caesar. He made messages secret
by shifting each letter three letters forward in the alphabet (sending the last three letters of the
alphabet to the first three). For instance, using this scheme the letter B is sent to E and the letter
X is sent toA. This is an example of encryption, that is, the process of making a message secret.
To express Caesar’s encryption process mathematically, first replace each letter by an ele-
ment of Z 26 , that is, an integer from 0 to 25 equal to one less than its position in the alphabet. For
example, replace A by 0, K by 10, and Z by 25. Caesar’s encryption method can be represented
by the function f that assigns to the nonnegative integer p, p ≤ 25, the integer f(p) in the set
{0, 1, 2,..., 25} with
f(p) = (p + 3) mod 26.
In the encrypted version of the message, the letter represented by p is replaced with the letter
represented by (p + 3) mod 26.