The RSA Cryptosystem Ali Mohamed Abu Oam asam295@hotmail.com aaalll20002000@yahoo.com To encipher a message using the RSA cryptosystem, we first convert the message into a list of nonnegative integers by applying a mapping. We then choose distinct primes p and q and define n = pq and m = ?(n) = (p1)(q 1). Next, we choose a in Z*m such that (a,m) = 1, and find b in Z*m that satisfies ab = 1 mod m. (Recall that b can be found by constructing the Euclidean algorithm table for a and m.) To encipher the message, we form ciphertext integers by raising the plaintext integers to the power a and reducing modulo n. according to Theorem.5, we can then recover the plaintext integers by raising the ciphertext integers to the power b and reducing modulo n. Example.2 In this example, we use the RSA cryptosystem to encipher and decipher the message, "NCSU".( N =13, C = 2, S = 18 and U = 20 ) to convert this message into the list of integers 13 2 18 20. Next, we choose primes p = 5 and q = 11, and define n = pq = 55 and m = (p 1)(q  1) = 40. We then choose encryption exponent a = 27. To encipher the message, we perform the following calculations. 13^27 = 7 mod 55 2^27 = 18 mod 55 18^27 = 17 mod 55 20^27 = 15 mod 55 Where the notation (^) denote the power to ( 27 ). Hence, the ciphertext is the list of integers 7 18 17 15. (Although we could use ??1 to convert this particular list of integers back into a list of letters, conversion of an RSA ciphertext back into a list of alphabet characters is not usually possible. To see this, note that because the results of these encryption calculations were reduced modulo n = 55, these results could have been as large as n1 = 54.) By Example.1, the decryption exponent that corresponds to the encryption exponent a = 27 in this example is b = 3. Hence, to decipher the message, we must only perform the following calculations. 7^3 = 13 mod 55 18^3 = 2 mod 55 17^3 = 18 mod 55 15^3 = 20 mod 55 Note that the results are the original plaintext integers. We still have several topics to address regarding the RSA cryptosystem. Note first that no matter how large we choose the encryption exponent and modulus for the RSAsystem, the system as illustrated in Example.2 will certainly not be secure because it will just yield a substitution cipher. However, we can use the RSA encryption procedure as presented to obtain a nonsubstitution cipher by simply grouping consecutive integers in the plaintext before enciphering. Because our exponentiation operations are done modulo n, we will still be able to convert between plaintext and ciphertext uniquely, provided the plaintext integers are grouped into blocks that are smaller than n. We illustrate this in the following example. Example.3 In this example, we again encipher and decipher the message, "NCSU". We begin by choosing primes p = 79 and q = 151, and defining n = pq = 11929 and m = (p 1)(q 1) = 11700. Next, we choose a = 473, chosen so that (a,m) = 1. We can then use the Euclidean algorithm to find that b = 8237 satisfies ab = 1 mod m. Recall that our plaintext converts to the list of integers 13 2 18 20. Since we have chosen a 5digit value for n, we can group the first two and last two plaintext integers into blocks that will be smaller than n. That is, we can express the plaintext as 1302 1820 (note that we use 02 for 2), and use the RSA encryption procedure as presented. To encipher the message, we perform the following calculations. 1302^473 = 7490 mod 11929 1820^473 = 9723 mod 11929 Hence, the ciphertext is 7490 9723. To decipher the message, we perform the following calculations. 7490^8237 = 1302 mod 11929 9723^8237 = 1820 mod 11929 We can then split the resulting 4digit integers into the original 2digit plaintext integers. Another topic we must address regarding the RSA cryptosystem is how the system actually progresses between two people wishing to exchange a secret message. We stated in the introduction to this paper that the RSA cryptosystem is a publickey system. This forces the system to progress in a particular way. Recall that in general we assume almost everything in a cryptosystem is public knowledge, including the form of the enciphering function. This means that we would assume an intruder who intercepts an RSA ciphertext would know that each ciphertext integer was formed as x^a mod n for some plaintext integer x and positive integers a and n. The fact that the RSA cryptosystem is a publickey system means that we would assume the intruder also knows the actual values of a and n used in the encryption. For example, we would assume an intruder who intercepts the ciphertext in Example.3 would know that each ciphertext integer was formed as x^473 mod 11929 for some plaintext integer x. Although this obviously affects the security of the system, we make this assumption because in practice the RSA system is used with a and n being public knowledge. The benefit of this is that two people wishing to use RSA to send a secret message across an insecure line of communication do not have to figure out a way to secretly exchange an encryption exponent and modulus. The comments made in the previous paragraph imply that the RSA system in Example.3 is not mathematically secure. This is because an intruder could mathematically break the system as follows. After finding the values of p and q in n = pq = 11929, an intruder could form m = (p  1)(q  1), use the Euclidean algorithm to find that b = 8237 satisfies ab = 1 mod m, and decipher the message by raising the ciphertext integers to the power b and reducing modulo n. Hence, none of the operations necessary to break this system would take an intruder more than a few minutes. And even with significantly larger numbers, the Euclidean algorithm and modular exponentiation can easily be efficiently programmed on a computer. However, the first step in this process requires an intruder to find the two prime factors of n. It is the apparent difficulty of this problem, provided p and q are very large, that gives the RSA system an extremely high level of security. For example, if p and q are both around 100 digits long, the fastest known factoring algorithms would generally take millions of years to factor n = pq, even when programmed on a computer that can perform millions of operations per second. Hence, even if the encryption exponent a is public knowledge, an intruder should not be able to determine the decryption exponent b. This is precisely why the RSAcryptosystem is called a publickey system  the parameters in the enciphering function f(x) = mod n can be public knowledge without revealing the parameter b in the deciphering function f1(x) = mod n We now mention how the RSAsystem actually progresses between two people wishing to exchange a secret message across an insecure line of communication. Because only the intended recipient of the message must be able to decipher the message, the intended recipient of the message initiates the process by choosing primes p and q, and defining n = pq and m = (p1)(q 1). The intended recipient then chooses an encryption exponent a ?Z?m such that (a,m) = 1 and, using the Euclidean algorithm if necessary, finds b ? Z?m that satisfies ab = 1 mod m. The intended recipient then sends the values of a and n to the originator of the message across the insecure line of communication, forcing the assumption that a and n are public knowledge. The originator of the message enciphers the message by applying the function f(x) = x^a mod n to the plaintext integers, and then sends the resulting ciphertext integers to the intended recipient across the insecure line of communication. Since only the intended recipient knows b, only the intended recipient can decipher the message by applying the function f1(x) = x^b mod n to the ciphertext integers. Example.4 Suppose we wish to use the RSAcryptosystem to send the message, "NCSU" to a colleague across an insecure line of communication. Our colleague begins the process by choosing primes p and q, and defining n = pq = 363794227 and m = (p  1)(q  1). Next, our colleague chooses a = 13783, chosen so that (a,m) = 1, and uses the Euclidean algorithm to find b ? Z?m that satisfies ab = 1 mod m. Our colleague then sends the values of a and n to us across the insecure line of communication. Recall that our plaintext converts to the list of integers 13 02 18 20. Since our colleague has chosen a 9digit value for n, we can group all four of these 2digit plaintext integers into a single block that will be smaller than n. That is, we can express the plaintext as 13021820, and encipher our message by applying the function f(x) = x^a mod n to this plaintext integer. To encipher the message we perform the following calculation. 13021820^13783 = 91518013 mod 363794227 We would then transmit the ciphertext integer 91518013 to our colleague across the insecure line of communication. In order for an intruder who intercepts this ciphertext and the previously transmitted values of a and n to decipher the message, the intruder would need to find the decryption exponent b. But to find b, an intruder would first need to find m. And to find m, an intruder would need to find the prime factors of n, a problem that, as we have stated, is essentially impossible provided our colleague has chosen sufficiently large values for p and q. This would not pose a problem for our colleague, however, because our colleague began the process by choosing p and q. Hence, our colleague would know that the prime factors of n = pq = 363794227 are p = 14753 and q = 24659, and would have no difficulty in forming m = (p  1)(q  1) = 363754816 and using the Euclidean algorithm to find that b = 20981287 satisfies ab = 1 mod m. To decipher the message, our colleague would then only need to perform the following calculation. 91518013^20981287 = 13021820 mod 363794227 RSA With Maple: The RSA system is a publickey cryptographic method that permits both encryption and digital signatures (authentication). Ronald Rivest, Adi Shamir, and Leonard Adleman developed the RSA system in 1977. RSA stands for the first letter in each of its inventors' last names.
The way the RSA system works:
Suppose Ali wants Ahmed to send him a secret message using the RSA system. Here's what he does. [The communication can take place via email, for example.]
1. He (Ali) finds two large primes p and q.
2. He forms the product m = pq. We call m the modulus. 3. He computes . [This is the socalled Euler phi function applied to the modulus m. ]
4. He chooses a positive integer e such that igcd(e,) = 1.
5.He computes the inverse, call it d, of e modulo . 6. He sends the pair of numbers [m,e] to Ahmed. This pair of numbers may be made public, but the numbers p,q, d and should be kept secret! We call [m,e] the public key and d, the private key.
7. He tells Ahmed how to use Maple to convert the text of his message into a sequence of positive integers , , . . . , each less than m. One such method is shown below.
8. He tells Ahmed to compute for each i the number and to send Ali the sequence of numbers , , . . ., . He (Ahmed) need not keep the 's secret after he has computed them. But, he should keep the 's secret.
9. Now when Ali gets the 's from Ahmed, he computes and this will turn out to be the 's. Then Ali can use Maple to convert these back into text as we illustrate in the next section.
Binary Exponentiation Modulo m :
A key component in implementing the RSA scheme is the computation of for large positive integers x, e, and m. An obvious, but infeasible, way to do this is to try the command :

