s
Section 5.6 The Mighty Mod Function
431
Here y is the result of a 1-bit left circular shift of x. This algorithm generalizes
to an n-bit string x ( p = x mod 2
n−1
, q = p # 2, s = x ! p, t = s # 2
−(n−1)
, and
y = q + t). A 2-bit left circular shift can be accomplished by two 1-bit shifts.
A ciphertext that is the result of a DES encryption can be decoded into plaintext by reversing all the steps of the encoding process, including applying the keys
for each round in the reverse order in which they were used for encoding. Because
the DES algorithm is well-known, the only “secret” part is the 56-bit key that is
used. Hence a DES ciphertext can be decrypted by a brute force technique of trying all possible 56 bit keys, of which there are 2
56
. Even assuming that on the average one would hit the right key after trying about half the possibilities, this is still
2
55
binary strings to generate and test in the DES algorithm. This number used to
be considered so impossibly large that DES encoding was deemed perfectly secure, and the U.S. government insisted for many years that it was “unbreakable.”
But with faster computers and using parallelism, it’s possible to find the key in a
matter of hours.
In recognition of this potential weakness, a new encoding scheme called aes
(Advanced Encryption Standard) was adopted by the U.S. National Institute of
Standards and Technology in 2001 after a five-year design competition. AES is
also a block encryption scheme, but it uses a key length of 128 bits or more. (AES
also uses a form of the Euclidean algorithm, discussed in Section 2.3, the idea of
relatively prime numbers, discussed in Section 2. 4, arithmetic modulo n, illustrated in the first few exercises at the end of this section, and ideas from Section 9.1.)
A disadvantage of both DES and AES is that they are symmetric encryption (also called private key encryption) schemes. The same key is used to both
encode and decode the message; for example, in a Caesar cipher, the key is the
amount of shift k, and decoding is accomplished by shifting left instead of right.
In a private key encryption scheme, both the sender and receiver must know the
key. The problem of securely transmitting a message turns into the problem of
securely transmitting the key to be used for the encryption and decryption.
asymmetric encryption (public key encryption) schemes use different
keys for encoding and decoding. The decryption key cannot be derived in any
practical way from the encryption key, so the encryption key can be made public.
Anyone can send a message to the intended receiver in encrypted form using the
receiver’s public key, but only the intended receiver, who has the decryption key,
can decode it. The best-known asymmetric encryption scheme is the rsa public
key encryption algorithm, named for its developers Ron Rivest, Adi Shamir,
and Len Adleman. RSA uses the mod function, as well as the Euler phi function
discussed in Section 2.4, to produce secure public keys. The RSA method works
as follows:
1. Two large prime numbers p and q (on the order of 200 digits each) are
chosen at random (such numbers can be found relatively easily), and
p # q = n is computed.
■
PRaCtiCe 46 Use the algorithm of Example 53 to compute the 1-bit circular left shift of 1011 (write the
bit strings for x, p, q, and so on).
Section 5.6 The Mighty Mod Function
431
Here y is the result of a 1-bit left circular shift of x. This algorithm generalizes
to an n-bit string x ( p = x mod 2
n−1
, q = p # 2, s = x ! p, t = s # 2
−(n−1)
, and
y = q + t). A 2-bit left circular shift can be accomplished by two 1-bit shifts.
A ciphertext that is the result of a DES encryption can be decoded into plaintext by reversing all the steps of the encoding process, including applying the keys
for each round in the reverse order in which they were used for encoding. Because
the DES algorithm is well-known, the only “secret” part is the 56-bit key that is
used. Hence a DES ciphertext can be decrypted by a brute force technique of trying all possible 56 bit keys, of which there are 2
56
. Even assuming that on the average one would hit the right key after trying about half the possibilities, this is still
2
55
binary strings to generate and test in the DES algorithm. This number used to
be considered so impossibly large that DES encoding was deemed perfectly secure, and the U.S. government insisted for many years that it was “unbreakable.”
But with faster computers and using parallelism, it’s possible to find the key in a
matter of hours.
In recognition of this potential weakness, a new encoding scheme called aes
(Advanced Encryption Standard) was adopted by the U.S. National Institute of
Standards and Technology in 2001 after a five-year design competition. AES is
also a block encryption scheme, but it uses a key length of 128 bits or more. (AES
also uses a form of the Euclidean algorithm, discussed in Section 2.3, the idea of
relatively prime numbers, discussed in Section 2. 4, arithmetic modulo n, illustrated in the first few exercises at the end of this section, and ideas from Section 9.1.)
A disadvantage of both DES and AES is that they are symmetric encryption (also called private key encryption) schemes. The same key is used to both
encode and decode the message; for example, in a Caesar cipher, the key is the
amount of shift k, and decoding is accomplished by shifting left instead of right.
In a private key encryption scheme, both the sender and receiver must know the
key. The problem of securely transmitting a message turns into the problem of
securely transmitting the key to be used for the encryption and decryption.
asymmetric encryption (public key encryption) schemes use different
keys for encoding and decoding. The decryption key cannot be derived in any
practical way from the encryption key, so the encryption key can be made public.
Anyone can send a message to the intended receiver in encrypted form using the
receiver’s public key, but only the intended receiver, who has the decryption key,
can decode it. The best-known asymmetric encryption scheme is the rsa public
key encryption algorithm, named for its developers Ron Rivest, Adi Shamir,
and Len Adleman. RSA uses the mod function, as well as the Euler phi function
discussed in Section 2.4, to produce secure public keys. The RSA method works
as follows:
1. Two large prime numbers p and q (on the order of 200 digits each) are
chosen at random (such numbers can be found relatively easily), and
p # q = n is computed.
■
PRaCtiCe 46 Use the algorithm of Example 53 to compute the 1-bit circular left shift of 1011 (write the
bit strings for x, p, q, and so on).