Notes on Cryptography - Edward Bosworth



Notes on Cryptography

We now present an introduction to cryptography, which appears to be the basis for much of modern information assurance. We begin by examining different variants of substitution ciphers and then discuss a number of popular algorithms that are a bit more sophisticated.

We begin with a number of definitions

A cipher is a system whereby each letter or symbol in a message is translated individually into another letter. The process of applying a cipher is called enciphering. The process of retrieving the clear text from an enciphered message is called deciphering.

A code is a system whereby each word in a message is translated to a set of letters (that is often shorter than the letter count in the word). The process of translating a word to code is called encoding. The process of retrieving a word from its code is called decoding. It should be noted that the primary purpose of codes is often something other than secrecy; many commercial codes were developed in the days of telegraphy to reduce the per-letter charge of transmitting an order.

In earlier days, there was a process of first encoding a message and then enciphering the code. This process, called super-enciphering, may or may not be in current use. One imaginary example will illustrate. Suppose we want to apply both code and ciphers to the message “MIDWAY IS OUT OF WATER”, by first applying the code “AF” for the name “MIDWAY”. We then encipher the message “AF IS OUT OF WATER”, say to something like “DI LV RXW RI ZDWHU” or better “DILVRXWRIZDWHU”.

Encryption is the term applied to either enciphering or encoding, while decryption is the term applied to the reverse process, be it either deciphering or decoding. The original form of a message is called a plaintext and the encrypted form is called ciphertext.

Cryptanalysis is the process of retrieving the meaning of intercepted ciphertext. Here we make one point that should be the major emphasis of this chapter – that the study of cryptography is really the study of cryptanalytic methods. One cannot devise encryption methods that are useable unless he or she has a good background in breaking encryption. The history of codes and ciphers is littered with a number of “unbreakable” ciphers that were easily defeated. For example, the monoalphabetic substitution ciphers appear unbreakable, having 26! ( 4.033(1026 possible keys until one realizes that frequency analysis will easily defeat them. As we shall see a bit later, complexity of the algorithm does not often equate to difficulty in cracking the cipher. Most of us should use commercially available ciphers.

There are two simple forms of enciphering: substitution ciphers and transposition ciphers. We shall view substitution ciphers as permutations in which each letter is replaced by another letter. The Caesar cipher is a specific permutation cipher in which the permutation is specified by a given formula. More sophisticated substitution ciphers can be viewed as application of a sequence of different permutations to the plaintext.

Substitution (permutation) ciphers

A simple substitution cipher can be viewed as a permutation of the letters. Consider the Caesar cipher in which each letter is replaced by the letter three places after it. The following table can be used to specify the cipher.

Plain: A B C D E F G H I J K L M N O P Q R S T U V W X Y Z

Cipher: D E F G H I J K L M N O P Q R S T U V W X Y Z A B C

If we use the notation of a permutation to specify the above cipher, we need give only the second row as the first row is assumed. As a permutation, the above cipher is defined by

(D,E,F,G,H,I,J,K,L,M,N,O,P,Q,R,S,T,U,V,W,X,Y,Z,A,B,C).

There is an important statement to be made about these ciphers. Mathematically, we say that the composition of two permutations is another permutation. To illustrate what is meant by that statement, we consider three substitution ciphers as applied to a seven-character alphabet with letters in the set {A, B, C, D, E, F, G}. We consider three permutations

Plaintext (A, B, C, D, E, F, G)

F1 = (C, D, E, F, G, A, B) - offset by 2

F2 = (E, A, G, C, D, B, F)

F3 = (G, D, B, C, F, E, A)

Suppose that we apply multiple encryptions in an attempt to gain security. Will this be successful? To consider this strategy, suppose that we encipher first with F1 and then with F2, so that the function may be viewed as G1(X) = F2(F1(X)) for X being the character.

G1(‘A’) = F2(F1(‘A’)) = F2(‘C’) = ‘G’

G1(‘B’) = F2(F1(‘B’)) = F2(‘D’) = ‘C’

G1(‘C’) = F2(F1(‘C’)) = F2(‘E’) = ‘D’

G1(‘D’) = F2(F1(‘D’)) = F2(‘F’) = ‘B’

G1(‘E’) = F2(F1(‘E’)) = F2(‘G’) = ‘F’

G1(‘F’) = F2(F1(‘G’)) = F2(‘A’) = ‘E’

G1(‘G’) = F2(F1(‘G’)) = F2(‘B’) = ‘A’

Note that G1 may be represented as another permutation.

G1 = (G, C, D, B, F, E, A)

One should note that this single permutation offers no more security than either of the permutations F1 or F2. To make this point more clearly, consider G2(X) = F3(F2[F1(X)]). We see that G2(‘A’) = F3(‘G’) = ‘A’, G2(‘B’) = F3(‘C’) = ‘B’, G2(‘C’) = F3(‘D’) = ‘C’, and in general G2(X) = F3(F2[F1(X)]) = X for all letters X. Thus, we have made the permutation so complicated that we accidentally undid all of the ciphering and have produced the identity permutation. The rule is that the composition of two or more substitution ciphers is no better than a given substitution cipher and may be considerably worse.

Does Multiple Encryption Offer Advantages?

The student who has read this chapter will now have seen two examples of encryption in which multiple encryption offers different outcomes. There is Triple DES, which seems to be “better” than Single DES in that it is the equivalent of Single DES with a key of twice the length. We have examines the triple substitution cipher and shown it to be no better than a single substitution and possibly much worse. This should show that the question of multiple encryptions has no general answer. It always takes longer and the results vary.

There are two goals for this discussion.

1) The student should realize that complexity does not always equate to security.

2) The student should realize that what works for one algorithm (DES) may

