Digital Signature Algorithm (DSA)
Digital Signatures
➢ digital signatures provide the ability to:
⚫ verify author, date & time of signature
⚫ authenticate message contents
⚫ be verified by third parties to resolve disputes
➢ hence include authentication function with
additional capabilities
Digital Signature Model
Digital
Signature
Model
Attacks and Forgeries
➢ attacks
⚫ key-only attack
⚫ known message attack
⚫ generic chosen message attack
⚫ directed chosen message attack
⚫ adaptive chosen message attack
➢ break success levels
⚫ total break
⚫ selective forgery
⚫ existential forgery
Digital Signature Requirements
➢ must depend on the message signed
➢ must use information unique to sender
⚫ to prevent both forgery and denial
➢ must be relatively easy to produce
➢ must be relatively easy to recognize & verify
➢ be computationally infeasible to forge
⚫ with new message for existing digital signature
⚫ with fraudulent digital signature for given message
➢ be practical save digital signature in storage
Direct Digital Signatures
➢ involve only sender & receiver
➢ assumed receiver has sender’s public-key
➢ digital signature made by sender signing
entire message or hash with private-key
➢ For Confidentiality →it can encrypt using
receivers public-key
➢ important that sign first then encrypt
message & signature
➢ security depends on sender’s private-key
Digital Signature Standard (DSS)
• US Govt approved signature scheme
• designed by NIST & NSA in early 90's
• published as FIPS-186 in 1991
• revised in 1993, 1996 & then 2000
• uses the SHA hash algorithm
• DSS is the standard, DSA is the algorithm
• FIPS 186-2 (2000) includes alternative RSA &
elliptic curve signature variants
• DSA is digital signature only unlike RSA, which
is a public-key technique
DSS vs RSA Signatures
In RSA approach,
- the message to be signed is input to a hash function → produces a
secure hash code of fixed length.
- Hash code is encrypted using sender's private key to form the signature.
- Both the message and the signature are then transmitted.
- The recipient takes the message and produces a hash code.
- The recipient also decrypts the signature using the sender's public key.
- If calculated hash code matches the decrypted signature, the signature
is accepted as valid. Because only the sender knows the private key,
only the sender could have produced a valid signature
DSS vs RSA Signatures…
DSS Approach
• The DSS approach also makes use of a hash function. The hash code is
provided as input to a signature function along with a random number k
generated for this particular signature.
DSS Approach…
• The signature function also depends on the sender's private key (PR a) and
a set of parameters known to a group of communicating principals. We can
consider this set to constitute a global public key (PUG).
• The result is a signature consisting of two components, labeled s and r. At
the receiving end, the hash code of the incoming message is generated.
This plus the signature is input to a verification function.
• The verification function also depends on the global public key as well as the
sender's public key (PUa), which is paired with the sender's private key.
• The output of the verification function is a value that is equal to the signature
component r if the signature is valid. The signature function is such that only
the sender, with knowledge of the private key, could have produced the valid
signature.
Digital Signature Algorithm (DSA)
➢ creates a 320 bit signature
➢ with 512-1024 bit security
➢ smaller and faster than RSA
➢ a digital signature scheme only
➢ security depends on difficulty of computing
discrete logarithms
DSA Key Generation
➢ have shared global public key values (p,q,g):
⚫ Choose a 160-bit prime number → ‘q’
⚫ Select a large prime → ‘p’
•Length of p → between 512 to 1024 bits (multiple of 64)
•such that q divides (p – 1) [ i.e.q is 160 bit prime divisor of (p-1) ]
⚫ choose g = h(p-1)/q mod p
•where h is an integer 1<h<p-1 and g must be >1
➢ users choose private & compute public key:
⚫ choose random private key → x ; x<q
⚫ compute public key→ y ; y = gx mod p
Note: Given the public key y, it is computationally infeasible to determine x,
which is the discrete logarithm of y to base g, mod p.
DSA Signature Creation
• To sign a message M the sender:
• generates a random signature key k, k<q
• k should be generated randomly or pseudo-
randomly and be unique for each signing
• then computes signature pair:
• r = (gk mod p)mod q
• s = [k-1(H(M)+ xr)] mod q
• sends signature (r,s) with message M
DSA Signature Creation…
Additional information on creating a signature
• a user calculates two quantities, r and s :
- these are functions of the public key components (p,q,g)
- the user’s private key → x
- Hash code of the message → H(M)
- Additionally an integer k → must be random (be
destroyed after use, and never be reused )
- use of temporary signature key k, per message
- calculations done → first mod p and then mod q →
to reduce the size of the result
DSA Signature Creation…
Additional information on creating a signature…
- The signature (r,s) is then sent with message to the
recipient.
Note :
- computing r only involves calculation mod p and does not
depend on message → it can be done in advance.
- Same thing is applicable with randomly choosing k’s and
computing their inverses.
DSA Signature Verification
➢ having received M & signature (r,s)
➢ to verify a signature, recipient computes:
• w = s-1 mod q
• u1= [H(M)w ] mod q
• u2= (rw)mod q
• v = [(gu1 yu2)mod p] mod q
➢ if v=r then signature is verified
DSA - Summary
Functions of Signing
Functions of Verifying
DSA - Problem
q = 11 selected prime divisor
p = 23 computed prime modulus: (p-1) mod q = 0
g=4 computed: 1 < g < p, gq mod p = 1;
and g = h((p–1)/q) mod p
411 mod 23 = 1 ; 4194304 mod 23 = 1
DSA – Problem…
x=7 selected: 0 < x < q
y=8 computed: y = gx mod p = 47 mod 23
Public Key : {p,q,g,y} = {23,11,4,8}
Private Key : {p,q,g,x} = {23,11,4,7}
DSA – Problem…
Assume Hash value H(M) as the message digest : H = 3
k=5 selected: 0 < k < q
compute: r = (gk mod p) mod q
k-1 Mul_inverse
= (45 mod 23) mod 11 => r = 1 modulo
compute: k-1 mod q = 1; 5*k-1 mod 11= 1 k-1 = 9
compute: s = k-1 *( H + rx) mod q
= 9 * (3 + (1*7) ) mod 11 => s = 2
Digital Signature {r,s} : {1,2}
DSA – Problem…
Digital Signature {r,s} : {1,2}
H=3 Hash value H(M) as the message digest
compute w=s-1mod q =1 ; 2-1 mod 11 = 1 ➔ w = 6
compute u1 = H*w mod q = 3*6 mod 11 = 7 ➔ u1 = 7
compute u2 = r*w mod q = 1*6 mod 11 = 6 ➔ u2 = 6
compute v = (((gu1)*(yu2)) mod p) mod q
= (((47)*(86)) mod 23) mod 11 = 2
= (16384 * 262144 mod 23) mod 11 = 1 ➔ v = 1
v == r verification passed
DSA vs RSA
• DSA and RSA are both cryptographic algorithms used for digital
signatures and encryption.
• DSA (Digital Signature Algorithm)
- DSA is a signature-only algorithm and requires a private key for
signing and a public key for verifying.
- DSA is a faster algorithm and is simpler to implement than RSA.
- DSA is more secure than RSA as it provides message integrity
and non-repudiation.
• RSA (Rivest-Shamir-Adleman)
- RSA is a signature and encryption algorithm that can be used
for both digital signatures and encryption.
- RSA is a slower algorithm and is more challenging to implement
than DSA.
- RSA is less secure than DSA, which is vulnerable to chosen-
ciphertext attacks and requires more computing power.