Chapter 4 – RSA Encryption - Apps for the TI89 Calculator



Chapter 4 - RSA Cipher

In this Chapter I am going to show you how highly secure communication is realized. We are leaving behind the breakable ciphers that we studied in the previous chapters. Rather, we are going to use learned concepts such as MOD arithmetic, Euler’s (-function, Euler’s Theorem and the Euclidean Algorithm in order to create an unbreakable cipher: The RSA Cipher. It is the most popular cryptosystem among today’s secure ciphers. It leads us to Two-Key Cryptography – commonly called Public-Key Cryptography.

The US-Cryptographer Bruce Schneier[1] distinguishes roughly between One-Key and Two-Key Cryptography as follows:

“There are two kinds of cryptography in this world: cryptography that will stop your kid sister from reading your files, and cryptography that will stop major governments from reading your files.”

The previous chapters are about the earlier. This chapter is about the latter: the strong cryptography. Phil Zimmermann [2] gives a more insightful explanation for the strong versus weak cryptography:

Cryptography can be strong or weak, as explained above. Cryptographic strength is measured in the time and resources it would require to recover the plaintext. The result of strong cryptography is ciphertext that is very difficult to decipher without possession of the appropriate decoding tool. How difficult? Given all of today’s computing power and available time—even a billion computers doing a billion checks a second—it is not possible to decipher the result of strong cryptography before the end of the universe. One would think, then, that strong cryptography would hold up rather well against even an extremely determined cryptanalyst. Who’s really to say? No one has proven that the strongest encryption obtainable today will hold up under tomorrow’s computing power.

4.1 The Beginning of Public Key Cryptography

Public Key Cryptography started in 1976 when 31-year-old computer wizard named Whitfield Diffie came up with a new system that surprised the world of ciphers. As a child, Diffie devoured all the books he could find on the subject of cryptography. Certainly there is something about codes -- secret rings, intrigue -- that appeals to youngsters. Diffie, son of an historian, took them very seriously.

Diffie solved the major problem of existing cryptography by making the key transfer unnecessary

The problem with the existing system of cryptography was the key transfer. In order to communicate secretly the sender has to deliver the secret key to the recipient. In that way the recipient can decrypt the encrypted message. The dilemma: In order to transfer a secret a different secret (the key) had to be delivered before. How can the key be sent from one party to another? If you sent it over an insecure channel (i.e. telephone, internet, etc.) what's to stop someone from intercepting it and using it to decode all subsequent messages? Diffie showed in a clever manner how to overcome the key transfer dilemma.

4.1.1 The Diffie-Hellman Key Exchange

In 1976, the two Mathematicians Whitfield Diffie and Martin Hellman devised the notion of Public-Key-Cryptography in “New Directions in Cryptography” [3]. They showed how two communication partners that are at different locations can publicly create a common key without fearing that a third person who observes the key generation could crack it. The public creation of a common secret key was the first major step in Public Key Cryptography. It enables two parties to establish secure communication without having to deliver the secret key at some earlier point in time.

Since you know how to perform MOD arithmetic you will understand the Diffie-Hellman Key Exchange between Alice and Bob easily. Here it is in 4 steps. The two left columns show the general key exchange protocol. The two right columns display an example for the key exchange protocol:

|1) Alice and Bob publicly pick 2 integers: |1) Alice and Bob publicly pick |

|a prime number p |p = 11 and |

|and an integer s between 1 and p. |s = 3. |

|2) Alice picks a random number a |2) Bob picks a random number b |2) Alice picks a=2. |2) Bob picks b=4. |

|that is less than p. |that is less than p. | | |

|3) Alice computes |3) Bob computes |3) Alice computes |3) Bob computes |

|A = sa MOD p and sends A to Bob. |B = sb MOD p and sends B to Alice.|A = 32 MOD 11 = 9 |B = 34 = 81 |

| | | |= 4 MOD 11 |

|4) Alice computes the key K = Ba |4) Bob computes the key K = Ab MOD|4) Alice computes |4) Bob computes |

|MOD p. |p. |K = 42 MOD 11 = 5 |K = 94 = 6561 MOD 11 = 5. |

We have to answer the following two questions:

1) Why do Alice and Bob always end up with the same key K ?

2) Why can’t an eavesdropper compute K ?

Answer to questions 1):

Alice and Bob compute the key K in the final step as follows:

Alice: K = Ba = sba MOD p.

Bob: K = Ab = sab MOD p.

Since sba = sab MOD p both Alice and Bob compute the same key K.

Answer to questions 2):

Say, an eavesdropper did a great job by intercepting the values A and B, p and s. In order to uncover the key K he has to compute either a or b. Mathematics teaches that this is impossible if a, b, p, s, A, B were chosen as of 100-digits numbers or larger.

The reason: although it is quite simple to compute i.e. A = sa MOD p, however, solving this equation for a is impossible. More formally stated: Although the “discrete exponential function” can be executed, its inverse, the “discrete logarithm function” can not. Hence, the “discrete exponential function” is an example of a “One-Way function”. We will study such functions later on this chapter.

4.1.2 Diffie’s Search for a Public Key Cryptosystem

While Hellman was working on the public key exchange algorithm, Diffie continued his research. His public key exchange idea is feasible, however, it has one major practical limitation: Both parties have to first create their secret key in a mutual process. As a consequence, the sender has to wait until the common key is created to send the encrypted message. Diffie tried to overcome this deficit as follows: Each party shall possess a key pair, a public and a private key. I.e. Alice’s public key is used by Bob to encrypt the message for Alice whereas her private key is used to decrypt Bob’s encrypted message.

Although it was not Diffie who actually designed an algorithm that realizes his provoking idea of a public and private key, he deserves credit for making the inconceivable conceivable. He initiated mathematical research groups worldwide to find an appropriate mathematical setting that realizes his vision. The research question was:

Which mathematical function allows anybody to encrypt a secret message for Alice using her publicly known encoding key e and prevents everybody but Alice to decrypt such cipher message?

It requires an experienced mathematician to find such one-way functions since most functions are two-way and can thus be reversed. I.e. A Caesar right shift can be reversed by a corresponding left shift. Mathematically, since addition can be reversed by subtraction it is (the simplest) two-way function.

[pic]

Figure 4.1: This diagram shows that Public–Key Cryptography uses two different keys for en- and decryption. The crux: knowing the public encoding key does not reveal the decoding key.

The winners of the worldwide search for appropriate one-way functions are the 3 Israelis Ronald Rivest, Adi Shamir and Leonard Adleman[4]. Let’s talk for a moment about how the three MIT researchers Rivest, Shamir and Adleman came up with their idea for the RSA Ciphers in 1977.

The irony of the process to create the RSA Cipher is that Rivest, Shamir and Adleman originally tried to prove that Diffie’s idea of a public and a private key could NOT be realized by showing that there are no appropriate one-way functions. Thus, while being unsuccessful the three Cryptographers became really successful: While Rivest devised encryption ideas, Adleman tried to attack them and Shamir contributed to both[5]. The final RSA idea was ground-breaking as it simultaneously answers the contemporary quests for a public key cipher as well as a scheme to perform digital signatures.

