ch-13 Digital Signature FOR CNS STUDENTS

SIGNATURE

1. 13.1
Copyright © The McGraw-Hill Companies, Inc. Permission required for reproduction or display.
Chapter 13
Digital Signature

2. 13.2
Objectives
Todefineadigitalsignature
Todefinesecurityservicesprovidedbyadigital
signature
Todefineattacksondigitalsignatures
Todiscusssomedigitalsignatureschemes,including
RSA,ElGamal,
Schnorr,DSS,andellipticcurve
Todescribesomeapplicationsofdigitalsignatures
Chapter 13

3. 13.3
13-1 COMPARISON
Letusbeginbylookingatthedifferencesbetween
conventionalsignaturesanddigitalsignatures.
13.1.1Inclusion
13.1.2Verification Method 390
13.1.3Relationship
13.1.4Duplicity
Topics discussed in this section:

4. 13.4
Aconventionalsignatureisincludedinthedocument;it
ispartofthedocument.Butwhenwesignadocument
digitally,wesendthesignatureasaseparatedocument.
13.1.1 Inclusion

5. 13.5
Foraconventionalsignature,whentherecipientreceives
adocument,shecomparesthesignatureonthedocument
withthesignatureonfile.Foradigitalsignature,the
recipientreceivesthemessageandthesignature.The
recipientneedstoapplyaverificationtechniquetothe
combinationofthemessageandthesignaturetoverify
theauthenticity.
13.1.2 Verification Method

6. 13.6
Foraconventionalsignature,thereisnormallyaone-to-
manyrelationshipbetweenasignatureanddocuments.
Foradigitalsignature,thereisaone-to-onerelationship
betweenasignatureandamessage.
13.1.3 Relationship

7. 13.7
Inconventionalsignature,acopyofthesigneddocument
canbedistinguishedfromtheoriginaloneonfile.In
digitalsignature,thereisnosuchdistinctionunlessthere
isafactoroftimeonthedocument.
13.1.4 Duplicity

8. 13.8
13-2 PROCESS
Figure13.1showsthedigitalsignatureprocess.The
senderusesasigningalgorithmtosignthemessage.
Themessageandthesignaturearesenttothereceiver.
Thereceiverreceivesthemessageandthesignature
andappliestheverifyingalgorithmtothe
combination.Iftheresultistrue,themessageis
accepted;otherwise,itisrejected.
13.2.1Need for Keys
13.2.2Signing the Digest
Topics discussed in this section:

9. 13.9
13-2 Continued
Figure 13.1 Digital signature process

10. 13.10
13.2.1 Need for Keys
Figure 13.2 Adding key to the digital signature process
A digital signature needs a public-key system.
The signer signs with her private key; the verifier
verifies with the signer’s public key.
Note

11. 13.11
13.2.1 Continued
A cryptosystem uses the private and public keys of
the receiver: a digital signature uses
the private and public keys of the sender.
Note

12. 13.12
13.2.2 Signing the Digest
Figure 13.3 Signing the digest

13. 13.13
13-3 SERVICES
We discussed several security services in Chapter 1
including message confidentiality, message
authentication, message integrity, and nonrepudiation.
A digital signature can directly provide the last three;
for message confidentiality we still need
encryption/decryption.
13.3.1Message Authentication
13.3.2Message Integrity
13.3.3Nonrepudiation
13.3.4Confidentiality
Topics discussed in this section:

14. 13.14
Asecuredigitalsignaturescheme,likeasecure
conventionalsignaturecanprovidemessage
authentication.
13.3.1 Message Authentication
A digital signature provides message authentication.
Note

15. 13.15
Theintegrityofthemessageispreservedevenifwesign
thewholemessagebecausewecannotgetthesame
signatureifthemessageischanged.
13.3.2 Message Integrity
A digital signature provides message integrity.
Note

16. 13.16
13.3.3 Nonrepudiation
Figure 13.4 Using a trusted center for nonrepudiation
Nonrepudiation can be provided using a trusted
party.
Note

17. 13.17
13.3.4 Confidentiality
A digital signature does not provide privacy.
If there is a need for privacy, another layer of
encryption/decryption must be applied.
Figure 13.5 Adding confidentiality to a digital signature scheme
Note

18. 13.18
13-4 ATTACKS ON DIGITAL SIGNATURE
Thissectiondescribessomeattacksondigital
signaturesanddefinesthetypesofforgery.
13.4.1Attack Types
13.4.2Forgery Types
Topics discussed in this section:

