Avoiding certicom patents.

James A. Donald jamesd at echeque.com
Thu Oct 11 19:42:18 EDT 2007

Avoiding certicom patents.

The two patents that are actually useful are point
compression and ECMQV

Bodo Moeller, quoted by Bernstein, points out that one
can do point compression following the method of page
171 of the Harper-Menezes-Vanstone paper "Public-key
cryptosystems with very small key lengths" at Eurocrypt
'92, published more than a year before the filing of the
point compression patent.

::	The key length can be shortened to n+1 bits as
::	follows. Observe first that the change of
::	variables (x,y) -> (x,xz) transforms equation
::	y^2 + x*y = x^3 + a*x^2 + b, (1)
::	to
::	z^2 + z = x + a + b*x^(-2),  (3)
::	Given the x-coordinate of a point P = (x,y),
::	we can compute the right hand side of (3).
::	Then (3) has precisely 2 solutions, namely z'
::	and z'+1, and these solutions can be easily
::	found. We can then select the correct solution
::	z (and hence reconstruct y as y = xz) if we
::	know the least significant bit of z. Thus to
::	transmit P it is sufficient to transmit x and
::	the least significant bit of y/x.

I am not a lawyer, but if one follows the method as
given in the paper, and place direct quotes from the
paper in the source code comments and product
documentation, that should cover one's ass.

What ECMQV does is get forward secrecy *and*
authentication without additional cost.

If, however, we don't need the point compression patent,
neither do we need ECMQV.

Let capital letters represent elliptic curve points,
lower case letters represent integers modulo the order
of the generator.  Multiplication of an elliptic curve
point by an integer to give another elliptic curve point
takes polynomial time, division by an integer takes
exponential time, takes time 2^(n^2) where n is the bit
size of the field.

Simpe DH is as follows:

Bob has a secret key b, the integer b, and a well known
public key B = b*G, where G is the generator.

Carol has a secret key c, the integer c, and a well
known public key C = c*G, where G is the generator.

Bob constructs the shared secret b*C, Carol constructs
the shared secret c*B, b*C=c*B

This, however, means they use the same secret each time,
which can cause problems.  Best to use a secret that
randomly changes from time to time.

So to fix this:

Bob generates a random and frequently changing secret
number x, and transmits the point compressed value of X,
X=x*G to Carol.

Carol generates a random and frequently changing secret
number y, and and transmits the point compressed value
of Y, Y=y*G to Bob.

Bob computes (x+b)*(Y+C), Carol computes (c+y)*(X+B).
(x+b)*(Y+C) =(c+y)*(X+B)

Now if we were transmitting uncompressed points, there
would be some attacks which ECMQV prevents, but since we
are transmitting compressed points, these attacks cease
to work.

I repeat, I am not a lawyer, but then neither are the
judge or jury mathematicians.  If you simply don't have
the additional steps listed in ECMQV, how are they going
to justify the claim that it somehow really is ECMQV?

Note that that point compression avoids the attacks that
motivate ECMQV has not been examined in the literature,
nor have patent lawyers looked at any of the information
I present here.

          James A. Donald

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

More information about the cryptography mailing list