[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]
Re: Sun's Elliptic Curve Technology Contribution to the OpenSSL Project
On October 10, 2002 09:22 pm, Bob Beck wrote:
> >So if I were to create a free clean-room clone of Sun's ECC library,
> >it wouldn't matter how many patents Sun had on it, because I'm not
> >selling anything, and there is no revenue stream for the litigation to
> >attack. Even the much hated DMCA wouldn't be useable because
> >implementing a published algorithm is engineering not reverse
> >engineering.
>
> But Dragos, there is revenue stream to attack if I make a
> successful commercial product based on your clean room library that
> Sun thinks violates their patent. This prevents free software from
> being incorporated into commercial products by vendors other than Sun,
> who don't already have existing contracturual NDA crap going with Sun
> so they don't sue each other over existing patents. It's the same
> readon we couldn't use "free" RSA implementations the same way before
> it's patent expired, and the same reason we don't use IDEA. - same
> problem.
Ok, very good points, Bob.
I haven't been paying close attention to open source as
long as you and Theo have so I defer to your wisdom
in understanding the traps.
But enough conjecture.
So here is the scoop on the "Sun" ECC patents.
Searching on Sun and Elliptic Curve yielded nothing.
However I did find two applicable patents. (I don't play
a patent lawyer on TV and an authoritative search would
have to be done in person in Ottawa or at the US Patent
Office, but that disclaimer aside... the internet searches
should be just as good in theory so let's go on.)
Elliptic Curve crypto was discovered by Neal Koblitz and V.S. Miller
in 1985 is not patented per se. However, there are only two efficient
implementations of ECC that I dug up, Nyberg-Rueppel and ECDSA.
Both schemes depend on the order of the base point being a large
prime number for security. Supposedly the Nyberg-Rueppel version
is patented but US Patent number 5600725 patents are the discrete
logarithm versions and not the elliptic curve versions at explicit claim.
The DSA version isn't patented at all (it was patented, but...) and is
unencumbered since the owners lost a suit against the US
Government. (The NSA are the only guys who get to play the
submarine patent game. :-)
However In 1998 Certicom was formed, and filed the attached
patent affadavit with IEEE. The Sun patent claim seems to stem from
a 5% stake Sun bought into Certicom. Which also explains the
funny wording in the Sun license about other people's patents
on this code - they must be talking about the other Certicom
stake-holders.
So ECC is _not_ patented, just one particular implementation (and
there seems to be some wiggle room in that too) and other
implementations or other methods of evading the patent may
exist in addition to this.
Other comments: The patent _applications_ below are just saber rattling
from Certicom. And if patents are not granted for applications in a fixed
length of time from the application they become void (the time period
varies from country to country and in international patents, AFAIR this
is typically less than 2-5 years. Sooo since they are dated 1998.... :-).
To be granted patent status literature searches would have to confirm
the lack of any pre-existing publication.
Important comment: Since there are TWO implementations and one is
UNPATENTED... I must ask why OpenSSL felt the need to accept the
patented libraries instead of sticking to unpatented DSA version?
cheers,
--dr
P.S. RSA seems to hold a patent on an interoperability schema
between these two ECC implementations.
P.P.S. Good Eliptic Curve Reference: http://www.cryptoman.com/elliptic.htm
The patents section at the bottom makes interesting reading. :-)
And curiously at the bottom it has links to two other ECC library
implementations ( I haven't checked licenses :-). (Bada Boom Bada Bing :-)
--kyx--
(Dated June 25 1998)
Attachment to Certicom response of June 24, 1998 to IEEE P1363 patent
solicitation letter
PART I. Elliptic Curve Discrete Logarithm Method
An implementation conforming to IEEE P1363 methods based on the elliptic
curve discrete logarithm may require a license from Certicom for one or
more of the following items.
Certicom has the license rights to the following patent:
4745568: 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.
Certicom has the exclusive North American license rights to the following
patent:
5600725: Digital signature method and key agreement method,
issued Feb. 4, 1997.
This patent includes the Nyberg-Rueppel (NR) signature method.
Certicom has patent applications that include the following:
1. Methods for efficient implementation of elliptic curve arithmetic over
finite fields. This includes efficient methods for computing inverses.
2. Methods for point compression.
3. Methods to improve performance of private key operations.
4. Various versions of the MQV key agreement protocols.
5. Methods to represent an elliptic curve point using a normal basis and
methods for efficient computation using such representations.
6. Methods to improve performance of finite field arithmetic of
characteristic two by using subfields.
7. Methods to avoid the small subgroup attack.
8. Methods to improve performance of elliptic curve arithmetic; in
particular, fast efficient multiplication techniques.
9. Methods to improve performance of finite field arithmetic of
characteristic two using a permuted optimal normal basis representation.
10. Methods to improve performance of finite field multiplication.
11. Methods for efficient implementation of arithmetic modulo n, where n
is prime or composite.
12. Methods to perform validation of EC public keys.
13. Methods to improve performance for some public key based protocols.
PART II. Discrete Logarithm Problem Methods
An implementation conforming to IEEE P1363 methods based on the discrete
logarithm problem over a finite field might require a license from Certicom
for one or more of the following items.
Certicom has the license rights to the following patent:
4745568: 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.
Certicom has the exclusive North American license rights
to the following patent:
5600725: Digital signature method and key agreement method,
issued Feb. 4, 1997.
This patent includes the Nyberg-Rueppel (NR) signature method.
Certicom has patent applications that include the following:
14. Methods to improve performance of private key operations.
15. Various versions of the MQV key agreement protocols.
16. Methods to improve performance of finite field arithmetic of a
characteristic two by using subfields.
17. Methods to avoid the small subgroup attack.
18. Methods to improve performance of finite field arithmetic of
characteristic two.
19. Methods to improve performance of finite field multiplication.
20. Methods for efficient implementation of arithmetic modulo n, where n
is prime or composite.
21. Methods to perform validation of DL public keys.
22. Methods to improve performance of public key operations.
PART III. Integer Factorization Methods
An implementation conforming to P1363 methods based on the integer
factorization problem might, if the applicable patent applications are
granted, require a license from Certicom for one or more of the following
items.
Certicom has patent applications that include the following:
23. Methods for efficient implementation of arithmetic modulo n, where n
is prime or composite.
24. Methods to perform validation of IF public keys.
--
dr@kyx.net pgp: http://dragos.com/kyxpgp
Advance CanSecWest/03 registration available: http://cansecwest.com
"The question of whether computers can think is like the question
of whether submarines can swim." --Edsger Wybe Dijkstra 1930-2002