Accelerated verification of digital signatures and public keys

A cryptographic module operable to generate a digital signature of a message, the cryptographic module comprising one or more processors configured to:

• generate a digital signature comprising a first signature component and a second signature component, said first signature component based on a first coordinate of an elliptic curve point representing an ephemeral public key;
• and
• generate, for use with said digital signature, an indicator to identify which value of a plurality of values recoverable from said first signature component is said ephemeral public key.

A non-transitory computer readable medium storing instructions operable when executed by data processing apparatus to perform operations for generating a digital signature of a message, the operations comprising:

• generating a digital signature comprising a first signature component and a second signature component, said first signature component based on a first coordinate of an elliptic curve point representing an ephemeral public key;
• and
• generating, for use with said digital signature, an indicator to identify which value of a plurality of values recoverable from said first signature component is said ephemeral public key.