432
Relations, Functions, and Matrices
2. RSA, like DES and AES, is a block cipher, so let us assume that a block
B of text has been encoded by some invertible function g into an integer T
(much as is done in the Caesar cipher) where T is an integer, 0 < T < n.
3. The Euler phi function w(n) is computed. Because n is the product of two primes, we know from Equation (2) of Section 2.4 that
w(n) = (p − 1)(q − 1).
4. A value e is chosen with 1 < e < w(n) such that e and w(n) are relatively
prime, that is, gcd (e, w(n)) = 1. (This will surely be true if e is itself a
prime number.)
5. gcd(e, w(n)) = 1 means that 1 can be written as a linear combination of e
and w(n)
d # e + f # w(n) = 1
or
d # e ≡ 1 mod w(n)
The Euclidean algorithm can be used to find unique values for d (and f )
such that 1 < d < w(n).
6. The public key is the pair of values (n, e). T is encoded by computing
T
e
mod n.
7. The private key is the pair of values (n, d ), of which only the “d ” part
is secret. The received message T
e
mod n is decoded by computing
(T
e
mod n)
d
mod n.
(T
e
mod n)
d
mod n = (T
e
)
d
mod n by Equation (1)
= T
ed
mod n with d # e ≡ 1 mod w(n)
and it happens that this expression equals T. (The proof depends on two
classic results from number theory called Fermat’s little theorem and the
Chinese remainder theorem. See Exercises 37–41.)
8. Then g
−1
(T ) = B, the original text block.
Because n and e are public, anyone who could factor n into its prime factors p
and q could then reconstruct the decryption key d and decode the message. However, there is no efficient algorithm to find the prime factors of a (large) n. Hence,
while the RSA cryptosystem is not technically secure, it is practically so, although
a number of demonstration “factor attacks” have been made using many people
working together via PCs and the Internet.
Although public key encryption solves the “key distribution” problem of shared
keys between sender and receiver, it is a relatively slow encryption/decryption
method. Hence in applications such as financial transactions over the Internet, public
key encryption is often used for secure transmission of keys for private key communication, which is then used to transmit the actual message. The user’s browser may
send a request to the Web server for the server’s public encryption key. Upon receipt,
the browser uses this public key to send an encrypted message back to the server
that contains a symmetric key for DES encryption. At this point both the browser
and the server share a secret key that has been securely transmitted, and the rest of
the transaction can be carried out using the faster DES encryption.
Relations, Functions, and Matrices
2. RSA, like DES and AES, is a block cipher, so let us assume that a block
B of text has been encoded by some invertible function g into an integer T
(much as is done in the Caesar cipher) where T is an integer, 0 < T < n.
3. The Euler phi function w(n) is computed. Because n is the product of two primes, we know from Equation (2) of Section 2.4 that
w(n) = (p − 1)(q − 1).
4. A value e is chosen with 1 < e < w(n) such that e and w(n) are relatively
prime, that is, gcd (e, w(n)) = 1. (This will surely be true if e is itself a
prime number.)
5. gcd(e, w(n)) = 1 means that 1 can be written as a linear combination of e
and w(n)
d # e + f # w(n) = 1
or
d # e ≡ 1 mod w(n)
The Euclidean algorithm can be used to find unique values for d (and f )
such that 1 < d < w(n).
6. The public key is the pair of values (n, e). T is encoded by computing
T
e
mod n.
7. The private key is the pair of values (n, d ), of which only the “d ” part
is secret. The received message T
e
mod n is decoded by computing
(T
e
mod n)
d
mod n.
(T
e
mod n)
d
mod n = (T
e
)
d
mod n by Equation (1)
= T
ed
mod n with d # e ≡ 1 mod w(n)
and it happens that this expression equals T. (The proof depends on two
classic results from number theory called Fermat’s little theorem and the
Chinese remainder theorem. See Exercises 37–41.)
8. Then g
−1
(T ) = B, the original text block.
Because n and e are public, anyone who could factor n into its prime factors p
and q could then reconstruct the decryption key d and decode the message. However, there is no efficient algorithm to find the prime factors of a (large) n. Hence,
while the RSA cryptosystem is not technically secure, it is practically so, although
a number of demonstration “factor attacks” have been made using many people
working together via PCs and the Internet.
Although public key encryption solves the “key distribution” problem of shared
keys between sender and receiver, it is a relatively slow encryption/decryption
method. Hence in applications such as financial transactions over the Internet, public
key encryption is often used for secure transmission of keys for private key communication, which is then used to transmit the actual message. The user’s browser may
send a request to the Web server for the server’s public encryption key. Upon receipt,
the browser uses this public key to send an encrypted message back to the server
that contains a symmetric key for DES encryption. At this point both the browser
and the server share a secret key that has been securely transmitted, and the rest of
the transaction can be carried out using the faster DES encryption.