Patent ID: 8750499

Claim:
A cryptographic method of a type with a public key over a non-supersingular elliptic curve E, determined by the simplified Weirstrass equation y 2 =x 3 +a·x 2 +b over a finite field GF(3 n ), with n being an integer greater than or equal to 1, the method comprising the following steps performed by an electronic device: associating an element t of said finite field with a point P′ of the elliptic curve, wherein associating comprises: obtaining a pre-determined quadratic non-residue η on GF(3 n ); obtaining a pre-determined point P=(z P , y P ) belonging to a conic C defined by the following equation: a·η·z 2 −y 2 +b=0; obtaining a point Q=(z Q , y Q ), distinct from the point P belonging to the conic C and a straight line D defined by the following equation: y=t·z+y P −t·z P ; obtaining the element ξ of GF(3 n ) verifying the following linear equation over GF(3): −η·ξ=(η 2 ·z Q )/a; and associating, with the element t of the finite field, the point P′ of the elliptic curve, for which the coordinates are defined by the pair (η·z Q /ξ, y Q ). using a hash function on a message m represented by a sequence of bits to produce a hashed message; and converting the hashed message into said element t of the finite field on which the elliptic curve is defined.