Recursion - Data Structures and Problem Solving Using Java - page 318

Next, Bob computes and , which for this
example gives N = 26,797 and = 26,460. Bob continues by choosing any
such that gcd( e, N ′ ) = 1 . In mathematical terms, he chooses any e that
is relatively prime to N ′ . Bob can keep trying different values of e by using
the routine shown in Figure 7.17 until he finds one that satisfies the property.
Any prime e would work, so finding e is at least as easy as finding a prime
number. In this case, e = 13,379 is one of many valid choices. Next, d, the
multiplicative inverse of e , mod N ′ is computed by using the routine shown in
Figure 7.18. In this example, d = 11,099.
Once Bob has computed all these constants, he does the following. First,
he destroys p, q, and N ′ . The security of the system is compromised if any one
of these values is discovered. Bob then tells anybody who wants to send him
an encrypted message the values of e and N, but he keeps d secret.

N q = N ′ = ( p - 1 ) ( q - 1 )

N ′

e > 1

encryption and decryption algorithms
To encrypt an integer M, the sender computes M e (mod N ) and sends it. In our case,
if M = 10,237, the value sent is 8,422. When an encrypted integer R is received, all
Bob has to do is compute R d (mod N ). For R = 8,422, he gets back the original M =
10,237 (which is not accidental). Both encryption and decryption can thus be carried
out by using the modular exponentiation routine given in Figure 7.16.
The algorithm works because the choices of e, d, and N guarantee (via a
number theory proof beyond the scope of this text) that M ed = M (mod N ), so
long as M and N share no common factors. As the only factors of N are two
100-digit primes, it is virtually impossible for that to occur. 5 Thus decryption
of the encrypted text gets the original back.
What makes the scheme seem secure is that knowledge of d is apparently
required in order to decode. Now N and e uniquely determine d . For instance,
if we factor N, we get p and q and can then reconstruct d . The caveat is that
factoring is apparently very hard to do for large numbers. Thus the security of
the RSA system is based on the belief that factoring large numbers is intrinsi-
cally very difficult. So far it has held up well.

This general scheme is known as public key cryptography, by which anybody
who wants to receive messages publishes encryption information for anybody
else to use but keeps the decryption code secret. In the RSA system, e and N
would be computed once by each person and listed in a publicly readable place.
The RSA algorithm is widely used to implement secure e-mail, as well as
secure Internet transactions. When you access a Web page via the http s proto-
col, a secure transaction is being performed via cryptography. The method

In public key cryp-
tography , each par-
ticipant publishes
the code others
can use to send
encrypted mes-
sages but keeps
the decrypting code
secret.

5. You are more likely to win a typical state lottery 13 weeks in a row. However, if M and N
have a common factor, the system is compromised because the gcd will be a factor of N .