s
Section 5.6 The Mighty Mod Function
443
24. Describe how to perform a 1-bit right circular shift on a 4-bit binary string x using the left circular shift
operation.
25. Using RSA encryption/decryption, let p = 5 and q = 3. Then n = 15 and w(n) = 4 # 2 = 8. Pick e = 3.
a. Use the Euclidean algorithm to find the value of d.
b. Encode T = 8 using the public key (n, e).
c. Decode your answer to part (b) to retrieve the 8.
26. Why is the RSA encryption of Exercise 25 a poor choice?
27. Using RSA encryption/decryption, let p = 5 and q = 11. Then n = 55 and w(n) = 4 # 10 = 40.
Pick e = 7.
a. Use the Euclidean algorithm to find the value of d. (Hint: If the Euclidean algorithm produces an equation 1 = x # e + f # w(n)where the value of x is negative, add and subtract the product e # w(n) to the
right side of the equation to get a positive value for d.)
b. Encode T = 12 using the public key (n, e).
c. Decode your answer to part (b) to retrieve the 12.
28. Using RSA encryption/decryption, let p = 23 and q = 31. Then n = 713 and w(n) = 22 # 30 = 660.
Pick e = 17.
a. Use the Euclidean algorithm to find the value of d.
b. Encode T = 52 using the public key (n, e).
c. Decode your answer to part (b) to retrieve the 52.
29. a. All n people in a group wish to communicate with each other using messages encrypted with DES or
AES. A different secret key must be shared between each pair of users. How many keys are required?
b. All n people in a group wish to communicate with each other using messages encrypted with a public
key encryption system. How many keys are required?
30. Computer users are notoriously lax about choosing passwords; left to their own devices, they tend to pick
short or really obvious passwords. At Simpleton University, passwords must contain only lowercase letters, and the campus computer system uses an (unrealistically simple) cryptographic hash function given
by the following algorithm:
1. Letters in the password are converted to an integer equivalent (a S 1, b S 2, and so on).
2. In the result of step 2, all individual digits are added (for example, 17 becomes 1 + 7) to give an
integer value x.
3. h(x) = x mod 2
5
Joe Hack has managed to steal the password table, and he notices that there is a password entry of 20 for
bsmith. Joe decides to try to hack into the system as bsmith by guessing bsmith’s password. Can you guess
bsmith’s password?
31. a. The ISBN-10 of the sixth edition of this book is 0-7167-6864-C where C is the check digit. What is the
check digit?
b. What is the ISBN-13 of the sixth edition?
32. A bookstore placed an order for 2000 copies of Harry Potter and the Deathly Hallows, the seventh and
final volume in the hugely popular Harry Potter series by J. K. Rowling. When placing the order with the
publisher, the ISBN-13 978-0-545-01022-5 was used. Is this correct?
33. Given the 11 digits 02724911637, compute the check digit for the UPC-A code.
Section 5.6 The Mighty Mod Function
443
24. Describe how to perform a 1-bit right circular shift on a 4-bit binary string x using the left circular shift
operation.
25. Using RSA encryption/decryption, let p = 5 and q = 3. Then n = 15 and w(n) = 4 # 2 = 8. Pick e = 3.
a. Use the Euclidean algorithm to find the value of d.
b. Encode T = 8 using the public key (n, e).
c. Decode your answer to part (b) to retrieve the 8.
26. Why is the RSA encryption of Exercise 25 a poor choice?
27. Using RSA encryption/decryption, let p = 5 and q = 11. Then n = 55 and w(n) = 4 # 10 = 40.
Pick e = 7.
a. Use the Euclidean algorithm to find the value of d. (Hint: If the Euclidean algorithm produces an equation 1 = x # e + f # w(n)where the value of x is negative, add and subtract the product e # w(n) to the
right side of the equation to get a positive value for d.)
b. Encode T = 12 using the public key (n, e).
c. Decode your answer to part (b) to retrieve the 12.
28. Using RSA encryption/decryption, let p = 23 and q = 31. Then n = 713 and w(n) = 22 # 30 = 660.
Pick e = 17.
a. Use the Euclidean algorithm to find the value of d.
b. Encode T = 52 using the public key (n, e).
c. Decode your answer to part (b) to retrieve the 52.
29. a. All n people in a group wish to communicate with each other using messages encrypted with DES or
AES. A different secret key must be shared between each pair of users. How many keys are required?
b. All n people in a group wish to communicate with each other using messages encrypted with a public
key encryption system. How many keys are required?
30. Computer users are notoriously lax about choosing passwords; left to their own devices, they tend to pick
short or really obvious passwords. At Simpleton University, passwords must contain only lowercase letters, and the campus computer system uses an (unrealistically simple) cryptographic hash function given
by the following algorithm:
1. Letters in the password are converted to an integer equivalent (a S 1, b S 2, and so on).
2. In the result of step 2, all individual digits are added (for example, 17 becomes 1 + 7) to give an
integer value x.
3. h(x) = x mod 2
5
Joe Hack has managed to steal the password table, and he notices that there is a password entry of 20 for
bsmith. Joe decides to try to hack into the system as bsmith by guessing bsmith’s password. Can you guess
bsmith’s password?
31. a. The ISBN-10 of the sixth edition of this book is 0-7167-6864-C where C is the check digit. What is the
check digit?
b. What is the ISBN-13 of the sixth edition?
32. A bookstore placed an order for 2000 copies of Harry Potter and the Deathly Hallows, the seventh and
final volume in the hugely popular Harry Potter series by J. K. Rowling. When placing the order with the
publisher, the ISBN-13 978-0-545-01022-5 was used. Is this correct?
33. Given the 11 digits 02724911637, compute the check digit for the UPC-A code.