(1) 
The problem with this approach is that x^e is computed first. If x and e are large, x^e may be larger than the number of particles in the universe. So storing this number to divide it by m is not possible. For large enough integers x, m and e this may even cause Maple to crash. Instead, one should use the command Power(x,e) mod m. This procedure implements an algorithm called binary exponentiation modulo m. The basic idea is to perform a series of operations of the form y:=x^2 mod m. This will give powers of the form x^N mod m where N is a power of 2. Some of these can be multiplied together to obtain x^e mod m. The algorithm is actually pretty simple, but amazingly efficient. One can see the Maple code for Power(x,e) mod m (which is the same as `mod/Power`(x,e,m) ) as follows. Aside from the error checking the procedure is quite simple.
> 
interface(verboseproc=3); print(`mod/Power`);


(2) 
Let us compare the time required for 2^e mod m and Power(2,e) mod m for e = and m = 10^100+3. If we tried to increase the value of e here we would quickly find that the first method would cause trouble.

(3) 
> 
st:=time(): a:=2^e mod m: elapsed_time:=(time() st)*sec; a;


(4) 
> 
st:=time(): b:=Power(2,e) mod m: elapsed_time:=(time() st)*sec; b;


(5) 
Using the first method for large e will be unfeasible, however, note how rapidly the binary exponentiation method works for the following large integers:
> 
die:=rand(1..10^100): x:=die(); e:=die(); m:=die();

