12 Example: Playfair Cipher - EECS at UC Berkeley

1 Pairskeyword219playfairkeyword12 Example: PlayfairCipherProgramfileforthis chapter:Thisprojectinvestigatesa cipherthatis ,thereis nota singletranslationofeachletterofthealphab et;thatis,youdon t justdecidethatevery B , howit start, ,I llpicktheword. Nowwritethelettersofthatwordinthefirstsq uaresofa fivebyfivematrix:KEYWORDT henfinishfillinguptheremainingsquaresoft hematrixwiththeremaininglettersofthealph abet,inalphabeticalorder. Sincethereare26lettersandonly25squares,w eassignI andJ YD ON TY OUYI EA ES VK EZjuiceWHY A BIJWHYIYJYWYEK rowkind220 Chapter12 Example: PlayfairCipherKEYWORDABCFGHI JLMNPQSTUVXZ(Actually, whenchoosingthekeyword,besidesmakingsure thatnoletterappearstwiceyoumustmakesuret hatI andJ donotbothappear. Forexample,wouldn t doasa keyword.)To enciphera message,divideit ,thesentence Why, don t you? becomesNow, findeachpairoflettersinthematrixyoumadee arlier.

2 Mostpairsofletterswillformtwocornersofa ,inmymatrix,thefirstpairofletters() areattwocornersofa two-by-threerectanglealsocontaining,,, and. Theencipheringofthepairis thepairatthetwoothercornersofthisrectang le,namely. (Icouldalsohavechosen, inthiscase.)It simportanttobeconsistentabouttheorderoft henewpair:theonethatcomesfirstistheoneon thesameasthefirstoftheoriginalpair. Inthiscase,is onthesamerowas. We cancontinuetotranslatetheremainingpairso flettersinthesameway, endingupwithNoticethattheletterturnedint ointhesecondpairofletters,butit codesecretis ,toa cryptographer, area deadgiveawaythata PlayfaircipherwasQWWQCOCOCOCOLCOZCOEWYOW QBXEEYYDDQdoChapter12 Example: PlayfairCipher221 Yie ae, ME TO TH EW IN DO WLC NK ZK VF YO GQ CE BXTH EB IG WH EE LQTH EB IG WH EQ ELused,soit s traditionaltoinsertirrelevantspacingandp unctuationintheactualwrittenversionofthe message,likethis:Ofcoursetherecipientoft hemessage,knowinghowthemessagewasencoded , ,considerthemessage, Cometothewindow.

3 Firstwedivideit upintopairs:Thefirstproblemis solvethisproblemwesimplyaddanextraletter at theend,generally. Inthisexample,thefinalbecomesa youlookupthefirstpairofletters,, inmymatrix,you llfindthattheydonotdeterminea rectangle,becausetheyareinthesamecolumn. (Strictlyspeaking,theydeterminea one-by-tworectangle,butthetwodiagonalsar ethesame,sothatwouldbeencodedasif wefollowedtheusualrule.)Fortwolettersint hesamecolumn,theruleis toreplaceeachletterbytheonebelowit,sobec omes. (Ifoneofthelettersis attheendofthecolumn,it is replacedbythetopletter. So,forexample,wouldbecome.)Similarly, fortwolettersinthesamerow, eachis cannowtranslatetheentiremessage:Thepair, ona singlerow, hasbecome; thefinalpair, ona singlecolumn, theoneinwhichthesameletterappearstwicein a ,thephrase thebigwheel dividesintoThepairis treatedspecially. It couldbetranslatedinto(treatingit astwolettersinthesamerow)orinto(ifyouthi nkofit astwolettersinthesamecolumn).

4 Instead,though,theruleis :PlayfairCipherWHYJYIJIJE T AKFDZYKEOTYFIIT DA ZTEKYWEB I J Q XIQXGYFK VFZKGYHE thethemthenVFTHZKTOFKRT worthor toVF WD LH YJ WN OGZK DW KC SE XM ZK DW VF RV LQ VF WN ED MZ LW QE GY VF KD XF MP WC GOBF MU GY QF UG ZK NZ IM GK FK GY ZS GQ LN DP AB BM CK OQ KL EZ KF DHYK ZN LK FK EU YK FK KZ RY YD FT PC HD GQ MZ CP YD KL KF EZ CI ON DPAC WK QS SY QL UN DU RU GY NSThisversioncannowbetranslatedinto(Noti cethatI chosetotranslateintoinsteadofinto. Youshouldusesomeofeachwhencodinga cipherwithnos atall,oronewitha simplepatternofandalternating,is anothergiveawaythatthePlayfaircipherwasu sed.)Whataboutthefrequenciesoflettersina Playfair -encodedmessage?Youcan tsimplysaythatthemostcommonlettersarelik elytorepresentoror, becausealetterdoesn t representa singleletterthatway. Butit is stillpossibletosaythata commonletterinthecodedversionis ,hereis a well-knowntextinPlayfair-codedform:Themo stcommonlyoccurringlettersinthiscodedtex tare(19times),(12times),and(tiedat11),an d(10times).

