CNS - Unit - 4 - Public Key Cryptosystem

Public Key Cryptosystems with Applications, Requirements and
Cryptanalysis, RSA algorithm, its computational aspects and security, Diffie-Hillman Key Exchange algorithm, Man-in-Middle attack

1. UNIT -4
Public Key Cryptosystem
1
Cryptography and Network Security

2. Outline….
•Public Key Cryptosystems with Applications
•Requirements and Cryptanalysis
•RSA Algorithm
•RSA Algorithms Computational aspects and Security
•Diffie-Hillman Key Exchange Algorithm
•Man-in-Middle Attack

3. Public Key Cryptosystems
•Asymmetricencryptionisaformofcryptosysteminwhichencryption
anddecryptionareperformedusingthedifferentkeys—oneapublic
keyandoneaprivatekey.Itisalsoknownaspublic-keyencryption.
•Asymmetricencryptioncanbeusedforconfidentiality,
authentication,orboth.
•Public-keyalgorithmsarebasedonmathematicalfunctionsrather
thanonsubstitutionandpermutation.
•Public-keyencryptionismoresecurefromcryptanalysisthanis
symmetricencryption.

4. Terminology Related to Asymmetric Encryption
•AsymmetricKeys
➢Tworelatedkeys,apublickeyandaprivatekey,thatareusedto
performcomplementaryoperations,suchasencryptionand
decryptionorsignaturegenerationandsignatureverification.
•PublicKeyCertificate
➢Adigitaldocumentissuedanddigitallysignedbytheprivatekeyofa
CertificationAuthoritythatbindsthenameofasubscribertoapublic
key.Thecertificateindicatesthatthesubscriberidentifiedinthe
certificatehassolecontrolandaccesstothecorrespondingprivate
key.

5. Terminology Related to Asymmetric Encryption
•PublicKey(Asymmetric)CryptographicAlgorithm
➢Acryptographicalgorithmthatusestworelatedkeys,apublickey
andaprivatekey.Thetwokeyshavethepropertythatderivingthe
privatekeyfromthepublickeyiscomputationallyinfeasible.
•PublicKeyInfrastructure(PKI)
➢Asetofpolicies,processes,serverplatforms,softwareand
workstationsusedforthepurposeofadministeringcertificatesand
public-privatekeypairs,includingtheabilitytoissue,maintain,and
revokepublickeycertificates.

6. Public-Key Cryptosystems
•Asymmetricalgorithmsrelyononekeyforencryptionandadifferent
butrelatedkeyfordecryption.Thesealgorithmshavethefollowing
importantcharacteristic.
❖Itiscomputationallyinfeasibletodeterminethedecryptionkey
givenonlyknowledgeofthecryptographicalgorithmandthe
encryptionkey.
❖Eitherofthetworelatedkeyscanbeusedforencryption,withthe
otherusedfordecryption.

7. Encryption with Public Key

8. Encryption with Private Key

9. Public-Key Encryption scheme has six ingredients
•Plaintext:Thisisthereadablemessageordatathatisfedintothe
algorithmasinput.
•Encryptionalgorithm:Theencryptionalgorithmperformsvarious
transformationsontheplaintext.
•Publicandprivatekeys:Thisisapairofkeysthathavebeenselectedso
thatifoneisusedforencryption,theotherisusedfordecryption.The
exacttransformationsperformedbythealgorithmdependonthepublicor
privatekeythatisprovidedasinput.
•Ciphertext:Thisisthescrambledmessageproducedasoutput.Itdepends
ontheplaintextandthekey.Foragivenmessage,twodifferentkeyswill
producetwodifferentciphertext.
•Decryptionalgorithm:Thisalgorithmacceptstheciphertextandthe
matchingkeyandproducestheoriginalplaintext.

10. Essential steps for Public-Key Cryptography
1.Eachusergeneratesapairofkeystobeusedfortheencryptionand
decryptionofmessages.
2.Eachuserplacesoneofthetwokeysinapublicregisterorother
accessiblefile.Thisisthepublickey.Thecompanionkeyiskeptprivate.
AsFiguresuggests,eachusermaintainsacollectionofpublickeys
obtainedfromothers.
3.IfBobwishestosendaconfidentialmessagetoAlice,Bobencrypts
themessageusingAlice’spublickey.
4.WhenAlicereceivesthemessage,shedecryptsitusingherprivate
key.NootherrecipientcandecryptthemessagebecauseonlyAlice
knowsAlice’sprivatekey.

