Solutions to the csc609/706 Midterm 
spring 2015-2016 semester (161 in old numbering)

burt rosenberg
solutions 12 oct 2019



*** Problem 1:

no solution provided.





*** Problem 2: 

The Feistel gadget was invented by Horst Feistel, who was born in Berlin in 1915, with
degrees from MIT and Harvard, and then worked for IBM on ciphers. 
He invented LUCIFER and co-invented DES.

You can read off from the diagram:

    R0==L1, L1==R2, and R2==L3. 

so L3==R0

also R3 = L2 + F_k(R0)  because R0==R2.  
  
But L2 = L0 + F_k(R0), so the F_k(R0)s cancel and R3 = L0.


*** Problem 3:

Let delta be the exclusive or between m_j and m'_j. then you can write out the 
equations to show that c'_j = c_j ex-or delta, and the tag is also changed just 
by exclusive-or of the delta.

    tag' =  (  (+)_{i != j} m_i )  (+) m'_j (+) G_k(n+1) 
         = m'_j (+)  ( tag (+) m_j ) = tag (+) delta
          


*** Problem 4:

Try different plaintexts of the form IV=0, P1=0, and P2 varies, until C1==C2.

(must there be such a P2? Why?)

then E_k2(E_k1(0)) == E_k2(E_k1(  P2 + E_k1(0) ) .
then 0 == P2+E_k1(0) implying P2 == E_k1(0)

now try all k1 for the one the encrypt 0 to P2,
and all k2 that encrypts P2 to C1


*** Problem 5:

Pr(m=0) = 3/4
Pr(m=1) = 1/4
Pr(k=0) = 2/3
Pr(k=1) = 1/3

(a) the calculate the probability of the event c=0, consider what events must 
    occur so that c=0. in this context, and event would be saying whether m is 
    0 or 1 and whether k is 0 or 1. 
    
    the relationship between choosing 0 or 1 for m, and 0 or 1 for k are independent,
    so you can multiply probabilities to get the probability that the events occur
    together.
    
    the events that lead to c=0 when m is 0 or m is 1 are disjoint, so you can add these.
    
    the result, I think, is 7/12
    
(b) the result, I think, is 5/12

(c) use Bayes:   Pr(m|c) = Pr(c|m)Pr(m)/Pr(c).  
    we use Bayes because Pr(c|m)=Pr(k), that is, given say m=0, the probability that
    c=0 becomes the probability that k=0.
    
    the result, I think, is 6/7
   
(d) if you don't like bayes, then the Pr(m|c) = Pr(m and c)/Pr(c). m and c are not 
    independent, but m and k are, and there is a direct correspondence between c and k,
    = Pr(m)Pr(k)/Pr(c) where the m event is it being 1, the c event is it being 1, and
    therefore the k event is it being 0.

    or use Bayes :)

    the result, I think, is 2/5
    
(e) guess what is more likely, given the ciphertext.
    if on seeing a c=0 the probability is 6/7 m=0 (hence 1/7 m=1), what should you guess
    is m?
    
    and a similar consideration (following (d))  when c=1?
    
    the result, I think, is always guess 0.
    
(f) and if you always guess 0, you are right 3/4 of the time, because that is the 
    frequency that m=0.

(g) so is this a perfect cipher? it seems that Pr(M|C)=P(M) in this case.

    There are really only four strategies for guessing the message.
    1- guess c, you get m correct when k=0, or 2/3 of the time
    2- guess not c, you get m correct when k=1, or 1/3 of the time
    3- guess 0, you get m correct when m=0, or Pr(m=0) of the time
    4- guess 1, you get m correct when m=1, or Pr(m=1) of the time
    
    In the situation presented, we take option (3). It provides a correct answer
    3/4 of the time.
  
    But when P(m=1/2), then option (1) is the best, providing a correct answer 
    2/3 of the time.
    
    Review in detail the definition of perfect secrecy and see how this adds up.

    

*** Problem 6:

no solution provided.


*** thanks to Shengxin Luo for correcting my solution 5(c)