NSA and ECC - page 3. | Bitcointalksearch.org

gmaxwell

staff

Activity: 4172

Merit: 8419

Quote from: hashman on July 01, 2014, 05:31:02 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 [...]".

hashman

legendary

Activity: 1264

Merit: 1008

Quote from: gmaxwell on June 29, 2014, 08:54:06 PM

Quote from: AnonyMint on June 29, 2014, 12:30:31 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_.

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. .

gmaxwell

staff

Activity: 4172

Merit: 8419

Quote from: AnonyMint on June 29, 2014, 12:30:31 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.

AnonyMint

hero member

Activity: 518

Merit: 521

Quote from: gmaxwell on October 14, 2013, 01:56:13 PM

Quote from: AnonyMint on October 14, 2013, 01:54:31 PM

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:

Quote from: gmaxwell on October 13, 2013, 03:58:03 PM

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.

Altoidnerd

sr. member

Activity: 406

Merit: 251

http://altoidnerd.com

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.

justusranvier

legendary

Activity: 1400

Merit: 1009

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.

NewLiberty

legendary

Activity: 1204

Merit: 1002

Gresham's Lawyer

Quote from: withnail on December 23, 2013, 06:35:41 PM

Quote from: rarkenin on December 23, 2013, 06:26:17 PM

Quote from: withnail on December 23, 2013, 06: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?

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.

rarkenin

hero member

Activity: 784

Merit: 500

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.

jackjack

legendary

Activity: 1176

Merit: 1233

May Bitcoin be touched by his Noodly Appendage

Quote from: bluemeanie1 on December 23, 2013, 06:13:36 PM

Quote from: rarkenin on December 23, 2013, 05: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.

if

Quote from: BurtW on December 23, 2013, 04:52:31 PM

Maybe you did not realize that:

y² = x³ + 7 (mod p).

is shorthand for:

y² (mod p) = x³ + 7 (mod p)

how do I say y² = x³ + 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

Quote from: bluemeanie1 on December 23, 2013, 06:13:36 PM

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

BurtW

legendary

Activity: 2646

Merit: 1136

All paid signature campaigns should be banned.

Quote from: bluemeanie1 on December 23, 2013, 06:55:35 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?

bluemeanie1

sr. member

Activity: 280

Merit: 257

bluemeanie

Quote from: gmaxwell on September 12, 2013, 02:37:29 AM

Quote from: drawingthesun on September 12, 2013, 02:13:42 AM

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.

rarkenin

hero member

Activity: 784

Merit: 500

AFAIK Bitcoin is unadulterated.

withnail

newbie

Activity: 12

Merit: 0

Quote from: rarkenin on December 23, 2013, 06:26:17 PM

Quote from: withnail on December 23, 2013, 06: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?

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?

rarkenin

hero member

Activity: 784

Merit: 500

Quote from: withnail on December 23, 2013, 06: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?

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.

bluemeanie1

sr. member

Activity: 280

Merit: 257

bluemeanie

Quote from: withnail on December 23, 2013, 06: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?

might have something to do with the title of this thread: "NSA and ECC". ECC stands for Elliptic Curve Cryptography.

withnail

newbie

Activity: 12

Merit: 0

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?

bluemeanie1

sr. member

Activity: 280

Merit: 257

bluemeanie

Quote from: rarkenin on December 23, 2013, 05: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.

if

Quote from: BurtW on December 23, 2013, 04:52:31 PM

Maybe you did not realize that:

y² = x³ + 7 (mod p).

is shorthand for:

y² (mod p) = x³ + 7 (mod p)

how do I say y² = x³ + 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.

withnail

newbie

Activity: 12

Merit: 0

Quote from: bluemeanie1 on December 23, 2013, 05:07:08 PM

Quote from: BurtW on December 23, 2013, 04:52:31 PM

Maybe you did not realize that:

y² = x³ + 7 (mod p).

is shorthand for:

y² (mod p) = x³ + 7 (mod p)

because knowing that your correct equation:

y = ( x³ + 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

rarkenin

hero member

Activity: 784

Merit: 500

On this planet. The design of ECC revolves around age-old mathematical definitions and theorems with that kind of shorthand, so accept it here.

marcus_of_augustus

legendary

Activity: 3920

Merit: 2349

Eadem mutata resurgo

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.

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