11. Public-Key Cryptosystem: Secrecy

12. Public-Key Cryptosystem: Authentication

13. Public-Key Cryptosystem: Authentication and Secrecy

14. Applications for Public-Key Cryptosystems
•Public-keysystemsarecharacterizedbytheuseofacryptographic
algorithmwithtwokeys,oneheldprivateandoneavailablepublicly.
•Dependingontheapplication,thesenderuseseitherthesender’sprivate
keyorthereceiver’spublickey,orboth,toperformsometypeof
cryptographicfunction.Inbroadterms,wecanclassifytheuseofpublic-
keycryptosystemsintothreecategories.
•Encryption/decryption:Thesenderencryptsamessagewiththe
recipient’spublickey.
•Digitalsignature:Thesender“signs”amessagewithitsprivatekey.Signing
isachievedbyacryptographicalgorithmappliedtothemessageortoa
smallblockofdatathatisafunctionofthemessage.
•Keyexchange:Twosidescooperatetoexchangeasessionkey.Several
differentapproachesarepossible,involvingtheprivatekey(s)ofoneor
bothparties.

15. Applications for Public-Key Cryptosystems
Algorithm Encryption/DecryptionDigital SignatureKey Exchange
RSA Yes Yes Yes
Elliptic Curve Yes Yes Yes
Diffie-Hellman No No Yes
Digital Signature
Standard
No Yes No

16. Requirements for Public-Key Cryptosystems
•Thedistinguishingtechniqueusedinpublic-keycryptographyisthe
useofasymmetrickeyalgorithms,whereakeyusedbyonepartyto
performencryptionisnotthesameasthekeyusedbyanotherin
decryption.Eachuserhasapairofcryptographickeys–apublic
encryptionkeyandaprivatedecryptionkey.

17. Cryptanalysis for Public-Key Cryptosystems
•Thekeysizemustbelargerenoughtomakebrute-forceattack
impracticalbutsmallenoughforpracticalencryptionanddecryption.

18. RSAalgorithm
•Oneofthefirstsuccessfulresponsestothechallengewasdeveloped
in1977byRonRivest,AdiShamir,andLenAdlemanatMITandfirst
publishedin1978.TheRivest-Shamir-Adleman(RSA)schemehas
sincethattimereignedsupremeasthemostwidelyacceptedand
implementedgeneral-purposeapproachtopublic-keyencryption.
•TheRSAschemeisablockcipher.

19. RSA algorithmsteps
•EncryptionequationforRAS[C=P.T.^e%n]
•DecryptionequationforRAS[P.T.=C^d%n]
1.SelectTWOprimenumber(p)and(q).
2.Computen=p*q.
3.Computeφ(n)=(p-1)*(q-1).
4.Chooseesuchthat1<e<φ(n)andeandnarecoprime.
5.Computeavaluefordsuchthat(d*e)%φ(n)=1.
6.Publickeyis(e,n).
7.Privatekeyis(d,n).

20. RSA Algorithm Example
•Choose p = 3 and q = 11
•Compute n = p * q = 3 * 11 = 33
•Compute φ(n) = (p -1) * (q -1) = 2 * 10 = 20
•Choose e such that 1 < e < φ(n) and e and n are coprime. Let e = 7
•Compute a value for d such that (d * e) % φ(n) = 1. One solution is d =
3 [(3 * 7) % 20 = 1]
•Public key is (e, n) => (7, 33)
•Private key is (d, n) => (3, 33)
•The encryption of m = 2is c = 2
7
% 33 = 29
•The decryption of c = 29is m = 29
3
% 33 = 2

21. Diffie-Hellmanalgorithm
•IntroductionWhitefieldDiffieandMartinHellmandevisedan
amazingsolutiontotheproblemofkeyagreementorkeyexchangein
1976.ThissolutioniscalledastheDiffie-Hellmankey
Exchange/AgreementAlgorithm.
•Thebeautyofthisthetwoparties,whowanttocommunicate
securely,canagreeonasymmetrickeyusingthistechnique.
•Thiskeycanthenbeusedforencryption/decryption.
•Diffie-Hellmankeyexchangealgorithmcanbeusedonlyforkey
agreementnotforencryption/decryption.

