Ipnfxpsl $4

TD811 ==Npefso Jogpsnbujpo Qspupdpmt

Cptupo Vojwfstjuz

 

Assigned:  November 5, 2002.  Start early!

DUE:  November 25 at the beginning of class.

 

In each case, to get full credit you must a)  show your work, mentioning the techniques used for decryption; b) include any programs you use for the decoding.  You might want to make use of Maple or Mathematica, available on engc, for large-integer arithmetic.

 

1.  [40 points]

a)  Agents have determined that the following English message was encrypted with a substitution cipher.  Please decode it:


foxpxefmxqqrhxjrqxpdlbxbuqiphryihxpxaxdinoxafoxsxztxphforpbdlpfxpfqraxtxwfwlazluflbxdinoxauqiphfoxfxdopivuxqzlumrzoryxtxrapxbipdtrqqdrpzlublif

 

b)  The following strange cipher was found on an e-mail signature sent to you by a friend.  What does it say?


KCCPKBGUFDPHQTYAVINRRTMVGRKDNBVFDETDGILTXRGUDDKOTFMBPVGEGLTGCKQRACQCWDNAWCRXIZAKFTLEWRPTYCQKYVXCHKFTPONCQQRHJVAJUWETMCMSPKQDYHJVDAHCTRLSVSKCGCZQQDZXGSFRLSWCWSJTBHAFSIASPRJAHKJRJUMVGKMITZHFPDISPZLVLGWTFPLKKEBDPGCEBSHCTJRWXBAFSPEZQNRWXCVYCGAONWDDKACKAWBBIKFTIOVKCGGHJVLNHIFFSQESVYCLACNVRWBBIREPBBVFEXOSCDYGZWPFDTKFQIYCWHJVLNHIQIBTKHJVNPIST


2.  [15 points]  Alice seeks to meet Pierre for a clandestine romantic encounter at the production of a French theater company, which she has encoded using RSA encryption with public key N = 22,879 and encryption exponent 259:


08864 00235 20699 08186 16629 01277 16675 19828 12791

Alice's jealous ex-boyfriend, Oscar, has hired you at significant expense to find out the location of the meeting.  Decrypt the message.

 

3.  [45 points]  Alice discovers that Oscar is spying on her and changes her public key.  Oscar has hired you to crack the key (i.e. determine p and q) in each case:

a)  Alice has made her key much longer...unfortunately, she picked p and q terribly:
N = 37649606755989309660848896543522520184860442468875173906157
e = 3

b)  Alice has tried to pick better and much large p and q, but failed yet again (though not as obviously):
N=2073460713594865259966662742102733483131915732787396625056411028069852706118260281187468578469941017601
e=3

c)  Alice has improved her key, but Oscar has managed to determine the secret key d by hacking into her private computer:
N=49292648137019202972571737254366871219319612585889780030657
e=3
d=39434118509615362378057389803136588904534865635739948641181

4. [EXTRA 0.25 points]  Factor N=188198812920607963838697239461650439807163563379417382700763356422988859715234665485319060606504743045317388011303396716199692321205734031879550656996221305168759307650257059