5 Is onthesamerowasbothand, (especiallyinthecommonpair);canrepresent ;canrepresent. Ofallthelettersthatmightrepresent, whyshouldandbethepopularones? , forexample,theotherletterofthe(cleartext )pairmustbe,,,, or. Ofthese,onlyis particularlycommon, youweretryingtobreaka Playfaircipher, ,inthemessageabove,theonlypairsthatoccur morethantwiceare, fourtimes,and,, and, s a goodguessthateachofthesecorrespondstoa commonly ,asit turnsout,correspondsto, whichis notonlyawordbyitselfbutalsopartof,,, , anextremelycommonpair;correspondsto, whichis againa ,,correspondsto. Thisis notsucha commonEnglishpair, althoughit doescomeupinwordslike. Butit turnsoutthatintheparticularsampletextI musing,thispairofletterscomesupmostlyasp artsoftwowords, ,DataRedundancy223printplayfair "keyword [cometo the window]?lcnkzkvfyogqcebxmake"matrix {{k e y w o} {r d a b c} {f g h i l}{m n p q s} {t u v x z}}to letter:rowcoloutput mditem:rowcol :matrixend* Inthetic-tac-toeprogram,I useda one-dimensional arraytorepresenttheboard,eventhougha tic-tac-toeboardis couldhaveusedanarrayofthreearraysofthree numberseach,butthatwouldn t ,theninesquaresarenamed1 ,forexample,notinrow3, , Playfaircipher, youcanseeanexampleina mystery ,I mlessambitious:theprogrammerelyenciphers a message, word, listofwords, ,andthecleartextinputmustcontainonlyword sofletters, anexample:isanoperationwhoseoutputisa ,thefirstquestionI thoughtaboutwashowtorepresentina atwo-dimensionalarray thatis,anarraywithfivemembers,eachofwhic his anarrayoffiveletters.

6 *Soif thekeywordisthentheprogramwill,ineffect, dothis:Thepositionofa letterinthematrixis representedasa listoftwonumbers, includesanoperationthattakessucha listasaninput,alongwitha multi-dimensionalarray, andoutputsthedesiredmember:make"a [2 3]make"w [1 4]make"z [5 5]redundantspace/timetradeoff;224 Chapter12 Example: PlayfairCipherIJkeywordTAT[5 1]A[2 3][5 3][2 1] (Theactualprocedurelistedattheendofthiss ectionincludesa slightcomplication todealwiththecaseofand, butthat s notimportantrightnow.)ThePlayfairprocess goeslikethis:Theprogramis findseachletterinthematrix,determineseac hletter s rowandcolumnnumbers,thenrearrangesthosen umberstomakenewrowandcolumnnumbers, ,supposewearegiventhekeywordandtheletter sand. Thefirststepis totranslateintotherowandcolumnlist,andto translateinto. Thentheprogrammustcombinetherowofonelett erwiththecolumnoftheother, givingthenewlistsand.

