Homework 5 Solution Set

Note: It was assumed that each student would start with 8 points. Each wrong answer took away from the 8 points, and an exceptional answer added to the 8 points.

1. (9.8.2)--(Courtesy of Rafael Bonilla)

 The Ceasar cipher is the widely known cipher in which letters are shifted using the formula:

c_i = E(p_i) = p_i + k

Given the ciphertext TEBKFKQEBZLROPBLCERJXKBSBKQP. A Statistical Analysis of Frequency shows us that B is the most common letter in the ciphertext. Using the table in page 29 of [2] (basically this table shows that e is the most common letter in plain English) we can find the correspondence B = e in plaintext. From this we realize that B has been shifted 3 position so k = 3 with high probability.

Given that k = 3 we construct the following table.

Plaintext

a

b

c

d

e

f

g

h

i

j

k

l

m

Ciphertext

D

E

F

G

H

I

J

K

L

M

N

O

P

Plaintext

n

o

p

q

r

s

t

u

v

w

x

y

z

Ciphertext

Q

R

S

T

U

V

W

X

Y

Z

A

B

C

Now, using this table to find the correspondences for each letter of the ciphertext with the plaintext we can decipher the message. For example T in the ciphertext is q in plaintext. By doing the same with each letter we have:

TEBKFKQEBZLROPBLCERJXKBSBKQP

wheninthecourseofhumanevents

Inserting spaces in all the appropriate places we have the final plaintext

When in the course of human events

Standard deductions were:

• +0.5           for exceptional answer.

2. (9.8.3)--(Courtesy of Ahmet Burak Can, and Wen Bian)

There are some technical difficulties in using one-time pad:

• The most important reason for that is sending key sequence to receiver in a secure channel (TA—Key distribution and management). Since the one-time pad ciphertext is unbreakable, it can be sent over computer networks easily. An eavesdropper can’t determine plaintext by only getting ciphertext. However, the key sequence can’t be sent over computer networks, phone line, satellite link etc. All of these communication medium can be eavesdropped, you can’t guarantee the security of these mediums. Someone may advise enciphering the key sequence using 3DES, IDEA, Rijndael kind of algorithm and sending it over some communication medium. However, in this case, the security of the key sequence, (which is equal to security of one-time pad) is dependent the breakability of the enciphering algorithm. Since none of these algorithms are provably secure, we can’t trust them for securing key sequence. … Because of these concerns, in history, one-time pad key sequence is generally stored in a tape medium and brought to the receiver by a human carrier. All of these methods are not easy to apply, thus one-time pads are not a preferred method of communication.
• For example, key sequence is sent securely to the receiver. This key sequence can be used only one time. For the next time communication, another key sequence have to be sent. If sender encrypts two plaintexts with same key sequence, an adversary who captured two ciphertexts can easily break it by doing,.
• TA—Others mentioned the fact that after use, a key needs to be destroyed.
• Random generation of key as long as plaintext is not an easy task. Random number generators in computers do not produce provably random numbers. Thus, an attacker may guess the possible key sequences and may break whole plaintext or a part of it. Using some psychical inputs, for example, temperature, noise, voltage change (in very low sensitivity) etc. or using special devices better random numbers can be produced. … (TA—Hash anything together that has at least some randomness. If one bit of the input is changed, a good hash function will change roughly half of the output bits).
• There are certain other codes that present advantages over one time pads, and are nearly unbreakable, and therefore used in practice. (TA—In other words, other encryption algorithms exist that are good enough and don’t have the above limitations).

Standard deductions were:

• +0.5           for exceptional answer.
• -0.5 where I felt from the answer given, the problems presented could be practically overcome. For example, I think if random number generation were the only difficulty, we would use one-time-pads all the time.

Note from TA: 

Many people also said that one-time-pads don’t provide any authentication. I do not believe this is a significant problem; DES keys don’t provide authentication either (see 10.10.6) and are used regularly.

3. (9.8.9)--(Courtesy of Haiya Zou)

 The Diffie-Hellman Key exchange protocol works like the following:

1)Two users agree on a common large p and a constant value g.

2)Alice select a private key in and compute

3)Bob select a private key in and compute

4)Alice send to bob, and bob send to Alice.

5)Alice compute , and Bob compute ,

Then:

Since , so . Alice and Bob can choose certain agreed-upon bits from (or ) to use as their share keys. Thus two users will have the same shared key.

Standard deductions were:

• +0.5           for exceptional answer.

4. (9.8.13)--(Courtesy of Ather Imran Nawaz)

Ciphertext corresponding to 0,1 and n-1 is the same as the message. Hence RSA encipherment function is an example of an unconcealed function (a function f(x) for which at least one x exists for which x = f(x))

RSA function is M^e mod n, where M is the message and e is the public key of the recipient.

For 0, (0)^e mod n = 0 mod n = 0

For 1, (1)^e mod n = 1 mod n = 1

For proving (n-1)^e mod n = n – 1, we give the following argument.

(n-1)^e = n^e + an^e-1 + …. + bn + (-1)^e

where a and b are constants. As we are moving to the right, the power of the constant term increases while that of n decreases. a and b are abstracted as constants that represent the entire constant term evaluation.

We note that each term other than the last term has n to some power greater than 1. Hence when such expansion is used and each term is evaluated mod n, the n^k factor of the term will force it to be 0.

We are only left with the last term which is (-1)^e. Note that in RSA, e is a term which is relatively prime to Ф(n). Ф(n) is equal to (p-1)(q-1) where p and q are the two secret primes of RSA. Ф(n) is an even number since (p-1) and (q-1) are even. Hence e has to be odd. (-1)^e will always be -1.