4.1.3 The RSA Cipher is a Public-Key-Cryptosystem

Given sufficiently large key lengths, RSA realizes the

Public-Key Property:

The knowledge of the encoding key does not reveal the knowledge of the decoding key. Even the usage of the most powerful computers combined will not suffice to crack the secret decoding key based on the knowledge of the publicly known encoding key.

Although the encoding keys are publicly known, nobody in the world can make use of that knowledge in order to crack the secret decoding key. WHY is that? How can the knowledge of the encoding key NOT reveal the decoding key? What do we have to consider when choosing the encoding key so that its decoding key remains secret? The next section will tell you.

As a consequence:

Only one key pair per person is needed. Therefore, a total of only n key pairs are needed for n communicating people.

In particular, 100 people communicating just need 100 key pairs. The 100 encoding keys are publicly known. Think of them being listed in a directory. These days the internet provides the means to locate the public encoding key of any correspondent. Currently, the public keys of the most popular encryption software, “Pretty Good Privacy” or simply “PGP”, can be looked up at . The corresponding 100 private decoding keys must be kept absolutely secure (i.e. in a vault) by its respective owner. They should not be saved on the hard-drive or other accessible devices.

Exercise 1: Ever since its invention in 1978, RSA has heavily impacted secure communication such as financial transactions, electronic mail, Pay TV, secure telephone calls etc. To gain further insight into RSA and its impact, research RSA usage and security on the internet by searching for “RSA encryption” and visiting sites such as .

Exercise 2: Find out about the RSA implementations in the Netscape Navigator for secure web-based transactions.

Exercise 3: (Discover how the RSA-Cipher works): Click here to perform your own RSA encryption. Try to figure out how the cipher numbers are produced from the plain letter numbers. By doing so you can discover for yourself how the RSA encryption works before I will introduce it in the next section.

4.2 An Example for RSA Encryption

The RSA Cipher is actually quite easy to understand. Don’t be mislead: The fact that a cipher can be executed easily does not make it insecure. On the other hand, ciphers that are hard to execute are not necessarily secure. The 4 steps involved in the RSA Cipher are displayed in the middle column. In the right column I demonstrate how the word “SAFE” is en- and decrypted using the RSA Cipher. We use the same letter values as in the previous chapters to encrypt: S=18, A=0, F=5, E=4. Again, the choice of the letter values is arbitrary. It just matters that sender and recipient use the same letters values. Let’s go ahead and perform the RSA encryption.

Example for RSA Encryption and Decryption:

|Step: |a) Choose two primes p and q so that their product |a) Say p=3 and q=11, then n=33 |

|Preparation |n=p*q is greater than the used alphabet length M | |

| |(i.e. here M=26). | |

| |Compute ((n). | |

| | |b) ((33) = (3-1)*(11-1) = 20 |

|2. Step: |a) Choose a public encoding key e that has to be |a) Here, possible values for e are 3, 7, 9, 11, 13, |

|Encryption |relative prime to ((n). |17, 19. Let’s pick e=3. |

|uses the public key |b) We now encrypt each plain letter P by computing |b) We encrypt as follows: |

|(n,e) | | |

| |C=Pe MOD n. |S =18: 183 = 24 MOD 33 |

| | |A = 0: 03 = 0 MOD 33 |

| | |F = 5: 53 = 26 MOD 33 |

| | |E = 4: 43 = 31 MOD 33 |

|3. Step: |a) The private decoding key d is chosen as the |a) d=7 since 3*7 = 1 MOD 20. |

|Decryption |inverse of e MOD ((n): e * d = 1 MOD ((n) | |

|uses the private key|Mathematically, find integers d and k that fulfill: e|b) |

| |* d = 1 + k * ((n) via the Extended Euclidean |247 = 18 MOD 33, 18=S. |

|(d,n) |Algorithm. |07 = 0 MOD 33, 0=A. |

| | |267 = 5 MOD 33, 5=F. |

| |b) We decrypt by computing P=Cd MOD n |317 = 4 MOD 33, 4=E. |

Remark: I computed the above powers MOD 33 using the Windows 98 calculator. Let’s verify by hand that i.e. the computation of 317 actually yields 4 MOD 33:

Since 31= -2 MOD 33 I can just multiply –2 by itself 7 times to compute (-2)7 and obtain –128. Now, –128 = -95 = -62 = -29 = 4 MOD 33 which produces the calculator answer.

Exercise 4: Verify the above RSA example and encrypt other words by clicking here.

4.3 Why does RSA work? – A Proof

Why does the RSA Cipher work? With other words: for what miraculous reason does the final exponentiation Cd MOD n in step 3 yield the correct plain letter P ? Nobody would use the RSA encryption to encrypt highly sensitive data if RSA’s encryption scheme is not guaranteed to yield the original plain text. Therefore, it is important to mathematically prove its correctness. The proof demonstrates how Rivest, Shamir and Adleman took advantage of Euler’s Theorem. We studied this theorem already in chapter 3, now you understand why we did so.

Proof of Correctness of the RSA Cipher

We saw in the above example that the decryption yields the proper plain text SAFE. Will it always – for any given plain text – work ? To be sure, we have to prove that the final exponentiation in the decryption process, Cd, is guaranteed to yield the proper plain letter P. In order to do so we have to distinguish two cases:

I) The vast majority of plain letters values P are relative prime to the modulus n. For this case we take advantage of Euler’s Theorem to prove the correct functioning of RSA.

II) We also have to prove the correctness of RSA for the rare instances when P is not relative prime to n. i.e. P and n possess a common divisor that is greater than 1.

I) RSA-proof when P and n are relative prime

We establish that Cd actually yields P by using a chain of identities that involves simple exponent rules and Euler’s Theorem. Verify each step in the proof.

| Cd |The cipher letter C was encrypted by raising the original plain letter P to the power of |

| |e: C=Pe. We substitute: |

|= (Pe)d MOD n |When raising a power to a power, we multiply the exponents: |

|= P d*e MOD n |The decoding key d was chosen to be relative prime to the encoding key e which can be |

| |stated as: |

| |d*e = 1 + k * ((n). Therefore, |

|= P 1 + k * ((n) MOD n |Adding exponents allows to multiply powers: |

|= P 1 * P k * ((n) MOD n |Multiplying exponents allows raising a power to a power: |

|= P * (P ((n) )k MOD n |What is the purpose of setting up (P ((n) ) ? Answer: To make use of Euler’s Theorem: P |

| |((n) = 1 MOD n when P and n are relative prime. If P and n don’t happen to be relative |

| |prime RSA still works properly. I will prove this case in part II) of the proof. |

|= P * (1)k MOD n |Raising 1 to any power yields 1. Guaranteed. |

|= P MOD n |The proof is complete. We verified that Cd yields P in case P and n are relative prime. |

II) RSA-proof when P and n are not relative prime

In that case P and n have a common divisor. Consequently, either p or q must be a divisor of P. This results from the choice of n as the product of the primes p and q. In other words, p and q are the only divisors of n and any divisor that n has in common with P must be either p or q or a multiple of p or q. Without limiting the generality of our proof, we assume that p is a divisor of P. That means that there exists an integer x such that P = x * p.

In the first proof, we made use of Euler’s Theorem. We now make use of its simplified version, the so-called “Fermat’s Little Theorem”. If the modulus is a prime number p, the exponent simplifies to ((p) = p-1. Why is that? Recall from chapter 3 that Euler’s (-function ((n) gives the number of integers less than n that are relative prime to n.

Fermat’s Little Theorem

Given a prime p, then

ap-1 = 1 MOD p

holds true for any integer a.

We start with Fermat’s Little Theorem to prove that Pde = P MOD n. I will simultaneously show you an example in the 3rd column.

|Fermat’s Little Theorem with the prime q holds |Pq-1 = 1 MOD q |If p=5 and q=7 then n=p*q=35. Let’s |

|true for any integer P. We manipulate the | |encrypt the message P=10. Then |

|exponent by raising both sides to the power of | |107-1 = 106 = 1 MOD 7 is |

|(p-1)*k for some integer k. | |guaranteed true because of Fermat’s |

| | |Little Theorem. |

|Raising powers to powers allows multiplying |(Pq-1 )(p-1)*k = 1(p-1)*k MOD q |(106)4*k = 14*k = 1 MOD 7 |

|exponents. | | |

|Why did we do so? Because |P(q-1)*(p-1)*k = 1 MOD q |106*4*k = 1 MOD 7 |

|(p-1)*(q-1)*k | |We choose d=5 and e=5 so that they are |

|= ((p*q) * k | |inverse MOD 24 where 24 = ((35) = |

|= ((n) * k | |(7-1)*(5-1) since 5 * 5 = 25 = 1 MOD 24.|

|= de –1 | | |

|when choosing d and e to be inverse mod ((n) . | | |

|We may therefore write | | |

|Subtracting 1 on both sides yields |Pde-1 = 1 MOD q |With k=1: |

| | |106*4*k = |

| | |10d*e-1 = |

| | |105*5-1 = 1 MOD 7 |

| | | |

|(Adjusting the modulus) |Pde-1 - 1 = 0 MOD q |105*5-1 –1 = 0 MOD 7 |

|If Pde-1 - 1 is a multiple of q then p* (Pde-1| | |

|- 1) must be a multiple of p*q. Consider a simple| | |

|example with p=2: If 15 is a multiple of 5 then | | |

|30 is a multiple of 10. | | |

|Can you finish the proof without looking at the | | |

|remaining proof? Try it, it is not difficult. |p*(Pde-1 - 1) = 0 MOD p*q |5* (105*5-1 –1) = 0 MOD 7 * 5 |

|(Obtaining Pde = P ) Since P is a multiple of p | | |

|P*(Pde-1 - 1) must also be a multiple of p*q. |p*(Pde-1 - 1) = 0 MOD p*q |5* (105*5-1 –1) = 0 MOD 35 |

|Continuing our example P=7*p: If 30 is a | | |

|multiple of 10 then 7*30 = 210 is also a multiple| | |

|of 10. | | |

|Distributing yields | | |

| |P*(Pde-1 - 1) = 0 MOD p*q |10* (105*5-1 –1) = 0 MOD 35 |

|Adding P on both sides and substituting n for p*q| | |

|concludes our proof. |Pde - P = 0 MOD p*q |105*5 – 10 = 0 MOD 35 |

|We verified that P’ = P when P and n are not | | |

|relative prime. Combining the proofs I) and II), |Pde = P MOD n |105*5 = 10 MOD 35 |

|we understand why the RSA encryption works | | |

|properly in any case. | | |

We considered already an example when P and n are relative prime. Let’s now consider two simple examples for the case that P is a multiple of p.

Example 1: Say we choose p=3 and q =5 as two small distinct primes. Then: n = p*q = 15 (allowing us to only encrypt 15 letters) and ((15) = 2*4 = 8. We may therefore choose the keys to be e = 3 and d = 3 since their product yields 9 and 9 = 1 MOD 8 where 8 = ((15). It is coincidence that the encryption key equals the decryption key. Instead, we could have also chosen e = 3 and d = 11 (since 33 = 1 MOD 8) or e = 3 and d = 19 (since 57=1 MOD 8). Or e = 5 and d = __ ? Do not miss to fill in the answer. Then continue!

Let’s now select a plain letter P such that it has a common divisor with n = 15, say we have to encrypt letter P = 6. We have to verify that Pde = P MOD n (here 69 = 6 MOD 15).

Since 62 = 36 = 6 MOD 15, we deduce that 68 = 62 * 62 * 62 * 62 = 6 * 6 * 6 * 6 = 62 * 62 = 6 * 6 = 62 = 6 MOD 15.

Thus, 69 = 68 * 6 = 6 * 6 = 6 which shows that the RSA scheme decrypts the correct plain letter P = 6.

Exercise1: (Test your understanding) Why would it be incorrect to argue as follows: Euler’s Theorem yields 6((15) = 68 = 1 MOD 15 and therefore 69 = 68 * 6 = 1 * 6 = 6 MOD 15. Even though the final answer is correct, where is a mistake in my argument? We computed correctly in example 1 that 68 = 6 MOD 15.

Example 2: Let’s now verify that RSA decrypts the plain letter P = 12 correctly. For that, we have to verify that 129 = 12 MOD 15. Since 122 = 144 = 9 MOD 15 and 124 = (122)2 = 92 = 81 = 6 MOD 15, we know that 128 = (124)2 = 62 = 36 = 6 MOD 15. This leads us to the final result: 129 = 128 *12 = 6 *12 = 72 = 12 . Correct.

Exercise 2: Prove that the plain letter P = 10 will be decrypted correctly by showing that 109 = 10 MOD 15.

Exercise 3: Prove that the plain letter P = 8 will be decrypted correctly by showing that 89 = 8 MOD 15.

4.4 Why is RSA secure?

You may say now: RSA does not fulfill the above mentioned Public-Key-Property since we could derive the decoding key d=7 from the encoding key e=3 and ((33)=20. I admit, you are right. However, the crux of the RSA cryptosystem is that it can be upgraded so that even though everybody knows the modulus n, not even the best eavesdropper is able to compute ((n).

How can the RSA Cipher be upgraded to a secure cipher?

Answer: Choose the two primes p and q to be at least 100-digit numbers.

Why does that make RSA secure? Because no eavesdropper (not even the NSA or the FBI) is able to compute ((n) from the publicly known modulus n since its factors p and q – required to compute ((n) as ((p*q) = (p-1) * (q-1) - can not be derived from n. As experienced computer experts, Rivest, Shamir and Adleman knew that the multiplication of two large numbers is not difficult, however, finding the factors of a given large integer is a difficult computer problem.

I.e. we easily find that

| 35 = 7 * 5 |or |

| 70 = 7 * 5 * 2 |or |

| 69 = 3 * 23 |or |

| 221 = 13 * 17 |and using some trial and error even |

|11413 = 113 * 101 | |

A factoring program quickly finds the factors of 20-digits numbers such as

|10726291417797115873 = 1223233789 * 8768799157 |

However, even today’s best factoring programs can not find the factors of 196-digit numbers such as

1072629139784206448651876669948737985105534479415491719546499789238601953099099917195464891606235569002029020617284133518518580548148163084320989148925926075485185203509876558141111112930000042837

Exercise2:

Realize that the multiplication of large numbers can easily be performed by a computer. Verify that the product of the following two 98-digit numbers

12232337897777777778888888889333333333444444444455555555556666666666777777777888888888900000000327

and

87687991351111111111222222222233333333334444444444555555555566666666677777777778888888890000000131

yields the above 196-digit number by using the java applet prime.htm .

Reflection on the Security of the RSA Cipher:

Among the many possible ways of attacking the RSA Cipher, factoring is the most promising one. Fact is that sufficiently large integers can not be factored, even when using the best factoring algorithms on the fastest computers in the world. In section 4.4.3 I will specify what I mean by “sufficiently large”. Consequently, if n is chosen sufficiently large nobody is able to find the factors p and q of n and thus nobody can compute ((n) in order to then identify the decoding key d. I will show you mathematically that the ability to find the factors of n is equivalent to the ability to compute ((n). The equivalence is based on the following two facts:

I) Knowing the factors p and q is sufficient to compute ((n) since ((n) = ((p*q) = (p-1) * (q-1). I showed you already that if p=3 and q=5 then ((15) = ((5)* ((3) = 4 * 2 = 8.

II) “Knowing ((n) and the publicly known value n is sufficient to find the factors p and q” can be seen as follows:

We know that n = p*q and that ((n) = (p-1)*(q-1). How could Mr. X use the two identities to compute p and q? We know how to solve two equations with two variables if only we can set up two equations that allow us to eliminate either p or q. Here is how:

((n) = (p-1)*(q-1)

= (p*q - p - q + 1)

= (p*q – [p + q] + 1)

= (n – [p + q] + 1)

Solving for p+q yields:

p+q = n - ((n) +1 (2)

We managed to express p + q in terms of n and ((n). If additionally we manage to express the difference of the two primes, p – q, in terms of n and ((n) we can use those two equations to compute p and q. So, let’s express p – q in terms of n and ((n).

|(p-q)2 = (p-q) * (p-q) = p2 – 2*p*q + q2 . | |

|(p+q)2 = (p+q) * (p+q) = p2 + 2*p*q + q2 . | |

|(p-q)2 - (p+q)2 = - 4*p*q . |This equation stems from subtracting the two|

| |previous equation. We add (p+q)2 on both |

| |sides. |

| (p-q)2 = (p+q)2 - 4*p*q |Taking the square root yields. |

| p-q = [(p+q)2 - 4*p*q]1/2 |We are done since we can express (p+q) as (n|

| |- ((n) +1) replace and p*q as n |

| p-q = ( n - ((n) +1)2 - 4*n]1/2 (3) |Combining the equations (2) and (3) yields |

| p+q = n - ((n) +1 | p and q can be derived by solving a 2 by 2 |

|p -q = [( n - ((n) +1)2 - 4*n ]1/2 |system. |

Example 2: Say an eavesdropper knows that ((n) = 30600 in addition to the publicly known n = 31003. To find p and q, he uses the identities (2) and (3) to set up the 2 by 2 system

p + q = n - ((n) +1 = 31003 – 30600 + 1 = 404 (2)

p - q = [( n - ((n) +1)2 - 4*n]1/2 = (404)2 - 4*31003 = 198 (3)

He just has to solve the 2 by 2 system for p and q. How? This is left as an exercise for you:

Your answer should be p=301 and q=103.

Exercise 2: Find the factors p and q of n using n = 31003 and ((n) = 30600.

This section can be summarized as follows:

(SECURITY OF THE RSA-CIPHER:

Since finding the factors of a huge integer n [without knowing ((n)] is difficult, the RSA encryption is secure.

4.4.1 Multiplication is a “One-Way Function” for Large Integers

The inability to crack RSA is based mathematically on the inability to factor the product n into the two huge primes p and q. However, the reverse process, computing the product given the two primes was easy as I showed you above. A function with such property is called a one-way function.

Definition of a one-way function:

A one-way function is a function that computes the result (i.e. the product of two primes) easily. However, given the result it is practically impossible to compute the original values.

Mathematically stated: Given x, f(x) can be computed easily. However, given f(x), computing x is practically impossible.

Example1: RSA’s one-way function is f(p,q) = p*q = n since n does not yield p and q if chosen sufficiently large.

Among other conceivable one-way functions, Rivest, Shamir and Adleman’s choice turned out to be a good one since no Mathematician has been able to design a fast factoring algorithm to make the one-way function “Multiplication of large numbers” a two way function. Nevertheless, if somebody devises an algorithm to factor huge integers quickly the RSA encryption is not secure anymore. Believe me: Designing fast factoring algorithms is a hot topic in current mathematics research, particularly to assess the security of RSA. Although there has not been a major breakthrough, the combination of refining the existing factoring algorithms (such as the number field sieve to name the currently best factoring algorithm for numbers consisting of 110 digits and more) with the ever-increasing power of computers yields new factoring records.

4.4.2 RSA Factoring Challenge

In fact, there is an ongoing factoring challenge, the so-called RSA factoring challenge, open for everyone to participate. You can find the latest factoring records on the internet at . The factoring list keeps RSA-users informed about factoring records. At the time of writing in spring 2001, the largest number that an alliance of groups of computer scientists with many powerful computer were able to factor consists of 155 digits. This 155 digit number named “RSA-155” consists of 512 bits. In summer 1999, the following email was sent around the world

On August 22, 1999, we found that the 512-bits number RSA-155 = 1094173864157052742180970732204035761200373294544920599091384213147634 9984288934784717997257891267332497625752899781833797076537244027146743531593354333897

can be written as the product of two 78-digit primes:

102639592829741105772054196573991675900716567808038066803341933521790711307779 *

106603488380168454820927220360012878679207958575989291522270608237193062808643

The number RSA-155 is taken from the RSA Challenge list. This factorization was found using the Number Field Sieve (NFS) factoring algorithm, and beats the 140-digit record RSA-140 that was set on February 2, 1999, also with the help of NFS. The amount of computer time spent on this new factoring world record is estimated to be equivalent to 8000 mips years. For the old 140-digit NFS-record, this effort was estimated to be 2000 mips years. 124 722 179 relations were collected by eleven different sites, distributed as follows:

• 20.1 % (3057 CPU days) Alec Muffett

• 17.5 % (2092) Paul Leyland

• 14.6 % (1819) Peter L. Montgomery, Stefania Cavallar

• 13.6 % (2222) Bruce Dodson

• 13.0 % (1801) Francois Morain and Gerard Guillerm

• 6.4 % (576) Joel Marchand

• 5.0 % (737) Arjen K. Lenstra

• 4.5 % (252) Paul Zimmermann

• 4.0 % (366) Jeff Gilchrist

• 0.65 % (62) Karen Aardal

• 0.56 % (47) Chris and Craig Putnam

The total calendar time for factoring RSA-155 was 5.2 months (March 17 - August 22) excluding polynomial selection time, whereas RSA-140 took about 9 weeks.

Exercise 6: The next number on the challenge list is RSA-160:

RSA-160 =

2152741102718889701896015201312825429257773588845675980170497676778133145218859135673011059773491059602497907111585214302079314665202840140619946994927570407753.

Yes, RSA-160 consists of 160 digits and can be factored into two primes each consisting of about 80 digits. Therefore, I wrote a java applet that generates five prime numbers at random each consisting of about 80-digits. Run the applet (have patience with the computations since it takes a while to generate the 80-digit prime numbers) and see if you are the first person in the world to factor a 160-digit number. I should inform you though that the chances of being successful are lower than winning the New York lottery. However, it is free to participate. You may want to run your computer overnight, the applet stops automatically if it finds a factor of RSA-160. To start the java applet click here.

4.4.3 Why was the RSA-155 Challenge particularly meaningful for Public-Key-Cryptography?

The reason is simple yet extremely relevant in terms a choosing the modulus n. A number with 155 decimal digits has about 512 binary digits which is exactly the modulus length n presently used by some RSA based encrypting systems. This justifies why in particular a 155-digit number was challenged.

The entire RSA challenge consists of a list starting with 100-digit and ending 500-digit numbers incrementing in steps of 10 digits. The RSA challenge number with tag "RSA-nnn" has “nnn” decimal digits. Therefore, the RSA challenge numbers are thus tagged RSA-100, RSA-110, RSA-120, ... , RSA-500. Additional "landmark" RSA Challenge numbers (added on February 7, 1997) are RSA-155, RSA-232, RSA-309 and RSA-617.

These four additional RSA-numbers are the size of the commonly used keys of bit-length 512, 768, 1024 and 2048. Even though the RSA-155 challenge took almost half a year and required a major combined effort, the challenge of cracking keys consisting of 155 decimals (= 512 bits) was proven to be feasible. Since computer speed is still increasing rapidly and more factoring expertise is gained we can expect that even larger keys will be cracked. However, it is believed that the last integer on the RSA challenge list, RSA-617: a 617-decimal or 2048-bit number, will not be factored with the known factoring methods for a long time. Don’t expect any Mathematician to specify any time periods. Firstly, who is to say that a faster factoring is going to be found tomorrow. Secondly, Computer Scientists are trying to build super computers that would factor 100 digits number in a matter of seconds. Such computers are called quantum computers and are currently researched worldwide.

What are the implications of the above-mentioned factoring challenge for the security of RSA encryptions? Choosing the key length n wisely becomes crucial when transferring sensitive information. Choosing a public key length i.e. of 768 bits (232 decimal) or 1024 bits (309 decimal) digits is recommended today, such keys are presently out of reach and thus secure. Choosing 2048-bits keys is beyond any doubts (since RSA-617 is far from being factored) and should be chosen today in order to avoid too frequent future key changes. Certainly, the payoff is speed. Greater key sizes slow the computerized encryption process down. A compromise has to be made. I will show you in section 4.6 how so-called “hybrid cryptosystems” incorporate the RSA Cipher without suffering from RSA’s speed deficit.

4.4.4 How else could RSA be cracked?

In order to make a cipher airtight we have to consider any conceivable attack that Mr.X could attempt. Which ones are there?

The good news for RSA users are: Among the many possible RSA attacks, the only promising attack known these days is the factoring method that I described to you in the previous section. The status quo is: Cracking the RSA encryption is at most as difficult as factoring huge numbers. By that I mean that there might be other conceivable attacks that have not been discovered yet which may turn out to be easier than solving the factoring problem. The German cryptographer Albrecht Beutelspacher[6] thinks that “Introducing a crypto-system whose strength is based on the fact that no Mathematician has come up yet with a reasonable factoring algorithm is a massive insult for the Mathematicians.”

4.5 Digital Signatures and RSA

How can a sender prove his authenticity? Besides eliminating the key exchange, proving that authenticity was a major quest that RSA realized in the late 70’s. Understanding how the RSA encryption scheme works and why it properly decrypts cipher messages will help you understand how to digitally sign documents. In fact, you may be able to discover it for yourself since RSA’s digital signature uses both the public and private keys that are used for the RSA encryption.

Hint: The RSA encryption requires you to use the publicly known encryption key (eR,nR) of the recipient, however, the RSA signature requires the sender to use his private decryption key (dS,nS).

An additional reason for the popularity of the RSA cryptosystem is the following: Not only can we encrypt or digitally sign a document, we can even do both for the same document! We first encrypt using the recipient’s encryption key (eR,nR) to afterwards sign the encrypted message using our private decryption key (dS,nS). In this section I will demonstrate to you how this can be achieved.

Exercise 1: Try to devise the RSA digital signature.

4.5.1 How to Sign a Digital Document using RSA

Recall one of the quests of cryptography: How can a sender prove his authenticity?

A hand-written text is signed by pen to document the authenticity of the sender. Observe that the sender uses unique personal information - a secret that only he possesses to prove his authenticity. Similarly, in order to digitally sign a document the sender has to possess a unique information that nobody else is able to figure out or copy. Now it is your turn: How can RSA be used to digitally sign a document? What does an RSA user possess that nobody else knows about? Of course, it is his private decryption key (dS,nS). Again, if only the modulus n is chosen sufficiently large (i.e. 1024 bits) nobody and no computer in the world is capable to compute the private key (dS,nS) based on the publicly known encryption key (eS,nS). In fact, since private keys can not be forged whereas pen-signatures can, digital signatures are even more trustworthy than traditional signatures.

It is now time to sign a document. Say Alice wants to send a signed letter to Bob.

Example of the RSA Digital Signature scheme:

The RSA Digital Signature Example:

|Step: |Alice has to generate a key pair (as explained in |Using the key pair in the introductory example we have|

|Preparation: |4.1). As before, he has to keep the private key (d,n)|(d,n) = (7,33) |

| |secret and makes the public key (e,n) publicly known.|(e,n) = (3,33) |

| | | |

|2. Step: |The sender applies his private key to the document P |SAFE is signed with d=7: |

|Signing the document P |in S = Pd Mod n to obtain the signature S which is |S =18: 187 = 6 MOD 33 |

|uses the private key |sent to the recipient. Additionally, the original |A = 0: 07 = 0 MOD 33 |

|(d,n) |message P is sent to the recipient as well. |F = 5: 57 = 14 MOD 33 |

| | |E = 4: 47 = 16 MOD 33 |

|3. Step: |Bob verifies the authenticity of the sender by |The authenticity of the message is verified by the |

|Verifying the |computing Se MOD n. He then matches Se with P. If |recipient using the senders public encoding key e=3 |

|authenticity of the |they are not equal, the document is not authentic. | |

|sender by applying the |Attention: fraud or a possible computation error has |63 = 18 MOD 33, 18=S. |

|public key (e,n) |occurred!! |03 = 0 MOD 33, 0=A. |

| | |143 = 5 MOD 33, 5=F. |

| | |163 = 4 MOD 33, 4=E. |

Exercise 1: Say you are Alice. You want to digitally sign the document “FRAUD” using n=5*7 = 35. First you will have to generate a key pair, secondly you sign FRAUD and send “FRAUD” together with the signed version of “FRAUD”. Now, pretend you are the recipient Bob. Firstly, you un-sign Alice’s signed message. Secondly, you check the authenticity of Alice’s message simply by matching the un-signed message with the original message “FRAUD”. For the necessary MOD calculations make use of the windows calculator.

Exercise 2: Does the RSA-signature require large key lengths just as the RSA-encryption does? Or would you accept Alice’s authenticity based on the key pair used in our example above?

Exercise 2 should have been easy for you. Attention: since the small key (e,n) = (3,33) is publicly known we can easily factor 33 into 3 * 11 to then compute ((33)= (3-1)*(11-1) = 20. Since e=3, the secret encryption key can be easily derived as d=7 since 3*7=1 mod 20. This empowers an eavesdropper to forge any message since he possesses the personal secret (d,n) of the sender – the equivalence of being able to fake a pen-signature perfectly. Once a sender has disclosed his secret key/trait he gives up the power to uniquely authenticate himself.

Exercise 3: Which of the following may be used as means for authentication that may not be altered or passed on and are thus secure: Fingerprint, passport, high school diploma, your eyes, your best friend, your mother, your picture ID.

4.5.2 How to Encrypt AND Digitally Sign with RSA

In the previous section, we learned how Alice may sign a document that can be sent i.e. as an email to the recipient. Since she did encrypt “FRAUD”, it was like sending a signed postcard to authenticate the sender. What if she wants to add security and decides to sign and encrypt her message? Sending an encrypted and signed letter electronically corresponds to signed postcard that is mailed in a sealed envelope. How can Alice accomplish this electronically?

Exercise 1:

1) Devise a scheme with which a sender can encrypt and sign a message before sending it?

2) How does the recipient of the message decrypt and verify the authentication? Before you start complete the following diagram.

Encrypts with (eB,nB) Digitally signs with____?____

Bob verifies authenticity with (eA,nA)

and __?____ with (dB,nB).

The combined RSA scheme: Encryption and Digital Signature

The combined RSA scheme Example:

|Step: |a) Alice has to generate a key pair (as explained in |Alice wants to encrypt and sign “FRAUD”. |

|Preparation: |4.1). She has to keep her private key (dA,nA) secret |Alice uses the key pair |

| |and makes her public key (eA,nA) publicly known. |(dA,nA) = (5,35) and (eA,nA) = (5,35) |

| |b) She has to know Bob’s public encoding key (eB,nB) |Since n = 35 = 5 * 7 we obtain ((35)= (5-1)*(7-1) = 24|

| |. |and choose e=5 (which is relative prime to 24) and |

| | |d=5. |

| | |Bob’s key pair is |

| | |(dB,nB)=(7,33) and (eB,nB) = (3,33) |

|2. Step: |Alice uses Bob’s public encoding key (eB,nB) to |She encrypts FRAUD using (eB,nB) = (3,33): C = Pe |

|Encrypting the document|encrypt the document P: C = Pe MOD nB |MOD nB |

|P | |F = 5: 53 = 26 MOD 33 |

|uses the public | |R =17: 173 = 29 MOD 33 |

|encoding key (eR,nR) of| |A = 0: 03 = 0 MOD 33 |

|the recipient. | |U =19: 193 = 28 MOD 33 |

| | |D = 3: 33 = 27 MOD 33 |

|3. Step: |Alice applies her private key (dA,nA) to the document|To sign the document C she uses her private key |

|Signing the document C |C: |(dA,nA) = (5,35): |

|uses the private key |S = Cd MOD nS |Cd = S MOD nA |

|(dS,nS). |and sends the signature S to the recipient Bob. |265 = 31 MOD 35 |

| |Additionally, the encrypted message C is sent to Bob.|295 = 29 MOD 35 |

| |(Why not P ?) |05 = 0 MOD 35 |

| | |285 = 28 MOD 35 |

| | |275 = 27 MOD 35 |

|4. Step: |Bob may verify the authenticity of the sender by |Bob verifies the authenticity of the document with |

|Verifying the |computing |(eA,nA) = (5,35). |

|authenticity of the |Se MOD nA |Se = C MOD nA |

|sender by applying the |and checking if Se = C. If they don’t match, the |315 = 26 MOD 35 |

|public key (eB,nB) of |document is not authentic. Attention: fraud or a |295 = 29 MOD 35 |

|the recipient. |possible computation error has occurred!! |05 = 0 MOD 35 |

| | |285 = 28 MOD 35 |

| | |275 = 27 MOD 35 |

| | |We observe that C’=C which authenticates the sender. |

|5. Step: |The recipient finally decrypts the cipher C by |Bob decrypts using (dB,nB) = (7,33). |

|Decryption |computing P’ = Cd MOD nB. We proved already that P’ =|Cd = P’ MOD nB |

|The recipient uses his |P for all P. |267 = 5 MOD 33 5 = F |

|private key | |297 = 17 MOD 33 17 = R |

|(dB,nB) . | |07 = 0 MOD 33 0 = A |

| | |287 = 19 MOD 33 19 = U |

| | |277 = 3 MOD 33 3 = D |

The encryption and authentication process is straightforward and does not seem to cause any trouble - even if the recipient's modulus nR turns out to be larger than the modulus of the sender nA. I.e. imagine we switch the above moduli to nB = 35 and nA= 33. When reaching the signing stage (step 3) we handle the 33 integers 0-32 and after the encrypting stage (step 2) we may obtain the 35 integers between 0-34. Here, the integers 0 and 33, 1 and 34 as well as 2 and 35 are signed in the same manner so that C' = C allowing a proper digital signature.

Exercise 1: Encrypt, sign, authenticate and decrypt the document “CODE” using nB = 35 and nA= 39. Again, you first have to determine the encryption and decryption keys in step 1. Subsequently, execute the steps 2 - 5.

4.6 RSA in Practice

How is RSA practically used? I mentioned to you already that the RSA encryption is quite slow because of the large keys that have to be used to ensure security. For the same reason, RSA’s digital signatures are slow as well: The length of the transmitted signature equals the length of the transmitted message. In other words: The longer the message, the longer the digital signature. This does not resemble pen signatures which is independent of the length of the document. Consequently, although RSA is a cutting edge cipher it is too slow to encrypt or sign messages in a reasonable amount of time. Is RSA one of the most brilliant yet unuseful inventions in history? No, it is not. Let’s study how RSA can practically be used?

RSA is practically used to encrypt keys of secure symmetric ciphers.

You may think that this sounds weird. Why are keys encrypted? Aren’t they used to encrypt messages? True. However, RSA is only of practical use if coupled with a fast executing symmetric cipher. I will explain to you what I mean by that in the next section.

4.6.1 Modern Cryptosystems are Hybrid

The term “hybrid” is borrowed from the natural sciences, it means “crossbreed”. Cryptographically, it refers to the combination of symmetric and asymmetric ciphers: The fast encryption speed of symmetric ciphers is coupled with the security of asymmetric ciphers such as RSA. Certainly, breakable symmetric ciphers such as the Caesar or the Linear Cipher are not used. Rather, the so called “IDEA Cipher” is commonly used for hybrid cryptosystems. The fast executing IDEA stands for “International Data Encryption Algorithm” and is considered a secure symmetric cipher. (It has withstood any breaking attack.) IDEA was developped in 1991 by professor Jim Massey, ETH Zurich, Switzerland, and his student Xuejia Lai. Its mechanism is too convoluted to be explained in a few sentences. However, it is important for us to know that the IDEA keys consist of only 128 bits. Such keys are encrypted even with the slow RSA Cipher in milliseconds. Thus, time is not an issue for hybrid cryptosystems.

Encryption with a hybrid cryptosystem

How does a hybrid cryptosystem work? Imagine that a lengthy message has to be encrypted. Firstly, a secret IDEA key of length 128 bits is generated. Using this key, the message is encrypted in a quick manner. Afterwards, the key itself is encrypted with the recipient’s public encoding key. Finally, the encrypted key together with the encoded message is sent to the recipient. The recipient has to first decrypt the encrypted IDEA-key by using his private RSA decryption key. He obtains the IDEA key which he then uses to decrypt the IDEA-encoded message. The crux of this method: Even if Mr. X intercepts both pieces of the transmitted cipher text, he can’t crack anything. IDEA-encrypted messages are unbreakable, so is the RSA encrypted IDEA-key.

Before getting acquainted in section 4.6.3 with the most popular hybrid cryptosystems, the Pretty Good Privacy (PGP) encryption program, I want to first show you some important considerations when implementing the RSA Cipher.

4.6.2 RSA encrypts Chunks of Bits

Recall that the security of RSA depends on the size of the modulus n when choosing the public key (e,n). However, independent of the choice of n and e, same plain letters turn into the same cipher letters. Thus, RSA turns out to be a mono-alphabetic cipher ? Such ciphers can be cracked using letter frequency analysis. Say we encode a message using the 28=256 ASCII symbols. Thus, the cipher text consists of only 256 different symbols. An eavesdropper may intercept the corresponding 256 cipher numbers and perform frequency analysis on them to crack the cipher. He just doesn’t have to show any respect for the length of the cipher numbers. If the modulus n was chosen to be a 1024 bit-number to assure security each cipher number will be a number less than 21024. He could then start applying the technique to crack Monoalphabetic ciphers starting with the identification of the encrypted “e” etc.

Thus, the wonderful ideas of RSA’s one-way functions and the inability to factor n simply dissolve to a fata morgana? Simple frequency analysis is sufficient to crack RSA ciphers? Well, the success story of RSA would not endure if this were true. Therefore, let’s identify precisely the problem and then see how it can be solved.

The problem of the RSA encryption as used in our introductory example was that it was used as a mono-alphabetic cipher: We encrypted the plain text “SAFE” letter by letter and transferred the cipher text consisting of each cipher letter. How can we prevent using a breakable mono-alphabetic substitution? Can you guess what the standard crypto-trick is to disguise letter frequencies? I introduced the idea in the previous chapter for the Linear Cipher.

Answer: Instead of encoding letters individually, we simply form chunks of letters and encode the chunks.

Exercise 7: Try to think ahead and give a reasonable size for the chunks to be encrypted.

The plain numbers are 8-bit numbers defined by the ASCII-code. We combine these 8-bit numbers to form large plain numbers that must be less than or equal to the modulus n. How many 8-bit numbers does i.e. a 1024-bit modulus accommodate? 1024/8 = 128. Thus, chunks consisting of 128 plain letters can be encrypted at once.

… 8 8 8 8 8

1024 bits

Figure 4.1: A 1024-bit number can accommodate up to 128 8-bit blocks each representing one text symbol. The 8-bit numbers are entered from right to left so that the first letter is the outermost left letter.

Exercise 8: To get an idea how many lines you can write with 128 symbols count the symbols of this paragraph. Using MS WinWord you first have to highlight this paragraph. Secondly, go to Tools/Word Count and find out how many “characters with spaces” this paragraph contains. Using the “TimesNewRoman” size 12, how many lines would be encrypted at once with 128 symbols. What if we change the size to 10? For your information: The number of characters displayed by WinWord includes both letters and digits.

Mr. X is not able to crack the cipher text. He can not deduce the most frequent letter e anymore since it is just one among 128 symbols. He would have to perform frequency analysis on 128-letter “words” and use his knowledge on the distribution of 128-letter words in the English language. Mission impossible.

Exercise 9: Explain why there are 1.797693134862315907729305190789 * 10308, a 308-digit integer, many combinations of 128 symbols that fill up a 1024-bit number.

Exercise 10: Keys of length 2048 bits hold how many 128-letters chunks?

4.6.3 The most popular Hybrid Cryptosystem:

PGP or Pretty Good Privacy

In this last section I want to introduce you to PGP. PGP stands for “Pretty Good Privacy”, it is the most popular hybrid cryptosystem. In fact, it is the most successful public-domain encryption program. It is hard to believe that PGP is the product of only one person. Computer Scientist Phil Zimmerman developed PGP by himself and made it public in 1991. When Zimmerman first heard about Public-Key Cryptography in 1977 he was handling two jobs: One as a programmer and another unpaid post as "savior of the world." (You will find out what I mean by that by reading his Introduction to PGP below.) He was able to find a way to combine the two. Why not implement a public-key system on personal computers using the RSA algorithm?

Zimmerman’s motivation to create PGP and to make it public domain can be well understood by reading his Introduction to PGP[7]. Enjoy reading the following two pages that also give an insight to the ongoing political debate on the use of cryptography.

Find out why PGP helps preserve democracy:

It's personal. It's private. And it's no one's business but yours. You may be planning a political campaign, discussing your taxes, or having an illicit affair. Or you may be doing something that you feel shouldn't be illegal, but is. Whatever it is, you don't want your private electronic mail (E-mail) or confidential documents read by anyone else. There's nothing wrong with asserting your privacy. Privacy is as apple-pie as the Constitution.

Perhaps you think your E-mail is legitimate enough that encryption is unwarranted. If you really are a law-abiding citizen with nothing to hide, then why don't you always send your paper mail on postcards? Why not submit to drug testing on demand? Why require a warrant for police searches of your house? Are you trying to hide something? You must be a subversive or a drug dealer if you hide your mail inside envelopes. Or maybe a paranoid nut. Do law-abiding citizens have any need to encrypt their E-mail?

What if everyone believed that law-abiding citizens should use postcards for their mail? If some brave soul tried to assert his privacy by using an envelope for his mail, it would draw suspicion. Perhaps the authorities would open his mail to see what he's hiding. Fortunately, we don't live in that kind of world, because everyone protects most of their mail with envelopes. So no one draws suspicion by asserting their privacy with an envelope. There's safety in numbers. Analogously, it would be nice if everyone routinely used encryption for all their E-mail, innocent or not, so that no one drew suspicion by asserting their E-mail privacy with encryption. Think of it as a form of solidarity.

Today, if the Government wants to violate the privacy of ordinary citizens, it has to expend a certain amount of expense and labor to intercept and steam open and read paper mail, and listen to and possibly transcribe spoken telephone conversation. This kind of labor-intensive monitoring is not practical on a large scale. This is only done in important cases when it seems worthwhile.

More and more of our private communications are being routed through electronic channels. Electronic mail is gradually replacing conventional paper mail. E-mail messages are just too easy to intercept and scan for interesting keywords. This can be done easily, routinely, automatically, and undetectably on a grand scale. International cablegrams are already scanned this way on a large scale by the NSA.

We are moving toward a future when the nation will be crisscrossed with high capacity fiber optic data networks linking together all our increasingly ubiquitous personal computers. E-mail will be the norm for everyone, not the novelty it is today. The Government will protect our E-mail with Government-designed encryption protocols. Probably most people will acquiesce to that. But perhaps some people will prefer their own protective measures.

Senate Bill 266, a 1991 omnibus anti-crime bill, had an unsettling measure buried in it. If this non-binding resolution had become real law, it would have forced manufacturers of secure communications equipment to insert special trap doors in their products, so that the Government can read anyone's encrypted messages. It reads:

"It is the sense of Congress that providers of electronic communications services and manufacturers of electronic communications service equipment shall insure that communications systems permit the Government to obtain the plain text contents of voice, data, and other communications when appropriately authorized by law."

This measure was defeated after rigorous protest from civil libertarians and industry groups.

In 1992, the FBI Digital Telephony wiretap proposal was introduced to Congress. It would require all manufacturers of communications equipment to build in special remote wiretap ports that would enable the FBI to remotely wiretap all forms of electronic communication from FBI offices. Although it never attracted any sponsors in Congress in 1992 because of citizen opposition, it was reintroduced in 1994.

Most alarming of all is the White House's bold new encryption policy initiative, under development at NSA since the start of the Bush administration, and unveiled April 16th, 1993. The centerpiece of this initiative is a Government-built encryption device, called the Clipper chip, containing a new classified NSA encryption algorithm. The Government is encouraging private industry to design it into all their secure communication products, like secure phones, secure FAX, etc. AT&T is now putting the Clipper into their secure voice products. The catch: At the time of manufacture, each Clipper chip will be loaded with its own unique key, and the Government gets to keep a copy, placed in escrow. Not to worry, though -- the Government promises that they will use these keys to read your traffic only when duly authorized by law. Of course, to make Clipper completely effective, the next logical step would be to outlaw other forms of cryptography.

If privacy is outlawed, only outlaws will have privacy. Intelligence agencies have access to good cryptographic technology. So do the big arms and drug traffickers. So do defense contractors, oil companies, and other corporate giants. But ordinary people and grassroots political organizations mostly have not had access to affordable military grade public-key cryptographic technology. Until now.

PGP empowers people to take their privacy into their own hands. There's a growing social need for it. That's why I wrote it.

A Brief Introduction on “How to use PGP”

(An excerpt from the PGP manual[8])

PGP is a security software application that enables you and your co-workers to exchange or store information securely, so that no one else can read it. One of the most convenient ways to use PGP is through one of the popular email applications supported by the PGP plug-ins. With these plug-ins, you can encrypt and sign as well as decrypt and verify your messages while you are composing and reading your mail with a simple click of a button.

If you are using an email application that is not supported by the plug-ins, you can easily encrypt the text of the message using PGPtray. In addition, if you need to encrypt or decrypt file attachments, you can do so directly from the Windows clipboard by choosing the appropriate menu option. You can also use PGP to encrypt and sign files on the hard disk of your computer for secure storage, to securely wipe files from your hard disk and to wipe free disk space so that sensitive data can’t be retrieved with disk recovery software.

PGP is based on a widely accepted encryption technology known as public key cryptography in which two complementary keys, called a key pair, are used to maintain secure communications. One of the keys is designated as a private key to which only you have access and the other is a public key which you freely exchange with other PGP users. Both your private and your public keys are stored in keyring files, which are accessible from the PGPkeys window. It is from this window that you perform all your key management functions. For a comprehensive overview of PGP’s encryption technology, refer to “An Introduction to Cryptography,” which you can access by clicking here.

-----------------------

[1] Bruce Schneier: “Applied Cryptography: Protocols, Algorithms, and SourceCode in C” , 1996

[2] Phil Zimmermann: “An Introduction to Cryptography”, Copyright© 1990-1998 Network Associates, Inc.

[3] The British Mathematicians Ellis, Cocks and Williamson devised the public-key notion already in 1968/69 for the British Security Service, however, it had to remain secret. Diffie and Hellman’s discovered it independently.

[4] R.L. Rivest, A. Shamir, and L.M. Adleman, A method for obtaining digital signatures and public-key cryptosystems, Communications of the ACM (2) 21 (1978), 120-126..

[5] Whitfield Diffie: “The First Ten Years of Public-Key-Cryptography. In: G. Simmonds (ed.): Contemporary Cryptology. The Science of Informtaion Integrity. IEEE Press, New York, 1992.

[6] Albrecht Beutelspacher: “Geheimsprachen – Geschichte und Techniken” 1997.

[7] Phil Zimmerman: “Why do you need PGP? ” in chapter 1 of “Introduction to Cryptography” in the PGP 6.5.1 documentation. Copyright © 1990-1999 Network Associates, Inc. and its Affiliated Companies at

[8] Phil Zimmerman’s PGP 6.5.1 documentation. Copyright © 1990-1999 Network Associates, Inc. and its Affiliated Companies

-----------------------

ALICE

BOB

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

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

Google Online Preview   Download