THE FUTURE

Although Moore’s Law may cease to hold at some point in the near future it is still an inevitability that the power of computer processors will increase with each passing year.

Within a matter of a few decades computers many more times powerful than those available today will be in use. These more powerful processors will allow more complicated encryption algorithms to be run within a reasonable time span. This will inevitably lead to the steadily increasing power of encryption systems. The same computing power which makes these computers useful to cryptographers will make them useful to cryptanalysts. The computer shown in Figure 10 is one in use at the Government Communications Headquarters in Cheltenham, with computers hundreds of times more powerful it will become plausible to decrypt many ciphers by a simple brute force attack where it had not been so before. This will probably spell the end of existing cryptosystems, however, other, more complicated ones will be developed in their place. We have already seen this happen. In November 1998 the US Government discontinued its usage of the DES system because what was considered secure upon the algorithms conception is no longer so. A variant of DES called triple-DES will be used until AES (Advanced Encryption System) is ready.

It also seems likely that better factoring algorithms will be developed in the future. Coupled with increasing computing power this may mean the end of RSA, or simply that people will be using larger and larger primes to stay ahead of the cryptanalysts.

There is an inherent danger in attempting to make any definite statements about the future, more often than not they are hilariously inaccurate. However, in my opinion, I believe that the balance between cryptographer and cryptanalyst will be roughly maintained although I think it is likely that the actual volume of encrypted traffic will increase due to individuals using cryptography to protect their privacy. This is of course the great fear of law enforcement agencies who have, for many years, enjoyed the ability to tap phone lines. Attempts to set-up some sort of escrow key system such as what the United States government attempted with the clipper clip may be successful, or they may not. Whatever happens, however, cryptology promises to remain an area of interesting developments for a long time yet.

CRYPTANALYSIS

It is beyond the scope of this essay to deal with all types of cryptanalysis so I will give a brief overview and an example of where cryptanalysis has been successful. Unlike cryptography which is a clearly defined science, cryptanalysis is as much an art as it is a science. Success in cryptanalysising a cipher is a flash of inspiration almost as often as it the result of using crytanalysis techniques alone.

Types of Cryptanalysis

There are several distinct types of cryptanalytic attack. The type used depends on the type of cipher and how much information the cryptanalyst has.

Types Of Cryptanalytic Attacks

A standard cryptanalytic attack is to determine the key which maps a known plaintext to a known ciphertext. This plaintext can be known because it is standard or because it is guessed. If the plaintext segment is guessed it is unlikely that its exact position is known however a message is generally short enough for a cryptanalyst to try all possible positions in parallel. In some systems a known ciphertext-plaintext pair will compromise the entire system however a strong encryption algorithm will be unbreakable under this type of attack.

A brute force attack requires a large amount of computing power and a large amount of time to run. It consists of trying all possibilities in a logical manner until the correct one is found. For the majority of encryption algorithms a brute force attack is impractical due to the large number of possibilities.

Another type of brute force attack is a dictionary attack. This essentially involves running through a dictionary of words in the hope that the key (or the plaintext) is one of them. This type of attack is often used to determine passwords since people usually use easy to remember words.

In a ciphertext only attack the cryptanalyst has only the encoded message from which to determine the plaintext, with no knowledge whatsoever of the actual message. A ciphertext only attack is presumed to be possible, if not easy. In fact, an encryption techniques resistance to a ciphertext only attack is considered the basis for its cryptographic security.

In a chosen plaintext attack the cryptanalyst has the capability to find the ciphertext corresponding to an arbitrary plaintext message of his or her own choosing. The likelihood of this type of attack being possible is not much. Codes which can survive this attack are considered to be very secure.

In a chosen ciphertext attack the cryptanalyst can choose an arbitrary ciphertext and find the corresponding decrypted plaintext. This attack can be used in public key systems, where it may reveal the private key.

In an adaptive chosen plaintext attack the cryptanalyst can determine the ciphertext of chosen plaintexts in an iterative process based on previous results. This is the general name for a method of attacking product ciphers called "differential cryptanalysis".

Frequency Tables

