Cryptography, Information Theory, and Error-Correction. Aiden A. Bruen

is a whole number , then the remainder of upon division by must be (see Chapter 19).

      The recipient Bob, however, can calculate immediately from a formula involving his private key consisting of a “decryption index” along with two prime numbers , . The reason is that is the product of and . Bob knows and . Anybody else, even knowing , cannot in general determine what the factors , are in a reasonable amount of time.

      Eve can try guessing the message without knowing by guessing . Alternatively, Eve can try guessing and from which she can calculate . In other words, Eve can try to guess the private key and then determine the message.

      We detail some potential weaknesses with public key algorithms such as RSA. However, this algorithm is still a central public key algorithm. Its security, when carefully implemented, seems to still be strong after many years of constant use.

A fact in cryptography is that in a brute‐force attack on a key‐space (one where we try all possible keys), the correct key is likely to be found after trying about half the total number of keys. In this chapter, we provide a short simple proof of this fact.

      The encryption exponent mentioned above must be chosen to have no factors in common with and no factors in common with . The reason for assuming this is so that exists. Another reason is that this condition must be satisfied in order that two different messages get two different encryptions. This comes up in Problem 3.1. We mention also that, for a given , the decryption index need not be unique! We provide several examples. This is important because some attacks on RSA are possible if is small; we refer to Chapter 7. So if is not unique, this makes it more difficult to guard against this attack.

      What we mean by “not unique” is that there may be more than one value of such that the remainder of , on division by , is . The reason for nonuniqueness is that, instead of working with , we can work with any number that is divisible by and , as explained in the algorithm description and in Chapter 19. It is often possible to find so that the calculations are simplified, and we get a shortcut even if the resulting is the same.

      We present new insights on public key and symmetric encryption.

      

3.1 The Basic Idea of Cryptography

      Cryptography is an old subject dating back at least as far as 1500 BCE. A technique developed by Porta associated also with Vigenère in the Middle Ages is close to the cutting edge of part of modern cryptography. Additionally, cryptography is closely connected to information theory and error‐correction, with many fundamental ideas going back to Claude Shannon. Further details about Shannon and the history of cryptography are provided in Chapter 1.

      Cryptography is the art of keeping messages secret. Imagine that A, B are two entities who wish to communicate in secret. Assume A wants to send a secret message to B.

The procedure is as follows (Figure 3.1). First, A scrambles the message using a cryptographic key. The process of scrambling the message is called encryption: alternatively, A enciphers the message.

Figure 3.1 General encryption.

The encryption or enciphering scrambles the message , that is, the plain text, into unintelligible output called the cipher text. Next, the sender A transmits in the open (publicly) the cipher text to the receiver B. When B receives the cipher text, B descrambles or deciphers the cipher text using a key that may or may not be the same