> 
st:=time(): a:=Power(x,e) mod m: elapsed_time:=(time()  st)*sec; a;


(7) 
An Example of the RSA System :
We illustrate the RSA system using two randomly chosen primes with 20 decimal digits. Note that is the smallest n decimal digit integer and is the largest. For example if n = 3, we obtain the smallest and largest 3 digit integers:

(8) 
We first generate two 30 digit random positive integers and then use the Maple command nextprime to obtain the smallest primes greater than each number. Notice that in rand we use the range 10^29..10^301.
> 
N:=rand(10^29..10^30 1)(); M:=rand(10^29..10^30 1)();


(9) 
Now we use the command nextprime. The command nextprime(n) finds the smallest prime greater than n.
> 
p:=nextprime(N); q:=nextprime(M);


(10) 
Now we multiply these together to form our modulus m:

(11) 
How many digits does m have? This tells us:

(12) 
Now we compute which is possible since we know p and q . We simply use the formula . We denote it by the variable phi.

(13) 
Now we wish to find a number e such that . We keep trying random 20 digit integers till we find one that works.
> 
for i from 1 do e:=rand(10^19..10^201)(); if igcd(e,phi) = 1 then break; fi; od: e;


(14) 
The inverse of e modulo phi is an integer d such that e*d mod phi = 1. From number theory it is known that an integer e has an inverse mod phi if and only igcd(e,phi) = 1. The following command will compute the inverse of e modulo phi:

