Project URL: http://github.com/seb-m/wcurve
This package implements basic arithmetic operations such as point addition and single-scalar multiplication on elliptic curves in short Weiertsrass form.
Example:
import wcurve, random
# Instantiate secp256r1 aka nistp256r1 standardized curve
curve = wcurve.secp256r1_curve()
# Generate a new secret value
sk = random.SystemRandom().randint(1, curve.n - 1)
# Compute the public key associated with the previous secret
pk = sk * curve.base_point
# Get its affine coordinates
pkx, pky = pk.to_affine()
Internally, curve points are represented in Jacobian coordinates. There’s currently no optimized implementation for the double scalar multiplication operation, it is merely the addition of two independents single-scalar multiplications.
The primary goal of this code is to keep things simple and offer a pure Python standalone interface to some of currently the most used curves.
As implemented, single-scalar multiplications are not protected against DPA and some types of fault attacks. However, exponentiations algorithms are regulars, without dummy operations and conditional branching instructions are avoided.
Beside the usual scalar multiplication algorithm transparently used when secp256r1_curve() is instantiated, another algorithm is implemented. This one uses infective computations techniques [2] to prevent an attacker from extracting useful information from a wrong scalar-multiplication result. This algorithm is automatically used when a secp256r1_curve_infective() curve is instantiated. For more details on infective computations read the docstring of JacobianPoint.scalar_multiplication_infective().
Note
functions, classes and methods prefixed with _ in the source code are privates to this module, there are not intended to be called from external client code.
Factory function returning a secp256r1 curve (as defined in this file). This _Curve object can be manipulated as a singleton and can be reused with different points.
It also provides useful attributes:
curve = wcurve.secp256r1_curve()
# Base point (instance of JacobianPoint)
curve.base_point
# Base point's order
curve.n
# Curve parameters and cofactor
curve.a
curve.b
curve.h
It will use JacobianPoint.scalar_multiplication() as scalar multiplication algorithm.
This curve uses auxiliary curves to ensure scalar multiplication’s result is either mathematically correct or otherwise returns a wrong result disclosing no useful information [2].
It will use JacobianPoint.scalar_multiplication_infective() as scalar multiplication algorithm.
Example:
curve = wcurve.secp256r1_curve_infective()
sk = random.SystemRandom().randint(1, curve.n - 1)
# This scalar-multiplication introduces extra-computations with
# noticeable computational costs.
pk1 = sk * curve.base_point
# pk1 expected to be the same than as if it had been computed with the
# usual algorithm.
pk2 = curve.base_point.scalar_multiplication(sk)
assert pk1 == pk2
The object instantiated and returned is a _Curve object which can be manipulated as a singleton and be reused with different points. It also provides useful attributes, see docstring of secp256r1_curve().
Point representation in Jacobian coordinates. It uses Co-Z arithmetic [1] to compute operations between curve points.
Adds up together this point with another point and returns the result.
Very inefficient algorithm when used for double scalar multiplication, the only upside in this case is that it is formed of regular operations. Additions with identity points are handled as special cases.
Usually points are public elements (at least in the algorithms I know) therefore we’re being slightly less careful in how we are manipulating and comparing them.
Returns True when the two points are equals. The compared points might have to be modified in-place in order to obtain an equivalent representation facilitating their comparison.
x, y, z are the Jacobian coordinates of this point, curve is the underlying/associated curve. curve must be a valid curve, it is the responsability of the caller to provide a valid and secure curve. curve is usually an instance of _Curve.
Returns scalar * self with self representing this point.
The choice of the underlying scalar multiplication algorithm will depend on the instantiated curve type. If the curve supports infective computations it will call scalar_multiplication_infective() otherwise it will call scalar_multiplication().
Example:
curve = wcurve.secp256r1_curve()
# Will internally call scalar_multiplication()
p = 42 * curve.base_point
curve = wcurve.secp256r1_curve_infective()
# Will internally call scalar_multiplication_infective()
p = 42 * curve.base_point
Returns the point (x, -y, z) or an unmodified copy if the point is the point at infinity.
Transform this point to an equivalent and unique representative taking 1 as z coordinate in (x : y : 1) when the point is not at infinity and taking x, y as 1 in (1 : 1 : 0) when the point is at infinity. This method is used for faciliting points comparisons and to convert a point to its affine representation. Before any transformation takes place this method checks that the point is on the curve.
Return the compression bit odd(y) associated to the y coordinate. Does not work for the point at infinity. See example in uncompress().
Returns a new JacobianPoint from affine coordinates x, y, curve is an instance of _Curve, see __init__() for more details.
Returns the affine coordinate x of this point.
Returns the affine coordinate y of this point.
Returns True if the order of this point is the same than the order of the base point. This method is a step of the validation performed by is_valid().
Returns True if this point is at infinity. This method is part of the validation done by is_valid().
Returns True if this point is on curve. This method is a step of the validation performed by is_valid().
Returns True if this point is valid.
It checks that this point P meets the following requirements:
This method does the scalar multiplication of the submitted scalar with the current point. The scalar value is used as is, it is not randomized, it is not reduced mod n. Before the computation this point is validated through is_valid() and at the end the final result must verify is_on_curve(). If any validation step fails, a ValueError exception is immediately raised. The result is only guaranteed to be a point on the curve, which of course doesn’t ensure the computations were correct.
There is nothing that prevent the use of first two Coron‘s DPA countermeasures (prior to the call of this method).
Restrictions: scalar * infinity is not permitted.
This scalar multiplication implicitly checks the correctness of its result and uses infective computations to propagate an eventual unexpected error and return in this case an harmless wrong result.
This implementation follows the Algorithm 8 presented at section 4 of [2] by Blomer and al. and it also implements infective computations techniques as presented by the modified version of this algorithm introduced at the end of section 4.1.
See function secp256r1_curve_infective() for more details and for an example. Also read comments in scalar_multiplication() it mostly remain valid for this method as well.
Convert this point to its affine representation (x/z2, y/z3). Does not work for point at infinity.
Uncompress and construct the Jacobian point represented by x and bit_y. See compression_bit_y() for how bit_y was initially obtained. curve’s order must be a congruent of 3 mod 4.
Example:
curve = wcurve.secp256r1_curve()
bit_y = curve.base_point.compression_bit_y()
# p is a copy of the base point curve.base_point
p = wcurve.JacobianPoint.uncompress(curve.base_point.x, bit_y, curve)