115
Wisecrack
212d

So I cracked prime factorization. For real.

I can factor a 1024 bit product in 11hours on an i3.
No GPU acceleration, no massive memory overhead. Probably a lot faster with parallel computation on a better cpu, or even on a gpu.

4096 bits in 97-98 hours.

Verifiable. Not shitting you. My hearts beating out of my fucking chest. Maybe it was an act of god, I don't know, but it works.

What should I do with it?

Comments
  • 55
    Source code, or it didn't happen.
  • 6
    @SparkyTD

    I don't want to get drone striked.

    I'm not fucking around.

    Any advice what to do?
  • 15
    Idk write a scientific paper, create a web service, sell it to a company?
  • 6
    @24th-Dragon

    Good idea! Maybe charge a few grand per factoring job.

    Trying to think of something bigger.
  • 36
    Well, keep ping us every 4 hours to make sure they don't get you.
    At the first miss, we will call the police.
  • 6
    Mind sharing what you even mean? You're talking about https://en.wikipedia.org/wiki/... ?
  • 7
    @nitwhiz

    It means the algol can derive the factors of a public key.

    You can imagine the implications.
  • 6
    Sensation!
  • 12
    @Wisecrack how about sharing the verification of your result?
  • 5
    @nitwhiz

    Ok, cool. Go head and post a 1024 bit product I'll factor it and repost the result here later.

    I use https://asecuritysite.com/encryptio...

    Lets you set the bit length.

    Will make good enough proof I guess.
  • 5
  • 4
    @Coffe2Code

    I double dog dare you.
  • 4
    @turbod

    As fast as people are seeing this post and responding, the only way for me to keep up (without being flooded the next time I log in), is to stay logged in.
  • 7
    1. backup your code

    2. be careful

    3. ?

    So does this mean encryption is no longer secure?
  • 6
    @Demolishun

    If I'm not another schizophrenic madman on the internet, yes and no.

    So if it takes say 3 days to break a 4096 bit key on an i3, probably takes a couple of hours on a dedicated gpu based rig.

    It'll just mean they will massively increase key size.

    It's a hack, not a genie..

    assuming i'm not just insane. Which would be a fair thing for people who are familiar with the problem to assume.

    I'd believe I'm insane too if I weren't seeing the proof right in front of my face.
  • 7
    @Demolishun No, because there are quantum-resistant encryption methods.

    RSA, which is basically just lots of long division, is trivial for a quantum computer.
  • 13
    @Wisecrack I'm not doubting your results, but you need more eyes on this for peer review - get some people that you know and trust in on this. You got to see that this can be replicated and that it's not a fluke.
  • 7
    @Root

    This only covers integer factorization. I'm unfamiliar with the discrete logarithm problem or the elliptic-curve discrete logarithm problem, so I might be missing other big important pieces.

    All I know is integer factorization now appears trivial.

    You sound like you know what you're talking about. If you get some time will you make a post going into what you know about quantum resistant encryption?
  • 7
    @Root

    It is currently zero day exploit. Encryption around the world will take months to update. That is a lot of time to use this hack.
  • 4
    @theKarlisK

    I don't currently work in the programming industry in any capacity, just occasional team stuff, and hobby coding. Don't know any mathematicians either.

    Which is why I posted on here. Somebody (who doesn't immediately dismiss it as crazy) is bound to be able to give me a better idea of what this is and if it works the way I think it is.
  • 8
    @Wisecrack

    Wait, does this just tell you the primes used for the key? Or does this actually let you crack the key? Because it still takes a lot of effort to crack the key even when the primes are known.
  • 4
    @Demolishun

    Just primes at the moment. Thats all I've been focused on.
  • 13
    "Maybe it was an act of god..."

    This sounds fishy
  • 9
    @JhonDoe

    What, you don't believe in the one true god?

    You don't believe in Thor?
  • 13
    https://pastebin.com/psmKMad1
    Here's the product of two 1024b primes. Give me the primes to prove that it works.
  • 11
    @SparkyTD

    Finally, a challenger appears!

    Edit: Also you do realize once it's factored, people are going to accuse you of being a sockpuppet or a partner of mine..
  • 11
    Round 1, FIGHT!
  • 32
    - Backup your code according to 3.2.1.
    - share it with someone else, preferably someone distant enough.
    - Share in non-obvious way. Maybe half via mail, another half - via messenger, I'd create a few throw-away accounts for this purpose
    - I'd share separate parts with several people
    - if possible, I'd print the code, hide it somewhere safe. Definitely not in my house.

    Then and only then would I go public. In case smth happened to you, your work will live on.

    Call me paranoid, idc. I take my measures. My work will not vanish.
  • 7
    @SparkyTD

    should take 33.6~ (lets say 36 hours), a day and a half on my machine.

    This thread will probably be buried by then. Is there an email or phone number you want me to send the results to?

    Also whats the prize when I finish?
  • 19
    @Wisecrack I don't care what people accuse me of. If you give me the correct primes, then *I* will belive you. This was the reason for my comment.
  • 9
  • 9
    @Wisecrack what's the prize? With this power, probably some form of world domination.

    You can @ me with a pastebin link on this thread in 2 days, I'll get a notification.
  • 8
    @SparkyTD

    Okay, will do. Should have your answer by 2:30AM

    saturday.

    Call it Saturday 6AM to be safe.

    Gotta do some backups in the meantime.
  • 10
    @SparkyTD

    "With this power, probably some form of world domination. "

    Mwahahahaha.

    need an evil laugh emoji.
  • 12
    @Wisecrack If you dont want to post the code yet can you at least give us the insight into:
    What launguage did you use?
    What is the general algorithm?
    Is it based on old research or did you discover it yourself?
    What are you planning to do with the code?

    If you can complete the challenge i would be really interested in that code of yours. Also since im studying at university i might be able to help you with mathematics, we have a lot of cool prof too!

    We can talk using devrant discord
  • 5
    @Gregozor2121

    Didn't even know devrant had a channel in discord.

    All I want to write at thise time is the code is written in julia. It's kind of a terrible language but the perf beats python.

    Some others might have already seen the previous post talking about it but at the time the algol was numerically unstable and way slower than it is now.
  • 5
    @Wisecrack are you encrypting your backups?
  • 7
    @coffeeholic

    I mean, if someone where to come and try and take the algorithm (no black vans, helicopters, or drone strikes yet lol), they'd be coming to make sure it never gets out anyway.

    At least decrypted it'd have a chance of being leaked by somebody.
  • 4
    have you tried this -2048

    2519590847565789349402718324004839857142928212620403202777713783604366202070

    7595556264018525880784406918290641249515082189298559149176184502808489120072

    8449926873928072877767359714183472702618963750149718246911650776133798590957

    0009733045974880842840179742910064245869181719511874612151517265463228221686

    9987549182422433637259085141865462043576798423387184774447920739934236584823

    8242811981638150106748104516603773060562016196762561338441436038339044149526

    3443219011465754445417842402092461651572335077870774981712577246796292638635

    6373289912154831438167899885040445364023527381951378636564391212010397122822

    120720357
  • 5
    you should better get cracking on sparky's number.

    It would be a great proof, finding the numbers of an anonymous stranger
  • 5
    but it wouldn't really mean much for security... just a step.
  • 5
    @StopWastingTime He is cracking this number already. He had said that it will be done tomorrow at 6AM
  • 5
    Ok so first thing first, go to a lawyer, get a provisional patent on this. Then get it peer reviewed and do all that shit. GET A PROVISIONAL PATENT pay the money just in case
  • 7
    @enron456 I dont recommend it. Patents can bankrupt you and companies just dont give a shit about them.
  • 7
    @Gregozor2121

    6 AM saturday.
  • 5
    📍
  • 5
  • 8
    @Wisecrack Did you check https://en.wikipedia.org/wiki/...#Faulty_key_generation that your chosen prime numbers p and q don't fall into that one?

    (Edit: link pasting with hash anchors is broken, please go to the "faulty key generation" section manually)
  • 5
    @Gregozor2121 I'd usually agree but unless he wants to drop it as open source, better safe than sorry, I made one for 300 bucks and def wasn't worth it but for this level of groundbreaking I'd say it's worth it
  • 16
    Okay, I cracked the number. It is... 42...
  • 10
    @Demolishun OH MY GOD. YOU STOLE HIS ALGO.
  • 6
    @Fast-Nop

    I'm getting my primes from a single source unfortunately.

    You want to throw a few low bit products my way (<52bit, or 26bits per prime) with various generators other than the one I linked, so I can check them for myself I'd be grateful. Busy porting over to ArbFloat to handle the additional precision needed for SparkyTD's challenge.
  • 10
    @Wisecrack The issue is that if p and q are "too close" to each other, or if (p-1) or (q-1) have only small prime factors, then it's well-known that factorisation is rather easy. And obviously also if either p or q are very small.

    So it's not that factorisation is automatically hard - you have to choose p and q carefully to make it hard.
  • 5
    @enron456 As i have said, even with patent, companies will just copy the algo without caring about you at all.

    It might be better to sell it to the company that might be interested instead. Or publish a paper and get some prizes.
  • 6
    @Wisecrack Wait. I generated the numbers with the site you linked without even noticing that you linked a site. What's the guarantee that the site isn't yours or that you don't have access to its logs?
  • 8
    @Fast-Nop

    I was concerned about something like that. Posted before hardly any response to give me a heads up. Creating a stir worked better.

    I do get combinations of factors that are definitely experiencing worst case time complexity but no where near what would be expected.
  • 7
    @SparkyTD

    See, this is what I'm talking about!

    Next thing you know, everyone and their dog is a sockpuppet account "in on the scheme", and every source of primes is obviously a site I control lololol.
  • 5
  • 9
    @Wisecrack I'm not quite sure, but couldn't you use a website certificate of a well-known and respectable website like Google or Youporn, get the underlying prime product out and factorise it? Or don't certificates work that way anymore these days?
  • 7
    . tactical dot, because I want to see how this ends.
  • 7
    @Fast-Nop

    This is why I write "I'm an idiot and it must have been an act of god."

    I know nothing about public key cryptography beyond that factorization of large numbers is supposed to be hard.

    i'm literally an idiot savant and this might just be undiscovered low hanging fruit, like athena from the head of a retarded zeus.
  • 8
    @Fast-Nop
    Modern certs should use ecdsa-keys and as he mentioned before, he can't attack elliptic curve algos.
    He can only attack regular RSA.
  • 6
    @Wisecrack Mh yeah I see - I wouldn't be able to extract an underlying prime product from a certificate either.
  • 5
    @metamourge

    dont count on it. A broken clock is right twice a day.

    Give an idiot a hammer and if he bangs on things long enough eventually he's bound to break something.

    Also, shit like this: 1861836577 * 11

    will break it. I think I may have a fix, but basically, if I'm wrong, the product should be safe as long as the factors are several orders of magnitude separate.
  • 2
    Maybe a package signature on aur?
  • 3
    If you can do this, then i want to be the first to know about it.
  • 6
    @Wisecrack Of course they need to be orders of magnitude apart:

    p − q >= 2*n^(1/4)

    is required. If you have your sample p and q from your tests, you can check that part with any pocket calculator because it's just about orders of magnitude, not about precision to the last digit.
  • 5
    @Fast-Nop

    This is the kind of answer I'm looking for!

    I don't know enough about the problem otherwise. You know how hard it is for a regular person to get feedback from an expert?
  • 8
    @Wisecrack Actually, I didn't know that either one hour ago. :-)
  • 3
    @Fast-Nop

    Whats the 'n' in that equation?
  • 6
    @Fast-Nop Ahh yes the classical wiki search to make sure a stranger on the internet isnt wrong.

    Because if you dont talk face to face that ability is indistingushable from being an expert in that subject.
  • 4
    @Wisecrack n is the product of p and q, your prime numbers.

    @Gregozor2121 I'm a google-fu black belt. I just faintly remembered that there was something about choosing the numbers, but not what it was.
  • 4
    @Gregozor2121 I try not to memorize anything, except things I use all the time. Those things you just memorize by attrition. Tech changes so fast that it is more valuable to get good at Googling than it is to just know things. So I focus on concepts of how things work, not the details of how things work. Design approaches versus APIs. Consequently websites that only show the how are not nearly as useful as those that show the why.
  • 6
    May I ask, as a newbie in the field, what you're talking about?

    Everyone seems to be amazed and I'm just sitting here like "wat"
  • 2
    @Demolishun It is necessary to me as well. Since i learn from very different tech fields i wouldnt be able to memorise everything. I just use internet as a expantion of my mind.
    Passive memory is freaking useful
  • 7
    @Ranchu

    Basically some encryption that a lot of tech relies on, is based on integer factorization being hard.

    And I may have stumbled completely by accident on a means to make it quick and easy.

    Btw, I ran some of my products through the p-q>=2*n(1/4) filter and even ones that comply to it are vulnerable.

    Did come across a factor pair that failed FINALLY. Rounding error I suspect. It's lower bit length than some of the others I factored so I don't know.
  • 3
    @Ranchu If you have two suitable large prime numbers, it is easy to multiply them. But if you have only the product, it is very difficult to get the two factors back out of it ("factorisation").

    This is used in some crypto algorithms, e.g. within PGP. Basically, if you can easily do the factorisation, then you can easily crack PGP encrypted emails.
  • 9
    @Ranchu What is 234*846?
    197964
    So tell me what factors does 186384537 have?

    You cant (at least in your head) because it is difficult (imagine a number with 1024 digits, because this oneis too small and too trivial for a pc to solve)

    Operations that are easy to do in one way and hard to do in the oposite way are the foundation of cryptography. If somebody finds a easy way to do it backwards that means that that specyfic crypto algorithm is useless because everyone will be able to easly crack it.

    If he is right, that means a scientific breakthrough... and massive internet vunluarebility.
  • 2
  • 2
  • 1
    6am GMT-0 I presume? You're not IST or PST I guess, are you?
  • 3
    @netikras I'm GMT-5.
  • 3
    @Wisecrack I'm not a cryptographer, sorry. I'm not even a journeyman or enthusiast, just an avid reader.
  • 11
    You should test this veeeery good and be absolutely sure about it.

    I once thought I had created the new super compression algorithm being way more effective than everything else known. The next day nothing worked anymore; I had overseen a tiny mistake fooling me.
  • 1
    📌
  • 3
    @Wisecrack damn.. For some reason I was sure you are irish 😁 thanks
  • 3
    @Wisecrack

    Maybe what you found is a way to select primes that don't suffer from a potential vulnerability. So this may in fact strengthen current methods of encryption.
  • 10
    @Benedikt

    I guess I'll be the butt of the joke for a month if I'm wrong. "Hey Wisecrack, remember that time you thought you found a method to factor numbers fast! LOL!"

    Took a lot of dead ends finding this. Years worth. Lots of stumbling on interesting stuff I didn't know was already discovered. Imagine my surprise when I was eleven and rediscovered all the primes I came across could be described with 2*n+1.
  • 3
    finally. i’ve been waiting for P=NP to watch the world burn for so long.
  • 1
    @offworld It isnt that... yet...
  • 2
    what the heck.
    📌
  • 11
    @Wisecrack Nah it's good even if it should fail. How else would we have progress if nobody dared to challenge the status quo out of fear to be wrong?
  • 3
    @Gregozor2121 AFAIK prime factorization is in NP and is not known to be NP-hard so this would be a hint into the opposite direction everybody is believing because no proof was found yet.
  • 2
    @offworld That algo might be better but since we dont have the code we cant determine its computational complexity.
  • 1
  • 1
    @Gregozor2121 sure, I was a bit half-serious here :^)
  • 0
  • 9
    @Wisecrack, you may have stumbled onto something nearly as important: "devbait".

    1. make provocative claim

    2. lead people on as the solution "takes time"

    3. enjoy upvotes

    4. profit?
  • 6
    @Demolishun He clearly stated the date so i would hold the judgement a bit. It is good to be sceptical but being too sceptical is connected with stupid and flat earthers.
  • 6
    If your algorithm works you might want to set up a propper zero knowledge proof and then show it to a tech university.
  • 4
    @Gregozor2121 It is levity, not criticism or judgement. Hence the "nearly as important" exaggeration. I am looking forward to the results, because progress is cool. For instance I dislike Google, but I cannot help but applaud their efforts in quantum computing. It is fun to figure out new things and break the rules.
  • 7
    Had a military helicopter fly low over my house lol.

    For a split second thought it was the NSA boogeymen come to gitmo me :D
  • 1
    @Wisecrack If gov had discovered what you did then it would be more beneficial for them to support you so you can help them fix the issiue. But in current times everything is possible...
  • 1
  • 10
    @Wisecrack nah, if you were to present this to the NSA they would tell you that they already knew the algo and didn't publish it or had better ways to get the private key, for obvious reasons. Keep up the good work anyways.
  • 2
    @p100sch Possible but equaly not possible.
  • 7
    @p100sch They have had a backdoor for a while. For a long time everyone used the default primes in software libraries. Nobody changed them. So the NSA paid to get the solution for that prime set. So for that prime set they have had a backdoor for a while. I think people finally caught on, but who knows what they had access to.
  • 2
    ----[==]
  • 5
    📌🔨
  • 4
    🔭🍿
  • 7
    Yo ow, if I'd solved this, I definitely wouldn't be posting it here.

    Scream it from the rooftops, give it to cryptographers for peer review, release it for anarchy sake, sell in for millions, but the last thing I would do is try to prove I did it by factoring numbers from a rants comments.

    But I'm eager to see the results
  • 1
    Uh oh! 📍
  • 9
    How about taking on one of the unsolved RSA challenges: https://en.wikipedia.org/wiki/... ?
  • 5
    While we're all at it, I'd like to point out that everytime we want to check out new comments in this thread, we have to srcoll from the top all the way to the bottom. And it freaking sucks!

    Edit: nvmd, just found out there's a scroll-to-bottom feature in the meatballs menu of this thread.
  • 1
    📌
  • 3
    . subscription dot for notifications from this thread
  • 0
    @deadPix3l

    Hey did anyone every tell you that you're awesome.

    Wasn't even aware there was a specific wikipedia page for that.
  • 3
    @netikras i think in short you wanna say create horcruxes for his code 😂.
  • 1
    Subscribing.
  • 3
    @Wisecrack hmm? Wikipedia? Was that meant to be a reply to @coffemaker ?

    Either way. Excited to see what happens Saturday, but i only meant for something so revolutionary, so amazingly impressive, with the power to completely change security as we know it, you chose a kinda weird way to announce this achievement.
  • 1
    📍👀
  • 1
    📌
  • 1
  • 2
    Tactical .
  • 1
    @-pthread pretty much - yes 😁 good to see another HP fan here!
  • 1
  • 2
    📍
  • 3
    Well that's funny because yesterday I thought about looking into this exact thing but I was too busy to even begin looking into it. Now this appears in my feed
  • 3
    📍
  • 2
    📍
  • 2
    I think a few hours is left on this claim, right?
  • 4
    @deadPix3l

    I explained my thinking on it. I had to be sure because I'm a complete novice and the only way to do that was to get feedback without giving up the code.

    Finish date is 6 AM GMT-5 1/11/2020

    Edit: Holy shit this thread blew up.
  • 2
  • 8
    Death by pins.
  • 2
    @offworld

    "i’ve been waiting for P=NP"

    wait, would that really be the implication?
  • 3
    @Wack

    I'm gonna do the RSA challenges.
  • 1
    @EaZyCode Algo strikes again.
  • 2
    . Tactical dot
  • 2
    Gmt -5 shows 6.30 am right now, is it done yet?

    Edit : realised that you were asking about 11th 6amb, and its 10th. No worries i guess we will be getting answer in next exact 24 hours
  • 2
    @StopWastingTime

    No worries.

    You're like the fifth person to think it was today.
  • 2
  • 2
  • 3
  • 1
    @tits-r-us I don't think so, the NSA already had ways to bypass RSA encryption, probably. If they have, then they already killed them, most certainly.
  • 2
    I don't even get it. You must've 2 primes right now, which, when multiplied (or whatever RSA even does with these numbers) result in the number from RSA-1024 am i right?

    Why don't you tell us those numbers, wouldn't that be proof enough?
  • 2
  • 2
    Some results ?
  • 3
    Looking forward to the Sat morning funny papers!

    If it's successful, gonna be doing more challenges for the next week. If unsuccessful, looking forward to the troubleshooting!
  • 10
    I was here when it happened!
  • 2
  • 2
    @nitwhiz the numbers are gonna be released 2020-01-11 06:00:00:00 GMT-5
  • 10
    @Quirinus write eveything down on golden plates and hide them under a rock for future generations to discover and form religious groups based on them!
  • 5
    @mintchase

    "If it's successful, gonna be doing more challenges for the next week. If unsuccessful, looking forward to the troubleshooting!"

    Basically this.
  • 2
    @Wisecrack

    DAD! ARE WE THERE YET! 😉
  • 5
    📌
    This is like the second time I'm on DevRant in about a year. Not disappointed! 😮😅
  • 2
  • 4
    @Demolishun son, patience is everything in this world.
  • 5
    @p100sch yeah i read that, i was here before this thread got completely out of hand - but the statement was that op's i3 did it in 11 hours. So there must be a result already, which can be verified?
  • 4
    @nitwhiz that is correct, but op walked it back to 33.6 hours. Maybe a admission of overstating ones rigs capabilities or algo performance. But if it is technically multi threadable we certainly would manage to hit the target time with ease.
  • 5
    @nitwhiz I think saturday was the first deadline. dunno if @wisecrack moved it. very thrilled about this. totally waiting for tomorrow.

    "How soon is now?"
  • 2
    This should be interesting...📌
  • 1
    @p100sch @JhonDoe
    He didnt move the deadline, you are just crap :P

    Deadline should be reach soon.
  • 2
    🗡
  • 3
    @Velitar shit just got real... (🗡)
  • 2
  • 3
    I don't believe it. But I'm grabbing my popcorn to see whether I'm right or not. Good luck finding the answer 👍
  • 2
  • 2
  • 3
    If I calculated this correctly, it should be done in like 8-9 more hours.
  • 2
    @Gregozor2121 op claimed to be able to perform said action in 11 hours and after receiving a challenge op extended the time frame to 33.6 hours. What about this information is incorrect?
  • 2
    I'm all ears on this one.
  • 1
    @p100sch 4096 bit ~ 96 hours is what he said.

    IDK why, but when he took the challenge, he posted that it'd take 36 hours whatsoever.
  • 2
    📌
  • 0
    Apparently no one cared enough to specify times with timezones. Is it already Saturday 6:30 AM? Not here
  • 3
    @mexandroide Saturday 6AM GMT-5
  • 1
    If only we could look up a user's profile and see if they have put a location!

    CA, GMT-8.
  • 7
    @Quirinus @p100sch @cbsa Again he said (if you werent so crap at paying attention) that he needs additional time to rewrite the program.

    Also, not everybody has a spare pc and some people have idk.... a JOB?

    Lets just wait patiently.
  • 3
    @mexandroide I did. I asked TZ two daysvago and I was answered. In fast I think it was repeated here at least 3 times.

    If only you cared to look before complaining...
  • 10
    A plot twist: windows updates came in at 5.30 and rebooted @wisecrack's pc at 5.59 am 😁
  • 1
    @netikras I'm sorry, I did read a bunch of the initial posts, but I also have a job
  • 3
    @mexandroide I reckon others do too. Or at least better things to do than keep reposting for every new lad in the party who doesn't bother enough himself
  • 0
    @netikras good thing there's people like @velitar that doesn't bitch and likes to help. Cheers.
  • 3
    @Gregozor2121 If you weren't so crap at paying attention, you'd see that I never commented on him increasing the time. I just calculated the time left, from his eta.
  • 2
  • 2
    DEFCON talk?
  • 7
    POST MORTEM because sadly in the age of autoplay being disabled rick rolls are a dead meme. Time to eat humble pie. I've grown accustomed to the taste.

    Numeric stability bit me in the ass again. The largest prime product I factored was a 32 bit number 1855526741 * 2163967087, it took 1116.111s in python.

    The julia build used a slightly different method and managed to factor a 27 bit number, 103147223 * 88789957 in 20.9s,

    I don't know if these number are supposed to be good.

    As others said, 6 AM came and I'm no debugging.

    Thank you all for coming to the show.
  • 2
    @PunkerenxD Welcome back Punkeren!
  • 6
    @cbsa

    "4096 bit ~ 96 hours is what he said.

    IDK why, but when he took the challenge, he posted that it'd take 36 hours"

    I added time because I was in the middle of a port involving ArbFloat so I could get arbitrary precision. Had a crude desmos graph doing projections on what I'd already factored in order to get an idea of how long it'd take.

    I'm doing a write-up now and I'll make a dedicated post linked here in this thread when it's done. I know everyone hates scrolling and theres really not enough room in a comment.
  • 4
    @nibor I put CA as my location in case you all come to burn my house down :D
  • 3
  • 3
    @Wisecrack you might want to think about using Haskell it has unbounded numeric types built in and is pretty powerfull for these things.
  • 2
    @Wack

    I'll take a look but what complicated it, among other things, was GC pressure due in part to both julia and python abstraction precision libraries implementing immutable, rather than mutable, types.
  • 5
  • 1
    @Quirinus Yep Im crap.
  • 2
    @Wisecrack I think the wild fires will probably burn your house down first :/
  • 3
    @andpeterson

    My imaginary house seeing as I dont live in california.

    And how do you know they will?

    Maybe they can be reasoned with?

    Like a benevolent alien force.

    Maybe they're INTELLIGENT fires?

    Congratulations, you just lost about 5 IQ points reading that.
  • 1
    CIA at the door in 3...2...1...
  • 3
    Nice way to get more ++s ;)
  • 0
    @page394

    Nice way to get flooded with fucking updates about being ++'d.
  • 2
    did you get the numbers? 🙄
  • 0
  • 1
    should people wait for more or pass it as a bs?🙄
  • 6
    OP is bullshit and a waste of time. I mean if I would crack the RSA I would probably not go to devRant
  • 1
    Any update?
  • 0
    @PublicByte isn't quantum computing just better guessing with machine learning? Cant wait to see what the creators of Meltdown do to break this shit...

    https://en.m.wikipedia.org/wiki/...
  • 2
    @arcsector you can think of it more like a nondeterministic machine. Exploring different possible states/paths at once and collapses at a solution.

    Note: this is an abstraction, not how it really works.
  • 2
    @pedrodev OP left a link to a update rant. @xerex09
  • 5
    I was wondering how long this thread would move from skepticism to excitement and on into rage. I'll post some code for you to glance at later so you can see the problems that were encountered.
  • 2
  • 1
    #
  • 1
    update?
  • 2
    @moqs Read the thread?
  • 2
    TL;DR? there are more than 200 comments
  • 9
    @don-rager The CIA blackmailed @Wisecrack with a goat fucker video, and all of a sudden, she claims the algo doesn't work as expected.
  • 1
  • 3
    For a variety of reasons the key space still balloons.

    I'm pretty sure I have 128bit keys down to 18ish hours though from timing the current rate of progress.

    It's gonna require more work -_-
  • 0
  • 3
    Well? Have you broken security as we know it?
  • 1
    @iSwimInTheC There was already a reply, anwser: no.
  • 3
    @Gregozor2121 lol hype is finish
  • 1
  • 1
    🗿
  • 1
  • 1
    Update:

    At approximately 1 AM today, on april 11th, 2020,

    I factored a 64bit product in 556.92 seconds. This was done on a single thread of an i3, in unoptimized code written in python.

    P==NP => TRUE

    Edit: The product I factored was

    11880864431416488451

    I'm now working on products of larger bit lengths.

    The approach was completely different from anything I or anyone else thought of before.

    And worse, it's completely obvious in hindsight.
  • 0
    Also if anyone wants to jump in discord with me and throw some numbers my way in real time, we can test it together.

    Takes 19-20 for 64 bits.
  • 0
    @Wisecrack
    19-20m for a number. Must have missed the 'm' key.

    20 minutes for a 64 bit key is good right?
  • 2
    But what is the time complexity then? Is it really polynomial time?
  • 0
    @cafecortado let just say it's pretty fucking fast.

    Was premature in the post before but I think this is the real deal this time.

    Edit: still working it out. Appears faster than subexpotential time.
  • 0
    Apparently early it is an undiscovered variation of the rho algorithm by pollard. Had me shouting "for fucks sake."
  • 2
    @Wisecrack the fuck, U dont even know about the RSA algorithm, am done, jus gonna call it fraud!!!
  • 0
    @brayo I like to break things, not fix them.
  • 0
    Well I did it. Took about 30 minutes. Probably take longer with factors that are further apart. But it's done.

    Solved partly with dynamic programming.

    Post your 64 bit numbers and I'll try em against this version
  • 2
    @Wisecrack I'm not holding my breath, but what about 19976643039047372800274729278485493309
  • 0
    is there a git repo where we can see what you did?
  • 3
    @yung-stallman no but you scrolled all the way here to just be disappointed.
  • 1
    @yung-stallman yeah but its not this algorithm.

    Built an algol to explore properties of numbers automatically.

    The thinking is every product can be described as an "ad hoc" graph traversal where the nodes are numbers and the edges are operations on those numbers.

    So I built something called Libra to generate and explore those graphs for relationships between numbers for any given product.

    There were tens of thousands of them, dozens of which were applicable.

    This is just one.

    It works off something called a 'sublimate'.

    Which isn't anything fancy. It's just the unit digit and mantissa of a number. I don't know what it's called when you take those two things together (I just know what a mantissa is), so I gave it that name.

    In any case, in the special circumstance of the sublimate of a products root, the sublimate plus some number n relates to the factors of the product p in a cyclic graph.

    Thats part of what the algorithm does, looks for that graph.
  • 0
    @RedPolygon I'll do it here in a bit. Been tiling a wall for the last three hours.

    Anyway to continue what I wrote, heres an example of the graph I'm talking about.

    I always like to use the number p= 697 because it's a trivial case.

    The sublimate of the √p = 6.400757~

    Where n=3, ♎(√p, n) = 9.400757564888170492167773772962391376or 's'

    w*s = 248.18712139690106 (lets call it Q).

    We don't use Q in this case but it's useful in other circumstances.

    w/s = 2.808364898537007 (lets call it q)

    Well for some value q-m there is a number

    that when multiplied by s, equals one of the factors p (either a, the smallest factor, or b, the largest)

    And we see

    (s-1)*9.40075756488817 = 17, one of our factors of p

    Or

    (2.808364898537007-1)*9.40075756488817

    This is the core idea but theres several improvements that make it *much* faster.
  • 0
    I also understand how ridiculous it is to use emoji in formulas (please don't shoot me), least of all astrology emojis but I didn't want to use common greek symbols because those mean something to people who can *actually* do math in different fields, and I needed a common shorthand that was it's own thing.

    Edit: give me a 64 bit bit product, not 128.

    I haven't tested it on numbers that large and you still might be waiting a long (but finite) time.
  • 1
    💡📍📌
  • 0
    @sofo actually this is perfect. The detractors are the ones who should be posting the numbers so they can see for themselves.

    Go https://asecuritysite.com/encryptio...

    enter 32 bit for the prime size, and then generate a number (which should be the 64 bit product) and I'll test it.

    Shouldn't take more than 30-60 minutes based on my current tests as long as the factors aren't more than a magnitude in difference, but even then it should be practical.

    Edit: You have nothing to lose. I'll be the only one who looks like a fool if it doesn't work this time, but by now I'm used to that.

    I kept working after this initial rant/post was made a while ago because after the hype died down I figured I owed it to you all to actually make it work, or at least give it my best.
  • 1
    @Fast-Nop isn't that what they call "the modulus"?

    Kinda confusing use of the term. They should have just called it the product.
  • 1
    @Wisecrack Not sure about the naming - my studies are like decades back. Even then, what I hated most about math was stupid naming up to whole pages of shit that looked like a postscript file got misprinted as plain text. ^^
  • 0
    @Fast-Nop seeing as you're willing to humor me, would you post a 64 bit product (32 bit keys) for me to try out? It's not the massive waits and run times like before. We'll know whether this works within 30 minutes to an hour tops.

    Otherwise people are gonna start calling this new effort a scam and I'd really like to give you guys something that isn't broken trash like last time.

    Also, on the p-q front, I was reading and what the implication is, is not that they have to be orders of magnitude apart, but that *randomly picking the keys* assures security. Well, thats what a random quora poster was on about.

    I've only managed to factor products where the the lowest factor was at most, half of the highest factor but the next goal is to see how fast it runs where 'p and q are secure'.
  • 0
    So I'm running it on some smaller numbers, and it appears that the run time is multiplied by the ratio of the largest factor to the smallest factor.

    32bit products

    p=143282891 (39461*3631)

    factor ratio = 10.86780501239328

    time = 4.7746164s

    p=3391690499 (63671*53269)

    factor ratio = 1.195273048114288

    time: 0.4660498000000004s

    If that holds, then 1 order of magnitude difference between factors of a 64 bit number should mean about 5 hours to crack.
  • 1
    @Wisecrack Yeah I'll see to this tomorrow, I just need to hack some prime checker together for the factors. Looking up 32 bit primes wouldn't be as much fun. ^^
  • 1
    For everyone that previously participated in this thread you can now win five crisp new washingtons by proving me wrong.

    Check it out here:

    https://devrant.com/rants/2495590/...
  • 1
    @Fast-Nop

    mfw no one is responded because you all are busy looking at what I wrote and reimplementing it.

    It's not the whole algorithm fyi. But it can and will find vulnerable products.
  • 1
    @Wisecrack hang in there, I'm sure the algo sort will swing around sooner or later and people will get back on this hypetrain.
  • 1
    @theKarlisK I feel like whenever I got to do a public test thats when my algorithms laugh maliciously and decide THEN to throw up edge cases.
Add Comment