(15) 
We check that e*d mod = 1.

(16) 
So the public key Ali sends to Ahmed and mades public is

(17) 
The information we must keep secret in this case is:
> 
Private_key:=[p,q,d,phi];


(18) 
In cryptography, plain text refers to any message that is not enciphered. After encryption it is called cipher text. We assign Ahmed's message to the variable named plain_text, as follows. (Of course, the name of the variable is not important.):
> 
plain_text:="Hello,Ali: our mission is to reform the Mathematics Education. Mathematics education needs to be reformed as we now pass into the new millennium. This conviction shared with topics of science and engineering that based on mathematical modeling. The reason is of course the computer revolution, which has fundamentally changed the possibilities of using mathematical and computational techniques for modeling. Education in mathematics form the basis of science and engineering education from undergraduate to graduate level, because engineering and science are largely based on mathematical modeling. The level and the quality of mathematics education sets the level of the education as a whole; Ahmed";


(19) 
Note that the text includes new line symbols, \n, as well as numerous blanks.The \ at the end of each line is just Maple's way of saying that this should all be on one line.
We now convert this text to a list of numbers:
> 
List1:=convert(plain_text,bytes);


(20) 
We consider List1 as the base 256 representation of a number. We convert this to a base m number as follows:
> 
List2:=convert(List1,base, 256,m);


(21) 
Now we apply the mapping which sends x to Power(x,e) mod m to each number in List2. This can be done using map. We thus obtain the enciphered message that will be sent to Ali.
> 
cipher_text:=map(x>Power(x,e) mod m, List2);


(22) 
Now Ahmed sends this to Ali and the whole world for that matter. But since only Ali has the secret private key, only Ali will be able to decipher the message (in the case where p and q are chosen with sufficient care.)
We show now how Ali deciphers the message: he applies the mapping which sends x to Power(x,d) mod m where d is his private key to each received number:
> 
decipher1:=map(x>Power(x,d) mod m,cipher_text);


(23) 
Next Ali converts this to base 256:
> 
decipher2:=convert(decipher1,base,m,256);


(24) 
Finally ali converts the numbers back to text and sees what message Ahmed sent him:
> 
decipher3:=convert(decipher2,bytes);


(25) 
Breaking the RSA System :
To decipher the message it is believed (but not proved) that one must be able to find the private key d given only the public key [m,e]. If one knows then Maple quickly computes d by the command 1/e mod . It is known that computing is the same order of difficulty as factoring m. If m is the product of two 100 digit primes, say, then m is 200 digits long and current factoring algorithms are unable to factor such numbers within a reasonable time unless the primes are poorly chosen . Factoring algorithms always depend on luck. After all one might guess the factors, but this would be very unlikely. Of course, the technology is changing rapidly. Mathematicians are finding better algorithms and Engineers are building faster computers every day it seems.
