Our group is prime and has no sub groups
so any point should work as a G.
so any point should work as a G.
Ah ha! Thanks. I was wondering why the group order needed to be prime.
Topic: NSA and ECC - page 5. (Read 48727 times)
Ah ha! Thanks. I was wondering why the group order needed to be prime.
Our group is prime and has no sub groups so any point should work as G.
This brings up something that I have been wondering about:
If any point will work equally well for G why not use an "easy" point or an "obvious" point?
x = 0 or x = 1 or x = 2n all come to mind.
Anyone have any idea why G is not a more "obvious" starting point?
This brings up something that I have been wondering about:
If any point will work equally well for G why not use an "easy" point or an "obvious" point?
x = 0 or x = 1 or x = 2n all come to mind.
Anyone have any idea why G is not a more "obvious" starting point?
This totally hypothetical situation can be generalized to an arbitraty number of points that are selected before G is selected:
Select P0
P1 = n0*P0
P2 = n1*P1
P3 = n2*P2
...
G = nM*PM
Now all these "premined"
key pairs could maybe be used in some way 
But it seems to me that all of these key pairs are just like any other key pairs that get generated after G is selected, right?
Select P0
P1 = n0*P0
P2 = n1*P1
P3 = n2*P2
...
G = nM*PM
Now all these "premined"
key pairs could maybe be used in some way But it seems to me that all of these key pairs are just like any other key pairs that get generated after G is selected, right?
Wait wait wait... I may be out of my depth here, but isn't the generating point supposed to be able to generate a group of the same size as the order of the curve? If you pick G to be a multiple of an existing point on the curve, then it won't be a "good" generator... it will only generate a smaller sub-group. Am I making any sense?
This totally hypothetical situation can be generalized to an arbitraty number of points that are selected before G is selected:
Select P0
P1 = n0*P0
P2 = n1*P1
P3 = n2*P2
...
G = nM*PM
Now all these "premined" key pairs could maybe be used in some way
But it seems to me that all of these key pairs are just like any other key pairs that get generated after G is selected, right?
Select P0
P1 = n0*P0
P2 = n1*P1
P3 = n2*P2
...
G = nM*PM
Now all these "premined"
key pairs could maybe be used in some way But it seems to me that all of these key pairs are just like any other key pairs that get generated after G is selected, right?
Imaging a Bitcoin' where all coins had to be assigned to some pubkey. And lets also imagine that coins in this system expire, to make them unspendable it assigns them to SHA256("expired"). If I can pick G I can set G to SHA256("expired")*N ... and 1/N is now effectively the private key for SHA256("expired")! So what _looks_ like a nothing up my sleeve address really isn't one, and I can spend those coins.
G cannot be SHA256 * N because both SHA256 and N are scalar numbers in your example. You need a 2D point somewhere in this equation.
Quote
If I can pick G I can set G to ("expired")*N ... and 1/N is now effectively the private key for SHA256("expired")!
It is just a typo, ("expired") is a point on the curve. Imaging a Bitcoin' where all coins had to be assigned to some pubkey. And lets also imagine that coins in this system expire, to make them unspendable it assigns them to SHA256("expired"). If I can pick G I can set G to SHA256("expired")*N ... and 1/N is now effectively the private key for SHA256("expired")! So what _looks_ like a nothing up my sleeve address really isn't one, and I can spend those coins.
G cannot be SHA256 * N because both SHA256 and N are scalar numbers in your example. You need a 2D point somewhere in this equation.
I think this is just a matter of encoding. You can map integers to 2D integer-valued points in a 1-to-1 way.
Imaging a Bitcoin' where all coins had to be assigned to some pubkey. And lets also imagine that coins in this system expire, to make them unspendable it assigns them to SHA256("expired"). If I can pick G I can set G to SHA256("expired")*N ... and 1/N is now effectively the private key for SHA256("expired")! So what _looks_ like a nothing up my sleeve address really isn't one, and I can spend those coins.
G cannot be SHA256 * N because both SHA256 and N are scalar numbers in your example. You need a 2D point somewhere in this equation.
I've finally come up with a way to exploit ECDSA given control of only the generator.
Basically, you set the generator to some random multiple of an existing "public key". Then you can effectively use the "public key" as the secret for signing arbitrary messages from that "public key".
In quotes because the whole idea of a public key is ill defined if you don't yet have a generator.
Imaging a Bitcoin' where all coins had to be assigned to some pubkey. And lets also imagine that coins in this system expire, to make them unspendable it assigns them to SHA256("expired"). If I can pick G I can set G to SHA256("expired")*N ... and 1/N is now effectively the private key for SHA256("expired")! So what _looks_ like a nothing up my sleeve address really isn't one, and I can spend those coins.
I don't think this exposes us to any particular risk, since it only works for one key, and we have no nothing up my sleeve pubkeys, and the parameters for our system were fixed before Bitcoin existed.
But if some nice man from the NSA or Certicom claims to have a nothing up his sleeve pubkey for some protocol or another... perhaps you'd be wise to not believe him.
Basically, you set the generator to some random multiple of an existing "public key". Then you can effectively use the "public key" as the secret for signing arbitrary messages from that "public key".
In quotes because the whole idea of a public key is ill defined if you don't yet have a generator.
Imaging a Bitcoin' where all coins had to be assigned to some pubkey. And lets also imagine that coins in this system expire, to make them unspendable it assigns them to SHA256("expired"). If I can pick G I can set G to SHA256("expired")*N ... and 1/N is now effectively the private key for SHA256("expired")! So what _looks_ like a nothing up my sleeve address really isn't one, and I can spend those coins.
I don't think this exposes us to any particular risk, since it only works for one key, and we have no nothing up my sleeve pubkeys, and the parameters for our system were fixed before Bitcoin existed.
But if some nice man from the NSA or Certicom claims to have a nothing up his sleeve pubkey for some protocol or another... perhaps you'd be wise to not believe him.
Interesting!
So G could be a secret multiple of some number. You say this only works for one key... could it work for a set of related keys? Presumably you could derive an entire set of public/private keys deterministically from the private key you got by choosing G.
Yes, and perhaps set up "rogue" full nodes.
What the heck is a "rogue" full node?Maybe it just takes in transactions but does not send them out! No, wait...
Maybe it makes up a lot of bogus transactions? No, wait...
Hmmm. I guess I don't know.
What is a "rogue" full node? Anyone?
Yes, and perhaps set up "rogue" full nodes.
What the heck is a "rogue" full node?Maybe it just takes in transactions but does not send them out! No, wait...
Maybe it makes up a lot of bogus transactions? No, wait...
Hmmm. I guess I don't know.
What is a "rogue" full node? Anyone?
Yes, and perhaps set up "rogue" full nodes.
What the heck is a "rogue" full node? 
Also, the NSA is not going to crack the crypto used on Bitcoin because their goal is not to actively attack Bitcoin (I doubt the NSA care much about financial regulations). Their goal is to spy on everyone. They're much more likely to do graph analysis of the block chain than worry about the crypto.
Yes, and perhaps set up "rogue" full nodes. 
I've finally come up with a way to exploit ECDSA given control of only the generator.
Basically, you set the generator to some random multiple of an existing "public key". Then you can effectively use the "public key" as the secret for signing arbitrary messages from that "public key".
In quotes because the whole idea of a public key is ill defined if you don't yet have a generator.
Imaging a Bitcoin' where all coins had to be assigned to some pubkey. And lets also imagine that coins in this system expire, to make them unspendable it assigns them to SHA256("expired"). If I can pick G I can set G to SHA256("expired")*N ... and 1/N is now effectively the private key for SHA256("expired")! So what _looks_ like a nothing up my sleeve address really isn't one, and I can spend those coins.
I don't think this exposes us to any particular risk, since it only works for one key, and we have no nothing up my sleeve pubkeys, and the parameters for our system were fixed before Bitcoin existed.
But if some nice man from the NSA or Certicom claims to have a nothing up his sleeve pubkey for some protocol or another... perhaps you'd be wise to not believe him.
Basically, you set the generator to some random multiple of an existing "public key". Then you can effectively use the "public key" as the secret for signing arbitrary messages from that "public key".
In quotes because the whole idea of a public key is ill defined if you don't yet have a generator.
Imaging a Bitcoin' where all coins had to be assigned to some pubkey. And lets also imagine that coins in this system expire, to make them unspendable it assigns them to SHA256("expired"). If I can pick G I can set G to SHA256("expired")*N ... and 1/N is now effectively the private key for SHA256("expired")! So what _looks_ like a nothing up my sleeve address really isn't one, and I can spend those coins.
I don't think this exposes us to any particular risk, since it only works for one key, and we have no nothing up my sleeve pubkeys, and the parameters for our system were fixed before Bitcoin existed.
But if some nice man from the NSA or Certicom claims to have a nothing up his sleeve pubkey for some protocol or another... perhaps you'd be wise to not believe him.
If you write the code.
?
My point is that previously the core devs have suggested an intention to migrate from bag-of-keys to heirarchical deterministic wallets. The argument, AIUI, is that it simplifies backup, but such a decision would seem to negate the argument given in this thread that Bitcoin is largely safe from ECDSA attacks as long as we avoid address reuse.
So, in the light of the concerns over NSA activity in this area, I'm wondering whether it's still the intention to trust our coins (more than at present) to the security of ECDSA.
roy
If you write the code.
If you're asking about BIP32, BIP32 is specific to SECP256k1 (as its results are well defined), but it supports both public and private derivation. The private derivation could be applied to any cryptosystem, though that wouldn't be BIP32 anymore. The public derivation could be applied to at least any ECDSA cryptosystem.
Is it still the intention for Bitcoin-QT to move to BIP 32 in the future?
roy
pardon me the lame question, but what is the actual formula to calculate the order (N), from the A & B?
can I calc it myself, using a python shell, or do I need a six dimensions math library?
You can use sage. They have an online version of their shell here. Here's how you calculate the order of secp256k1:can I calc it myself, using a python shell, or do I need a six dimensions math library?
Code:
sage: F = FiniteField(0xFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFEFFFFFC2F)
sage: F
Finite Field of size 115792089237316195423570985008687907853269984665640564039457584007908834671663
sage: C = EllipticCurve(F, [ 0, 7 ])
sage: C
Elliptic Curve defined by y^2 = x^3 + 7 over Finite Field of size 115792089237316195423570985008687907853269984665640564039457584007908834671663
sage: print(C.cardinality())
115792089237316195423570985008687907852837564279074904382605163141518161494337
sage: hex(C.cardinality())
'fffffffffffffffffffffffffffffffebaaedce6af48a03bbfd25e8cd0364141'
sage: G = C.point((0x79BE667EF9DCBBAC55A06295CE870B07029BFCDB2DCE28D959F2815B16F81798, 0x483ADA7726A3C4655DA4FBFC0E1108A8FD17B448A68554199C47D08FFB10D4B8))
sage: G
(55066263022277343669578718895168534326250603453777594175500187360389116729240 : 32670510020758816978083085130507043184471273380659243275938904335757337482424 : 1)
sage: G.order()
115792089237316195423570985008687907852837564279074904382605163141518161494337
sage: hex(G.order())
'fffffffffffffffffffffffffffffffebaaedce6af48a03bbfd25e8cd0364141'
An explanation on G would be nice to have, yes. As for p, someone would need to dig into the implementation of optimized reduction algorithms to explain why t being less than 1024 is helpful.
The thing is that they went for largest t less than 1024. They could have gone for largest prime less than 2^256 or (2^256 - 2^32), but they went for smallest prime greater than (2^256 - 2^32 - 2^10).
That helps to explain p a bit more. (In other words, we have an alternative explanation that doesn't involved 2^10).
Can you run the same check for 2^256 - t.
Quote
I guess we can narrow down our investigation to the G point and the P (since we still don't seem to know what is so great about 1024 aka 2^10).
An explanation on G would be nice to have, yes. As for p, someone would need to dig into the implementation of optimized reduction algorithms to explain why t being less than 1024 is helpful. I've implemented a secp256k1 specific reduction algorithm before (link to source), but it's been awhile and I didn't take the time to intuitively understand exactly which Mersenne-like primes make the method work effectively. Nor do I understand why they chose the smallest p, and not the largest. Perhaps that particular p allowed a small (a,b) for the curve? I recall there being better (less code required) Mersenne-like primes to choose.I'm not sure if this is the optimisation you're after, but section 2.2.6 of http://www.springeronline.com/sgw/cda/pageitems/document/cda_downloaddocument/0,11996,0-0-45-110359-0,00.pdf (from here: http://cacr.uwaterloo.ca/ecc/) describes the property as: the prime must be a sum or difference of powers of 2^32. secp256k1 doesn't have this property exactly, which is why your code has all that shifting in it.
Here's another interesting data point. If we search all primes of the form 2**256 - 2**32 - t, starting from t = 0 to t = infinity, the first prime order curve with a = 0 and b < 1000 is the secp256k1 curve. Code:
That helps to explain p a bit more. (In other words, we have an alternative explanation that doesn't involved 2^10).
Code:
from sage.all import *
def find_group (prime):
K = FiniteField (prime)
for b in xrange (1, 1000):
E = EllipticCurve (K, [0, b])
if E.order () in Primes ():
return b, E.order ()
return None
p = 2**256 - 2**32 + 1
while True:
p -= 1
if not p in Primes ():
continue
result = find_group (p)
if result is not None:
break
print "Found curve: "
print "p = %X" % p
print "a = 0"
print "b = %d" % result[0]
print "N = %X" % result[1]
That helps to explain p a bit more. (In other words, we have an alternative explanation that doesn't involved 2^10).
Jump to: