Cryptographic method

Abstract

A cryptographic method including selecting secret keys p and q, being prime numbers greater than 3, selecting public parameters for a series of data values which belong to one of a plurality of pairs of groups whereby any one of the data values in one of the pairs of groups is recovered by performing an operation kN.sub.i +1 times modulo n beginning with the any one of the data values, where k is an integer, N.sub.i is the order of the ith pair of groups and n=p.q, selecting a public encryption key e which is a factor of kN.sub.i +1 for all i, and processing communications data as a member of one of the pairs of groups by performing the operation on the communications data, whereby the order N.sub.i of the pair of groups i that the communications data belongs to can be determined on the basis of p and q, and a secret decryption key d.sub.i can be determined using e.d.sub.i =kN.sub.i +1.

Claims

I claim:

1. A cryptographic method including:

selecting secret keys p and q, being prime numbers greater than 3;

selecting public parameters for a series of data values which belong to one of a plurality of pairs of groups whereby any one of said data values in one of said pairs of groups is recovered by performing an operation kN.sub.i +1 times modulo n beginning with said any one of said data values, where k is an integer, N.sub.i is the order of the ith pair of groups and n=p.q;

selecting a public encryption key e which is a factor of kN.sub.i +1 for all i; and

processing communications data as a member of one of said pairs of groups by performing said operation on said communications data, whereby the order N.sub.i of the pair of groups i that said communications data belongs to can be determined on the basis of p and q, and a secret decryption key d.sub.i can be determined using e.d.sub.i =kN.sub.i +1.

2. A cryptographic method as claimed in claim 1, including encrypting message data having a data value x to obtain ciphertext s by performing said operation e times on x.

3. A cryptographic method as claimed in claim 1, including decrypting ciphertext having a data value s by determining which one of said pairs of groups s belongs to and N.sub.i and d.sub.i for said one of said pairs of groups on the basis of e, p, q and said public parameters, and performing said operation d.sub.i times on s.

4. A cryptographic method as claimed in claim 1, including obtaining a digital signature, on message data having a data value x by determining which one of said pairs of groups x belongs to and N.sub.i and d.sub.i for said one of said pairs of groups on the basis of e, p and q and said public parameters, and performing said operation d.sub.i times on x.

5. A cryptographic method as claimed in claim 1, including verifying a digital signature having a data value s by performing said operation e times to obtain plaintext.

6. A cryptographic method as claimed in claim 3, wherein only said ciphertext s, said public parameters and p and q are required to determine said one of said pairs of groups.

7. A cryptographic method as claimed in claim 4, wherein only said message data x, said public parameters and p and q are required to determine said one of said pairs of groups.

8. A cryptographic method as claimed in claim 1, wherein said pairs of groups include complementary groups which include indeterminate data values.

9. A cryptographic method as claimed in claim 1, wherein said parameters are parameters of curve and said data values represent points on said curve.

10. A cryptographic method as claimed in claim 9, wherein said curve is elliptic.

11. A cryptographic method as claimed in claim 10, wherein said curve includes said points (x,y) such that

y.sup.2 =x.sup.3 +ax+b(mod n)

where a and b are said public parameters and gcd (4a.sup.3 +27b.sup.2, n)=1, and said data values represent x coordinates.

12. A cryptographic method as claimed in claim 11, wherein said operation is a point multiplication on said curve denoted by the symbol #, such that

(x,y)#{kN.sub.i +1}.ident.(x,y)#e.d.sub.i .ident.(x,y)(mod n).

13. A cryptographic method as claimed in claim 12, wherein y may be indeterminate and equal u.sqroot.v where u is an integer and v is a fixed quadratic non-residue.

14. A cryptographic method as claimed in claim 13, wherein for a point (s,t) obtained by performing said operation on a point (x,y), (s,t) belongs to one of four of said pairs of groups, i equal to 1, 2, 3 or 4, where ##EQU13## .alpha. and .beta. being constants such that let .vertline..alpha..vertline..ltoreq.2.sqroot.p and .vertline..beta..vertline..ltoreq.2.sqroot.q and ##EQU14## being the Legendre symbol, whereby said one of said pairs of groups has an order N.sub.1, N.sub.2, N.sub.3 or N.sub.4 and corresponding decryption key d.sub.1, d.sub.2, d.sub.3 or d.sub.4, respectively.

