Elliptic curve point ambiguity resolution apparatus and method

• US 7,200,225 B1
• Filed: 11/08/2000
• Issued: 04/03/2007
• Est. Priority Date: 11/12/1999
• Status: Expired due to Term

• Current Assignee: Richard Schroeppel
• Original Assignee: Richard Schroeppel
• Inventors: Schroeppel, Richard
• Primary Examiner(s): Vu; Kim
• Assistant Examiner(s): Dada; Beemnet W
• Application Number:
  US09/710,987
• Time in Patent Office: 2,337 Days
• Field of Search: 380/30, 380/9, 380/28, 380/44, 380/277, 380/278
• US Class Current: 380/28
• CPC Class Codes: G06F 7/725 over elliptic curves
• CPC Class Codes: H04L 2209/043 of tables, e.g. lookup, substitution or mapping
• CPC Class Codes: H04L 2209/56 Financial cryptography, e.g. electronic payment or e-cash
• CPC Class Codes: H04L 2209/60 Digital content management, e.g. content distribution
• CPC Class Codes: H04L 9/08 Key distribution or management, e.g. generation, sharing or updating, of cryptographic keys or passwords network architectures or network communication protocols for supporting key management in a packet data network H04L63/06
• CPC Class Codes: H04L 9/3013 involving the discrete logarithm problem, e.g. ElGamal or Diffie-Hellman systems
• CPC Class Codes: H04L 9/3066 involving algebraic varieties, e.g. elliptic or hyper-elliptic curves

Abstract

An apparatus for operating a cryptographic engine may include a key generation module for creating key pairs for encrypting substantive content to be shared between two users over a secured or unsecured communication link. The key generation module may include a point-modification module as part of an elliptic curve module for creating and processing keys. The point-modification module preferably employs a point-halving algorithm for creating and processing keys but may also employ any one or a combination of a variety of other algorithms. Hash functions may be used to further process ephemeral secrets or ephemeral keys that may be used for transactions, sessions, or other comparatively short time increments of communication. The keys generated by the key generation module may be configured to be processable by an encryption system for divulging independently to two independent parties a secret to be shared by the two independent parties. A point-halving algorithm may be provided to reduce the operation count of a cryptographic process.

Claims

1. A computer implemented method embodied in data structures stored in a computer-readable medium to execute the following steps:

selecting an elliptic curve method;

executing a point modification algorithm to manipulate points of the elliptic curve method,

wherein the point modification algorithm includes at least five occurrences of point fractioning, with inputs to said at least five occurrences after a first depending directly or indirectly on results from a previous occurrence;

generating a signal having a distinct characteristic using the selected elliptic curve method;

providing substantive content; and

manipulating the substantive content using the distinct characteristic.

2. The method of claim 1, wherein the point modification algorithm is selected from point addition, point subtraction, point fractioning, point multiplying, rotating, negative point modification, and a combination of one or more thereof.

3. The method of claim 1, wherein manipulating the substantive content comprises encrypting the substantive content.

4. The method of claim 1, wherein manipulating the substantive content comprises decrypting the substantive content.

5. The method of claim 1, wherein the distinct characteristic is selected from a key and a signature.

6. The method of claim 2, wherein point fractioning is selected from integral point fractioning, corresponding to a denominator that is an integral number.

7. The method of claim 2, wherein point multiplying is selected from integral multiplication, imaginary multiplication, and complex multiplication.

8. The method of claim 1, further comprising dynamically specifying the point modification algorithm in lieu of specifying the modification operation in advance.

9. The method of claim 2, further comprising selecting a first point for execution of the point modification algorithm, based on a selected property.

10. The method of claim 9, wherein the selected property is a membership condition placing the first point in a subgroup.

11. The method of claim 10, further comprising repeating the point modification algorithm with a second point selected by another entity selected from a deterministic process, a random process, and a third party.

12. The method of claim 11, wherein the second point is communicated to the point modification algorithm in a format selected from a message and a certificate.

