Can anyone briefly explain how factoring a large number is used to crack the TI? I know they needed to figure out what key to sign a new OS with, but is it symmetric or asymmetric? Also, what are the inputs to the problem and how do you know when it's solved/cracked? Thanks.
The calculator has an RSA public key in it (exponent e, modulus n). TI keeps secret an RSA private key (exponent d, same modulus n). The private key is used to sign the OS and the calculator verifies the signature before running the OS.
The modulus is composed of two primes, p and q. Factoring n into p and q is sufficient to regenerate the private exponent d. Thus, the hackers can now sign their own OS and have it loaded on stock calculators.
I suspect the 512-bit RSA key was used in order for the Z80 to verify a signature in a short period of time. It's possible they even use a small public exponent (e=3), which could enable simpler/quicker attacks than factoring.
TI could have solved this in a number of ways. Partitioning the key space so there isn't one global key (like broadcast encryption) is one solution. Another would be to use ECDSA with a fast curve.
The two prime numbers are multiplied to generate a larger number for use in the RSA algorithm. It is a hard problem to factor a large number and that is why it is used in the RSA algorithm. http://en.wikipedia.org/wiki/RSA . The inputs to the problem are the primes and you know when it is solved when you have the two numbers multiply to give you the larger number.
The 'input' (the public key) of the problem can probably be found in the firmware of the device (it's probably too large to have been bruteforced). To be able to sign code so that the device will run it, you need the private key, which is one of the factors of the public key. So the guy used a program to factor the public key to get the private key so that he could sign the code (whatever code he wants) with it and get the calculator to run it.
