Whoracle said:
ROM SmartCard [http://shop.kernelconcepts.de/product_info.php?cPath=1_26&products_id=42]. The key was even generated on the damn thing. Now, if that hardware has a backdoor, then I'm screwed, but that's the crux: There's always SOMEONE you have to trust...
I'm impressed. *bow*
Whoracle said:
Strazdas said:
Tamayo mentions its "Hard" but isnt that just using same encryption in reverse?
See, this is where the math comes in. Tamayo can explain that way better if you've got a head for it, but until he chips in, suffice to say that no, it's not simply doing stuff in reverse.
er, s/he/she/g
I get this a lot. It's not easy being green. Or short. Or ... um ... yeah.
On topic: the difficulty is similar (but not exactly the same, naturally) to the fact that division is more difficult than addition. Factoring numbers is a kind of division where the dividend is unknown; if you have to search through all different possible dividends, that makes it even harder. Consider my example of n=p*q; if p and q each have 1000 decimal digits, that's an immense and terrifying task one sets oneself. Yes, there are ways of reducing the search space[footnote]The General Number Field Sieve, to be precise---or Shor's algorithm, if you have a quantum computer[/footnote], but until quantum computers are available, they're not good enough.
Edit:
I may not have been sufficiently explicit. Encrypting something in RSA is taking a value m and exponentiating it to the power e, that is, multiplying m by itself e times, modulo n, which is the public key.[footnote]Actually, for an e which is less than 2^f but more than or equal to 2^(f-1), then it takes at most 2*f multiplications.[/footnote] That's fairly slow, but tolerable.
Consequently, decrypting a value c=m^e(mod n) in RSA must be an inverse exponentiation, modulo n. However, inverse exponentiations in general are difficult to perform. I'll have to mention a little bit of math, here, and I'm sorry I didn't do it earlier.
Theorem. ("Fermat's Little Theorem") Let p be a prime, and let a be a positive integer. Then a^p is congruent to a, modulo p. Furthermore, if p does not divide a, then a^(p-1) is congruent to 1, modulo p. (Proof omitted.)
Let e and d be positive integers such that e*d = 1(mod p). Then a^(e*d) = a (mod p). But a^(e*d) = (a^e)^d; that is, if we know e, and (a^e), we can recover a just by exponentiating (a^e) to the power of d, modulo p. Finding such a d where e*d = 1(mod p) is easy, but only because p is a prime.
Theorem. ("Chinese Remainder Theorem") Let s and t be different positive integers each at least two and such that the greatest common divisor of s and t is 1.[footnote]This condition is trivially satisified if s and t are both primes.[/footnote] Let c be a positive integer less than s*t. Then there exist unique positive integers a and b less than s and t respectively such that c = a*b (mod s*t). (Proof omitted.) It is important here to note that given s, t, and c, it is easy and swift to calculate a and b. It is also important to note that finding a c such that 1 <= c < s*t given a and b where 1 <= a < s and 1 <= b < t is even easier and swifter.
So, back to the RSA decryption example: remember that c=m^e(mod n), and m is unknown. However, if we know the factorization n=p*q, we can use the Chinese Remainder Theorem to represent c as c_p and c_q and e as e_p and e_q. Then we can use Fermat's Little Theorem to find the inverses of c_p (mod p) and c_q (mod q). Explicitly, given c_p, we want to find m_p. But c_p = m_p^e_p (mod p) and (by Fermat's Little Theorem) m_p=(m_p^e_p)^(e_p^-1 (mod p)) (mod p), so m_p = c_p^(e_p^-1 (mod p)). Similarly, we find m_q = c_q^(e_q^-1(mod q)) (mod q).
Finally, having found m_p and m_q, we use the Chinese Remainder Theorem again to find the related unique m where 1 <= m < p*q, and we have thus decrypted the message c. Instead of using a difficult procedure (finding an inverse modulo a composite number n) we have used secret knowledge (the factorization of n into p and q) to operate in the far simpler realm of inverting modulo the prime factors of n.
Any asymmetric cryptosystem has this kind of structure. Encrypting something is a matter of applying a function which is difficult in general to invert; decrypting something is a matter of using secret knowledge to make a special case in the difficulty of inversion.
