Small memory footprint fast elliptic encryption
First Claim
1. A digital signature verification system, comprising:
- a processor;
a computer readable medium coupled to the processor and having stored thereon instructions, which, when executed by the processor, cause the processor to perform the operations of;
generating a first random number from a finite field of numbers;
sending the first random number to a signing device;
receiving a digital signature packet from the signing device including a first point on an elliptic curve defined over the finite field of numbers and a signature component, wherein the signature component is a function of the first random number and a second random number generated by the signing device;
generating a second point on the elliptic curve defined over the finite field of numbers by performing elliptic curve arithmetic on the signature component and an initial public point on the elliptic curve;
generating a product from the first random number and a field element of the first point;
reducing the product using one or more modular operations, wherein the one or more modular operations are based on a modulus equal to an order of the elliptic curve;
generating a third point on the elliptic curve defined over the finite field of numbers by performing elliptic curve arithmetic on the reduced product and a public point on the elliptic curve representing a public key of the signing device and distinct from the initial public point; and
evaluating an elliptic identity using the first, second and third points to produce a result indicative of either a positive or negative verification of the digital signature packet.
0 Assignments
0 Petitions
Accused Products
Abstract
A method of generating a digital signature includes generating a first random number from a finite field of numbers, and generating 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. The method continues by generating a product from a field element, a private key, and a second random number received from a challenger seeking verification of a digital signature, and generating a signature component by summing the product and the first random number. The signature component is reduced using one or more modular reduction operations, using a modulus equal to an order of the elliptic curve, and then the reduced signature component and the field elements are sent to the challenger as a digital signature for verification by the challenger.
-
Citations
22 Claims
-
1. A digital signature verification system, comprising:
-
a processor; a computer readable medium coupled to the processor and having stored thereon instructions, which, when executed by the processor, cause the processor to perform the operations of; generating a first random number from a finite field of numbers; sending the first random number to a signing device; receiving a digital signature packet from the signing device including a first point on an elliptic curve defined over the finite field of numbers and a signature component, wherein the signature component is a function of the first random number and a second random number generated by the signing device; generating a second point on the elliptic curve defined over the finite field of numbers by performing elliptic curve arithmetic on the signature component and an initial public point on the elliptic curve; generating a product from the first random number and a field element of the first point; reducing the product using one or more modular operations, wherein the one or more modular operations are based on a modulus equal to an order of the elliptic curve; generating a third point on the elliptic curve defined over the finite field of numbers by performing elliptic curve arithmetic on the reduced product and a public point on the elliptic curve representing a public key of the signing device and distinct from the initial public point; and evaluating an elliptic identity using the first, second and third points to produce a result indicative of either a positive or negative verification of the digital signature packet. - View Dependent Claims (2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20)
-
-
21. A computer-implemented method of verifying a digital signature, comprising:
-
at an electronic device comprising one or more processors and a communications interface coupled to a signing device; generating a first random number from a finite field of numbers; sending the first random number to a signing device; receiving a digital signature packet from a signing device including a first point on an elliptic curve defined over the finite field of numbers and a signature component, wherein the signature component is a function of the first random number and a second random number generated by the signing device; generating a second point on the elliptic curve defined over the finite field of numbers by performing elliptic curve arithmetic on the signature component and an initial public point on the elliptic curve; generating a product from the first random number and a field element of the first point; reducing the product using one or more modular operations, wherein the one or more modular operations are based on a modulus equal to an order of the elliptic curve; generating a third point on the elliptic curve defined over the finite field of numbers by performing elliptic curve arithmetic on the reduced product and a public point on the elliptic curve representing a public key of the signing device and distinct from the initial public point; and evaluating an elliptic identity using the first, second and third points to produce a result indicative of either a positive or negative verification of the digital signature packet.
-
-
22. A computer-readable medium having stored thereon instructions, which, when executed by a processor in a system for generating a digital signature, cause the processor to perform the operations of:
-
generating a first random number from a finite field of numbers; sending the first random number to a signing device; receiving a digital signature packet from a signing device including a first point on an elliptic curve defined over the finite field of numbers and a signature component, wherein the signature component is a function of the first random number and a second random number generated by the signing device; generating a second point on the elliptic curve defined over the finite field of numbers by performing elliptic curve arithmetic on the signature component and an initial public point on the elliptic curve; generating a product from the first random number and a field element of the first point; reducing the product using one or more modular operations, wherein the one or more modular operations are based on a modulus equal to an order of the elliptic curve; generating a third point on the elliptic curve defined over the finite field of numbers by performing elliptic curve arithmetic on the reduced product and a public point on the elliptic curve representing a public key of the signing device and distinct from the initial public point; and evaluating an elliptic identity using the first, second and third points to produce a result indicative of either a positive or negative verification of the digital signature packet.
-
Specification