Fun Number Theory Facts

[brandonw]

Simply amazing.

Considering the 84+/SE boot code bug with key 0004 (it worked for me on my 84+SE because it has Free83P, with the 0004 key embedded in the certificate), the next most important key would be 000A, to make this discovery as significant as it should be.

And then 0102.
And then 0002.
And then 010A.

[Michael]

I wish my desktop wasn't seven years old or else I'd start on one of them...

Benjamin, are you still going to do 0102 next or 000A?

[FloppusMaximus]

010A... I don't see that one being terribly useful. Now, 0101 and 0103, on the other hand...

Edit: I agree, 0A sounds enticing. At the same time, thanks to Brandon, it's not so urgently needed anymore. And to be honest, as much fun as it is to write an OS, I feel like the ability to sign apps is more potentially useful to the community.

[IAmACalculator]

Two quick questions:

1. How many keys are there?
   
2. Would a distributed computing setup be out of the question? Because even 10 computers of equal speed to Flop's could theoretically break a key in a week (assuming it takes a 10^th of the time). It'd probably be more like a month, as there'd be some downtime from regular use, but it'd still be a significant time difference.
   

I think this is the most active UTI's been in months, maybe years...

EDIT'd for parenthetical discombobulation.

EDIT²:Not to mention that the people viewing this topic haven't been sighted since...I don't know when. Amazing.

[Graphmastur]

There is like 10 users viewing this topic. Anyway, what is the process for signing an os?

[FloppusMaximus]

There are 12 more keys, I think, that are potentially of interest to third-party developers: 01, 02, 03, 08, 09, 0A, 0101, 0102, 0103, 0108, 0109, 010A. (The "0x" keys are for OS signing, the "010x" keys for app signing. 1 = TI-92+, 2 = TI-73, 3 = TI-89, 4 = TI-83+, 8 = V200, 9 = Titanium, A = TI-84+.)

Edit: I'm not actually sure that there are 0108 and 0109 keys; can anyone confirm or deny this? Anyway, the 0108, 0109 and 010A keys are obviously less useful than the 0101, 0103 and 0104 keys.

The first two phases of factoring -- polynomial selection and sieving -- can be done in a distributed manner; it does require moving a few gigabytes of data from one place to another. The final processing needs to be done on a single PC or a tightly networked cluster.

You can sign OSes using RabbitSign; the exact process will depend on what assembler you're using, but basically you just need to generate a multi-page Intel Hex file. If you're using TASM, a process similar to what I used for PongOS will do the trick. ZMASM and tpasm can both generate multi-page hex directly. Brandon also has an OS signing tool; I don't know the details of how it works.

[brandonw]

I'm afraid I have to take issue with going with 0102 first. Now that it's public knowledge that we can generate these keys, we need to complete a "group" of keys, which right now is the 83+ series OS signing keys, so I think 000A is more important.

I'm not sure if it's public knowledge, but I wrote something called Free73 which basically adds the 0104 key to the 73 certificate, and so you can sign applications with the 83+ key and send them, and a Flash application called Tortoise which is basically a wrapper of Mallard to run programs/games. We can write 73 Flash applications; we can't easily give 84+/SE users a third-party OS without extra programs, and I think that's critical.

Despite having released Free83P, screwing around with the certificate isn't the smartest idea in the world, which I've proven by bricking 4 84+/SEs in the process of developing it. If we have to rely on messing with the certificate to get what we want, I'd rather be doing it on the less-used 73 than the 83+ series.

[DigiTan]

So in the beginning...what kind of information did you need to put together to get this started?

[Graphmastur]

[FloppusMaximus]

Graphmastur: I've got 4 GB of RAM. You don't need to load the whole sieving database into memory -- the database contains a fair number of duplicated relations, and the filtering phase throws away "singletons" (if an ideal is only used by one relation, that relation can't contribute to the final result.) As I said above, the complete database was 51 million relations, but only about 10 million were used in the final factorization.

For writing PongOS, I basically assembled the two pages separately. In the code for page 1C, I used the TASM .export directive to generate an include file containing the useful addresses; I then #included that export file in page 0. Finally, I wrote a program called "multihex" to stitch the hex files together, and a program called "packxxu" to convert it into an 8xu file. When using RabbitSign, you could skip the packxxu step. (But you'd need to add an OS header in some other way.)

DigiTan: I'm not sure what you mean. The public keys can be found in the calculator certificate; the details of the signing algorithm weren't too hard to find. (I seem to remember that Brandon Sterner did the hard work there.) As for the factoring software, it's all out there on the Web - you just have to be crazy enough to look for it. :)

Also, if you have two OSes signed with the same key, you can calculate the public key based on their signatures. That's how I found the 89/92+ keys. Unfortunately, I've had no luck so far doing the same for the Nspire.

Brandon: I see your point. 0A it is, and one of the app keys after that.

Edit: On a tangentially related note, it might be possible to use the 04 key for the 84+ after all. You might be able to send an OS header that claimed to be signed with key 0A, then later on, strategically overwrite page 1A to change the key ID to 04. I'll have to play around with this to see if it's possible.

[Michael]

I have to repeat it again. This is so cool and exciting!

[IAmACalculator]

Looks like you've gotten yourself sucked in again.

Someone needs to move this to Community News.

[FloppusMaximus]

[Graphmastur]

I read it, but how ling do you think it will take on a dual core intel mac?

[brandonw]

Since the man who knows the most about this process is working on the 0A key, I suggest if you want to play around with this but aren't entirely confident on it, work on another key like 0102. There are plenty to go around.

[FloppusMaximus]

Graphmastur: If you want to give it a try, go for it! I suggest that you try a smaller number first to give you an idea of how the various tools work together. The rule of thumb for GNFS is that it will take about 10 times as long for every 21 digits, so a 155-digit number will take 10 times as long as a 134-digit number, which will take 10 times as long as a 113-digit number.

I don't know the exact specifications of your machine, so it would be hard for me to give a good estimate. Most of the time will be spent sieving, of course; that part is pretty much bounded by your CPU speed. If it's a Core 2, I'd expect it to behave similarly to my Athlon 64; you can do the math. (Incidentally, for 64-bit machines, I highly recommend the "experimental" GGNFS siever; it's significantly faster than the 32-bit siever and quite a lot faster than the "generic" siever that is built by default on 64-bit machines.)

[fullmetalcoder]

[IAmACalculator]

I'm no expert, but I'd guess that using the 04 key will make no difference, as the 84+ series uses the 0A key, which hasn't been broken yet. I don't know why free83p/05key doesn't work, though. You'll have to ask Brandon on that one, but he usually doesn't visit UTI very often.

[fullmetalcoder]

[Graphmastur]

If I get a chance later, I will look at his vb code, but I am working under unix, so no promises.