Chapter 8
Reinforcement
Problem R-8.1
Eve has tricked Alice into decrypting a bunch of ciphertexts that Alice encrypted last month
but forgot about. What type of attack is Eve employing?
Problem R-8.2
Eve has an antenna that can pick up Alice’s encrypted cell phone conversations. What type
of attack is Eve employing?
Problem R-8.3
Eve has given a bunch of messages to Alice for her to sign using the RSA signature scheme,
which Alice does without looking at the messages and without using a one-way hash func-
tion. In fact, these messages are ciphertexts that Eve constructed to help her figure out
Alice’s RSA private key. What kind of attack is Eve using here?
Problem R-8.4
Eve has bet Bob that she can figure out the AES secret key he shares with Alice if he will
simply encrypt 20 messages for Eve using that key. For some unknown reason, Bob agrees.
Eve gives him 20 messages, which he then encrypts and emails back to Eve. What kind of
attack is Eve using here?
Problem R-8.5
What is the encryption of the following string using the Caesar cipher: THELAZYFOX.
Problem R-8.7
What are the next three numbers in the pseudo-random number generator 3xi+ 2 mod 11,
starting from 5?
Problem R-8.9
In the inverse of the S-box from Figure 8.14, what is the substitution for e3, in hexadecimal?
Problem R-8.12
Bob is arguing that if you use Electronic Codebook (ECB) mode twice in a row to encrypt
a long message, M, using the same key each time, that it will be more secure. Explain why
Bob is wrong in the case of using a binary one-time pad encryption scheme.
Problem R-8.16
Roughly how many times would you have to call a primality tester to find a prime number
between 1,000,000 and 2,000,000?
Problem R-8.17
What is 7120 mod 143?
Problem R-8.18
Show the result of encrypting M= 4 using the public key (e, n)=(3,77) in the RSA
cryptosystem.
Problem R-8.20
Alice is telling Bob that he should use a pair of the form (3,n) or (16385,n) as his RSA
public key, where, as usual, n=pq, for two large primes, pand q, if he wants people
to encrypt messages for him from their cell phones. What is the justification for Alice’s
advice?
Problem R-8.24
Explain why nonforgeability and nonmutability imply nonrepudiation for digital signatures.
33
Problem R-8.25
Explain the strengths and weaknesses of using symmetric encryption, like AES, versus a
public-key cryptosystem, like RSA.
Problem R-8.26
Name two things that the RSA and ElGamal cryptosystems have in common, other than
the fact that they are both public-key cryptosystems?
Creativity
Problem C-8.1
What is the plaintext for the following ciphertext, which was encrypted using a simple
substitution cipher: @par CJBT COZ NPON ZJV FTTK TWRTUYTFGT NJ DTN O
XJL. Y COZ ZJV CPJVIK DTN O XJL MYUCN.
Solution SOME SAY THAT YOU NEED EXPERIENCE TO GET A JOB. I SAY YOU
Problem C-8.2
ROT13 is a cyclic shift cipher that substitutes each English letter with one that is 13 away
in the alphabet. It is used today not for security, but as a simple obfuscation device, because
the same algorithm is used for both encryption and decryption. People wishing to encrypt
or decrypt a message, M(such as a spoiler paragraph in a movie review), just cut-and-paste
Mto a ROT13 converter and click a button “APPLY” to do the encryption or decryption.
Give an example of another ROTitransformation that could be used for both encryption
and decryption in a similar way.
34
Problem C-8.4
How many valid English plaintexts are there for the ciphertext message CJU using a length-
3, one-time pad of cyclic shifts, (i, j, k)?
Problem C-8.5
Alice is using a linear congruential generator, axi+bmod 13, to generate pseudo-random
numbers. Eve sees three numbers in a row, 7, 6, 4, that are generated from Alice’s function.
What are the values of aand b?
Problem C-8.6
Bob is arguing that if you use output feedback (OFB) mode twice in a row to encrypt a
long message, M, using the same key each time, it will be more secure. Explain why Bob
is wrong, no matter what encryption algorithm he is using for block encryption.
Problem C-8.7
Why can’t Bob use the pair (6,n) as an RSA public key, where n=pq, for two large primes,
pand q?
Problem C-8.8
Use Euler’s Theorem, not repeated squaring, to compute
2010203 mod 10403.
Show your work.
35
Problem C-8.13
Bob is stationed as a spy in Cyberia for a week and wants to prove that he is alive ev-
ery day of this week and has not been captured. He has chosen a secret random num-
ber, x, which he memorized and told to no one. But he did tell his boss the value
y=H(H(H(H(H(H(H(x))))))), where His a one-way cryptographic hash function. Un-
fortunately, he knows that the Cyberian Intelligence Agency (CIA) was able to listen in
on that message; hence, they also know the value of y. Explain how he can send a single
message every day that proves he is still alive and has not been captured. Your solution
should not allow anyone to replay any previous message from Bob as a (false) proof he is
still alive.
36