LAY NETWORKS
MCA – I I I Semister
CS-13
RSA Algorithm
MCA(6)
By Kartik Shah
You can send your contributions to contribute@laynetworks.com
1
LAY NETWORKS
The RSA Algorithm
Encryption is the act of encoding text so that others not privy to the decryption
mechanism (the "key") cannot understand the content of the text. Encryption has
long been the domain of spies and diplomats, but recently it has moved into the
public eye with the concern of the protection of electronic transmissions and
digitally stored data. Standard encryption methods usually have two basic flaws:
(1) A secure channel must be established at some point so that the sender may
exchange the decoding key with the receiver; and (2) There is no guarantee who
sent a given message. Public key encryption has rapidly grown in popularity (and
controversy, see, for example, discussions of the Clipper chip on the archives
given below) because it offers a very secure encryption method that addresses
these concerns.
In a classic cryptosystem in order to make sure that nobody, except the intended
recipient, deciphers the message, the people involved had to strive to keep the
key secret. In a public-key cryptosystem. The public key cryptography solves one
of the most vexing problems of all prior cryptography: the necessity of
establishing a secure channel for the exchange of the key.
The RSA algorithm, named for its creators Ron Rivest, Adi Shamir, and Leonard
Adleman, is currently one of the favorite public key encryption methods. Here is
the algorithm:
1. Choose two (in practice, large 100 digit) prime numbers p and q and let n
= pq.
2. Let Pi be the block of (plain) text to be encrypted. Actually Pi is the
numerical equivalent of the text which may either be single letters or
blocks of letters, just as long as .
3. Choose a random value E (usually small) such that E is relatively prime to
. Then the encrypted text is calculated from
The pair of values (n,E) act as the public key.
4. To decode the ciphertext, we need to find an exponent D, which is known
only to the person decoding the message, such that
Note that . Then we may calculate
2
LAY NETWORKS
This step is based on the following result:
where Show that this result is true.
(Since , then for some integer m. Thus,
applying Euler's theorem we have
).
By Euler's theorem
provided E and are relatively prime, which is true by the choice of E. So we
obtain
Therefore, we have an equation that can be used to find the "key" exponent D.
The central result of the RSA algorithm is that this equation is computationally
solvable in polynomial time (actually using the Euclidean Algorithm) whereas
solving by factoring n requires exponential computational time. [Note however
that this last statement has never actually been proven but only demonstrated
given today's algorithms. Should someone discover an algorithm that factors
integers in polynomial time, the RSA and similar algorithms could be rendered
useless for secure communications.] Central to these calculations is knowing the
factorization of n, since we will need to calculate both and .
Example
Suppose we wish to encode the plaintext message Pi = 3 (that is, under our
encoding some letter has been assigned the numerical value 3) subject to our
3
LAY NETWORKS
choices of p=11, q=17 (thus, n=187) and E=7 (note that 7 is relatively prime to
187.) Then the ciphertext Ci is given by
Ci = 37 = 2187 130 mod(187).
Thus the receiver must decode the message Ci = 130. To decode this "message"
the receiver must calculate the exponent D. [Note that in this example the
factorization of n is relatively easy, so someone could break the code by
factoring n and calculating D. However, in practice, we could choose n large so
that only we would (theoretically) know the factorization.]
Since n = 11 · 17, then , and
[WARNING! WARNING! Will Robinson.] Thus we obtain
Example: Calculate 763 mod(160).
Why was there a warning in the previous example? If you have been closely
examining what has taken place in the RSA algorithm you may have noticed that
although we know the factorization of n (since we choose the prime factors p and
q) and hence , we may not have an easy time determing
, which requires us to know all the factors of what
could be a very large number. This seems to contradict the polynomial time
needed to solve for the key. The solution is (and is a key -- unintentional pun --
element of the RSA algorithm) that the formula for D, although concise, is not
the way the solution is found in practice. The actual method of solution (which
does require polynomial time computation) is based on the Euclidean algorithm.
Returning to our previous example, recall that we want to solve
By our choice of E, 7 and 160 are relatively prime, and thus
using the Euclidean algorithm. Working in reverse gives
4
LAY NETWORKS
In algebraic terms, we say we have written 1 as a linear combination of 7 and
160. Since 160 is the modulus, we have
Hence D=23! Thus the real key to the solution of D is knowing which
requires the knowledge of the factorization of n since .
A Simple explanation of RSA
Algorithm in view to computer :
Let p and q be distinct large primes and let n be their product. Assume that we
also computed two integers, d (for decryption) and e (for encryption) such that
d * e 1 (mod ø(n))
where ø(n) is the number of positive integers smaller than n that have no factor
except 1 in common with n
The integers n and e are made public, while p, q, and d are kept secret.
Let m be the message to be sent, where m is a positive integer less than and
relativley prime to n. A plaintext message is easily converted to a number by
using either the alphabet position of each letter (a=01, b=02, ..., z=26) or using
the standard ASCII table. If necessary (so that m<n), the message can be broken
into several blocks.
The encoder computes and sends the number
m' = m^e mod n
To decode, we simply compute
.
e^d mod n
Now, since both n and e are public, the question arises: can we
compute from them d? The answer: it is possible, if n is factored into
5
LAY NETWORKS
prime numbers.
The security of RSA depends on the fact that it takes an impractical
amount of time to factor large numbers.