13. The method of claim 2, further comprising selecting a first point and pre-modifying the first point by a modification operation configured to compensate for some of the processing steps, added and corresponding to execution of a series of steps in accordance with the method.

14. The method of claim 1, further comprising sending by a sender and receiving by a receiver the substantive content, and wherein the sender executes a first operation during modification for encryption and the receiver executes a second and distinct operation during modification for decryption.

15. The method of claim 1, wherein generating the distinct characteristic further comprises creating a distinct characteristic selected from a symmetric key configured to be shared by two or more parties, a decryption code for processing an encrypted signal, a digital signature, an asymmetric key, and an authentication.

16. The method of claim 1, further comprising selecting a point and wherein the point is of a type selected from a hyperelliptic curve, an algebraic curve, and abelian variety.

17. The method of claim 1, wherein modifying a point further comprises halving a point represented in a cartesian space and a point existing in a mapped cartesian space having a cartesian representation.

18. The method of claim 17, wherein halving further comprises executing a single field multiplication per halving operation.

19. The method of claim 18, further comprising selecting a point characterized by a cartesian tuple and completing halving using no more than two field multiplications.

20. The method of claim 19, wherein halving further comprises negative halving including computation of a minus one-half multiple.

21. The method of claim 1, further comprising computing a fractional multiple of a point selected from a proper fraction, an improper fraction, and a complex fractional multiple.

22. The method of claim 18, further comprising determining a selection of points to execute a halving operation with respect to, based on testing for membership in a subgroup.

23. The method of claim 22, wherein testing further comprises reliance on a bit mask of coordinates corresponding to points in the subgroup.

24. The method of claim 23, wherein testing is executed by testing whether a halving procedure can be executed an arbitrary number of times selected by a user.

25. The method of claim 24, further comprising determining which of a selected number of points is to be used.

36. The method of claim 1, wherein the elliptic curve is over a finite field;

the finite field is represented by a field polynomial; and

the field polynomial is of low hamming weight.

37. The method of claim 36, wherein the field polynomial is selected from a binomial, a trinomial, and a pentanomial.

42. The method of claim 1, wherein the point modification algorithm comprises solving a quadratic equation using an efficient algorithm.

43. The method of claim 1, wherein the point modification algorithm comprises computing a reciprocal of a field element using an efficient algorithm.

44. The method of claim 1, wherein the point modification algorithm comprises at least one of adding and subtracting of elliptic curve points using an efficient algorithm.

45. The method of claim 44, wherein the addition and subtraction comprises computing a reciprocal of a field element using an efficient algorithm.

46. The method of claim 1, wherein the point modification algorithm comprises point multiplication using a sliding-window method.

47. The method of claim 1, wherein the point modification algorithm comprises at least two occurrences of point fractioning chained together.

48. The method of claim 47, wherein the elliptic curve points comprise intermediate points, having coordinates, and wherein the computation of some of the coordinates is omitted.

49. The method of claim 1, wherein the point modification algorithm further comprises choosing a multiplier having a low hamming weight.

50. The method of claim 1, wherein the point modification algorithm includes point addition and subtraction steps and the point modification algorithm is chosen to minimize the number of steps.

51. The method of claim 1, wherein the point modification algorithm is an addition-subtraction chain, intermixed with point fractioning.

52. The method of claim 1, wherein the elliptic curve is over a finite field, and the size of the finite field is increased such that a smaller number of addition and subtraction steps may be combined with a larger number of point fractioning steps, such that the overall computation effort is reduced, while preserving a specified level of security.

53. The method of claim 42, wherein the efficient algorithm is accelerated by using a Half-Trace formula.

54. The method of claim 42, wherein the efficient algorithm is accelerated by using the relationship between Qsolve(C) and Qsolve(C^2).

55. The method of claim 42, wherein the required storage of the efficient algorithm is reduced by using the relationship between Qsolve(C) and Qsolve(C^2).

56. The method of claim 1, wherein the point modification algorithm further comprises:

using a plurality of representations of the points;

using input points in one or more representations to produce output points in a different representation;

selecting representations that are optimal for succeeding point modification algorithms; and

