Hacker News Reader

Comment by codys | Hacker News Reader

The TI-84 Premium/Plus CE uses a larger RSA key that has not been factored.

Well that sounds like a challenge. Got it handy?

It’d be nice if the bitcoin community put their brute forcing power towards something meaningful like brute force factoring of RSA keys. Sadly, that doesn’t make money.

The proof-of-work for Bitcoin is leading 0's in SHA-256 sums.

It doesn't make money, it's just a simple way of proving you did an approximate unit of work.

It doesn’t make one money directly, but when a block is mined, bitcoin are created and can be sold for money. I’m not saying it’s a good idea; it’s not. But wouldn’t putting that computing power to factoring RSA keys be a better use of electricity? It could be run in a distributed fashion where, if a node says it found it, it’s checked?

Much slower to verify than a hash, and who makes the keys so that you can trust them not to cheat?

> ... who makes the keys so that you can trust them not to cheat?

What? I’m talking about something like BOINC or whatever, but with a project dedicated to factoring RSA keys. Similar to how we have one for protein folding, and whatever. Now, I’m not familiar with how RSA factoring works, but I’d assume a node would be given a “project” (a range of divisors to test), and if one works, it’ll report the factors back to the central server. Then the server would verify the work, and if it’s correct, we now would have a factored RSA key.

Now, you could do something like Bitcoin where the project is distributed, and if a node claims to have factored the block’s key, it’ll broadcast it to the network and be verified by the other nodes. Then the factorer(?) would be rewarded (idk, maybe FactorCoin?). The problem I see with that is: you would still need an authoritative node to say what they “keys of the day” are.

Maybe some rich person could set up a fund to pay out people who put effort into factoring? Or do a fund where people donate money that’s paid out based on effort?

Now, I am aware that 2048 bit RSA is virtually “unfactorable” before the heat death of the universe, but maybe 1024 bit keys or smaller?

Ultimately, this idea comes from an extension of the idea behind the RSA Factoring Challenge[0]: pay people for factoring keys.

[0]: https://en.m.wikipedia.org/wiki/RSA_Factoring_Challenge

> The problem I see with that is: you would still need an authoritative node to say what they “keys of the day” are.

Yes, that part. Some node is telling you what key to attack. What if they make the keys, hang on to the factors, and secretly hand them out to nodes they like?

That completely undermines the idea of "proof of work".

Without any real decentralization or proof of work, with a coin that isn't even scarce, nobody is going to mine that coin because they actually want it. They're only going to mine it because they want whatever bounty you're paying in real money. And at that point the coin is just a layer of obfuscation over "We're paying a dollar bounty to crack RSA keys".

Is there a way to get a partial match on factoring an RSA key, so you can use it as proof of work?

Not really, that'd break the cryptographic requirements of a hash.

Partial matches on a secure hash don't break anything. They don't get you any closer to a full match. And it's trivial to match the first few bits of a hash; just try a hundred random values. Or for 20 bits, do about a million, etc.

Right, so my point is that there isn't a way to incentive partial matches in a way to break these. Partial matches don't get you any closer to the complete solution.

The payouts for partial matches aren't because partial matches are useful. They're incentive to keep guessing.

If you have an 70 bit hash to break and offer a pile of money to whoever cracks it, you won't get a whole lot of attention. Instead you can offer a steady stream of rewards to anyone that matches at least the first 50 bits, building up a swarm of miners. Eventually someone will match all 70.

The question is whether you can set up a scheme like this for factorization. We already know it's a viable mining method for hashes.

I think it's RSA 2048, in which case even if you ran all the computers until the the sun supernovas, you wouldn't be able to factor it probably.

In this case the keys are secure, since the calculators moved from 512 bit keys to 2048 bit keys. But the proposal was more about general RSA cracking, and there are a whole lot of 1024 bit keys out there that could be cracked by a cryptocurrency-scale network.

But even with current tech and current methods, 2048 is doable long before the sun burns out. Bitcoin's approaching 2^80 hashes per day, on par with 1024 bit RSA. Rope in 10x as many computers and you could crack 2048 bit RSA in a mere billion days, give or take some constant factors.

The sun's way too small to supernova anyway. It will become a red giant that blows off the outer layers and leaves behind a white dwarf.

It's be real nice if PoW was protein folding, or SETI matches, or anything else that benefitted humanity instead of random speculators.

Has this been tried, or at least discussed? I often contemplate the vast CPU resources even just in a small radius around me, doing nothing most of the time.

It can be! Hasn't worked so well in practice, however:

https://foldingcoin.net/

Not much going on there... seems the last on-chain transaction happened about a month ago:

https://xchain.io/asset/FLDC

Reply on news.ycombinator.com