I believe it is when it is installed. And no "let's modify the OS" comments, please, btw.  I think Ndless should do fine for that, while this thread is for RSA. Just a precaution.

Oh, and I didn't realize it before, but I definitely got Ninja'd on my last post.

the reason we need to factor n into p*q is so that we can calculate phi(n)=(p-1)*(q-1), right? well, what if, instead of trying to find a better factoring algorithm, we try to find a fast way to compute the totient without knowing the factors.....

We could.  The difference between n and t is (P+Q-1), though.

That code will not work, calcdude.  The first routine will return a random number 0-9, the second, 0-8, the third ,0-7.  In other words, they could still all end up being 7 or something.

[EDIT] Ignore this post.

Okay, so many people want to break RSA security because of the Nspire.  Well, it's not at all easy, and the current algorithms won't even work well on a 1024 bit number.  So I was thinking, that if an entire calculator community put their heads together, then we might actually think of a workable algorithm.  Now then, first I will explain RSA.

RSA is a public/private key cryptography system.  You have a public key (n,e) and a private key (n,d).  When you "break" RSA, it means that you found the private key using the public key.  Now then, I will show you how you get n, d, and e, and why it is so difficult to break as n grows larger.

The basis of the algorithm is simple.  You find two prime numbers, p and q, that are somewhat close together (about the same bit-length).  You set n=pq.  Now, n is a semi-prime, which means it is a multiple of two primes.  You then choose an e (most common one is 65537 or 2^16+1).  You find the totient function (which in the case of primes is p-1), so you set t=(p-1)(q-1).  Now you use an algorithm (Extended Euclidean) to find d such that de-1 is divisible by t.

With the Nspire keys, we have the public key: n and the exponent (most likely 65537, but that doesn't really matter), and we need to find the private key: n and d.

Finding d using e and the totient is easy.  The question is how to find the totient from n.  Well, the most obvious method would be to factor the number n, and use the factors, p and q, to find the toitent function (p-1)(q-1).  Now then, I believe an example is in order.  (Note: The number used here is not even close to the size of the actual numbers used.)

This is done as if we were TI, making the keys for the initial use.
Say we choose two prime numbers. p=13 and q=17.  We can easily see that (13-1)(17-1)=(12)(16)=192=t.  Now, using the Extended Euclidean algorithm, we use e=65537 and t to find d.  This makes d=65.  In case you don't want to read the Extended Euclidean algorithm (Specifically modular multiplicative inverse), let me explain how it works.  de-1=(65)(65537)-1=4259905-1=4259904.  4259904/192=22187, with the remainder being 0.  This is the d for the private key.  We are done finding the keys to use.

TI can either encrypt or sign their OS.  What signing means, is that a checksum of the data of the OS is taken, and encrypted using the private key.  (That is done one the computer)  The calc then does a checksum of the os, and uses it's public key to decrypt the checksum of the OS.  If the two checksums are equal, it is a valid os sent by TI.

Now then, this is our part:
The easiest way to send an OS or open the calc completely would be to, using the public key (which we already have) factor the number n.  Using the factors, we can easily find the private key.  The number 221 that I used earlier is only a byte.  That is 8 bits.  The number we are trying to factor for the Nspire is 1024 bits.  That is a lot bigger, so there are a few things that won't work:

• Naive algorithms like trial division. (Seriously, please don't suggest it)
• Any current algorithm.  Yep, no current algorithm is good enough to factor the key.  The current record is 768 bits, made by the top researchers with algorithms we don't even have access to.

Have I made it seem like all hope is lost?  Good! Now then, the reason I am creating this thread is not to discourage, but encourage.  I believe that if we all work on an algorithm together, that it is possible to actually factor the numbers.

(I just realized that I use the phrase "now then," a lot when trying to explain something.)

Any questions  (Wow, that was a long post with a lot of parenthesis.)

@graphmastur: OK, I see. So much for hope.... I still think we should at least TRY to factor the keys. After we're done, we're free forever!

well, we're not quite free.  TI will find some way around it.  Okay, so if you really want to try, you are most likely going to want to use the boinc project.  There would have to be a custom server, because NFS won't do it.  The current record is 768-bits made by the top experts in the field.  This is 1024 bits.  This would take absolutely forever.  It's just not possible, without a better algorithm.  So unless you find a better algorithm, then it is not going to work.

Oh well.

Edit: 555^th post! I'm 5/6 of the way to being evil

Congrats!

Mhmm I see, thanks graph

No problem.

What about grayscale support?

*gasp*  a troll!  ban him from the kingdom!!!

oh, and...
1st! (Sorry, couldn't resist)

so they don't say why?  wow.  Can you respond and ask them why?