Small memory footprint fast elliptic encryption

A computer-implemented method of generating a digital signature, comprising:

• at an electronic device comprising one or more processors and a communications interface coupled to a challenger device:
• generating a first random number from a finite field of numbers;
• generating a plurality of field elements defining a first point on an elliptic curve defined over the finite field of numbers by performing elliptic curve arithmetic on the first random number and an initial public point on the elliptic curve;
• generating a product from a field element of the plurality of field elements, a private key, and a second random number from the finite field of numbers, wherein the second random number is received from the challenger device;
• generating a signature component by summing the product and the first random number;
• reducing the generated signature component using one or more modular reduction operations, wherein the one or more modular reduction operations are based on a modulus equal to an order of the elliptic curve;
• and
• sending the reduced signature component and the plurality of field elements to the challenger device as a digital signature for verification by the challenger device.

A computer-readable medium having stored thereon instructions, which, when executed by a processor in a system for generating a digital signature, causes the processor to perform the operations of:

• generating a first random number from a finite field of numbers;
• generating a plurality of field elements defining a first point on an elliptic curve defined over the finite field of numbers by performing elliptic curve arithmetic on the first random number and an initial public point on the elliptic curve;
• generating a product from a field element of the plurality of field elements, a private key, and a second random number from the finite field of numbers, wherein the second random number is received from a challenger device;
• generating a signature component by summing the product and the first random number;
• reducing the generated signature component using one or more modular reduction operations, wherein the one or more modular reduction operations are based on a modulus equal to an order of the elliptic curve;
• and
• sending the reduced signature component and the plurality of field elements to the challenger device as a digital signature for verification by the challenger device.