Patent ID: 6697946
Filing Date: 2004-02-24
Classification: H04L

Abstract:
A message recovery signature apparatus for signing a message m with a secret key xA using a discrete logarithm problem as a basis for security, based on operations performed on a finite field GF(p) where p is a prime number and g is an element whose order is q, the message recovery signature apparatus comprising:random number generating means for generating a random number k; commitment generating means for generating a commitment r1 from the random number k according to a function f11(k)=gk; message masking means for generating a masked message r2 from the commitment r1 and the message m according to a function f12(r1,m) that maps GF(p)Ã—GF(p) into the finite field GF(p); and signature generating means for generating a signature s from the masked message r2 and the secret key xA according to a function f13(r2xA)=s, wherein r2â€²=r2(mod q) and satisfies ha(r2â€²,s,1)k=hb(r2â€²,s,1)+hc(r2â€²,s,1)xA(mod q) wherein the functions ha(r2â€²,s,1), hb(r2â€²,s,1), and hc(r2â€²,s,1) define a mapping from ZqÃ—ZqÃ—Zq into Zq where Zq={0, 1, . . . , qâˆ’1}, and when r2â€² and s are elements of Zq, the functions ha(r2â€²,s,1), hb(r2â€²,s,1), and hc(r2â€²,s,1) satisfy conditions (1) and (2): (1) if ha(r2â€²,s,1)=ha(rr2â€²,ss,1) and hc(r2â€²,ss,1)=hc(rr2â€²,ss,1), then hb(r2â€²,s,1)âˆ’ha(r2â€²,s,1)â‰ hb(rr2â€²,ss,1) (2) if ha(r2â€²,s,1)=ha(rr2â€²,ss,1) and hb(r2â€²,s,1)=hb(rr2â€²,ss,1), then hc(r2â€²,s,1)âˆ’ha(r2â€²,s,1)â‰ hc(rr2,ss,1) for every rr2â€² and ss except predetermined values, the message recovery signature apparatus being characterized by f12(r1,m)=r1+m.