Lab 4 Assignment 
			Due on Friday, Oct 28, 2005 
                    ------------------------------------

1. If P is a prime and a is relative prime to P (a<P), prove the following is true:

          a^(p-2)= a^(-1) mod (P)

2. Alice wants to give her bike to Bob, but their schedules make it impossible for them 
to meet. If both of them have bike locks, can Alice let Bob have her bike without someone
 else stealing it? How?

3. What's the man-in-the-middle attack? give a brief description of this kind of attack.

4.you have just received an offer to join a startup that is in the network security business.
  They have a patent on an authentication mechanism that works as follows.

Two people (Alice and Bob) want to verify that each has a key X of length b bits.  Alice selects
 a random binary string S of length b, computes S' = (S xor X), and sends S' to Bob.  Bob, who
 has key X', now computes S'' = (S' xor X') and sends S'' to Alice.

To verify if Bob's key X' is the same as her key X, Alice can now simply check if S'' is identical
 to S.  Neither Alice nor Bob have sent their key over the connection, and the method is very fast.

Would you take up the offer?  Explain in as much detail as possible.

5. Decrypt the cipher text in Appendix 1.  Show in detail the steps that you followed.


--------------------------------------------------
Appedix 1
---------------------------------------


Iy cgo yuw iwoy pe yvnwo, vy cgo yuw cploy pe yvnwo, 
vy cgo yuw gmw pe cvoxpn, vy cgo yuw gmw pe epprvoudwoo, 
vy cgo yuw wzpku pe iwrvwe, vy cgo yuw wzpku pe vdklwxjrvyb, 
vy cgo yuw owgopd pe Lvmuy, vy cgo yuw owgopd pe Dglsdwoo, 
vy cgo yuw ozlvdm pe upzw, vy cgo yuw cvdywl pe xwozgvl, 
cw ugx wfwlbyuvdm iweplw jo, cw ugx dpyuvdm iweplw jo, 
cw cwlw grr mpvdm xvlwky yp Hwgfwd, cw cwlw grr mpvdm xvlwky 
yuw pyuwl cgb--vd ouply, yuw zwlvpx cgo op egl rvsw yuw zlwowdy
zwlvpx, yugy opnw pe vyo dpvovwoy gjyuplvyvwo vdovoywx pd vyo
iwvdm lwkwvfwx, epl mppx pl epl wfvr, vd yuw ojzwlrgyvfw xwmlww
pe kpnzglvopd pdrb.

Tuwlw cwlw g svdm cvyu g rglmw qgc gdx g tjwwd cvyu g zrgvd egkw,
pd yuw yulpdw pe Edmrgdx; yuwlw cwlw g svdm cvyu g rglmw qgc gdx
g tjwwd cvyu g egvl egkw, pd yuw yulpdw pe Flgdkw.  Id ipyu
kpjdylvwo vy cgo krwglwl yugd klboygr yp yuw rplxo pe yuw Sygyw
zlwowlfwo pe rpgfwo gdx evouwo, yugy yuvdmo vd mwdwlgr cwlw
owyyrwx epl wfwl.

Iy cgo yuw bwgl pe Ojl Lplx pdw yupjogdx owfwd ujdxlwx gdx
owfwdyb-evfw.  Szvlvyjgr lwfwrgyvpdo cwlw kpdkwxwx yp Edmrgdx gy
yugy egfpjlwx zwlvpx, go gy yuvo.  Mlo. Spjyukpyy ugx lwkwdyrb
gyygvdwx uwl evfw-gdx-ycwdyvwyu irwoowx ivlyuxgb, pe cupn g
zlpzuwyvk zlvfgyw vd yuw Lvew Gjglxo ugx uwlgrxwx yuw ojirvnw
gzzwglgdkw ib gddpjdkvdm yugy gllgdmwnwdyo cwlw ngxw epl yuw
ocgrrpcvdm jz pe Lpdxpd gdx Wwoynvdoywl.  Efwd yuw Cpks-rgdw
mupoy ugx iwwd rgvx pdrb g lpjdx xpawd pe bwglo, geywl lgzzvdm
pjy vyo nwoogmwo, go yuw ozvlvyo pe yuvo fwlb bwgl rgoy zgoy
(ojzwldgyjlgrrb xwevkvwdy vd plvmvdgrvyb) lgzzwx pjy yuwvlo.
Mwlw nwoogmwo vd yuw wglyurb plxwl pe wfwdyo ugx rgywrb kpnw yp
yuw Edmrvou Clpcd gdx Pwpzrw, elpn g kpdmlwoo pe Blvyvou ojiqwkyo
vd Anwlvkg:  cuvku, oylgdmw yp lwrgyw, ugfw zlpfwx nplw vnzplygdy
yp yuw ujngd lgkw yugd gdb kpnnjdvkgyvpdo bwy lwkwvfwx yulpjmu
gdb pe yuw kuvkswdo pe yuw Cpks-rgdw ilppx.

