Java Reference
In-Depth Information
7.4.4 the rsa cryptosystem
For centuries, number theory was thought to be a completely impractical
branch of mathematics. Recently, however, it has emerged as an important
field because of its applicability to cryptography.
The problem we consider has two parts. Suppose that Alice wants to send
a message to Bob but that she is worried that the transmission may be com-
promised. For instance, if the transmission is over a phone line and the phone
is tapped, somebody else may be reading the message. We assume that, even
if there is eavesdropping on the phone line, there is no maliciousness (i.e.,
damage to the signal)—Bob gets whatever Alice sends.
Number theory is
used in cryptogra-
phy because fac-
toring appears to
be a much harder
process than
multiplication.
A solution to this problem is to use encryption, an encoding scheme to
transmit messages that cannot be read by other parties. Encryption consists of
two parts. First, Alice encrypts the message and sends the result, which is no
longer plainly readable. When Bob receives Alice's transmission, he decrypts
it to obtain the original. The security of the algorithm is based on the fact that
nobody else besides Bob should be able to perform the decryption, including
Alice (if she did not save the original message).
Encryption is used
to transmit mes-
sages so that they
cannot be read by
other parties.
Thus Bob must provide Alice with a method of encryption that only he
knows how to reverse. This problem is extremely challenging. Many proposed
algorithms can be compromised by subtle code-breaking techniques. One
method, described here, is the RSA cryptosystem (named after the initials of its
authors), an elegant implementation of an encryption strategy.
Here we give only a high-level overview of encryption, showing how the
methods written in this section interact in a practical way. The references con-
tain pointers to more detailed descriptions, as well as proofs of the key prop-
erties of the algorithm.
First, however, note that a message consists of a sequence of characters
and that each character is just a sequence of bits. Thus a message is a
sequence of bits. If we break the message into blocks of B bits, we can inter-
pret the message as a series of very large numbers. Thus the basic problem is
reduced to encrypting a large number and then decrypting the result.
The RSA cryptosys-
tem is a popular
encryption method.
computation of the rsa constants
The RSA algorithm begins by having the receiver determine some constants.
First, two large primes p and q are randomly chosen. Typically, these would be at
least 100 or so digits each. For the purposes of this example, suppose that p = 127
and q = 211. Note that Bob is the receiver and thus is performing these computa-
tions. Note, also, that primes are plentiful. Bob can thus keep trying random num-
bers until two of them pass the primality test (discussed in Chapter 9).
 
Search WWH ::




Custom Search