Print

[crystalgeek]

i know its  a lot of numbers lol, but at least it would be a start by giving us all the multiples of the public key right?

[crosseye]

The problem is that it would take a SETI like program with thousands of computers working all day for like a year or more. I still think you are underestimating the sheer volume of what you are asking. Your computer would crap out and complain of massive headache before it even got close.

[VoiceOfReason]

QUOTE(crystalgeek)

lol all jokes aside would it not be easier to write a simple script to figure out all the multiples of the public key and then to test them?

heres how i see the program written

N defined as 1
Public key = P
A = Number
(etc)

Dude, you totally need to send that to a mathematical journal and have it published. You'll be famous!

There are exactly two factors of the public key. Good luck finding them. Start your computer running your program, and someday after the stars have grown dim and the universe is crumbling to dust it might complete... but I doubt it.

QUOTE(crosseye)

The problem is that it would take a SETI like program with thousands of computers working all day for like a year or more. I still think you are underestimating the sheer volume of what you are asking.

Actually, you're guilty of underestimation too... by a lot.

This is a 2048-bit key, created by multiplying together two 1024-bit prime numbers. So there are 2^1024 keys to check, or about 10^308. Specificially, that's about a trillion trillion trillion trillion trillion trillion trillion trillion trillion trillion trillion trillion trillion trillion trillion trillion trillion trillion trillion trillion trillion trillion trillion trillion trillion potential keys.

Suppose your computer is able to test a trillion keys in a trillionth of a second. Your program will complete in 10^277 years. If you started it running at the Big Bang, it would be about 0.000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000001% complete.

Okay, so computers will get faster. Let's take your computer, capable of checking a trillion keys in a picosecond, and make it not twice as fast, not three times as fast, not ten times as fast, not a thousand times faster, but a trillion times faster. Now your program will complete in only 10^215 years.

So we'll go with the distributed model. We'll make like SETI and get a whole bunch of computers in on the act. Let's give every one of Earth's six billion people a computer and network them all together. No, wait, that's not enough. Let's give every one of Earth's six billion people a million computers and network them all together. Let's assume this network is infinitely fast and every computer can receive and submit work units in no time at all. Now our runtime is merely 10^199 years.

Still no good, we're gonna need to call in the extraterrestrials to help. There's about 100 billion stars in the Milky Way galaxy. Let's assume that every one of them (except our own) has ten Earth-like planets, with similar population as Earth, and give every one of those little green men their own collection of a million computers and add them to our network. Now our runtime is down to a snappy 10^187 years. Of course, that's using only our galaxy. It's unknown how many galaxies are in the Universe, but let's arbitrarily say there are a billion trillion of them and add them all to our network. We'll be done in 10^166 years.

But who's to say there's only one Universe? Maybe there are several parallel Universes, and maybe we can enlist them all. Let's say that for every single proton in our universe, there's another whole Universe out there we can somehow communicate with and get them to devote every one of their resources to cracking the Xbox 360 key. That'll get the runtime down to a very manageable 10^80 years or so... which is only a billion billion billion billion billion billion billion billion billion times longer than the entire age of the Universe.

But you want your SETI-like project to complete in a year. Frankly, I'm at a loss as to how we can reduce it any further.

Someday, the problem of factoring big primes will be solved -- and that day will be a terrible day, because while you may be able to sign your own Xbox code, the security that controls everything will pretty much collapse. But until that day, forget about cracking the key. Brute force won't do it, no matter how enthusiastic you are.

[VoiceOfReason]

By the way, crystalgeek, I notice you're writing every result to a file... which would take a bit more than 10^600 bytes. Let's say that they manage to get hard drives ultraminiaturized, so you can store a trillion terabytes in a cubic nanometer. Assuming the universe has been expanding at the speed of light since the Big Bang, it now has a radius of about 20 billion light years. If it were packed completely full of these ultraminiaturized hard drives... no stars, no planets, no empty space, just hard drives... you'd have about 10^107 bytes of storage space, which is 1/1000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000th of what you'd need.