Flgdkw, rwoo egfpjlwx pd yuw cuprw go yp ngyywlo ozvlvyjgr yugd
uwl ovoywl pe yuw ouvwrx gdx ylvxwdy, lprrwx cvyu whkwwxvdm
onppyudwoo xpcd uvrr, ngsvdm zgzwl npdwb gdx ozwdxvdm vy.  
Udxwl yuw mjvxgdkw pe uwl Culvoyvgd zgoyplo, ouw wdywlygvdwx
uwlowre, iwovxwo, cvyu ojku ujngdw gkuvwfwnwdyo go owdywdkvdm
g bpjyu yp ugfw uvo ugdxo kjy pee, uvo ypdmjw ypld pjy cvyu
zvdkwlo, gdx uvo ipxb ijldwx grvfw, iwkgjow uw ugx dpy sdwwrwx
xpcd vd yuw lgvd yp xp updpjl yp g xvlyb zlpkwoovpd pe npdso
cuvku zgoowx cvyuvd uvo fvwc, gy g xvoygdkw pe opnw eveyb pl
ovhyb bglxo.  Iy vo rvswrb wdpjmu yugy, lppywx vd yuw cppxo pe
Flgdkw gdx Nplcgb, yuwlw cwlw mlpcvdm ylwwo, cuwd yugy ojeewlwl
cgo zjy yp xwgyu, grlwgxb nglswx ib yuw Wppxngd, Fgyw, yp kpnw
xpcd gdx iw ogcd vdyp ipglxo, yp ngsw g kwlygvd npfgirw elgnwcpls
cvyu g ogks gdx g sdvew vd vy, ywllvirw vd uvoyplb.  Iy vo rvswrb
wdpjmu yugy vd yuw lpjmu pjyupjowo pe opnw yvrrwlo pe yuw uwgfb
rgdxo gxqgkwdy yp Pglvo, yuwlw cwlw ouwrywlwx elpn yuw cwgyuwl
yugy fwlb xgb, ljxw kglyo, iwozgyywlwx cvyu ljoyvk nvlw, odjeewx
gipjy ib zvmo, gdx lppoywx vd ib zpjrylb, cuvku yuw Fglnwl, Dwgyu, 
ugx grlwgxb owy gzgly yp iw uvo yjnilvro pe yuw Rwfprjyvpd.  
Bjy yugy Wppxngd gdx yugy Fglnwl, yupjmu yuwb cpls jdkwgovdmrb,
cpls ovrwdyrb, gdx dp pdw uwglx yuwn go yuwb cwdy gipjy cvyu
njeerwx ylwgx:  yuw lgyuwl, eplgonjku go yp wdywlygvd gdb ojozvkvpd 
yugy yuwb cwlw gcgsw, cgo yp iw gyuwvoyvkgr gdx ylgvyplpjo.

