World


January 26, 2013, 09:19:10 PM 

This is symmetric cryptography. Ie. cryptography where the encrypting and decrypting keys are the same. It explains how two people can agree on a shared secret key when their communication is intercepted by a third party, without that third party being able to figure out what the key is. This is called the DiffieHellman key exchange. Bitcoin uses asymmetric cryptography, where the are two keys: the public and the private, and one encrypts and the other decrypts. ArtOfTheProblem is really good at explaining this stuff for nonmathematicians though. They've also made a video on public key cryptography. This one covers RSA. http://www.youtube.com/watch?v=wXBV_Keiu8Really great video! They are good explaining the extreme complex concepts we are dealing with. The important thing, in my opinion, is understanding the one way function. Both videos explain it with the same color mixing examples. really liked both videos ^ ,but I would like to see simple video with ECC Public Key Cryptography be the same author Brit Cruise I asked him and he answered that he'll be making one "in the not too distant future": http://www.youtube.com/watch?v=wXBV_Keiu8&lcor=1&lc=Bam_R8yp790_LA4eLMLqV6QUQ2iJ5Z4T4Iywos68Z4If you're still interested in learning about ECC, from a tutorial expressed in simple terms, I recommend these two documents by Certicom. The first is an introduction, and the next is a tutorial where you learn the various aspects of ECC and prime fields one step at a time. The latter includes a lot of visual aid, which was a great way to learn it for me. Introduction: http://www.certicom.com/images/pdfs/WPECCprimer.pdfTutorial: http://www.certicom.com/index.php/ecctutorialI read all the comments just now,thumbs up thx Off the top of my head http://www.khanacademy.org/ should set up a BTC donation button great site.

Supporting people with beautiful creative ideas. Bitcoin is because of the developers,exchanges,merchants,miners,investors,users,machines and blockchain technologies work together.





Advertised sites are not endorsed by the Bitcoin Forum. They may be unsafe, untrustworthy, or illegal in your jurisdiction. Advertise here.

AsymmetricInformation


January 28, 2013, 04:30:08 AM Last edit: January 28, 2013, 06:21:48 AM by AsymmetricInformation 

My take on explaining it: Simplification: PublicKey = PrivateKey*AnotherNumber
So try to answer these questions, and hopefully you'll catch onto the concept real quick.
I multiplied 2 prime integers and got 21. What two integers did I use?
I multiplied 2 prime integers and got 187. What two integers did I use?
I multiplied 2 prime integers and got 1688063245889. What two integers did I use?
ECDSA Public keys (used in bitcoin) are also the product of two large numbers...resulting in a huge product: 6013791818574714160321075769550160928403040221691660914916154278519966847051905 1547600040617210584736371110675553294866150136440087998368169814283413476604. (Actual ECDSA pubkey I just made). Factoring this would be tough!
(Thanks to casascius for pointing out my careless screwup that ECDSA are not 2 prime factors).




casascius
Mike Caldwell
VIP
Legendary
Offline
Activity: 1386
Merit: 1040
The Casascius 1oz 10BTC Silver Round (w/ Gold B)


January 28, 2013, 04:33:39 AM 

I multiplied 2 prime integers... (Actual ECDSA pubkey I just made).
RSA instead of ECDSA? I don't think ECDSA public keys can be created by simply multiplying integers. Given that the number ends in a 4, I'll bet that one of the integers was 2, or perhaps more realistically, there was a transcription mistake.

Companies claiming they got hacked and lost your coins sounds like fraud so perfect it could be called fashionable. I never believe them. If I ever experience the misfortune of a real intrusion, I declare I have been honest about the way I have managed the keys in Casascius Coins. I maintain no ability to recover or reproduce the keys, not even under limitless duress or total intrusion. Remember that trusting strangers with your coins without any recourse is, as a matter of principle, not a best practice. Don't keep coins online. Use paper or hardware wallets instead.



AsymmetricInformation


January 28, 2013, 06:18:45 AM 

I multiplied 2 prime integers... (Actual ECDSA pubkey I just made).
RSA instead of ECDSA? I don't think ECDSA public keys can be created by simply multiplying integers. Given that the number ends in a 4, I'll bet that one of the integers was 2, or perhaps more realistically, there was a transcription mistake. Christ the people on this forum are sharp as a tack! Indeed, I simplified to the two primes example to just explain the basics of public vs private key, and completely forgot that ECDSA's dont work that way when I posed that actual integer PubKey (even though that key was in fact made by multiplying a private key with another number, they arent both primes). And I thought that was a very clear way of explaining it...now the clarity of the explanation is in danger!




casascius
Mike Caldwell
VIP
Legendary
Offline
Activity: 1386
Merit: 1040
The Casascius 1oz 10BTC Silver Round (w/ Gold B)


