4 ms·
1. Setup few servers operating in different countries, pay for a few years and set up a timer which will publish this algorithm on few public websites, then des
by vbezhenar 7y ago
1. Setup few servers operating in different countries, pay for a few years and set up a timer which will publish this algorithm on few public websites, then destroy all credentials, so it could not be undone.
2. Steal bitcoins from very old wallets with some small amounts. Supposedly those wallets are lost. Steal enough to have enough money to live a good life. Well, if for some reason I would have enough money, skip this step.
3. Break google.com certificate and mail hashes to Google Security team. Ask them to disclose that factorization is broken, so the rest of the world can prepare. Repeat with some other big companies.
4. Disclose algorithm when the world is ready.
- lowdose 7y agoYou have given this much thought care to elaborate?
- Ar-Curunir 7y agoFactoring doesn't allow you to break discrete log; you won't be able to steal from old wallets.
- phkahler 7y agoIt's been a long time since I looked at this but IIRC factoring and discreet log are equivalent.
- dvdkhlng 7y agoIt's also a long time since I looked at this, but I recall pretty clearly, that factoring is "easier" than DLP. "Easier" as in factoring is reducible [1] to the DLP. I.e. if you could do DLP in polynomial time, then also factoring becomes polynomial (thanks to Shor's Algorithm [2]). The reverse, however, is not currently known to be true AFAICS: having an oracle that computes the DLP does not help you to speed up factoring (at least not in a way that makes it polynomial). [1] https://en.wikipedia.org/wiki/Reduction_(complexity) https://en.wikipedia.org/wiki/Reduction_(complexity) [2] https://en.wikipedia.org/wiki/Shor%27s_algorithm https://en.wikipedia.org/wiki/Shor%27s_algorithm (EDIT: typo)
- baby 7y agoThey are equivalent according to this: https://crypto.stackexchange.com/questions/9385/reduction-of-integer-factorization-to-discrete-logarithm-problem https://crypto.stackexchange.com/questions/9385/reduction-of...
- Ar-Curunir 7y agoThat for DLP modulo a composite, whereas Bitcoin uses DLP over elliptic curve groups.
- dvdkhlng 7y agoI think you are mistaken, they are not equivalent in any way that would be meaningful to assessing cryptographic strength. The stack-exchange questions that you link to refers to [1] "Discrete Logarithms and Factoring". Section 1 "Introduction" already states many facts that imply that DLP is hard, even if you can factor: * fastest known method for DLP is O(exp(c sqrt(log n log log n))) * 1. 3c) "if we can factor in polynomial time, then to quickly solve a^x ≡ b mod n, all we need are solutions modulo the prime divisors of n" Note that "solutions modulo the prime divisors of n" are still instances of the DLP with super-polynomial complexity, and in cryptographic applications N is usually a prime number anyway (DHE, ElGamal crypto-system), so 1 3c) does not actually apply. See also the paper's section 6 final remarks "Conversely, one can ask for a fast algorithm for prime-modulus problems, assuming all needed factorizations. Both of these questions remain unanswered". [1] https://www2.eecs.berkeley.edu/Pubs/TechRpts/1984/CSD-84-186.pdf https://www2.eecs.berkeley.edu/Pubs/TechRpts/1984/CSD-84-186...
- phkahler 7y ago>> I.e. if you could do DLP in polynomial time, then also factoring becomes polynomial That is what I remembered. You don't need Shor's Algorithm though. DLP would help finding roots, in particular if the log of a number is even, you can compute the square root of the original number which is useful for finding quadratic congruences (the goal of the quadratic sieve). The reverse (factoring enables DLP) does not appear to be true.
- Ar-Curunir 7y agoThey are equivalent (with some caveats) when considering the multiplicative subgroup Z_N where N is a composite. Bitcoin relies on DLP over elliptic curve groups.
- tuxxy 7y agoSolving the discrete log problem would require that your factorization algorithm have the capability of being adapted to DLP. Some factorization algorithms can do this, but, IIRC, some cannot.
- ConcernedCoder 7y agopossesses quite literally, the "keys to the kingdom"... steals lol
- simonebrunozzi 7y agoI am not sure I'd ever want to reveal my identity, ever. Becoming famous for something like this would make my life way too dangerous, forever.