completely fail for another algorithm (substitution).

More On Permutation Ciphers

As noted above, these ciphers can be viewed either as a permutation of the set of letters to be enciphered or as a simple function that assigns to each letter in the alphabet another letter in the alphabet; mathematically F: ( ( (. Mathematically speaking, we require that the function has an inverse, so that we can decrypt the ciphertext. To be specific about an inverse function, consider the permutation G1 defined above.

G1 = (G, C, D, B, F, E, A)

The implication of this notation is that the alphabet is ( = (A, B, C, D, E, F, G) and that the function G1 maps the letters of the alphabet as follows.

G1(‘A’) = ‘G’ G1(‘D’) = ‘B’ G1(‘G’) = ‘A’

G1(‘B’) = ‘C’ G1(‘F’) = ‘E’ G1(‘E’) = ‘F’

G1(‘C’) = ‘D’

The requirement that we be able to determine the unique plaintext that gave rise to the ciphertext implies that the encryption function be invertible. We show that G1 is invertible by displaying its inverse.

G1-1(‘A’) = ‘G’ G1-1(‘D’) = ‘C’ G1-1(‘G’) = ‘A’

G1-1(‘B’) = ‘D’ G1-1(‘F’) = ‘E’ G1-1(‘E’) = ‘F’

G1-1(‘C’) = ‘B’

Given the inverse function, we can ask questions such as “What letter encrypted to ‘E”?” The answer is the letter ‘F’. In case the inverse appears somewhat similar to the original function, one should note that it is quite possible to create functions (permutations) that are inverses of themselves. The following permutation is its own inverse

H = (B, A, D, C, F, E, G)

Cryptanalysis of Permutation Ciphers

We now begin our discussion on cryptanalysis of substitution ciphers, including the Caesar cipher. We first note the obvious (and very inefficient) method that will always crack a substitution cipher – the brute force method of guessing all of the keys until one is found that produces good results. When this method can be automated, it should not be totally disregarded; indeed this is the way many of the German enigma messages were cracked.

For an alphabet with 26 characters, there are 26! ( 4.033(1026 possible keys. Were one to insist that no method, other than brute force, existed to crack this cipher, he or she could conclude that the substitution cipher is secure as it would take a prohibitive time to guess the key without some outside assistance (such as bribing a cipher clerk).

But we all know that the simple substitution cipher can be quickly cracked using frequency analysis of letters, digrams, and trigrams as found in the base language. The inventor of a substitution cipher might not notice such an attack but a cryptanalyst would; this observation is the basis for my statement that one must study cryptanalysis in order to understand ciphers.

Multiple Permutations and the Vigenere Tableau

A way to make ciphers more secure is to defeat the frequency analysis tools that will crack the simple substitutions. Many of these can be viewed as a sequence of permutations applied one at a time – the first permutation is applied to the first letter, the second permutation is applied to the second letter, etc. until the first is used again. The tool of choice for this is the Vigenere tableau, which is a table with 26 columns of 26 rows each. The key to the cipher indicates which row or column is used to encipher or decipher as appropriate. There are a number of methods that can crack this cipher for a key of finite length, but they are more complex than the simple frequency counts used to attack the simple substitution cipher.

One general rule is that the longer the ciphertext, the easier the task of cryptanalysis. For a sufficiently long text enciphered under the Vigenere tableau, one can make assumptions about the length of the key and observe the frequency distributions. When one has the correct key length, the frequency distribution of the cipher letters will show. For example, suppose that the key has three characters. We then write the cipher letters in three columns and produce three sets of statistics, one for each of the columns. The use of session keys is a response to the general rule. A session key is a key generated at the time an on-line session begins and used only for that session, thus limiting the amount of ciphertext produced with that key. Almost any short ciphertext can resist cryptanalysis.

There are a number of basic ciphers built upon the Vigenere tableau, such as the book cipher. Many of these appear clever, but given enough ciphertext they can be cracked.

Transposition Ciphers

Not all ciphers require the use of a key. The columnar transposition method illustrates such an algorithm. One imagines the text as rows in a rectangular array and then reads the letters by columns. Consider the message “THIS IS A GOOD ENCRYPTION ALGORITHM”. The first thing to do is to remove all spaces – it is better not to give any clues to the word length. Thus we encrypt the message “THISISAGOODENCRYPTIONALGORITHM”. The only thing to do now is to select the number of columns. I shall opt for 7 columns.

|T |H |I |S |I |S |A |

|G |O |O |D |E |N |C |

|R |Y |P |T |I |O |N |

|A |L |G |O |R |I |T |

|H |M |A |B |C |Y |Z |

The first thing to note is that the message is 30 characters long. For this reason, I must pad it with five extra characters in order to fill five rows of seven characters each. The suggestion that infrequent letters be used to pad the columns might give some clue to their size.

The ciphertext for this method is “TGRAHHOYLMIOPGASDTOBIEIRCSNOIYACNTZ”. There are a number of problems with this method, among them the ease of guessing the row size. We shall see the use of this technique as a part of other ciphers.

Product Ciphers

Most modern ciphers are product ciphers in that they are combination of substitution and transposition ciphers. As is the case with all tools, these combinations must be used well or the resulting cipher may be weak. I shall quote from page 55 of the text.

Just because you apply two ciphers does not necessarily mean the result is any stronger than, or even as strong as, either individual cipher.

Properties of Good Encryption Methods

The first principle of good encryption is that neither the key nor the algorithm by itself will suffice to decipher the ciphertext. The requirement that both key and algorithm be known means that the loss of either will not greatly facilitate cryptanalysis. Recall that most methods of cryptanalysis postulate the algorithm and try to derive the key.

Another goal is that the loss of a fragment of ciphertext and its known plaintext will not facilitate the cryptanalysis of other fragments of ciphertext. There are many tricks based on getting the enemy to transmit a known document as an enciphered text to get the material for comparison. Having such material would allow immediate solution of all future substitution ciphers transmitted and be of great help in many other ciphers.

This attack on ciphers suggests one of the most important controls on the use of ciphers. This is that one should always paraphrase known text before enciphering and transmitting it. This protocol should be followed even for the more sophisticated ciphers in which the possession of a considerable length of plaintext with associated ciphertext will not lead to the successful decryption of any new ciphertext.

Two qualities of a good cipher are confusion and diffusion. Ciphers designed with these two principles in mind are seen to be more resistant to cryptanalysis. The principle of confusion states that an interceptor “should not be able to predict what will happen to the ciphertext by changing one character in the plaintext”. The principle of diffusion means that the information from one plaintext character be spread over the entire ciphertext message. This last requirement is not really possible in most algorithms done by hand but is easily done by computer. Remember ASCII code.

As an example, consider the plaintext “ACE”. Encoded with 8-bit ASCII, this becomes the 24-bit string 0100 0001 0100 0011 0100 0101, where we have highlighted the bits for the C. Suppose that we do a 5-column transposition on this. The results are

|0 |1 |0 |0 |0 |

|0 |0 |1 |0 |1 |

|0 |0 |0 |0 |1 |

|1 |0 |1 |0 |0 |

|0 |1 |0 |1 |1 |

We read this out as 00010 10001 01010 00001 01101 and the image of the letter ‘C’ has been diffused throughout the message.

Properties of Commercial-Grade Cryptosystems

As stated above, the history of cryptography is littered with many failed cryptosystems. One may ask how to select a cryptosystem that is appropriate to his or her application. There are a few rules that can apply. For most users the first rule is “Don’t roll your own”; thus do not try to invent a cryptosystem as you are likely to invent a weak one. The characteristics of a good-quality cryptosystem are the following.

1) It is based on sound mathematics. For example, the mathematical basis of the Caesar

cipher is correct but not sound as it is much too simple.

2) It has been extensively analyzed by competent experts and not found to have any

known flaw. Review of an algorithm by outside experts will either expose a flaw or

increase the confidence that no flaw exists.

3) It has stood the “test of time”. This is related to the second point. Although extended

analysis cannot guarantee the lack of flaws, one suspects that the more challenges the

algorithm has survived, the more likely it is to survive future challenges.

We shall discuss three commonly used encryption algorithms: DES, AES, and RSA.

The DES (Data Encryption Standard)

The DES (more properly DEA for Data Encryption Algorithm) is a system developed under the sponsorship of the U.S. government for transmission of sensitive, but unclassified, information. Because the U.S. military organizations did not want to reveal any of their methods for transmitting classified information, the project was initiated by the NBS (National Bureau of Standards, now called NIST or National Institute of Standards and Technology) The DES is a product cipher incorporating both substitution and transposition.

The original DES, now called “Single DES” involved the use of a 56-bit key for encryption. The length of the key has always been a source of concern and becomes even more so as it is now computationally feasible to crack the encryption by brute-force testing of all possible keys. There are 256 possible keys for Single DES. As an exercise we estimate that value.

Since the base-10 logarithm of 2 is 0.30103, we calculate 256 ( (100.30103)56 = 1016.858, and conclude that 256 ( X(1016, where X is the antilog of 0.858. We know that the base-10 logarithm of 3 is 0.47712, so conclude that the log of 6 is (0.30103 + 0.47712) = 0.787815, from which we can conclude that 256 > 6(1016.

We also know that log(8) = log(23) = 3(log(2) = 0.90309, thus 6(1016 < 256 < 8(1016. In 1998 researchers build a special DES-cracker that could find a DES key in approximately four days. Since one day is 86,400 seconds, this involved calculating about 1.5(1014 keys per second – a feat that must have involved quite a few CPU’s.

Does this above success imply that Single DES is insecure? The answer depends on one’s definition of the word “secure”. The most common usage is to define an algorithm to be secure if the only ways known to break it involve the use of brute-force generation of all possible keys. Thus substitution ciphers are not secure in that there are known attacks that require substantially less work. Under this criterion, the DES is secure. The algorithm has, however, been overtaken by raw computing power, so that the NIST has stated publicly that “Single DES will be permitted for legacy systems only”.

One immediate answer to this problem is called Triple DES. This process uses two keys and can be represented by C = F( G-1[ F(M) ] ), where

M is the plaintext message,

C is the ciphertext produced,

F is the encryption with the first key, denoted E(K1, M) in the textbook, and

G-1 is the decryption with the second key, denoted D(K2, C) in the textbook.

The author of these notes prefers to use a named function to denote encryption and its inverse to denote decryption as decryption undoes what encryption does.

The Advanced Encryption Standard (AES)

The AES is the result of a competition sponsored by the NIST (formerly the NBS). The algorithm for the AES was submitted in 1997 and approved in 2001. It is a block cipher, breaking the plaintext into 128-bit blocks and having a key length of 128, 192, or 256 bits.

At this point, there is not much more to be said about the AES. Given that the AES is known to be based on sound mathematics and have survived four years of intense scrutiny by experts, one can expect that it is a good encryption algorithm. One can certainly assert that it remains computationally infeasible to compute all 2256 ( 7(1076 possible keys.

Public Key Encryption

Public key encryption, an example of an asymmetric encryption system, is a theoretical construct with two known implementations – the RSA and Merkle-Hellman algorithms. Each of these cryptosystems uses two keys – one that is public (and should be widely published) and another that is private.

The book denotes the algorithms again using the E and D notation, with

C = E(KPUB, M) denoting encryption with the public key, and

M = D(KPRIV, C) denoting decryption with the private key.

Using my notation, I would say

C = F(M) F denotes encryption with the public key

M = F-1(C) F-1 denotes decryption with the private key.

We shall immediately focus on the more common implementation of public key encryption.

The RSA (Rivest-Shamir-Adelman) Cryptosystem

The RSA is the best-know public key cryptosystem, with the only known flaws being due to flaws in its use. The statement in our textbook best states the consensus on its security.

RSA has been the subject of extensive cryptanalysis, and no serious flaws have yet been found. Although the amount of analysis is no guarantee of a method’s security, our confidence in the method grows as time passes without the discovery of a flaw.

It should be noted that the security of this algorithm depends on the fact that factoring large (more than 200 digits) into two prime factors is a very hard problem. Should an easy way be found to factor integers, the RSA would become a weak cryptosystem. Needless to say, no professional mathematician expects that the problem of factoring integers is an easy one.

The RSA is based on a pair of keys, one public and one private. At one level, the two keys are equivalent in that either can be the public key and either can be the private key. One picks one of the pair arbitrarily and, keeping it private, publishes the other.

The RSA is implemented using some results of number theory. The following description of the cryptosystem is taken from my paper on Public Key Encryption. In the RSA public key cryptosystem, the user creates a public and private key pair as follows.

1. Select two large prime numbers p and q, with p ≠ q. The prime numbers should be

chosen by some random process, so they cannot be guessed. The strength of the

encryption depends on the size of the numbers, so that the primes should each have

at least 150 digits. 512 bit numbers are good candidates. Note that

2512 ( 10154.13 ( 1.34•10154, a 155 digit number.

2. Compute n = p•q.

3. Select a small odd integer e that is relatively prime to ((n), the Euler phi function. It

can be shown that ((n) = (p – 1)•(q – 1) for n = p•q, as both p and q are prime.

4. Compute the integer d as the multiplicative inverse of e, modulo ((n); thus

e•d ( 1 mod ((n). For e and ((n) as defined, it can be proven that the multiplicative

inverse exists and is uniquely defined.

5. Publish the pair P = (e, n) as the RSA public key.

6. Keep secret the pair S = (d, n) as the RSA private key.

For use of the cryptosystem, a string of ASCII characters is considered to be a large integer represented by the bit pattern. Both the encryption and decryption functions involve taking powers of these integers, modulo n = p•q. Let M be the integer representing the plain-text message to be encrypted and C be the integer representing the encrypted message.

Then C = P(M) = Me (mod n)

M = S(C) = Cd (mod n)

One should expect from the above description that execution of the RSA algorithm involves a lot of computation, thus making it much slower than symmetric encryption. For that reason, a hybrid system is often used.

Mixed Usage and Session Keys

The hybrid system used is to use the RSA cryptosystem to transmit a session key. Here is a typical scenario that is repeatedly seen in electronic commerce.

Suppose George logs onto the website of Frank’s Fruit Company and wants to purchase a bushel of red delicious apples. George wants to use his credit card number, but wants to insure that it is sent securely so that no eavesdropper could copy it and use it for other purposes. He also wants other details of the order to be secure from other parties.

The scenario is as follows:

1) Frank sends the public key F (really just the public key pair) to George.

2) George’s computer computes K, a large random number, for use as the session

key, encrypts C = F(K), and sends C to Frank,

3) The transaction between Frank and George takes place using symmetric encryption

with the private key K used for only that session.

Theory of Public Key Encryption

Private key encryption usually involved the application of a key to transform the clear text message into a cipher text for transmission to the recipient who then uses the same key to decrypt the message. Any eavesdropper possessing the key would be able to read all messages without difficulty; for this reason the key must be kept private.

One major difficulty with private key encryption is key distribution. One must have a secure channel, distinct from the messages themselves, for distributing the keys to all users who have need to read the messages. One method commonly used is hand transmission via trusted couriers. There are a number of other difficulties, including the impossibility of “digital signatures” – basically certificates of the authenticity of the message. If a number of users have the secret key, then any one of them might have sent it.

In mathematical terms, the important feature of private key encryption is that given the encrypting function F it is straightforward to obtain the decrypting function F-1.

The key development in public key encryption was the discovery of a class of mathematical functions, often called “trap door functions” for which it is not computationally feasible to derive the inverse function F-1 given only the function F.

In a public key cryptosystem, each user has two keys – a public key that is widely disseminated and a secret key that is closely guarded. In the RSA cryptosystem, each key comprises a pair of integers. One integer, the product of two large prime numbers, is common to each key. The public key is often denoted (p•q, e) and the secret key (p•q, d), where p•q is the product of two large prime numbers p and q.

The reader should note that public key encryption is not identical to RSA; RSA is just one (and at present, the only) implementation of public key encryption. The remarks in this section, except where noted, apply to all possible implementations of the public key system.

Consider two users Frank and George. Frank has public key represented by function F and secret key represented by the inverse function F-1. George’s keys are represented by the pair of functions G and G-1 respectively. Each of the two users publishes the public key: Frank publishes F and George publishes G. These are the functions used to encrypt messages sent to Frank and George, respectively. Thus, if George wants to send an encrypted message M to Frank, he computes C = F(M) and sends this to Frank. The presumption is that only Frank can compute M = F-1(C), because Frank has kept the secret key secure.

Should Frank, or anyone else, want to send an encrypted message to George, he computes

C = G(M) on the assumption that only George can apply G-1 to obtain the original message.

We now consider an unusual idea: the use of the secret key to encrypt a message. Suppose Frank calculates X = F-1(M). Note that the message is not secure because any user having Frank’s public key can compute M = F(X); it is assumed that the public key is widely known. However there is another assumption here. If a user, other than Frank, computes M = F(X) for a given encrypted message X and produces a coherent text, the assumption is that it could have been produced only by Frank; thus authenticating the message.

In this scenario we see one of the strengths of the public key cryptosystem. Suppose Frank wants to send a message that only George can read and that is authenticated as having been written by Frank. He computes C = G(F-1(M)) and George computes M = G-1(F(C)); the message is secure and authenticated. The actual practice differs somewhat from this example, but the important features are the same.

The security of a public key cryptosystem depends on the computational infeasibility of determining the decrypting function F-1 given only the encrypting function F. Note that infeasibility is not the same as impossibility; for example, it would probably be satisfactory if it were possible to compute F-1, but only given 1000 years of computing time. Most users would be happy with a key that resisted cracking for only 100 years.

The security of the RSA cryptosystem depends on the infeasibility of computing the factors of a large (300 digits or more) integer which is the product of two large prime numbers; thus given the number p•q it is not presently feasible to determine either p or q from the produce alone if both p and q are large enough (150 digits). Obviously if it were possible to factor very large composite integers efficiently, the RSA cryptosystem would not be secure. It is important to note, however, that even assuming the infeasibility of factoring very large integers does not guarantee the security of RSA as it may be vulnerable to other attacks. All that can be said is that RSA has withstood intense scrutiny and that no other attack has been found. While not a proof of security, this is a fairly good certificate.

................
................

In order to avoid copyright disputes, this page is only a partial summary.

Google Online Preview   Download