January 28, 2013, 06:27:17 AM 

I think you still made your point: you've clearly demonstrated an intractable function, even with just the first three examples. Someone just learning this isn't actually going to try to factor any large number you throw out, nor are they going to try to use it in any way. So you had just said it's a real key, but as it turns out it's probably not. This is not an important detail, so no harm no foul.

Companies claiming they got hacked and lost your coins sounds like fraud so perfect it could be called fashionable. I never believe them. If I ever experience the misfortune of a real intrusion, I declare I have been honest about the way I have managed the keys in Casascius Coins. I maintain no ability to recover or reproduce the keys, not even under limitless duress or total intrusion. Remember that trusting strangers with your coins without any recourse is, as a matter of principle, not a best practice. Don't keep coins online. Use paper or hardware wallets instead.



BurtW
Legendary
Offline
Activity: 2366
Merit: 1015
All paid signature campaigns should be banned.


January 28, 2013, 03:08:51 PM 

I simplified to the two primes example to just explain the basics of public vs private key, and completely forgot that ECDSA's dont work that way when I posed that actual integer PubKey (even though that key was in fact made by multiplying a private key with another number, they arent both primes).
To further clarify, in ECC the private key is in fact a large scalar (number) but the public key is not a number at all  it is a point on the chosen eliptical curve. The public key is a set of two numbers, an X and a Y coordinate in the finite group that makes up the points on the selected eliptical curve. I explained this in some detail in post number 4 in this very thread: https://bitcointalk.org/index.php?topic=136933.msg1458864#msg1458864In the specific set of ECC parameters selected to be used by the Bitcoin system the finite field used for the private keys is in fact a prime field, but the private keys themselves do not need to be prime and will only be prime if you are very lucky and randomly generate a prime number for your private key.

Our family was terrorized by Homeland Security. Read all about it here: http://www.jmwagner.com/ and http://www.burtw.com/ Any donations to help us recover from the $300,000 in legal fees and forced donations to the Federal Asset Forfeiture slush fund are greatly appreciated!



DeathAndTaxes
Donator
Legendary
Offline
Activity: 1218
Merit: 1005
Gerald Davis


January 28, 2013, 03:27:58 PM 

Well the compressed version of public key is a single value.
With the X value and the curve one can compute the Y value. The y value is deterministic to the x value and the curve. This means the public key can be reduced to just the X value of the point on the curve.
"Compressed" is a misleading term IMHO as there is no compression going. "Normal" ECSA public key (xvalue, yvalue) "Compressed" ECDSA public key (xvalue) yvalue is computed at runtime using the curve.
Sadly Bitcoin didn't use compressed keys from the beginning so most of the potential savings is wasted.




kjj
Legendary
Offline
Activity: 1302
Merit: 1001


January 28, 2013, 04:18:10 PM 

You actually need more than just the xvalue, because a quadratic is used to find the yvalue. A single bit (parity) will allow you to distinguish between the two possible yvalues and pick the correct one.
And in my opinion, it is compression, in the sense of that word that we normally use. Redundant information is discarded, and enough is kept to reconstruct the original.
 feel free to stop reading here 
There is a second flag involved in the compression scheme, by the way. It is for the private key export format.
privkey(int256 value) > pubkey(int256 xvalue,int256 yvalue) > address privkey(int256 value) > pubkey(int256 xvalue,int256 yvalue) > pubkey(int256 x,bool yflag) > address
(xvalue,yvalue) and (xvalue,yflag) give different hashes, and thus, different addresses. While doing the ECDSA verification, both pubkeys will give the same result because the yvalue is reconstructed if necessary. But, the bitcoin software watches for transactions based on "secrets", and it only stores one secret per privkey. So, when exporting a private key, it will attach the flag if the key is compressed, so that the importing wallet knows which secret to watch for, and which address to give to the user.

17Np17BSrpnHCZ2pgtiMNnhjnsWJ2TMqq8 I routinely ignore posters with paid advertising in their sigs. You should too.



proff
Newbie
Offline
Activity: 46
Merit: 0


January 29, 2013, 07:24:53 PM 

Elliptic curves are 1dimensional but points on them are not "integers", if that is confusing people. You can visualize a typical elliptic curve as the set of points (x, y) in the plane satisfying a certain algebraic equation, and you may speak of integral points or rational points on the curve, but for cryptographic purposes the coordinates should lie in a certain finite field.
Back to complexity, it is worth pointing out that just from the statement of a problem it is not always obvious how hard it is to solve it, and that is what makes life interesting. For example, testing whether a huge number is prime by trying to divide it by 2, 3, 5, and so on will take a huge amount of time, but a 100% reliable way to do it "fast" was not discovered until 2002.




BurtW
Legendary
Offline
Activity: 2366
Merit: 1015
All paid signature campaigns should be banned.


