Omnimaga
Calculator Community => Other Calc-Related Projects and Ideas => TI-Nspire => Topic started by: willrandship on June 29, 2010, 01:04:36 am
-
Just think: a virus that infects a computer, completes some rsa factoring, sends results to a server as it does (so as not to duplicate work), and spreads to some more hosts. Nobody notices it's there since it has a low processor priority, and we get the nspire keycode super fast! (well, not super fast, but you get the idea)
Like it?
-
I don't think it would need to be a virus (which is incredibly difficult to write). I'm sure a lot of people in this community as well as Cemetech, UTI and other forums would be willing to donate some of their cycles for it and a news article on ticalc would draw a lot more participants. The bigger question is is there anyone who actually cares enough to write the software required to do this? That would take a lot of time, unless one already exists, in which case we'd just need to borrow someone's server.
-
I dont like the idea of a Virus designed to crack Texas Instruments codes being designed at Omnimaga. That being said, a *voluntary* system similar to the one they used to crack the remaining codes could be used, but this is 1024 bit we are talking about, that is enormous. There is also memory requirements, which are also large, although you would have to ask someone more knowledgeable in factoring the keys than me to get the specifics. Bottom line: No Virus
-
I am against the virus idea. I think it's even illegal since it's kinda malicious in some ways to infect other ppl computers against their will. It would be better if someone wrote a program that people install only if they wish, to help cracking the key.
-
Factoring a 1024-bit key in a reasonable amount of time is impossible, even as a collective effort, unless you can find hundreds of thousands of cores.
The 768-bit number factored recently took several months of highly coordinated effort on a cluster.
-
willrandship, your idea is probably already used in the wild, just not applied to numbers this size ;)
* factoring RSA-768 took than two years of highly coordinated effort on several clusters totaling hundreds of computers (and even more processor cores). The effort was led by top researchers of the integer factoring field, who used unpublished algorithms that are better than the published ones (ggnfs, cado-nfs, msieve). And sieving integers that large takes an awful lot of memory.
* factoring 1024-bit integers by GNFS (i.e. integers without special mathematical properties) is at least a thousand of times harder than factoring 768-bit integers.
Has a Fermat attack been tried on the Nspire and Nspire CAS keys, BTW ? It's extremely unlikely that it would yield the factors (the 512-bit keys wouldn't have fallen to it, the factors were too different from each other), but we never know.
-
It's worth a try, but it hasn't been done to my knowledge.
-
Well, every bit you add doubles the difficulty, so 1024 is 2^256 harder than 768. That's a lot more than 1000. :P Not very easy at all.....
I was thinking, if you assign computers to do so many numbers, randomly within a certain bit range, it might go faster, so:
(increments of 40 example)
Server:
0-40 Unsolved
41-80 Solved, no answer
81-120 In process by 12.60.2.255
121-160 Unsolved
When a computer finishes its portion, it receives a random other portion to solve. Hopefully, several computers doing this all at the same time should hopefully hit the solution eventually, and the server sends the message to all the rest, spreading the key instantly to (hopefully) thousands of people!
By a fermat attack, are you referring to http://en.wikipedia.org/wiki/Fermat%27s_factorization_method (http://en.wikipedia.org/wiki/Fermat%27s_factorization_method)?
I'd be willing to write it if I knew how a little better. Unfortunately, my best programming language is still TI-Basic :P I have lots of time on my hands for this kind of thing.
Yes, I know 40 numbers is nothing. It was just an example. It would probably be maybe 30-minute segments, not too long or they get interrupted before they finish when you turn off your computer.
brute forcing the key doesn't require much memory. Check that perl script's memory usage, and it's slim to none. But yes, the virus portion was a bad idea.
I had one other idea: Where exactly is this code stored? Is there any way we could replace it with a different key, that we know? That way, you couldn't have the nspire OS (which sucks anyways :P) but you could have another OS, maybe similar to KnightOS, or moonshell (flashcart menu for DS) based.
Edit: repitition fix. Sorry about that.
-
Well, every bit you add doubles the difficulty, so 1024 is 2^256 harder than 768. That's a lot more than 1000. :P Not very easy at all.....
(http://www.cs.brown.edu/people/aaronak/over9000.jpg)
Sorry, I couldn't resist. :P
But seriously, if it's this much harder, I doubt even 10000 computers with quad core processors could manage to do it during our lifetime.
-
Actually, I had planned on doing this a long time ago, but there was a hiccup in the program and it wasn't factoring it right. It was basically just a C port of the perl algorithm used on the hackspire site(link (http://hackspire.unsads.com/wiki/index.php/OS_upgrade_files#Breaking_RSA_:_an_new_twist_on_an_old_algorithm)) with some minor changes to allow for already checked keys and an update routine to shoot of to the server ever once and awhile. There was a problem in it though, for some reason the library I was using or something just kinda broke while trying to work with these numbers :/. I also tried a C# library I found on the web, it might have actually just been a .NET binding of the C library but it's been awhile ago so I'm not sure.
You could just modify the perl script instead of porting it, but I wasn't(and still am not) able to write perl, but it probably wouldn't be too hard. I had original decided to port it since a C derivative would have been faster(being compiled and not interpreted) and I would understand the coding more than the perl script since I have been working with it for much longer.
-
I would actually say that if you are doing a distributed computing project, java is your best bet. Simply download data file with server name and the key to be factored, and have the program automatically look at the file. Judging by the ease of use, it makes it possible for even non- programmers to help.
-
ease to use would be the best solution. Trust me, I hate when I download a software and despite reading the instructions, it's still a major pain to use, or when they don't even provide binaries with the download and force you to compile the whole thing. It generally turns me away. I am sure it's the same with several other people. If it's easy to use, more people will be interested in running it. Look at how many BASIC programmers there are in the TI community compared to ASM.
Also, it would be nice if not done already if such software continued where they left off when the computer shuts down, for example. We never know when a power outage could happen.
-
i was hoping for something that would be completely automatic user-side, so you just run it.
For power outages, I was thinking since it would do segments, reporting to the server every time. you would simply lose maybe 15 min. of progress in a power outages
-
Oh ok. Doesn't sound too bad then. I was worried it was only saving once you manually close the software or something. That would have sucked.
-
Well, this way the server can send new numbers faster. If it doesn't recieve one set within x min/hrs of sending, it resets it to open.
-
Can we use BOINC?
-
Well, BOINC would mean the computers act like one supercomputer. The idea I had in mind would have them all as separate computers sending information to a server and (hopefully) working faster and it could be random, but still regulated.
If you can work out a way for BOINC to work, though, why not? I have an atom that can be our master node, but you'll have to tell me how to set it up.
-
Perhaps we could just ask TI nicely? Pretty please with sugar on top? [picture of lolcat]
But they apparently are pissed that the previous keys were cracked, so they went all ninja with the Nspire key...
:'(
-
Perhaps we could just ask TI nicely? Pretty please with sugar on top? [picture of lolcat]
But they apparently are pissed that the previous keys were cracked, so they went all ninja with the Nspire key...
:'(
I'm pretty sure the Nspire came out before the other keys were cracked.
-
Well, every bit you add doubles the difficulty
Well, no. From the introduction of the RSA-768 factoring paper linked to from http://france.rsa.com/rsalabs/node.asp?id=3723 :
This result is a record for factoring general integers. Factoring a 1024-bit RSA modulus would be about a thousand times harder, and a 768-bit RSA modulus is several thousands times harder to factor than a 512-bit one.The figure given in the paper assumes that GNFS is used, as it should for an integer of this size: it's the only currently known method that wouldn't yield a thoroughly impractical run time. TF, whose run time is thoroughly exponential with the number of bits (2^n), wouldn't make the cut in our lifetime, unless we are extremely lucky.
I would actually say that if you are doing a distributed computing project, java is your best bet.
The JIT in Sun's JVM is a good one, but the code it yields remain far from the performance reachable through native code. Nobody uses Java for distributed computing.
Judging by the ease of use, it makes it possible for even non- programmers to help.
Well, have you ever tried to join a BOINC project, be it RSALS or another one ? ;)
Lots of non-programmers (hundreds of thousands or millions, worldwide) are using easy-to-use distributed computing.
Well, BOINC would mean the computers act like one supercomputer.
Yes, but only for the easily parallelizable part of the NFS algorithm, called sieving. You'd still have to use an uncommon computer, or presumably a cluster of uncommon computers, for the post-processing stages.
I'm pretty sure the Nspire came out before the other keys were cracked.
Indeed, by more than two years.
-
despite the fact this is nearly impossible, it really wouldn't hurt to try, would it? We could advertise it to the TI community and other large sites that might care, see how much power we get, and decide from there, even if it would require extreme luck, the key would be so valuable that the combined effort would seem like nothing.
tldr: this is impossible. let's do it anyways
-
I hope TI wouldn't try to block the project in every way possible, though. It might be good to not advertise in public way too much either.
-
We could advertise it to the TI community and other large sites that might care
How are you going to do that without TI somehow noticing and getting in our way ? ;)
(OK, factoring their keys is for the purpose of creating alternative software that runs on the devices we own, which is largely allowed across countries. But the previous time, that it's allowed hasn't stopped them from getting in the way of publishing the results, and later, they attacked Ndless - so why wouldn't they get in our way yet another time ?)
From the RSA-768 paper:
[...]Although different sieving-clients do not need to communicate, each client needs to communicate a fair amount of data to the central storage location. This required a bit more organizational efforts than expected, occasional recovery from mishaps such as unplugged network cables, switched off servers, or faulty raids, [b]and a constantly growing farm of backup drives[/b]. We do not further comment on these more managerial issues in this article, but note that [b]larger efforts of this sort would benefit from full-time professional supervision[/b].
-
I say that is worth to try some algorithms for special keys cases because we might be lucky. But for now it is impractical a full sieving.
Resuming work on Ndless is the way to go and we can find some tricky exploits like the TI-83+ pulling batteries during 3rd party OS sending or other tools like BrandonW released (he did).
Now, if anyone works on RSA-1024 investigation please choose the Nspire keys cracking and give news when you have the keys. j/k
-
So I shouldn't continue making a cracking program? All I have left todo is create a network interface and it will be ready to go :-X
-
Making network-aware any program based on TF (trial factoring) doesn't seem that useful to me.
However, for those who want to burn lots of CPU cycles with very, very low chance of success, I think it would still be useful to make the TF program as fast as it could be, by switching to compiled languages, as you've started doing. In Perl, the most CPU-intensive routines of Math::BigInt are native code (at least, if using GMP), but Perl has some overhead on top of GMP.
I've added a second Perl script to http://hackspire.unsads.com/wiki/index.php/OS_upgrade_files . It's still TF, but with 512-bit pseudo-random numbers generated by a LFSR seeded by the current time.
-
really, the chances of us solving this before we can make a quantum computer to do it don't look too go. we should wait until then :P
-
Well if the program can be optimized/modified to do it faster still, I would wait until it's optimized/modified and then start the key factoring
-
I'm happy to say that my C/++ port works a lot faster than the perl script. But unfortunetly it seems neither are able to crack rsa keys effectively :'(
I had been messing around with mine and wondering why the secret key 'd' for the TI-84+ keys I've been testing with always comes up wrong, and so I tried on the perl script and it was ALSO wrong. Can someone verify this just to make sure this is not just a fluke?
-
Aw sorry to hear :/
-
I had been messing around with mine and wondering why the secret key 'd' for the TI-84+ keys I've been testing with always comes up wrong, and so I tried on the perl script and it was ALSO wrong. Can someone verify this just to make sure this is not just a fluke?
Indeed, the value of d computed by the Perl script for the 84+ key, and the one that can be found at various places, do not match... but, er, the following piece of Java code outputs the same value as the Perl code !!!
p = new BigInteger("94489014C63CC9E1E1ADB192DBBDD1F78F90A630DA9C86EFC4CBCA44E5B4D54D",16);
q = new BigInteger("19D431AF2794229620B884E3750D622D1C74F2E4569DC15486FC8D5A3BCDFE2F5",16);
// Find PQ and phiPQ
pq = p.multiply(q);
phiPQ = (p.subtract(BigInteger.ONE)).multiply(q.subtract(BigInteger.ONE));
// Find E
e = new BigInteger("11");
// Find D
d = e.modInverse(phiPQ);
System.out.println("d: " + d.toString(16));
Why ?
Mistake caught by BrandonW on #ti: PEBKAC on my side, I was using 11 (decimal) instead of 0x11 (hex) for e. With 11 in base 16, the values of d match. Tribal, maybe you did the same ?
-
i was messing around with really smalls keys just for the fun of it, and sometimes my d would come out negative and i'd have to add phiPQ to it
-
BTW, my LFSR-randomized TF Perl code unconditionally divides n by p, no matter p is even or odd. This is because in Perl, letting it do so is faster (on my computer, anyway) than shifting p right while it's even, and dividing n by p only when p is odd. However, I'd expect things to be different in C: both parity test and 1-bit right shift can be performed in many less processor instructions than computing a ~1024-bit number modulo a ~512-bit number...
-
I only think that people would more or less be willing to do it if all the had to do was put a program on their computer, that could easily be uninstalled by removing one file. (Well, except the temporary data files.)
Also, for anyone thinking about Trial Division, I promise it won't work. If you write a program that starts with three, and adds two to every number after that, it will take absolutely forever. Distributed computing won't change that.
So then, I would be okay with boinc. Will you set it up, Lionel?
-
If you write a program that starts with three
wouldn't it be best to start at sqrt(n) and work either up or down (both if adventuresome) because don't the factors usually have about half as many digits as n? so, they'd be closer to sqrt(n) than 3 or n/3
-
If we use the GNFS, how in the world will we find a computer powerful enough to solve the matrix?
-
offtopic, i know absolutely nothing about the nspire or what RSA is, or what you're trying to do. However, bwang's post made my day. it needed to be noted. [/offtopic]
on a more related note.. would anyone care to explain exactly what you are trying to do? or link me to a good article?
-
well, you could try the wikipedia page on rsa keys
basically, we've got this number n, and we know that it is the product of two VERY LARGE prime numbers p and q. And there's this other number d that we really want to have, but the only way to get it is to break into TI headquarters, or figure out what p and q are. The only way to do that is with a sophisticated 'guess and check' system that would possibly take years
-
that sounds.. depressingly hopeless :-\ and what are the possible benefits of getting this number d?
-
RSA is a public/private key cryptographic system. Basically, there is a key that we have that is the public key. If we factor the public key, then we can find the private key. The thing is, although factoring a number sounds easy and possible in your head, like counting, these numbers are far beyond a person's comprehension. They are mind blowing huge, and that is just the 512 bit ones. We're talking about 1024 bit here. Very hard to factor.
I don't exactly know how GNFS works, though.
-
it essentially lets us *cough*hack*cough* the nspire, write custom OSes for it, etc.
and GNFS (general number field sieve) is the 'sophisticated' part of the guess and check system
-
that's a lot of faith TI is hinging on one number...
sounds interesting though. i'll do some of my own research later.
-
We should use Cabamap.
It would be so lolworthy if we cracked the Nspire key with an 84...
-
With an 84? Are you crazy? Use a TI-81.
@nemo: They have good reason to have faith in that number. It's encrypted with 1024-bit encryption. To put that into perspective, it took a team with extremely high-tech resources about 2 years to decrypt a 768-bit number.
-
1024 bits is 128 bytes. That is a big number. It would be impossible with a ti-84.
-
Alright, I will write up a program to use a guess and check system, and we can sync it up on all of our computers. It will pick up where it left off each time you start up, and let you know when it finishes.
-
2 years? for only 768 bits? that's ridiculously long.. and you guys want to tackle 1024? good luck. let me know if i can help though, i'll gladly install a program on my computer if it won't give me any hassle.
-
If we use the GNFS, how in the world will we find a computer powerful enough to solve the matrix?
I lol'ed XD
Anyway, one positive thing about this is that it could maybe spark interest from non-calc communities as well. Remember how many new members got involved in the key factoring discussion and Ndless talk when it made ticalc.org front page and other non-calc sites front pages?
-
Heh. If only we had access to a TOP500 supercomputer or have some Omni@home project requiring all the spare CPU of the entire TI community. Yeah, I like this BOINC idea.
Actually, if would be awesome if we can crack a RSA-1024 because the biggest RSA number ever factored was RSA-768... Even RSA, at one time, had a challenge about factoring their keys. http://en.wikipedia.org/wiki/RSA_Factoring_Challenge
-
the 1024 bit key has a $100,000 prize. We should apply whatever we do here and win it.
-
the 1024 bit key has a $100,000 prize. We should apply whatever we do here and win it.
That's been withdrawn.
I hate to be a party pooper, but the computer power required to do something like this is inconceivable.
at each bit increase, time taken to compute doubles.
768 took 2 years.
769 would take 4 years.
770 would take 8 years.
771 would take 16 years.
etc...
1024-bit, given current tech, would be completely infeasible. You'd have better luck with the power supply flickering techniques.
Edit: a little bit more of perspective
1024-bit RSA Signatures are what the Xbox 360 uses to prevent unsigned code from being ran. That's a multi-million, probably into the billion, design cost that selected RSA-1024 as the signature method of choice. They designed the system to be viable for 10 years as of 2005. Assuming that the computing power in 2015(and that we don't die in 2012) is powerful enough to crack one in 2 years(which is a big assumption), the nspire would likely be replaced or on the verge of replacement, going off of TI's previous release cycles.
-
The GNFS is not of exponential complexity (in fact, that is why people use it). Its complexity is:
O(exp((c+o(1)) * log(n)^(1/3) * log log (n)^2/3)so doubling n does not double the run time.
-
I only think that people would more or less be willing to do it if all the had to do was put a program on their computer, that could easily be uninstalled by removing one file.
Well, that's the case with a Perl script, a Java class / archive or a C/C++ program pre-compiled for the most common platforms :)
wouldn't it be best to start at sqrt(n) and work either up or down (both if adventuresome) because don't the factors usually have about half as many digits as n? so, they'd be closer to sqrt(n) than 3 or n/3.
Definitely. Besides, that's what both Perl scripts are doing: they start working on numbers whose size is near from 512 bits.
Also, for anyone thinking about Trial Division, I promise it won't work. If you write a program that starts with three, and adds two to every number after that, it will take absolutely forever.
Yes, exhaustive TF is going to take forever, but it may produce a miracle. TF'ing the Nspire's 1024-bit RSA keys is a challenge comparable to playing at the national and international lotteries (well, the odds to win the factorization are even extremely lower than winning any lottery) - but that does not stop millions of people all over the world playing at the lotteries :)
Will you set [a BOINC project] up, Lionel?
No. As I wrote above, and as you repeated, TF is almost hopeless.
Together, we can spend several CPU-years in total on TF-ing the 1024-bit numbers with random integers of 480-512 bits. But we don't need a BOINC project for such a low effort (in distributed computing measurement).
If we use the GNFS, how in the world will we find a computer powerful enough to solve the matrix?
Indeed, and we would also need to find the algorithms that were used for RSA-768 but remain, AFAICT, unpublished so far. But it may be insufficient: in order to scale up three orders of magnitude, those algorithms are likely to require further improvements.
1024 bits is 128 bytes. That is a big number. It would be impossible with a ti-84.
It's entirely possible to divide 1024-bit integers by 512-bit integers on TI-Z80 calculators - but that would be orders of magnitude slower on a calculator than on a moder PC, all the more the Z80 does not have division / modulo instructions.
(the irony of a TI-Z80, TI-68k or Nspire calculator factoring a 1024-bit RSA key by TF would feel extremely bitter to TI :D)
Anyway, one positive thing about this is that it could maybe spark interest from non-calc communities as well
Indeed. But the serious factoring community would probably (and rightfully) frown upon spending an unreasonable amount of effort TF'ing a 1024-bit number.
I hate to be a party pooper, but the computer power required to do something like this is inconceivable.
Between others, I have pooped the party before you did, don't worry ;)
The rule of thumb (which I saw on MersenneForum) for the formula just posted by bwang is that the amount of work necessary for GNFS doubles every five-six digits.
Tribal, could you post somewhere your C conversion of the Perl script ? TIA ;)
[EDIT: grammar.]
-
Assuming that the computing power in 2015(and that we don't die in 2012) is powerful enough to crack one in 2 years(which is a big assumption), the nspire would likely be replaced or on the verge of replacement, going off of TI's previous release cycles.
Not sure about that...
TI has no interest any more in designing new graphic calculators (Casio has been releasing more calculators in the last 3 years than TI)
TI has completly abandonned TI-68k technology since 2002/2003, and is doing allmost nothing for the TI-z80 technology.
TI is only interested in the Nspire technology, which is primarily a software runnable on different systems.
I think the TI-Nspire is going to be the last "true" graphic calculator made by TI.
As you aren't using a mechanical calculator, I think we won't be using graphic calculators any more in 10 years.
What we'll be using will be a little portable computer (netbook? pocketPC? PDA? phone?...) with a non-math oriented OS, but running a math-software.
All graphic calculators designers have understood that, as there is a software-equivalent for their latest calculators:
* TI has the "Nspire SmartView" software
* Casio has the "ClassPad manager" software
* HP has the "Xpander" software
I don't know about Sharp.
-
I think the TI-Nspire is going to be the last "true" graphic calculator made by TI.
As you aren't using a mechanical calculator, I think we won't be using graphic calculators any more in 10 years.
What we'll be using will be a little portable computer (netbook? pocketPC? PDA? phone?...) with a non-math oriented OS, but running a math-software.
That might not be the case for TI. They've been making graphing calcs for a while now that were at least intended to just do math ;), so they'll probably just make their own little portable thing that only runs their own software.
For the moment here's some ideas that would really hit TI where it hurts:
Apply for a job as a software developer at TI and "accidentally" release their secrets. [We really need a ninja smiley]
Amass an army of nSpires, all linked with their USB port to factor the key. [TI-81s would've been better, but they don't have link ports]
-
Yea, and schools are very slowly adopting the 'Lets give every student a computer in the class' idea.
-
have you ever wondered if the government (or RSA Laboratories) has a list of all these factors for all these keys somewhere for security purposes?
-
Doubtful.
Even if they did, 2048-bit keys are not breakable in any reasonable amount of time.
-
Actually, technically the nspire is just that: a common netbook-style processor (granted, a fairly weak one)
If they wanted the nspire to be some fancy handheld computer, they could do it with one OS release. The OS currently used on the nspire is one made for mininetbooks anyways, so it would take minimal effort.
Better yet, fb39, get an army of 81s with all their keypads hacked to talk to each other, and crack it.
Edit: Oh, btw I'm leaving on another trip, won't be back until tuesday night. Sorry!
I was thinking: if we used ndless, could we ever access the area of the memory to change the factor required? We could make our own rsa key and replace ti's (making a key takes like 3 seconds)
-
I was thinking: if we used ndless, could we ever access the area of the memory to change the factor required? We could make our own rsa key and replace ti's (making a key takes like 3 seconds)
I really don't know much about this, but I don't think TI would make it that easy on us. If that was the case, I would think that the same thing would have been done to get the keys for all of the other calcs.
-
I was thinking: if we used ndless, could we ever access the area of the memory to change the factor required? We could make our own rsa key and replace ti's (making a key takes like 3 seconds)
I really don't know much about this, but I don't think TI would make it that easy on us. If that was the case, I would think that the same thing would have been done to get the keys for all of the other calcs.
Back before the keys were cracked, BrandonW released some programs for Z80 calcs (73 and 83+) that patch the certificate to allow this; one gets the 83+ to accept community-signed OSes, and one gets the 73 to accept community-signed apps.
http://www.ticalc.org/archives/files/fileinfo/420/42048.html (http://www.ticalc.org/archives/files/fileinfo/420/42048.html)
http://brandonw.net/calcstuff/free73.zip (http://brandonw.net/calcstuff/free73.zip)
And there's also a program called FlashAppy that does the same thing for 68k calcs, it gets them to accept community-signed flash apps.
http://www.ticalc.org/archives/files/fileinfo/413/41328.html (http://www.ticalc.org/archives/files/fileinfo/413/41328.html)
So it's probably not impossible for the Nspire.
-
Yeah I remember that, it came out only a day or two before FloppusMaximus announced he factored a key on United-TI. It was a major revolution when BrandonW released this, even thought it was quickly obsoleted ;D
-
I had been working on a project for this and have a successful C++ port of the perl code on hackspire, which checks keys around 3x faster(based on the C++ version taking around 2m for 5000000 numbers and the perl script taking around 6m). Although, my network programming experience is near to none, and it might be awhile until I can get a server/client interface set up :/
If anybody would be interested, I can see what I can do about just packaging up the factoring part of the program along with the source code and putting it up somewhere. This incomplete version of the program would allow you to start at a position of your choosing(instead of getting this information automatically from the server like the full version will) and will be able to save/load your work upon exiting and re-opening.
-
I'm glad to hear this, I've been checking the discussion on and off in #omnimaga/OmnomIRC in the past two days. I wish you good luck for the networked version. I would love to help factoring that key.
-
As per a few people's request, I've attached the source code of just the factoring part of the program. I will be putting up a LSFR-randomized version in a bit if I can get it working(thanks to debrouxl for sending me the perl script since hackspire is temporarily down, and also for suggesting on making it). And hopefully debrouxl will be on soon to help me if I can't figure out the problem I'm having :-X
EDIT: Added a non-functioning LFSR version as cspire_lsfr.zip. Can someone check it out and see what I'm doing wrong?
-
Well, I don't know what your exact problem was, but the "0x" in "mpz_init_set_str(tap, "0xa48...");" was definitely a problem :)
(I got myself bit too several days ago by the exact same problem, in Java :D).
I'm attaching a new version of the C(++) LFSR-based program. It's much faster than the Perl script indeed, I thought the overhead of Perl would be lower. The LFSR is seeded with the current time; for better seeding, on POSIX platforms, we could use gettimeofday().
Some performance analysis using Valgrind on my Core 2 reveals that:
* it's much faster to mindlessly divide by all odd integers than to use any form of primality testing. And we can do slightly better than mindlessly dividing, by adding several trial divisions by the smallest primes;
* mpz_divisible_p is slightly faster than mpz_mod + mpz_cmp_si.
Enjoy :)
NOTE1: you probably want to rate-limit the program's output further, e.g. write data every 1048576 iterations rather than every 65536 iterations :D
NOTE2: for best results, compile GMP yourself from the sources (`./configure --prefix=$PREFIX --enable-cxx; make; make check; make install`): GMP tailors itself to your processor architecture, which results in a noticeable speedup for me, compared to stock Debian x86_64 binaries.
[EDIT: attaching a new version, with resuming support and automatic "0x" removal.]
-
I was thinking: if we used ndless, could we ever access the area of the memory to change the factor required? We could make our own rsa key and replace ti's (making a key takes like 3 seconds)
I think I read somewhere on hackspire that the factors were stored in read-only memory.
BTW, how do you show who a quote was from?
-
[q u o t e=<poster name>]...[/q u o t e]
-
Isn't a uint64_t just a 'unsigned long long int'?
-
With GCC, I'd say yes. With compilers that don't support 'long long', no :)
(well, MSVC doesn't embed stdint.h, unless you're using the 2010 version. I don't know whether that one supports 'long long')
-
My computers have now performed a bit more than 10^12 trial divisions on 0xaba7... unsurprisingly, they did not find a factor :D
I'll switch them to TF on 0xc3b3 by the end of the week, and will stop TF attempts when both numbers have received roughly the same number of attempts (somewhere between 1e12 and 2e12). Doing more than this would not be reasonable.
Whatever we do, we collectively can't reasonably make more than somewhere between 10^14 and 10^20 TF attempts, but we'd need ~10^155 >> the estimated number of atoms in the universe (~10^100) >> 10^20.
-
I don't know what any of that stuff means, being a TI-BASIC/Axe coder mostly, but good luck on this project :P
-
Which is why trial division is not a good way to factor it. It is the easiest method, though. I wonder how much distributed computing would add to that. How long has it been running?
-
We don't have access to the only practical method (or rather, the only not-completely-impractical method) for factoring 1024-bit integers.
My 4 cores (4-year-old models, Core 2 Duo T7200 & T7600) perform between 10^6 and 2*10^6 per second each, which translates to <250K seconds (~3 days full-time) for 10^12 operations. Even if we used a million equivalent computers for a year (which is wildly unrealistic), we wouldn't reach much above 10^20 operations, hence my figure above.
TF-ing these keys is no different in principle from playing at the lottery - the odds are extremely lower, but no money (my computers are loaded 100% with grid computing anyway, this is just a different kind of load) is involved.
-
I second Lionel Debroux's opinions on this idea.
Seriously, your time, CPU cycles, and electricity are better spent on something worthwhile than on trial-factoring a 1024-bit number.
What is the "only practical method"? I thought the GNFS was currently the fastest algorithm for factoring large integers with no special form.
-
I agree too. We should be realistic. That team that factored the 768 bit number took two years to do it. If they factored a 1024 bit number with the same resources, it would take about as long as factoring 2^256 of those 768 bit numbers.
-
It would not take 2^256 times longer, but it would still take too long.
-
My cores are usually working on stuff more useful than TF'ing 1024-bit numbers ;)
That I know fully well that TF'ing 1024-bit numbers is impractical (I was the second person to write it in the topic, an hour after bwang :) ) does not mean that I cannot help speeding up the program (as a ways to learn a bit about the GMP API, which I had never used before) and make my computers spend a reasonable amount of time trying. I might end up unfathomably lucky, after all - and if not, no biggie, I knew it was impractical :)
What is the "only practical method"? I thought the GNFS was currently the fastest algorithm for factoring large integers with no special form.
Yes, it is GNFS. But we don't have access to the special implementation of GNFS + post-processing steps that enabled factoring RSA-768, made by the top researchers in the field :)
And anyway, even if we had it, I don't think it would be that useful to us, as some pieces of it would probably need some improvements so that they can scale up three orders of magnitude in difficulty, for factoring RSA-1024. Only the top researchers of the field can make the (probably) needed improvements.
-
out of morbit curiosity, do we know what the probability that we actually manage to factor this is?
-
See reply #70, http://ourl.ca/6236/101082 :)
-
Stopping work on 0xaba7... after ~3.1e12 trial divisions, switching to 0xc3b3...
-
hey, on a side note, think of how famous the ti-community would be if we factored ANY 2048 bit key, not specifically the nspire's. so, ponder this: if you multiply two 2048 bit keys together, and try to factor that, you now have to locate one of 4 possible prime numbers in a field that is no larger than if you were factoring a single key alone. you've just doubled your chances, which halves the amount of time it takes to do it! with 4 keys together, you could factor one of them in 1/4 the time!!!! actually, its a little longer than that because you're working with a bigger number, but still!!!! ok, so we won't be able to factor the specific key we want, necessarily, but we'll still be famous for being the first people to factor a 2048 bit RSA key!!!
-
We should maybe at least manage to do 1024 first, though :P
-
oops, sorry! I meant to say 1024 bit. I was just testing you all....slash, I was 50 years ahead in computer technology. good job DJ!
-
2^1024 * 2^1024 = 2^2048.
Isn't that a lot bigger than one key by itself?
I think you were thinking add, or multiply by two.
-
hey, on a side note, think of how famous the ti-community would be if we factored ANY 2048 bit key, not specifically the nspire's. so, ponder this: if you multiply two 2048 bit keys together, and try to factor that, you now have to locate one of 4 possible prime numbers in a field that is no larger than if you were factoring a single key alone. you've just doubled your chances, which halves the amount of time it takes to do it! with 4 keys together, you could factor one of them in 1/4 the time!!!! actually, its a little longer than that because you're working with a bigger number, but still!!!! ok, so we won't be able to factor the specific key we want, necessarily, but we'll still be famous for being the first people to factor a 2048 bit RSA key!!!
I think the community would become famous if we did just crack the 1024 bit key. Has this ever been done before? The community even got some publicity with the 512 bit keys!
-
As far as I know, it hasn't been done, considering the best one I heard about was 2 years for 768 bits.
-
I think you were thinking add, or multiply by two.
no, i actually meant multiply the 'n' values for two different keys together. the resulting number has 4 primes, each having about half as many digits as ONE of the n's. the probability of selecting a correct factor is doubled.
-
Actually, that is incorrect. They are still 512 bits in length, so it makes no difference.
-
One team actually did crack a 1024-bit key, but it wasn't through a factoring method. It was by starving the cpu of electricity, giving out tiny parts of the factor along with a bunch of other stuff. It took 11 months, and isn't applicable to the nspire, because of how it's factored.
Check out the article here
http://www.engadget.com/2010/03/09/1024-bit-rsa-encryption-cracked-by-carefully-starving-cpu-of-ele/ (http://www.engadget.com/2010/03/09/1024-bit-rsa-encryption-cracked-by-carefully-starving-cpu-of-ele/)
-
That's interesting. Maybe we could emulate a power fluctuation in Goplat's emulator.
-
We wouldn't need to. Since it's an emulator, we have full control over what's happening inside.
The problem, however, is that the private key is used for signing, but the Nspire only contains the public key. (The private key is held by TI.)
-
Hence why I said it doesn't apply to the nspire. Too bad though. That emulator idea sounded cool!
I still like the idea of replacing the public key, by using an arm asm program. It might be possible, I'm not sure. Plus, you invalidate the Standard OS in the process. Who cares about that one, anyways, as long as we get a z80 emu? :P It's only good for math anyways. I'd love to see an 89-style GUI on it, personally.
-
I wonder if Ndless 2.0 ever never comes out if it will eventually be possible to just make a third-party OS and add TI-Nspire linking support for every possible OSes and be able to send it to the Nspire?
-
We should just port Linux.
-
;D True!
If people do so, they should try to port an user-friendly version, though, for people who hate having to use command console to do every single thing
-
Hackspire says that the files containing the public keys are themselves signed with a 1024-bit RSA key. TI is not _that_ stupid ;)
-
Lol, encrypting encryptions? I guess TI really didn't want these keys factored :P So do we even have the *public* keys?
-
Yeah, we have the public keys, otherwise we wouldn't have a reference point for the factoring programs. IIRC they were acquired due to some error on TI's part, but I may be wrong.
-
The public keys are simply embedded in OS upgrades files, either in clear binary (TI-Nspire.cer), in compressed form (boot2.img) or in encrypted form (TI-Nspire.img) :)
See http://hackspire.unsads.com/wiki/index.php/OS_upgrade_files , linked multiple times in this topic.
In TI-68k calculators, the keys are in clear binary. They probably are on TI-Z80 calculators, too.
-
Did you just need to rename the .tno/.tnc file to .zip and grab the stuff inside?
-
Yes and no, it depends on your ZIP reader program :)
Mine (ark on Linux) handled the .tno/.tnc as a ZIP file properly, but it printed a note that there was some leading garbage.
-
Aaah ok. I remember WinRAR opened my .tno files fine, same for .exe.
-
I had an idea for simplifying the key decryption that doesn't involve algorithms.
Right now, it decrements by 2 every time. That makes the ending numbers look like this
9
7
5
3
1
9
7
5 will never be the last number in a factor. what if, instead of subtracting by 2, we had 4 computers (or more, obviously) subtracting by 10? The program is no more complicated than before, it should run just as fast. Therefore, we should get a 1/5 decrease in time.
Yeah, it's farfetched, but it's worth it if it works, right?
I'll check out tribal's C program. It should be a bit more readable than the perl script for me, and it works faster anyways.
Edit: Tribals already only checks primes. Never mind....my optimization only works for the perl script :P
-
Also, if you are looking for only p, where p is the lower prime, and q is the higher, you could try 0 through 9 for p, and see which ending digits are the same. Take 221 for example. It's prime factor is 13 and 17. There are only three possible ending numbers, 3x7 and 9x9 and 1x1.
This is a list of the ending number, and the numbers that the primes would have to end with:
1: 1x1, 3x7, 9x9
3: 1x3
7: 1x7, 3x9
9: 1x9, 3x3, 7x7
So if my theory and math is correct, which I'm pretty sure it is, then the number ending with 3 is your best case, and 1 and 9 are your worst case. (Using your theory of adding 10)
-
I wonder how long it would take the program to finish this, factoring the entire possible range, doing just 3.
I found this site, and prime numbers ending with 3 are as common as 1 or 9. That means it's as likely to be 3 as any other number.
http://korn19.ch/coding/primes/ending.php
-
I still think this would take a very long time even if it only did 3. I really don't think we will ever crack this key until (if) some other method for cracking 1024 bit keys is released. Nevertheless, it is always worth trying. If we succeed, the TI community will probably be famous and we will strike back in the war TI has started with OS 2.1.
-
Don't forget, we don't really need to check all the possible numbers from 2 to the public key. The only truly likely ones will be in a certain bit range, and that is a much smaller amount than totally brute-forcing the entire number.
2.1? TI started the war by not adding an asm( command in future OS releases, or integrating ndless. 2.1 is just going a little farther.
-
Yeah, you are right about that. I haven't been following this topic too closely, and don't have much knowledge about signing keys methods of factoring them. It would be really nice if we could crack this key. We need to come back in the battle we are now losing!
-
You misunderstood my post. I'm talking about the ending number for p and q multiplied together. Let me brake it down further. We know N is a semiprime, which means a multiple of two primes. N cannot end with 2,4,5,6,8,0. Otherwise, factorization would be trivial. N must end in 1,3,7,9. The way that multiplication works, the least significant digit (The right most) of the two primes multiplied together has the same last digit as N. Like in 221. 13x17=221. The last digit could be 1x1, 3x7, or 9x9. We don't know if we don't have the factorization. But we do know that the two primes must end in either both a 1, a 3 and a 7, or both end in 9. Otherwise, it would be impossible to multiply them together to get 221, because the last digit would be different. The only two prime numbers that can multiply to end in a 3 are 1 and 3. That means, if the number ends in 3, like N=143, then the factors must end in 1 and 3, which they do, because 143=11x13. It just makes it so you don't necessarily need 4 computers.
Besides, you could make it even faster than that. If you have 10 computers, you could start them at offsets of 10, and count by 100. If you had 6 computers, you could offset by 10 and have them count by 60. Basically, in a distributed computing project, the server would tell each computer a number to stop at, so that each computer would again be an offset of 10 from each other, then increase the count by 10, and send it to each computer. This way, all the computers would not have to wait for the others to finish if it was like 10,000 ahead of the rest of them. Let me explain further. Let's say I have computers A, B, and C.
A is at 10, B is at 20, and C is at 30. They are each counting by 30. Then, computer D decides to join in. So, the server gets a request, and asks all the clients where they are at. The server then chooses the highest one, plus some huge number to stop at. Let's say C is the fastest, and is at 90. D now is set to 100. A and B go with the previous increment until A gets to 70 and B gets to 80. Then, they use the new increment given by the server to continue.
This has been one long post. Does this make sense?
-
Edit: Tribals already only checks primes. Never mind....my optimization only works for the perl script
And checking primes makes Tribal's program slow: as I wrote above, kicking this check out divides the speed of the program by ~80 on my computer !
I added some trial divisions by the smallest prime factors, it speeds up the program a bit.
But even after my optimization, TF remains massively impractical. A server wouldn't make it more practical, it would only be more work for us.
-
Yeah, graphmastur, I see what you mean now. Subtracting by 10 with several computers actually isn't a bad idea, although according to this pdf, incrementing by 6 would be more efficient. More primes, less non-primes.
http://www.dozenalsociety.org.uk/pdfs/primeforms.pdf
With enough optimizations and enough pcs, perhaps this would be possible. you never know!
Server-wise, not much has to be done.....send numbers to computers, receive negatives for a set length, and send again. If a positive response is found, it immediately sends the factors to every computer doing the program, spreading the key before ti has a chance to squelch it.
Do you think TI could change the keys with an OS update? Scary thought.
-
I doubt it. They could maybe change the hardware, though.
-
At the moment, I believe boot1 gets verified by boot0, boot2 by boot1, and the OS by boot2. Each of the bootloaders has the verification code for the one above it, but that same code is signed by the one below it. So, yes, TI can change the key if they want. Also, I'm pretty sure boot0 is non-modifiable.
-
They cannot change to boot2 key. That is the one we should factor.
-
There's a boot0? Or is boot0 the diag menu?
-
There's a boot0? Or is boot0 the diag menu?
no boot0 to my knowledge
-
With enough optimizations and enough pcs, perhaps this would be possible. you never know!
Not by TF, no, by an extremely large margin. We'd need ~1e55 times the estimated number of electrons in the universe.
-
My computers are reaching 1e13 trial divisions on the boot2 key, so I'll stop them. On an individual basis, it's not reasonable to spend much more effort on TF. With a number of PCs (running independently is enough), we can maybe reach 1e14 or 1e15, and stop wasting electrons with extremely low chance of success :D
-
There's a boot0? Or is boot0 the diag menu?
no boot0 to my knowledge
Ok thanks.
-
@lionel
Well, I was counting algorithms as an optimization...:P
Hehehe, I just submitted a support request politely asking for the RSA keys for the nspire. It would be so funny if, on the off chance we got someone who didn't know what they were, they searched, found them and gave them to us.
I put it in code so they can't google it.
-
What code did you put in? I hope you did not send them some precious info on how the community did some stuff...
I think we need to be careful with what kind of e-mails we send them. If they get too many e-mails involving Nspire cracking, it might backfire on us as they might try harder at protecting the calc.
-
What code did you put in? I hope you did not send them some precious info on how the community did some stuff...
I think we need to be careful with what kind of e-mails we send them. If they get too many e-mails involving Nspire cracking, it might backfire on us as they might try harder at protecting the calc.
I think he's referring to why he posted the message in code tags.
-
Yes, I think so too :)
Someone else posted a letter to TI-Cares in a code block.
-
I didn't tell them how we use ndless or anything. I don't even have that kind of stuff. I just sent a request for the keys (without calling them that) and put it in code so they couldn't google it.
If they do give me the key, you can bet I'll post it everywhere I can :P. And scrawl it on 50 pieces of paper at my house too.
-
What does the code block do?
-
nothing, my comment on the board was in a code block. Sorry for the misconception.
Edit: added bolded words
-
Yes, I think so too :)
Someone else posted a letter to TI-Cares in a code block.
i did. I bet you anything that they google the message. although there is probably a member here thats part of ti, so it wouldn't matter.
-
I knew you were talking about the code blocks in this forum, but how does it stop google search?
-
try googleing whats in it. Google doesn't check codes, only text.
note: these are only observations. There may be parts that don't hold true.
-
Thats interesting, so the text itself is in the html, but its ignored by google because google doesn't think it is text?
-
right. Hopefully, they don't see this and start checking all the pages constantly.
-
yep :P... but i wonder what google has hidden up it's sleeve. Maybe they have special google for large companies for a high price...
-
Is the same true for other search engines?
But really, if TI does follow calculator forums, a thread with a title like this one is definitely one that they would follow.
-
Maybe we should name titles things like gay porn so ti won't look, but really they contain threads like these :P
-
If my parents saw that on my firefox window, they'd freak :P
-
my parents would say, well james that is your decision and we will support you... bla bla bla
-
It would sure attract spambots a lot, though. Some spambots only post if the content they want to advertise matches keywords used on the site they crawl. Hence why I always delete bot posts even if they are clean. :P (not to mention some spambots leads to chain reactions, where a bot tracks the name of another bot, tracked by another, by another, and so on :P)
-
Actually, I have stopped TF'ing the Nspire's boot2 key on my four computers just today, slightly beyond 3.2e13 divisions, representing about half a CPU-year of Core 2 Duo T7200 with tuned GMP 4.3.x binaries.
A small server will keep running the program until some day (possibly the next reboot), it has performed ~2.3e12 divisions so far.
-
Is that a lot? I haven't checked this topic in a while so I am wondering if it is a lot compared to what remains to be factored?
-
I think we need to do like something*10^55 divisions.
-
meaning approximately 1e42 more time to proceed with that setup? x.x
-
3e13 divisions is a significant number in absolute value, but a ridiculously tiny part of the whole search space of ~1e154-1e155 divisions :D
Finding the factors using that method (as explained above, it's the only one we can use for up to several CPU-years, though it's ridiculously impractical, because we don't have access to the special GNFS + filtering + LA + square root implementation) would have been ludicrously lucky.
-
A gpu-based program would run faster- doesn't the GTX 480 chip have 512 processors? All of which could divide a number in a single clock cycle.
-
I'm not quite sure that arbitrary precision (here, 1024 / 512 bits) arithmetic has been implemented on a GPU, even if I know that trial factoring Mersenne numbers to ~80 bits at least can be done on GPUs.
But let's assume arbitrary precision arithmetic has been implemented on a GPU, and for the sake of the argument, let's also assume that the GPU trial factoring program is a billion times faster than the CPU program (which is wildly optimistic !). It still wouldn't improve much the chances to find the factor by much: 1e154 - 1e22 ~ 1e154 >> the number of atoms in the universe >> 1e22 >> 1e13.
Remainder: trial factoring is completely impractical for our purposes, if nothing else because it requires many more operations than the number of atoms in the universe.
-
Yeah, the biggest issue is the fact that the number is so large that the cpu has to divide it using several different cycles, each representing a portion of the number, using complicated math. The GPU idea only has merit for numbers around 10-bits or so.
Oh btw, if we ever do crack it, check this out: http://www.freertos.org/
-
I'm not quite sure that arbitrary precision (here, 1024 / 512 bits) arithmetic has been implemented on a GPU, even if I know that trial factoring Mersenne numbers to ~80 bits at least can be done on GPUs.
But let's assume arbitrary precision arithmetic has been implemented on a GPU, and for the sake of the argument, let's also assume that the GPU trial factoring program is a billion times faster than the CPU program (which is wildly optimistic !). It still wouldn't improve much the chances to find the factor by much: 1e154 - 1e22 ~ 1e154 >> the number of atoms in the universe >> 1e22 >> 1e13.
Remainder: trial factoring is completely impractical for our purposes, if nothing else because it requires many more operations than the number of atoms in the universe.
he he just wait until I have finished my fpga project then cracking this is easy :P (not)
-
This is why you run Wacky Fun Numbar Generator Operating System and ditch Windows, Linux and Mac. :P
j/k seriously, good luck guys on this project. I hope you find a way to factor the keys in a decent amount of time eventually.
-
I have a theory I'm working on, won't mention it here though :P
Too many prying eyes from TI and such.
-
If only we had a quantum computer...
-
hmm, once some other 1024 RSA key is cracked, we can use the same method to crack these
-
Except we don't have a supercomputer at our disposal.
-
good point...
How much does one cost?
-
http://www.cray.com/Products/Products.aspx
edit: https://cx1.cray.com/ConfigureBOM.aspx?opt=234&state=48
-
http://www.cray.com/Products/Products.aspx
edit: https://cx1.cray.com/ConfigureBOM.aspx?opt=234&state=48
We'll need to do a bake sale or something...
-
http://www.cray.com/Products/Products.aspx
edit: https://cx1.cray.com/ConfigureBOM.aspx?opt=234&state=48
We'll need to do a bake sale or something...
lol! or start putting a price on brandonw's creations :p
-
If only we had a quantum computer...
Yea men that would help. As far as my understanding goes to Quantum computers a working model should theoretically solve this problem instantly.
What really boggles me is that we are skimming trough more possibilities then atoms in the know universe, zomg, that gives a vague idea of the amount of computer power it requires...even if examining each atom would take just a planck second it would still take long to calculate. I myself have a theory on a better approach that simply increases the possibility of finding it, its still brute force though.
My idea is like this:
we start brute forcing in the middle of all the possibilities. In the exact middle that is. So if a key is 32 bits we factor a key that has the decimal value 16.
Then we divide by two and factor decimal 8, at the same time we multiply by two and examine decimal 32, next is decimal 64 but since that is out of bounds
we start dividing only now we divide by three (if dividing caused crossing the upper bound we will round down if dividing caused crossing the lower
bound we round up and then multiply), if by dividing we cross the lower bound we simply multiply by 3, 4 then 5 etc.
so:
try(0F)
then
try(08)
try(FF)
then
try(04)
try(0A)
then
try(02)
try(03)
then
try(06)
try(01)
Edit; I have very poorly documented it/ written it but just for the 'image' this is how it should work;
you start out in the middle then you examine the middle of the middle then the middle of the middle of the middle etc. You wont cover all numbers with this but I developed a method in my head already to do so....its VERY hard to explain and I don't think its correct but i'll try to work it out anyways...
Edit2: Maybe the virus idea isn't so bad after all, I mean seriously if we really want this this is the most viable option. I don't like to virus-bug people though...if anyone plans to do this I reccomend that person to take personal responsibility and leave all the communities outside of this, basically keep the calc-community from getting sewed...
-
Well, actually I've been working on a new CPU design for a few years, got second place in a state science fair with it. Analog logic computers. Theoretically, it could easily go past 1024-bit, and at any number base (I made quaternary logic gates with it, and a quaternary ALU adder)
So, computers counting up to 1024 Binary bits (in other number bases) are currently in a very makeable position for me. That would be an interesting attempt!
unfortunately, the higher the number base, the more soldering I need to do. It works in theory, but it gets harder as you go higher. Plus, I don't think anyone wants 3072 Volts running through their CPU, so Octal or Hex (24 or 48 V) which are still pretty high. The advantage of 12V (Quaternary or Base Four) is that it's already the standard for analog circuits.
You may be wondering why I chose to have 3 volts for each number. It's because there's no such thing as a 1V zener diode, among other analog components.
For those who don't know (probably not anyone who's ever messed with asm), number bases are how high you count before you set the number to ten:
Binary (base 2)
001
010
011
100
etc.
Trinary
001
002
010
011
012
020
etc.
Quaternary (my personal favorite)
001
002
003
010
etc.
Base 16 (hexadecimal)
01
02
03
04
05
06
07
08
09
0A
0B
0C
0D
0E
0F
10
Yay for complicated long explanations!
Edit: Oh, and btw I only have And, Or, Not gates, An adder, Memory and the logic itself.
-
http://www.cray.com/Products/Products.aspx
edit: https://cx1.cray.com/ConfigureBOM.aspx?opt=234&state=48
We'll need to do a bake sale or something...
This would be quite ironic if the OTCalc project happened to be successful and all profits went on computers to factor the TI-Nspire keys ;D
-
http://www.cray.com/Products/Products.aspx
edit: https://cx1.cray.com/ConfigureBOM.aspx?opt=234&state=48
We'll need to do a bake sale or something...
This would be quite ironic if the OTCalc project happened to be successful and all profits went on computers to factor the TI-Nspire keys ;D
Hey, that would be awesome. Well, most of the profits. We must reinvest. ;-)
-
If OTCalc is succesful, we need to put some of it at least towards making even better, cheaper ones. cray supercomputers wouldn't be that much more powerful than making a big old beowulf cluster.
Here's a cool idea: Borrow a school for a day, boot beowulf off a flash drive or network on every computer, as a node. Giant supercomputer cluster without installing.
-
lol gl with that. I do hope this eventually is worked out though
-
If OTCalc is succesful, we need to put some of it at least towards making even better, cheaper ones. cray supercomputers wouldn't be that much more powerful than making a big old beowulf cluster.
Here's a cool idea: Borrow a school for a day, boot beowulf off a flash drive or network on every computer, as a node. Giant supercomputer cluster without installing.
Tried that before. I got rejected. Oh well. Although, we could use boinc. Lionel has access to a server, I believe. Either way, that still wouldn't work. We need a better algorithm.
-
Maybe during the summer....if the IT is friendly at my school. My comp. Tech teacher does half of it, but he has a rather dim view of linux. Perhaps the other guy though....:P
Edit: Man I just realized something awesome! My school is connected to the entire network of my district. In other words, instead of getting the entire power of the High school, I'd be getting the entire power of 2 High Schools, 2 Middle Schools, 2 Intermediate (6th and 7th here) schools and 18 Elementary Schools! That is a lot of computers!
I hope they'd let us do it. Maybe if I pointed out how prestigious this really is, cracking an rsa 1024-bit without cheating, they would consider it.
-
http://www.cray.com/Products/Products.aspx
edit: https://cx1.cray.com/ConfigureBOM.aspx?opt=234&state=48
We'll need to do a bake sale or something...
This would be quite ironic if the OTCalc project happened to be successful and all profits went on computers to factor the TI-Nspire keys ;D
Hey, that would be awesome. Well, most of the profits. We must reinvest. ;-)
I wouldn't trust TI, though. What if we factor the key and they decide to release a new Nspire hardware that won't run any old OS and use a different key? x.x
-
http://www.cray.com/Products/Products.aspx
edit: https://cx1.cray.com/ConfigureBOM.aspx?opt=234&state=48
We'll need to do a bake sale or something...
This would be quite ironic if the OTCalc project happened to be successful and all profits went on computers to factor the TI-Nspire keys ;D
Hey, that would be awesome. Well, most of the profits. We must reinvest. ;-)
I wouldn't trust TI, though. What if we factor the key and they decide to release a new Nspire hardware that won't run any old OS and use a different key? x.x
Won't happen if we break the Boot2 key. It's not possible to change it.
-
If we need money for computing power, we could spread the word that we are trying to crack this key. Cracking something this strong is a rare occurrence, and has significance outside of the calculator world. Some people may be willing to help fund the effort, perhaps even RSA themselves. Let's put together a good argument and publicize it!
-
YAY! Omnimaga as a team to crack the keys!
-
would it be possible to give half of my computing power to breaking the key while still using the other half,
and have many many many many many many many many many many many many many many many many many many many many many many many many many many many many many many many many many many many many many many many many many many many many many many many many many many many many many many
people add onto it?
-
I love your enthusiasm, but this is not going to happen any time soon. We're still working on algorithms, though.
-
http://www.cray.com/Products/Products.aspx
edit: https://cx1.cray.com/ConfigureBOM.aspx?opt=234&state=48
We'll need to do a bake sale or something...
This would be quite ironic if the OTCalc project happened to be successful and all profits went on computers to factor the TI-Nspire keys ;D
Hey, that would be awesome. Well, most of the profits. We must reinvest. ;-)
I wouldn't trust TI, though. What if we factor the key and they decide to release a new Nspire hardware that won't run any old OS and use a different key? x.x
Won't happen if we break the Boot2 key. It's not possible to change it.
Yeah but I mean a totally new Nspire, like the TI-Nspire II or something, that would be very different from the ones we have now, different memory layout, etc. Wouldn't that have a different boot 2 or does all calc models use the same?
-
http://www.cray.com/Products/Products.aspx
edit: https://cx1.cray.com/ConfigureBOM.aspx?opt=234&state=48
We'll need to do a bake sale or something...
This would be quite ironic if the OTCalc project happened to be successful and all profits went on computers to factor the TI-Nspire keys ;D
Hey, that would be awesome. Well, most of the profits. We must reinvest. ;-)
I wouldn't trust TI, though. What if we factor the key and they decide to release a new Nspire hardware that won't run any old OS and use a different key? x.x
Won't happen if we break the Boot2 key. It's not possible to change it.
Yeah but I mean a totally new Nspire, like the TI-Nspire II or something, that would be very different from the ones we have now, different memory layout, etc. Wouldn't that have a different boot 2 or does all calc models use the same?
It would be counterproductive to Ti, so they probably won't do that.
-
So then we have all the nspire line cracked, and can feel 1337, then move on to crack the others later. If they're that different they won't bother calling them nspires. It would be the TI-nspire plus or something similar :P or the Ti-Nspire Explorer edition. Something incompatible
-
I have slightly revisited my idea, and I think it has some potential. Why? because this; shows it. no this is NOT about cracking this is about 3D rendering. It's not the purpose I fancy but the way it is achieved. He uses a search algorithm to skim trough all that data to find out what needs to be drawn on the screen. Searching algortihms have greatly improved over the last years and basically my idea was a very, very rudimentary search algorithm. I am suggesting not to count up every possibility from decimal 1 to 8,9884656734115795386465259539451e+307. Instead of doing that I suggest we start to search from the middle, then from the middle from the middle (both on the left, and the right side), then the middle of the middle of the middle (making 4 middles in total by now) then the middle of the middle of the middle if the middle (8 middles and counting) etc. It would be best if each of these is calculated to be correct or incorrect in parallel, that's where FPGA's kick in. :D
Anyways the sheer size of this problem I think prooves, N!=P
-
matthias1992, that would be exactly as efficient as a routine that counts from 1 to 89884656734115795386465259539451e+307.
-
But it is more likely that the factor will be around 512 bits, so the algorithm should start around there.
-
matthias1992, that would be exactly as efficient as a routine that counts from 1 to 89884656734115795386465259539451e+307.
correct and incorrect at the same time, yes it will do the same things but one will more likely come accros a correct value, altough I must admit that, that last statement is just intuition. yes I do use intuition, I suck at math, really.
-
it's not really as efficient. If you used it to find better bounds on where to find the prime, then maybe, but there is no function to find if the prime was in a range. If there was, this would be so easy.
-
I was thinking, if I could convince my School district to run a server, could someone whip up some software to run on this massive computer? I think I can convince them via the "big deal, famousness" angle. the server even has the facilities to reset every computer in the district from one location!
-
so.. your plan.. is to borrow.. a whole entire school district? O.O that's a lotta computers.
-
Do you really think a school will allow that, though, especially if it takes an intense amount of ressources, hindering people who use the computers for projects?
-
well odd are he could have it pause during the school day or something or not work as fast and limit it self so that during the periods of access it wont be as noticable maybe ?
-
I still wouldn't think that a whole school district would let you borrow every single computer. I guess you could try though. They would probably say no, because they would think it would just clutter up their system and get in their way
-
Another issue is that some schools turn all computers off at the end of classes.
-
I was thinking summertime.
Plus, DJ, these computers can be turned on and off from any of the admin computers. Not kidding. my Comp. Teacher showed me one time. They all turn on and off automatically at the end of the day.
-
yes i know that they turn on and off and kind of damage the computers like 'the plug being pulled' this happened at my whole school. it would be a large project to convince to the principal....
-
People, would you mind re-reading early pages of the topic, where it is explained multiple times why we can't even think about using the only algorithm that wouldn't be completely impractical, because we have neither the hardware nor the software required for that enormous task ?
Remember, in the current state of things (i.e. without major breakthroughs), the top researchers of the field don't expect the factorization of a 1024-bit RSA modulus by the next five years (it's closer to four nowadays, since the RSA-768 paper where they make that claim was released at the end of 2009). And we can never, for the life of the Universe, reasonably hope doing that by Trial Factoring. The cspire program (or any FPGA / GPU / whatever version of it, which might be several orders of magnitude faster but would still in no way make the task practical) might, with extreme luck, make a hit (again, see above for multiple posts containing figures) - but again, we shouldn't be spending too much processing time on that.
-
Well the thing is that it's a complicated thing it seems and there's quite a lot of vocabulary and stuff to remember on the subject, so it's inevitable some people will suggest the same things again. It's best to remind people, though, that it was already tried. Let's just remain polite towards them, though.
-
I think what Lionel is saying is that no matter what amount of computer power we could get, it's not going to happen, not for at least 4 or 5 years, and even at that point, it will still likely take upwards 6 months to factor.
By then, we'll be on the TI-Nspire CAS Silver-Titanium Explorer Edition.
Personally, I think that instead of the community focusing on factoring the RSAs, we put more of an effort towards programming on the existing exploits, and towards finding new exploits, we'll more than likely get more out of it as a community.
-
WHile still being careful to who we reveal the exploits, too.
-
Yea, although in a lot of cases it's really hard to hide the exploit while publishing it. nleashed, for example, is pretty obvious, if you know what to look for. I was able to run my own code earlier through the same exploit that nleashed uses, just by looking at nleashed. Too bad the exploit destroys everything in RAM, so you can't call any OS functions or anything(or do anything like ndless, without basically rebuilding the OS in-ram)
-
I think what Lionel is saying is that no matter what amount of computer power we could get, it's not going to happen, not for at least 4 or 5 years, and even at that point, it will still likely take upwards 6 months to factor.
By then, we'll be on the TI-Nspire CAS Silver-Titanium Explorer Edition.
And? Even if it happens (I'm not sure about that), in 4-5 years, many students will still have TI-Nspire ClickPads, TI-Nspire Touchpads and TI-83+/84+, unless a major change in exam organisation occurs.
It's not everybody who buy the latest brand new calculator...
-
People, would you mind re-reading early pages of the topic, where it is explained multiple times why we can't even think about using the only algorithm that wouldn't be completely impractical, because we have neither the hardware nor the software required for that enormous task ?
Remember, in the current state of things (i.e. without major breakthroughs), the top researchers of the field don't expect the factorization of a 1024-bit RSA modulus by the next five years (it's closer to four nowadays, since the RSA-768 paper where they make that claim was released at the end of 2009). And we can never, for the life of the Universe, reasonably hope doing that by Trial Factoring. The cspire program (or any FPGA / GPU / whatever version of it, which might be several orders of magnitude faster but would still in no way make the task practical) might, with extreme luck, make a hit (again, see above for multiple posts containing figures) - but again, we shouldn't be spending too much processing time on that.
++ I think we should first focus on getting asm on the nspire, THEN we can worry about RSA keys
-
++ I think we should first focus on getting asm on the nspire, THEN we can worry about RSA keys
We can't really help ExtendeD & co. with that, though, and anyway once we have the keys, we'd have all the ASM freedom we'd ever need.
-
I think what Lionel is saying is that no matter what amount of computer power we could get, it's not going to happen, not for at least 4 or 5 years, and even at that point, it will still likely take upwards 6 months to factor.
By then, we'll be on the TI-Nspire CAS Silver-Titanium Explorer Edition.
And? Even if it happens (I'm not sure about that), in 4-5 years, many students will still have TI-Nspire ClickPads, TI-Nspire Touchpads and TI-83+/84+, unless a major change in exam organisation occurs.
It's not everybody who buy the latest brand new calculator...
I agree. The 83+ keys were factored about a decade after the calc was released. I have still seen people using TI-82s. By the time it is feasible to factor the keys, we'll still be using nspires.
-
Hmm, I wonder, did the TI-82/85/86 have OS upgrades?
-
No. These calcs didn't have any flash memory.
-
I think what Lionel is saying is that no matter what amount of computer power we could get, it's not going to happen, not for at least 4 or 5 years, and even at that point, it will still likely take upwards 6 months to factor.
By then, we'll be on the TI-Nspire CAS Silver-Titanium Explorer Edition.
And? Even if it happens (I'm not sure about that), in 4-5 years, many students will still have TI-Nspire ClickPads, TI-Nspire Touchpads and TI-83+/84+, unless a major change in exam organisation occurs.
It's not everybody who buy the latest brand new calculator...
I am a bit worried about how fast clickpad Nspires vanished from stores over here and the Staples online store, though. The Touchpad is very recent, yet clickpads are already no longer available here. While some people will stick to their current calc, borrow their brother or sister calc or buy it used, the other people may be forced by TI to buy a new model if TI decides to phase the current Nspires out. And after a few years, very few people will have them. As example, on this forum, several people were not even aware that the TI-83 Plus Silver Edition even existed.
Yup. What should happen is that your home's IP address should be banned unless you are logged in.
This has been done already.
Actually, the way it is set up, you would not even be able to browse the forums while logged in either from your parents home. I may lift it after a week or so due to the banning policies here, but if he does it again the IP would be banned whenever you don't have to go use the computer at your parents home. (You would have to warn me in advance)
-
It just occurred to me that I have a computer I don't use and isn't good for much of anything besides data processing. I could devote it to trying to guess the RSA or whatever the final verdict was that this would follow :D Unfortunately, no internet for it.
-
Without Internet access on that computer, it will be harder to get the necessary resources for compilation on it.
You can, however, compile the program (my version of the program started by Tribal, which is faster because I commented the probable prime checking) on another computer with similar environment, and transfer the binaries. For minimum file transfers, try compiling the executable statically.
-
What Type of computer is it?
-
It's a random laptop, nearly 10 years old. I ussually run Puppy Linux on it, and it's speedy fast :D I think I asked my dad about getting internet back on it, but he didn't seem to have any answers for it so that it would work. Out of curiosity, what extra libraries does the program require?
On a side note: If this doesn't work, what could I do with my extra computer? I'd like it to just handle data, but I don't really know of any data I want it to work with. The RSA cracking thing sounded like the best idea.
-
you can always crack meh sig! :P
-
Err, what am I looking for?
-
Lol, he encrypted his sig with 1024 bit rsa. This is equivalent to breaking nspire security, I don't remember how to get the public key from the file, though. Either way, if you break his sig quickly, you can break the nspire key quickly.
-
hehe yep! I decided to do that as a joke, as you make your avatar in a code :p
-
Ah, I decrypted it! It says "The Game." The TI-Nspire should be just as easy to crack ;)
-
no.. it says something else now! :D
-
Aw, dang it. A bad sign :(
EDIT: Anyway, we should get back on topic.
-
Yeah, I notice a lot of the Nspire topics turns into randomness lately. We should maybe keep it for the actual randomness section. Also some people might get confused about if we are serious or not when posting future info or progress on that.
-
What would cracking the nSpire RSA codes do? Aren't they simply used for the Certificate?
-
What would cracking the nSpire RSA codes do? Aren't they simply used for the Certificate?
They are, but the PUBLIC certificate verifies the boot2 and the OS itself.
If we cracked the PRIVATE keys, we can sign our own boot2/OS and make a jailbreak permanent. :)
-
Oh, so cracking the code would make custom OS patches viable?
So all you would really need is the private key and the encrypted data, correct (it's been a little while since I've worked with RSA)?
-
Oh, so cracking the code would make custom OS patches viable?
So all you would really need is the private key and the encrypted data, correct (it's been a little while since I've worked with RSA)?
Yup. :)
The private key will let us resign the modified OS, making any changes possible. PLUS - it would also let us create better OSes (hint: Linux calc distro!!), and install them too.
As for this virus idea, I think there was a C program posted.
It would be perfect if there was a simple tray icon to indicate that it's running, and if it ever finds the key, upload it to every single calculator website. :)
-
Oh, so cracking the code would make custom OS patches viable?
So all you would really need is the private key and the encrypted data, correct (it's been a little while since I've worked with RSA)?
Yup. :)
The private key will let us resign the modified OS, making any changes possible. PLUS - it would also let us create better OSes (hint: Linux calc distro!!), and install them too.
Linux on-calc ... so it's really possible?
-
If all you need to find is the private key (I'm assuming someone's already located the encrypted data), why go to the trouble of number sieving? What you have is a situation any code cracker would dream of where you have access to the device itself. Instead of inefficiently using random numbers, use the bits in the memory itself as the random numbers. When you get a combination that works for the private key, then there's your answer. And since I'm fairly sure the nSpire's emulator can run 84+ ASM, just use an Assembly program to look at the bit level data in the memory. In fact, this is exactly what one of my current projects does.
If you know the approximate location in the memory, then the situation gets even better as you can narrow your search.
EDIT: Yep, you could probably get something like Tiny Core Linux (http://www.tinycorelinux.com/) to run on-calc.
-
@Deep: ARM processors are fully capable of running Linux. :)
If all you need to find is the private key (I'm assuming someone's already located the encrypted data), why go to the trouble of number sieving? What you have is a situation any code cracker would dream of where you have access to the device itself. Instead of inefficiently using random numbers, use the bits in the memory itself as the random numbers. When you get a combination that works for the private key, then there's your answer. And since I'm fairly sure the nSpire's emulator can run 84+ ASM, just use an Assembly program to look at the bit level data in the memory. In fact, this is exactly what one of my current projects does.
If you know the approximate location in the memory, then the situation gets even better as you can narrow your search.
EDIT: Yep, you could probably get something like Tiny Core Linux (http://www.tinycorelinux.com/) to run on-calc.
FYI, the private key is not stored in the memory of the Nspire AT ALL, nor in the OS.
The public key verifies and decrypts it, that's all. Encrypting uses the private key.
Now, if you were saying that this method could find the private key from the PUBLIC key, then you might have a case.
-
I think I need to look at RSA again :P
You're right.
-
I think I need to look at RSA again :P
You're right.
Basically, the ndless devs already decrypted the OS and boot2, which is how they can produce hacks to make ndless itself. :) But the major hurdle is that we can't write back to the OS, since it's encrypted, and writing anything breaks the signature, causing boot2 to reject it and not load it at all. When you turn off your calculator, the ndless portion is still "loaded" in a way. Now, if you pulled batteries or did a true reset, the jailbreak is gone, and you would need to rerun.
In iPod JB terms, it's a tethered jailbreak, but not as bad as an iPod Touch/iPhone tethered jailbreak, in which any reboot/power off (which happens a lot more than a calc) requires a computer to JB again. (Whereas the Nspire doesn't drain that fast, and can be JB via a TI-84+ :))
I still like the "virus" idea, but I wouldn't make it a virus. I'd make it a easy, portable program that can be distributed easily, has a tray icon and simple dialog for progress, and can submit the final factored key to the internet (and spread to every flash drive and such) if it successfully finds it. People can give this to friends, and they can give to others. If we can build a large base with people doing this, the probability of finding the key goes up. It's hard and slow, but it's the best chance we have to knock TI down with a swift knife. :)
-
First an 84 jb's a ps3, now (possibly) an NSpire. Nice. This is looking looking interesting.
-
First an 84 jb's a ps3, now (possibly) an NSpire. Nice. This is looking looking interesting.
Possibly? It's already done! :) http://www.ticalc.org/archives/files/fileinfo/426/42627.html
Anyway, I need to find that lovely C source and repost about it here. :P
-
Found the source code! :)
http://ourl.ca/62360
Post #64, 65 - READ them, then peek at source code from downloading from the attachment, or from here:
http://dl.dropbox.com/u/1016340/NspireRSACrackingPrograms/cspire.zip
http://dl.dropbox.com/u/1016340/NspireRSACrackingPrograms/cspire_lfsr.zip
Happy hacking! :) Remember, implement a simple dialog to track progress, stop, etc., then make it minimizable w/tray icon, then add support for posting on internet/infecting HDDs with the factored key file/etc., and finally add support for only running when no CPU hogging process is on.
AND - it must be cross-platform. We want to run this on every computer on the planet (or at least try to).
If you can do all of these, or at least contributed to parts, you get 1024 cookies. :P
-
And you double-posted :P
/me eats alberthrocks
I wonder how many computers will be needed to crack the keys x.x
-
how much time would it take to do every key possible?
there is one correct solution out of 'blank' possible?
maybe we can each take 10000 possibilities or what ever and split it up so we don't repeat the same number.
(sorry for bad wording)
-
If I understand correctly, there're 1.8×10308 (that's a googol cubed and then some) different combinations, so it's gonna take a while if we were to do it like that ;)
-
We'll need way, way over 900142 computers to get it in a reasonable amount of time :P
Edit: Assuming Deep Thought's number is right, of course.
-
That's >9000! :o
Anyway, is there anyway to simply wipe ALL of the data from the nspire? That way, you can at least start from scratch with a 3rd party OS, assuming that the nspire doesn't use firmware to store the certification routines.
-
It's in actual ROM, though, right?
-
I'm pretty sure you can erase ROM, although it wouldn't be available to anyone outside of an electronics lab. Never mind.
Bloody TI...
-
Well, technically you could, but that would require resetting and programming the flash chip manually. (I Think. Don't quote me on this.)
-
We'll need way, way over 900142 computers to get it in a reasonable amount of time :P
Edit: Assuming Deep Thought's number is right, of course.
Define "reasonable."
Also, this big of an RSA key has never been cracked, IIRC. It might be something someone with lots of resources may want to help with outside the calculator world.
-
We'll need way, way over 900142 computers to get it in a reasonable amount of time :P
Edit: Assuming Deep Thought's number is right, of course.
Define "reasonable."
Also, this big of an RSA key has never been cracked, IIRC. It might be something someone with lots of resources may want to help with outside the calculator world.
The people with "lots of resources" would be the ones who cracked the current record 768 bits. Reasonable, meaning that in 20 years after a different calc comes out, we might find a factor.
-
We'll need way, way over 900142 computers to get it in a reasonable amount of time :P
Edit: Assuming Deep Thought's number is right, of course.
Define "reasonable."
Also, this big of an RSA key has never been cracked, IIRC. It might be something someone with lots of resources may want to help with outside the calculator world.
The people with "lots of resources" would be the ones who cracked the current record 768 bits. Reasonable, meaning that in 20 years after a different calc comes out, we might find a factor.
A calc with a 16384-bit RSA. That would be fun :P
So, what's our best chance? Find a new algorithm?
-
We'll need way, way over 900142 computers to get it in a reasonable amount of time :P
Edit: Assuming Deep Thought's number is right, of course.
Define "reasonable."
Also, this big of an RSA key has never been cracked, IIRC. It might be something someone with lots of resources may want to help with outside the calculator world.
The people with "lots of resources" would be the ones who cracked the current record 768 bits. Reasonable, meaning that in 20 years after a different calc comes out, we might find a factor.
A calc with a 16384-bit RSA. That would be fun :P
So, what's our best chance? Find a new algorithm?
Yep. Which is why this topic is here.
-
Slightly off topic, but what if everyone hooked their Nspires up to their computers at night and the Nspires were used to hack the Nspire through distributed computing? :-P Although distributed factoring does seem to be the way to go.
-
This topic is two and a half years old and, as was explained earlier in the thread, completely infeasible. Please don't post in such old threads unless you have something significant to contribute. Locked.