Introduction
Hillpasswordisanalternativepasswordusingtheprinciplesofbasicmatrixtheory,inventedbyLesterS.Hillin1929.
Eachletteristreatedasa26-basenumber:A=0,B=1,C=2...Astringoflettersistreatedasann-dimensionalvector,multipliedbyann×nmatrix,andthenTheresultwillbemodulo26.
Notethatthematrix(key)usedforencryptionmustbereversiblein,otherwiseitwillbeimpossibletodecode.Onlythematrix'sdeterminantand26aremutuallyprime,aretheyinvertible.
Reasons
Withtherapiddevelopmentoftechnologyandtheincreasingdependenceofpeopleoncreditcardsandcomputers,cryptographyhasbecomemoreandmoreimportant.Cryptographyisadisciplineaboutencryptionanddecryption,ciphertextandplaintext.Iftheoriginalsymbolisreplacedbyanothersymbol,itcanbecalledageneralizedcipher.Thenarrowpasswordismainlyforkeepingsecret.Itisanothertypeofsymboltextdesignedtopreventthethieffromknowingthecontent,anditisalsoapasswordwellknowntoordinarypeople.
Passwordsarerequiredtousecreditcards,networkaccountsandpasswords,e-mails,andelectronicsignatures.Inordertofacilitatememory,manypeopleusebirthdays,phonenumbers,andhousenumbersaspasswords,butthisislesssecure.
Inordertomakethepasswordmorecomplexandmoredifficulttodecrypt,manydifferentformsofpasswordhavebeenproduced.Thefunctionalcharacteristicofthepasswordistheone-to-oneorone-to-manyrelationshipbetweentheplaintextandthepassword,thatis,theplaintextisafunctionofthepassword.Oneofthetraditionalciphersiscalledtheshiftmethod.ThebasicformoftheshiftmethodistheadditiveencryptionsystemC=P+s(modm).Generallyspeaking,weuse1forA,2forB,...,25forY,26forZ,andsoon.Sinces=0isequivalenttounencrypted,and0≤s≤m-1(s≥mcanbereplacedby0≤s≤m-1),therefore,theentiresystemhasonlym-1changes.Inotherwords,ifyoutrym-1times,confidentialinformationwillleakout.
Fromthispointofview,thereliabilityofpasswordsindailylifeandtraditionalpasswordsispoor.Weneedtofindawaytoeasilyconcealorhomogenizethenaturalfrequencyofletters,whichisconducivetostatisticalanalysis.Thesafeandreliableencryptionmethod.HillCiphercanbasicallymeetthisrequirement.
Principle
ThebasicideaoftheHillencryptionalgorithmistoconvertdplaintextlettersintodciphertextlettersthroughlineartransformation.Decryptionrequiresonlyoneinversetransformation,andthekeyisthetransformationmatrixitself.
TheHillpasswordisatypeofmulti-lettersubstitutionpassword.Multi-lettersubstitutioncipherscanbeconvenientlydescribedbymatrixtransformation,sometimescalledmatrixtransformationciphers.LettheplaintextalphabetbeZ,andifLlettersareusedastheunitforsubstitution,themulti-codesubstitutionisthemappingf:Z→Z.Ifthemappingislinear,thenfisalineartransformation,whichcanberepresentedbyanL×LmatrixKonZ.Ifitisfullrank,thetransformationisaone-to-onemapping,andthereisaninversetransformationK.DenotethenumberofLlettersastheL-dimensionalvectormonZ,thecorrespondingciphertextvectorc,andmK=c,usingKasthedecryptionmatrix,thecorrespondingplaintextc·K=mcanberecoveredfromc.
Inmilitarycommunications,characters(information)areoftencorrespondedtonumbers(forconvenience,wecorrespondtocharactersandnumbersintheoriginalorder,infact,thiscorrespondenceruleisextremelyeasytocrack):
abcde…xyz
12345…242526
Forexample,themessage"NOSLEEPPING"correspondstoasetofcodes14,15,19,12,5,5,16,16,9,14,7.Butifitisdirectlytransmittedinthisway,itcanbeeasilydecipheredbytheenemy.Therefore,encryptionmeasuresmustbetaken,thatis,theoriginalsignalBismultipliedbyanagreedencryptionmatrixK,thetransmissionsignalisC=KB(encryption),andthepartyreceivingthesignalrestores(deciphers)thesignaltoB=KC.Iftheenemydoesnotknowtheencryptionmatrix,itisdifficulttodecipher.
Encryption
Thefirststep,settheencryptionmatrixtoK=112-120113,thatis,setq=26,L=intheHillpassword3.Selectthefullrank3×3orderinvertiblematrix.Thereasonwhywetakethe3×3reversiblesquarematrixisalsofortheconvenienceofcalculation,andthecorrespondingsecurityislower.
Thesecondstep,dividetheinformation14,15,19,12,5,5,16,16,9,14,7into4columnmatrices:X1=141519,X2=1255,X3=16169,X4=1470,wherethe"0"inXisimaginary,anditspurposeistobeconsistentwiththenumberofrowsinthecolumnmatrix.Thenumberofrows3andthenumber4ofthecolumnmatrixcompletelydependonthenumberofnumberscorrespondingtotheencryptedinformationandtheorderoftheencryptionmatrix.
Thethirdstep,encrypttheinformation.Performmatrixmultiplication:Y1=KX1=112-120213141519=6716100;Y2=KX2=112-1202131255=27-244;Y3=KX3=112-12021316169=501675;Y4=KX4=112-1202131470=21035.Thenewencryptedcodeis67,16,100,27,-2,44,50,16,75,21,0.Althoughthe35inYisredundantinformation,itshouldbesenttotheotherpartytogetherwiththepassword,andtheotherpartymustparticipateinthecalculationwhencrackingthepassword.
Decryption
Thefirststep,findtheinversematrixofthekeymatrixK.KcanbecalculatedwithMathematica.Thatis,K=-614-3125-1-3.
Thesecondstep,performmatrixmultiplicationagain:X1=-614-3125-1-3671610=141519;X2=-614-3125-1-327-244=1255;X3=-614-3125-1-3501675=16169;X4=-614-3125-1-321035=1470.Inthisway,theoriginalinformationiscodedas14,15,19,12,5,5,16,16,9,14,7.
Thethirdstep,comparethecodingtable,youcangettheinformationcontentsentbytheotherpartyas"NOSLEEPPING".
Securityanalysis
ItisnotdifficulttoseethattherearetwoveryimportantconditionsintheHillcipheralgorithm.Thefirstconditionisthecorrespondencetableofcharacters(information)andnumbers.Whentheorderoftheencryptionmatrixn(theorderoftheencryptionmatrixinthisexampleisn=3)islarger,thedifficultyofdecipheringwillincrease.Atthistime,theamountofcalculationItisalsobig,wecanuserelatedmathematicssoftwaresuchasMathematicatoimprovecomputingefficiency.Thesecondconditionistheencryptionmatrix.Howtodefineandsolvethismatrixiscrucialtotheencryptionanddecryptionofpasswords.
Fromtheperspectiveofdecipheringpasswords,traditionalpasswordshaveafatalweakness,thatis,deciphererscanfindthelawfromthestatisticalcharacterfrequency,andthenfindoutthebreakthroughpoint,especiallyattheheightofcomputertechnology.Today,whenitisdeveloped,thespeedofdecipheringisfaster.TheHillcipheralgorithmcompletelyovercomesthisdefect.Byusingmatrixmultiplicationandinverseoperationsinlinearalgebra,itcanbetterresistfrequencyanalysisandisdifficulttobreak.
TheHillcryptosystemsetsatleastthreebarriersfordecipherers,whichincreasesthedifficultyofdeciphering.ThekeytodecipheringtheHillcipheristoguesshowthetextisconvertedintoafew-dimensionalvector(thenumberofrowsinthecolumnmatrix),howthecorrespondingalphabetisarranged,andmoreimportantly,totrytoobtaintheencryptionmatrixA.Tocrackthepassword,thedimensionsofthevector,thealphabeticallistandtheencryptionmatrixareindispensable.Inespionagewarsinancientandmoderntimes,bothsidesalwaystrytheirbesttoobtainthekeytocracktheotherparty'spassword,butitisnoteasytogetthethreekeysofHill'spassword.
Thereisnounbreakablepasswordintheworld,andtheHillpasswordisnoexception.ThedisadvantageoftheHillcipheralgorithmisthatthesecurityoflineartransformationisveryfragileandeasytobebrokenbyattacks.Hackersusetheweaknessesofvariouscipherstofrequentlylaunchattacksonusers.Nevertheless,theHillpasswordisstillasimpleandefficientpassword.
Example
ConsiderthemessageACT,becauseA=0,C=2,T=19,themessageis:
SetThekeyis
Confirmthatitisreversible:
Encryptionprocess:
Thecorrespondingciphertextis"POH".
Assumingthattheotherpartyknowstheciphertextandthekey,firstfindouttheinversematrixofthekey:
Multiplytheinversematrixandtheciphertext:
p>
youget"ACT".