15. A cryptographic method as claimed in claim 14, including encrypting plaintext having a data value x to obtain ciphertext s by performing the following

(s,t).ident.(x,y)#e(mod n).

16. A cryptographic method as claimed in claim 14, including decrypting ciphertext having a data value s to obtain plaintext x by performing the following

(x,y).ident.(s,t)#d.sub.i (mod n).

17. A cryptographic method as claimed in claim 14, including obtaining a digital signature having data value s on plaintext x by performing the following

(s,t).ident.(x,y)#d.sub.i (mod n)

and substituting z for w to determine N.sub.i and d.sub.i.

18. A cryptographic method as claimed in claim 14, including verifying a digital signature having a data value s to obtain plaintext x by performing the following

(x,y).ident.(s,t)#e(mod n).

19. A cryptographic method as claimed in claim 14, wherein x=X/Z (mod n) and y=Y/Z (mod n) and (x.sub.j, y.sub.j).ident.(X.sub.j /Z.sub.j, Y.sub.j, Z.sub.j (X/Z, Y/Z)#j(mod n), and points in said groups are obtained using the following

X.sub.2j .ident.(X.sub.j.sup.2 -aZ.sub.j.sup.2).sup.2 -8bX.sub.j Z.sub.j.sup.3 ( mod n)

Z.sub.2j .ident.4Z.sub.j (X.sub.j.sup.3 +aX.sub.j Z.sub.j.sup.2 +bZ.sub.j.sup.3) (mod n)

X.sub.2j+1 .ident.Z[4bZ.sub.j.sup.2 Z.sup.2.sub.j+1 +2(aZ.sub.j Z.sub.j+1 +X.sub.j X.sub.j+1) (X.sub.j Z.sub.j+1 +X.sub.j+1 Z.sub.j)]-X(X.sub.j Z.sub.j+1 -X.sub.j+1 Z.sub.j).sup.2 (mod n)

Z.sub.2j+1 .ident.Z(X.sub.j Z.sub.j+1 -X.sub.j+1 Z.sub.j).sup.2 (mod n).

20.

20. A cryptographic method as claimed in claim 19, including encrypting plaintext having a data value x to obtain ciphertext s using the following

s.ident.x.sub.e .ident.X.sub.e /Z.sub.e (mod n)

where X=x and Z=1.

21. A cryptographic method as claimed in claim 19, including decrypting ciphertext having a data value s to obtain plaintext x using the following

x.ident.s.sub.di S.sub.di Z.sub.di (mod n)

where S=s, Z=1.

22. A cryptographic method as claimed in claim 19, including generating a digital signature having a data value s from plaintext x using the following

s.ident.X.sub.di /Z.sub.di (mod n)

where X=x, Z=1 and to determine N.sub.i and d.sub.i, z is substituted for w.

23. A cryptographic method as claimed in claim 19, including verifying a digital signature having a data value s to obtain plaintext x by performing the following:

x.ident.S.sub.e /Z.sub.e (mod n)

where S=s and Z=1.

Description

The present invention relates to cryptology and, in particular, to a cryptographic method which can be used for public key encryption and to produce digital signatures.

Cryptographic techniques have become of significant practical importance in the area of digital communications, particularly with the increasing prevalence of digital telecommunications networks. Development has concentrated on schemes which allow message data, often referred to as plaintext, to be encrypted using a key which is available to the public, to produce ciphertext which can only be decrypted using a secret key that is related to the public key but which cannot be derived therefrom. Schemes of this nature were first discussed in W. Diffie and M. E. Hellman, "New Directions in Cryptography", IEEE Transactions on Information Theory, Vol. 22, No. 6, 1976, pp. 644-654, and the first practical implementation was proposed in R. L. Rivest, A. Shamir and L. Adeleman, "A Method for Obtaining Digital Signatures and Public-Key Cryptosystems", Communications of the ACM, Vol. 21, No. 2, 1978, pp. 120-126, and is known as RSA. The schemes can also be used to produce digital signatures, where the plaintext can be signed by encrypting with the secret key, and then read using the public key.

The cryptographic operations performed on the ciphertext and plaintext are best described and defined using mathematical formula and symbols that depict the cryptographic process as being a sequence of mathematical operations on the numerical value represented by the bits of the data forming the plaintext or ciphertext. RSA, for example, involves a sequence of operations which are performed in modulo n arithmetic, where n is part of the public key and is the product of two large primes p and q, that constitute the secret key. The security of RSA relies primarily on the difficulty of factoring the composite number n. Although relatively secure and simple to implement, RSA is susceptible to homomorphic attack, where valid digital signatures can be produced from the combination of previously signed messages that have been recorded.

Elliptic curves over finite fields have also been found to be applicable to cryptology where the points on a curve can form a group and where an initial point can be used to derive other points in the group in a cyclical manner until the initial point of the curve is obtained again. The plaintext can be made a coordinate of a point on an elliptic curve and encrypted by performing the operations on the point to move it to another point within the group. The message can only be retrieved by knowing the characteristics of the curve and the order of the group to which the plaintext belongs. The elliptic curve operations are also performed modulo n, where n is the product of two large primes p and q. The first elliptic curve based scheme which is analogous to RSA is proposed in K. Koyama, U. M. Maurer, T. Okamoto and S. A. Vanstone, "New Public-Key Schemes based on Elliptic Curves over the Ring Zn", CRYPTO '91 Abstracts, Santa Barbara, Calif., pp. 6-1 to 6-7, 11-15 August, 1991. The paper essentially describes two schemes, discussed hereinafter, which can be used for the same applications as RSA, one can only be used to produce digital signatures, while the second scheme can also be used for public key encryption. The latter scheme, however, is restricted in the types of primes, p and q, and the types of elliptic curves which can be used, and a second coordinate needs to be transmitted with the ciphertext to enable decryption. The first scheme has the disadvantages that the digital signatures are roughly twice as long as the message or plaintext and that trial and error is required to locate a point on the elliptic curve corresponding to a plaintext, which involves incrementing the value x of the plaintext.

In accordance with the present invention there is provided a cryptographic method including:

selecting secret keys p and q, being prime numbers greater than 3;

selecting public parameters for a series of data values which belong to one of a plurality of pairs of groups whereby any one of said data values in one of said pairs of groups is recovered by performing an operation kN.sub.i +1 times modulo n beginning with said any one of said data values, where k is an integer, N.sub.i is the order of the ith pair of groups and n=p.q;

selecting a public encryption key e which is a factor of kN.sub.i +1 for all i; and processing communications data as a member of one of said pairs of groups by performing said operation on said communications data, whereby the order N.sub.i of the pair of groups i that said communications data belongs to can be determined on the basis of p and q, and a secret decryption key d.sub.i can be determined using e.d.sub.j =kN.sub.j +1.

A preferred embodiment of the present invention is hereinafter described, by way of example only, with reference to the accompanying drawing, wherein:

FIG. 1 is a diagram of an elliptic curve used in a preferred embodiment of a cryptographic method.

The preferred embodiment involves operations based on the elliptic curve

y.sup.2 =x.sup.3 +ax+b (1)

where a and b are constants chosen so that

4a.sup.3 +27b.noteq.0 (2)

which ensures that the cubic equation

z=x.sup.3 +ax+b (3)

has three distinct roots. The graph of the curve is as shown in FIG. 1 if Equation 1 has three real roots. The curve has the property that if a non-vertical line 2 intersects it at two rational points (x.sub.1,y.sub.1) and (x,.sub.2 y.sub.2) then a third rational point of intersection (x.sub.3, y.sub.3) will exist. A tangent 3 to the curve is considered to have a double point of intersection (x.sub.k, y.sub.k) at the point of tangency. If two points (x.sub.1,y.sub.1) and (x.sub.2, Y.sub.2) are known then the third point of intersection (x.sub.3,y.sub.3) can be obtained by the following

x.sub.3 =.lambda..sup.2 -x.sub.1 -x.sub.2 (4)

y.sub.3 =.lambda..times.(x.sub.3 -x.sub.1)+y.sub.1 (5)

where if x.sub.1 .noteq.x.sub.2 then ##EQU1##

and if x.sub.1 =x.sub.2 then ##EQU2##

.lambda. being the slope of the line connecting the points.

Using the curve an "addition" operation can be defined where

(x.sub.1,y.sub.1)+(x.sub.2,y.sub.2)=(x.sub.3,-y.sub.3) (8)

The sum of the two intersecting points does not give the third intersection point but in fact gives the reflection across the x-axis of the third intersection point (x.sub.3,y.sub.3), as shown in FIG. 1. To form a group of points for which every straight line which intersects the curve at two points also intersects at a third, an identity .infin. is defined for the addition operation

(x,y)+(x,-y)=(x,-y)+(x,y)=.infin. (9)

The point .infin. can be though of as a point infinitely distant from the curve so that every vertical line passes through the point.

E(a,b) can be used to denote the group of rational points on the curve for a given a,b, including the point .infin.. Rational points can be derived from one another using the addition operation.

The above arithmetic operations also apply if performed modulo p where p is a prime number larger than 3 and a and b are integers chosen such that

4a.sup.3 +27b.sup.2 .noteq.0 (mod p) (10)

E.sub.p (a,b) can then be used to denote an elliptic curve group modulo p having elements (x,y) which are pairs of non-negative integers less than p which satisfy

y.sup.2 .ident.x.sup.3 +ax+b(mod p) (11)

The group includes the identity .infin., and the points in the group can be derived from one another using the addition operation. The modulo p curve of Equation 11 would of course be a discontinuous form of that illustrated in FIG. 1. A third point on the curve, R=(x.sub.3, y.sub.3), can be derived by adding two other points of the group, P=(x.sub.1,y.sub.1) and Q=(x.sub.2, y.sub.2),

using the following ##EQU3##

The identity element is defined such that if x.sub.1 .ident.x.sub.2 and y.sub.1 .ident.-y.sub.2 (mod p), then P+Q=.infin., i.e., P=-Q or (x.sub.2,-y.sub.2).ident.-(x.sub.2, y.sub.2) (mod p). The - symbol before a point in the group denotes the inverse of that point.

A point can be added to itself using the addition operation a number of times, i, to produce other points in the group. This is denoted as

(x.sub.i, y.sub.i).ident.(x.sub.1, y.sub.1)#i(mod p) (15)

where (x.sub.i,y.sub.i) is the ith point derived from the point (x.sub.1,y.sub.1). The # operation is often referred to as multiplication, i.e., the point (x.sub.i, y.sub.i) is the result of multiplying the point (x.sub.1,y.sub.1) by i. Efficient methods, as discussed hereinafter, arc available to perform this multiplication, for large values of i, by performing a chain of addition operations on ascending pairs of points in the group.

For example, (x.sub.2, y.sub.2) can be obtained by treating (x.sub.1, y.sub.1) as a double point or point tangency and adding it onto itself. Then (x.sub.4,y.sub.4) can be obtained by adding (x.sub.2,y.sub.2) onto itself, and (x.sub.3,y.sub.3) can be obtained by adding (x.sub.2,y.sub.2) onto (x.sub.1, y.sub.1) and (x.sub.6, y.sub.6), can be obtained by adding (x.sub.3,y.sub.3) onto (x.sub.3, y.sub.3) and so on.

If i equals the order of the group, the resulting point is the identity, .infin.. If i is one more than the order of the group the resulting point is the original point (x.sub.1,y.sub.1), i.e., the group has the property that P+.infin.=.infin.+P=P.

The elliptic curve cryptographic method relies on knowing the order of or number of points in E.sub.p (a,b). The order can be evaluated by observing that for a given value of x, if x.sup.3 +ax+b is a quadratic residue, i.e., possesses a square root modulo p, then there are two values of y that correspond to x, if x.sup.3 +ax+b is divisible by p, then there is only one value of y that corresponds to that x, and otherwise there are no values of y that correspond to that x. Taking also into account the point at .infin., the order of the group, denoted .vertline.E.sub.p (a,b).vertline.N.sub.p, is given by: ##EQU4##

where (z .vertline.P) is the Legendre symbol and z.ident.x.sup.3 +ax+b (mod p). The Legendre symbol is an operation performed using modulo arithmetic, in this case modulo p, to determine whether a number, in this case z, possesses a quadratic residue or not. The operation produces the value of .+-.1 or 0, 1 if the number is a quadratic residue, -1 if it is a quadratic non-residue and 0 if it is divisible by the modulus, p.

As an example, if p=5, and a=b=-1, the points of E.sub.5 (-1, -1) must satisfy

y.sup.2 .ident.x.sup.3 -x-1(mod 5) (17)

The coordinate x is not allowed to equal 3 as 23 is not a quadratic residue modulo

5. The elements of the group are

    ______________________________________
    (0,2), (1,2),     (2,0), (4,2),
    (0,3), (1,3),            (4,3),   and  .infin.
    If (x.sub.1, y.sub.1) = (0, 2), then
    (x.sub.2,
         = (0, 2) + (0, 2)
                      .lambda. = (3 .times. 0 - 1) .times. 4
                                      = 1 (mod 5),
    y.sub.2)          x.sub.2 = 1 - 0 - 0
                                      = 1 (mod 5),
                      -y.sub.2 = 1 .times. (1 - 0) + 2
                                      = 3 (mod 5),
         = (1, 2);
    (x.sub.3,
         = (1, 2) + (0, 2)
                      .lambda. = (2 - 2) .times. 1
                                      = 0 (mod 5),
    y.sub.3)          x.sub.3 = 0 - 1 - 0
                                      = 4 (mod 5),
                      -y.sub.3 = 0 .times. (4 - 0) + 2
                                      = 2 (mod 5),
         = (4, 3);
    (x.sub.4,
         = (4, 3) + (0, 2)
                      .lambda. = (3 - 2) .times. 4
                                      = 4 (mod 5),
    y.sub.4)          x.sub.4 = 16 - 4 - 0
                                      = 2 (mod 5),
                      -y.sub.4 = 4 .times. (2 - 0) + 2
                                      = 0 (mod 5),
         = (2, 0);
    (x.sub.5,
         = (2, 0) + (0, 2)
                      .lambda. = (0 - 2) .times. 3
                                      = 4 (mod 5),
    y.sub.5)          x.sub.5 = 16 - 2 - 0
                                      = 4 (mod 5),
                      -y.sub.5 = 4 .times. (4 - 0) + 2
                                      = 3 (mod 5),
         = (4, 2);
    (x.sub.6,
         = (4, 2) + (0, 2)
                      .lambda. = (2 - 2) .times. 4
                                      = 0 (mod 5),
    y.sub.6)          x.sub.6 = 0 - 4 - 0
                                      = 1 (mod 5),
                      -y.sub.6 = 0 .times. (1 - 0) + 2
                                      = 2 (mod 5),
         = (1, 3);
    (x.sub.7,
         = (1, 3) + (0, 2)
                      .lambda. = (3 - 2) .times. 1
                                      = 1 (mod 5),
    y.sub.7)          x.sub.7 = 1 - 1 - 0
                                      = 0 (mod 5),
                      -y.sub.7 = 1 .times. (0 - 0) + 2
                                      = 2 (mod 5),
         = (0, 3);
    (x.sub.8,
         = (0, 3) + (0, 2) = .infin..
    y.sub.8)
    ______________________________________

• Inventors
  Demytko, Nicholas;
• Assignee
  Telstra Corporation Limited (Melbourne, AU)
• Published
  May-6-1997
• Current US Classes:
  380/28
  380/30
  713/180
• Application #
  446816
• International Classes
  H04L 009/26
• Field of Search
  380/30 380/28 380/23
• Examiner
  Cain; David S.
• Agent
  Engellenner; Thomas J., Laurentano; Anthony A. Lahive & Cockfield
• US Patent References:
  4933970
  4935962
  4944007
  5146500
  5159632
  5272755