Efficient point verification for semi-static elliptic curve diffie-hellman authentication protocols
AssigneeNXP B.V.
InventorsMario Lamberger, Bruce Murray
Life of this patent
Estimating the term…
Abstract
An elliptic curve point validation method, comprising: receiving a standard projective X and Z coordinate on an elliptic curve; computing X·Z; inverting X·Z to get (XZ)−1; multiplying Z2, (XZ)−1, and a constant √{square root over (b)} resulting in √{square root over (b)}·x−1, where b is a constant of the elliptic curve; multiplying X2 and (XZ)−1 resulting in x; computing Tr(x) and checking that it has a value of 1, where Tr(⋅) is a trace of Frobenius map that maps an input to a value of 0 or 1; computing Tr(√{square root over (b)}x−1) and checking that it has a value of 0; and outputting x and a PointOnCurve value, where the PointOnCurve value indicates whether x is on the elliptic curve.
Claims20
An elliptic curve point validation method, comprising:
- receiving a standard projective X and Z coordinate on an elliptic curve;
- computing X·Z;
- inverting X·Z to get (XZ)−1;
- multiplying Z2, (XZ)−1, and a constant VT resulting in √{square root over (b)}·x−1, where b is a constant of the elliptic curve;
- multiplying X2 and (XZ)−1 resulting in x;
- computing Tr(x) and checking that it has a value of 1, where Tr(⋅) is a trace of Frobenius map that maps an input to a value of 0 or 1;
- computing Tr(√{square root over (b)}x−1) and checking that it has a value of 0;
- and
- outputting x and a PointOnCurve value, where the PointOnCurve value indicates whether x is on the elliptic curve.
A data processing system comprising instructions embodied in a non-transitory computer readable medium, the instructions for an elliptic curve point validation method based on an elliptic curve in a processor, the instructions, comprising:
- receiving a projective X and Z coordinate on the elliptic curve;
- computing X·Z;
- inverting X·Z to get (XZ)−1;
- multiplying Z2, (XZ)−1, and a constant VT resulting in √{square root over (b)}·x−1, where b is a constant of the elliptic curve;
- multiplying X2 and (XZ)−1 resulting in x;
- computing Tr(x) and checking that it has a value of 1, where Tr(⋅) is a trace of Frobenius map that maps an input to a value of 0 or 1;
- computing Tr(√{square root over (b)}x−1) and checking that it has a value of 0;
- and
- output x and a PointOnCurve value, where the PointOnCurve value indicates whether x is on the elliptic curve.
An elliptic curve point validation method, comprising:
- receiving a Jacobian projective X and Z coordinate on an elliptic curve;
- computing (X·Z)2;
- inverting (X·Z)2 to get (XZ)−2;
- multiplying X3 and (XZ)−2 resulting in x;
- multiplying Z4 and (XZ)−2 to get Z2·X−2;
- multiplying Z2·X−2 with X and a constant √{square root over (b)} resulting in √{square root over (b)}·x−1, where b is a constant of the elliptic curve;
- computing Tr(x) and checking that it has a value of 1, where Tr(⋅) is a trace of Frobenius map that maps an input to a value of 0 or 1;
- computing Tr(√{square root over (b)}x−1) and checking that it has a value of 0;
- and
- outputting x and a PointOnCurve value, where the PointOnCurve value indicates whether x is on the elliptic curve.
A data processing system comprising instructions embodied in a non-transitory computer
- receiving a projective X and Z coordinate on an elliptic curve;
- computing (X·Z)2;
- inverting (X·Z)2 to get (XZ)−2;
- multiplying X3 and (XZ)−2 resulting in x;
- multiplying Z4 and (XZ)−2 to get Z2·X−2;
- multiplying Z2·X−2 with X and a constant √{square root over (b)} resulting in √{square root over (b)}·x−1, where b is a constant of the elliptic curve;
- computing Tr(x) and checking that it has a value of 1, where Tr(⋅) is a trace of Frobenius map that maps an input to a value of 0 or 1;
- computing Tr(√{square root over (b)}x−1) and checking that it has a value of 0;
- and
- outputting x and a PointOnCurve value, where the PointOnCurve value indicates whether x is on the elliptic curve.
Dependencies are inferred from the claim text.