Id Edmrgdx, yuwlw cgo okglkwrb gd gnpjdy pe plxwl gdx zlpywkyvpd
yp qjoyveb njku dgyvpdgr ipgoyvdm.  Dglvdm ijlmrglvwo ib glnwx
nwd, gdx uvmucgb lpiiwlvwo, ypps zrgkw vd yuw kgzvygr vyowre
wfwlb dvmuy; egnvrvwo cwlw zjirvkrb kgjyvpdwx dpy yp mp pjy pe
ypcd cvyupjy lwnpfvdm yuwvl ejldvyjlw yp jzuproywlwlo' cglwupjowo
epl owkjlvyb; yuw uvmucgbngd vd yuw xgls cgo g Cvyb ylgxwongd vd
yuw rvmuy, gdx, iwvdm lwkpmdvowx gdx kugrrwdmwx ib uvo ewrrpc-
ylgxwongd cupn uw oypzzwx vd uvo kuglgkywl pe "yuw Cgzygvd,"
mgrrgdyrb oupy uvn yulpjmu yuw uwgx gdx lpxw gcgb; yuw ngrr cgo
cgbrgvx ib owfwd lpiiwlo, gdx yuw mjglx oupy yulww xwgx, gdx yuwd
mpy oupy xwgx uvnowre ib yuw pyuwl epjl, "vd kpdowtjwdkw pe yuw
egvrjlw pe uvo gnnjdvyvpd:" geywl cuvku yuw ngrr cgo lpiiwx vd
zwgkw; yugy ngmdvevkwdy zpywdygyw, yuw Lplx Mgbpl pe Lpdxpd, cgo
ngxw yp oygdx gdx xwrvfwl pd Tjldugn Glwwd, ib pdw uvmucgbngd,
cup xwozpvrwx yuw vrrjoylvpjo klwgyjlw vd ovmuy pe grr uvo
lwyvdjw; zlvopdwlo vd Lpdxpd mgpro epjmuy igyyrwo cvyu yuwvl
yjldswbo, gdx yuw ngqwoyb pe yuw rgc evlwx irjdxwlijoowo vd gnpdm
yuwn, rpgxwx cvyu lpjdxo pe oupy gdx igrr; yuvwfwo odvzzwx pee
xvgnpdx klpoowo elpn yuw dwkso pe dpirw rplxo gy Cpjly
xlgcvdm-lppno; njoswywwlo cwdy vdyp Sy. Gvrwo'o, yp owglku epl
kpdylgigdx mppxo, gdx yuw npi evlwx pd yuw njoswywwlo, gdx yuw
njoswywwlo evlwx pd yuw npi, gdx dpipxb yupjmuy gdb pe yuwow
pkkjllwdkwo njku pjy pe yuw kpnnpd cgb.  Id yuw nvxoy pe yuwn,
yuw ugdmngd, wfwl ijob gdx wfwl cplow yugd jowrwoo, cgo vd
kpdoygdy lwtjvovyvpd; dpc, oylvdmvdm jz rpdm lpco pe nvokwrrgdwpjo 
klvnvdgro; dpc, ugdmvdm g upjowilwgswl pd Sgyjlxgb cup ugx iwwd
ygswd pd Tjwoxgb; dpc, ijldvdm zwpzrw vd yuw ugdx gy Nwcmgyw ib
yuw xpawd, gdx dpc ijldvdm zgnzurwyo gy yuw xppl pe Wwoynvdoywl Hgrr;
yp-xgb, ygsvdm yuw rvew pe gd gylpkvpjo njlxwlwl, gdx yp-npllpc pe g
clwykuwx zvrewlwl cup ugx lpiiwx g eglnwl'o ipb pe ovhzwdkw.

Arr yuwow yuvdmo, gdx g yupjogdx rvsw yuwn, kgnw yp zgoo vd
gdx krpow jzpd yuw xwgl prx bwgl pdw yupjogdx owfwd ujdxlwx 
gdx owfwdyb-evfw.  Edfvlpdwx ib yuwn, cuvrw yuw Wppxngd gdx yuw
Fglnwl cplswx jduwwxwx, yupow ycp pe yuw rglmw qgco, gdx yupow
pyuwl ycp pe yuw zrgvd gdx yuw egvl egkwo, ylpx cvyu oyvl wdpjmu,
gdx kgllvwx yuwvl xvfvdw lvmuyo cvyu g uvmu ugdx.  Tujo xvx yuw
bwgl pdw yupjogdx owfwd ujdxlwx gdx owfwdyb-evfw kpdxjky yuwvl
Glwgydwoowo, gdx nblvgxo pe ongrr klwgyjlwo--yuw klwgyjlwo pe yuvo
kulpdvkrw gnpdm yuw lwoy--grpdm yuw lpgxo yugy rgb iweplw yuwn.