[gjm]

However! The first two combinations you try, could just be the right ones..  

[crystalgeek]

ok well i said im no programmer but it would work only taking twenty thousand years no worries

[sn4k13s]

lol...i was just going to say that it would take too long for all the computers in the world to calc together to solve the problem. but im sure he got the point with your examples.  nice job

[crystalgeek]

well lets add two then and im sure when someone thinks of a better way of factoring prime numbers then the world will be a better place, althou as i said it WOULD work just taking forever by then no one would care anymore lol

[ajouvenat]

Don't forget to add all the time it would take to actually test each key.  

[lordvader129]

im having a hell of a time even finding a publishd list of primes to use as potential factors, i can find the 10,000 smallest, but they are all 6 digits or less, too small to be considered here, and the 5000 largest known, all of which are over 1000 digits, too big, i cant seem to find anything in the 100-500 digit range, which what i think we need to be looking at

figuring that, we'd probably have to run 2 processes simultaneously, one to calculate a new prime and one to try to divide it into the key, given that there is no discernable pattern to prime numbers even the first process will take an ungodly amount of time

after some more research i found why i cant find any lists of 100-500 digit primes, the number of primes below a certain valu eis given by a formula, for 4*10^22 the number of primes is 783,964,159,847,056,303,858 (thats the current world record) we need to know all primes to the order or 2*10^600 or so, just giving a simply unfathomable amount of possible factors

also remember an RSA key can be 2 or more primes, so even if you find a factor after all of this there still might be more, youd have to test the primality of the result to see if its actually just 2 primes and not more, if its more youd have to start over at square one (albeit with a smaller number)

and thats just for xbox1, 360 probably has an even bigger RSA key, 4096bit or even larger

[CattyKid]

Anyoen listen to Coast to Coast AM or have ever heard of Remote Viewing?  Supposedly, it is real.  You might be able to go to Google and type define:remote viewing.  
Why don't we have a psychic remote view the digital signature for us?!

[ruli00]

QUOTE(CattyKid @ Dec 5 2005, 11:49 PM)

Anyoen listen to Coast to Coast AM or have ever heard of Remote Viewing?  Supposedly, it is real.  You might be able to go to Google and type define:remote viewing.  
Why don't we have a psychic remote view the digital signature for us?!

From What ive read in this thread, it may be the only way.

[Derrida]

Hey, I'm absolutely in over my depth here, but if one went to MS and got an XBE signed, could it be reverse-engineered into the real thing? I mean, I know it can't be converted directly, but would it reduce factoring time by any significant amount? Or does random seeding foil that completely?

[Vegita]

QUOTE(Derrida @ Dec 6 2005, 09:25 AM)

Hey, I'm absolutely in over my depth here, but if one went to MS and got an XBE signed, could it be reverse-engineered into the real thing? I mean, I know it can't be converted directly, but would it reduce factoring time by any significant amount? Or does random seeding foil that completely?

It would basically come down to the brute forcing problem the others have already discussed.

Unless we build a quantum computer or something the brute force approach isn't feasible. The mathematics of it are very sound... much more likely there's some human error goofup somewhere that can be exploited... and seeing how the system was RUSHED... i'm sure there will be one... and that's only MS's fault.

Honestly when I read about these overheating issues it makes me think this thing was very rushed... which raises my hopes there is some simple exploit waiting for us.

[Safrole]

I agree with that.  I hold hope that this "hypervisor" is not so hypervigilante.  There seems to be a lot of "hype" in the name anyway.  But then again I'm like a monkey looking at the space shuttle.

Maybe the M$ signing computer is just sitting in the corner of some room and they have some flunky answering the phone sign apps in their spare time.

"Hello, M$.  Yes, yes it is.  No he's out to lunch.  I'm sorry can you hold on a minute?  I'm in the middle of signing Halo3...."

Or maybe somebody at a factory in some third-world country making chips can lend a helping hand. (?)