NSA and ECC

[jackjack]

They say

the order #E(Fq) of the elliptic curve is divisible by a large prime number n (say n >= 2^160)

So their n (random prime number) isn't our n (order of the EC) (?)


With p=FFFFFFFF FFFFFFFF FFFFFFFF FFFFFFFF FFFFFFFF FFFFFFFF FFFFFFFE FFFFFC2F
and n=FFFFFFFF FFFFFFFF FFFFFFFF FFFFFFFE BAAEDCE6 AF48A03B BFD25E8C D0364141

Code:

p^1  - 1 % n = 000000000000000000000000000000014551231950b75fc4402da1722fc9baed
p^2  - 1 % n = 9d671cd581c69bc5e697f5e1d12ab7e0bd57efff7678bda14d8f2b05a6047402
p^3  - 1 % n = ac7a8c3d903db4f5506b3cd06358dbb83c0356f1426f6154796949ebcaf2c963
p^4  - 1 % n = 4a9039c8e0cf1d2e546bf94562b4cdd3f931a37f7210ea3d2448e17471c13846
p^5  - 1 % n = 13257c198a85197265443fa89aac96ccdac5495c438984dc734659a59cd53681
p^6  - 1 % n = 48e1ad01feb908300c9be1bd9d9d7afe6b7d929d4954c6e73f5b35d6d38c8ce7
p^7  - 1 % n = 98c10d11ce5ba0e56349034ff8f0078cefdbb6462b5fadb02b77e6f9b15e63a0
p^8  - 1 % n = d450873664cc63bee8debf0810f4d3885087441407bdebb24ea9c33ab125b3cc
p^9  - 1 % n = 3763ce8ef848dd69408119a522e171d9ad2132e2eb349967bebdea391b96d024
p^10 - 1 % n = 3e07117dea68ea380611113c0988e37608059d1e8315f2dc397457536359b05a
p^11 - 1 % n = 1c16652e13748ed710097fe21c21c0ee3cf4dddca456a0d0900601f2c136da93
p^12 - 1 % n = 0a95c2539eba1d41b55552516bf5a46a2417109fb45813aecc859ccab824fd91
p^13 - 1 % n = a12715798e6b78096c12e8e73a5e1550e4184561cafbb5dbfb34ffcacbbeba6c
p^14 - 1 % n = 637f4698784525945df4080fa4334351f3a8137f01d1b2118cfe4f00a79ff5eb
p^15 - 1 % n = 4adf22895fd4ced7120a9b5bd1bedb0358b25073a52879da089054cef992b7f0
p^16 - 1 % n = cc43712c43c1b51af2e29020520ae03abccd9f5c3ffdeb0c94a585ac91372278
p^17 - 1 % n = ec473f03332198fd61c411b184e81b7093423dd2a245fa278e111aac1c9c7af6
p^18 - 1 % n = 2abbbd0960d7884ac5648cfd88fd6a8485fea0af29300256d827369ccd72db9b
p^19 - 1 % n = 4ced2137a0dc99c48f9203c2dd9b423fd31d95998b29165efb48bf868170e857
p^20 - 1 % n = ac95279e81042a93568de45d91f29ccdd83acb8097ec611ba84fcace3e140ed1

[BurtW]

I believe the order #E(Fp) of our elliptic curve n is prime and is in fact their n.

I think this is also validated by the fact that h = 1.

But hey, I am just treading water here...

[NewLiberty]

Hmm I wonder how many colours of coloured coin it takes to [something something] a blockchain?

(You only need four whatzits to build a DNA strand? Hmm....)

Think like the game "sprouts".

(And maybe read Peirs Anthony's "Macroscope" while you're at it.)

One point is a point, two is a line, three is a circle.

If the fourth is inside the circle, it is surrounded, no luck there.

If the fourth is outside the circle, how you gonna connect it to the other three without surrounding any of them?

-MarkM-

Congratulations to your child-self.
The personal implications of your avatar icon are suddenly more manifold.

[fpgaminer]

I believe the order #E(Fp) of our elliptic curve n is prime and is in fact their n.

I think this is also validated by the fact that h = 1.