The cryptanalysis of single-key cryptosystems depends on one simple fact - that some traces of the original structure of the plaintext may be visible in the ciphertext. For example, in a monoalphabetic substitution cipher where each letter in the plaintext is replaced by a letter in the ciphertext which is the same each time, a simple analysis of a sizeable portion of ciphertext can be used to retrieve most of the plaintext.

Here is a monoalphabetic substitution cipher of a random paragraph of English:

UFMDHQAQTMGRG BX GRAZTW PWM

UFMDHBGMGHWOG VWDWAVG BA BAW

GRODTW XQUH AQOWTM HCQH HFQUWG

BX GHFIUHIFW BF DQHHWFA RA HCW

DTQRAHWLH OQM GIFJRJW WAUFMDHRBA

QAV SW VRGUWFARSTW RA HCW

URDCWFHWLH.

W occurs 20 times in the cipher, H occurs 16 times. From this information and using the frequency table to the left it would be possible for a cryptanalyst to recover the majority of the plaintext. The usefulness of analysing the structure of the ciphertext can be reduced by any encryption procedure that attempts to disguise the structure. However, eliminating the underlying structure is harder than it would first seem. Digraphs, for example, show a strong frequency distribution - TH occurs very often, about 20 times more often than HT and so on. With tables of digraph frequencies it is possible to recover the underlying plaintext, however, the amount of ciphertext required would be much greater. In the heyday of manual cryptanalysis huge volumes of word patterns were compiled. Although these only contained the most obvious and easily recognised word patterns they were still of importance if they could provide that vital clue which could break the entire cipher.

Cryptanalysis Of Public Key Ciphers

Public key cryptography requires a fundamentally different type of cryptanalysis than is used for single key cryptanalysis. Because public key cryptography relies on "hard" mathematical problems, their cryptanalysis is essentially research into solving the underlying mathematical problems. Cryptanalysis of public key ciphers is therefore virtually indistinguishable from research into any other area of mathematics.

For example, to "crack" the RSA algorithm and obtain the private key from the public key would essentially involve research into factoring algorithms. Factoring is a very active field of research among mathematicians and computer scientists. The best general-purpose factoring algorithm today is the Number Field Sieve but even so, the running time to search through all the possibilities is very long.

In 1980 it was possible to factor a 50-digit number with 1,000,000,000,000 computer operations. By 1984 factoring algorithms had advanced to the stage where a 75-digit number could be factored in the same number of operations. If a mathematical advance was made which enabled a 150 (or more) digit number to be factored in the same number of operations it would allow cryptanalysts to break many RSA implementations.

A Triumph of Cryptanalysis - Enigma

No look at cryptanalysis, however brief, with even the slightest element of historical content, could finish without at least briefly covering the tale of how the Enigma was broken.

What Was Enigma?

The efficiency of the German armed forces during World War 2 would not have been possible without radio communication. Messages sent over the radio had to be encrypted and the encryption system they used was adapted from one which was commercially available before the war. Despite the fact that it was modified so as to make it harder to crack it was broken by a group working at the GCHQ.

The Enigma machine consisted of a 26 letter keyboard for input. The output was read off 26 lamps which each corresponded to a letter. The encipherment was performed by a device called a "scrambler" that was made of three rotating wheels on a common spindle and a plugboard known as a "Steckerboard" that added an additional level of security.

The keyboard and lampboard were both connected to a common cabling bus. When no keys were being held down all the lamps were connected to the bus and the current present on any particular wire would cause its lamp to glow. When a key was pressed a current was placed on its wire but the corresponding lamp was disconnected from the bus.

Since no letter could ever be enciphered to itself this was a good set-up. When a key was pressed one wire on the bus would have current applied to it and the other 25 could respond with the enciphered letter. The one that actually did respond was the result of the other components.

The original, commercial, Enigma did not have the plugboard. The 26 wire bus was connected to a circular set of contacts that sat to the right hand side of the three rotor scrambler. These three rotors were identical except in their internal wiring. The rotors had two sets of 26 connectors, one on the left and one on the right. All three rotors had to be rotated by hand and by doing so the "key" could be changed. Because each rotor could be set independently there were 26 ´ 26 ´ 26 (17576) possible rotor settings. This would not have provided a secure ciphering system so every time a key was pressed one of the rotors (known as the "fast" rotor) was advanced one position so that even if the same key was pressed three times the result would be three different characters. When the fast rotor got to a certain position it would cause the middle rotor to be rotated to one position, which in turn could cause the slow rotor to move one position.

