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

Чтение книги онлайн.

СКАЧАТЬ 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 should have at least 308 digits (1024 bits) each. Of course, with longer keys, transmission errors become more and more prevalent.

      Several additional remarks are in order.

      1 P. Shor has proved that factoring numbers is computationally feasible with a quantum computer. Thus, if quantum computers ever become a reality, RSA will no longer be viable: it will be completely insecure.

      2 The problem of transmission errors has to be addressed given that primes , should be at least 308 digits (1024 bits) each, ensuring a modulus of 617 digits (2048 bits) for long‐term security.

      3 Despite the recent mathematical results of Agrawal et al., [AKS04] which shows that one can quickly test for primality³ of a given number, one still has to generate large primes , of roughly the same size which are suitable for RSA use. In particular, they must be resistant to factorization algorithms, one of which is discussed later in the book.

      4 For frequent RSA communications, one also needs a fast algorithm for ensuring that has no factors in common with and .

      5 The RSA algorithm is slow relative to some comparable symmetric‐key algorithms.

      6 The security of RSA is in jeopardy without extensive “preprocessing” of plain text message units before encryption (see Mollin [Mol02]).

      7 Other attacks on RSA include timing attacks and “man‐in‐the‐middle” attacks. These are discussed in Chapter 7.

      Apart from guaranteeing the secrecy of the message from A to B (or B to A), other fundamental issues in cryptography are as follows:

      1 Authentication. Roughly, how can B be sure that the message came from A?

      2 Message integrity. How can B be sure that the message has not been altered?

      3 Digital СКАЧАТЬ