(1) ECC used as a shared-secret-key cipher
(2) ECC used in conventional PKI
(3) ECC used as a component of Identity Based
Encryption (IBE)
(4) ECC in other applications.
Some supporting evidence for your assessments would
be nice.
Does anyone know of any official pronouncements on
what the NSA thinks about ECC, in particular with
respect to its use in military or government
applications?
ECC is probably the best all-around technology for PKI, but
market share is miniscule and RSA and DSA are adequate.
> (3) ECC used as a component of Identity Based
> Encryption (IBE)
Too early to tell.
> (4) ECC in other applications.
> Some supporting evidence for your assessments would
> be nice.
> Does anyone know of any official pronouncements on
> what the NSA thinks about ECC, in particular with
> respect to its use in military or government
> applications?
Here on sci.crypt, there are those who think an NSA endorsement
proves it is best, and others who think that anything the NSA says
publicly is part of a sinister plot.
> (1) ECC used as a shared-secret-key cipher
I think you'll find that rather hard to do. ECC is Diffie-Hellman done
over Elliptic Curves.
> (2) ECC used in conventional PKI
ECC is not one of the conventional PKIs
> (3) ECC used as a component of Identity Based
> Encryption (IBE)
Used in place of Diffie-Hellman it will work quite well, other than
that it generally fails to even fit.
> (4) ECC in other applications.
Like signing? ECDSA
Like Key Agreement? EC-DH, EC-MQV
Like replacing ElGamal? EC-ElGamal
That's basically all it's good for, it's a straight replacement for DH
in all forms, it's primary benefit is that it requires smaller keys
than DH.
Joe
A number of proposals are moving forward.
> (3) ECC used as a component of Identity Based
> Encryption (IBE)
Check out http://crypto.stanford.edu/ibe/
>
> (4) ECC in other applications.
>
> Some supporting evidence for your assessments would
> be nice.
>
> Does anyone know of any official pronouncements on
> what the NSA thinks about ECC, in particular with
> respect to its use in military or government
> applications?
ECDSA is approved for use by NIST in non-classified by sensitive
government uses (FIPS 186-2).
The WAP forum's version of WTLS uses elliptic curve diffie hellman in
its key exchanges (WAP-224?).
IKE WG of IETF has a couple of ECDH groups either approved or fairly
close to approval for use in IKE.
The TLS working group of IETF is hammering out a framework for
extending TLS for supporting elliptic curve diffie hellman and EC
digital signatures.
As for the NSA, I don't know of any official pronouncements, but it is
known that NIST consults with the NSA, so if NIST approved ECDSA, draw
your own conclusions.
ANSI has several ECC standards, including X 9.62 and X 9.63. IEEE has
IEEE 1363 which covers ECC.
ECC is coming. Just try to imagine doing a key exchange for 256 bit
keys with RSA or discrete log Diffie-Hellman and you'll see why
something else is needed. The momentum is behind elliptic curve
discrete log based solutions.
Some nitpicking...
<...>
> IKE WG of IETF has a couple of ECDH groups either approved or fairly
> close to approval for use in IKE.
There is no "IKE wg", only IPSec. Already the IKE spec (RFC2409,
November 1998) defines four "Oakley" groups. That isn't an official
statement on behalf of the IETF that ECC or the selected curves are any
good; they just have been allocated identities in the protocols. IETF
doesn't pretend to be an expert on cryptology ;-)
-- Lassi
Cheers,
Elisabeth
--
Elisabeth Oswald <=> Elisabet...@iaik.at
IAIK, TU-Graz, Austria
Phone: (+43 316) 873 5527
I had been under the impression that the patent-free ECC solutions
available were too slow, was I mistaken?
--
__ Paul Crowley
\/ o\ s...@paul.cluefactory.org.uk
/\__/ http://www.cluefactory.org.uk/paul/
"Conservation of angular momentum makes the world go around" - John Clark
What patents? I don't think that there are any significant ECC patents.
Several people independently came up with the idea of using 'halves' to
speed up EC multiplications (don't ask - I don't know). One of them
patented it, and appears to be aggressively chasing other people who use
the technique. Consequently, one has to be careful about whose EC
library one uses. However, this isn't really a patent on the Crypto
itself, merely a low-level technique in the EC library it's based on.
Phil
http://cr.yp.to/nistp224/timings.html
---Dan
Ok, but that is just one minor technique for a speedup, and not that
big a deal IIRC. Also, I think it only applies to characteristic 2 fields.
Is there definitely no patent on point compression?
From my recent US patent search, there is a patent 6,252,960 "Compression
and decompression of elliptic curve data points", which applies to
compression of one bit of X coordinate.
I cannot guarantee it. I believe HP applied for a patent on a
trick for saving 1 bit in the case of even fields. I don't know
what HP's intentions are, but I doubt that anyone is going to
license a patent and do some extra and nonstandard computations
just to save 1 lousy bit.
The main "point compression" of interest to ECC is the simple
observation that numbers in a field have (at most) 2 square
roots, so a single bit can indicate which to choose. Ie, a point
(x,y) on a curve can be represented by x and 1 extra bit,
because y satisfies a quadratic equation.
Certicom used to go around hinting that it had some sort of
patent application pending for point compression. Other times
it implied that it had no such claims. I think that it is just FUD.
Yes, thanks. One bit of X, over even (char-2) fields. Its a clever trick.
If the field were 160 bits, then saving a bit could mean saving a
byte. But GF(2^160) is out of fashion, and keys are usually
rounded to the nearest byte anyway, so this technique is just not
of much practical significance, if any.
http://cr.yp.to/nistp224/patents.html
The simplest (and generally best) form of compression was published in
1985, so it is obviously not patented.
---Dan
Re Patents on ECC stuff...
As far as I am aware, and remember I am just a humble academic
and dont have a team of lawyers/patent attorneys looking at this
stuff.
Definitely Not Patented
=======================
The actual cryptographic algorithms EC-DSA, EC-DH etc
Probably Patented
=================
Numerous implementation tricks (but this also applies to any
scheme you care to mention, eg RSA, DSA etc)
eg Point halving
ONB fields
Koblitz curve tricks
Note, you can probably implement a good ECC scheme without
infringing these patents. But you may infringe others you know
nothing about though, however an RSA implementation could do that
as well.
Expect to be Patented
=====================
(i.e. If these are not patented I would be VERY surprised)
MQV Protocol (Very, very efficient authenticated key agreement scheme)
Point compression
Cheers
Nigel
--
Dr Nigel P. Smart | Phone: +44 (0)117 954 5163
Computer Science Department, | Fax: +44 (0)117 954 5208
Woodland Road, | Email: ni...@cs.bris.ac.uk
University of Bristol, BS8 1UB, UK | URL: http://www.cs.bris.ac.uk/~nigel/
DJohn37050 <djohn...@aol.com> wrote:
> Certicom has always claimed it has a patent (pending) on point
> compression in every standards body that asked.
What ``invention'' does Certicom claim in that patent application?
---Dan
All it says is that Certicom has patent applications on ``methods of
point compression.'' Is that for some minor technique that nobody will
bother to use, like 6252960, or is it broader?
Many people have asked for details, and nobody has received an answer.
If Certicom actually had a legitimate patent covering the whole field
then it wouldn't be trying to hide the details.
Anyway, Certicom obviously can't patent Miller's 1985 point-compression
method, and that's the method I'm using, so I'm not worried.
---Dan
It's hard to imagine any useful computation that would scale linearly
from a superscalar 32-bit processor such as the Pentium down to a
tinkertoy 8-bit processor. It's also not good for the users if we ignore
the ``fancy arithmetic'' available on serious computers.
---Dan
Quisquater wrote:
> Patent ECC on point compression,
> see <http://www.delphion.com/details?pn=US06252960__>
US06252960__> in elliptic curve processing systems, information is
US06252960__> typically processed to yield elliptic curve data points,
US06252960__> with X and Y coordinates each represented by N bits, N
US06252960__> typically being 160 or more. Valid Y coordinates must
US06252960__> satisfy a quadratic equation for any given X coordinate,
US06252960__> such that any Y data may be represented by its corresponding
US06252960__> X coordinate and a single additional byte or bit. In
US06252960__> accordance with this disclosure, a vector t is chosen for
US06252960__> which the dot product between t and any X coordinate is
US06252960__> equal to a constant. The vector t is used in a compression
US06252960__> mode of the preferred embodiment to select a bit position in
US06252960__> X coordinate data with the X bit at that location being
US06252960__> discarded and the Y coordinate information being stored in
US06252960__> its place. As a result, an extra byte of data is not needed
US06252960__> and any elliptic curve data point may be represented by N
US06252960__> bits only.
so it is about representing point with X and one bit for Y (compressed into X),
but representing point with Y and one bit for X (compressed into Y) is not not patented!
or is it? I didn't read very carefully....
__
Disastry http://disastry.dhs.org/
http://disastry.dhs.org/pgp <----PGP plugins for Netscape and MDaemon
^--GPG for Win32 (supports loadable modules and IDEA)
^----PGP 2.6.3ia-multi05 (supports IDEA, CAST5, BLOWFISH, TWOFISH,
AES, 3DES ciphers and MD5, SHA1, RIPEMD160, SHA2 hashes)
-----BEGIN PGP SIGNATURE-----
Version: Netscape PGP half-Plugin 0.15 by Disastry / PGPsdk v1.7.1
iQA/AwUBO+k+vTBaTVEuJQxkEQMNYACcC6LrLixtPwTAyWyYeXVNbbL9m8oAn38X
eRVD1QUyhuk2cPvnMI34yG2h
=r4I2
-----END PGP SIGNATURE-----
---Dan"
It is a choice. If one is only concerned with speed on a specific platform,
one can optimize for that platform. If one WANTS scalability, one can do that,
and Certicom does that in some of its products. When we give performance
numbers, they scale down, as we find that is the most useful for our customers.
We often provide solutions in constrained systems, so this makes sense for our
purposes.
Don Johnson
The basic idea is that if anyone is doing point compression as in P1363, then
they should consider asking Certicom and HP for licensing info. The patent
owner then say what it is willing to license. In fact, if one is doing any
form of point compression, one can still ask.
Don Johnson
A quick search on Delphion shows Certicom has 20 granted US patents
and 2 applications that are published.
A very quick scan shows the following patent:
http://www.delphion.com/details?pn=US06141420__
This patent issued on Oct 31, 2000. It may or may not be THE pending
patent. I will let more knowledgable people decide what it says.
--
Stanley Chow CTO stanle...@cloakware.com
Cloakware Corp (613) 271-9446 x 223
"Use of Elliptic Curves in Cryptography", Victor S. Miller, Crypto 85.
Miller writes:
"Finally, it should be remarked, that even though we have phrased
everything in terms of points on an elliptic curve, that, for the key
exchange protocol (and other uses as one-way functions), that only the
x-coordinate needs to be transmitted. The formulas for multiples of a
point cited in the first section make it clear that the x-coordinate of
a multiple depends only on the x-coordinate of the original point."
So Miller's "compression" is to just leave off the y coord. This is
not the same as the compression used in most EC standards today, which
is to send 1 bit to distinguish between the two possible square roots
which could represent the y coordinate.
Is Miller right about the x coordinate of all multiples of a point
depending only on the x coordinate of the original? The recurrence
relation he gives goes as follows:
g[1] = 1
g[2] = 1
g[3] = 3x^4 + 6ax^2 + 12bx - a^2
g[4] = x^6 + 5ax^4 + 20bx^3 - 5a^2x^2 - 4abx - 8b^2 - a^3
g[2n] = g[n] ( g[n+2]g[n-1]^2 - g[n-2]g[n+1]^2 )
g[4n+1] = 16y^4g[2n+2]g[2n]^3 - g[2n+1]^3g[2n-1]
g[4n+3] = g[2n+3]g[2n+1]^3 - 16y^4g[2n+2]^3g[2n]
f[2n] = 2yg[2n]
f[2n+1] = g[2n+1]
p[n] = xf[n]^2 - f[n+1]f[n-1]
4yw[n] = f[n+2]f[n-1]^2 - f[n-2]f[n+1]^2
then integer n times curve point (x,y) is:
(p[n]/f[n]^2, o[n]/f[n]^3)
The x coordinate depends on p and f. p depends on f and x, and f depends
on g and y. g depends on x and y, although the only use of y is as y^4
which depends only on x, so g really depends only on x.
f depends on y only via f[2n] = 2yg[2n]. So for even indexes f depends
on y, while for odd indexes it only depends on x. Howver, even _powers_
of f will not depend on y since y^2 depends only on x.
In the x-coordinate, p[n]/f[n]^2, obviously the denominator is an even
power of f and so will depend only on x, whether n is odd or even.
The numerator p[n] = xf[n]^2 - f[n+1]f[n-1]. The first term is an
even power of f, and the second term is a product of two adjacent
odd or even indexes of f, which will either have two y terms or none.
That term will therefore either depend on y not at all, or depend on y^2,
and hence only on x.
So Miller seems to be correct that the x coordinate of a curve point
multiple depends only on the x coordinate of the initial point.
The IEEE P1363 elliptic curve algorithms all depend only on the x
coordinates of elliptic curve points. For these algorithms, then,
Miller's optimization should be usable and the y coordinate can be
eliminated from data exchange.
However many current EC protocols use a less efficient compression,
in which one bit of the y coordinate is sent in order to distinguish
which square root is meant. This also requires sending a bit to indicate
whether compression is in use or not. There is also the need to indicate
a zero curve point, which requires another bit. In practice an extra
byte is sent which holds a 3 bit value.
Given Miller's argument, it should not be necessary to send the
y bit. The receiver can choose either square root for y and perform
his calculations. He will get the same x coordinate as the sender,
whether he used the same y value or not. And since zero is not a legal
curve point for these protocols, there is no need for the extra byte
(as long as compression is always used).
Is it possible that Certicom has a submarine patent on the use of one
bit to indicate the y coordinate? Perhaps if so, implementations can
avoid infringement by simply ignoring the y bit, even if the protocol
sends it. With the basic secret-value-derivation and signature primitives
as defined by P1363, there is no need for the bit. By ignoring the bit
and choosing a specific y value independent of the bit in the message,
it should be possible to avoid infringing any patent on this technique.
Miller writes:
Your analysis is wrong, I agree it would be a good question on a crypto exam.
Miller's observation, is, of course, correct.
Don Johnson
I also disagree that Certicom has not been forthcoming. Certicom says what it
claims to have according to the rules of the relevant forums.
Don Johnson
Not true. I have asked you questions myself at IEEE P1363
meetings about Certicom's claims regarding patents. Every time
you were evasive. I don't think I ever got a straight answer out
of you for anything.
In particular, you refused to tell us whether Certicom had a patent
application with an independent claim for point compression, or
what Certicom was claiming in its application, or even the serial
number(s) of the patent application. I ultimately concluded that you
were just blowing smoke.
That is just not true. I was Secretary of the IEEE P1363 group. At
one point, we threw out the patent technologies (RSA, etc), but
we left in elliptic curves with point compression because we
believe that it was unpatented. Certicom participated in all those
discussions and drafts, and led us to believe that Certicom had
no patents pending on point compression.
Here is the June 1998 letter from Certicom.
http://grouper.ieee.org/groups/1363/P1363/letters/Certicom.txt
This letter was presented years after we put elliptic curves in, and
it is hopelessly ambiguous.
Why? The rumor is that Certicom's patent application was rejected.
Certicom said what was requested to be said in that forum. You might WANT more
to be said, but that was not what that forum specified. It is just kvetching
to complain that I do not say what I am not authorized to say or need to say in
a forum.
Also, I do not blow smoke. If you disagree with the way patent policy is in
USA, tell someone with the power to change the system. If you disagree with
IEEE IP policy, talk to them. If you want to see what Certicom licenses, talk
to the director of licensing.
Don Johnson
I cannot say what happened before I attended IEEE P1363 meetings. I know that
my experience before I joined was that I heard Certicom claim to have a patent
pending on point compression. I know once I joined that I did not hide this.
RSA was not thrown out, rather it was delayed being able to be worked on until
the appropriate licensing assurances letter was sent. This was as an entire
algorithm, as the entire algorithm was patented. This was not the case with
ECC.
I also do not think the Certicom patent letter is hopelessly ambiguous. You
look in certain sections of IEEE P1363 and you can see where Certicom claims
IP. It may not be specific enough for your wishes, but it was not intended to
meet your wishes, it was intended to meet IEEE P1363 policy. If you want to
find out more info about a potential license, you need to ask the director of
licensing.
Don Johnson
That is just not true. I asked you what Certicom was claiming,
and you refused to tell us.
> You might WANT more
> to be said, but that was not what that forum specified. It is just
kvetching
> to complain that I do not say what I am not authorized to say or need to
say in
> a forum.
Perhaps Certicom would fire you if you told the truth.
> Also, I do not blow smoke. If you disagree with the way patent policy is
in
> USA, tell someone with the power to change the system. If you disagree
with
> IEEE IP policy, talk to them. If you want to see what Certicom licenses,
talk
> to the director of licensing.
> Don Johnson
Answer this: What did Certicom invent related to point compression?
I am not quibbling to US patent policy. I do object to you saying that
Certicom has been forthcoming with patent information, and then
being totally evasive in response to any simple question.
Ah. Then why does Certicom claim to have invented ``transferring the
coordinates of a point on an algebraic curve defined by a function of
two variables'' by sending ``a coordinate of said point''?
---Dan
You joined in 1995. The Certicom letter was in 1998. I didn't hear
anything about a Certicom patent application until that letter, and I
was the Secretary!
> RSA was not thrown out, rather it was delayed being able to be worked on
until
> the appropriate licensing assurances letter was sent.
We actually removed it from the working draft.
> I also do not think the Certicom patent letter is hopelessly ambiguous.
The letter does not say whether Certicom is claiming to have invented
elliptic curve point compression.
> You
> look in certain sections of IEEE P1363 and you can see where Certicom
claims
> IP.
Really, which sections?
> It may not be specific enough for your wishes, but it was not intended to
> meet your wishes, it was intended to meet IEEE P1363 policy. If you want
to
> find out more info about a potential license, you need to ask the director
of
> licensing.
I use ECC point compression. Have used it for years. To the best of
my knowledge, I don't need a license. Not even Certicom says I
need a license.
On the contrary. It's comparing fresh, crunchy, hand-picked apples to
old, mushy, machine-picked apples. Even better, the fresh apples are
being given away for free.
The machine company thinks it's unfair to compare hand-picked apples to
machine-picked apples? That's not my problem. The choice is clear.
---Dan
Is it just me, or does this sound odd? What reason does Certicom have
for not disclosing more? I am hard-pressed to think of any good reasons,
but if this is a failure of my imagination, I hope you will enlighten me.
Three little words, F U D.
When asked, Don will tell you that US law allows patent applications
to remain secret, and therefore he doesn't have to tell you what
Certicom is trying to patent.
The usual rationale for that aspect of US patent law is that
inventors should be allowed to use their ideas as trade secrets
until they have the protection of patent law. In this case, Certicom
obviously has other motives.
I only see 2 explanations.
1. Certicom has a submarine patent on point compression pending,
and wishes to trap as many companies as possible into unwitting
infringement, so they'll have to pay when the patent issues.
2. Certicom has no such patent pending, and is just spreading FUD
to help get license deals.
The version that is in the standards has been broken, so who cares?
No one uses it anyway.
> Point compression
I doubt it. If Certicom invented this, why aren't the inventors
bragging about it? Why won't Certicom say what it is trying
to patent? What is new -- that a number might have 2 square
roots? That a bit can be used to indicate 1 of 2 values?
Am I missing something important here?
I agree that scalability is often very important, but perhaps I mean
something different by the word. One of the very attractive things
about Rijndael is that it is scalable in the sense that I mean: it can
be made efficient either on very constrained environments like smart
cards, or on modern superscalar processors, and the two can
interoperate. However, the implementations that are fast on each of
these platforms couldn't be more different: one is fundamentally
byte-oriented, while the other makes heavy use of 32-bit word-oriented
instructions. This isn't a problem, since they're implementing the
same standard.
If scalability is desirable in this instance, it is the duty of the
standards body to publish a standard that can be efficiently
implemented across the board. But Bernstein isn't proposing a
standard; he's implementing an existing standard. Specifically, he's
publishing an implementation optimized for a selection of modern
superscalar processors, the most efficient known on (eg) the Pentium
III. His only duty is to conform to the standard; scalability doesn't
come into it.
That leaves open the question of who has the best implementation on
(eg) Z80-based smart cards. Maybe Certicom has. But it's impossible
to see this as a reason to use Certicom's implementation on the
Pentium. If you're implementing the same standard on two platforms,
why does it need to be the same implementation?
--
__ Paul Crowley
\/ o\ s...@paul.cluefactory.org.uk
/\__/ http://www.cluefactory.org.uk/paul/
"Conservation of angular momentum makes the world go around" - John Clark
: What patents? I don't think that there are any significant ECC patents.
Make a research ,, that is not hard, right?
--
------------------------
Yongge Wang
http://cs.uwm.edu/~wang/
------------------------
Each patent letter to a standards forum is crafted to meet the requirements of
the forum. What is so hard to understand? If you want to use point
compression, I suggest you talk to the director of licensing. It is just a
pointer, not a complete thesis.
Don Johnson
http://cr.yp.to/patents/us/6141420.html
---Dan
So what do you mean by this supposedly desirable aspect of
implementations, "scalability"?
I don't think King's New Clothes is a good way to conduct a debate on
sci.crypt or elsewhere.
MQV is broken. MQV was proposed to IEEE P1363, ANSI
X9.42, and X9.63 as a DH alternative that avoided the unknown
key-share attack. At the time, some variants of DH were under
consideration that were subject to the unknown key-share attack,
and the MQV authors convinced the committees that the unknown
key-share attack was important, so they only adopted variants
of DH that were believed to be not subject to the attack. This
included the DH "unified model" and MQV.
But unfortunately, MQV was modified before these standards
were finalized, and the standardized version of MQV is subject
to the unknown key-share attack.
NSA does not like MQV enough to use it itself.
Yes, but the inventors do know what claims they are making
in the application. It is always possible that a pending application
will be rejected.
> When a patent issues, it is public info
> anyway and everyone can see the claims and the teaching.
Yes, when the patent issues. We did not have that info when we
put point compression into IEEE P1363.
> Each patent letter to a standards forum is crafted to meet the
requirements of
> the forum. What is so hard to understand?
It's not -- I know FUD when I see it.
> If you want to use point
> compression, I suggest you talk to the director of licensing. It is just
a
> pointer, not a complete thesis.
Are you referring to US Patent 6,141,420, claim 29?
This is true, it does not work for the DSA signature. Although only
the x coordinate is used ultimately, the verification actually uses the
x coordinate of k1*G + k2*W, where G is a known curve parameter and W
is the signer's public key, which is the value we would be interested
in compressing. Although the x coordinate of k2*W can be found from
the x coordinate alone of W, the sum requires knowing the y coordinate.
However compression is perhaps not as much of an issue for keys, since
they can be cached and don't need to be sent as often as signatures.
It's also possible to simply run the verification equation twice, once
with each possible value of y, when verification is not as time sensitive
as signing (often the case in server-client applications).
With the Diffie-Hellman algorithm, however, the shortcut above does work,
as Dan Bernstein points out. Given the other party's public key W'
and the local private key s, the shared secret value is the x coordinate
of s*W'. (One or the other of the remote and local keys may be ephemeral
for ElGamal style communication.) This can be computed knowing only the
x coordinate of W'.
So for static _encryption_ keys, there is no need to distribute the
y coordinate. And in the case of ephemeral keys, this saves space on a
per-message basis since the ephemeral public key has to be communicated
with each message.
Thanks. I hadn't noticed that patent.
Your ECC stuff seems to use prime fields. The prime field point
compression claims in the above patent seem to be only directed
at a method that uses the Legendre symbol to compress the point.
But no one uses that. The standards just use the least significant
bit of y, since exactly one of { y, p-y } will be odd (and one even).
You have a lot more faith in the technical skills of patent examiners
than I do. I hope I don't need to cite past examples of ridiculous
patents that were accepted by patent examiners. Frankly, the fact that a
patent was issued gives, to first order, roughly zero bits of information
concerning whether it ought to be valid, as far as I can tell.
Your word 'sometimes' is certainly correct. I guess
that other times challenges are not made for diverse
reasons, including high cost of legal processes.
M. K. Shen
The examiner probably spent less than 5 minutes looking at the Miller
paper. It is safe to say that Dan has a better understanding.
Miller describes ECC key exchange, and remarks that it can be
done using the x-coordinate also. If that is what Dan is doing, then
he is safe.
Can you describe this a little more? If you just send the x
coordinate, you can try both possible square roots and see which one
works, but that's more computation than if you send a bit selecting
which square root you want. Is that what you're talking about?
Over a prime field, a point (x,y) satisfies y^2 = cubic in x.
Given x, the 2 square roots are y and -y, giving points (x,y) and (x,-y).
When multiplying by an integer N,
N (x,-y) = N (-1) (x,y) = - N (x,y)
So if you don't know whether the sender is using y or -y, you can just
guess, and N(x,y) will still have the correct x-coordinate and a 50%
chance that the y-coordinate is correct also.
When you are doing ECC key exchange, all you need is for the 2
parties to compute a shared secret. You can do this:
Ann sends x-coord of public key
Bob sends x-coord of public key
Each guesses the other's y-coord
Each computes a shared EC point.
Each uses the x-coord of the point as the shared secret.
The idea is that you are not sure of the y-coord but you don't need it
anyway.
For signatures, it is a bit trickier. (Sorry! <g>) There you have to be
more careful about the choice of y or guess and see what works or
something like that.
> I had been under the impression that the patent-free ECC solutions
> available were too slow, was I mistaken?
If you use the OpenSSL elliptic curve library [1] on PCs, you can get
about the same performance for a 160-bit GF(p) curve as for 1024-bit
DSA. These also are believed to provide essentially the same
security. On Sun hardware, NIST curve P-192 provides about the same
performance as 1024-bit DSA. (RSA is different in that private-key
operations are slower than for DSA while public-key operations are very
fast.) The comparison gets better for elliptic curves if you want
more security than this because attacks against DSA and RSA have
subexponential complexity while attacks against ECC appear to have
exponential complexity.
The OpenSSL EC operations can be made roughly 50% faster for NIST
and similar curves over GF(p): The current implementation uses
only Montgomery reduction and not Solinas' fast reduction method for
Generalized Mersenne Primes (which may or may not have a patent
pending).
Using Koblitz curves over GF(2^p), it should be possible to obtain
nearly four times the current OpenSSL performance while avoiding
patents. (The best techniques for Koblitz curves, which are due to
Solinas, are patented by the NSA. I am not aware of the licensing
conditions. Earlier techniques are not covered by patents as far as I
am aware.)
There are many patent issues for GF(2^p) with normal bases, but
hardly anyone uses normal bases anyway. They certainly appear pretty
useless for software implementations.
[1] Not available in any released version of OpenSSL so far (it will
be in 0.9.7); the current development version is always available
at <URL:ftp://ftp.openssl.org/snapshot;type=d>.
--
Bodo Möller <moe...@cdc.informatik.tu-darmstadt.de>
PGP http://www.informatik.tu-darmstadt.de/TI/Mitarbeiter/moeller/0x36d2c658.html
* TU Darmstadt, Theoretische Informatik, Alexanderstr. 10, D-64283 Darmstadt
* Tel. +49-6151-16-6628, Fax +49-6151-16-6036
On the other hand, as a follow-up to my nistp224 work, I'm developing a
replacement for the NIST P-224 standard, providing at least 1.5x the
performance at the same security level.
(One good choice of curve is y^2 = x^3 + 7530x^2 + x mod 2^226 - 5. But
I'm thinking of switching to something mod 2^228 + 3.)
One might reasonably ask whether this change in curve is a good idea for
tinkertoy computers. The answer is that it provides even larger speedups
in that situation, because minimizing the amount of arithmetic no longer
requires spending thousands of bytes of memory.
---Dan
Is there any concern that these special curves might be easier to
compute DL's on than random curves?
This curve isn't special. It has nearly prime order and nearly prime
twist order; a large fraction of such curves are isomorphic to curves of
the shape y^2 = x^3 + c_2 x^2 + x.
To speed up computations, I chose a fairly small c_2 coefficient, and
small coefficients of the modulus, but nobody knows any way for an
attacker to take advantage of these small coefficients.
Algorithms based on smoothness become a constant factor more effective
when coefficients are small---for example, a genus-0 discrete log with
the number field sieve can handle inputs twice as large if the
coefficients are small---but algorithms based on smoothness are, as far
as we know, useless for typical elliptic curves.
---Dan
>"Paul Rubin" <phr-n...@nightsong.com> wrote
>> > Miller describes ECC key exchange, and remarks that it can be
>> > done using the x-coordinate also. If that is what Dan is doing, then
>> > he is safe.
>> Can you describe this a little more? If you just send the x
>> coordinate, you can try both possible square roots and see which one
>> works, but that's more computation than if you send a bit selecting
>> which square root you want. Is that what you're talking about?
>
>Over a prime field, a point (x,y) satisfies y^2 = cubic in x.
>Given x, the 2 square roots are y and -y, giving points (x,y) and (x,-y).
>
>When multiplying by an integer N,
> N (x,-y) = N (-1) (x,y) = - N (x,y)
>So if you don't know whether the sender is using y or -y, you can just
>guess, and N(x,y) will still have the correct x-coordinate and a 50%
>chance that the y-coordinate is correct also.
>
>When you are doing ECC key exchange, all you need is for the 2
>parties to compute a shared secret. You can do this:
>
> Ann sends x-coord of public key
> Bob sends x-coord of public key
> Each guesses the other's y-coord
> Each computes a shared EC point.
> Each uses the x-coord of the point as the shared secret.
And on smart cards, it gives you which computation time ??? I just read Nigel Smart book and the
algorithm that is given for the square root is not what I would call "fast and direct" ...
If you only have the sign bit of the y coord, you still have to calculate
the square root, I thought.
It makes sense if you have severe bandwidth contraints.
If you are more interested in minimizing computation,
then send x and y.
Montgomery's x-coordinate point-multiplication method, when applied to
curves of Montgomery's shape y^2 = x^3 + c_2 x^2 + x, is faster for
typical curve sizes than any known x,y point-multiplication method, so
you can happily skip both the y transmission and the square root.
In fact, if both the curve and its twist have nearly prime order, then
you can even skip square testing.
---Dan
Can you recommend a reasonable book about this stuff? Thanks.
Pedal-to-the-metal optimization of state-of-the-art cryptographic
systems is a current research area. Many techniques haven't even
appeared in papers, never mind books.
Would there actually be a market for a book on high-speed cryptography?
Are many people interested in learning how the fastest software works?
---Dan
<insert two cents here>
I'd say a book that covers both the design/analysis of fast algorithms as
well as how to implement them on x86 series processors would be a useful
book.
Tom
I don't think a book is necessary. For most public key schemes the critical
calculation is integer multiplication. The trick then is to (a) figure out
the best way to access the multiplier unit via the available instruction
set, and (b) to organise your code so that the multiplier hardware is kept
as busy as possible. BTW as far as I am aware the algorithms are basically
good old fashioned long multiplication, done column by column - no great
mystery there.
The answer to (a) is that the fmul instruction is the best, or arguably in
the Pentium IV one of the new SSE2 instructions. My understanding is that
the multiplier unit is pipelined, so that a new fmul can be issued every one
or two clock cycles, but you have to wait maybe 4 or 5 more cycles for the
result. The integer multiplication instruction always write to EAX and DAX,
so in this case unfortunately you have to wait for the full instruction to
complete. However the output of the fmul instruction can be directed to any
of the 8 FP registers. Therefore the next fmul instruction can be issued
almost immediately, as long as its output is written to a different
register. Furthermore the extended precision FP registers can accumulate the
80-bit integer result of the summation of a column of 64-bit partial
products - the basis of long multiplication with 32 bit digits.
The answer to (b) is to suitable schedule your code so that the multiplier
can be kept busy, but this requires really complex in-line coding -
overlapping column calculations and executing them well out of the natural
order. Unfortunately the pipline seems to have gotten deeper as we
"progressed" from the Pentium II to the Pentium III to the Pentium IV, so
its getting harder all the time. And if you want to write the code in C, you
need to know more or less exactly how the compiler will generate the code,
or else write it directly in assembler. Happily with a few hints the GCC
compiler will play ball.
Regrettably good scheduling/cycle counting tools are not easy to come by.
Also in my experience most processor manuals do not provide sufficient
information to facilitate this kind of optimization.
Mike Scott
>
> Tom
>
>
On the athlon you can send one fmul or mmx multiply every two cycles. I
believe they take three cycles so something like
pmullw mm0,mm1 [1]
mov ebx,3 [2]
pmullw mm2,mm3 [3]
[mm0 ready] [4]
Well that is my experience anyways. I used tons of 16-bit multiplies in my
winamp plugin and I found that it takes 3.5 cycles per 16-bit sample to be
linearly remapped [a 16x16=32 multiply and a shift].
I'd much rather use MMX then the FPU since MMX deals primarily with integer
arithmetic. The biggest problem is comparaisons are a pain. For example,
there is no quick way to tell if a bit is set, etc...
Also to use MMX you'd have to pack the data in an awkward format that would
probably take more time than you'd save.
The 32x32=64 multipliers are fairly fast. Often you can scheduled a
multiply every two cycles since they're pipelined.
> The answer to (b) is to suitable schedule your code so that the multiplier
> can be kept busy, but this requires really complex in-line coding -
> overlapping column calculations and executing them well out of the natural
> order. Unfortunately the pipline seems to have gotten deeper as we
> "progressed" from the Pentium II to the Pentium III to the Pentium IV, so
> its getting harder all the time. And if you want to write the code in C,
you
> need to know more or less exactly how the compiler will generate the code,
> or else write it directly in assembler. Happily with a few hints the GCC
> compiler will play ball.
>
> Regrettably good scheduling/cycle counting tools are not easy to come by.
> Also in my experience most processor manuals do not provide sufficient
> information to facilitate this kind of optimization.
The trick I use is to obviously to pick a good algorithm, but I also
schedule the code in a logical sense. For example, I avoid simple stalls
like
mov eax,ecx
shl eax,4
mov edi,[ebx]
and write
mov eax,ecx
mov edi,[ebx]
shl eax,4
I think both take the same amount of time on an Athlon, but things like that
are usually a good idea.
Another good trick is to have a RDTSC timer routine handy. Look at the
manual, make a change, profile, and restart. I've used this for my TC15
cipher for example. It takes about 170 cycles per block on my Athlon. My
winamp plugin also remaps samples at approximately 3.5 cycles per sample
[excluding calling overhead and such].
Most integer multipliers like in GMP and MPI are sufficiently fast for most
personal uses. I'd say more interest is in the algorithms then the
implementation details. A fast multiplier in C for example is not usually
straightforward [albeit none to complex]. There is more than just
multipliers though, fast reduction modulo a number, fast exponentiation,
etc...
Tom
The real problem is that we will never know because that is the way they operate.
Note as of today I no longer work for Certicom and opinions are my own.
Don Johnson
Is there evidence that they're doing that for classified stuff?
Are they going to replace all the STU-III phones? Have they done
that already? I don't keep up with stuff like that.
It's not classified that the military (at least in the past) used
STU-III phones for classified conversations (or that the air force
flies F15's). The technical details of how a STU-III or an F15 works
may be classified, but their existence is not.
If the air force suddenly got rid of all its F15's, I think that would
be public knowledge.
My question is, are STU-III's still in use?
Maybe that's classified but it doesn't seem that likely.
It's also possible that they kept the STU-III's but upgraded the
internal algorithms. However, I don't have the impression that that's
feasible.
Yes they are. Like much other crypto gear, the
level of security they can support depends on the
keying material used to set them up. Properly
keyed, and when used inside an appropriate facility,
they can support up to T/S over unsecured public
circuits. For additional info:
http://www.smdc.army.mil/SecurityGuide/S1class/Stu3.
htm
> Maybe that's classified but it doesn't seem that
likely.
>
It's not. Without keying material, the STU-III
itself, like a lot of other crypto equipment, is
unclassified.
> It's also possible that they kept the STU-III's
but upgraded the
> internal algorithms. However, I don't have the
impression that that's
> feasible.
There are several variations by at least two
manufacturers. For voice comm, they are compatible.
For data comm, there seem to be some differences.
There is also a new STU phone for use in ISDN
networks.
Yes, but quite some time ago a new scheme was introduced.
The newer products typically have a STU-III compatibility mode
so they can interoperate with sites that haven't yet upgraded.