Initial Work On Cryptanalysing Enigma

The initial work on cryptanalysing Enigma was done by the Polish. The earliest Polish work on the intercepting German machine ciphers had begun in 1928, right after the systems introduction by the German Army. However, no progress was made during the first four years. Then the Polish Cipher Bureau decided to recruit three young mathematicians. Among them was Marian Rejewski. On September 1, 1932 Rejewski and his two somewhat younger colleagues began work at the Cipher Bureau in Warsaw. In early October Rejewski began work on the Enigma and was supplied with an obsolete commercial Enigma machine which had been brought in Germany.

The whole, complicated process of mastering the German Enigma was ultimately concluded in the early days of 1933. This included combinations of mathematics, statistics, computational ability and guesswork. The breaking of Enigma involved two distinct processes. The first was the theoretical reconstruction of the Enigma cipher device itself including the internal wiring and the interdependence between different components of the machine. This knowledge of the machine enabled the Poles to build doubles of the Enigma, The second was the creation of methods for recovering the Enigma keys (starting positions) based exclusively on the basis of intercepts.

At the beginning of the second world war, realising that a German invasion was imminent, the Polish handed over all the information including the duplicate Enigma models over to the British.

What Made It Possible?

With the level of sophistication of the Enigma machines it should have been unbreakable. However, the Germans had a number of procedural flaws which allowed the British and Polish to break the cipher.

Some of these were just stupid. For example, the Germans reused the monthly code book settings. Others were less obvious. It was discovered that the German military messages were very similar in nature and, once they were decrypted, very careful records were kept regarding how the messages tended to be formatted. When the British thought they had a likely idea of what the start of the message was, they would use this to reduce the many trillions of possible Enigma settings to a small enough number to be tested individually.

The Turing Bombe

The design of the Turing bombe is normally credited to two British mathematicians - Alan Turing and Gordon Welchman, working in secret at Bletchley Park. The information handed over to the British by the Polish was much more advanced than anything the British (or anyone else) had accomplished . One of the things the Polish had developed was a machine they called a Bomba (the Polish word for bomb - probably named because of the ticking sound it made). The Polish machine and the British one worked on different algorithms but were mechanically very similar. This provided Turing with a starting point.

The Bombe was effectively a collection of Enigma machines that were all working together. According to Welchman there were twelve sets of Enigma rotors in the Bombe, but there is also other evidence that larger Bombes existed. None of the Bombes survived the war so it is difficult to be sure.

The theorem the Bombe was based on the loop that exists between the crib (a guessed sequence of letters) and the equivalent cipher text. The method Turing devised to test this was based upon the mathematical technique reductio ad adsurdum. For every one of the possible rotor settings Turing would start by assuming that this was the correct setting and then try to disprove this. If the procedure did disprove the setting the machine would automatically advance to the next setting to be tested. If it did not the setting was recorded, and then the procedure continued to try and find other possible settings.

Cryptography in the "Real World"

Applications Of Cryptography

In the information dependent world in which we now live cryptography can be found all around us, often in places where you would not expect it. When people think about encryption they tend to think about vast computer banks processing military and diplomatic communications, or a world war two rotor cipher machine slowly deciphering an order. In reality, cryptography - although obviously essential for the military and diplomatic services - has many commercial uses and applications. From protecting confidential company information, to protecting a telephone call, to allowing someone to order a product on the Internet without the fear of their credit card number being intercepted and used against them, cryptography is all about increasing the level of privacy of individuals and groups. For example, cryptography is often used to prevent forgers from counterfeiting winning lottery tickets. Each lottery ticket can have two numbers printed onto it, one plaintext and one the corresponding cipher. Unless the counterfeiter has cryptanalysed the lottery’s cryptosystem he or she will not be able to print an acceptable forgery.

In a world where virtually all data of any importance is held on a computer system the necessity of cryptography cannot be disputed.

Politics Of Cryptography

Widespread use of cryptosystems is something most governments are not particularly happy about - precisely because it threatens to give more privacy to the individual, including criminals. For many years, police forces have been able to tap phone lines and intercept mail, however, in an encrypted future that may become impossible.

This has lead to some pretty strange decisions on the part of governments, particularly the United States government. In the United States, cryptography is classed as a munition and the export of programs containing cryptosystems is tightly controlled. In 1992, the Software Publishers Association reached agreement with the State Department to allow the export of software that contained RSA's RC2 and RC4 encryption algorithms, but only if the key size was limited to 40 bits as opposed to the 128 bit keys available for use within the US. This significantly reduced the level of privacy produced. In 1997 this was increased to 56 bits. The US government has proposed several methods whereby it would allow the export of stronger encryption, all based on a system where the US government could gain access to the keys if necessary, for example the clipper chip.

The resolution of this issue is regarded to be one of the most important for the future of e-commerce.

PUBLIC KEY CRYPTOGRAPHY

Up to this point all the examples have assumed that the encryption process is undertaken with the same key as the decryption process, and that only the sender and the receiver possess the secret key. However, this can cause problems.

The Key Distribution Problem

A major problem in the practical use of single-key cryptography is the key distribution problem. This problem basically occurs because both the sender and receiver must hold a copy of the key, but they must also prevent others from gaining a copy of the key.

This does not, on the face of it, appear to be a problem, but it can be one as is probably best illustrated by an example.

Suppose that two individuals, O and L, wish to exchange information securely but can not guarantee the security of the transmission itself. They would probably use some sort of encryption to ensure that even if the message was intercepted its contents would remain secret. In order for this to operate they would both have to know a secret key which could be used to encrypt the data. However, since the transmission medium is not secure they would have to meet in person to decide upon the key. Once this was done, however, they could exchange information happily, encrypted with this secret key, in the knowledge that to anyone without the key it would simply look like garbage. O and L must protect the security of the key in their possession since if a cryptanalyst, C, obtained it, he could read, alter or fake a message from either O or L.

This appears to be working perfectly, except a problem could soon arrive. Suppose that O or L then wanted to correspond with another individual, T. If they were to give T the key they would further compromise it because C would now have another source from which he might obtain it. In order to ensure that each message is not intercepted by another party both O and L would have to create different keys to exchange with T so that they would all each hold two keys (because otherwise O could alter T’s message to L and so forth).

Now consider a system with 1,000 members, all of whom wish to communicate in secret with each other. In this case, each individual would need to hold a key for every individual besides himself, in other words 999 keys for other people. Each individual would also have to protect those 999 keys from being compromised.

It is possible to calculate the number of keys present in a system with any number of members using these facts as I have done below, calculating the number of keys required by multiplying the number of members minus one by the number of members and divided by two.

Keys = [n ´ (n-1)]/2

Members	#/Members2	# of keys required
2	4	1
3	9	3
4	16	6
5	25	10
6	36	15
7	49	21
8	64	28
9	81	36
10	100	45
100	10000	4950
1000	1000000	499500

The number of keys is divided by two because some of the keys are duplicated (the key A uses to send to B is the same which B uses to send to A). The reason why I have included a column containing the number of members squared is made obvious below.

Here is a graph of the number of members squared against the number of keys required (I have excluded the final two rows to ensure that there is a practical scale).

As you can see the number of different keys required is nearly proportional to the square of the number of members in the system. This is the key distribution problem.

A Solution To The Key Distribution Problem

A solution to the key distribution problem can be found in public key, or two-key, cryptography. Public Key cryptography is based on the idea that a user can possess two keys - one public and one private key. The public key can only be used to encrypt the data to be sent and the private key can only be used to decrypt it. Although single-key cryptography has been in use for centuries, public key cryptography is a relatively new invention with the first discussion about the subject in open literature being in 1976.

The fact that anyone can use a single "locking" key to encrypt a message which they are confident can still only be read by a single authorised user means that the number of keys required can be greatly reduced. For example, in the 1000 member system above the number of keys necessary could be reduced from 499,500 to 2000 (1000 public and 1000 private keys).

For example I will use a far simpler three user system. An individual, say P, could distribute his public key to two other individuals, A and C. A could then send a message to P by encrypting it with the public key. When P receives the message he could then decrypt and read the message using his private key. Supposing C was a nosy individual then he might attempt to spy on the communications between A and P, however, because he only possesses the encrypting key, he can not decrypt the message.

