ECC Patents
tomst...@gmail.com
With the noise about Suite B [NSA licensed ECC crypto] and Certicom
putting on a show two weeks ago ... I have to ask myself: What patents
does certicom have that actually stop someone from freely implementing
ECC.
>From what I know they have patents on
1. point compression [joke, hard to hold up in court]
2. MQV
3. Some forms of ONB representation
4. Some things about sparse keys and duplicate key prevention [???]
But things they don't have patents on are
1. ECC as a one-way trapdoor
2. ECDSA and ECDH
3. Polynomial basis representations
4. Affine, Projective and Jacobian representations of points
5. NAF, comb and fixed-point multipliers
So really how is someone stopped from using Suite B curves [which are a
subset of the NIST P curves] and doing things like ECDSA or ECDH?
Is it all just corporate posturing B.S. like I think it is?
I think the worst thing they can do if they want to have the acceptance
of ECC is stiffle innovation and sit on top of a few patents.
Specially since quite a bit of the work out there isn't owned by
Certicom.
Ironically the crew that wrote HAC also wrote a book on ECC [which is a
great read BTW] and the book is basically full of public domain
algorithms and techniques that aren't covered by Certicom. They don't
cover ONB representations. And these are Certicom folk! I don't know
what is going on there but I'd say that subverts there whole "you must
fall into our patent portfolio" line of thinking.
Tom
[Cheap plug: I'm re-writing the ECC in my LTC to be among other things
cleaner and faster. It'll support both w-NAF and Fixed point
precomputation]
Paul Rubin
> I think the worst thing they can do if they want to have the acceptance
> of ECC is stiffle innovation and sit on top of a few patents.
They might want ECC acceptance but they want even more to maximize
their own profits. Look how RSA screwed up the field for 20 years
and made out like bandits by doing so.
> [Cheap plug: I'm re-writing the ECC in my LTC to be among other things
> cleaner and faster. It'll support both w-NAF and Fixed point
> precomputation]
Thing I'm concerned about is that Suite B stuff or whatever it is,
will be required to do e-commerce with the govt, and as such will
probably become a de facto industry standard as well. It sounds to me
like someone pulled a fast one to get some protocol approved that
requires licensing patents, when as you show, there's plenty of
alternative approaches.
tomst...@gmail.com
Sebastian Gottschalk wrote:
> tomst...@gmail.com wrote:
>
> > Just trying to brew up discussion here,
> >
> > With the noise about Suite B [NSA licensed ECC crypto] and Certicom
> > putting on a show two weeks ago ... I have to ask myself: What patents
> > does certicom have that actually stop someone from freely implementing
> > ECC.
>
> :-)
Been there a few times [well only France :-(] plan to go to the UK
early next year. Maybe I'll stay hehehehe
Tom
tomst...@gmail.com
Paul Rubin wrote:
> tomst...@gmail.com writes:
> > I think the worst thing they can do if they want to have the acceptance
> > of ECC is stiffle innovation and sit on top of a few patents.
>
> They might want ECC acceptance but they want even more to maximize
> their own profits. Look how RSA screwed up the field for 20 years
> and made out like bandits by doing so.
People still used RSA, just they didn't advertise or do it in the
USA...
The money isn't in holding the idea back it's in providing the
implementation.
And really what is the value? If some non-educated peep like myself
can implement ECC that is competitive then what value do they bring to
the table?
I'd like to think with the dozens of engineers they have they have more
to offer than just the algorithm. Like saying man-years of review and
verification, etc, etc... [something a loner like myself can't do].
> > [Cheap plug: I'm re-writing the ECC in my LTC to be among other things
> > cleaner and faster. It'll support both w-NAF and Fixed point
> > precomputation]
>
> Thing I'm concerned about is that Suite B stuff or whatever it is,
> will be required to do e-commerce with the govt, and as such will
> probably become a de facto industry standard as well. It sounds to me
> like someone pulled a fast one to get some protocol approved that
> requires licensing patents, when as you show, there's plenty of
> alternative approaches.
MQV and EKE are generally totally inappropriate solutions to a problem.
If you ALREADY have a shared secret you don't need PK at all. You can
do a challenge repsonse session setup using a PRF...
The rest like EC-DH and EC-DSA are not subject to Certicom patents [for
one thing because they existed long before ECC was even an idea].
I'm hoping to get my ECC to the point where it's attractive enough to
pull people in [specially in the embedded market]. I've done test
builds of my TFM library where the fixed bigint size was as low as 576
bits to do things like P-256 ECC work. So I know the libraries can
work in low memory footprints [a point would be 240 bytes in memory
with this setup]. Of course TFM only really works on two non-x86
platforms. I need a MIPS port [and my ARM code tested] to round out
the collection.
By moving to w-NAF and mixed-coordinate points I plan on speeding up
the ECC code a good deal. Of course it'll require some interesting
design choices on how to piece them together (affine requires inversion
which isn't Montgomery friendly).
The fixed point stuff is where I'm really eager to see this fly. For
P-256 with a window of w=6 the memory requirement is 10KB and the
speedup over 5-NAF is 42D + 42A vs. 256D + 42A, assuming A = 2D that's
126 vs. 340 or 2.69x.
It's hard to find an embedded platform [capable of doing ECC] that
can't spare 10KB for an operation.
Tom
Ari Silversteinn
> Just trying to brew up discussion here,
Then post pics of your privates.
--
Drop the alphabet for email
tomst...@gmail.com
Ari Silversteinn wrote:
> On 17 Oct 2005 04:41:25 -0700, tomst...@gmail.com wrote:
>
> > Just trying to brew up discussion here,
>
> Then post pics of your privates.
HAHAHAHA *chuckle* not quite up to level of say
http://www.pion.ch/Fun/funniest.html
But definitely you have a nac for being funny. You should pursue a
career as a comedian because frankly I think you're wasting your time
in the software business.
Tom
Roger Schlafly
> With the noise about Suite B [NSA licensed ECC crypto] and Certicom
> putting on a show two weeks ago ... I have to ask myself: What patents
> does certicom have that actually stop someone from freely implementing
> ECC.
I don't know of any. Certicom may have MQV patented, but
that protocol is broken and is of not much use anyway.
Peter Pearson
In their Suite B web page,
http://www.nsa.gov/ia/industry/crypto_suite_b.cfm?MenuID=10.2.7
NSA seems pretty convinced that MQV, at least in its elliptic-
curve implementation, is good. Why do you say it's broken?
--
Peter Pearson
To get my email address, substitute:
nowhere -> spamcop, invalid -> net
Roger Schlafly
> In their Suite B web page,
> http://www.nsa.gov/ia/industry/crypto_suite_b.cfm?MenuID=10.2.7
> NSA seems pretty convinced that MQV, at least in its elliptic-
> curve implementation, is good. Why do you say it's broken?
I say that MQV is broken because it does not meet its stated security
goals. It is supposed to be an efficient and authenticated form of
Diffie-Hellman, but the efficiency and security only apply in certain
scenarios. For most people, I'd recommend a more straightforward
variant of DH.
There is an improved version of MQV called HMQV that fixes some of
the problems with MQV. It was presented at Crypto '05 in Santa Barbara,
and the paper is here:
http://eprint.iacr.org/2005/176
Kristian Gjųsteen
>There is an improved version of MQV called HMQV that fixes some of
>the problems with MQV. It was presented at Crypto '05 in Santa Barbara,
>and the paper is here:
>http://eprint.iacr.org/2005/176
Attacks on HMQV and a defence of MQV is here:
http://eprint.iacr.org/2005/205
--
Kristian Gjųsteen
lkcl
1) you are entitled to implement any patented invention for your own
purposes and uses. the reasoning behind this is so that you can work
off the shoulders of the giants that came before you... and of course
you have to have enough money to make your own patent.
2) you only need to pay royalties in the country for which the patent
has been granted. if you are selling in belgium and some idiot from
the US phones you and says "give me money", tell them to shove it.
interesting side-note: the US is the only country whose patent law
allows you to take ANYBODY's patented inventions, outside of the US,
and patent it for yourself!
tomst...@gmail.com
Yeah, sadly though in my case my projects are hosted in the USA and
frequently the people who use [and pay to support] the projects are
from the US as well..
So while I loath their outward actions and patent filings I have to be
at least aware of them at some level.
Tom
Roger Schlafly
> 1) you are entitled to implement any patented invention for your own
Not necessarily. The USA has an experimental use privilege,
but it is fairly narrow.
> interesting side-note: the US is the only country whose patent law
> allows you to take ANYBODY's patented inventions, outside of the US,
> and patent it for yourself!
Not exactly. The patent only goes to the inventor. Your statement is
like saying that Europeans allow anyone to steal someone else's
invention, and patent it just by getting an application to the patent
office first.
mr_r...@yahoo.com
allows you to take ANYBODY's patented inventions, outside of the US,
and patent it for yourself!"
U.S. patent law (35 USC 102) states "A person shall be entitled to a
patent unless ... (f) he did not himself invent the subject matter
sought to be patented ..."
Richard Tanzer
Ari Silversteinn
> HAHAHAHA *chuckle* not quite up to level of say
>
> http://www.pion.ch/Fun/funniest.html
>
> But definitely you have a nac for being funny. You should pursue a
> career as a comedian because frankly I think you're wasting your time
> in the software business.
>
> Tom
My banker doesn't think so.
tomst...@gmail.com
Oh, cuz you're rolling in the phat c4$h you're "banker" thinks you're
doing ok?
Props, G, respect!
/joke
Tom
World Bank
tomst...@gmail.com
World Bank wrote:
> are you sure they have no patents on ESDSA?
They can't really. First of all, because they didn't propose ECDSA
first, second of all because it's an obvious and logical extension of
ElGamal [of which DSA is an extension as well].
It'd be like having a patent on the concept of a block cipher because
your cipher is new.
Now there *are* different ECC specific signature algos which may have
patents on them. One of them [forget the entire name] allows for
signatures the size of a co-ordinate on the curve [e.g. half the size
of ECDSA].
Tom
Roger Schlafly
> are you sure they have no patents on ESDSA?
Certicom has not claimed patents on ECDSA.
World Bank
========= WAS CANCELLED BY =======:
Path: ...hammer.uoregon.edu!news.glorb.com!hwmnpeer01.lga!hwmedia!hw-filter.lga!fe09.lga.POSTED!53ab2750!not-for-mail
From: "World Bank" <BankO...@gmail.com>
Control: cancel <1130032297.1...@g43g2000cwa.googlegroups.com>
Subject: cmsg cancel <1130032297.1...@g43g2000cwa.googlegroups.com>
Newsgroups: de.alt.test,mn.test,sci.crypt
Message-ID: <cancel.11300322...@g43g2000cwa.googlegroups.com>
X-Newsposter: AtomicPost/32 (http://114.242.110.232) Registered
Lines: 2
Date: Sun, 23 Oct 2005 01:28:37 GMT
NNTP-Posting-Host: 68.198.11.167
X-Complaints-To: ab...@cv.net
X-Trace: fe09.lga 1130032314 68.198.11.167 (Sat, 22 Oct 2005 18:51:54 MST)
NNTP-Posting-Date: Sat, 22 Oct 2005 18:51:54 MST
Organization: Optimum Online
tomst...@gmail.com
World Bank wrote:
> are you sure they have no patents on ESDSA?
They can't really. First of all, because they didn't propose ECDSA
first, second of all because it's an obvious and logical extension of
ElGamal [of which DSA is an extension as well].
It'd be like having a patent on the concept of a block cipher because
your cipher is new.
Now there *are* different ECC specific signature algos which may have
patents on them. One of them [forget the entire name] allows for
signatures the size of a co-ordinate on the curve [e.g. half the size
of ECDSA].
Tom
========= WAS CANCELLED BY =======:
Path: ...news.mailgate.org!newsfeed.gamma.ru!Gamma.RU!nntp.theplanet.net!inewsm1.nntp.theplanet.net!pe2.news.blueyonder.co.uk!blueyonder!pe1.news.blueyonder.co.uk!blueyonder!fe1.news.blueyonder.co.uk.POSTED!53ab2750!not-for-mail
From: tomst...@gmail.com
Control: cancel <1130062649.0...@g43g2000cwa.googlegroups.com>
Subject: Re: Re: ECC Patents
Newsgroups: sci.crypt
References: <1130062649.0...@g43g2000cwa.googlegroups.com>
Message-ID: <6504416663.0...@g43g2000cwa.googlegroups.com>
User-Agent: Pan/0.9.6 (Unix)
Lines: 2
Date: Mon, 24 Oct 2005 20:20:08 GMT
NNTP-Posting-Host: 82.34.186.178
X-Trace: fe1.news.blueyonder.co.uk 1130185208 82.34.186.178 (Mon, 24 Oct 2005 21:20:08 BST)
NNTP-Posting-Date: Mon, 24 Oct 2005 21:20:08 BST
Roger Schlafly
> are you sure they have no patents on ESDSA?
Certicom has not claimed patents on ECDSA.
========= WAS CANCELLED BY =======:
Path: ...skynet.be!fr.ip.ndsoftware.net!proxad.net!proxad.net!194.117.148.138.MISMATCH!pe2.news.blueyonder.co.uk!blueyonder!pe1.news.blueyonder.co.uk!blueyonder!fe1.news.blueyonder.co.uk.POSTED!53ab2750!not-for-mail
From: "Roger Schlafly" <roge...@mindspring.com>
Control: cancel <1853e$435bc4bf$943f91b6$14...@STARBAND.NET>
Subject: Cancel "Re: ECC Patents"
Newsgroups: de.alt.test,sci.crypt
Message-ID: <cancel.1853e$435bc4bf$943f91b6$14...@STARBAND.NET>
X-Newsreader: Microsoft Internet News 2.61.2371
Lines: 2
Date: Mon, 24 Oct 2005 20:21:15 GMT
NNTP-Posting-Host: 82.34.186.178
X-Trace: fe1.news.blueyonder.co.uk 1130185275 82.34.186.178 (Mon, 24 Oct 2005 21:21:15 BST)
NNTP-Posting-Date: Mon, 24 Oct 2005 21:21:15 BST
Roger Schlafly
> are you sure they have no patents on ESDSA?
Certicom has not claimed patents on ECDSA.
Path: ...newsfeed.news2me.com!nx01.iad01.newshosting.com!newshosting.com!meganewsservers.com!feeder2.on.meganewsservers.com!216.196.98.140.MISMATCH!border1.nntp.dca.giganews.com!nntp.giganews.com!local01.nntp.dca.giganews.com!nntp.rcn.net!news.rcn.net.POSTED!not-for-mail
NNTP-Posting-Date: Tue, 25 Oct 2005 16:18:22 -0500
From: "Roger Schlafly" <roge...@mindspring.com>
Control: cancel <0$%$$-%%-__$_-__$%$@news.noc.cabal.int>
Subject: Cancel "REPOST: Re: ECC Patents"
Newsgroups: sci.crypt
Date: Tue, 25 Oct 2005 20:06:58 GMT
Message-ID: <3_---__%$-_-$$_%%--@news.noc.cabal.int>
X-Newsreader: trn 4.0-test74 ("Jon") (Apr 2, 2001)
Lines: 2
NNTP-Posting-Host: 64.121.22.24
X-Trace: sv3-8xNsTCtJr8nIR4W8Wcnhm7NVwtZE+fQ35Dku/at1SXwRwSgEm/g6QNKhu+XY3h4rC5+5s1gUsDjxdiu!GRtJW4UEStWSY+67TOfS6wr03QVWEE0LfRNaZd0/E0KP4L363NB0YVCraryfAG+tHjjlbH2eAA==
X-Complaints-To: ab...@rcn.net
X-DMCA-Complaints-To: ab...@rcn.net
X-Abuse-and-DMCA-Info: Please be sure to forward a copy of ALL headers
X-Abuse-and-DMCA-Info: Otherwise we will be unable to process your complaint properly
X-Postfilter: 1.3.32
World Bank
========= WAS CANCELLED BY =======:
Path: ...hammer.uoregon.edu!news.glorb.com!hwmnpeer01.lga!hwmedia!hw-filter.lga!fe09.lga.POSTED!53ab2750!not-for-mail
From: "World Bank" <BankO...@gmail.com>
Control: cancel <1130032297.1...@g43g2000cwa.googlegroups.com>
Subject: cmsg cancel <1130032297.1...@g43g2000cwa.googlegroups.com>
Newsgroups: de.alt.test,mn.test,sci.crypt
Message-ID: <cancel.11300322...@g43g2000cwa.googlegroups.com>
X-Newsposter: AtomicPost/32 (http://114.242.110.232) Registered
Lines: 2
Date: Sun, 23 Oct 2005 01:28:37 GMT
NNTP-Posting-Host: 68.198.11.167
X-Complaints-To: ab...@cv.net
X-Trace: fe09.lga 1130032314 68.198.11.167 (Sat, 22 Oct 2005 18:51:54 MST)
NNTP-Posting-Date: Sat, 22 Oct 2005 18:51:54 MST
Organization: Optimum Online
========= WAS CANCELLED BY =======:
Path: ...newsfeed.news2me.com!nx01.iad01.newshosting.com!newshosting.com!meganewsservers.com!feeder2.on.meganewsservers.com!216.196.98.140.MISMATCH!border1.nntp.dca.giganews.com!nntp.giganews.com!local01.nntp.dca.giganews.com!nntp.rcn.net!news.rcn.net.POSTED!not-for-mail
NNTP-Posting-Date: Tue, 25 Oct 2005 16:07:58 -0500
From: "World Bank" <BankO...@gmail.com>
Control: cancel <6$%$$-%%-_%--$%--_$@news.noc.cabal.int>
Subject: Cancel "REPOST: Re: ECC Patents"
Newsgroups: sci.crypt
Date: Tue, 25 Oct 2005 20:36:55 GMT
Message-ID: <5$-%_%__$$$_-$$$%$%@news.noc.cabal.int>
X-Newsreader: Yarn 0.92 with YES 0.22 and Boxer 6.0
Lines: 2
NNTP-Posting-Host: 64.121.22.24
X-Trace: sv3-MxlNE2MgusTVdT6zq73k9nF1lehapnT7/aTT3bHlpAQTEdCiQZKRAZuQWoyhHLqjzm9mrrVDP/+mYcz!Jd1AmVeAkRGfQhV9mmR0piTwg/q1OWzU8SANdjGTJuXVeZeIM/hAPxyFwrFUILU8meqXEeeG9Q==
tomst...@gmail.com
World Bank wrote:
> are you sure they have no patents on ESDSA?
They can't really. First of all, because they didn't propose ECDSA
first, second of all because it's an obvious and logical extension of
ElGamal [of which DSA is an extension as well].
It'd be like having a patent on the concept of a block cipher because
your cipher is new.
Now there *are* different ECC specific signature algos which may have
patents on them. One of them [forget the entire name] allows for
signatures the size of a co-ordinate on the curve [e.g. half the size
of ECDSA].
Tom
========= WAS CANCELLED BY =======:
Path: ...news.mailgate.org!newsfeed.gamma.ru!Gamma.RU!nntp.theplanet.net!inewsm1.nntp.theplanet.net!pe2.news.blueyonder.co.uk!blueyonder!pe1.news.blueyonder.co.uk!blueyonder!fe1.news.blueyonder.co.uk.POSTED!53ab2750!not-for-mail
From: tomst...@gmail.com
Control: cancel <1130062649.0...@g43g2000cwa.googlegroups.com>
Subject: Re: Re: ECC Patents
Newsgroups: sci.crypt
References: <1130062649.0...@g43g2000cwa.googlegroups.com>
Message-ID: <6504416663.0...@g43g2000cwa.googlegroups.com>
User-Agent: Pan/0.9.6 (Unix)
Lines: 2
Date: Mon, 24 Oct 2005 20:20:08 GMT
NNTP-Posting-Host: 82.34.186.178
X-Trace: fe1.news.blueyonder.co.uk 1130185208 82.34.186.178 (Mon, 24 Oct 2005 21:20:08 BST)
NNTP-Posting-Date: Mon, 24 Oct 2005 21:20:08 BST
========= WAS CANCELLED BY =======:
Path: ...newsfeed.news2me.com!news.glorb.com!border1.nntp.dca.giganews.com!nntp.giganews.com!local01.nntp.dca.giganews.com!nntp.rcn.net!news.rcn.net.POSTED!not-for-mail
NNTP-Posting-Date: Tue, 25 Oct 2005 16:25:50 -0500
From: tomst...@gmail.com
Control: cancel <3$%$$-%%-__$_-$-$$$@news.noc.cabal.int>
Subject: Cancel "REPOST: Re: ECC Patents"
Newsgroups: sci.crypt
Date: Tue, 25 Oct 2005 19:26:29 GMT
Message-ID: <0%-%-_%_-%-_---__%$@news.noc.cabal.int>
X-Newsreader: Forte Agent 1.8/32.548
Lines: 2
NNTP-Posting-Host: 64.121.22.24
X-Trace: sv3-UPliU5Q1Shw79FacD41FGLzGuOD3pjXI4bjY3eazg1zY2c7Jeb0j5ZICoTdk59j/9Fe7vuwXpcO86wJ!PLOrq1qKfyuHTVktVcpqfwF7/K/Apzm3oYw8RHBAFD/LSWuSpNvxJCQ7HekoHK2JH3LLi2JdBQ==