Efficient Signature Generation by Smart Cards

Efficient Signature Generation by Smart Cards 20103112 Suk Ki Kim 20103114 Sunyeong Kim

Contents 1. Introduction 2. What is the problem in RSA 3. ESG Feature 4. Key Authentication Center 5. Introduce existing Chaum 6. Minimizing the Number of Communication Bits 7. Comparison Chaum and ESG 8. Signature Generation / Verification 9. Efficiency 10. Hash Function h 11. Performance Analyze 12. Preprocessing

1. Introduction Writer : C.P.Schnorr (Universitat Frankfurt) This paper presents an efficient algorithm for generating public-key signatures which is particularly suited for interactions between smart cards and terminals. This paper presents a new public-key signature scheme and a corresponding authentication scheme that are based on discrete logarithms.

2. What is the problem in RSA = ed mod M n M = e mod C M n = d mod M C n 1. Computation amount is message dependent! 2. Require many modular multiplications

3. ESG Feature 1. minimizes the message-dependent amount of computation. 2. signature generation can be done during the idle time of the processor. 3. The length of signatures is about 212 bits, it is less than half of the length of RSA signatures.

4. Key Authentication Center Key Authentication Center(KAC) Chooses Primes p and q such that, with order q, A one-way hash function h: Its own private and public key The KAC publishes p,q, , h and its public key. 140 512 2 , 2 q p Z = Z q (mod 1 ), 1 0 { p p } 1 t ,..., 2 Z p

4. Key Authentication Center Name, Address, ID number, Etc Register request KAC KAC verifies its identity Generates an identification number I and generates a Signatures S for the pair (I,v) consisting of I and the user s public key v. User A user generates by himself a private key s which is a random number in {1,2, ,q}. The corresponding public key v is the number = s (mod p ) v

5. Introduce existing chaum Prover A Verifier B A picks a random number } 1 1 { ,..., r q and computes I,v,S,x = r : (mod ) x p Verifies the signatures S and sends a random number e e } 1 t ,..., 0 { 2 y := r + se(mod q) y = y e (mod p ) x v The Authentication protocol

5. Introduce existing chaum A fraudulent A can cheat by guessing the correct e v x = (mod : = : r e ), p y r t 2 The probability of success for this attack is

6. Minimizing the Number of Communication Bits Prover A Verifier B A picks a random number 1 { } 1 I,v,S ,..., r q and computes = r : (mod ) x p h(x) Verifies the signatures S and sends a random number e e } 1 t ,..., 0 { 2 y := r + se(mod q) y = y e (mod p ) x v Check that h(x) = ( ) x h The Authentication protocol

7. Comparison Chaum and ESG I,v,S,x I,v,S h(x) e y e y : = 512 rmod 2 x p p , } 1 t ,..., 0 { 2 Z Z A one-way hash function h: p + + + = v + + + ( , , ) 512 140 I Q ( , , ) 140 Q I v S t Q I v S t t + = + ( , , ) 724 ( , , ) 284 Q I v S S

8. Signature Generation / Verification , q, p, h Message m I, v, (S) I, s, v, (S) Check I, v, (S) Pick random r = r : (mod ) x p e = : ( , ) h x m e : t bits, y : 140 bits = y e : (mod e= ) , x v p x = + : (mod ) y r se q ( m ) Check that h Signature Generation Signature Verification

9. Efficiency Signature Generation Preprocessing Compute se (mod q) (from e = r + se (moe q)) Signature Verification 25 . 0 5 . 1 l + ) = ( log t l 2q

10. Hash Function h Possible Attack I Given a Message m find a signature for m collision-free for x Uniform with respect to x x e m x h ob = = ] ) , ( [ Pr t 2 t ) } 1 ( , 0 { ... 2 , e Uniformly distributed : 2tstep for attacking

10. Hash Function h (contd) Possible Attack II Chosen message attack. Sign an unsigned message m of your choice. One-way in the argument m If not, the probability of attack success = 1 depend on 140 bits of x

10. Hash Function h (contd) About Message m Not necessary collision-free H(x,m) = h(x, m ) Signature for m = x Can t use to sign m

11. Performance Analyze Number of multiplications New Scheme t=27 Fiat- Shamir k=9, t=8 RSA GQ Signature generation (without preprocessing) Preprocessing Signature verification 0 44 750 180 210 228 0 44 0 >2 0 180

12. Preprocessing During idle time An exponentiation random number (xi,ri) Initialize by KAC Use random combination pair ... r of a (mod p } q ) r { , 1 r ,

12. Preprocessing Algorithm Each smart cards have own algorithm Example algorithm Initiation. Load ri,xifor i = 1, ,k, := 1 1. pick a random permutation a of {1, ,k} 2. r := r +2r -1(mod q), x := x x -12(mod p), u := r, z := x 3. for i = k, ,1 do {u := ra(i)+ 2u (mod q), z := xa(i)z2 (mod p) 4. r := u, x := z, := +1 (mod k), go to 1 for the nest round + + 2 k 2 k = = 1 i = 2 a = 1 i : (mod ) x x p r : 2 (mod ) r q Finally, , ( ) i ( ) a i 1 i 1 i (Quasi-independent form the old pairs.)

Reference Chaum, D.,Evertse, J.H. and van de Graaf, J, An Improved Protocol For Demonstrating Possession of Discrete Logarithms and Some Generalizations , Advanced in Cryptology, EUROCRYPT 87. Lecture Notes in Computer Science 304 (1988). Pp. 127-141 Kevin S.M., The Discrete Logarithm Problem , Proceedings of Symposia in Applied Mathematics Volume 42, 1990 H. Cohen, A Course in Computational Algebraic Number Theory , Springer, 1996.

Q & A