Digital Signature

Digital Signatures Applied Handbook of Cryptography: Chapt 11 slides courtesy of Xuhua Ding

Outline      

Framework RSA related signature schemes DSA related signature schemes One-time digital signatures Arbitrated signature schemes Signatures with added functionality

Framework Digital Signatures can provide  Authentication  Data Integrity  Non-Repudiation One Application  Certification of public keys in large networks

Framework (cont) 

Definitions 





Digital Signature - a data string which associates a message with some originating entity Digital Signature Generation Algorithm – a method for producing a digital signature Digital Signature Scheme - consists of a signature generation algorithm and an associated verification algorithm

Framework (cont) 

Notation M message space MS signing space S R

signature space a one-one mapping from M to MS called the redundancy function MR the image of R R-1 the inverse of R h a one-way function with domain M Mh hash value space, the image of h (h: M→ Mh)

Framework (cont) 

Taxonomy of digital signatures randomized message recovery deterministic

signature schemes

randomized appendix deterministic

Framework (cont) 

Schemes with appendix 





Requires the message as input to verification algorithm Rely on cryptographic hash functions rather than customized redundancy functions DSA, ElGamal, Schnorr etc.

Framework (cont) 

Digital Signature with Appendix M

Mh

h

m

m

SA,k

h

Mh x S

VA

u ∈ {True, False}

S s* s* = SA,k(mh) u = VA(mh, s*)

Framework (cont) 

Desirable Properties 

For each k ∈ R, SA,k should be efficient to compute



VA should be efficient to compute



It should be computationally infeasible for an entity other than the signer to find an m ∈ M and an s ∈ S such that VA(m’, s*) = true, where m’ = h(m)

Framework (cont) 

Digital Signature with Message Recovery M R

m

MR m

SA,k

S s*

Mr S S s*

VA

MR m r

R-1

M m

Framework (cont) 

Desirable properties 

For each k ∈ R, SA,k should be efficient to compute



VA should be efficient to compute



It should be computationally infeasible for an entity other than A to find any s* ∈ S such that VA(s*) ∈ MR

Framework (cont)

M m

h

Mh m h

R

MR m Mr S

SA,k

S s*

Framework (cont) 

Breaking a signature scheme  



Total Break: private key is comprimised Selective forgery: adversary can create a valid signature on a preselected message Existential forgery: adversary can create a valid signature with no control over the message

Framework (cont) 

Types of attacks  

Key-only: adversary knows only the public key Message attacks 





Known-message attack: adversary has signatures for a set of messages which are known to the adversary but not chosen by him Chosen-message attack: adversary obtains valid signatures from a chosen list of his choice (non adaptive) Adaptive chosen-message attack: adversary can use the signer as an oracle

RSA  



Key generation n, p, q, e, d Sign 

Compute mr = R(m)



Compute s = mrd mod n



The signature for m is s

Verify  

Obtain authentic public key (n, e) Compute mr = se mod n



Verify that mr ∈ Mr



Recover m = R-1(mr)

RSA (cont) 

Attacks  



Reblocking problem 



Integer factorization Homomorphic property If signatures are encrypted different modulus sizes can render the message unrecoverable

Importance of the redundancy function 

ISO/IEC 9796

RSA (cont) 

Performance (p, q are k-bit primes)  



Signature O(k3) Verification O(k2)

Bandwidth 

Bandwidth is determined by R. For example, ISO/IEC 9796 maps k-bit messages to 2k-bit elements in MS for a 2k-bit signature (efficiency of ½)

DSA 

DSA Algorithm : key generation  

  

select a prime q of 160 bits Choose 0≤t≤8, select 2511+64t
DSA (cont) 

DSA signature generation     

Select a random integer k, 0 < k < q Compute r=(αk mod p) mod q compute k-1 mod q Compute s=k-1 ∗(h(m) + ar) mod q signature = (r, s)

DSA (cont) 

DSA signature verification     

Verify 0
h(m) ≡ −ar + ks (mod q ) wh(m) + arw ≡ k (mod q ) u1 + au 2 ≡ k (mod q ) α u1 y u 2 mod p (mod q ) = α k mod p (mod q )

DSA (cont) 

Security of DSA 



Parameters: 



two distinct DL problems: ZP*, cyclic subgroup order q q~160bits, p 768~1Kb, p,q, α can be system wide

Probability of failure 

Pr[s=0]= (1/2)160

DSA (cont) 

Performance 

Signature Generation   



One modular exponentiation Several 160-bit operations (if p is 768 bits) The exponentiation can be precomputed

Verification 

Two modular exponentiations

ElGamal  

Key generation: p, q, α, a, y=αa mod p Signature Generation     

Select random k, 1 ≤ k ≤ p-1, gcd(k, p-1)=1 Compute r = αk mod p Compute k-1 mod (p-1) Compute s = k-1 ∗ (h(m) - ar) mod (p-1) signature is (r,s)

ElGamal (cont) 

Signature Verification  

Verify 1 ≤ r ≤ p-1 Compute v1 = yrrs mod p



Compute h(m) and v2= αh(m) mod p



Accept iff v1=v2 −1

s ≡ k {h(m) − ar} (mod p − 1) ks ≡ h(m) − ar (mod p − 1) α

h(m)

≡α

ar + ks

a r s

≡ (α ) r (mod p )

ElGamal (cont) 

Security (based on DL problem)   

Index-calculus attack: p should be large Pohlig-Hellman attack: p-1 should not be smooth Weak generators: If p ≡ 1 mod 4, α|p-1, DL can be broken for subgroup S of order α. Forgeries are then possible

ElGamal (cont) 

In addition… 

k must be unique for each message signed 



