Welcome back! These hints are great
First stab at part one (using gmpy2 for fast bignums)
from gmpy2 import mpz, isqrt_rem, t_div, gcddef one(c): # Determine if a square if t_div(c, 4) 2: # Make it square? c = t_div(c, 2) # Find the square root d and remainder e d, e = isqrt_rem(c) # First decision, if e is 0, return d if e 0: return d # Second decision, if(GCD(e,d)!=1) return GCD(e,d) tmp = gcd(e, d) if tmp != 1: return tmp return None
Thanks. Reminds me how much I hate recursive programming too :)
If you're lazy like me and want to see the tree immediately you can cheat a bitprint(json.dumps(recurse(c), indent=4))This needs to go in OpenGL for the larger numbers!
Filtering out some useless formatting, this is what I get for RSA100 61218444075812733697456051513875809617598014768503 13204334350125320769126278 2 6602167175062660384563139 7824221627472775882440665 1915100302336 1357695 5 271539 1383871 895 54 5 1 1 1 2 1 1 1 1 1 1 7 3 2 1 1 1 1 1 1 1 1 1 2 1 1 1 1 1 1 29 4 2 2 5 1 1 1 2 1 1 1 1 1 1 1176 2 588 2797181014427 1698898 1089 33 33 1303 7 3 2 1 1 1 1 1 1 1 1 1 2 1 1 1 1 1 1 36 6 6 1672477 628 3 2 1 1 1 1 1 1 1 1 1 25 5 5 1293 68 4 17 35 5 7 39020571855401265512289573339484371018905006900194 2 19510285927700632756144786669742185509452503450097
Hadn't heard of it either till your post inspired me to look for better options. There is an interactive viewer too!
The code I used (after changing dicts in IseePatterns code to tuples) is this. There are probably better waysdata = (c, recurse(c))t = Tree(str(data) + ";")ts = TreeStyle()ts.mode = "c"ts.arc_start = 0ts.arc_span = 360nstyle = NodeStyle()nstyle["shape"] = "sphere"nstyle["size"] = 3nstyle["fgcolor"] = "red"for n in t.traverse(): n.set_style(nstyle)t.show(tree_style=ts)#t.render("image.png", tree_style=ts)
Ok so I've had this ready to go since december… Good time to drop! Please keep it safe and don't go destroying the internet
Presenting sonic_rainboom.py
https://pastebin.com/vNqnPRJR
Full support for PEM certificates and certificate requests, armored PGP public keys, SSH public keys, and verification of results before outputting private key. And ECC of course.
Ponies not included
Have fun
Yep. Solution goes in the factors function.
If you generate your own keys you can test it with the private keys like this
class FakeVQC: def _load(self, key): f = open(key, 'rb') key = serialization.load_pem_private_key(f.read(), None, default_backend()) return key.private_numbers() def factors(self, c): priv = self._load('rsa/key.pem') return priv.p, priv.q def ecpoint(self, curve, x, y): priv = self._load('ecc/key.pem') return priv._private_value
Yeah
No, this is just boring wrapper code to directly read the most common types of public keys, and output correctly formatted private keys. For some reason most crypto libraries have no way to just add private numbers to a public key (since its considered impossible, who needs functions for it). Just so we don't have to code it later!
The final ingredient is missing
Yeah and its tedious to do by hand even when you have the factors (especially PGP, the keys this spits out can be used right away). I wanted this available for when shit hits thef fan, and its a good way to verify our factoring algorithm against real keys as well (this could be considered illegal if they are not yours, fyi). This is the most obvious proof I can think of, right after solving all RSA numbers in a few minutes.
The "keep it safe" bit was serious too, please create backups!
I am not a lawyer. Hence the "could be". I'm betting someone will make the argument that cracking the Verisign root key shows malicious intent or something, DMCA laws and all. Would rather not be the one to defend that in a courtroom claiming "but mathematics!". Not disagreeing, just saying.
Obviously the proof will spread like wildfire and everything based on broken crypto will have a bad time. Nothing can stop that.
The tree we're working on now is not gonna put a dent in any cryptocurrencies until we get the crumbs on how elliptic curves are the same as prime numbers (or something). When that happens and ECC is broken as well, everyone will shit their pants, including bitcoiners, as there are no implemented alternatives ready to go, anywhere.
Checked! I will cook up some more tomorrow if the whole thing isn't broken already. Seem to have made more art during this adventure than actual breakthroughs, hope they're inspirational
You're just killing it with these, did you make them by hand? I might steal your color scheme. Awesome stuff
Just for you
Its stupidly fast, even with unoptimized python code on a single core. Generating the images takes way longer
RSA100 tree without removing trailing zeroes (binary) is 0.3ms
RSA100 tree with all trailing zero bits removed on every branch is ~1ms (can probably cut this in half compared to my current code)
RSA2048 tree with zero bits removed is about 2.4ms…
The full RSA2048 circular image which is 18673x18723 and too large to post takes about half a minute.
Will see what happens if we need to remove one bit at a time and try all combinations of every branch though
Yeah but thats even more annoying when dealing with recursive problems. Easier to write it with recursion and refactor it with tail-calls and accumulators and shit afterwards, which says a lot.
Good point. Have to wait till its public knowledge or obscure it really well. Tree-based procedural generation of landscapes from random RSA keys or something.
Wouldn't call myself a musician, I just mess around with synths tbh
There is all kinds of applications for this that we can't even imagine yet. Guess its called the tree of knowledge for a reason… can't wait to se where we're going, now that the tree is taking shape my mind is already going crazy with possibilities
No pessimism here, just a fun hobby I hope to get good at someday, if not its still fun! Good luck with your album/EP!
>evil internet hacker nazi who masturbates to anime.
Did I forget how deep this rabbit hole is again? Yay for reminders
The credit goes to >>3590. The only addition is removing all trailing zero bits (divide number by two for as many times as needed until it is odd). This is one tree. Using the numbers as is and not dividing at all is another (original code). I posted both. There are lots of possibilities in between.
If >>3654 is right, we don't know which numbers have to be divided, and how many times, so this a bounded logarithmic number of possible trees. Since the trees are small (computationally speaking), generating all of them and checking if the sum of all leaf nodes are a factor of c should still be pretty quick (seconds.. ish). One of these trees is the solution. This is the part that is hard to code.
If we do that, we may find ways to decide how many times and when to divide each number, and not have to try every tree.
So… my code has a bug, I have been removing zeros from only the e values so far.
Here are trees with trailing zeros removed from both e and d, just e, and just d (third image is the one you asked for). I haven't added up the leafs and checked these yet