wherein at least three changes of representation occur.

57. The method of claim 1, wherein at least some of the points are represented in XR representation.

58. The method of claim 56, further comprising switching between the XR and XY representations.

26. An apparatus comprising:

a system for creating a distinct characteristic configured to support cryptographic manipulation of information;

a memory device operably connected to the system for storing the distinct characteristic and executables programmed to operate on the distinct characteristic;

an encrypting device operably connected to the system for controlling an encryption process using the distinct characteristic;

the system further configured to execute an elliptic curve method for generating the distinct characteristic; and

the system further configured to execute a point modification algorithm for generating the distinct characteristic,

wherein the point modification algorithm includes at least five occurrences of point fractioning, with inputs to said at least five occurrences after a first depending directly or indirectly on results from a previous occurrence.

27. The apparatus of claim 26, wherein the point modification algorithm is selected from point addition, point subtraction, point fractioning, point multiplying, rotating, negative point modification, and a combination of one or more thereof.

28. The apparatus of claim 26, wherein the distinct characteristic is configured to be processable by the system for divulging independently to two independent parties a secret to be shared by the two independent parties.

29. An article of manufacture comprising a computer-readable medium storing operational data and executable data structures executable on a processor, the executable data structures comprising:

an encryption engine for operating on distinct characteristics configured to encrypt substantive content representing information;

the encryption engine, further comprising a distinct characteristic generation module for operating on the distinct characteristics;

the distinct characteristic generation module, further comprising an elliptic curve module for providing the distinct characteristics; and

the elliptic curve module, further comprising a point modification algorithm for calculating points related to the distinct characteristic,

wherein the point modification algorithm includes at least five occurrences of point fractioning, with inputs to said at least five occurrences after a first depending directly or indirectly on results from a previous occurrence.

30. The article of claim 29, wherein the point modification algorithm is selected from point addition, point subtraction, point fractioning, point multiplying, rotating, negative point modification, and a combination of one or more thereof.

31. The article of claim 30, wherein point fractioning is selected from integral point fractioning, corresponding to a denominator that is an integral number.

32. The article of claim 30, wherein point multiplying is selected from integral multiplication, imaginary multiplication, and complex multiplication.

33. The article of claim 29, further comprising dynamically specifying the point modification algorithm in lieu of specifying the modification operation in advance.

34. The article of claim 30, further comprising selecting a first point for execution of the point modification algorithm, based on a selected property.

35. The article of claim 29, wherein the distinct characteristics are selected from a key and a signature.

38. A computer implemented method embodied in data structures stored in a computer-readable medium to execute the following steps:

selecting an elliptic curve method,

wherein the elliptic curve is over a finite field and the finite field is represented as a field tower;

executing a point modification algorithm to manipulate points of the elliptic curve method,

wherein the point modification algorithm includes at least one occurrence of point fractioning;

generating a signal having a distinct characteristic using the selected elliptic curve method;

providing substantive content; and

manipulating the substantive content using the distinct characteristic.

39. The method of claim 38, wherein the field tower comprises an outer field;

and

the extension degree of the outer field is selected from the numbers 2, 3, 5, a product of the numbers, or repeated uses of any of the numbers.

40. The method of claim 38, wherein the field tower has more than two levels.

41. The method of claim 38, wherein the field tower comprises an inner field, having arithmetic, and wherein the arithmetic is accelerated by using pre-computed tables for operations selected from the group consisting of multiplication, squaring, taking the square root, division, reciprocation, taking the logarithm, exponentiation, calculating solutions of quadratic equations, and calculating the solutions of polynomial equations.

59. A computer implemented method embodied in data structures stored in a computer-readable medium to execute the following steps:

selecting an elliptic curve method;

executing a point modification algorithm to manipulate points of the elliptic curve method, the point modification algorithm comprising one or more ambiguous point triplication steps, where the ambiguity is resolved by determining whether a point is twice halvable;

generating a signal having a distinct characteristic using the elliptic curve method;

providing substantive content; and

manipulating the substantive content using the distinct characteristic.