Omnimaga
Calculator Community => Other Calc-Related Projects and Ideas => Topic started by: willrandship on November 06, 2010, 01:01:47 am
-
As you can probably deduce, this is about RSA :P
Here's the idea. Instead of trying to find primes, what about eliminating many non-primes? the calculation is much faster, since, if you do it in a reasonable way, you are dividing an extremely large number by a fairly small one (probably max of 32768 or so, at least at first) instead of two extremely large ones.
Once you eliminate, say, 30-50% (not counting even numbers :P) of all the non-primes, any method of testing would be much faster. Plus, you can manage it in a very community-friendly way, by having one computer test all of the numbers for one number as a factor, gradually moving up the list itself.
Here's an example with very low numbers, but expandable.
original list, 1-50
cut out evens (divide by two)
take lowest number on list (3) and divide all remaining, looking for non-decimal divisions
this gives 9, among others, that you then remove from the list
from there, you move to 5, being next on the list, knowing both 5 and 3 are primes.
Repeat until you reach the point that it would be better just to use the remaining numbers in an algorithm.
For a community-based version: Server has a database with all said numbers (it might be practical to start higher than one :P)
Server gets a request from a PC, sends lowest number and list.
Server gets another request, sends next lowest number and the same list (since the first results aren't back yet)
First returns results, server removes nonprimes from list (if the current lowest untested is nonprime, it bumps it to the next one, no point in dividing by nonprimes)
Second returns results, server removes any remaining nonprimes that were missed by the first, ignores those already removed.
What do you think?
-
Server has a database with all said numbers
There happen to be about 1000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000 or 1e154 numbers to store and search through. Thats around 1e147 terabytes of memory to store all of these numbers. This is some seriously huge amounts of data we are talking here.
-
I know it's been said before, but I'ma say it again:
It's mathematically impossible to find the primes for these numbers within our lifetimes using current hardware.
The idea of starting now would not work, you'd have barely made a dent by the time that hardware that could do this within a reasonable time exists. Chances are that we'll all be on to the prizm by then anyways.
It'd be less effort to break into TI and steal the keys.
-
At the risk of sounding dumb and annoying but what is this RSA and prime numbers and all that thing about? I tried to go through the other topic but didn't have time and got lost, I think. It was a while ago. So just thought I'd ask.
-
At the risk of sounding dumb and annoying but what is this RSA and prime numbers and all that thing about? I tried to go through the other topic but didn't have time and got lost, I think. It was a while ago. So just thought I'd ask.
The nspire OS is signed with an RSA signature, the base of which is computed off of two very very large prime numbers. Get those prime numbers and you can compute your own, making your own OS for the nspire, but they're ridiculously unfathomably large.
-
As you can probably deduce, this is about RSA :P
Here's the idea. Instead of trying to find primes, what about eliminating many non-primes? the calculation is much faster, since, if you do it in a reasonable way, you are dividing an extremely large number by a fairly small one (probably max of 32768 or so, at least at first) instead of two extremely large ones.
That method is known as the Sieve of Eratosthenes. It works, but it's one of the most inefficient ways to eliminate the primes. Basically, you're brute forcing the answer and RSA was designed to circumvent such methods.
-
At the risk of sounding dumb and annoying but what is this RSA and prime numbers and all that thing about? I tried to go through the other topic but didn't have time and got lost, I think. It was a while ago. So just thought I'd ask.
The nspire OS is signed with an RSA signature, the base of which is computed off of two very very large prime numbers. Get those prime numbers and you can compute your own, making your own OS for the nspire, but they're ridiculously unfathomably large.
What's an RSA signature? Just like the thing that keeps people from creating new OS's or hacking it or something?
-
What's an RSA signature? Just like the thing that keeps people from creating new OS's or hacking it or something?
It's like a signature on a check, it just verifies that the OS came from TI, and hasn't been altered.
Also, some math fun:
Assuming that every single person on earth(using 6,697,254,041, what google returns) has a computer with 4GB of ram and a 250GB HDD, you'd have 1,701,102,526,414,000 MB of storage.
Based off of Bboy's calculations, you'd need
1,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000 MB of storage.
That isn't even including the totally overwhelming number of flops you'd need
-
RSA is a method of encrypting so that people who shouldn't know the answer don't. There are basically three classes of encryption methods: noncryptographic methods, such as the MD5 Hash, Weakly Cryptographic methods, such as SHA-1 which are suspected of being faulty, and strong cryptographic methods, such as RSA as well as ElGamal. When a method provides strong encryption, it is exceedingly difficult to break provided that it is used correctly. With RSA, you generate two large primes, then compute several additional numbers related to those primes and use those to encrypt the data such that no one who doesn't know the decryption key can reasonably decipher the message. TI, however, went overboard and used ridiculously large primes, making a brute force crack essentially impossible. The only real way to crack the code would be to exploit a flaw in the algorithm used to create it. Unfortunately, RSA is very secure and has been extensively tested over the years by some of the most knowledgeable people in the field.
-
There is a line between encryption and signing, though.
RSA can be used for encryption, but in this case, it's just used to verify that the OSes haven't been tampered with, or acting as signing them.
iirc, the OSes just have some sort of weird compression on them, no actual encryption.
-
Ah ok, thanks guys.
-
Ah ok, thanks guys.
no problem.
@willrandship, basically, any method there is right now would just take amazing amounts of resources that just don't exist.
-
Aww....
So, if i found it I'm assuming you would accuse me of somehow getting it from TI? :P
-
If you found it and it worked, we wouldn't really care how you got it.
EDIT: In fact, I would be happier if you got it from TI ;-)
-
If you found it and it worked, we wouldn't really care how you got it.
This. :P
Although I'd have my suspicions.
-
So, if i found it I'm assuming you would accuse me of somehow getting it from TI? :P
I'd ask what their system codes were ;D
-
We should find Herb(or whatever the lawyers name was) and beat the codes out of him!
-
He eats lunch at the Blue Cafe every Tuesday at 1:30 sharp. Just sayin'...
-
There is a line between encryption and signing, though.
RSA can be used for encryption, but in this case, it's just used to verify that the OSes haven't been tampered with, or acting as signing them.
iirc, the OSes just have some sort of weird compression on them, no actual encryption.
I think how it worked was that the boot2 was compressed and the OS itself was encrypted. Of course, once Goplat figured out the compression of the boot2 and extracted the binary, it was a relatively simple step to run the OS through the decryption routine in the boot2.
-
I know it's been said before, but I'ma say it again:
It's mathematically impossible to find the primes for these numbers within our lifetimes using current hardware.
The idea of starting now would not work, you'd have barely made a dent by the time that hardware that could do this within a reasonable time exists. Chances are that we'll all be on to the prizm by then anyways.
It'd be less effort to break into TI and steal the keys.
Sounds like a job for the Lobster nation army... :D
-
I doubt Herb has a really long hexadecimal number memorized. :P
And unfortunately, the boot2 has its own certificate. If we wanted to (and we had the key) we could simply do a complete format and overwrite the boot2, except that the checker for it is the boot1, which is ROM (not flash ROM either, completely unchangeable)
-
except that the checker for it is the boot1, which is ROM (not flash ROM either, completely unchangeable)
It actually is Flash ROM, and there is code in the diagnostics to re-flash the BOOT1 from a file read from an SD card. But there's no reason you'd ever want to flash it because 1) there would be a major chance of completely bricking your calculator, and 2) unless you have whatever hardware TI uses to connect an SD card reader, only way you could flash it is if you already have the ability to execute your own code, which would mean there's no point.