Example: barber

ElGamal:Public-Key Cryptosystem

ElGamal:Public-KeyCryptosystemJaspreetKa urGrewalApap erpresentedforthedegreeofMasterofScience MathandComputerScienceDepartmentIndianaS tateUniversityTerreHaute,IN,USA9/30/2015 CryptographyElGamalContents1 Intro etweentwoparties,p o ,whichusesapairofcryptographickeys, ,whilepublickeycanb edistributedop enly, ,itmo di estheDi e-Hellmanproto colwiththegoalsothatitcanb othsystemsdep endsonthetroubleof guringdiscretelogarithmsover nite dulusandKnown-PlaintextattackonElGamal, ,itssecurityisusuallyb :Public-KeyCryptosystemJaspreetkaurgrewa l29 Septemb er20151 Intro ductionCryptographyisasciencewithhistory thatisasoldasthehuman' endablyaneedtocoverupessentialdata, , , ossibletomakeasafecipherandsendittothere cipientwithoutonetoonemeeting, ,therestillwasnorealwaytosecurelysendthe key-intheeventthatitgottoth

Key exchange is any technique in cryptography by which crypto-graphic keys are exchanged between two parties, permitting utilization of keys in a cryptographic algorithm. The key exchange issue is the manner by which to exchange whatever keys or other data are needed so that nobody else can obtain a cop.y The public key cryptograph,y

Tags:

  Crypto

Information

Domain:

Source:

Link to this page:

Please notify us if you found a problem with this document:

Other abuse

Transcription of ElGamal:Public-Key Cryptosystem

1 ElGamal:Public-KeyCryptosystemJaspreetKa urGrewalApap erpresentedforthedegreeofMasterofScience MathandComputerScienceDepartmentIndianaS tateUniversityTerreHaute,IN,USA9/30/2015 CryptographyElGamalContents1 Intro etweentwoparties,p o ,whichusesapairofcryptographickeys, ,whilepublickeycanb edistributedop enly, ,itmo di estheDi e-Hellmanproto colwiththegoalsothatitcanb othsystemsdep endsonthetroubleof guringdiscretelogarithmsover nite dulusandKnown-PlaintextattackonElGamal, ,itssecurityisusuallyb :Public-KeyCryptosystemJaspreetkaurgrewa l29 Septemb er20151 Intro ductionCryptographyisasciencewithhistory thatisasoldasthehuman' endablyaneedtocoverupessentialdata, , , ossibletomakeasafecipherandsendittothere cipientwithoutonetoonemeeting, ,therestillwasnorealwaytosecurelysendthe key-intheeventthatitgottotheeavesdropp ershands, eldDi eandMartinHellmandistributedapap erwheretheyprop osedthethoughtofpublickeycryptographyinw hichtwodiverseyetscienti ointthat guringofonekey(the'privatekey')iscomputa tionallyinfeasiblefromtheother(the'publi ckey')

2 , ,b othkeysarepro ducedsecretly, eandHellmandistributedthe rstpublic-keyalgorithmknownasa"Di e-Hellmankeyexchange"thatyear, 'spublickeyandreceiverdeco ortedpublickeycryptosystemutilizesdistin ctivekeysasapartofencryptionanddecryptio n,whichisacryptosystemtakingintoaccountt heinfeasibilityincountof ndingdeco ,afterDi e-Hellman,oneofthethemostwell- ,lateformsofPGP,anddi ,theDigitalSignatureAlgorithm(DSA)varian t,inviewoftheElGamalalgorithm(calledtheE lGamalsignaturescheme),isusedtosigndigit aldo jorpro cesses:thekeygeneration,theencryption, outthatasasendercalledAliceneedstosendap rivatemessagetotherecipientBob, cedureworksasfollows:Inthe rststep,Bob(Receiver)hastocomputeapublic keyandsendittotheAlice(Sender).

3 AfterreceivingtheBob'spublickeyshedotheE ncryption, cess,Eve(thirdp erson)couldnotb eabletoknowthesecretkeyb ,ElGamalPKCisoneofmanyalgorithmsthatutil izesrandomizationintheencryptionpro ,Whit eldDi osedacryp-tosysteminwhichtheencryptionke yandthedeco dingkeyweredi ,knownaspublickeycryptography,uti-lizesa pairofcryptographickeys, ,whilethegeneralpublickeycanb edisp ersedop enly, ,p ermittingthesenderofamessagetoencrypthis messageutilizingthereceiver' ede-co dedutilizingtherecipients' e-HellmanKeyexchangealgorithmgivesatechn iqueforop enlysharinganarbitrarysecretkey.

4 Itdo esnotaccomplishthefullob jectiveofb eingapublickeycryptosys-tem,sinceacrypto systemgrantsexchangeofparticulardata, ,aftertheDi e-HellmankeyexchangeandPKC,TaherElGamali n1985describ edtheElGamalcryptosystemalgorithminatyp eofpublickeycryptosystemwhichisusedover nite eldsanditssecurityisbasedontheDiscreteLo garithmProblem(DLP).TheElGamalCryptosys- temisaverysuccessfulimplementationofDi e-HellmanalgorithmBecauseElGamalalgorith mcanb nition:CryptosystemWecharacterizethecryp tosystemasthe5-tuple(M,C,K,E,D)whereM ? esplitinnumerousblo ?istheresultofanencryptionfunctionEk(P) :C,whichtakestheplaintextandanextrakeyK, ,whogetsC,utilizesitwithadecryptionfunct ionDK(C) :P, eentransferred, , "keypair"iscustomized,wewillmeanthepriva tekeywithap ersonsorsubstancesintro ewrittenasitis gured,leavingthemo dulusop , "keypair".