19. 13.19
13.4.1 Attack Types
Key-OnlyAttack
Known-MessageAttack
Chosen-MessageAttack
the attacker first learns signatures on arbitrary messages of the attacker's
choice.
the attacker is given valid signatures for a variety of messages known by
the attacker but not chosen by the attacker.
the attacker is only given the public verification key.

20. 13.20
13.4.2 Forgery Types
ExistentialForgery
SelectiveForgery
Existential forgery is the creation (by an adversary) of
any message/signature pair (m,σ), where σ was not
produced by the legitimate signer.
Selective forgery is the creation (by an adversary) of
a message/signature pair (m,σ) where mhas been
chosenby the adversary prior to the attack.

21. 13.21
13-5 DIGITAL SIGNATURE SCHEMES
Severaldigitalsignatureschemeshaveevolvedduring
thelastfewdecades.Someofthemhavebeen
implemented.
13.5.1RSA Digital Signature Scheme
13.5.2ElGamal Digital Signature Scheme
13.5.3Schnorr Digital Signature Scheme
13.5.4Digital Signature Standard (DSS)
13.5.5Elliptic Curve Digital Signature Scheme
Topics discussed in this section:

22. 13.22
KeyGeneration
KeygenerationintheRSAdigitalsignatureschemeis
exactlythesameaskeygenerationintheRSA
13.5.1 Continued
In the RSA digital signature scheme, dis private;
eand nare public.
Note

23. 13.23
SigningandVerifying
13.5.1 Continued
Figure 13.7 RSA digital signature scheme

24. 13.24
13.5.1Continued
Asatrivialexample,supposethatAlicechoosesp=823andq=
953,andcalculatesn=784319.Thevalueoff(n)is782544.Now
shechoosese=313andcalculatesd=160009.Atthispointkey
generationiscomplete.NowimaginethatAlicewantstosenda
messagewiththevalueofM=19070toBob.Sheusesherprivate
exponent,160009,tosignthemessage:
Example 13.1
AlicesendsthemessageandthesignaturetoBob.Bobreceivesthe
messageandthesignature.Hecalculates
BobacceptsthemessagebecausehehasverifiedAlice’ssignature.

25. 13.25
RSASignatureontheMessageDigest
13.5.1 Continued
Figure 13.8 The RSA signature on the message digest

26. 13.26
13.5.1 Continued
When the digest is signed instead of the message
itself, the susceptibility of the RSA digital signature
scheme depends on the strength of the hash
algorithm.
Note

27. 13.27
13.5.2 ElGamal Digital Signature Scheme
Figure 13.9 General idea behind the ElGamal digital signature scheme

28. 13.28
KeyGeneration
Thekeygenerationprocedurehereisexactlythesameas
theoneusedinthecryptosystem.
13.5.2 Continued
In ElGamal digital signature scheme, (e
1, e
2, p) is
Alice’s public key; dis her private key.
Note

29. 13.29
VerifyingandSigning
13.5.2 Continued
Figure 13.10 ElGamal digital signature scheme

30. 13.30
13.5.3 Schnorr Digital Signature Scheme
Figure 13.11 General idea behind the Schnorr digital signature scheme

31. 13.31
13.5.4 Digital Signature Standard (DSS)
Figure 13.13 General idea behind DSS scheme

32. 13.32
DSSVersusRSA
ComputationofDSSsignaturesisfasterthan
computationofRSAsignatureswhenusingthesamep.
DSSVersusElGamal
DSSsignaturesaresmallerthanElGamalsignatures
becauseqissmallerthanp.
13.5.4 Continued

33. 13.33
13.5.5 Elliptic Curve Digital Signature Scheme
Figure 13.15 General idea behind the ECDSS scheme

34. 13.34
13-6 VARIATIONS AND APPLICATIONS
Thissectionbrieflydiscussesvariationsand
applicationsfordigitalsignatures.
13.6.1Variations
13.6.2Applications
Topics discussed in this section:

35. 13.35
13.6.1 Variations
TimeStampedSignatures
Sometimesasigneddocumentneedstobetimestampedto
preventitfrombeingreplayedbyanadversary.Thisis
calledtime-stampeddigitalsignaturescheme.
BlindSignatures
Sometimeswehaveadocumentthatwewanttoget
signedwithoutrevealingthecontentsofthedocumentto
thesigner.