Cryptographic Challenges

The assignment content involves four problems: (1) decrypting a message using a mono-alphabetic substitution cipher with a key of 40 bits, (2) finding the expected number of keys that encrypt an 8-character plaintext into a given ciphertext, (3) calculating the probability that there is no other key that encrypts a given plaintext to a given ciphertext in a block cipher, and (4) determining the plaintext message from an intercepted ciphertext by fixing errors in a DES implementation.

1. 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
2. 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.
4.
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?