1
Digital Signature
曹天杰
Tianjie Cao
tjcao@cumt.edu.cn
College of Computer Science and
Technology,China University of Mining and Technology,
Xuzhou,China
中国矿业大学计算机科学与技术学院
2003.6.6
2
Definitions
? 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 verification algorithm - a method
for verifying that a digital signature is authentic
(i.e.,was indeed created by the specified entity),
– Digital Signature Scheme - consists of a signature
generation algorithm and an associated
verification algorithm
3
Applications
Digital Signatures can provide
? Authentication
? Data Integrity
? Non-Repudiation
One Application
? Certification of public keys in large networks
4
Classification
? Digital signature schemes with appendix
require the original message as input to the
verification algorithm,
? Digital signature schemes with message
recovery do not require the original message
as input to the verification algorithm,In this
case,the original message is recovered from
the signature itself,
5
Classification (cont)
? Taxonomy of digital signatures
signature schemes
message recovery
appendix
deterministic
randomized
randomized
deterministic
6
Types of Signatures
? Direct digital signature – involves only the
communicating parties
?Assumed that receiver knows public key of
sender,
?Signature may be formed by (1) encrypting
entire message with sender’s private key or (2)
encrypting hash code of message with sender’s
private key,
?Further encryption of entire message +
signature with receiver’s public key or shared
private key ensures confidentiality,
7
Types of Signatures
? Problems with direct signatures,
?Validity of scheme depends on the security of
the sender’s private key ? sender may later
deny sending a certain message,
?Private key may actually be stolen from X at
time T,so timestamp may not help,
8
Types of Signatures
? Arbitrated digital signature – involves a
trusted third party or arbiter
?Every signed message from sender,X,to
receiver,Y,goes to an arbiter,A,first,
?A subjects message + signature to number of
tests to check origin & content
?A dates the message and sends it to Y with
indication that it has been verified to its
satisfaction
9
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
10
Arbitrated Digital Signatures
? Signature Generation (by A)
A TTP IA,u = EkA(h(m))
s = EkT(h(m)||IA)
11
Arbitrated Digital Signatures
? Signature Verification (by B)
B TTP IB,v = EkB(s)
EkB(h(m)||IA)
12
Digital Signature Standards
? RSA Digital Signature
- ISO 9796
- ANSI X9.31
- CCITT X.509
? El Gamal
? NIST FIPS 186 Digital Signature Standard
(DSS)
13
Public Key Cryptography
Signature schemes
Let
? P be the set of all messages
? A be the set of signatures
? K be the set of all keys
14
Basic Mechanism of Signature
Schemes
? K,A key generation algorithm to randomly select
a public key pair,
? Sig K, A signature algorithm that takes message +
private key as input and generates a signature for
the message as output
? Ver K, A signature verification algorithm that
takes signature + public key as input and generates
information bit according to whether signature is
consistent as output,
15
Attack models
? Total Breaking Attack
- The attacker knows the public key,He tries to recover the
corresponding secret key,
? Forgery Attack
- The attacker knows the public key,He tries to find the signature
for a given message,
? Existential Forgery Attack
- The attacker knows the public key,He tries to find a pair of
a message and its signature,
? Chosen Message Attack (CMA)
- The attacker is able to sign messages but does not know the key
used,He tries to perform the (existential) forgery or to obtain the
secret key,
16
Forgery Attack
The attacker tries to find the signature s
from a given message m and the public key,
Forgery
attacker
message m
public key
signature s of m
(d,secret key )
17
Existential Forgery Attack
Existential
Forgery Attacker
public key
(m,s),pair of
message
and signature,
The attacker tries to find a pair of a message
and its signature from the public key,
The message of the pair may have no meanings,
(d,secret key )
18
Chosen Message Attack
The attacker tries to find a pair (m,s) from several pairs of signature
(mi,si) and the public key,
Chosen Message
Attacker public key
(m,s),
pair of message
and signature,
(d,secret key )
Signing Oracle
messages m Sd(m),signatures
If the attacker can choose new messages dependent to obtained signatures,
it is called the adaptive chosen message attack,
19
The RSA digital signature
Let n = pq,where p and q are primes,
Let P = A = Zn,and define
K = {(n,p,q,e,d), ed = 1 mod f(n) },
For each key K = (n,p,q,e,d),define
sigK(m) = md mod n
and
verK(m,y) = true y
e = m mod n,
where (m,y) ? Zn,
Public key = (n,e),Private key (n,d),
?
20
Existential Forgery of RSA
Let (S1,S2) be the signatures of the messages (M1,M2),
namely S1 = M1d mod n,S2 = M2d mod n,
Then S = S1*S2 mod n is the signature of M = M1*M2 mod n,
because S = S1*S2 = M1d M2d = (M1*M2)d mod n,
The message M must be randomized before signing,
The message M is usually signed by S = h(M)d mod n,
where h is the hash function h,{0,1}* -> Z/nZ,
(h(M) = h(M1)*h(M2) mod n does not hold)
21
The ElGamal signature scheme
Let p be a prime and g ? Zp a primitive element,
Let P = Zp*,
A = Zp* x Zp-1 and
K = {(p,g,x,y),y = gx mod p },
? The values p,g,y are the public key,
? x is the private key,
22
The ElGamal signature scheme
? Signing
Let m ? Zp* be a message,
For K = {(p,g,x,y),y = gx mod p },and secret random
number k ? Zp-1 *,define,sigK(m,k) = (s,t),where
– s = gk mod p
– t = (m-xs)k-1 mod p-1(kt +xs =m mod p-1 )
? Verification
verK(m,(s,t)) = true st·y s = gm mod p,
st·y s =gkt· gxs = gm mod p kt +xs =m mod p-1
?
?
23
Toy example
Let p = 467,g = 2,x = 127,Then y = 2127 mod 467 = 132,
Let message m = 100,
Choose k = 213,Then k-1 mod 466 = 431,
The signature is,
– s = 2213 mod 467 = 29
– t = (m-xs)k-1 mod(p-1) = (100-127x29)431 mod 466
= 51
Verification,2100 ?? 132292951 mod 467
24
The security of the ElGamal
signature
? If the Discrete Logarithm problem can be
solved then ElGamal signatures can be
forged,
? The converse may not be true,
? The exponent k must be
– private
– cannot be used twice
– best,chosen at random,
25
DSA
? A variant of the ElGamal and Schnorr Signature
Schemes
? Public key cryptographic system used for
generating and verifying digital signatures
? Cannot be used for data encryption or key
exchange
? Based on familiar number theory concepts
? Makes use of the Secure Hash Algorithm (SHA-1)
26
Key Generation Algorithm
? Generating public and private keys,
1) Select a prime number q
? 2159 < q < 2160
? |q| = 160 bits
2) Select a prime number p
? 2511 < p < 21024
? |p| = L bits
? 512 ≤ L ≤ 1024
? L ≡ 0 mod 64
? p – 1 ≡ 0 mod q
27
Key Generation Algorithm
? Generating public and private keys,
3) Calculate a qth root of 1,?
? ? = g (p – 1) / q mod p
? 1 < g < (p – 1)
? ? > 1
? ? ? Zp*
4) Select a random,personal” private key x
? 1 ≤ x ≤ (q – 1)
5) Calculate,personal” public key y
? y = ? x mod p
28
Key Generation Algorithm
? Global Public Key Components
– q,p,?
? User’s Private Key
– x
? User’s Public Key
– y
? User’s public key is calculated from his/her
private key
29
Signature Generation Algorithm
? Signing a message m,
1) Select a random secret integer k
? 0 < k < q
? should be unique for each message signed
2) Calculate s
? s = (? k mod p) mod q
? 0 < s < q
3) Calculate t
? t = (SHA-1(m) + (x s)) k -1 mod q
? 0 < t < q
4) The signature of m produces the pair (s,t) to
be used in the verification process
30
Signature Generation Algorithm
Message m SHA-1 Message Digest
Sign
s = (? k mod p) mod q
t = (SHA-1(m) + (x s)) k -1 mod q
Private Key x
Digital Signature (s,t)
31
Verification Algorithm
? Verifying a signature (s,t),
1) Verify
? 0 < s < q and 0 < t < q
2) Calculate e1
? u1 = SHA-1(m) t -1 mod q
3) Calculate e2
? u2 = s t -1 mod q
4) Calculate v
? v = [(? u1 y u2) mod p] mod q
5) Accept the signature iff,
? v = s
32
Verification Algorithm
Message m SHA-1 Message Digest
Verify
u1 = SHA-1(m) t -1 mod q
u2 = s t -1 mod q
v = [(? u1 y u2) mod p] mod q
Public
Keys
q,p,?,y
Digital
Signature
(s,t)
v = s v ≠ s
Signature
Verification
Succeeded
Signature
Verification
Failed
33
Proof
? Let w = t -1 mod q
u1 = ( SHA-1(m) w ) mod q
u2 = ( s w ) mod q
? From signature generation we have,
t = (k -1( SHA-1(m) + x s )) mod q
So,w = t -1 mod q
= ((k -1( SHA-1(m) + x s ))-1 ) mod q
= ( k ( SHA-1(m) + x s )-1 ) mod q
Rearranging,
( SHA-1(m) + x s ) w mod q = k mod q
34
Proof (continued)
? From key generation,we have,
y = ? x mod p
? So,v = ( (? u1 y u2) mod p ) mod q
= ( (? SHA-1(m) w y s w ) mod p ) mod q
= ( (? SHA-1(m) w ? x s w ) mod p ) mod q
= ( (? ( SHA-1(m) + x s ) w ) mod p ) mod q
= ( (? k ) mod p ) mod q (? q =1 mod p)
= s
35
Example
? Key Generation
– p = 124540019
– q = 17389
– (p – 1) / q = 7162
– g = 110217528
– ? = g(p – 1) / q mod p = 10083255
– x = 12496
– y = ? x mod p = 119946265
36
Example (continued)
? Key Generation
– Public Key,
? p = 124540019
? q = 17389
? ? = 10083255
–,Personal” Private Key,
? x = 12496
–,Personal” Public Key,
? y = 119946265
37
Example (continued)
? Signature Generation
– k = 9557
– s = (? k mod p) mod q = 34
– t = (SHA-1(m) + (x s)) k -1 mod q = 13049
? k -1 mod q = 7631
? SHA-1(m) = 5246 (contrived for example)
? Signature for m is (s = 34,t = 13049)
38
Example (continued)
? Signature Verification
– u1 = SHA-1(m) t -1 = 12716
– u2 = s t -1 mod q = 8999
– v = [(? e1 y e2) mod p] mod q = 34
? Since v = s = 34,the verification is
successful and the signature is validated
39
Security of DSA
? Adversary
– Does not know private key of signer
– Cannot generate valid signature
? Given the user’s public key,it is
computationally infeasible to determine the
user’s private key
– Discrete logarithm problem
40
Criticism,RSA vs,DSA
? RSA,
– used for both
encryption and digital
signatures
– signature verification
faster than signature
generation
? DSA,
– only for digital
signatures
– signature generation
faster than signature
verification
41
Criticism from RSA
? DSA lacked RSA’s flexibility
? DSA too new and not analyzed enough
? DSA signature verification was too slow
? Computer and hardware vendors already
standardized on the RSA algorithm
? Process NIST used to choose DSA was too
secretive and arbitrary
– too much influence from NSA
42
Criticism of the Key
? p was initially fixed at 512 bits
– Not secure enough
? Allowed up to 1024 bits
? October 2001,NIST recommended that p
be 1024 bits
–,neither a standard nor a guideline”
? Presently considered secure with 1024 bits
43
? The Elliptic Curve Digital Signature Algorithm
(ECDSA) is being proposed as an ANSI X9.62
standard
? Like DSA based on ElGamal signature scheme
? Better than DSA
? With much smaller key length it provides same level
of security as those of RSA and DSA
? Speed can be optimized
ECDSA
44
ECDSA (cont’d)
? Public keys,(E,P,n,Q)
? Private keys,d
where
– E is an Elliptic Curve
– P is a point on the curve whose order is n
– d is an integer randomly selected in the interval [1,
n-1]
– Q is another point on the curve such that
PdQ ??
45
ECDSA (cont’d)
? Signature,
where
– h(m) is Secure Hash of the message m (SHA-1)
– k is a random integer in the interval [1,n-1]
– (s,t) is signature
– is components of an EC point (integers)
1 1 1(,) a n d s m o dk P x y x n? ? ?
1 [ ( ) ] m o dt k h m d s n?? ? ? ?
),( 11 yx
46
ECDSA (cont’d)
? Verification,
? where
– w = t-1 (mod n)
12( ) m o d a n d m o du h m w n u s w n? ? ? ?
nxvyxQuPu m o d a n d ),( 00021 ?????
vs?
47
? A mechanism which can be used to sign,at most,
one message; otherwise,signatures can be forged
? A new public key is required for each message
? Public information (validation parameters) is
necessary for verification
? Signature generation and verification are very
efficient
? Useful in applications such as smart cards,where
low computational complexity is required
One-time signature schemes
48
? One-time private key,
–,each of bitlength l
? One-time public key,
–,each of bitlength l
such that
where
– E is a symmetric-key encryption scheme (e.g,DES)
–,is the binary
representation of i,
The Rabin one-time signature
scheme
? ?nkkk 221,,,?
? ?nyyy 221,,,?
niiMEy iki ???? 21)),(( 0
0110 0)( bbbiM eel ???? 011 bbb e ??
49
? Signature,
where
– m is message
– is signature
– h is hash function
– E is a symmetric-key encryption scheme (e.g,
DES)
nimhEs iki ???? 21))((
? ?nsss 221,,,?
The Rabin scheme (cont’d)
50
? Verification,
– Select n distinct random numbers such that
?[1,2n]
– Request the private keys
– Verify the authenticity of key by checking
where
– Verify that
– Unlike other digital signature schemes,verification
can be done only once,
jr
njk jr ??1,
jrj yz ? ))(( 0 jkj rMEz jr?
njmhEs
jrj kr
??? 1) ),((
jr
The Rabin scheme (cont’d)
51
The Rabin scheme (cont’d)
? key size,n=80,l=64,
? Resolution of disputes,signer A,verifier B and
TTP
– B provide m and signature
– TTP get private key k1,...k2n from A
– TTP verify authenticity of the private key
TTP compute ui=Eki(h(m)),1?i ?2n,If ui=si for at most n
values of i,it is forgery by B,If n+1 or more values
match,it is valid signature
? Rationale for dispute resolution protocol
– A can disavow with Pr=1/C2nn
52
The Rabin scheme (cont’d)
? Rationale for dispute resolution protocol
– If B has attempted to forge A’s signature on a new
message m0,B either needs to determine at least one
more key k0 so that at least n + 1 values of i give ui=si,
or determine m0 such that h(m) = h(m0),
– If A attempts to create a signature which it can later
disavow,A must ensure that ui=si for precisely n values
of i and hope that B chooses these n values,the
probability of which is only with Pr=1/C2nn
53
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
54
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 < n
– Protocol actions
? (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
55
Blind signature scheme (cont)
? cut-and-choose technique
– (1) BOB prepares n documents,each using a different cover name,
giving himself diplomatic immunity,
– (2) BOB blinds each of these documents with a different blinding
factor,
– (3) BOB sends the n blinded documents to ALICE,
– (4) ALICE chooses n – 1 documents at random and asks BOB for the
blinding factors for each of those documents,
– (5) BOB sends ALICE the appropriate blinding factors,
– (6) ALICE opens (i.e.,she removes the blinding factor) n – 1
documents and makes sure they are correct—and not pension
authorizations,
– (7) ALICE signs the remaining document and sends it to BOB,
– (8) Agent removes the blinding factor and reads his new cover name,
―The Crimson Streak.‖ The signed document gives him diplomatic
immunity under that name,
56
References
– FIPS PUB 186-2
Digital Signature
曹天杰
Tianjie Cao
tjcao@cumt.edu.cn
College of Computer Science and
Technology,China University of Mining and Technology,
Xuzhou,China
中国矿业大学计算机科学与技术学院
2003.6.6
2
Definitions
? 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 verification algorithm - a method
for verifying that a digital signature is authentic
(i.e.,was indeed created by the specified entity),
– Digital Signature Scheme - consists of a signature
generation algorithm and an associated
verification algorithm
3
Applications
Digital Signatures can provide
? Authentication
? Data Integrity
? Non-Repudiation
One Application
? Certification of public keys in large networks
4
Classification
? Digital signature schemes with appendix
require the original message as input to the
verification algorithm,
? Digital signature schemes with message
recovery do not require the original message
as input to the verification algorithm,In this
case,the original message is recovered from
the signature itself,
5
Classification (cont)
? Taxonomy of digital signatures
signature schemes
message recovery
appendix
deterministic
randomized
randomized
deterministic
6
Types of Signatures
? Direct digital signature – involves only the
communicating parties
?Assumed that receiver knows public key of
sender,
?Signature may be formed by (1) encrypting
entire message with sender’s private key or (2)
encrypting hash code of message with sender’s
private key,
?Further encryption of entire message +
signature with receiver’s public key or shared
private key ensures confidentiality,
7
Types of Signatures
? Problems with direct signatures,
?Validity of scheme depends on the security of
the sender’s private key ? sender may later
deny sending a certain message,
?Private key may actually be stolen from X at
time T,so timestamp may not help,
8
Types of Signatures
? Arbitrated digital signature – involves a
trusted third party or arbiter
?Every signed message from sender,X,to
receiver,Y,goes to an arbiter,A,first,
?A subjects message + signature to number of
tests to check origin & content
?A dates the message and sends it to Y with
indication that it has been verified to its
satisfaction
9
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
10
Arbitrated Digital Signatures
? Signature Generation (by A)
A TTP IA,u = EkA(h(m))
s = EkT(h(m)||IA)
11
Arbitrated Digital Signatures
? Signature Verification (by B)
B TTP IB,v = EkB(s)
EkB(h(m)||IA)
12
Digital Signature Standards
? RSA Digital Signature
- ISO 9796
- ANSI X9.31
- CCITT X.509
? El Gamal
? NIST FIPS 186 Digital Signature Standard
(DSS)
13
Public Key Cryptography
Signature schemes
Let
? P be the set of all messages
? A be the set of signatures
? K be the set of all keys
14
Basic Mechanism of Signature
Schemes
? K,A key generation algorithm to randomly select
a public key pair,
? Sig K, A signature algorithm that takes message +
private key as input and generates a signature for
the message as output
? Ver K, A signature verification algorithm that
takes signature + public key as input and generates
information bit according to whether signature is
consistent as output,
15
Attack models
? Total Breaking Attack
- The attacker knows the public key,He tries to recover the
corresponding secret key,
? Forgery Attack
- The attacker knows the public key,He tries to find the signature
for a given message,
? Existential Forgery Attack
- The attacker knows the public key,He tries to find a pair of
a message and its signature,
? Chosen Message Attack (CMA)
- The attacker is able to sign messages but does not know the key
used,He tries to perform the (existential) forgery or to obtain the
secret key,
16
Forgery Attack
The attacker tries to find the signature s
from a given message m and the public key,
Forgery
attacker
message m
public key
signature s of m
(d,secret key )
17
Existential Forgery Attack
Existential
Forgery Attacker
public key
(m,s),pair of
message
and signature,
The attacker tries to find a pair of a message
and its signature from the public key,
The message of the pair may have no meanings,
(d,secret key )
18
Chosen Message Attack
The attacker tries to find a pair (m,s) from several pairs of signature
(mi,si) and the public key,
Chosen Message
Attacker public key
(m,s),
pair of message
and signature,
(d,secret key )
Signing Oracle
messages m Sd(m),signatures
If the attacker can choose new messages dependent to obtained signatures,
it is called the adaptive chosen message attack,
19
The RSA digital signature
Let n = pq,where p and q are primes,
Let P = A = Zn,and define
K = {(n,p,q,e,d), ed = 1 mod f(n) },
For each key K = (n,p,q,e,d),define
sigK(m) = md mod n
and
verK(m,y) = true y
e = m mod n,
where (m,y) ? Zn,
Public key = (n,e),Private key (n,d),
?
20
Existential Forgery of RSA
Let (S1,S2) be the signatures of the messages (M1,M2),
namely S1 = M1d mod n,S2 = M2d mod n,
Then S = S1*S2 mod n is the signature of M = M1*M2 mod n,
because S = S1*S2 = M1d M2d = (M1*M2)d mod n,
The message M must be randomized before signing,
The message M is usually signed by S = h(M)d mod n,
where h is the hash function h,{0,1}* -> Z/nZ,
(h(M) = h(M1)*h(M2) mod n does not hold)
21
The ElGamal signature scheme
Let p be a prime and g ? Zp a primitive element,
Let P = Zp*,
A = Zp* x Zp-1 and
K = {(p,g,x,y),y = gx mod p },
? The values p,g,y are the public key,
? x is the private key,
22
The ElGamal signature scheme
? Signing
Let m ? Zp* be a message,
For K = {(p,g,x,y),y = gx mod p },and secret random
number k ? Zp-1 *,define,sigK(m,k) = (s,t),where
– s = gk mod p
– t = (m-xs)k-1 mod p-1(kt +xs =m mod p-1 )
? Verification
verK(m,(s,t)) = true st·y s = gm mod p,
st·y s =gkt· gxs = gm mod p kt +xs =m mod p-1
?
?
23
Toy example
Let p = 467,g = 2,x = 127,Then y = 2127 mod 467 = 132,
Let message m = 100,
Choose k = 213,Then k-1 mod 466 = 431,
The signature is,
– s = 2213 mod 467 = 29
– t = (m-xs)k-1 mod(p-1) = (100-127x29)431 mod 466
= 51
Verification,2100 ?? 132292951 mod 467
24
The security of the ElGamal
signature
? If the Discrete Logarithm problem can be
solved then ElGamal signatures can be
forged,
? The converse may not be true,
? The exponent k must be
– private
– cannot be used twice
– best,chosen at random,
25
DSA
? A variant of the ElGamal and Schnorr Signature
Schemes
? Public key cryptographic system used for
generating and verifying digital signatures
? Cannot be used for data encryption or key
exchange
? Based on familiar number theory concepts
? Makes use of the Secure Hash Algorithm (SHA-1)
26
Key Generation Algorithm
? Generating public and private keys,
1) Select a prime number q
? 2159 < q < 2160
? |q| = 160 bits
2) Select a prime number p
? 2511 < p < 21024
? |p| = L bits
? 512 ≤ L ≤ 1024
? L ≡ 0 mod 64
? p – 1 ≡ 0 mod q
27
Key Generation Algorithm
? Generating public and private keys,
3) Calculate a qth root of 1,?
? ? = g (p – 1) / q mod p
? 1 < g < (p – 1)
? ? > 1
? ? ? Zp*
4) Select a random,personal” private key x
? 1 ≤ x ≤ (q – 1)
5) Calculate,personal” public key y
? y = ? x mod p
28
Key Generation Algorithm
? Global Public Key Components
– q,p,?
? User’s Private Key
– x
? User’s Public Key
– y
? User’s public key is calculated from his/her
private key
29
Signature Generation Algorithm
? Signing a message m,
1) Select a random secret integer k
? 0 < k < q
? should be unique for each message signed
2) Calculate s
? s = (? k mod p) mod q
? 0 < s < q
3) Calculate t
? t = (SHA-1(m) + (x s)) k -1 mod q
? 0 < t < q
4) The signature of m produces the pair (s,t) to
be used in the verification process
30
Signature Generation Algorithm
Message m SHA-1 Message Digest
Sign
s = (? k mod p) mod q
t = (SHA-1(m) + (x s)) k -1 mod q
Private Key x
Digital Signature (s,t)
31
Verification Algorithm
? Verifying a signature (s,t),
1) Verify
? 0 < s < q and 0 < t < q
2) Calculate e1
? u1 = SHA-1(m) t -1 mod q
3) Calculate e2
? u2 = s t -1 mod q
4) Calculate v
? v = [(? u1 y u2) mod p] mod q
5) Accept the signature iff,
? v = s
32
Verification Algorithm
Message m SHA-1 Message Digest
Verify
u1 = SHA-1(m) t -1 mod q
u2 = s t -1 mod q
v = [(? u1 y u2) mod p] mod q
Public
Keys
q,p,?,y
Digital
Signature
(s,t)
v = s v ≠ s
Signature
Verification
Succeeded
Signature
Verification
Failed
33
Proof
? Let w = t -1 mod q
u1 = ( SHA-1(m) w ) mod q
u2 = ( s w ) mod q
? From signature generation we have,
t = (k -1( SHA-1(m) + x s )) mod q
So,w = t -1 mod q
= ((k -1( SHA-1(m) + x s ))-1 ) mod q
= ( k ( SHA-1(m) + x s )-1 ) mod q
Rearranging,
( SHA-1(m) + x s ) w mod q = k mod q
34
Proof (continued)
? From key generation,we have,
y = ? x mod p
? So,v = ( (? u1 y u2) mod p ) mod q
= ( (? SHA-1(m) w y s w ) mod p ) mod q
= ( (? SHA-1(m) w ? x s w ) mod p ) mod q
= ( (? ( SHA-1(m) + x s ) w ) mod p ) mod q
= ( (? k ) mod p ) mod q (? q =1 mod p)
= s
35
Example
? Key Generation
– p = 124540019
– q = 17389
– (p – 1) / q = 7162
– g = 110217528
– ? = g(p – 1) / q mod p = 10083255
– x = 12496
– y = ? x mod p = 119946265
36
Example (continued)
? Key Generation
– Public Key,
? p = 124540019
? q = 17389
? ? = 10083255
–,Personal” Private Key,
? x = 12496
–,Personal” Public Key,
? y = 119946265
37
Example (continued)
? Signature Generation
– k = 9557
– s = (? k mod p) mod q = 34
– t = (SHA-1(m) + (x s)) k -1 mod q = 13049
? k -1 mod q = 7631
? SHA-1(m) = 5246 (contrived for example)
? Signature for m is (s = 34,t = 13049)
38
Example (continued)
? Signature Verification
– u1 = SHA-1(m) t -1 = 12716
– u2 = s t -1 mod q = 8999
– v = [(? e1 y e2) mod p] mod q = 34
? Since v = s = 34,the verification is
successful and the signature is validated
39
Security of DSA
? Adversary
– Does not know private key of signer
– Cannot generate valid signature
? Given the user’s public key,it is
computationally infeasible to determine the
user’s private key
– Discrete logarithm problem
40
Criticism,RSA vs,DSA
? RSA,
– used for both
encryption and digital
signatures
– signature verification
faster than signature
generation
? DSA,
– only for digital
signatures
– signature generation
faster than signature
verification
41
Criticism from RSA
? DSA lacked RSA’s flexibility
? DSA too new and not analyzed enough
? DSA signature verification was too slow
? Computer and hardware vendors already
standardized on the RSA algorithm
? Process NIST used to choose DSA was too
secretive and arbitrary
– too much influence from NSA
42
Criticism of the Key
? p was initially fixed at 512 bits
– Not secure enough
? Allowed up to 1024 bits
? October 2001,NIST recommended that p
be 1024 bits
–,neither a standard nor a guideline”
? Presently considered secure with 1024 bits
43
? The Elliptic Curve Digital Signature Algorithm
(ECDSA) is being proposed as an ANSI X9.62
standard
? Like DSA based on ElGamal signature scheme
? Better than DSA
? With much smaller key length it provides same level
of security as those of RSA and DSA
? Speed can be optimized
ECDSA
44
ECDSA (cont’d)
? Public keys,(E,P,n,Q)
? Private keys,d
where
– E is an Elliptic Curve
– P is a point on the curve whose order is n
– d is an integer randomly selected in the interval [1,
n-1]
– Q is another point on the curve such that
PdQ ??
45
ECDSA (cont’d)
? Signature,
where
– h(m) is Secure Hash of the message m (SHA-1)
– k is a random integer in the interval [1,n-1]
– (s,t) is signature
– is components of an EC point (integers)
1 1 1(,) a n d s m o dk P x y x n? ? ?
1 [ ( ) ] m o dt k h m d s n?? ? ? ?
),( 11 yx
46
ECDSA (cont’d)
? Verification,
? where
– w = t-1 (mod n)
12( ) m o d a n d m o du h m w n u s w n? ? ? ?
nxvyxQuPu m o d a n d ),( 00021 ?????
vs?
47
? A mechanism which can be used to sign,at most,
one message; otherwise,signatures can be forged
? A new public key is required for each message
? Public information (validation parameters) is
necessary for verification
? Signature generation and verification are very
efficient
? Useful in applications such as smart cards,where
low computational complexity is required
One-time signature schemes
48
? One-time private key,
–,each of bitlength l
? One-time public key,
–,each of bitlength l
such that
where
– E is a symmetric-key encryption scheme (e.g,DES)
–,is the binary
representation of i,
The Rabin one-time signature
scheme
? ?nkkk 221,,,?
? ?nyyy 221,,,?
niiMEy iki ???? 21)),(( 0
0110 0)( bbbiM eel ???? 011 bbb e ??
49
? Signature,
where
– m is message
– is signature
– h is hash function
– E is a symmetric-key encryption scheme (e.g,
DES)
nimhEs iki ???? 21))((
? ?nsss 221,,,?
The Rabin scheme (cont’d)
50
? Verification,
– Select n distinct random numbers such that
?[1,2n]
– Request the private keys
– Verify the authenticity of key by checking
where
– Verify that
– Unlike other digital signature schemes,verification
can be done only once,
jr
njk jr ??1,
jrj yz ? ))(( 0 jkj rMEz jr?
njmhEs
jrj kr
??? 1) ),((
jr
The Rabin scheme (cont’d)
51
The Rabin scheme (cont’d)
? key size,n=80,l=64,
? Resolution of disputes,signer A,verifier B and
TTP
– B provide m and signature
– TTP get private key k1,...k2n from A
– TTP verify authenticity of the private key
TTP compute ui=Eki(h(m)),1?i ?2n,If ui=si for at most n
values of i,it is forgery by B,If n+1 or more values
match,it is valid signature
? Rationale for dispute resolution protocol
– A can disavow with Pr=1/C2nn
52
The Rabin scheme (cont’d)
? Rationale for dispute resolution protocol
– If B has attempted to forge A’s signature on a new
message m0,B either needs to determine at least one
more key k0 so that at least n + 1 values of i give ui=si,
or determine m0 such that h(m) = h(m0),
– If A attempts to create a signature which it can later
disavow,A must ensure that ui=si for precisely n values
of i and hope that B chooses these n values,the
probability of which is only with Pr=1/C2nn
53
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
54
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 < n
– Protocol actions
? (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
55
Blind signature scheme (cont)
? cut-and-choose technique
– (1) BOB prepares n documents,each using a different cover name,
giving himself diplomatic immunity,
– (2) BOB blinds each of these documents with a different blinding
factor,
– (3) BOB sends the n blinded documents to ALICE,
– (4) ALICE chooses n – 1 documents at random and asks BOB for the
blinding factors for each of those documents,
– (5) BOB sends ALICE the appropriate blinding factors,
– (6) ALICE opens (i.e.,she removes the blinding factor) n – 1
documents and makes sure they are correct—and not pension
authorizations,
– (7) ALICE signs the remaining document and sends it to BOB,
– (8) Agent removes the blinding factor and reads his new cover name,
―The Crimson Streak.‖ The signed document gives him diplomatic
immunity under that name,
56
References
– FIPS PUB 186-2
