Hill Code - adomain

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.

Hill Code

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.