ECC patents?

Alexander Klimov alserkli at inbox.ru
Sat Oct 15 18:41:46 EDT 2005


On Sun, 11 Sep 2005, Alexander Klimov wrote:
> Does anyone know a good survey about ECC patent situation?

I have made a shallow review (comments are welcome!) of the
patents that Certicom claims are pertained to ECC implementation
and it looks like there are no real road-blocks for ECDH and
ECDSA among them. In other words, IIUC it is possible to
implement EC encryption and signing without violating any patent
(of course, the implementer must be lucky enough to avoid any
patented optimization).

BTW, it looks like OpenSSL developers share this POV: README [1]
on branch OpenSSL_0_9_8-stable which implements ECDH and ECDSA
has PATENTS section which does not say a word about ECC.

In order to make this review I located two documents [2,3] in
which Certicom lists its patents related to ECC. It is
impossible to say that nobody else has patents in this area, but
the fact that the web site of SECG [4] (which is "the first
working group anywhere that is devoted exclusively to developing
standards based on ECC") does not have claims by anybody else
can be viewed as a hint of this.

Let us now review these lists. The first of them [2] contains
the following patents:

  [As of May 26, 1999] Certicom is the owner of the following
  issued patents:

  US 4,745,568 Computational method and apparatus for finite
  field multiplication, issued May 17, 1988. This patent
  includes methods for efficient implementation of finite field
  arithmetic using a normal basis representation.

[Optimization of multiplication in GF_{2^n}]

  US 5,787,028: Multiple Bit Multiplier, issued July 28, 1998.

[Multiplication in GF_{2^{nm}}, IIUC it is of no use now due to
Weil descent attack for EC(GF_{2^k}) with composite k.]

  US 5,761,305 Key Agreement and Transport Protocol with
  Implicit Signatures, issued June 2, 1998. This patent includes
  versions of the MQV protocols.

  US 5,889,865 Key Agreement and Transport Protocol with
  Implicit Signatures, issued March 30, 1999. This patent
  includes versions of the MQV protocols.

  US 5,896,455 Key Agreement and Transport Protocol with
  Implicit Signatures, issued April 20, 1999. This patent
  includes versions of the MQV protocols.

[These three are about MQV protocol and so are unrelated to ECDH
and ECDSA.]

  Certicom has the exclusive North American license rights to
  the following issued patent:

  US 5,600,725 Digital signature method and key agreement
  method, issued Feb. 4, 1997. This patent includes the
  Nyberg-Rueppel (NR) signature method.

[Described as "pertains to PV signatures" below.]

  Certicom has patent applications that include the following:

   * Methods for efficient implementation of elliptic curve
     includes efficient methods for computing inverses.

   * Methods for point compression.

   * Methods to improve performance of private key operations.

   * Various versions of the MQV key agreement protocols.

   * Methods to avoid the small subgroup attack.

   * Methods to improve performance of elliptic curve
     arithmetic; in particular, fast efficient multiplication
     techniques.

   * Methods to improve performance of finite field
     multiplication.

   * Methods for efficient implementation of arithmetic modulo n.

   * Methods to perform validation of elliptic curve public keys.

   * Methods to perform efficient basis conversion.

The second [3] of the lists contains the following:

  [As of February 10, 2005] Certicom is the owner of the
  following issued patents:

  EP 0 739 105 B1 (validated in DE, FR, and the UK) "Method for
  signature and session key generation" pertains to the MQV
  protocol

[Anybody knows, where it is available online?]

  US 5,761,305 "Key Agreement and Transport Protocols with
  Implicit Signatures" pertains to the MQV protocol

  US 5,889,865 "Key Agreement and Transport Protocol with
  Implicit Signatures" pertains to the MQV protocol

  US 5,896,455 "Key Agreement and Transport Protocol with
  Implicit Signatures" pertains to the MQV protocol

  US 6,122,736 "Key agreement and transport protocol with
  implicit signatures" pertains to the MQV protocol

  US 6,785,813 "Key agreement and transport protocol with
  implicit signatures" pertains to the MQV protocol

[Menezes-Qu-Vanstone (MQV) protocol -- an authenticated protocol
for key agreement based on the Diffie-Hellman scheme.]

  US 5,600,725 "Digital Signature Method and Key Agreement
  Method" pertains to PV signatures

[Pintsov-Vanstone (PV) signatures -- a scheme with partial
message recovery.]

  US 5,933,504 "Strengthened public key protocol" pertains to
  preventing the small-subgroup attack

[This one contains the following claims:

    1. A method of determining the integrity of a message
       exchanged between a pair of correspondents, said message
       being secured by embodying said message in a function of
       .alpha..sup.x where .alpha. is an element of a finite
       group S of order q, said method comprising the steps of
       at least one of the correspondents receiving public
       information .alpha..sup.x where x is an integer selected
       by another of said correspondents, determining whether
       said public information .alpha..sup.x when exponentiated
       to a value t where t is a divisor of q provides a
       resultant value .alpha..sup.xt corresponding to the group
       identity and rejecting messages utilizing said public
       information if said resultant value corresponds to said
       group identity.

    3. A method according to claim 1 wherein said order q is a
       prime number.

but IIUC it is exactly what DSA does: q is a prime, p = q z + 1
is also a prime, g = h^z (p), that is g^q = 1 (p) and thus g "is
an element of a finite group S of order q ... wherein said order
q is a prime number," as a part of a signature g^x is sent, where
"x is an integer selected by another of said correspondents". Am
I missing something?]

  US 6,141,420 "Elliptic Curve Encryption Systems" pertains to
  point compression

[Point compression theme seems to start from the following
claims:

    29. A method of transferring the coordinates of a point on
        an algebraic curve defined by a function of two
        variables between a pair of correspondents connected by
        a data communications link comprising the steps of
        forwarding from one correspondent to another a
        coordinate of said point, providing at said other
        correspondent parameters of said algebraic curve, and
        computing at said other correspondent said other
        coordinate from said one coordinate and said algebraic
        curve.

    30. A method according to claim 29 including the step of
        forwarding with said one coordinate identifying
        information of said other coordinate and utilising said
        identifying information and a discriminating function to
        determine the appropriate value of said other
        coordinate.

In other words, instead of sending a pair (x,y) that satisfies
F(x,y) = 0 one sends x and the recipient recovers y using the
equation alone (29) or using an additional hint about which of
several y was used (30). Here the art is (lossless) data
compression and every "person having ordinary skill in the art"
is aware of predictor-corrector method used here: using partial
data (x and, possibly, a hint) and the knowledge of data
distribution (F(x,y)=0) the recipient recovers the whole
information. How it is possible to get a patent on such an
obvious application of a well-known technique?

>From my POV point compression in the EC(GF_p) case is absolutely
trivial, but the case of EC(GF_{2^p}) probably is less so. In any
case, there is no problem to implement ECDSA and ECDH without
point compression.

Any pointers to prior art about at least point compression in
EC(GF_p)?]

  US 6,618,483 "Elliptic curve encryption systems" pertains to
  point compression

[Here Claim 3 seems to be of the same type.]

  US 6,704,870 "Digital Signatures on a Smart Card" pertains to
  ECDSA

[Seems to be an optimization for a smartcard which uses
computational power of the card accepting device:

    == Abstract ==

    A digital signature scheme for a "smart" card utilizes a set
    of prestored signing elements and combines pairs of the
    elements to produce a new session pair. The combination of
    the elements is performed partly on the card and partly on
    the associated transaction device so that the exchange of
    information between card and device does not disclose the
    identity of the signing elements. The signing elements are
    selected in a deterministic but unpredictable manner so that
    each pair of elements is used once. Further signing pairs
    are generated by implementing the signing over an anomalous
    elliptic curve encryption scheme and applying a Frobenius
    Operator to the normal basis representation of one of the
    elements.]

  CH 693 252 "Verfahren und Vorrichtung zur Erzeugenung einer
  ganzen Zahl" [that is, IIUC, "Procedure and device for the
  generation of an integer"] pertains to key generation

[Any idea where to download this one?]

  US 6,078,667 "Generating Unique and Unpredictable Values"
  pertains to key generation

[The method disclosed in this patent:

    == Abstract ==

    An integer for a private key is generated utilising a pair
    of components that are combined in a fixed predictable
    manner. The first component is generated from a sequencer
    such as a counter that generates non-repeating distinct
    value and the second component is generated in a random
    manner. By combining the components the integer has a unique
    and unpredictable value.

is both obvious (to get X with properties A and B concatenate
X_a, which has property A, and X_b, which has property B) and
AFAIU pointless for real key-generation because a long-enough
random key is unique with overwhelming probability.]

  AU 758044 "Implicit certificate scheme" pertains to bullet
  certificates

  EP 1 066 699 "Method of generating a public key in a secure
  digital communication system and implicit certificate"
  pertains to bullet certificates

  US 6,792,530 "Implicit certificate scheme" pertains to bullet
  certificates

[Implicit (aka. bullet) certificates "allow the recipient to
extract and verify the public key of the other party from the
signature portion."]

  Pertinent patent applications:

   * Methods to improve the performance of elliptic-curve
     arithmetic.

   * Methods to improve the performance of finite-field
     operations.

   * Methods to improve the performance of private-key
     operations.

   * Methods to improve the performance of public-key
     operations, including signature verification.

   * Methods to improve the performance of modular arithmetic.

   * Methods pertaining to the validation of elliptic-curve
     public keys.

   * Methods to thwart domain-parameter attacks.

   * Methods to perform efficient basis conversion.

   * Methods to generate keys with desirable cryptographic
     properties.

   * Methods pertaining to PV signatures.


[1] http://cvs.openssl.org/getfile/openssl/README?v=1.52.2.17

[2] http://www.secg.org/collateral/certicom_secg_patent.pdf

[3] http://www.secg.org/download/aid-398/certicom_patent_letter_SECG.pdf

[4] http://www.secg.org/?action=secg,docs_member_patents

-- 
Regards,
ASK

---------------------------------------------------------------------
The Cryptography Mailing List
Unsubscribe by sending "unsubscribe cryptography" to majordomo at metzdowd.com



More information about the cryptography mailing list