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

Tell me you're trolling

on what planet would that be?

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.

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

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:


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.

"somewhat mysterious region of mathematical knowledge"

no it is not. it might be so 100 years ago but not now. It is a generalization of ordinary arithmetic (ordinary arithmetic is arithmetic on a "flat line") and it is a major branch of present day math.

See a mathematician's take on NSA backdoor

http://jiggerwit.wordpress.com/2013/09/25/the-nsa-back-door-to-nist/

this will appear in AMS Notices.

As a lot of folks have pointed out, it is unlikely that SHA-2 has been compromised, since to compromise it you need genuine breakthrough in math (say, progress towards P vs NP, if you know what it is) not just sloppiness with malicious intentions. I mean if you can crack SHA-2 then getting insanely rich is the least you can do; try domination of the world, dude.



     

the fact is Elliptic Curve mathematics are a somewhat mysterious region of mathematical knowledge.  They were used in the famous proof of Fermat's Last Theorem: http://en.wikipedia.org/wiki/Wiles%27_proof_of_Fermat%27s_Last_Theorem , thus it's not implausible to suggest that perhaps there are aspects to Elliptic Curves that are not public information.  The Fermat Proof was incredibly complex and verbose.  Note that Fermat's Last Theorem was only proven very recently, here's something interesting

  an Elliptic Curve is

 

  while Fermat's Last Theorem is

  that no three positive integers a, b and c can satisfy the equation
 
  if n is an integer not equal to one or two.

Elliptic Curve Cryptography relies on the supposed computational difficulty of the Discrete Logarithm Function.  http://www.certicom.com/index.php/52-the-elliptic-curve-discrete-logarithm-problem

Supposedly, according to modern public crypto knowledge, there are no shortcuts to solving this problem.  As long as there are no shortcuts, then ECC remains secure.  Interestingly, Fermat's Last Theorem was proven in 1993, and ECC came into widespread use around 2005 [1].  Coincidence?

 [1] although it was suggested earlier

Please go back and read this entire thread, especially the part where this exact idea was brought up and the part where I personally emailed the current committee head and did get some of the answers to our questions.

BTW out of all the threads I have ever participated in this one is, by far, my favorite.

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:

As an aside: I've now removed AnonyMint from this thread. (Also, note that he edited the message after I responded to it, my quote is the version at the time I responded)

Seed has a generic meaning.

http://www.thefreedictionary.com/seed
8. A source or beginning

Is that the best FUD you can do to avoid addressing the point?

Is the only way you know how to discuss and debate is via personal insults?

Btw, I guess you forgot that is the first time you've told me that.  

Edit: since he edited his reply below, I will add he has deleted all my retorts which have refuted his reply below (specifically refuting full rigidity, his claim of decreased degrees-of-freedom, and his claim that he isn't being disingenuous). He even deleted my attempt to add my retorts to my thread. I would add a link to my retorts (and I bet you can find them if you really want to), yet he would then likely delete this post or edit or some other infantile, weasel, trolling behavior. Enjoy the bliss.

The edit I made which gmaxell refers to in his reply below is the definition of "seed" quoted above, as if he doesn't know the English language.

Also he edited his upthread post to remove his large point size text that I quoted above. Good to see he is embarrassed and had to backtrack on his trolling.

Their rigidity page doesn't appear to explain the choice of generator for any of their "Fully rigid" cases.  See upthread that it would be preferable for the generator to be rigid too, if not essential.

Came across this on HN, thought it would be useful here: SafeCurves: choosing safe curves for elliptic-curve cryptography.

There is no seed in the scheme Bitcoin uses, I am not sure how many times you will need to be told this.

He is also worried about math breakthroughs and the shorter key sizes of ECC, and he recommending never use unless required:

https://www.schneier.com/crypto-gram-9911.html#EllipticCurvePublic-KeyCryptography

And he recommends using symmetric instead of public-key (so Lamport instead):

https://www.schneier.com/blog/archives/2013/09/the_nsas_crypto_1.html

And the Koblitz curve explanations doesn't remove the lack of transparency in the seeds:

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


Until the government requires them to do so because Bitcoin becomes a tax-haven. The G20 has been ramping up their plans to go after all tax havens.


Disagree that he said that, also disagree that makes Bitcoin safe. See links above.


That bright spot is not assured:

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

Not for our G.

It should be possible, with an expensive search (e.g. >2^32 tries), to find a G that results in a lower hamming weight in the multiplies in a particular implementation and get a very small speed improvement. But I can find nothing about our G that suggests such a thing was done.

Now I am really out of my depth here but since P = n * G is a very commonly needed operation is is faster or simpler to use, for example the point:

x = 1, y = 29896722852569046015560700294576055776214335159245303116488692907525646231534 as G

In other words, is there any possible efficiency argument that can be made for the selection of G?

In my gut I expect that any G is equally computationally difficult as far as P = n * G goes.  Correct?

We aren't dealing with your ordinary, run-of-the-mill integers here.  We're dealing with a finite field!  y² = 1³ + 7 has a solution (two, in fact).  It's 4218F20AE6C646B363DB68605822FB14264CA8D2587FDD6FBC750D587E76A7EE.  Square that number, modulus our prime, and you get 8.

So yeah, G could have been selected as an obvious, nothing-up-my-sleeve number.  It wasn't.  I'd bet on it being some sentimental thing, like the hash of the author's name or something.

...

1 : 29896722852569046015560700294576055776214335159245303116488692907525646231534  is a point on our curve, as is
2 : 46580984542418694471253469931035885126779956971428003686700937153791839982430

and so on. The first missing x, other than zero obviously, is 5.

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

So x=0, means y²=7, which has no solution for an integer y, so there is no point on the curve with x coordinate 0.
Same for x=1,2,3,4,... I think you can go on for a while before finding a solution that way.

I think there is no "obvious" solution, so one starts with a "random" value for x and incrementing this until x³+7 has an integer square root.

I saw some posts of people generating their own curves incorporating hex-art and/or hashes of "copyright notes" into the value + a counter.
It really should not be different, the only thing is everybody needs to use the same G otherwise the key pairs (public/private key) don't match.

Not being able to answer that was why I spent a bunch of time trying to come up with "attacks" that selection of a non-obvious G could yield. But all I could come up with doesn't seem to be too much. ::shrugs::

Not just that, but if there are subgroups there are reductions that allow you to solve the DLP with basically no more work than solving it over a field thats the size of the largest factor.