There is a problem with this solution however. In this example, although C can not read or alter a message sent to P by A, he or she could easily fake a message because C has the same public key as A. Therefore, with a public key system the ability to authenticate messages has been given up in return for privacy. In many cases this will not be a problem however there are times when it will be so.

There is an alternative to this method. A could send P and C his or her private (unlocking) key and keep the public key secret. A could then encrypt messages with his public key and send them to either P or C. This system has the advantage that the person receiving the message knows that it must have come from A; however, both P and C can now decrypt the message. In this example secrecy has been sacrificed in order to maintain an ability to authenticate the message.

This is a problem with the public key system which can only be solved by increasing the number of keys in the system. It can be solved however, by combining the two methods outlined above. If each user had two sets of public and private keys and distributed one key from each set then the capability to authenticate messages and to keep them secret would be maintained.

For example, another three individuals P, D and W are using this system. Each user holds, in addition to their normal private (unlocking) key and everyone else’s public keys, a public key which is paired with a private key which they then distribute. P could then encrypt a message with his own public key, thus authenticating it, and then encrypt it with the public key of whoever the message was intended for (thus ensuring secrecy).

Under this system each message is encrypted twice, once in a way which only the intended receiver can decrypt it, and once in which only the authentic sender could have encrypted it. Even though the number of keys required has been increased it still does not approach the number of keys which would be required for a single-key system of the same size.

It is this idea of nested encryption processes with public and private keys which makes public-key cryptography so attractive.

Properties For A Two-Key Cryptosystem

For two-key cryptography to be possible a cryptosystem must have the following properties:

1. It must be easy for the cryptographer to calculate a pair of keys (private and public) but virtually impossible for a cryptanalyst to recover either key, regardless of how much ciphertext is available.
2. The encryption and decryption operations should be easy (computationally speaking) for legitimate users to carry out.
3. At least one of the keys must be virtually impossible for the cryptanalyst to recover even when he knows the other key and many matching plaintext and ciphertext pairs.

At present no cryptosystem ever devised has satisfied all of these conditions in a provable way. However, cryptographers have devised cryptosystems of this sort by starting with a difficult mathematical problem such as factoring a product of large prime numbers and attempting to make the cryptanalysis of the scheme be equivalent to solving the problem. If this can be done then the security of the scheme is at least as good as the underlying problem is hard to solve.

There are a number of problems that are commonly used as the basis for public key cryptosystems.

Knapsack Problem

Ralph Merkle, XEROX and Martin Hellman, Stanford University, put forward one of the best known proposals for a public-key cryptosystem in 1976. In 1997 the six co-founders of public key cryptography were awarded the Paris Kanellakis Theory and Practice Award, named after a researcher who died in 1995, for their work. Hellman and Merkle were among those who received the award.

They suggested using the knapsack, or subset-sum, problem as the basis for a public key cryptosystem. This problem entails determining whether a number can be expressed as a sum of some subset of a given sequence of numbers and, more importantly, which subset has the desired sum.

Given a sequence of numbers A, where A = (a₁ ... a_n), and a number C, the knapsack problem is to find a subset of a₁ ... a_n which sums to C.

For a specific example:

n = 5, C = 14, A = (1, 10, 5, 22, 3)

Solution = 14 = 1 + 10 + 3

In general, all the possible sums of all subsets can be expressed by:

m₁a₁ + m₂a₂ + m₃a₃ + ... + m_na_n where each m_i is either 0 or 1.

The solution is therefore a binary vector M = (1, 1, 0, 0, 1).

There is a total number 2ⁿ of such vectors (in this example 2⁵ = 32)

Obviously not all values of C can be formed from the sum of a subset and some can be formed in more than one way. For example, when A = (14, 28, 56, 82, 90, 132, 197, 284, 341, 455, 515) the figure 515 can be formed in three different ways but the number 516 can not be formed in any ways.

The only known solution to the general knapsack problem (as above) is a brute force test - testing all the possible subsets until either the sum is found or you run out of subsets.

