CMSC 414   

			       Fall 2002

Homework # 1   				Solutions to Written Exercises

(Doing the programming problems first will probably help you to solve
the written problems.  It's OK to use your programs to solve the written
problems, but all steps must be explained in order to receive credit.
"Computer programs says XXXX" is NOT an explanation)



1.  	(Problem # 6 from Chapter 9 of the textbook) Deciphering 
	ciphertext generated by a Caesar cipher involves enciphering
	with a key which is different from the enciphering key.
	Why then is a Caesar cipher considered to be a classical
	cryptosystem instead of a public key cryptosystem.  Be
	specific.  

Recall, from page 279 of your text, and your lecture notes, that for
a public key cryptosystem, it must be computationally infeasable to 
derive the private key from the public key.  This obvsiously is not
the case with a Caesar Cipher.



2.  	As discussed in class, one-time pads are provably secure but 
	there are some logistical problems associated with their use.  
	Give an example of a situation where a one-time pad can easily  
	be used and an example where use of a one-time pad would be 
	difficult to implement.  (The example given in class is 
	acceptable, but expand and fully explain why)

Recall that a one time pad must have enough RANDOMLY generated material
to encrypt the entire message, w/out ever repeating.  Generating truly
random material is not easy, and distributing it to both parties can
be a problem.  We talked in class of an overseas embassy making use of a
one time pad.  In the olden days, you'd send a couple of Marines over
periodically  to escort the guy with the briefcase full of key material
handcuffed to his wrist.  This is a case where it works, there is 
an oppurtunity to get the key material to both parties.  If somebody
decides tomorrow to start spying for the US forces in Afghanistan, getting
that person the key material for a one-time pad might prove problematic.
That person keeping the key material safe and hidden could also be a problem,
which is not the case with the sanctioned embassy example.


3.  	The following ciphertext is suspected to be the output of a
	Vigenere cipher.  Solve for the plaintext, explaining all 
	assumptions and showing each step.  (Obtaining the correct
	plaintext without explaining the steps is NOT a correct solution,
	and will not receive any credit)  Also keep in mind the class
	discussion on transcription errors when working these problems:

	fycpa lgvqq gqmfc odzjr joert tpdne jrlla njixo alfeq
	qvyxz wqbsy tphry mfofo lsrak iniva lglfs cllbn eozrg
	yvivo lsvbe ajfek haahf cqtqg lqody brtos cyrjr nchfu
	iopyk phdwn eowai jfzge pxxqy emwum usatf xhryy vifty
	qfvhs mqmmh qsfkq rnqfe ioyxj rvhwn wfjoe kuzbf hkfec
	uenwf ouakf twpps yvzfo mprbd srddm dldnx pwedk zklel
	ycggi clrto alycg vpchz ioixf kqrng xwwui lxvkw s

	(Robert Heinlein)

Solution, in columns (Key = FRIDAY):  [This will be graded mainly on 
the method (as discussed in class, in your textbook, and on the
webpage).  This goes for 4 and 5 also]

	ahuma nbein gshou ldbea bleto chang eadia perpl anani
        nvasi onbut chera hogco nnash ipdes ignab uildi ngwri
        teaso nnetb alanc eacco untsb uilda walls etabo necom
        fortt hedyi ngtak eorde rsgiv eorde rscoo perat eacta
        lones olvee quati onsan alyze anewp roble mpitc hmanu
        repro grama compu terco okata styme alfig hteff icien
        tlydi egall antly speci aliza tioni sfori nsect s

or, with spacing and punctuation:

	A human being should be able to change a diaper, plan an invasion,
butcher a hog, conn a ship, design a building, write a sonnet, balance
accounts, build a wall, set a bone, comfort the dying, take orders, give 
orders, cooperate, act alone, solve equations, analyze a new problem,
pitch manure, program a computer, cook a tasty meal, fight efficiently, 
die gallantly. Specialization is for insects.

	 Robert A. Heinlein

	
4.	Please decipher the following ciphertext.  Explain each step.
	(correct plaintext with no explanation is not an valid answer):

	Uiptf xip xpvme hjwf vq fttfoujbm mjcfsuz up qvsdibtf b mjuumf 

	ufnqpsbsz tbgfuz eftfswf ofjuifs mjcfsuz ops tbgfuz

	(Ben Franklin)


Solution:

	Those who would give up essential liberty to purchase a little 

        temporary safety deserve neither liberty nor safety




5.	Please decrypt the following cipher text.  Show and explain all
	steps (correct plaintext with no explanation is not an valid 
	answer):

        A HGWSIHLK C SSCIQE WPVU E KRKAR WCXTVDGD LRAY QEH ZKNQDX

        FAANVCT YEC D IPVUTC ICMEUZIT

        PANVC T VDG PVFTC Q WTR UIGCXY HTG WTCVYROS G

        SEN S OVTEPY EDVUP DSWZ OWBGV SEX OPMLRK P MTHTK YRFYS EBYKP

        NAGMC S PTY XVJT A YYWY OO EWZUG WXX IBSV OHTVD GSRU LMQX WKY

        AVSRX AHGZSJ ZID SPZ A YQPX YPSMSR UVFCDXR JKK ZMTR E FYRKOEEMS

        DWINO VZJOWVHY H VGZ MT REFYR RUYRB SXYAO REEK LKXKGYOIBED


Solution (Key = HACKER), with the spacing above:

	T HEMORALI S OBVIOU SYOU C ANTTR USTCODET HATY OUD IDNOTT

        OTALLYC REA T EYOURS ELFESPEC

        IALLY C ODE FROMC O MPA NIESTH ATE MPLOYPEO P

        LEL I KEMENO AMOUN TOFS OURCE LEV ELVERI F ICATI ONORS CRUTI

        NYWIL L PRO TECT Y OUFR OM USING UNT RUST EDCOD EIND EMON STR

        ATING THEPOS SIB ILI T YOFT HISKIN DOFATTA CKI PICK E DONTHECCO

        MPILE RICOULDH A VEP IC KEDON ANYPR OGRAM HAND LINGPROGRAM

or, with nicer spacing:

	The moral is obvious. You can't trust code that you did not 
totally create yourself. (Especially code from companies that employ 
people like me.) No amount of source-level verification or scrutiny 
will protect you from using untrusted code. In demonstrating the 
possibility of this kind of attack, I picked on the C compiler. I could 
have picked on any program-handling program