To be specific, n in BurtW's quote is any prime number that divides the order of the elliptic group.  In our case, the order of the secp256k1 group is prime, which means n can only be the order of the elliptic group (convenient!).

Given that our elliptic group is of prime order, we know a few things.  There are no subgroups.  It's cyclic.  It's abelian.  To the best of my knowledge, that also implies that we can pick any element of the group, except the identity element, to be our generator.  Which makes me wonder how secp256k1's generator was picked.  I don't yet know what restrictions one must apply to the generator.  I can only assume it doesn't matter ...

By the way, I ran a little experiment.  Given our finite field, and setting a to 0, 7 is the first (counting from 0) value for b that results in a prime order elliptic group.  I don't understand GLV well enough to know what restrictions it places on a and b, but if we have to pick a curve where a is 0, it seems like b being 7 would be a logical choice (again, given our finite field).

[BurtW]

This is the reply I got form Dan Brown the current SECG chair:

Hi Burt,

Rob forwarded your email to me.

I am the current SECG chair, so I will try to provide a partial answer. I did not know that BitCoin is using secp256k1.  Indeed, I am surprised to see anybody use secp256k1 instead of secp256r1.  With my SECG chair hat on, I am pleased because this curve is a pure SECG curve, not a NIST curve (but see * below).

Minor aside: SECG updated SEC2 in 2010.  The curve secp256k1 is now in Section 2.4, which is smaller because SECG removed the very small curves.

I was not involved in the parameter selection for secp256k1, and may not have even been a Certicom employee at the time of secp256k1 parameter selection.  I am going to assume that you are mainly concerned about a potential backdoor, given the coincidence of your query with certain news coverage.  I will attempt to address this concern mainly by looking directly SEC2 document and parameters.

1. The defining Weierstrass coefficients (a,b) of the curve are (0,7).  The SEC2 document says, in Section 2.1, “The recommended parameters associated with a Koblitz curve were chosen by repeatedly selecting parameters admitting an efficiently computable endomorphism until a prime order curve was found”.  Furthermore, I see that the small values 0 and 7 are certainly nothing-up-my-sleeve values.  More precisely, they cannot be the result of a malicious exhaustive search of curve selection until the curve lands in a weak class.  So, the only risk is that the special class, with small coefficient and efficient endomorphism is somehow weak.  I am not aware of any such weakness. Indeed, I highly doubt such a weakness, at least in the ECDLP: it would constitute a major breakthrough in ECDLP.  Also, some ECC theorists have established the equivalence ECDLP between curves of the same order, via something called isogenies.  I am not expert in that area, but it may imply that mere fact that the curve coefficients are small is insufficient to constitute a weak class of ECDLP.

2. The defining field size p seems to be a 256-bit prime of the special form 2^256-s where s is small.  This form is for efficiency.  I am not sure why this particular value of s is chosen, because I expect that smaller s could be found.  Nevertheless, there does not seem to be too much wiggle room in this choice of s, because s itself also has a special form: s = 2^32 + t, where t < 1024.  I would not be surprised if s was the smallest value of this form, but I did not check.  In any case, there are no known weak classes of prime order field for elliptic curves. 

3. The base point G is something I cannot explain, but the general understanding, at the time and still now, is that the base point G cannot contain a backdoor in the main problem underlying ECC, namely ECDLP and ECDHP. Indeed, random self-reducibility applies to prove that the choice of G is irrelevant for most versions of these problems.  Some cryptographic schemes, including ECDSA, seem to depend mildly on some other problems, in which the choice of G may be more relevant.    In particular, the ECDSA verification of a signature (r,s) includes a check that r is not zero.  If this check is dropped, then there is a possibility that party who chose G can have chosen G in such that to make some signature (0,s) valid for a particular message m.  (For details and examples, see my chapter in Advances in Cryptology II, or my paper “Generic Groups, Collisiion Resistance, and ECDSA”, or my IACR eprint “The One-Up Problem for ECDSA”.)   I strongly doubt that G is malicious, because these properties were not widely known at the time, and the adversary seems to have little to gain, the verifier has to be faulty.