However, there is a special case if A is sorted and when each progressive term is larger than the one which follows it (called the simple knapsack problem) and there is an easy solution (this type of sequence is described as superincreasing). The value of C is compared to each value of A, starting with the largest. If A is larger than C then that number is not in the subset, if it is smaller then that value is in the subset. The next value is then compared to C less the sum of all the values found already.

For example:

A = (1, 3, 5, 10, 22), C = 14

14 £ 22 m₅ = 0

14 ³ 10 m₄ = 1

4 £ 5 m₃ = 0

4 ³ 3 m₂ = 1

1 ³ 1 m₁ = 1

M = (1, 1, 0, 1, 0)

The cryptographer uses a secret transformation to turn a simple knapsack into a hard one. Legitimate users, knowing the secret transformation, could easily invert the hard knapsack back to the simple knapsack. This can be done using a private multiplier and a private modulus, the original sequence is multiplied by the multiplier and then dividing by the modulus (finds the remainder). This has the effect of scrambling the values. The plaintext is then converted into a set of binary bits which are then multiplied by the values of the public sequence and the result is recorded. To decrypt them is the equivalent of the hard knapsack problem for anyone who doesn’t know the secret information.

For example:

Taking the following private information:

A = (1, 3, 5, 10), b = 20, k = 7 (b is the private modulus, k is the private multiplier)

\ A = (7 ´ 1 mod 20, 7 ´ 3 mod 20, 7 ´ 5 mod 20, 7 ´ 10 mod 20)

Public key = (7, 1, 15, 10)

To encrypt the plaintext we must convert in into a binary number. For this simple example I will convert the letter to a value describing its position in the alphabet.

Let plaintext P = m (= 13) = 1101

Assigning each of these values a "size" from the public key and multiplying produces the following code, C.

C = 1 ´ 7 + 1 ´ 1 + 0 ´ 15 + 1 ´ 10 = 18 (= r)

The code letter is therefore r.

To decrypt this code letter without the secret transformation would be computationally infeasible, so we must perform the operation on the letter r (18).

To decrypt, use the inverse key k^-1.

Let k^-1 = 3 (any value for which k ´ k^-1 mod 20 = 1)

Let C = 18

C’ = 3 ´ 18 mod 20 = 14

Now we can use the value of 14 to solve the simple knapsack problem.

(1, 3, 5, 10)

14 ³ 10 m₄ = 1

4 £ 5 m₃ = 0

4 ³ 3 m₂ = 1

1 ³ 1 m₁ = 1

\ M = (1, 1, 0, 1) corresponds to binary 1101 = 13 = m

Unfortunately, it has been shown that it is possible, in a reasonable length of time, to derive the private key from the public key thus knapsack-based cryptosystems have been shown not to be secure. However, although of little practical use, they are an excellent introduction to the idea of public key encryption.

Rivest-Shamir-Adleman (RSA) Algorithm

The main contenders for two-key cryptosystems in the mid-1980s were those based on factoring large integers. Of these, the best known is the RSA algorithm, developed by Ron Rivest, Adi Shamir, and Leonard Adleman in 1977.

In this system a user chooses a pair of prime numbers so large that factoring the product is beyond all computing capabilities. This is possible because testing for primes is easy whereas factoring the product is very difficult.

In practise, RSA works as follows. The user takes two large primes, p and q, and computes their product n = pq. n is called the modulus. The user then chooses a number, e, less than n and with no common factors (except 1) with (p-1)(q-1). Another number, d, is then found, subject to the condition that (ed-1) is divisible by (p-1)(q-1). e is called the public exponent, d is called the private exponent. The public key is therefore the pair n and e, the private key is the pair n and d. The factors of n, p and q, can either be kept secret with the private key or destroyed.

It is currently virtually impossible to obtain the private key, d, from the public key (n and e). However, if n could easily be factored into p and q then a cryptanalyst could obtain the private key, d. The security of RSA is therefore based upon the assumption that factoring is difficult.

Here are the stages in sending a message using this method:

1. The receiver, M, distributes his public key pair.
2. The sender, F, composes a plaintext message, m, and then uses Ms public key to encrypt the message and form the ciphertext, c. c is the remainder left when m is raised to the power of e and divided by the modulus n.

c = m^e mod n (where e and n are Ms public key pair).

