New RSA Algorithm discussion

[graphmastur]

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.)

[DJ Omnimaga]

Wow thanks for the explanation. Hopefully it should help people into understanding the concept a bit. One concern I have, though: If we factored the key, could TI release a new line of Nspires that uses a totally different key as a counter-attack or something?

[calcdude84se]

Yes, but while they supported the old ones they'd have to release two copies of each OS, one for each key.
So either they'd drop the old one immediately (probably not) or they'd release two of each OS (possible, but I'm sure TI doesn't want to put their customers through figuring out which revision they have )
We're probably safe.
Thanks for the explanation, graphmastur! I do wonder if we could find a better way...

[quasi_Phthalo]

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.....

[calcdude84se]

That's another way to look at it.
And for those who don't know, the totient function returns how many natural number less than another natural number are relatively prime to it (i.e. no common factors) 1 is considered relatively prime to all natural numbers.

[graphmastur]

I hope we can find another way.  I don't fully understand the Nspire, so this is my way of contributing.  Also, I have one concern. If they can prevent another OS, like below a certain version, then there must be a way to prevent other non-ti os as well.  Basically, if we factor the boot2 key, we shouldn't have any problem at all.

Although, they would not have to do a whole new line, necessarily.  They would just need to change the keys on all new versions.  Also, if the system supported it, technically, the os could have many signatures, all signed with different keys, and if the any/all of the keys matched, it was accepted.  I don't know how effective that would be, though, as you are signing the same hash with different keys.

[t0xic_kitt3n]

When does the OS get validated? At each boot, or just when it is installed?

[graphmastur]

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.

[graphmastur]

Okay, so I noticed something with things mod 4. This table is done mod 4.  eg, 13 mod 4=1.

p	q	n
1	1	1
1	3	3
3	1	3
3	3	1

So in other words, if n mod 4=3, then the number is of the form (4x+1)(4y+3)=16xy+12x+4y+3.  You can graph it, but I know of no way to solve this over the integers.  Any ideas?

[EDIT] oh, and sorry for the double post.
[EDIT2]  See post by me a few posts down for a better explanation.  Post fixed here.

[calcdude84se]

I'm not sure if this can be generalized to higher moduli. If it can, it might not be pretty.

[graphmastur]

I'm not sure if this can be generalized to higher moduli. If it can, it might not be pretty.

Why would it be generalized to higher moduli? 4 is all that is necessary, and I believe it works on all numbers.  Besides, if you solve the equation above over the integers, then there is only one solution.

Can you please explain what you mean a little better?

[qazz42]

What TI needs is an eternity code, that might shut us up

[calcdude84se]

I guess I didn't read it well enough, my bad
Maybe you could explain it a bit better?

[graphmastur]

Okay, well take any n which is a semiprime and do mod 4 of it.  eg, the remainder when it is divided by 4.  So if I have p=13 and q=19, that means p mod 4=1 and q mod 4=3, so pq mod 4=3.  That means that if we have an n, where n mod 4=3, it either means the p mod 4=3 or q mod 4=3, and the other mod 4 =1.

There is one thing I messed up, though.  It is supposed to be (4x+1)(4y+3)=16xy+12x+4y+3.  I'll go fix that in my last post...  Basically, though, if you solve that over the integers, it yields the factors.  There is only one solution.

[bwang]

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.....

No. Computing phi(n) is polynomial-time equivalent to factoring n. It is generally accepted that the two problems are equally hard.

Okay, well take any n which is a semiprime and do mod 4 of it.  eg, the remainder when it is divided by 4.  So if I have p=13 and q=19, that means p mod 4=1 and q mod 4=3, so pq mod 4=3.  That means that if we have an n, where n mod 4=3, it either means the p mod 4=3 or q mod 4=3, and the other mod 4 =1.

There is one thing I messed up, though.  It is supposed to be (4x+1)(4y+3)=16xy²+12x+4y+3.  I'll go fix that in my last post...  Basically, though, if you solve that over the integers, it yields the factors.  There is only one solution.

Why 16*x*y^2? I think its 16xy.
---------------------------------------------------------------------------------------------------------------------
I believe the factorization of RSA-768 used the NFS. If we were really crazy, we could try writing an implementation of the NFS that is faster than what we currently have (GGNFS + Msieve).
Number field sieves are hard to write It would be an interesting community project, though.