4. Rob Lambert and John Goyo were present at the time Certicom generated the secp256k1 parameters, but were not directly involved either.  John Goyo recalls that two former employees generated the domain parameters.  In particular, no external organization, including any that some now asperse with backdoor insertion, generated the parameters.  We will continue to investigate our records and archives. 

I hope that the four points above address your main concerns, despite them not fully answering your questions.  Feel free to request further clarification, but, unfortunately, I am not sure if we have maintained all the archives.

(*) With my SECG chair hat off now, I recognize some validity of the following argument: the NIST curves have received more scrutiny than the other SECG curves, because the prominence of NIST created a greater incentive to study these curves.  Putting my SECG chair back on, a mild counterargument to the latter argument is that: none of the known weak classes of curves resulted by targeting particular parameters. Rather they are results from basic research on ECC. 


Best regards,

Dan

[Etlase2]

Very interesting, thanks for that Burt.

[Carlton Banks]

This is the reply I got form Dan Brown the current SECG chair:

Hi Burt,
[...]
I hope that the four points above address your main concerns, despite them not fully answering your questions.  Feel free to request further clarification, but, unfortunately, I am not sure if we have maintained all the archives.

Technical details aside (not qualified to comment), this comes across as an unambiguous "yes, no, ....maybe". Well, I suppose he could've skimped on information, and he certainly did not do that. But lines like the bolded text are concerning; you'd think they would be pretty meticulous, given that any rogue mathematician who deliberately did not disclose or document flaws and promptly moved to China for a "quiet retirement" could be a candidate for the "disposition matrix"  .

Bitcoin Foundation should be tendering research grants (or perhaps more appropriately commissioning long term studies) specifically to attract cryptographers of the highest calibre. At least in the more medium term that is. I fail to see how contributing mathematical prowess to the fundamental substance of what could morph into the 21st century monetary system couldn't attract the right talent. And the average Bitcoiner has to pay how much to join, only to discover this is not happening for whatever reason? This should be a serious endeavour, and their current focus is a political meat shield. [/cynical bullishness]

[BurtW]

Technical details aside (not qualified to comment), this comes across as an unambiguous "yes, no, ....maybe".