7 Finally, ,butwhataboutthefirststep?We needtheinverseoperationof, onethattakesa wouldbepossibletowriteaprocedurethatwoul dexamineeachletterinthematrixuntilit locatedthedesiredletter. ,I decidedtokeepinformationaboutthematrixin theformof26variables,oneforeachletter, eachofwhichcontainsthecoordinatesofthatl etter. Thatis,thevariablestaketheformandsoon.(A sinthecaseofthevariablenamedabove, ,usingthisparticularkeyword!)Theletterva riablescontainthesameinformationasthevar iable. Strictlyspeaking, ,I vemadeatheextravariablestakeuproominthec omputer s memory, buttheprogramrunsfaster. Oneoftherecurringconcernsofa professionalprogrammeris ,theextraspacerequiredis reallyquitesmall,comparedtothememory ofa modern computer, sothedecisionis is Functions225setkeyword jtoilowercase :keywordmake"matrix reorder word:word(remove:word"abcdefghiklmnopqrs tuvwxyz)to Playfair :keyword :messagelocal[matrix a b c d e f g h i j k l m n o p q r s t u v w x y z]output encode(reduce "word:message)endto setkeyword :wordmake"j :iendEarlierI showedainstructiontoputa particularcodingmatrixintothevariable.

8 Howdoestheprogramcreatea matrixforanykeywordgivenasinput?Herearet wooftherelevantprocedures:Thekeywordthat isprovidedbytheuserasoneoftheinputstothe toplevelproceduregoesthroughseveralstage sasit is transformedintoa very similartoa plumbingdiagramfromChapter2 a littledifferenttoputsomewhatmoreemphasis ontheinputsandoutputs,soyoucanfollowthe flow ,here s (Icouldhavechosentousecapitallettersinst ead;thegoalis tohavesomeuniformconvention.)If thekeywordhappenstocontaina, ,tomakethematrix,wecombine(with) twowords:thekeywordandtheresultofremovin gthekeyword slettersfromthealphabet(leavingout). Finally, thatcombinedwordmustberearrangedintoa :PlayfairCipherlowercasewordJtoiRemovere orderreorderreorder1 ReorderJ Ito jtoi:wordoutput map [ifelseequalp ? "j ["i][?]]:wordendto remove:letters :stringif emptyp:string [output "]if memberp first:string :letters [output remove:letters bf :string]output wordfirst:string remove:letters bf :stringendto reorder :stringoutput reorder1 :string(mdarray [5 5])1 1endto reorder1 :string :array:row:columnif :row=6[output :array]if :column=6 [output reorder1 :string :array:row+1 1]mdsetitem(list:row:column):array first:stringmakefirst:string(list:row:co lumn)output reorder1(butfirst :string):array:row:column+1endTheadvanta geofa viewsuchas thisoneis thateachofthesmallboxesinthediagramhasa , trivial:is a somewhatmessier.

9 It mustkeeptrackofwhatrowandcolumnit supto,sois werefillingina matrixbyhand,insteadofwritinga computerprogram,I dusea very dhandleoneletterata dgothroughthekeyworda letterata time,stuffingeachletterintothenextavaila bleslotinthematrix.(Ifnecessary, I dconvertuppertolowercaseandtointheproces s.)ThenI dgothroughthealphabeta letterata time,saying Ifthisletterisn t inthekeyword,thenstuff it intothematrix. Manypeoplewouldfindit naturaltousethatsametechniqueinwritinga computerprogram,also:Compositionof Functions227foreachforeachnot memberpjtoilowercasejtoiforeachmake"matr ix mdarray [5 5]local[rowcolumn]make"row1make"column 1foreach :keyword [stuff jtoilowercase ?]foreach "abcdefghiklmnopqrstuvwxyz ~[if not memberp ? jtoi:keyword [stuff?]]to Playfair :keyword :message;; sequential versionlocal[matrix a b c d e f g h i j k l m n o p q r s t u v w x y z]make"j :ioutput encode(reduce "word:message)endto stuff:lettermdsetitem(list:row:column):m atrix :lettermake:letter(list:row:column)make" column :column+1if :column=6 [make"row:row+1make"column1]end[stuff jtoilowercase ?]

10 ]foreach "abcdefghiklmnopqrstuvwxyz ~[if(ifelse equalp? "i[not(or(memberp "i :keyword)(memberp "j :keyword))][notmemberp ? :keyword])[stuff?]]Inthisversion, computer, processingoneletterata ,forexample,inthetemplateit s worthnotingthattheoperationsandarebeinga ppliedtosingle-letterinputs,eventhoughth oseoperationsweredesignedtoacceptwordsof anylengthasa cheated,though, wastryingtomaketheprogrammorereadable; :PlayfairCipherto [keyword cleartext]print[Welcome to the Playfair enciphering program.]print[Whatkeyword wouldyouliketo use?]make"keyword firstreadlistprint[Nowpleaseenteryourmes sage, usingas manylinesas needed.]print[Whenyou redone,entera linecontaining onlya period(.).]make"cleartext [] [Hereis the enciphered version:]print[]printplayfair :keyword :cleartextendto "linemake"linereadlistif equalp:line[.] [stop]make"cleartext sentence :cleartext subjectingyoutothis?