3 ms·

I have compiled many fast methods in detail here: http://loup-vaillant.fr/tutorials/fast-scalarmult http://loup-vaillant.fr/tutorials/fast-scalarmult Basically

I have compiled many fast methods in detail here: http://loup-vaillant.fr/tutorials/fast-scalarmult http://loup-vaillant.fr/tutorials/fast-scalarmult 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.

a1369209993 6y ago
> I'm not sure you'll be done before the heat death of the universe 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) http://en.wikipedia.org/wiki/Orders_of_magnitude_(time) 1: http://en.wikipedia.org/wiki/Orders_of_magnitude_(mass) 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.

a1369209993 6y ago

> I'm not sure you'll be done before the heat death of the universe 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) http://en.wikipedia.org/wiki/Orders_of_magnitude_(time) 1: http://en.wikipedia.org/wiki/Orders_of_magnitude_(mass) 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.