Cryptography Homework

This assignment covers various aspects of cryptography. It begins with questions on Data Encryption Standard (DES) and its use with cipher block chaining, exploring the effects of transmission and encryption errors on decrypted plaintext blocks. The assignment then delves into the vulnerability of Double DES and the efficiency of attacking Triple DES using a chosen plaintext attack. A Diffie-Hellman key exchange problem is presented, requiring the calculation of a shared secret key using given parameters. RSA cryptography is explored through a ciphertext decryption problem and a scenario involving a user's private key being identical to a friend's public key. The assignment also includes a decryption problem involving a monoalphabetic substitution cipher and a question on the probability of a unique key in a block cipher. Finally, a problem involving a flawed DES implementation is presented, requiring the determination of the plaintext given a ciphertext.

1. You are using DES with cipher block chaining to send a message (containing plaintext blocks m1,
m2, m3, . . . ) to your friend, Alice. Explain your answer to each of the following: (a) Assume that
an error occurs during the transmission of the first ciphertext block c1, so that Alice receives an
incorrect block c 0 1 instead of c1. After Alice decrypts the message, which of her plaintext
blocks will be incorrect? (b) Assume that an error occurs inside your computer during the
encryption of the second plaintext block (m2) and you end up computing c2 incorrectly as c 0 2 .
Assume no errors occur during transmission. After Alice decrypts the message, which of her
plaintext blocks will be incorrect?
2. It was shown during the lecture that Double DES is vulnerable to chosen plaintext attack using
the meet-in-the-middle approach in which the number of steps is of order O(263). If you were to
conduct a similar chosen plaintext attack on Triple DES in the most efficient way possible, what
is the order of the number of steps you will require?
3. Users A and B are using the Diffie-Hellman key exchange. You are an interceptor who notes that
they are using the common prime p = 71 and generator g = 7. You observe that A next sends B
her public key X = 51, and B sends A his public key Y = 47. What is the shared secret key? Hint:
Use Python if your calculator is not able to help you here.
4. Consider a user communicating using the RSA public key cryptography. You have just
intercepted the ciphertext C = 6, sent to the user whose public key is e = 31, n = 247. What do
you think is the plaintext?
5. Suppose you know that one of your nosy friends is interested in the content of your encrypted
messages you send and receive. One day you discover that your private RSA key, (n1, d1),
happens to be the same as the public RSA key of your friend, (n2, e2). That is, n1 = n2 and d1 =
e2. Should you change your public and private keys? Explain your answer.
6. Decrypt the following message shown below in exactly 70 characters per line (except
on the last line).
nhjQHktQSktQUwSjQ?hjgQ,hjQMjx,QwqQ,hjQkgESkdQUMjk,EwgQSktQkUc.EMjQ,hwx
jQMEPh,xQ?hEUhQgjejMQUw.dHQhkejQ jjgQ?E,hhwdHjgQqMwSQ,hjSQ .,Q tQ,hjQh
kgHQwqQ,tMkggtVQnhjQmMjgUhQhkejQkdMjkHtQHExUwejMjHQ,hk,Q,hjQ dkUfgjxxQ
wqQ,hjQxfEgQExQgwQMjkxwgQ?htQkQh.SkgQ jEgPQxhw.dHQ jQk kgHwgjHQ?E,hw.,
QMjHMjxxQ,wQ,hjQUkJMEUjQwqQkQ,wMSjg,wMVQG,QSktQwgjQHktQUwSjQ,wQ jQMjUw
PgEYjHQ,hk,Q,hjQg.S jMQwqQdjPxyQ,hjQeEddwxE,tQwqQ,hjQxfEgyQwMQ,hjQ,jMS

Egk,EwgQwqQ,hjQwxQxkUM.SQkMjQMjkxwgxQjc.kddtQEgx.qqEUEjg,QqwMQk kgHwgE
gPQkQxjgxE,EejQ jEgPQ,wQ,hjQxkSjQqk,jVQvhk,QjdxjQExQE,Q,hk,Qxhw.dHQ,Mk
UjQ,hjQEgx.JjMk djQdEgjuQGxQE,Q,hjQqkU.d,tQwqQMjkxwgyQwMQJjMhkJxQ,hjQq
kU.d,tQwqQHExUw.MxjuQ-.,QkQq.ddzPMw?gQhwMxjQwMQHwPQExQ jtwgHQUwSJkMExw
gQkQSwMjQMk,EwgkdyQkxQ?jddQkxQkQSwMjQUwgejMxk djQkgESkdyQ,hkgQkgQEgqkg
,QwqQkQHktQwMQkQ?jjfQwMQjejgQkQSwg,hyQwdHVQ-.,Qx.JJwxjQ,hjtQ?jMjQw,hjM
?ExjyQ?hk,Q?w.dHQE,QkekEduQnhjQc.jx,EwgQExQgw,yQLkgQ,hjtQMjkxwguQgwMyQ
LkgQ,hjtQ,kdfuQ .,yQLkgQ,hjtQx.qqjMu
7. Consider a mono-alphabetic substitution cipher (each character in the plaintext is
substituted by the same or another character to generate the ciphertext) applied on English words
which use
the 26-character alphabet from a to z and no other characters. Assume the keys used by this cipher are
40
bits in length. You may assume that each one of all possible plaintext-ciphertext mappings is equally
likely
to be the mapping used by a key with this cipher. When using this cipher, what is the expected number
of
different keys which will result in the encryption of the 8-character plaintext tortoise into the 8-
character
ciphertext kmakmsuh?
3. Consider a block cipher that uses blocks of length n bits and keys of length s bits.
Assume s ≤ n. The secret key used by the cipher is k. You are an attacker and you do not know k but
you want to find out the value of k. You discover one plaintext-ciphertext pair, (m, c). So, you know that
there exists k such that E(k, m) = c. Now, suppose you guess the value of the key as k
0
and verify that
E(k

0
, m) = c. But, you cannot be sure that k
0 = k because there may be more than one key which encrypts
m to c.
This question is related to how confident you can be that your guess is correct. What is the probability
that there is no other s-bit key (besides k) which will encrypt the same plaintext, m, to the same
ciphertext,
c? In other words, what is the probability that there is no k
0 6= k such that E(k
0
, m) = c? State any
assumptions you make.
8.
A not-so-bright programmer writing a piece of software to implement DES ends
up implementing the mangler function as simply an XOR of Rn and Kn for encryption, for each of the
16 rounds. In addition, the programmer forgets to implement the initial and final permutations. You also
find out that the 48-bit keys used in the rounds are all a string of 0’s. You happen to intercept a message
encrypted using this software. If the intercepted ciphertext, in hex, is 0xaaaa bbbb cccc dddd, what is
the
plaintext?