5 Ducedacryptosystemwhichdep endsontheonewayfunction, endsontheassumptionthattheDLcan'tb efoundinfeasibletime,whilethereverseop erationofthep owercanb ecomputede rstpublickeysystemprop osedbyDi eandHellmanrequiresasso cia-tionofb osesissuesifthecryptosystemshouldb eappliedtocommunicationsystemwhereb othsidesarenotabletointeractinreasonable timeb osedschemebyDi eandHellmanisnotageneralpurp oseencryptionalgorithmthatsatis ,afterDi e-Hellman, ,TheElGamalsolvedtheDi e-Hellmankeyexchangealgorithmbypresentin garandomexp onenttyp onentisareplacementfortheprivatetyp cationthealgorithmcanb eutilizedtoenco deinoneheading,withouttheneedofthesecond partytotakee eutilizedforencryp-tionofelectronicmessa ges,whicharetransmittedbythemetho , ove,wewillnowfollowBobthroughhispro ,Bobneedstoselectalargeprimepandthegener atorgofamultiplicativegroup(Zp) oftheintegersmo b p ,wecancalculatethepublickeypartgbmod ,thepublickeyofBobisthetriplet(p,g,gb)

6 ,Alice rstneedstoobtainhispublickeytriplet(p,g, gb) ,asthePage6 CryptographyElGamalonlysecretpart,b, , , edab ove,Alicehastoacquirethepublickeypart(p, g,gb)ofBobfromano dingWriteMassetofintegers(m1,m2, )intherangeof1, ,p eenco onentInthisstep,Alicewillselectarandomex p onentkthattakestheplaceofthesecondparty' sprivateexp onentintheDi onentktoBob,Alicecomputesgkmod pandcombinesitwiththeciphertextthatshall b , ,sheiteratesoverthesetcreatedinstep2andc alculatesforeachofthemi:ci=m1?(gb)kTheci phertextCisthesetofallciwith0< i |M|.TheresultingencryptedmessageCissentt oBobtogetherwiththepublickeygkmod pderivedfromtherandomprivateexp ,andinasecondstepwouldalsoacquirethepubl ickeypartgbofb obfromakeyserver,hewouldstillnotb eabletoderivegb?

7 Kascanb ,asknowledgeofonemessageblo ckmjdo (gb)kmodpandc2=m2?(gb)kmodp,fromPage7 CryptographyElGamalknowingonlym1thenextp artofthemessagem2canb ecalculatedbythefollowingformula:m1m2= ,Bobhastousetheencryptionalgorithmtob edAlicetode neasharedsecretkeywithoutBob' onentbandtherandomexp nedbythefollowingequation:(gk)p 1 b= (gk) b=b (gk) b? cimod osespA= 107, A= 2,dA= 67,andshecomputes A=267 94(mod107).Herpublickeyis(pA, A, A)=(2,67,94),andherprivatekeyisdA= "B"(66inASCI I) osesarandomintegerk=45andencryptsM= 66as(r,t) = ( kA, kAM) (245,944566) (28,9)(mod107).

8 Hesendstheencryptedmessage(28,9) (r,t) = (28,9),andusingherprivatekeydA=67shedecr yptstotr dA= 67 67 66(mod107).Page8 CryptographyElGamal5 SecurityThesecurityoftheElGamalschemedep endsontheprop ertiesoftheunder-lyinggroupGaswellasanyp addingschemeusedonthemessages. IfthecomputationalDi e-Hellmanassumption(CDH)holdsintheunderl yingcyclicgroupG,thentheencryptionfuncti onisone-way. IfthedecisionalDi e-Hellmanassumption(DDH)holdsinG, , ,givenanencryption(c1,c2)ofsome(p ossiblyunknown)messagem,onecaneasilycons tructavalidencryption(c1,2c2) ,theschememustb efurthermo d-i ed,oranappropriatepaddingschememustb endingonthemo di cation,theDDHassumptionmayormaynotb eenprop ofdo esnotusetherandomoraclemo osedschemeisDHAES,whosepro erentciphertexts, ,recentversionsofPGP, ,anditsslowersp eed(esp eciallyforsigning).

9 OtentialdisadvantageoftheElGamalsystemis thatmessageex-pansionbyafactoroftwotakes placeduringencryption(meanstheciphertext istwiceaslongastheplaintext.)7 ApplicationsTheElGamalcryptosystemdo esnotonlysupp ortencryptionanddecryption, eableto (M,S) cationBobhastob esnotdeliverinformationab cationisthatthemessagehasnotb eenalteredonthetransmissionpathb ep (r,s)with0 r,s < p 1de nedbytheequationgM (ga)r(r8)modpThepro cedureofsigningfollowssimilarstepsasthee ncryptionpro ce- oserandomk oveasgM gargksmodpandsolveitforsusingm ar+ksmod(p 1).

10 ThishasasolutionforsifkisPage10 CryptographyElGamalchosensuchthatgcd(k,p 1) = (M,r,s) ,heonlyneedstocomputeb er,wehavedescrib ,whichwasdevelop ,re-centversionsofPGP, , : Descriptionofcryptographyandpublic-keycr yptosystem. AnalysisofELGamalPublic-keyCryptosystem. ImplementationofElGamalkeyGeneraation,en cryptionandDecryp-tionAlgorithms. Inthelast,descriptionab [1]Wikip [2] (2005,June08) [3] ~leon/mcs425- s08/handouts/el.


Related search queries