January 29, 2013, 08:07:17 PM 

Elliptic curves are 1dimensional but points on them are not "integers", if that is confusing people. You can visualize a typical elliptic curve as the set of points (x, y) in the plane satisfying a certain algebraic equation, and you may speak of integral points or rational points on the curve, but for cryptographic purposes the coordinates should lie in a certain finite field.
Back to complexity, it is worth pointing out that just from the statement of a problem it is not always obvious how hard it is to solve it, and that is what makes life interesting. For example, testing whether a huge number is prime by trying to divide it by 2, 3, 5, and so on will take a huge amount of time, but a 100% reliable way to do it "fast" was not discovered until 2002.
Please explain what you mean by 1dimensional in this context especially when you go on to say "the set of points (x, y) in the plane", here the word plane implying two dimensions. The second bold statement is incorrect. The points on the eliptical cuve form a finite group, not a field.

Our family was terrorized by Homeland Security. Read all about it here: http://www.jmwagner.com/ and http://www.burtw.com/ Any donations to help us recover from the $300,000 in legal fees and forced donations to the Federal Asset Forfeiture slush fund are greatly appreciated!



casascius
Mike Caldwell
VIP
Legendary
Offline
Activity: 1386
Merit: 1040
The Casascius 1oz 10BTC Silver Round (w/ Gold B)


January 29, 2013, 08:13:18 PM 

Please explain what you mean by 1dimensional in this context especially when you go on to say "the set of points (x, y) in the plane", here the word plane implying two dimensions.
I am guessing that 1dimensional refers to the linelike nature of the curve, much like your position on a winding street can be described as a distance from an origin (a single value), even though your latitude and longitude are twodimensional.

Companies claiming they got hacked and lost your coins sounds like fraud so perfect it could be called fashionable. I never believe them. If I ever experience the misfortune of a real intrusion, I declare I have been honest about the way I have managed the keys in Casascius Coins. I maintain no ability to recover or reproduce the keys, not even under limitless duress or total intrusion. Remember that trusting strangers with your coins without any recourse is, as a matter of principle, not a best practice. Don't keep coins online. Use paper or hardware wallets instead.



DannyHamilton
Legendary
Offline
Activity: 2198
Merit: 1390


January 29, 2013, 08:14:05 PM 

Please explain what you mean by 1dimensional in this context especially when you go on to say "the set of points (x, y) in the plane", here the word plane implying two dimensions.
While a plane is two dimentional, I suppose a set of points in a plane could be one dimensional if they all happened to be on the same line in that plane (I doubt this is what was being stated though).




DannyHamilton
Legendary
Offline
Activity: 2198
Merit: 1390


January 29, 2013, 08:16:38 PM 

Please explain what you mean by 1dimensional in this context especially when you go on to say "the set of points (x, y) in the plane", here the word plane implying two dimensions.
I am guessing that 1dimensional refers to the linelike nature of the curve, much like your position on a winding street can be described as a distance from an origin (a single value), even though your latitude and longitude are twodimensional. In that case we are starting to alter the way the terms are typically used in mathematics. A line is one dimensional, but the only curve that is one dimensional is the curve that happens to also be a line. Most curves (those that are actually curvy and not straight) exist in two dimensions.




BurtW
Legendary
Offline
Activity: 2366
Merit: 1015
All paid signature campaigns should be banned.


January 29, 2013, 08:18:01 PM 

Please explain what you mean by 1dimensional in this context especially when you go on to say "the set of points (x, y) in the plane", here the word plane implying two dimensions.
I am guessing that 1dimensional refers to the linelike nature of the curve, much like your position on a winding street can be described as a distance from an origin (a single value), even though your latitude and longitude are twodimensional. That is a stretch. Well made myself laugh anyway.

Our family was terrorized by Homeland Security. Read all about it here: http://www.jmwagner.com/ and http://www.burtw.com/ Any donations to help us recover from the $300,000 in legal fees and forced donations to the Federal Asset Forfeiture slush fund are greatly appreciated!



kjj
Legendary
Offline
Activity: 1302
Merit: 1001


January 29, 2013, 08:58:08 PM 

Please explain what you mean by 1dimensional in this context especially when you go on to say "the set of points (x, y) in the plane", here the word plane implying two dimensions.
I am guessing that 1dimensional refers to the linelike nature of the curve, much like your position on a winding street can be described as a distance from an origin (a single value), even though your latitude and longitude are twodimensional. In that case we are starting to alter the way the terms are typically used in mathematics. A line is one dimensional, but the only curve that is one dimensional is the curve that happens to also be a line. Most curves (those that are actually curvy and not straight) exist in two dimensions. No, sorry, your math is outdated (by like a century, or at the very least 45 years if you start counting from 1967). The crisis in Mathematics that resulted from Peano's nondifferentiable monster curves was successfully resolved. We even have the word fractal now specifically to describe curves where the Hausdorff Dimension is not equal to the topological or Euclidean dimension.