I think he did a great job answering our questions to the best of his ability under the circumstances (people who actually did the work are no longer with SECG.

Bitcoin Foundation should be tendering research grants (or perhaps more appropriately commissioning long term studies) specifically to attract cryptographers of the highest calibre.

I am totally impressed by the calibre of the math, programing and cryptographers we have already.  Just read this very thread.

I am very satisfied with his answers.  The only thing left is to find out (if we can) is exactly how the random parameters were selected.

I am waiting for responses to my emails on that subject.

[Carlton Banks]

Technical details aside (not qualified to comment), this comes across as an unambiguous "yes, no, ....maybe".

I think he did a great job answering our questions to the best of his ability under the circumstances (people who actually did the work are no longer with SECG.

Bitcoin Foundation should be tendering research grants (or perhaps more appropriately commissioning long term studies) specifically to attract cryptographers of the highest calibre.

I am totally impressed by the calibre of the math, programing and cryptographers we have already.  Just read this very thread.

I am very satisfied with his answers.  The only thing left is to find out (if we can) is exactly how the random parameters were selected.

I am waiting for responses to my emails on that subject.

I am similarly more than impressed with the abilities of our current development team. What I'm suggesting is a dedicated team for long-term analysis and theoretical work, not only accomplished software developers that have well honed cryptography knowledge who apply pre-existing work to this project. You'll notice if you look at the SCIP thread that one well seasoned developer admits to being out of his depth at a certain stage, and he's certainly a capable developer.

The answers he gives can be interpreted as given, but could also be a well devised evasion tactic, although there is no way of knowing for certain at this stage. I commend that you did this, despite any misgivings. As I say, it could be that he is being totally upfront and honest, so whatever the eventual assessment, you have done us all a service.

[TierNolan]

I am very satisfied with his answers.  The only thing left is to find out (if we can) is exactly how the random parameters were selected.

I did a quick check on this assumption

Nevertheless, there does not seem to be too much wiggle room in this choice of s, because s itself also has a special form: s = 2^32 + t, where t < 1024.  I would not be surprised if s was the smallest value of this form, but I did not check.

The test code finds all primes of the form p = 2^256 - 2^32 - t where t < 1024.

Code:

import java.math.BigInteger;

public class PrimeTest {

        public static void main(String[] args) {

                BigInteger a = BigInteger.valueOf(2).pow(256);
                BigInteger b = BigInteger.valueOf(2).pow(32);

                BigInteger top = a.subtract(b);

                for (int t = 0; t < 1024; t++) {

                        BigInteger test = top.subtract(BigInteger.valueOf(t));

                        if (test.isProbablePrime(1024)) {
                                System.out.println(test.toString(16) + " (t = " + t + ")");
                        }

                }

        }
}

The result is

Code:

fffffffffffffffffffffffffffffffffffffffffffffffffffffffefffffef9 (t = 263)
fffffffffffffffffffffffffffffffffffffffffffffffffffffffefffffe99 (t = 359)
fffffffffffffffffffffffffffffffffffffffffffffffffffffffefffffe97 (t = 361)
fffffffffffffffffffffffffffffffffffffffffffffffffffffffefffffe19 (t = 487)
fffffffffffffffffffffffffffffffffffffffffffffffffffffffefffffd1d (t = 739)
fffffffffffffffffffffffffffffffffffffffffffffffffffffffefffffc4b (t = 949)
fffffffffffffffffffffffffffffffffffffffffffffffffffffffefffffc2f (t = 977)

The prime for t = 977 is the one that was selected for the curve.  It is the highest t that is lower than 1024.

[piotr_n]

The explanations are exactly like the one I had expected to be. I am quite sure you would receive a very similar ones from NIST.

It all can all be wrapped in one sentence:
Even though we are a highly professional and experienced scientists, who were assigned with a formal task to select a proper constants that would assure a security of the encryption, we have no idea how and why the specific constants were selected, but we are almost certain that none of them can weaken EC security, therefore you have nothing to worry about.

Professional scientists like hell

[BurtW]

piotr_n:

Your post is totally unfair and uncalled for.  Having been a contributing member of several technical specifications I can assure you that his email rings true.  Just try to find out how any decision was made on any technical specification and you will find that most of the decisions and grunt work are done by emails, phone calls, hallway conversations, conversations over meals during face to face meetings, etc.

Unless you actually participated in the decision the reason for most technical decisions in all the technical specifications I have worked on would be almost impossible to find.  For example, one time we were having a problem where the disk drive I was designing would not properly work in master/slave mode with a competitor’s disk drive.  I called up the competitor’s lead architect and we re-designed the master/slave protocol right there, on the spot, over the phone.  Our two companies implemented it and it eventually found its way into the ATA specification and is still there to this day.

The fact that the prime selected has the highest possible value of t lower than 1024 looks to be the answer to that particular question – unless we can find the person who actually selected the prime number, or the people present in the meeting that day when he presented the number and explained his selection to them.

This guy did not need to take the time to answer my query.  He did not know me from Adam.  If the situation was as you described he would have simply not answered my email and been done with it.

TierNolan:

Thanks for that!  Great work!

[piotr_n]

Sorry BurtW, but I totally disagree.

What is the point of creating a standard if you cannot justify the values you chose for it, nor you are able to reproduce a path that was taken to calculate them?

This is not a science!
This is a sloppy designing at best.
And at worst? Oh, let's hope not...

[NewLiberty]

Sorry BurtW, but I totally disagree.

What is the point of creating a standard if you cannot justify the values you chose for it, nor you are able to reproduce a path that was taken to calculate them?

This is not a science!
This is a sloppy designing at best.
And at worst? Oh, let's hope not...

His answer appears honest (at least so far as we've been able to check), rather than arguing from authority as you claimed.  He admits what he doesn't know, and why.  He made reasonable guesses at some points and stated they were such.

I agree that the answer is not perfect nor complete, but neither was your characterization of it accurate.  Keep in mind that it didn't take a FOIA request to get this, it was given freely and without lawyers in a friendly, informal and collegian manner.

It might look different were it a submission to a peer reviewed journal and meant to withstand critical review, instead it was a VERY swift and candid response at no benefit to himself.  Gratitude is warranted.

What you are seeking (a justification of values along with the path taken to calculate) may yet come, but that will take them some research and effort.  Just our asking for this may stimulate such an effort.  We are helping to guide them to do more meaningful work in light of the current reports and questions raised.

[piotr_n]

I think you guys got a wrong idea.
I was not criticizing the guy who wrote that email - not at all.
In fact I also find him as a very nice and sincere person who is trying to help.

Still, it does not help us at all, does it?
So let me quote again what I believe all the other answers concerning this issue will be about:

Even though we are a highly professional and experienced scientists, who were assigned with a formal task to select a proper constants that would assure a security of the encryption, we have no idea how and why the specific constants were selected, but we are almost certain that none of them can weaken EC security, therefore you have nothing to worry about.

Making the sarcastic comment, my only point was: if anyone will manage to get an answer that goes beyond what I had already figured, then we can talk..
I will be more than happy to turn out as an asshole again, if this is the price for finding out where these values come from.
And if we don't ever get to know how the values in question were chosen - well, feel free to perceive me as an asshole, anyway.

[BurtW]

Does anyone have a copy of ANSI X9.62 I can borrow?  Or does anyone know of a free link?  I would like to read it but don't really want to shell out the $100 for it.

Have not read it yet but this looks to be interesting:  http://cs.ucsb.edu/~koc/ccs130h/notes/ecdsa-cert.pdf

Part:

The Elliptic Curve Digital Signature Algorithm (ECDSA) is the elliptic curve analogue
of the DSA. ECDSA was first proposed in 1992 by Scott Vanstone [108] in response
to NIST’s (National Institute of Standards and Technology) request for public comments
on their first proposal for DSS. It was accepted in 1998 as an ISO (International
Standards Organization) standard (ISO 14888-3), accepted in 1999 as an
ANSI (American National Standards Institute) standard (ANSI X9.62), and accepted
in 2000 as an IEEE (Institute of Electrical and Electronics Engineers) standard (IEEE
1363-2000) and a FIPS standard (FIPS 186-2). It is also under consideration for inclusion
in some other ISO standards. In this paper, we describe the ANSI X9.62
ECDSA, present rationale for some of the design decisions, and discuss related security,
implementation, and interoperability issues.

Since ANSI X9.62 was accepted into IEEE as 1363-2000 I can probably get it there since I am a member.

[BurtW]

Here is a suggestion from Dan on the seeds for the random curves:  Convert them to ASCII and see what pops!

Hmm,

I just checked some of the seeds for the non-NIST random curves in SECG.

I noticed that some of the seeds look similar to each other, and had very non-random looking hex representations.  So, I just converted them to ASCII, and noticed that a large middle portion of some of the seeds contain the string “MinghuaQu”, which is the name of one of the inventors of MQV, and the person who was generating the seeds.  I would not be surprised if the remainder of the seeds also had some meaning, with just a little part left for the necessary searching.  If so, then the curves are really nothing-up-sleeve type values.  Unfortunately, most of these curves may be too small by today’s recommendations.

Best regards,

Dan

It would be fun to convert all the seeds we can find, especially the seeds used for the curves we are interested in, to ASCII and see what is there.

[maaku]

Anyone have contact info for MinghuaQu ?

[gmaxwell]

I'd already tried hextoasciiing the p256r curve's seed, before ever commenting on it, no such joy. (I'd also hoped to find a similar answer to our generator, but no such question, as the message said though— the generator isn't a known cause for concern, as you can generally convert numbers relative to one generator relative to another trivially. I'd though perhaps the generator would result in low hamming weight in the multiplies, allowing some stems to be avoided but it seems not)

[niko]

 Keep in mind that it didn't take a FOIA request to get this, it was given freely and without lawyers in a friendly, informal and collegian manner.

FOIA only applies to the US government agencies, it is irrelevant in the context of secg, fujitsu, certicom,etc. You might be able to get something from the US-based governmental member (NIST).