NSA and ECC

[bluemeanie1]

I tried to supply more detail for my post last night, but literally moments after I mentioned Elliptic Curve Cryptography and Wiles' Proof Of Fermat's Last Theorem, bitcointalk.org went down.  Later that night, my website was hacked by a fairly sophisticated hacker.

Anyway, let me establish a few things.  At this point in history it's fairly clear and obvious that NSA et al. are sabotaging not only our cryptographic technology, but our KNOWLEDGE OF CRYPTOGRAPHY.  I don't see it as a coincidence that just years after a very talented mathematician spends at least 5 years exploring the arcane properties of elliptic curves, suddenly, Elliptic Curves become fully accepted methods for cryptography for public use.  I've suggested some months ago that the NSA sabotages our cryptography and most on here thought the idea was ridiculous, today there is PROOF they are doing just that.

For starters most people on here really don't know much about this subject and there is quite a bit of posturing going on.  It's an open forum so that's to be expected.  People pretending to correct other people, while making no useful input to the conversation and posting links of which they don't even understand the content.  Even this thread is riddled with math mistakes that these people posing as experts seem to miss.  For example:

Well, the point must lie on the curve, so it must satisfy   y² = x³ + 7 (mod p).

this equation is wrong and doesn't even work for the point G on the Elliptic Curve.

Gy² = 3032293323238629131397093708741358902059848828670291900490749632219017966501037 851199852273530008094362088328117359813331037184493212192641774435470977600
Gx³ +7 mod p = 28522264212469271830151728101663411104844712793013968865831688505076558508754

no one is checking anything, most on here are just chattering away on subjects to look knowledgeable.  If anyone on here knew about EC math(there are few), they would have pointed out that to express the equation over field (integers) for instance the equation is:

y =  ( x³ + 7 ) ^(1/2) (mod p)


having established that...

the fact is if you followed the progression of events it was indeed highly suspect.  If you review the Fermat Proof you will see that there are people who can process elliptic curves in ways that make just about anything that has ever been discussed on here look pedestrian by comparison.  If you want to understand how the Fermat Proof works, you can start by studying the works of Galois. http://en.wikipedia.org/wiki/Galois , as well as mastering half a dozen higher order math concepts:   cover and lift, finite field, isomorphism, surjective function, decomposition group, j-invariant of elliptic curves, Abelian group, Grossencharacter, L-function, abelian variety, Jacobian, Néron model, Gorenstein ring, Torsion subgroup (including torsion points on elliptic curves here[20] and here[21]), Congruence subgroup, eigenform, Character (mathematics), Irreducibility (mathematics), Image (mathematics), dihedral, Conductor, Lattice (group), Cyclotomic field, Cyclotomic character, Splitting of prime ideals in Galois extensions (and decomposition group and inertia group), Quotient space, Quotient group , meanwhile people on here are claiming all these things are simple, but not offering any useful pointers on all the things the people in this very thread got wrong so far.  In other words- useless nerd.

Part of what the NSA et. al. have been doing for some time is making our crypto algorithms APPEAR simpler than they are.  I sometimes suspect that this Bruce Schneier job.  As I have established, the theory of elliptic curves is very deep and very complex, but rarely do you ever hear any of these ideas applied to our crypto systems.  Once in a while they pop up and the 'experts' pretend as if this is some surprising event that came out of left field.  For quite some time, our spying agencies have sequestered mathematicians, pay them and gag them to create this kind of fog of understanding around whatever math we use to hide our information.  This tradition goes back at least to Alan Turing.

[1715458344]

1715458344

[1715458344]

1715458344

[1715458344]

1715458344

[1715458344]

1715458344

[1715458344]

1715458344

[1715458344]

1715458344

[BurtW]

You may have a point in your post above but claiming that y² (mod p) does not equal x³ + 7 (mod p) for G is incorrect.  Your calculations above are totally incorrect.  Using the same web site you tried to use the correct calculations are:

Hex:
P  = 0xFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFEFFFFFC2F
G_x = 0x79BE667EF9DCBBAC55A06295CE870B07029BFCDB2DCE28D959F2815B16F81798
G_y = 0x483ADA7726A3C4655DA4FBFC0E1108A8FD17B448A68554199C47D08FFB10D4B8

Dec:
P  = 115792089237316195423570985008687907853269984665640564039457584007908834671663
G_x = 55066263022277343669578718895168534326250603453777594175500187360389116729240
G_y = 32670510020758816978083085130507043184471273380659243275938904335757337482424

(G_y)² (mod p) =
 
http://www.wolframalpha.com/input/?i=%2832670510020758816978083085130507043184471273380659243275938904335757337482424%5E2%29+%28mod+115792089237316195423570985008687907853269984665640564039457584007908834671663%29

= 32748224938747404814623910738487752935528512903530129802856995983256684603122
 
(G_x)³ + 7 (mod p) =  

http://www.wolframalpha.com/input/?i=%2855066263022277343669578718895168534326250603453777594175500187360389116729240%5E3+%2B+7%29+%28mod+115792089237316195423570985008687907853269984665640564039457584007908834671663%29

= 32748224938747404814623910738487752935528512903530129802856995983256684603122

[EDIT] at least I know this is all correct

[BurtW]

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.

[bluemeanie1]

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?

[jackjack]

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?

Tell me you're trolling

[marcus_of_augustus]

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.

[rarkenin]

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

[withnail]

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?    


 

[bluemeanie1]

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:

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]

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]

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.

[rarkenin]

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.

[withnail]

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]

AFAIK Bitcoin is unadulterated.

[bluemeanie1]

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.

[BurtW]

My point being, it is very possible that the NSA has secret knowledge of elliptic curves.

It is also possible they do not, right?

[jackjack]

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:

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

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

[rarkenin]

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.

[NewLiberty]

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.

[justusranvier]

For the sake of completeness I'd like to point out that:

John Goyo recalls that two former employees generated the domain parameters.

In no way implies:

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.