1
Chapter 8:RSA Ciphers
So far, we have primarily examined historical ciphers. In each of these ciphers, the originator and receiver of an encrypted message had to agree on a common key, be it a numerical parameter, keyword, etc. The logistics involved in the originator and receiver agreeing on a common key can be cumbersome.
In this chapter, we introduce an idea that was revolutionary when it was developed in the 1970’s. In particular, we describe the idea of where the receiver can make part of the key public knowledge without any pre-agreement with the message sender. The algorithms in this chapter are part of several that we describe in upcoming chapters that are used to transfer information securely in today’s computer age.
8.1 Introduction to Public-Key Ciphers
When we access the security of a cipher, normally we examine the difficulty (or lack thereof) of the ability of the intruder to discover the cipher’s key. Normally, we assume factors like the alphabet assignment and the algorithm being used to be public knowledge. However, the encryption keys for acipher must be kept secret in order to prevent an outsider from acting asthe intended recipient of a message, determining the corresponding decryptionkeys, and decrypting the message.
However, this fact changed in 1976 with the discovery by Whitfield Diffie and Martin Hellman.
Whitfield Diffie Martin Hellman
Diffie and Hellman first explained to the world in their 1976 paper, the encryption keys for a cipher need not always be kept secret. Such ciphers in which the encryption keys need not be kept secret are called public-key ciphers, since the encryption keys can be known publicly without ruining their security. The (tremendous) benefit to this is that a public-key cipher can be usedby two parties who have no way to secretly agree upon encryption keys.
While Diffie and Hellman described the idea of public-key ciphers in their 1976 paper, they did not actually provide a specific type of publickey cipher. The first specific type of public-key cipher was revealed to the world two years later by Ron Rivest, Adi Shamir, and Len Adleman, atrio of researchers at MIT.
The purpose of this chapter is to describe the RSA algorithm, the background needed for its implementation, and its implementation.
8.2 Introduction to RSA Ciphers
RSA ciphers use modular arithmetic with the mathematical operation of raising to powers, or exponentiation. RSA ciphers also use prime numbers.A positive integer p > 1 is said to be prime if the only positive integers that divide p evenly are 1 and p. For reference, the prime numbers less than 100 are 2, 3, 5, 7, 11, 13, 17,19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, and 97.
The following describes the setup of how encipherment and decipherment works for the RSA Cryptosystem.
RSA Cryptosystem Setup
1. The intended recipient of the message chooses two primes p and q and computes the quantities
and.
Next, the recipient chooses a positive integer e(we refer to as the encipheringexponent) where the. The recipient then sends (or makes public) the values of e and m to the originator ofthe message over the insecure communication line.
2. Using an alphabet assignment to convert from English letters to numbers, we express the plaintext as integers x less than m. Assuming that , the originator of the uses the enciphering exponent e and mto encipher the message by computing
.
The originator then sends the resulting ciphertext integer(s) y to theintended recipient over the insecure line of communication.
3.To decipher the message, the recipientcalculates an integer d(we refer to as the decipheringexponent) where
.
Note that d is the multiplicative inverse of , that is .
Then for each ciphertext integer y, therecipient uses the deciphering exponent dand mto reverse the process of step 2 by computing
.
The alphabet assignment is used to recover the message.
Important Facts Concerning the RSA Cryptosystem
1.A common place that causes confusion when first learning the RSA is when to use m and f computed in step 1. The integer is the modulus used in enciphering and deciphering messages (to compute in step 2 and in step 3). The integerf = (p -1)(q – 1)is only needed in step 3 and is the modulus needed to find the multiplicative inverse of , that is .
2.The reason that the encryption exponent e must be chosen so thatgcd(e, f) = 1 is because this guarantees the existence of a correspondingdecryption exponent. Since gcd(e, f) = 1, the multiplicative inversewill exist, and this multiplicative inverse d is the corresponding decryption exponent.
3.In practice, the recipient makes the modulus m and enciphering exponent e public (everyone knows). The recipient keeps the primes p and q, f, and d secret.
4.When the ciphertext message is formed, the numerical results obtained are not
guaranteed to have a corresponding alphabet assignment letters for expressing the ciphertext in terms of letters. The ciphertext is normally left in numerical form.
Example 1:Using the primes p = 3 and q = 11 with enciphering exponent e = 7 and
alphabet assignment A= 0, B= 1, C= 2, …, Z= 25,to create a RSA scheme to
encipher the message USA.
Solution:
█
Some Suggested Textbook Exercises for Practice for Section 8.2
p. 281: # 1-4
8.3 The Euclidean Algorithm
For an affine cipher with encryption calculation y = (ax + b) mod 26 that we studied in Chapter 5, the multiplicative key a must be chosen so that gcd(a,26) = 1. This is toguarantee that the multiplicative inverse will exist. For anaffine cipher, verifying that gcd(a,26) = 1 was done by inspection and we will able to display all of the positive integers less than 26 that have multiplicative inverses in a table because the modulus 26 is so small. For an RSA cipher with primesp and q and f = (p−1)·(q−1), the encryption exponent e must be chosen sothat gcd(e, f) = 1, and must be determined. Since the modulusin an RSA cipher is typically much larger than 26, it is often impractical toverify that gcd(e, f) = 1 and find by trial and error. However, an old, well known, and very efficient algorithm can be used to calculate the greatest common divisor of two numbers and find multiplicative inverses, which we examine in this section.
The algorithm we use is known as the Euclidean Algorithm, which we state next.
The Euclidean Algorithm
The Euclidean Algorithm makes repeated use of the division algorithm to find the greatest common divisor of two numbers. Suppoe we are given two integers a and b where . If bdivides a evenly, then . If not, wecompute the following:
The last nonzero remainder, , is the greatest common divisor of a and b, that is, .
Example 2: Find the gcd(2299, 627).
Solution:
█
Example 3: Find the gcd(160, 17).
Solution:
█
Example 4: Find the gcd(52598,2541).
Solution:
█
Theorem:For any pair of positive integers a and b, integers s and texist such that
gcd(a, b) = sa + tb
Example 5: Find s and t where sa + tb = gcd(a, b), where a = 2299 and b = 627.
Solution:
█
Example 6: Find s and t where sa + tb = gcd(a, b), where a = 52598 and b = 2541.
Solution:
█
Why are we interested in solving for the remainders and producing s and t after using the Euclidean Algorithm? For an RSA cipher with primes p and q and f = (p−1)·(q−1), the encryption exponent emust be chosen so that gcd(e, f) = 1, and must be determined.
If gcd(e, f) = 1,then our previous theorem states that integers s and t will exist such that
Solving this equation for te gives
Reducing this equation modulo f gives
Thus, assuming gcd(e, f) = 1, which we could verify using the initial part ofthe Euclidean algorithm, to determine , we can solve for the remainders
to find integers s and t such that . The value of will be (note if , taking will convert the result to an easier to use positive result for the inverse)
Process for Finding Multiplicative Inverse
1. Use the Euclidean Algorithm to find If , the inverse will exist and you can proceed to step 2. If , the inverse will not exist and there is nothing else to do.
2.If , then solve for the reminders and find integers s and t such that .
3.If , the resulting value of t will be the multiplicative inverse . If , take and use the resulting positive value for the multiplicative inverse..
Example 7: Compute .
Solution:
█
Example 8: Compute .
Solution:
█
Example 9:Compute .
Solution:
█
Some Suggested Textbook Exercises for Practice for Section 8.3
p. 286: # 1-3
8.4 Maplets for the Euclidean Algorithm
Some Suggested Textbook Exercises for Practice for Section 8.4
p. 290: # 1-2
8.5 Modular Exponentiation
When we introduced the RSA algorithm in Section 8.1, we saw that encryption decryption was dependent on exponentiation. When the base and exponent are small, we can do the exponentiation and then apply the modulus.
However, when the bases and/or exponents become larger, problems can occur. For example, consider . Since , computing the result directly will cause roundoff (even one-digit of roundoff will lead to inaccurate results) or will cause many calculators to overflow due to the large numbers required in the calculation.
Fortunately, however a method known as binary exponentiation or successive squaring can be used to do modular exponentiation efficient. The method involves writing the exponent as a sum powers of two less than or equal to it, from largest to smallest. The base raised to these powers of two is then computed, where the next result is computed by squaring the result of the previous answer. We illustrate the technique in the following examples.
Example 10: Compute .
█
Example 11: Compute
Solution: We first note that the exponent . We first determine the powers of 2 that are less than this exponent. Starting with, we see that
, , , , , , , , ,
We can stop at since We now decompose the exponent k into powers of 2.
.
We next write
We next compute the needed powers of 77114 needed with respect to the modulus 1010189. The ones that we will need are indicated by . Note that arrows are used to indicate the substitutions from the previous step.
.
.
.
.
.
.
.
.
.
.
continued on next page
Hence,
█
Note:In Example 7, to compute by ordinary exponentiation, 682 multiplications are required. Using successive squares requires only 13 multiplications.
Some Suggested Textbook Exercises for Practice for Section 8.5
p. 295: # 1
8.6 Maplets for the Euclidean Algorithm
Some Suggested Textbook Exercises for Practice for Section 8.6
p. 297: # 1
8.7ASCII
Recall that primarily we have used the correspondences A= 0, B= 1, C= 2, …, Z= 25, to convert characters to numbers. The RSA cryptosystem in practice is executed on computers. The most common way for text to be stored on computers is through the American Standard Code for Information Interchange, or ASCII for short. The ASCII table for the computer keyboard characters is given as follows.
ASCII table for keyword characters
This table provides a much flexible alphabet, since it allows us to include not only capital letters, but lower case letters, punctuation, the space characters, and numerical digits in our messages as well. For example, the ASCII table to convert the characters of the message THE RSA WAS INVENTED IN 1978 to numerical form, which is displayed in the following table.
I / N / V / E / N / T / E / D / I / N / 1 / 9 / 7 / 8 / .73 / 78 / 86 / 69 / 78 / 84 / 69 / 68 / 32 / 73 / 78 / 32 / 49 / 57 / 55 / 56 / 46
T / H / E / R / S / A / W / A / S / I / N / V / E / N / T / E / D
84 / 72 / 69 / 32 / 82 / 83 / 65 / 32 / 87 / 65 / 83 / 32 / 73 / 78 / 86 / 69 / 78 / 84 / 69 / 68 / 32
For the rest of this book and all of the remaining sections, we will continue to use the ASCII correspondences for our alphabet assignments.
8.8 RSA Ciphers
In this section, we extend the results of Section 8.2 and look at how more realistic encryptions can be done with the RSA cryptosystem. Previously, in Example 1 in this section we used small parameters to encrypt message characters one character at a time. However, doing the encryption in this manner produces just a simple substitution cipher, which can be broken by frequency analysis. However, this problem can be eliminated by grouping our message into larger blocks. As long as the numerical plaintext numbers representing the blocks are less than the modulus m, encryption and decryption can be done properly.
Why is it necessary for the numerical plaintext to be less than m. To demonstrate why, consider the parameters in Example 1 of m = 33 and f = 20 (produced using the primes p = 3 and q = 11). Using the encryption exponent e = 7 and decryption exponent d = 3, suppose attempt to encipher the message RU as one block number and then attempt to recover the message. Using the ASCII table to convert characters to numbers, we convert RU to the block number 8285. Note that x = 8285 > 33 = m. To encrypt this message, we use e = 7 and compute
.
To recover the message, we use the deciphering exponent d = 3 and compute
.
Hence, the message is completely lost. Of course, this stemmed from the fact that in modulo m arithmetic, the only possible remainders are from 0, 1, …, m – 1, making it impossible to recover any numerical plaintext larger of m or larger.
To alleviate this issue, we much create larger parameters. By creating our primes p and q larger, hence making m larger, we can encrypt larger numerical plaintexts. We demonstrate how the process works in the next example.
Example 12:Demonstrate using the ASCII table for converting from characters to numbers, how to encrypt the message Mr. Edusing the primes p = 433 and q = 2333 with encryption exponent of e = 683.
Solution:
█
By creating our primes even larger, we can encrypt messages in even larger blocks. Example 8.14 on p. 301 of your textbook demonstrates an example. There are Maplets, which we will describe in the next section, which can also be used for this purpose.
Some Suggested Textbook Exercises for Practice for Section 8.8
p. 302: # 1-3
8.9Maplets for RSA Ciphers
Some Suggested Textbook Exercises for Practice for Section 8.9
p. 310: # 1-5
8.10 Cryptanalysis of RSA Ciphers
Recall that when the RSA cipher was first developed, it represented the first commercial public-key cryptosystem. This allows the message recipient to create their own key, publish their e and m values, and have any number of message originator’s send them encrypted messages. The information is kept secure as long as the message recipient can keep the decryption exponent d secret from any potential intruders. The following diagram illustrates this idea.
Figure 1: Public Key Cryptosystem Illustration\
So how does the recipient keep d secret? The security of the method is based on the following comments.
Security of the RSA
The security of the method is based on the message recipient keeping the deciphering exponent d secret. To keep d secret, the recipient must keep the primes p and q must be kept secret. If p and q can be secret, can be kept secret and cannot be computed.
It begs to differ, however, that if the recipient makes public so that the value of m is known to the world, how does this prevent an intruder discovering what the primes and are? Well, the answer comes down to this fact:
It is much easier to find primes and and form then it is to start
with m and factor it as .
This can be seen somewhat intuitively in that, for example, it is faster to see that p = 23 and q = 31 are primes and find , than it is to start with say , and as quickly find the primes that produced it (the answer is that p = 31 and q = 43).
It turns out the same idea works for computers. Computer algorithms for generating primes and and forming are astronomically faster than starting with m and factoring to find the primes and that produced it. This assumes of course that the primes and are sufficiently large. However, it turns out that the primes used in practice, which are normally at least 100 digits in length, can easily be generated and m can be quickly computed. However, the size of m produced by the product of two primes does not nearly have to be as astronomically large for the best known computer algorithms to fail to factor m as the product of its primes, at least in a reasonable amount of time. The fact is, when implemented correctly, RSA ciphers have proved thus far to be impregnable.
Example 13:Suppose the ciphertext 209 583, was produced with an RSA cipher with public key values m = 943 and e = 139. Decipher the message.
Solution:
█
Public-key ciphers have obvious advantages over non-public-key ciphers, as we have clearly discussed. However, there are disadvantages as well. One is that public-key ciphers are in general slower than non-public-key ciphers, which can be especially important for users who have a lot of information to transmit confidentially. Also, public-key ciphers can be exploited if messageauthentication (e.g., the assurance to the intended recipient of a messagethat it actually came from the originator claiming to have sent it) is compromised.We will consider this important aspect of public-key ciphers in Chapter 11.
Some Suggested Textbook Exercises for Practice for Section 8.10
p. 314: # 1
8.11 A Maplet for Cryptanalysis of RSA Ciphers
Some Suggested Textbook Exercises for Practice for Section 8.11
p. 318: # 1
8.12 Primality Testing
To create a secure RSA, it is necessary to generate large primes. One fact that is not overly difficult to prove is that there are an infinite number of primes. Therefore, a question one asks is that given a large positive integer, how do we determine if it is prime. Of course, 2 is the only even prime, and hence, any even number larger than 2 cannot be prime. How about large positive odd integers? In this section, we examine some elementary ways to determine if a number is prime or not, known as primalitytesting.
Fact: A number m is prime if it has no prime factors less than the (this this is called trial divisions). Why?
Example 14:Determine if 839 is prime.
Solution:
█
Example 15:Determine if 1073 is prime.
Solution:
█
Example 16:Determine if 1709 is prime.
Solution:
█
As the numbers tested get larger, trial divisions for primality testing does have limitations. For example, to try to determine if 84308508309887 is prime by trial divisions, we would begin by computing , and there would be many primes to test less than 9181966. In fact, is a number s is large, the number of primes less than or equal to s, which is denoted by , is approximated by the following formula: