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

is divided by . A forms the cipher text , where is the remainder when is divided by . Let be the multiplicative inverse of modulo , so that leaves a remainder of 1 upon division by . Then, to decipher, B raises to the power and gets the remainder of upon division by . Let be the additive inverse of modulo . Then, to decipher, B adds to and gets the remainder of upon division by : this yields .

3.4 Public Key Versus Symmetric Key

The algorithms seem remarkably similar. However, by contrasting them we will glean the fundamental insights into the difference between public key and symmetric cryptography.

      We note the following:

      1 The integer is kept secret in the symmetric case and is known only to A and B. In the RSA case, is public knowledge.

      2 The choice of the integer in the symmetric case is unrestricted. In the RSA case, must be the product of two large unequal primes and furthermore, these primes are secret and are known only to B. The integer constitutes the private key of B in the RSA case.

      3 In this particular case, the symmetric algorithm provides perfect secrecy. This means that knowledge of the cipher text provides no clue as to the message since any message will fit with the given cipher text. The cipher text does not narrow down the possibilities for the message in any way. Thus, the only way for an intruder to get the message is by guessing; the eavesdropper Eve can try to guess the message but will have no way of verifying the guess is correct. For example, when and we take any cipher text, , say (as above), then any message can be made to fit this cipher text. For example, the message 14 can be made to fit this cipher text by choosing .

      Contrast this with the RSA situation. Only one message will fit with a given cipher text. If an intruder tries to guess the message, she can verify immediately whether or not the guess is correct. In particular, she can do this by enciphering the guess. Moreover, given sufficient time and computing resources an adversary is certain to get the message. (However, the adversary may need a very long time!)

      Thus, the RSA algorithm affords only computational security as do all other public key algorithms. This means that the security comes from the unproven mathematical assumption that no deciphering algorithm can be computed in a reasonable amount of time (technically, in polynomial time) to obtain the message.

      However, not all symmetric algorithms enjoy perfect secrecy. For this to happen, Shannon proved that roughly, “the key must be as long as the message.” Symmetric algorithms like AES, where the key is much shorter than the message, are sometimes “insecure.” The relative security offered by such a scheme depends on the length and the nature of the message, for example, a text message encoded in binary. Generally speaking, the knowledge of the cipher text will at least narrow down the possibilities for the message. We discuss this later in this chapter.

One of the main problems with RSA and public key systems is that somebody may come up with a fast method of deciphering or factoring. Also, as time progresses, the computational power that is available for an adversary to attempt an attack on an enciphering protocol increases, sometimes very quickly. (See Section 1.7 for further discussion.)

      Thus, one needs longer and longer keys for public key systems to withstand computational attack. Nowadays, the industry uses mainly symmetric cryptography. The secret key needed for this can be supplied by a central server (as is the case with the Kerberos system) or by a public key methodology such as RSA, where the message is the key to be used for the symmetric key session, i.e. the session key. The RSA algorithm is also widely used as the base for secure e‐mail applications, such as PGP, and Internet security protocols such as TLS.

      As mentioned, the computational power that an adversary Eve has at her disposal is increasing at a fast rate. Because of this one needs to work with bigger and bigger primes , to try to ensure that factoring cannot be done quickly. Back in 1998, one needed to have , at least 154 digits (512 bits) each. However, that no longer provides adequate protection.

      Table 2 of [Bar16, p. 53] gives estimated strengths for approved algorithms and key lengths. The security strength assigns a value to the amount of work that is required to break a cryptographic system. The higher the value, the more secure the system. NIST provides a recommendation for minimum security strengths and minimum numbers of bits for the various encryption algorithms that they recommend. The minimum number of bits needed for adequate protection for RSA is a keysize of 2048 bits (see [Bar16, p. 53, Table 2] or [BD15, p. 12, Table 2]). Therefore, and