Incorporating data into an ECDSA signature component

1. A non-transitory computer-readable storage medium containing computer-executable instructions which, when executed by a processor, result in the processor:

selecting particular information [V A ] to be incorporated in a first signature component [r] of a signature on a message [M] to be signed;

performing an iterative process of generating the first signature component [r] and applying a known function [F] to the first signature component [r], wherein the iterative process is repeated until applying the known function [F] to the first signature component [r] extracts the particular information [V A ];

calculating a second signature component [s] of the signature from the first signature component [r], from a private key [k A ], from a private integer value [d A ], and from a message-dependent value that is dependent on the message [M]; and

forming a signed message from the first signature component [r], from the second signature component [s], and from one of the message [M] and the message- dependent value.

2. The non-transitory computer-readable storage medium as claimed in claim 1 , wherein the particular information [V A ] comprises information related to one or more of the message [M] and a signer of the message [M].

3. The non-transitory computer-readable storage medium as claimed in claim 1 , wherein the message- dependent value comprises a hash of the message [Hash(M)].

4. The non-transitory computer-readable storage medium as claimed in claim 1 , wherein the iterative process comprises:

selecting the private integer value [d A ] and computing a public value [R] from the private integer value [d A ] and from a generator [G] of a finite cyclic group such that the public value [R] is included in the finite cyclic group;

calculating the first signature component [r] from the public value [R]; and

determining whether applying the known function [F] to the first signature component [r] extracts the particular information [V A ].

5. The non-transitory computer-readable storage medium as claimed in claim 4 , wherein in the event that applying the known function [F] to the first signature component [r] does not result in the particular information [V A ], the computer-executable instructions further result in the processor:

selecting a new private integer value [new d A ] and computing a new public value [R] from the new private integer value [new d A ] and from the generator [G] of the finite cyclic group such that the new public value [new R] is included in the finite cyclic group;

calculating a new first signature component [new r] from the new public value [new R]; and

determining whether applying the known function [F] to the new first signature component [new r] extracts the particular information [V A ].

6. The non-transitory computer-readable storage medium as claimed in claim 4 , wherein in the event that applying the known function [F] to the first signature component [r] does not result in the particular information [V A ], the computer-executable instructions further result in the processor:

calculating an incremented private integer value [d A +c] as a sum of the private integer value [d A ] and a constant integer [c];

calculating an incremented public value [R+cG] as a sum of the public value [R] and a product of the constant integer [c] and the generator [G], wherein the incremented public value [R+cG] is included in the finite cyclic group; and

determining whether applying the known function [F] to the incremented public value [R+cG] extracts the particular information [V A ].

7. A non-transitory computer-readable storage medium containing computer-executable instructions which, when executed by a processor, result in the processor:

selecting particular information [V A ] to be incorporated in a second signature component [s] of a signature on a message [M] to be signed;

performing an iterative process of generating a first signature component [r] of the signature, calculating the second signature component [s] from the first signature component [r], from a private key [k A ], from a private integer value [d A ], and from a message-dependent value that is dependent on the message [M], and applying a known function [F] to the second signature component [s], wherein the iterative process is repeated until applying the known function [F] to the second signature component [s] extracts the particular information [V A ]; and

forming a signed message from the first signature component [r], from the second signature component [s], and from one of the message [M] and the message- dependent value.

8. The non-transitory computer-readable storage medium as claimed in claim 7 , wherein the particular information [V A ] comprises information related to one or more of the message [M] and a signer of the message [M].

9. The non-transitory computer-readable storage medium as claimed in claim 7 , wherein the message- dependent value comprises a hash of the message [Hash(M)].

10. The non-transitory computer-readable storage medium as claimed in claim 7 , wherein the iterative process comprises:

selecting the private integer value [d A ] and computing a public value [R] from the private integer value [d A ] and from a generator [G] of a finite cyclic group such that the public value [R] is included in the finite cyclic group;

calculating the first signature component [r] from the public value [R];

calculating the second signature component [s] from the first signature component [r], from the private key [kA], from the private integer value [d A ], and from the message-dependent value; and

determining whether applying the known function [F] to the second signature component [s] extracts the particular information [V A ].

11. The non-transitory computer-readable storage medium as claimed in claim 10 , wherein in the event that applying the known function [F] to the second signature component [s] does not result in the particular information [V A ], the computer-executable instructions further result in the processor:

selecting a new private integer value [new d A ] and computing a new public value [R] from the new private integer value [new d A ] and from the generator [G] of the finite cyclic group such that the new public value [new R] is included in the finite cyclic group;

calculating a new first signature component [new r] from the new public value [new R];

calculating a new second signature component [new s] from the new first signature component [new r], from the private key [k A ], from the private integer value [d A ] and from the message-dependent value; and

determining whether applying the known function [F] to the new second signature component [new s] extracts the particular information [V A ].

12. The non-transitory computer-readable storage medium as claimed in claim 10 , wherein in the event that applying the known function [F] to the second signature component [s] does not result in the particular information [V A ], the computer-executable instructions further result in the processor:

calculating an incremented private integer value [d A +c] as a sum of the private integer value [d A ] and a constant integer [c];

calculating an incremented public value [R+cG] as a sum of the public value [R] and a product of the constant integer [c] and the generator [G], wherein the incremented public value [R+cG] is included in the finite cyclic group;

calculating a new first signature component [new r] from the incremented public value [R+cG];

calculating a new second signature component [new s] from the new first signature component [new r], from the private key [k A ], from the private integer value [d A ] and from the message-dependent value; and

determining whether applying the known function [F] to the new second signature component [new s] extracts the particular information [V A ].

13. A non-transitory computer-readable storage medium containing computer-executable instructions which, when executed by a processor, result in the processor:

receiving a signed message purported to be signed by a signer, the signed message having been formed from a first signature component [r] of a signature, from a second signature component [s] of the signature, and from one of a message [M] and a hash of the message [Hash(M)], wherein Hash is a cryptographic hash function that was used by the signer to calculate the second signature component [s];

extracting the first signature component [r], the second signature component [s], and one of the message [M] and the hash of the message [Hash(M)];

applying a known function [F] to the first signature component [r] or to the second signature component [s] to extract information [V A ]; and

checking the validity of the extracted information [V A ] by:

calculating a first value [ul] and a second value [u2] using the equations

u 1 =Hash( M ) s −1 (mod n )

u 2 =rs −1 (mod n )

wherein s −1 is the inverse of the second signature component [s], wherein n is the smallest positive prime number such that a product of the prime number [n] and a generator [G] of a finite cyclic group is equal to a point at infinity [0], and wherein Hash(M) has been converted to an integer;

calculating a public value [R] of the signer using the equation

R =u 1 G+u 2 k a

wherein K A is a public key of the signer that forms a key pair with a private key [k A ] of the signer; and

comparing the first signature component [r] to R x (mod n), wherein R x is the residue of the x-coordinate of the public value [R] of the signer.

14. The non-transitory computer-readable storage medium as claimed in claim 13 , wherein the extracted information [V A ] comprises information related to one or more of the signer and the message [M].

15. The non-transitory computer-readable storage medium as claimed in claim 13 , wherein checking the validity of the extracted information [V A ] comprises:

checking whether the extracted information [V A ] complies with digital signature management roles accessible by the verifier.