22. Diffie-Hellman algorithm steps
1.AliceandBobagreeontwolargeprimenumbers,nandg.Thesetwo
integersnumbernotbekeptsecret.Theycanuseinsecurechannelto
agreeonthem.
2.Alicechoosesanotherlargerandomnumberx,andcalculatesAsuch
that:A=g^xmodn
3.AlicesendsthenumberAtoBob.
4.Bobindependentlychoosesanotherlargerandomintegerandcalculate
Bsuchthat:B=g^ymodn
5.BobsendsthenumberBtoAlice.
6.AnowcomputesthesecretkeyK1asfollows:K1=B^xmodn
7.BnowcomputesthesecretkeyK2asfollows:K2=A^ymodn

23. Diffie-Hellman Key Exchange Algorithm Example
1.Let n=11 , g=7.
2.Let x=3. Then we have, A=7^3 mod 11 = 343 mod 11 = 2.
3.Alice send 2 to Bob.
4.Let y=6. Then we have, B=7^6 mod 11 = 117649 mod 11 = 4.
5.Bob send 4 to Alice.
6.We have, K1 = 4^3 mod 11 = 64 mod 11 = 9.
7.We have, K2 = 2^6 mod 11 = 64 mod 11 = 9.

24. Problem with Diffie-Hellman algorithm
•CanwenowconsiderthattheDiffie-Hellmankeyexchangealgorithm
solveallourproblemsassociatedwithkeyexchange?Unfortunately,
notquite!
•Diffie-Hellmankeyexchangealgorithmcanfallpraytotheman-in-
the-middleattackalsocalledasbucketbrigadeattack.

25. Diffie-Hellman Key Exchange Algorithm Example
1.Let n=11 , g=7.
2.Let x=3. Then we have, A=7^3 mod 11 = 343 mod 11 = 2.
3.Alice send 2 to Bob.
4.Let y=6. Then we have, B=7^6 mod 11 = 117649 mod 11 = 4.
5.Bob send 4 to Alice.
6.We have, K1 = 4^3 mod 11 = 64 mod 11 = 9.
7.We have, K2 = 2^6 mod 11 = 64 mod 11 = 9.

26. Man-in-the-middle attack
1.Alice want to communicate with Bob securely and therefore, she
first want to do a Diffie-Hellman key exchange with him. For this
purpose, she send the values of nand gto Bob, as usual. Len n=11
and g=7.
2.Alice does not realize that the attacker Tom is listening quietly to
the conversation between hear and Bob. Tom simply picks up the
values of n and g and also forward them to Bob as they originally
were.
Alice Tom Bob
n=11,g=7 n=11,g=7 n=11,g=7

27. Man-in-the-middle attack
3.Now, let us assume that Alice, Tom and Bob select random number x and y.
4.Now based on these values, all the three persons calculated the values of A
and B
Alice Tom Bob
x=3 x=8,y=6 y=9
Alice Tom Bob
A = g^xmod n
= 7^3 mod 11
= 343 mod 11
= 2
A = g^xmod n
= 7^8 mod 11
= 5764801 mod 11
= 9
B = g^ymod n
= 7^6 mod 11
= 117649 mod 11
= 4
B = g^ymod n
= 7^9 mod 11
= 40353607 mod 11
= 8

28. Man-in-the-middle attack
5.(a)AlicesendsherA(2)toBob.Tominterceptsitandinstead,send
hisA(9)toBob.
(b)Inreturn,BobsendhisB(8)toAlice.Asbefore,Tomintercepts
itand,sendshisB(4)toAlice.AlicethinkthatthisBcameto
fromBob.
(c)Thereforeatthistime,Alice,TomandBobhavethevaluesofA
andB.
Alice Tom Bob
A=2,B=4 A=2,B=8 A=9,B=8

29. Man-in-the-middle attack
6.Baseonthesevalues,allthethreepersonsnowcalculatetheirkeys.Wewill
noticethatAlicecalculatedonlyK1.BobcalculatedK2,whereasTom
calculatedbothK1andK2.
Alice Tom Bob
K1 = B^xmod n
= 4^3 mod 11
= 64 mod 11
= 9
K1 = B^xmod n
= 8^8 mod 11
= 16777216 mod 11
= 5
K2 = A^ymod n
= 2^6 mod 11
= 64 mod 11
= 9
K2 = A^ymod n
= 9^9 mod 11
= 387420489 mod 11
= 5