ElGamal signature schemes

1. A computing device implemented method for implementing a digital signature operation in place of a signing equation specified by a digital signature protocol, based on an underlying group, applied to a message, the method being performed by a correspondent computing device having a processing unit and memory storing a long-term private key, said protocol specifying a digital signature having a first signature component and a second signature component, said second signature component defined to be calculated by direct multiplication of said long term private key with another value, the method comprising:

(a) the processing unit obtaining an ephemeral private key and deriving said first signature component using said ephemeral private key; and

(b) the processing unit generating the second signature component by performing operations comprising:

(i) calculating a first value, said calculating based on said message and including a multiplication with an inverse of said other value;

(ii) obtaining said long-term private key from the memory and performing a single additive operation, said additive operation being one of an addition and a subtraction, on said long-term private key to combine said long-term private key with said first value to obtain a masked value;

(iii) deriving a second value based on said other value; and,

(iv) multiplying said masked value with said second value to obtain said second signature component,

wherein a value of said second signature component is equivalent to a value calculated by direct multiplication of said long term private key with said other value.

2. The method of claim 1 wherein said second value is also derived using said ephemeral private key.

3. The method of claim 2 wherein said first value has the form h(m)r −1 (mod n), said masked value has the form h(m)r −1 +d(mod n), said second value has the form k −1 r(mod n), and said second signature component is calculated as k −1 r(h(m)r −1 +d)(mod n); wherein m is said message, r is said first signature component, k is said ephemeral private key, d is said long-term private key, h( ) represents a cryptographic hash function, and n is the order of said underlying group.

4. The method of claim 3 wherein said underlying group is an elliptic curve group, and said digital signature is verifiable using an Elliptic Curve Digital Signature Algorithm (ECDSA) verification protocol.

5. The method of claim 2 wherein said first value has the form ke −1 (mod q), where e=h(m∥r), said masked value has the form d+ke −1 (mod q), said second value has the form e and said second signature component is calculated as s=e(d+ke −1 )(mod q); wherein m is said message, e is said first signature component, k is said ephemeral private key, d is said long-term private key, h( ) represents a cryptographic hash function, and q is the order of the underlying group.

6. The method of claim 2 wherein said first value has the form h(m)r −1 (mod(p−1)), said masked value has the form h(m)r −1 −d(mod(p−1)), said second value has the form k −1 r(mod(p−1)), and said second signature component is calculated as s=k −1 r(h(m)r −1 −d) (mod(p−1)); wherein m is said message, r is said first signature component, k is said ephemeral private key, d is said long-term private key, h( ) represents a cryptographic hash function and p is a prime number.

7. The method of claim 2 wherein said first value has the form kr −1 h(m) (mod(p−1)), said masked value has the form d+kr −1 h(m)(mod(p−1)), said second value has the form r, and said second signature component is calculated as s=r(d+kr −1 h(m))(mod(p−1)); wherein m is said message, r is said first signature component, k is said ephemeral private key, d is said long-term private key, h( ) represents a cryptographic hash function, and p is a prime number.

8. The method of claim 2 wherein said first value has the form h(m)h(r) −1 (mod n), said masked value has the form h(m)h(r) −1 −d(mod n), said second value has the form k −1 h(r)(mod n), and said second signature component is calculated as s=k −1 h(r)(h(m)h(r) −1 −d) (mod n); wherein m is said message, r is said first signature component, k is said ephemeral private key, d is said long-term private key, h( ) represents a cryptographic hash function, and n is the order of the underlying group.

9. The method of claim 2 wherein said first value has the form k(R(m)r) −1 (mod q), said masked value has the form d+k(R(m)r) −1 (mod q), said second value has the form R(m)r(mod q), and said second signature component is calculated as s=R(m)r(d+k(R(m)r) −1 ) (mod q), where m is said message, R(m)r=e is said first signature component, e=h(m∥r), k is said ephemeral private key, d is said long-term private key, h( ) represents a cryptographic hash function, q divides p−1, and p is a prime integer.

10. The method of claim 1 wherein said first value has the form krh(m) −1 (mod(p−1)), said masked value has the form d+krh(m) −1 (mod(p−1)), said second value has the form h(m), and said second signature component is calculated as s=h(m)(d+krh(m) −1 )(mod(p−1); wherein m is said message, r is said first signature component, k is said ephemeral private key, d is said long-term private key, h( ) represents a cryptographic hash function, and p is a prime number.

11. The method of claim 1 wherein said ephemeral private key comprises a random value generated by a random number generator in said correspondent.

12. The method of claim 1 wherein the operation of multiplying said masked value with said second value is performed using a Montgomery ladder.

13. A computing device comprising a processor and memory, said computing device adapted to perform the method of claim 1 .

14. A non-transitory computer readable medium having stored thereon computer readable instructions for performing the method of claim 1 .

15. The method of claim 9 wherein r=(a k mod p)mod q.