3. F sends the ciphertext, c, to M.
4. The receiver, M, decrypts the ciphertext and retrieves the plaintext message, m. m is the remainder obtained when c is raised to the power of d and divided by n.

m = c^d mod n

5. As you can see, this process requires d, which only M knows. Another person, I, who intercepts the message, can not decrypt it.

For example:

Let p = 5, q = 11, n = pq = 55

The least common multiple of (p-1)(q-1) is 20 = 2² ´ 5.

Therefore, in this case, any key, e, not divisible by 2 or 5 will have a matching key, d (e must be relatively prime to (p-1)(q-1) for it to be the key).

Let e = 7

(ed -1) mod (p-1)(q-1) = 0 \ d = 3

Let the plaintext message, m = b = 2

\ The ciphertext, c = m^e mod n = 2⁷ mod 55 = 18

To decrypt this information it is necessary to know d.

m’ = c^d mod n = 18³ mod 55 = 2 \ The message has been successfully decrypted.

This example used small primes so it can be seen that the product, n, is not at all difficult to factor to retrieve the original primes. In using RSA it has always been suggested to use "strong" primes which have certain properties making their product especially difficult to factor using certain factoring methods. However, advances in factoring techniques over the last decade have near completely negated the advantage of strong primes, the elliptic curve factoring algorithm is one such advance. Therefore, it is not choosing traditionally "strong" primes which matters but rather choosing large primes.

In 1997, a specific assessment of the security of 512-bit RSA keys shows that one may be factored for less than $1,000,000 in cost and eight months of effort. It is therefore believed that 512-bit keys provide insufficient security for anything other than short-term needs. RSA Laboratories currently recommends key sizes of 768 bits for personal use, 1024 bits for corporate use, and 2048 bits for extremely valuable keys like the root-key pair used by a certifying authority. Security can be increased by changing a users keys regularly and it is typical for a user’s key to expire after two years (the opportunity to change keys also allows for a longer length key to be chosen).

It should be noted that the key sizes for RSA (and other public-key techniques) are much larger than those for block ciphers like DES, but the security of an RSA key cannot be compared to the security of a key in another system purely in terms of length. It should also be noted that although increasing the length of the modulus may increase the security of the system it also significantly increases the amount of time required to perform encryption, decryption and authentication - doubling the modulus will, on average, quadruple the amount of time taken for encryption and increase the time taken for decryption by a factor of eight.

"Real World" Usage Of The RSA Algorithm

DES, and other block ciphers, are much faster in operation than RSA. Typically, in software, DES is approximately 100 times faster than RSA and in hardware can be between 1000 and 10000 times faster depending on the implementation. Because of the length of time taken for public key encryption a public key system such as RSA is often used in conjunction with a secret-key system such as DES. In this case the message is encrypted with a randomly chosen DES key and the key itself is encrypted and sent with RSA. This method combines the low number of keys required for RSA with the high-speed operation of DES.

RSA is the most widely used public-key cryptosystem available currently and has often been referred to as a de-facto standard regardless of official recognition. In fact, RSA is part of many official standards worldwide. These include ISO 9796 which lists RSA as a compatible cryptographic algorithm and many internet standards and proposals including S/MIME.

Data Encryption Standard (DES)

Originally developed by IBM under the name of LUCIFER, the American NSA (National Security Agency - the US equivalent of GCHQ) and the National Institute of Standards and Technology played a substantial role in the final stages of developing DES. DES is the most well known and widely used symmetric algorithm in the world. The NIST has re-certified DES every five years and it was last certified in 1993 but NIST have indicated that they would not re-certify DES again, AES (Advanced Encryption Standard) is expected to replace DES.

DES has a 64-bit block size and uses a 56-bit key during encryption. DES is a 16-round Feistel cipher and was originally designed for implementation in hardware. Because it is a single-key cryptosystem, when used for communication both sender and receiver must know the same secret key which can be used to encrypt or decrypt the message. DES can also be used by a single-user, for example to store files on a hard disk securely.

No easy attack on DES has yet been discovered, despite research efforts over many years. There is no feasible way to "break" DES other than an exhaustive search - a process which takes 2⁵⁵ steps on average. However, cryptanalysis methods which rely on knowledge of some of the plaintext have had some success. The consensus of the cryptography community is that, if it is not currently so, DES will soon be insecure. As a result of this as of November of 1998 DES was no longer used by the U.S. Government.