(s1-s2)k=(h(m1)-h(m2))mod (p-1)

An existential forgery attack can be mounted if a hash function is not used

ElGamal (cont) 

Performance 

Signature Generation   



Verification 



One modular exponentiation One Euclidean Algorithm Both can be done offline Three modular exponentiations

Generalized ElGamal Signatures

One-Time Signatures 



Definition: digital schemes used to sign, at most one message; otherwise signature can be forged. A new public key is required for each signed message. Most one-time signature schemes have the property that signature generation and verification are both very efficient

Rabin One-Time Signatures 

Key generation 





Select a symmetric key encryption scheme E (e.g. DES) Generate 2n random secret strings k1,k2...k2n∈K, each of bit length l Compute yi=Eki(M0(i)), i ∈[1,2n].



Public key is (y1,y2,...y2n),



private key is (k1,k2,...k2n).

Rabin One-Time Signatures 



Signature Generation: 

compute si=Eki(h(m)), i ∈[1,2n]



signature is (s1,s2,...s2n)

Verification:  

Compute h(m) Select n distinct random number rj, rj∈[1,2n]



Request from signer, the keys krj, ∀ j: 1 ≤ j ≤ n



Verify received n keys ie. does yrj= Ekr (M0(rj))?



Verify all srj = Ekr (h(m)),

j

j

Rabin One-Time Signatures 

Resolution of disputes: signer A, verifier B and TTP    

B provides m and the signature to TTP TTP gets private key k1,...k2n from A TTP verifies authenticity of the private key TTP computes ui=Eki(h(m)), 1 ≤ i ≤ n. If ui = si for at most n values of i, it is forgery. If n+1 or more values match, it is valid signature



1 Rationale for dispute resolution protocol 2n   A can disavow with Pr  =n   

Arbitrated Digital Signatures 







Requires an unconditionally TTP as part of the signature generation and signature verification. Each entity shares a symmetric key with the TTP Symmetric key cryptography results in a very fast algorithm However, this speedup is overshadowed by the TTP as well as communication overhead

Arbitrated Digital Signatures 

Signature Generation (by A)

A

IAs, = uE =k (h(m)||I Ek (h(m)) A) T

A

TTP

Arbitrated Digital Signatures 

Signature Verification (by B)

B

IBE,kv(h(m)||I = Ek (s) A) B

B

TTP

ESIGN 





Key generation  Compute n=p2q, select k>3  Public key(n,k), private (p,q) Sign message m  compute v=h(m), random x, 0 ≤ x < pq  w = ((v-xk) mod n/ (pq), y = w(kxk-1)-1 mod p  Compute s=x+ypq mod n Verify:  compute u = sk mod n, z = h(m)  if z ≤ u ≤ z + 22 lg(n)/3 , accept the signature

ESIGN (cont) 

Why does this work? I refer you to the text p 473 



Security of ESIGN  



Based on factoring of large integers. Not known whether n=p2q is easier than factoring RSA modulus Given m and s, inkorder to forge a signature 2 lg n 3 for m’, we must  h(m' ) ≤ s mod n ≤ h(m' ) + 2 have that Assuming h behaves like a random function, we would expect to try 2lg(n)/3 different values of m’

ESIGN (cont) 

Efficiency of ESIGN  The only modular exponentiation is with parameter k which may be taken to be quite small (e.g. k=4)  For a 768-bit modulus n, ESIGN signature generation may be between one and two orders of magnitude (10 to 100 times) faster than RSA signature generation.

Blind signature scheme 



Definition: A sends a piece of information to B. B signs and returns the signature to A. From this signature, A can compute B’s signature on a priori message m of A’s choice. At the completion of the protocol, B knows neither m, nor the signature associated with it. Application: e-cash

Blind signature scheme (cont) 

Chaum  



Sender A; Signer B B’s RSA public and private key are as usual. k is a random secret integer chosen by A, satisfying 0 ≤ k
 

(blinding) A: comp m* = mke mod n, to B Note: (mke)d = mdk (signing) B comp s* = (m*)d mod n, to A (unblinding) A: computes s = k-1s* mod n

Undeniable Signature Schemes 

Definition: signature verification requires the cooperation of signer



Chaum-van Antwerpen 

Key generation    

Select random prime p=2q+1, q is prime Select a generator α for the subgroup of order q in Zp* Select random a∈{1,2,...q-1}, y= αamod p public (p, α, y), private a

Chaum-van Antwerpen 

Signature Generation 



compute s = ma mod p

Verification 

  

B selects a random secret integers x1, x2 ∈ {1,2,...q-1} B computes z = sx1yx2 mod p, and sends z to A A computes w = za-1mod p, and sends w to B B computes w′ = mx1αx2 mod p. Valid iff w= w′

w≡z

a -1

x1

x2 a −1

≡ (s y )

≡ (m

ax1

α

ax2 a −1

)

x1

≡m α

x2

≡ w' mod p

Chaum-van Antwerpen 

If s is a forgery, B accept it with pr=1/q and independent of adversary’s computation resources



A could attempt to disavow a signature   

refuse to participate in verification perform the verification incorrectly claim a signature forgery even though the verification protocol is successful.

Chaum-van Antwerpen 

Disavowal protocol 





Select two pair (x1, x2) and (x’1, x’2) and verify twice Compute c = (wα-x2)x’1 mod p and c′ = (w′α-x’2)x1 mod p, if c = c′, s is a forgery, otherwise s is valid and A is attempting to disavow the signature

Let m be message, s a signature on m 



If s ≠ ma mod p and the disavowal protocol runs correctly, then c=c′ If s = ma mod p. B follows protocol, but A does not. The Pr[c=c′] is 1/q