Hence,

(n-1)^e mod n = (-1) mod n = n – 1

There do exist other messages that produce the same ciphertext as themselves. Such messages are called unconcealed messages. The number of unconcealed messages in an RSA system depends on the values e, p and q. A formula exists that determines the number of unconcealed messages in an RSA system. The formula is:

# of unconcealed messages = (1 + gcd(e-1, p-1))(1 + gcd(e-1, q-1))

Standard deductions were:

• +0.5           for exceptional answer.
• -0.5 many forgot to answer the second part of the question

Note from TA:

I gave credit for any attempt at the second part, as the question may have been unclear. Yes there do exists other cases where messages produce the same cipher text as plain text; however, not for all keys. So the answer could be yes or no depending on how the question was read.

5. (10.10.6)--(Courtesy of Ziad El Bizri)

This protocol does not authenticate Bob and is very dangerous to use, it fails very badly to the man-in-the-middle attack. Assume the following scenario:

Mallory contacts Alice and pretends to be Bob

Alice sends $\{r\}k$ to Mallory

Mallory receives the message and forwards it to Bob

Bob receives the message and sends $\{r+1\}k$ to Mallory

Mallory receives the message and forwards it to Alice

Mallory is now authenticated as Bob for Alice

>From this attack, we see how this authentication protocol fails.

Also, it can be even more dangerous: assume that the ``classical'' cryptosystem is based on exponentiation with a public modulus $p$ (such as RSA, Diffie-Hellman, ...). Then after another round of messages Mallory will have accumulated $r_1^k$ mod $p$, $(r_1+1)^k$ mod $p$, $r_2^k$ mod $p$, $(r_2+1)^k$ mod $p$.

Using these four messages, since $(r_1+1)^k$ mod $p$ can be rewritten as $r_1^k + kr_1^{k-1}+...+kr_1+1$ mod $p$ and $r_1^k$ mod $p$ is known, Mallory can compute $x_1 = (r_1+1)^k - r_1^k - 1$ mod $p$ which would be $x_1 = kr_1^{k-1}+...+kr_1$ mod $p$. He can do the same thing to compute $x_2 = (r_2+1)^k - r_2^k - 1$ mod $p$, or $x_2 = kr_2^{k-1}+...+kr_2$ mod $p$.\\

He can now compute $k$ by performing $k = gcd(x_1,x_2)$.

Also, if the encryption scheme uses instead a synchronous stream cipher, then assuming the last bit in $r$ is 0 (an average of two messages is needed for Mallory to find such an $r$), then this addition of 1 would be considered as a bit flipping, and this can also be used by Mallory to do an attack on the authentication scheme. 

Standard deductions were:

• +0.5           for exceptional answer.
• -0.5 for incorrect answers, or answers with the wrong reason why.

Note from TA:

The problem here is that Alice wishes to authenticate that someone she is “corresponding” with (using the wording in the question) is indeed Bob. In a passive attack where Eve sits between Alice and Bob (sniffs the line or routes traffic to and from) yet Alice is still corresponding with Bob, this authentication would work as the identity of Bob would be bound to the correspondent correctly. However, in a traditional man-in-the-middle attack, Alice is corresponding with Eve. Eve can make Alice believe she is Bob by replaying Alice’s challenge to Bob and then replaying Bob’s replies back to Alice. In this case, Alice believes the correspondent is Bob when it is really Eve.

There is a subtle difference between Eve pretending to be Bob, and Eve intercepting and relaying messages between Alice and Bob. In the first case, Eve is authenticated as Bob. In the second, Bob is authenticated as Bob. A number of people confused the two cases.

Also, in the future, please include a yes or no answer in your response. Arguing both ways can make grading difficult.

Also, please excuse the tex notations.

6. (10.10.9) (Courtesy of John Woodfin)

If Alice signs then enciphers the contract, the message sent to Bob is in the form:

(M^da mod na)^eb mod nb

Bob can decrypt the message using Alice's public key, but in order to create a new message he must either alter Alice's public key or determine her private key. The first option is impossible because Alice's public key is presumably well-known and published. The second option is computationally infeasible.

7. (11.8.3)

a) (courtesy Dan Aiello)

n = number of bits per key

l = length of ciphertext c0

Since the key length is n bits, then the number of possible keys is 2^n. If there are 2^n entries on the table, and each is of length l, then it would take l*2^n bits of memory to store. It takes 1 unit of time to do each encryption, and since we do it for 2^n keys, it takes 2^n time units to calculate the table.

c) (courtesy of Saumya Agarwal)

He can confirm this by using the other plaintext, ciphertext pair m1,c1 by verifying that c1 = Ex'(Ex(m1)) for x and x' got in part (b). If so, x and x' are the desired key pair, else they are incorrect.

d) (courtesy of Mercan Karahan)

This attack depends on keeping X in memory and sorting them according to Ex(m0) and then searching for generated Dx'(c0) in the sorted list for every (X', Dx'(c0)) pair.

Maximum time spent is, time spent for generation (X, Ex(m0)) pairs plus generation of (X', Dx'(c0)) pairs and search (it is 0(1) after generation). This makes:

maxt = 2^n + 2^n = 2^(n+1)

Expected time depends on average time of search for a matching pair between Ex(m0) and Dx'(c0), which is 2^n / 2. Thus expt = 2^n + 2^(n-1)

Memory usage for both worst and expected case is the same, n* 2^n, each line has a key.