STREAM CIPHER

A stream cipher also breaks the plaintext into units, this time it is normally a single character. It then encrypts the n^th unit of the plaintext with the n^th unit of the key stream. Stream ciphers can be designed to be exceptionally fast, much faster than any block cipher. While the encryption of any particular plaintext with a block cipher will result in the same ciphertext when the same key is used; with a stream cipher, the transformation of the smaller plaintext units will vary, depending on when they are encountered during the encryption process.

A stream cipher generates what is known as a keystream - a sequence of bits, which is used as a key. The encryption process involves combining the keystream with the plaintext.

The keystream can be generated in two ways:

1. Independent of the plaintext and ciphertext (this yields what is known as a synchronous stream cipher).
2. Depending on the data and its encryption (in which case the stream cipher is said to be self-synchronizing).

The majority of stream cipher designs are for synchronous stream ciphers.

Interest in stream ciphers is currently attributed to the appealing properties of the one-time pad. A one-time pad, which is sometimes called the Vernam cipher, uses a keystream which is the same length as the plaintext message and consists of a series of bits generated completely at random. Theoretically this should produce ciphertext which is the most secure possible, because since the keystream is random even a cryptanalyst with infinite computational resources can still only guess at the underlying plaintext. While the one-time pad has occasionally seen use in wartime for ultra secret transmissions the fact that the key is as long as the message introduces severe practical problems and so, while theoretically perfectly secure, the one-time pad is generally impractical. Stream ciphers were developed as an approximation to the one-time pad.

At this time there is no de facto standard for stream ciphers although the most widely used stream cipher is RC4, a stream cipher designed by Rivest for RSA Data Security Inc. It is a variable key-size stream cipher with an algorithm based on the use of a random permutation.

Strangely, certain modes of operation of a block cipher transform it into a keystream generator and so, in this way, any block cipher can be used as a stream cipher. Stream ciphers with a dedicated design and typically much faster, however.

One method for generating a keystream is a Linear Feedback Shift Register (LFSR). This is a mechanism for generating a sequence of binary bits. LFSRs are easy to implement and fast operating in both hardware and software however a single LFSR is not secure because over the years a mathematical framework has been developed which allows for the analysis of their output. This problem can be solved by using a shift register cascade, a set of LFSRs connected together so that the behaviour of one of them depends on another. The detailed operation of LFSRs and shift register cascades is beyond the scope of this essay.

BLOCK CIPHERS

Generally, ciphers transform pieces of plaintext of a fixed size into ciphertext. In older, manual systems, these pieces were usually single letters or characters (or sometimes, as in the Playfair cipher, digraphs), since these were the largest units that could be easily encrypted or decrypted by hand. Although systems which operated on sets of three characters and other, larger groups of numbers, were proposed and understood to potentially be more secure they were never implemented because of the extra difficulty in the manual encryption or decryption process. In modern, single key cryptography however, the units of information can be much larger.

A block cipher is a type of symmetric-key encryption algorithm that changes a fixed-length block of the plaintext into the same length of ciphertext. The encryption works by means of a key. Decryption is simply the reverse of the encryption process using the same secret key. The fixed length is called the block size and for modern block ciphers is usually 64 bits. As processors become more sophisticated, however, it is likely that this block size will increase to 128 bits.

Since different plaintext blocks are mapped to different ciphertext blocks, a block cipher effectively provides a permutation of the set of all possible messages. The actual permutation produced during any particular operation is of course secret, and determined by the key.

An iterated block cipher encrypts a plaintext block using a process with several stages (rounds). At each stage the same process (known as a round function) is applied to the data using a subkey (the set of subkeys usually being derived from a user provided key). The number of rounds in an iterated block cipher depends on the desired security level of the encrypted ciphertext and the trade-off that must be made with performance; fairly obviously a iterated block cipher with a large number of rounds will require more processing time. It is worth noting that in some cases the number of rounds required to provide an accurate level of security will be too large for the cipher to be practical.

An example of an iterated block cipher is a Feistel cipher. Feistel ciphers are a special class of iterated block ciphers. In this type of cipher the ciphertext is calculated from the repeated application of the same round function.