Patent ID: 8165285

Claim:
A process implemented in a crypto-coprocessor, the process using an elliptic curve represented in a plane by means of an equation containing first and second parameters (a, b), a bilinear pairing, and calculations in a finite group of integers constructed around a first reduction rule reducing each integer to a respective remainder in a whole division by a first prime number (p) that constitutes a third parameter, elements of the finite group being in bijection with points selected on the elliptic curve, and a quantity of which is linked to a fourth parameter (q), the process using public and private keys, each of which is represented by a given point of the elliptic curve or by a multiplication factor between two points of the elliptic curve, the process comprising: randomly generating a prime number as the fourth parameter (q); selecting, as a fifth parameter, an integer (d) that complies with constraints that are inherent in a complex multiplication with the form [u+v*root(−d)], where u and v are integers; randomly generating two extra integers (n, m); calculating an integer based on the fourth parameter (q), the integer (d) and the two extra integers (n, m); checking whether the calculated integer is a prime number; based on a result of the checking of the calculated integer, conditionally adopting the calculated integer as the third parameter (p); constructing the first and second parameters (a, b) by applying to the third parameter (p) a technique of complex multiplication by [u+v*root(−d)]; and obtaining the elliptic curve based on the constructed first and second parameters (a, b).