Otherwise, determining n given A and an end point would just be a matter of iterating from A until you hit the end point and counting, right?
Also, how do you actually use the keys to encrypt/decrypt?
One of the changes in modern cryptography compared to stuff from the 1990s is that we rarely have cause to use public key encryption at all.
A typical modern design uses a key agreement algorithm to choose a large shared secret known to both parties which is then used to do encryption with symmetric algorithms.
The elliptic curves show up in the key agreement algorithm and in a Digital Signature scheme used after the encryption switches on to prove who you really are, but we often don't use them to actually encrypt anything (and so likewise we don't use them to decrypt anything either).
As a classroom exercise you can use RSA to encrypt the message "I like toast". You turn "I like toast" into a big number. Using a public key you do the (textbook) RSA operation and out comes a different big number. The recipient uses the private key to get the first big number back - and it translates as "I like toast". Nobody did that in real crypto systems, even in the 1990s, and the way you'd do it as a classroom exercise is inherently unsafe, but you can watch it being done and it's somewhat helpful in understanding RSA.
Nothing like that is usually done with elliptic curves.
Fortunately we didn't want to send a message like "I like toast" with public key crypto anyway, we always actually want to agree symmetric cryptographic keys.
And agreeing keys we can do with elliptic curves. Such as https://en.wikipedia.org/wiki/Elliptic-curve_Diffie%E2%80%93...
What's the difference? The key agreement protocol doesn't let you choose the message. Alice and Bob will definitely agree on some shared key at the end of the protocol, but neither Alice nor Bob can choose what it is. For a key this doesn't matter, indeed it's arguably desirable to use random keys nobody actually picked, lots of things to like about that outcome.
Does that help?
? I'm not talking about encrypting data with RSA, but how else do you perform signing with RSA except by using the private key to transform some message that can then be verified with the public key?
I see now the article's trying to describe elliptic curve Diffie-Hellman, which makes much more sense (but makes the comparison to RSA in the article confusing...)
If you want 13P you do
2P = P + P
4P = 2P + 2P
8P = 4P + 4P
12P = 8P + 4P
13P = 12P + P
To use this for encryption you do a Diffie-Hellman operation, where A and B pick secrets a and b, send each other a x G and b x G, and compute the shared secret a x b x G = b x a x G. (Where G is a standard point.)
You can call "b x G" the public key and do ephemeral-static DH if you are not doing a key exchange between two online peers.
---
I mean, once you have the keys, how do you actually use them to transform data?
Instead we usually multiply our private key by someone else’s public key to get a point.
We take that points x value, hash it and use the output as a symmetric key.
The other person can take our public key and multiply it by their private key to get the same point.
We end up with something like this:
OurPrivate * TheirPub == secret point.
(TheirPub is actually equal to TheirPrivateG, thus the secret point is really OurPrivateTheirPrivate*G)
“Encryption” with elliptic curves is just ECDH and then using a symmetric cipher like AES.
Signature is a little more complicated. It’s not just “encrypting a hash”
Yes, this is in fact the basis of the cryptographic security. There's a way to iterate the generator whatever number of times, fast. This is called multiplication, just like there's a way to multiply arithmetic numbers in school without adding over and over.
The thing is it isn't quite so easy given the starting point and the result what you multiplied by.
Basically, adding point to itself n times requires O(log(n)) operations. That's how you can have n be as big as 2^255 or 2^448.
So yeah, you can still count back, but I'm not sure you'll be done before the heat death of the universe. There are better attacks than that, but they're still O(sqrt(n)), which is exponentially bigger than the O(log(n)) required for legitimate uses.
According to [0], the Stelliferous Era alone will last ~3 zettaseconds, which at a best already achieved clock rate of 12 attoseconds gives ~2^127 cycles, easily enough to break common 128-bit-'secure' cryptography with good probability on a single, serial computer.
Checking [1], converting the Virgo Supercluster into sand-grain-sized computer cores would give parallelism on the order of 2^170, enough to break 297-bit security ratings with certainty, and uncomfortably cut into even 384-bit security.
> as big as 2^255 or 2^448.
448-bit security (not 448-bit elliptic curves, but 896-bit curves) is probably okay, despite that these are still fairly underestimated[2] limits - you get better (smaller) limits based off dissipating waste heat at CMB temperatures, so even 384-bit security might be safe in practice.
These are all rather off-the-cuff estimates (read, I looked up the largest and smallest plausible-sounding numbers and divided them), but it's rather disturbing that most people don't even seem to think to wonder "what if the adversary was willing/able to sink a significant fraction of the mass and lifespan of the universe into breaking this cryptography?", much less keep semi-exact numbers handy when estimating security margins.
0: http://en.wikipedia.org/wiki/Orders_of_magnitude_(time)
1: http://en.wikipedia.org/wiki/Orders_of_magnitude_(mass)
2: 2^127 and 2^170 are both fairly achieveable (ie underestimated) individually, but dismantling all the stars you can access to build computers raises the question of how you're then going to power those computers, so I'm not sure just multiplying them together to get 2^297 actually works.
Yes, you could brute-force all the points. The good thing is, ECC is done on fields that are very large, so that actually enumerating them is not practical. Check out Curve25519[1] for some numbers.