22 Digital Signature Algorithm

Hiteishi Diwanji

The need of Digital Signature:

Message signed by the user such that all recipients or intended recipient of message can verify the digital signature.User A signs a message m so that any user can verify the signature;
dA(m)User A signs a message m in a way that only user B can verify the signature;
eB(dA(m))Sending a message m and a signed message digest of m obtained by using a hash function standard h:
(m, dA(h(m)))Cryptosystem: Let each user Auses a cryptosystem with encryption and decryption algorithms: eA, dA
Message: m
PUBLIC-KEY CRYPTOGRAPHY

Encryption: eA (m) Decryption: dA (eA (m))

PUBLIC-KEY SIGNATURES Signing:dA (m) Verification of signatures: eA (dA (m)) A digital signature system (DSS) consists:
P – the space of possible plaintexts (messages).
S – the space of possible signatures.
K – the space of possible keys.
For each k ε K there is a signing algorithm sigk ε Sa and a corresponding verification algorithm verk ε V such that- sigk : P → S. – verk : P Ä S → {true, false} and verk (w,s) = true, if s = sig (w); false, otherwise.
Algorithms sigk and verk should be computable in polynomial time. Verification algorithm can be publically known; key of the signing algorithm must be kept secret.Signing a message w by A for B is eB (dA (m)) but a symmetric solution with encoding as c = dA (eB (m)) is not proper. Indeed, an active enemy, the tamperer, can intercept the message, then compute dT (eA (c)) = dT (eB (m)) and send it to Bob, pretending it is from him (without being able to decrypt the message). NIST Digital Signature Algorithm
The National Institute of Standards and Technology(NIST) has published Digital signature Algorithm(DSA) which was published as Federal Information Processing Standard FIPS 186.
DSA uses Secure Hash Algorithm.

The DSA approach – Sender perspective

DSA approach makes use of a hash functions.
Signature function takes two inputs – hash code and random number k
The signature function takes sender’s private key(PRa) and global public key(PUG)
Set of parameters known as group of communicating principals constitute PUG

The DSA approach – At Receiver

The hash code of the incoming message is generated.
This plus the signature is input to a verification function.
The verification function takes global public key and PUa (paired with sender’s private key).
The output of the verification function is the value that is equal to the signature component r if the signature is valid.

The Digital Signature Algorithm

DSA is based on the difficulty of computing discrete logarithms.
p – a prime modulus, where 2L–1 < p < 2L, and L is the bit length of p. for 512≤L≤1024 and L a multiple of 64. bit length between 512 and 1024 bits in increment of 64 bits.
q – a prime divisor of (p – 1), where 2N–1 < q < 2 N, and N is the bit length of q.
g = h(p-1)/q mod p a generator of a subgroup of order q in the multiplicative group of GF(p), such that 1 < g < p. h is any integer with 1<h<(p-1) such that h(p-1)/q mod p>1
x the private key that must remain secret; x is a randomly or pseudorandomly generated integer, such that 0 < x < q, i.e., x is in the range [1, q–1]. [User’s private key]
y the public key, where y = gx mod p. [User’s public key]
k a secret number that is unique to each message; k is a randomly or pseudorandomly generated integer, such that 0 < k < q, i.e., k is in the range [1, q–1]. [User’s per message secret number] Selection of Parameter Sizes and Hash Functions for DSA This Standard specifies the following choices for the pair L and N (the bit lengths of p and q, respectively):

L = 1024, N = 160

L = 2048, N = 224

L = 2048, N = 256

L = 3072, N = 256

Signing

r= (gk mod p) mod q

s=[K-1 (H(M)+xr)] mod q

Signature (r,s)

Verifying

w=(s’)-1 mod q

u1=[H(M’)w]mod q

u2=(r’)w mod q

V=[(gu1yu2)mod p]mod q

Test: v=r’

M = message to be signed

H(M) = hash of M using SHA-1

M’,r’,s’ = received versions of M,r,s

DSA Signature Verification and Validation:

Signature verification may be performed by any party (i.e., the signatory, the intended recipient or any other party) using the signatory’s public key.
A signatory may wish to verify that the computed signature is correct, perhaps before sending the signed message to the intended recipient.
The intended recipient (or any other party) verifies the signature to determine its authenticity.

The signature verification process is as follows:

The verifier shall check that 0 < r′ < q and 0 < s′ < q; if either condition is violated, the signature shall be rejected as invalid.
If the two conditions in step 1 are satisfied, the verifier computes the following:

w = (s′)–1mod q.

u1 = (H(M’)w) mod q.

u2 = ((r′)w) mod q.

If v = r′, then the signature is verified.
If v does not equal r′, then the signature is invalid. The message or the signature may have been modified, there may have been an error in the signatory’s generation process, or an imposter may have attempted to forge the signature.

Strength of DSA

It is infeasible to recover k from r or to recover x from s because of difficulty in taking discrete logarithm.
gk mod p is computationally heavy but this value does not depend on the message so can be computed in advance.
Calculating k-1 is demanding task.

you can view video on Digital Signature Algorithm

Suggested Reading:

Cryptography and Network Security Principles and Practice by William Stallings, sixth Edition, PEARSON.
Security in Computing by Charles Pfleeger & Shari Lawrence Pfleeger, fourth Edition, PEARSON.
Network Security by Charlie Kaufman, Radia Perlman, Mike Speciner, second Edition, PHI.
The Complete Reference – Network Security by Roberta Bragg, Mark Rhodes-Ousley & Keith Strassberg, Tata McGraw Hill
Network Security Bible by Eric Cole, Ronald Krutz, James Conley, Wiley
Hacking 6 Exposed by Stuart McClure, Joel Scambray & George Kurtz , Tata McGraw Hill .
www.snort.org
https://nmap.org