Pages:
Author

Topic: NSA and ECC - page 3. (Read 48818 times)

staff
Activity: 4284
Merit: 8808
July 01, 2014, 05:32:15 AM
Well this one doesn't explain G so it's not all the parameters..  and out of all of the the generator point is the only one that looks like an obvious question "where did this come from?"
Yes, but G is security irrelevant for our normal usage in Bitcoin (and generally, except for some contrived examples— e.g. where I need to convince you that I don't know the discrete log of some nothing up my sleeve point X (X!=G), and I picked X long in advance and selected G so that I knew the discrete log of X, but this is contrived and isn't something that I can think of any reason we'd do in Bitcoin.

The term 'fully rigid' comes from safer curves and I complained to DJB that his own curves had no obvious specification for their generator on the site, and (after some back and forth there I gave him a sage implementation of an 'attack' in a contrived protocol) the page was revised to include an argument why the base point selection is irrelevant "What about rigid choices of base points? For each curve considered by SafeCurves, the specified base point is a generator of the specified subgroup. SafeCurves does not place restrictions on the choice of this base point [...]".
legendary
Activity: 1264
Merit: 1008
July 01, 2014, 04:31:02 AM

secp256k1 is "somewhat rigid" not "fully rigid":

Incorrect. The parameters _are_ minimal, there is a script to reproduce them from first principles _in this very thread_.


Thanks as usual gmaxwell.. hanging on your words here!

Well this one doesn't explain G so it's not all the parameters..  and out of all of the the generator point is the only one that looks like an obvious question "where did this come from?"

I also hadn't noticed until recently that b (=7 in secp256k1) can be replaced with anything at all with no effect on all bitcoin operations..  so definitely a waste of time investigating that choice further.      .

staff
Activity: 4284
Merit: 8808
June 29, 2014, 07:54:06 PM
secp256k1 is "somewhat rigid" not "fully rigid":
Incorrect. The parameters _are_ minimal, there is a script to reproduce them from first principles _in this very thread_.

Quote
Given that efficiency claims have been arbitrary.
There is nothing arbitrary about it, with use of the efficient endomorphism enabled libsecp256k1 is (AFAIK) the fastest implementation of ECDSA verification on general purpose hardware in existence, obviously if it contained an implementation of schnorr signatures over this group they'd be even faster due to being able to skip the modular inversion too, but as far as I know it is unparalleled by any other actual ECDSA implementation with comparable security...

Nor are there any obviously strictly superior alternatives, _even today_ much less several years ago, the best contenders have a cofactor greater than one— allowing a non-prime group at a minimum costs several bits of security (e.g. equal or worse to the rho improvement from the efficient endomorphism), and depend on implementation hacks that require private keys to be in a particular sub-group, making things like multiparty key derivation (e.g. BIP32) incompatible with those implementations.
hero member
Activity: 518
Merit: 521
June 29, 2014, 11:30:31 AM
Seed has a generic meaning. Is that the best FUD you can do to avoid addressing the point?
There is nothing in the scheme that we use which can be generically described as a seed either.  Our curve meets the SafeCurves definition of "Fully Rigid" (as I explained to you elsewhere by comparison to curve25519).

Edits:
The parameters in secp256k1 (which is not a NIST selected curve, contrary to your repeated instance) are fixed entirely by performance considerations, similar to the Ed25519 work which you lauded up-thread. There (far) are fewer degrees of freedom in secp256k1 than in SHA1.

secp256k1 is "somewhat rigid" not "fully rigid":

http://safecurves.cr.yp.to/rigid.html

https://bitcointalksearch.org/topic/m.3131916

Also some of us don't want to trust an industry consortium.

http://secg.org/
http://www.secg.org/collateral/sec2_final.pdf

Given that efficiency claims have been arbitrary.

http://safecurves.cr.yp.to

Quote
Subsequent research (and to some extent previous research) showed that essentially all of these efficiency-related decisions were suboptimal, that many of them actively damaged efficiency, and that some of them were bad for security.
sr. member
Activity: 406
Merit: 251
http://altoidnerd.com
January 21, 2014, 04:50:03 PM
Quote
My point being, it is very possible that the NSA has secret knowledge of elliptic curves.

It is very possible santa claus does as well.  Only evidence for a vulnerability is notable in this regard.
legendary
Activity: 1400
Merit: 1013
January 21, 2014, 01:30:18 PM
For the sake of completeness I'd like to point out that:

Quote from: Dan
John Goyo recalls that two former employees generated the domain parameters.
In no way implies:

Quote from: Dan
In particular, no external organization, including any that some now asperse with backdoor insertion, generated the parameters.

It's not possible to prove that an employee of a given organization is not also an employee of a different organization.

The latter statement might be true, but we'll never know since it's unfalsifiable.
legendary
Activity: 1204
Merit: 1002
Gresham's Lawyer
December 26, 2013, 04:33:04 PM
I did not read through all the craps above, but why are people talking about elliptic curves? SHA-256 is not based on elliptic curve cryptography, it is simple prime factorisation cryptography, am I mistaken?

Neither really. ECC is indeed based on elliptic curves. It's used to sign transactions in the bitcoin blockchain.

SHA is not prime factorization. That's RSA, just about. SHA is its own little thing, based on AFAIK a Merkle-Damgard construction.

yeah? I am a newbie when it comes to the inner workings of the bitcoin code, but  I am a bit concerned since NIST standard for pseudo-random number generation based on ECC is compromised. Perhaps bitcoin uses an unadulterated version?

Read this whole thread.  It isn't that long and will give you answers, even as a newbie.
hero member
Activity: 784
Merit: 500
December 23, 2013, 06:07:55 PM
You just can't take modulo on one side since that's not fundamentally following from theorems and not going to lead you anywhere. The (mod 9) annotation applies to the entire line, putting it into modular arithmetic. It looks like you screwed up and now hate us all for your own stupidity.
legendary
Activity: 1176
Merit: 1280
May Bitcoin be touched by his Noodly Appendage
December 23, 2013, 06:04:16 PM
On this planet. The design of ECC revolves around age-old mathematical definitions and theorems with that kind of shorthand, so accept it here.

if

Maybe you did not realize that:

y2 = x3 + 7 (mod p).

is shorthand for:

y2 (mod p) = x3 + 7 (mod p)

how do I say y2 = x3 + 7 (mod p)? in this idiotic language this person just made up that is understood by precisely one person?

Only 100% of mathematicians use that notation
You should track them down to make them learn your notation

have fun kids, the adults can't spend all day playing around on the internet.  have a nice day.
Yeah let the kids play together and never come back
legendary
Activity: 2646
Merit: 1137
All paid signature campaigns should be banned.
December 23, 2013, 05:57:44 PM
My point being, it is very possible that the NSA has secret knowledge of elliptic curves.

It is also possible they do not, right?
sr. member
Activity: 280
Merit: 257
bluemeanie
December 23, 2013, 05:55:35 PM
Oh ok. Do you reckon there is any need to switch bitcoin over to Ed25519 at the moment? Or do you trust the magic numbers in Secp256k1?
If it's possible for any of these ECC systems to be intentionally insecure that would require some profound math which is unknown to the public. If we assume the existence of profound math which is unknown to the public, I do not see a reason to also assume Ed25519 is more secure.

Including it would be a significant burden (a fast ecc signature validation implementation is not simple code, and would not overlap with our existing code) which would carry its own risks.

this is an example of what I'm talking about.

this 'profound math unknown to the public' does exist!  Just look at the Fermat Proof.  It shows that there is an extensive field of knowledge about elliptic curves(developed just a few years before the ECC came into widespread use).  Granted, more people today know these things, but even now it is considered arcane knowledge.  As a matter of fact, much of the Fermat Proof deals exactly with the area of theory that ECC resides.  Are these things pure coincidences?

My point being, it is very possible that the NSA has secret knowledge of elliptic curves.
hero member
Activity: 784
Merit: 500
December 23, 2013, 05:39:05 PM
AFAIK Bitcoin is unadulterated.
newbie
Activity: 12
Merit: 0
December 23, 2013, 05:35:41 PM
I did not read through all the craps above, but why are people talking about elliptic curves? SHA-256 is not based on elliptic curve cryptography, it is simple prime factorisation cryptography, am I mistaken?

Neither really. ECC is indeed based on elliptic curves. It's used to sign transactions in the bitcoin blockchain.

SHA is not prime factorization. That's RSA, just about. SHA is its own little thing, based on AFAIK a Merkle-Damgard construction.

yeah? I am a newbie when it comes to the inner workings of the bitcoin code, but  I am a bit concerned since NIST standard for pseudo-random number generation based on ECC is compromised. Perhaps bitcoin uses an unadulterated version?
hero member
Activity: 784
Merit: 500
December 23, 2013, 05:26:17 PM
I did not read through all the craps above, but why are people talking about elliptic curves? SHA-256 is not based on elliptic curve cryptography, it is simple prime factorisation cryptography, am I mistaken?

Neither really. ECC is indeed based on elliptic curves. It's used to sign transactions in the bitcoin blockchain.

SHA is not prime factorization. That's RSA, just about. SHA is its own little thing, based on AFAIK a Merkle-Damgard construction.
sr. member
Activity: 280
Merit: 257
bluemeanie
December 23, 2013, 05:23:00 PM
I did not read through all the craps above, but why are people talking about elliptic curves? SHA-256 is not based on elliptic curve cryptography, it is simple prime factorisation cryptography, am I mistaken?

might have something to do with the title of this thread: "NSA and ECC".  ECC stands for Elliptic Curve Cryptography.
newbie
Activity: 12
Merit: 0
December 23, 2013, 05:21:12 PM
I did not read through all the craps above, but why are people talking about elliptic curves? SHA-256 is not based on elliptic curve cryptography, it is simple prime factorisation cryptography, am I mistaken?
sr. member
Activity: 280
Merit: 257
bluemeanie
December 23, 2013, 05:13:36 PM
On this planet. The design of ECC revolves around age-old mathematical definitions and theorems with that kind of shorthand, so accept it here.

if

Maybe you did not realize that:

y2 = x3 + 7 (mod p).

is shorthand for:

y2 (mod p) = x3 + 7 (mod p)

how do I say y2 = x3 + 7 (mod p)? in this idiotic language this person just made up that is understood by precisely one person?

have fun kids, the adults can't spend all day playing around on the internet.  have a nice day.
newbie
Activity: 12
Merit: 0
December 23, 2013, 05:12:28 PM
Maybe you did not realize that:

y2 = x3 + 7 (mod p).

is shorthand for:

y2 (mod p) = x3 + 7 (mod p)

because knowing that your correct equation:

y =  ( x3 + 7 ) (1/2) (mod p)

is identical to the equation you corrected.


on what planet would that be?


I don't know which part the rhetorical question refers to. If it is about the notation then indeed it is standard. If it is about the square root part, then in principle it is OK, although one needs to note that not every element in a finite field is a square (after all this is what Gauss' quadratic reciprocity law is all about) and hence one would implicitly agree that the equation is meaningful if and only if the righthand side is defined. This in math literature is called "abuse of notation".

The list of "advanced math topics" you listed above, well, they are all very advanced for high school kids, but only half of them are advanced in any sense for a math major, and none of them should be advanced for a math graduate. Of course a topic like L-functions really emcompasses a large area of research  and is still ongoing, so some part of it is really advanced. For instance, you favorite Fermat's last theorem is not really considered very advanced anymore these days, but things related to the BSD conjecture (google it) is very advanced even for professionals.

You know I am a professional, don't you? Grin   


 



hero member
Activity: 784
Merit: 500
December 23, 2013, 04:51:19 PM
On this planet. The design of ECC revolves around age-old mathematical definitions and theorems with that kind of shorthand, so accept it here.
legendary
Activity: 3920
Merit: 2349
Eadem mutata resurgo
December 23, 2013, 04:48:57 PM
He has history ... and seriously guys please keep the pissing contests to the other sections of the forum.

Need I remind you this is a "Development and Technical Discussion" topic, we have enough crap to wade through elsewhere.
Pages:
Jump to: