Public key cryptographic system using elliptic curves over rings

Abstract

The cryptographic system comprises at least one encryption station, one decryption station and a trapdoor generator. The trapdoor generator comprises means for selecting r distinct prime numbers pi, generating a modulus m that is a product of the prime numbers pi, selecting a pair of integers (a,b) satisfying 0.ltoreq.a<m and 0.ltoreq.b<m, computing for each pi a number N(pi) of distinct pairs of integers (x,y) satisfying 0.ltoreq.x<pi and 0.ltoreq.y<pi and y.sup.2 .ident.x.sup.3 +a.multidot.x+b (mod pi) and a sum N(pi)+1 representative of an order of an elliptic curve defined as the set of pairs of integers (x,y), computing a least common multiple .mu. of the values N(pi)+1, selecting a public multiplier e relatively prime to .mu., computing a secret multiplier d according to d.ident.1/e (mod .mu.), and transferring data comprising at least m, a, b and e to a storage means provided in the cryptographic system. Alternatively, the trapdoor generator comprises means for selecting r distinct prime numers pi each corresponding to a sum value (pi+1) that satisfies (pi+1).ident.0 (mod j) wherein 1.ltoreq.i.ltoreq.r and j is 3 or 4, generating a modulus m that is a product of the prime numbers pi, computing the least common multiple .mu. of the numbers (pi+1), selecting a public multiplier e relatively prime to .mu., computing a secret multiplier d according to d.ident.1/e (mod .mu.), and transferring data comprising at least m and e to a corresponding storage means provided in the cryptographic system.

Dependencies are inferred from the claim text.