Page 319 - Discrete Mathematics and Its Applications

298 4 / Number Theory and Cryptography
EXAMPLE 7
We now illustrate the use of the definition of a cryptosystem.
Describe the family of shift ciphers as a cryptosytem.
Solution: To encrypt a string of English letters with a shift cipher, we first translate each letter
to an integer between 0 and 25, that is, to an element of Z 26 . We then shift each of these integers
by a fixed integer modulo 26, and finally, we translate the integers back to letters. To apply the
defintion of a cryptosystem to shift ciphers, we assume that our messages are already integers,
that is, elements of Z 26 . That is, we assume that the translation between letters and integers
is outside of the cryptosystem. Consequently, both the set of plaintext strings P and the set of
ciphertext stringsC are the set of strings of elements of Z 26 .The set of keysK is the set of possible
shifts, so K = Z 26 . The set E consists of functions of the form E k (p) = (p + k) mod 26, and
the set D of decryption functions is the same as the set of encrypting functions where D k (p) =
(p − k) mod 26. ▲
The concept of a cryptosystem is useful in the discussion of additional families of ciphers
and is used extensively in cryptography.
Public Key Cryptography
All classical ciphers, including shift ciphers and affine ciphers, are examples of private key
cryptosystems. In a private key cryptosystem, once you know an encryption key, you can
quickly find the decryption key. So, knowing how to encrypt messages using a particular key
allows you to decrypt messages that were encrypted using this key. For example, when a shift
cipher is used with encryption key k, the plaintext integer p is sent to
c = (p + k) mod 26.
Decryption is carried out by shifting by −k; that is,
p = (c − k) mod 26.
So knowing how to encrypt with a shift cipher also tells you how to decrypt.
When a private key cryptosystem is used, two parties who wish to communicate in secret
must share a secret key. Because anyone who knows this key can both encrypt and decrypt
messages, two people who want to communicate securely need to securely exchange this key.
(We will introduce a method for doing this later in this section.) The shift cipher and affine cipher
cryptosystems are private key cryptosystems.They are quite simple and are extremely vulnerable
to cryptanalysis. However, the same is not true of many modern private key cryptosystems. In
particular, the current US government standard for private key cryptography, the Advanced
Encryption Standard (AES), is extremely complex and is considered to be highly resistant to
cryptanalysis. (See [St06] for details on AES and other modern private key cryptosystems.)
AES is widely used in government and commercial communications. However, it still shares
the property that for secure communications keys be shared. Furthermore, for extra security, a
new key is used for each communication session between two parties, which requires a method
for generating keys and securely sharing them.
To avoid the need for keys to be shared by every pair of parties that wish to communicate
securely, in the 1970s cryptologists introduced the concept of public key cryptosystems. When
such cryptosystems are used, knowing how to send an encrypted message does not help decrypt
messages. In such a system, everyone can have a publicly known encryption key. Only the
decryption keys are kept secret, and only the intended recipient of a message can decrypt it,
because, as far as it is currently known, knowledge of the encryption key does not let someone
recover the plaintext message without an extraordinary amount of work (such as billions of
years of computer time).