17Np17BSrpnHCZ2pgtiMNnhjnsWJ2TMqq8 I routinely ignore posters with paid advertising in their sigs. You should too.



casascius
Mike Caldwell
VIP
Legendary
Offline
Activity: 1386
Merit: 1040
The Casascius 1oz 10BTC Silver Round (w/ Gold B)


January 29, 2013, 08:59:57 PM 

Please explain what you mean by 1dimensional in this context especially when you go on to say "the set of points (x, y) in the plane", here the word plane implying two dimensions.
I am guessing that 1dimensional refers to the linelike nature of the curve, much like your position on a winding street can be described as a distance from an origin (a single value), even though your latitude and longitude are twodimensional. That is a stretch. Well made myself laugh anyway. No, sorry, your math is outdated (by like a century, or at the very least 45 years if you start counting from 1967).
This is a thread started by someone trying to learn the basics of what a public and private key is. The fact that it's diverged this far off topic and is now "my math knowledge is better than your math knowledge" is embarrassing for us as a community.

Companies claiming they got hacked and lost your coins sounds like fraud so perfect it could be called fashionable. I never believe them. If I ever experience the misfortune of a real intrusion, I declare I have been honest about the way I have managed the keys in Casascius Coins. I maintain no ability to recover or reproduce the keys, not even under limitless duress or total intrusion. Remember that trusting strangers with your coins without any recourse is, as a matter of principle, not a best practice. Don't keep coins online. Use paper or hardware wallets instead.



DannyHamilton
Legendary
Offline
Activity: 2198
Merit: 1390


January 29, 2013, 09:11:07 PM 

This is a thread started by someone trying to learn the basics of what a public and private key is. The fact that it's diverged this far off topic and is now "my math knowledge is better than your math knowledge" is embarrassing for us as a community.
Nah. Cryptography is a complicated mathematical study. There are various levels of knowledge, and as people attempt to explain in the simplest terms possible some of these complex concepts, others who understand the mathematics better see a need to either correct an error (so that everyone can learn and avoid the error in the future) or clarify an explanation that might otherwise have been misleading. I do agree however that this conversation has drifted far enough from the original question that there probably isn't much need to continue the discussion any farther.




proff
Newbie
Offline
Activity: 46
Merit: 0


January 30, 2013, 12:34:09 PM 

This has nothing to do directly with complexity or with cryptography (public key or otherwise) now, just with the nature of elliptic curves.
They are 1dimensional as algebraic varieties, the same way a line or a circle is 1dimensional. A circle is a good example: the set of points in the plane satisfying
x^2 + y^2 = 1
is a circle, even though we have embedded it in a (2dimensional) plane and are using two coordinates (x, y). The set of all points (x, y) is the entire 2dimensional plane, while the set of only those points satisfying x^2 + y^2 = 1 is 1dimensional. If you feel like describing a point on a circle using a single coordinate, you can do it using stereographic projection, which gives a correspondence between points on a line and points on the circle.
An elliptic curve is also 1dimensional in this sense. Instead of x^2 + y^2 = 1 you have a different equation, for example y^2 = x^3 + a x + b. It is not "fractal" but smooth.
That is all pretty abstract, but what is important in this context is that since we are doing algebra we can plug in elements of any field for x and y. For the purposes of cryptography we want to use a finite field. Which finite field, and which elliptic curve for that matter? There is a list of standard curves published by NIST and others. The coordinates of a point on the curve then lie in a certain finite field, while the set of all points on the curve form an interesting finite group.
If you are implementing ellipticcurve cryptography, as in Bitcoin, unless you have a good reason you are better off just using one of the standard recommended curves. You do not need to numb your brain with too much detail to get started on the implementation side; it is more important to have a general understanding of how everything works. You can worry about specific mathematical details if and when they come up.




BurtW
Legendary
Offline
Activity: 2366
Merit: 1015
All paid signature campaigns should be banned.


January 30, 2013, 04:04:21 PM 

just using one of the standard recommended curves.
Thanks for the great write up and explaination. BTW for those that don't know or may be interested in looking it up Bitcoin uses the standard recommended curve secp256k1.

Our family was terrorized by Homeland Security. Read all about it here: http://www.jmwagner.com/ and http://www.burtw.com/ Any donations to help us recover from the $300,000 in legal fees and forced donations to the Federal Asset Forfeiture slush fund are greatly appreciated!



DeathAndTaxes
Donator
Legendary
Offline
Activity: 1218
Merit: 1005
Gerald Davis


January 30, 2013, 04:20:12 PM 





