Communication-Theory-of-Secrecy-Systems

CommunicationTheoryofSecrecySystems*ByC.E.SHANNON1.INTRODUCTIONANDSUMMARYTHEproblemsofcryptographyandsecrecysystemsfurnishaninterest­ingapplicationofcommunicationtheory.'Inthispaperatheoryofsecrecysystemsisdeveloped.Theapproachisonatheoreticallevelandisintendedtocomplementthetreatmentfoundinstandardworksoncryp­tography.There,adetailedstudyismadeofthemanystandardtypesofcodesandciphers,andofthewaysofbreakingthem.Wewillbemorecon­cernedwiththegeneralmathematicalstructureandpropertiesofsecrecysystems.Thetreatmentislimitedincertainways.First,therearethreegeneraltypesofsecrecysystem:(1)concealmentsystems,includingsuchmethodsasinvisibleink,concealingamessageinaninnocenttext,orinafakecover­ingcryptogram,orothermethodsinwhichtheexistenceofthemessageisconcealedfromtheenemy;(2)privacysystems,forexamplespeechinver­sion,inwhichspecialequipmentisrequiredtorecoverthemessage;(3)truesecrecysystemswherethemeaningofthemessageisconcealedbycipher,code,etc.,althoughitsexistenceisnothidden,andtheenemyisassumedtohaveanyspecialequipmentnecessarytointerceptandrecordthetransmittedsignal.Weconsideronlythethirdtype-concealmentsystemsareprimarilyapsychologicalproblem,andprivacysystemsatechnologicalone.Secondly,thetreatmentislimitedtothecaseofdiscreteinformation,wherethemessagetobeencipheredconsistsofasequenceofdiscretesym­bols,eachchosenfromafiniteset.Thesesymbolsmaybelettersinalan­guage,wordsofalanguage,amplitudelevelsofaquantizedspeechorvideosignal,etc.,butthemainemphasisandthinkinghasbeenconcernedwiththecaseofletters.Thepaperisdividedintothreeparts.Themainresultswillnowbebrieflysummarized.Thefirstpartdealswiththebasicmathematicalstructureofsecrecysystems.Asincommunicationtheoryalanguageisconsideredto,.ThematerialinthispaperappearedoriginallyinaconfidentialreportAMathe­maticalTheoryofCryptographydatedSept.1,1945.whichhasnowbeendeclassified.IShannon,C.E.,AMathematicalTheoryofCommunication,BellSystemTechnicalJournal,July1948,p,379;Oct.1948,p.623.2See,forexample,H.F.Gaines,ElementaryCryptanalysis,orM.Giviergc,CoursdeCryptographic.656CO.lIM['NICATIONTHEORYOFSECREel'SYSTEMS657berepresentedbyastochasticprocesswhichproducesadiscretesequenceofsymbolsinaccordancewithsomesystemofprobabilities.AssociatedwithalanguagethereisacertainparameterDwhichwecalltheredundancyofthelanguage.Dmeasures,inasense,howmuchatextinthelanguagecanbereducedinlengthwithoutlosinganyinformation.Asasimpleexample,sinceualwaysfollowsqinEnglishwords,theumaybeomittedwithoutloss.ConsiderablereductionsarepossibleinEnglishduetothestatisticalstruc­tureofthelanguage,thehighfrequenciesofcertainlettersorwords,etc.Redundancyisofcentralimportanceinthestudyofsecrecysystems.Asecrecysystemisdefinedabstractlyasasetoftransformationsofonespace(thesetofpossiblemessages)intoasecondspace(thesetofpossiblecryptograms).Eachparticulartransformationofthesetcorrespondstoencipheringwithaparticularkey.Thetransformationsaresupposedrever­sible(non-singular)sothatuniquedecipheringispossiblewhenthekeyisknown.Eachkeyandthereforeeachtransformationisassumedtohaveanaprioriprobabilityassociatedwithit-theprobabilityofchoosingthatkey.Similarlyeachpossiblemessageisassumedtohaveanassociatedaprioriprobability,determinedbytheunderlyingstochasticprocess.Theseprob­abilitiesforthevariouskeysandmessagesareactuallytheenemycrypt­analyst'saprioriprobabilitiesforthechoicesinquestion,andrepresenthisaprioriknowledgeofthesituation.Tousethesystemakeyisfirstselectedandsenttothereceivingpoint.Thechoiceofakeydeterminesaparticulartransformationinthesetformingthesystem.Thenamessageisselectedandtheparticulartrans­formationcorrespondingtotheselectedkeyappliedtothismessagetoproduceacryptogram.Thiscryptogramistransmittedtothereceivingpointbyachannelandmaybe'interceptedbytheenemy*.Atthereceivingendtheinverseoftheparticulartransformationisappliedtothecryptogramtorecovertheoriginalmessage.Iftheenemyinterceptsthecryptogramhecancalculatefromittheaposterioriprobabilitiesofthevariouspossiblemessagesandkeyswhichmighthaveproducedthiscryptogram.Thissetofaposterioriprobabilitiesconstituteshisknowledgeofthekeyandmessageaftertheinterception.Knowledgeisthusidentifiedwithasetofpropositionshavingassociatedprobabilities.Thecalculationoftheaposterioriprobabilitiesisthegen­eralizedproblemofcryptanalysis.Asanexampleofthesenotions,inasimplesubstitutioncipherwithran­domkeythereare261transformations,correspondingtothe26!wayswe*Thewordenemy,stemmingfrommilitaryapplications,iscommonlyusedincryp­tographicworktodenoteanyonewhomayinterceptacryptogram.658BELLSYSTEMTECHNlCALJOURNALcansubstitutefor26differentletters.Theseareallequallylikelyandeachthereforehasanaprioriprobabilityi/26!.IfthisisappliedtonormalEnglishthecryptanalystbeingassumedtohavenoknowledgeofthemessagesourceotherthanthatitisproducingEnglishtext,theaprioriprobabilitiesofvariousmessagesofNlettersaremerelytheirrelativefrequenciesinnormalEnglishtext.IftheenemyinterceptsNlettersofcryptograminthissystemhisprob­abilitieschange.IfNislargeenough(saySOletters)thereisusuallyasinglemessageofaposterioriprobabilityn