Masked digital signatures

• US 20010008013A1
• Filed: 02/02/2001
• Published: 07/12/2001
• Est. Priority Date: 11/10/1997
• Status: Active Grant

• Current Assignee: Certicom Corporation (Blackberry Limited)
• Original Assignee: Certicom Corporation (Blackberry Limited)
• Inventors: Johnson, Donald B., Vanstone, Scott A., Ou, Minghua
• Granted Patent: US 7,260,723 B2
• Time in Patent Office: Days
• US Class Current: 713/170
• CPC Class Codes: G06Q 20/341 Active cards, i.e. cards including their own processing means, e.g. including an IC or chip
• CPC Class Codes: G06Q 20/40975 using encryption therefor
• CPC Class Codes: G07F 7/1008 Active credit-cards provided with means to personalise their use, e.g. with PIN-introduction/comparison system
• CPC Class Codes: H04L 2209/04 Masking or blinding
• CPC Class Codes: H04L 9/3066 involving algebraic varieties, e.g. elliptic or hyper-elliptic curves
• CPC Class Codes: H04L 9/3247 involving digital signatures
• CPC Class Codes: H04L 9/3252 using DSA or related signature schemes, e.g. elliptic based signatures, ElGamal or Schnorr schemes

Abstract

The present invention relates to digital signature operations using public key schemes in a secure communications system and in particular for use with processors having limited computing power such as ‘smart cards’. This invention describes a method for creating and authenticating a digital signature comprising the steps of selecting a first session parameter k and generating a first short term public key derived from the session parameter k, computing a first signature component r derived from a first mathematical function using the short term public key, selecting a second session parameter t and computing a second signature component s derived from a second mathematical function using the second session parameter t and without using an inverse operation, computing a third signature component using the first and second session parameters and sending the signature components (s, r, c) as a masked digital signature to a receiver computer system. In the receiver computer system computing a recovered second signature component s'"'"' by combining a third signature component with the second signature component to derive signature components (s′, r) as an unmasked digital signature. Verifying these signature components as in a usual ElGamal or ECDSA type signature verification.

Claims

1. A method of signing and authenticating a message m in a public key data communication system, comprising the steps of:

in a secure computer system;

(a) generating a first short term private key k;

(b) computing a first short term public key derived from said first short term private key k;

(c) computing a first signature component r by using said first short term public key k;

(d) generating a second short term private key t;

(e) computing a second signature component s by using said second short term private key t on said message m, said long term private key and said first signature component r;

(f) computing a third signature component c using said first and second short term private keys t and k respectively, and sending said signature components (r, s, c) as a masked digital signature of said message m to a receiver computer system;

in said receiver system;

(g) using said second and third signature components (s, c) computing a normal signature component {overscore (s)} and sending said signature components ({overscore (s)}, r) as a normal digital signature to a receiver verifer computer system; and

in said verifier system

(h) verifying said normal signature.

2. A method as defined in

claim 1

, said first short term private key k is an integer and said first short term public key is derived by computing the value kP=(x₁,y₁) wherein P is a point of prime order n in E(Fq), wherein E is an elliptic curve defined over F_q.

3. A method as defined in

claim 2

, said first signature component r having a form defined by r={overscore (x)}(mod n) wherein {overscore (x)} is derived by converting said coordinate x₁ to an integer {overscore (x)}.

4. A method as defined in

claim 3

, said second short term private key being an integer selected such that 2≦

t ≦

(n−

2), and said second signature component being defined by s=t (e+dr) (mod n), wherein e is a hash of said message m.

5. A method as defined in

claim 4

, said third signature component being defined by c=tk(mod n).

6. A method as defined in

claim 5

, said normal signature component {overscore (s)} being defined by {overscore (s)}=c⁻

1s mod n.

7. A method of generating a digital signature S of a message in a data communication system, wherein the signor of the message has a private key d and a public key y derived from an element g and said private key d, said method comprising the steps of:

(a) generating a short term private key k;

(b) computing a first short term public key derived from said short term private key k;

(c) computing a first signature component r by using said first short term public key k;

(d) generating a second short term private key t;

(e) computing a second signature component s by using said second short term private key t on said message m, said long term private key and first signature component r;

(f) computing a third signature component c using said first and second short term private keys t and k respectively;

(g) sending said signature components (r, s, c) as a masked digital signature of said message m to a receiver computer system.

8. A method as defined in

claim 7

including the step of in said receiver computer system, using said second and third signature components (s, r) computing a normal signature component {overscore (s)}, and sending said signature components ({overscore (s)}, r ) as a normal digital signature to a verifier computer system, and verifying said normal signature (s, r) by said verifier system.

9. A method as defined in

claim 8

including the step of in said receiver system, using said second and third signature components (s, c) computing a normal signature component {overscore (s)}, to derive a normal digital signature components ({overscore (s)}, r) and;

verifying said normal signature components.

10. A processing means for assigning a message m without performing inversion operations and including a long term private key contained within a secure boundary and a long term public key derived from said private key and a generator of predetermined order in a field, said processing means comprising:

within said secure boundary;

means for generating a first short term private key;

means for generating a second short term private key;

means for generating a first signature component using at least said second short term session key; and

generating a masked signature component using said first and second short term session keys to produce masked signature components of said message m.

11. A processing means as defined in

claim 10

, including means for converting said signature components to a normal signature component;

and

means for transmitting said normal signature components to a recipient.