a superbly difficult question.

[xluryan]

this is not entirely related to the game, but a good questin indeed.  i read somewhere that people know how to crack RSA encryptions, but cannot.  first of all, how do you crack them?  second of all, why cant you?

[Crazy Carl]

RSA encryptions (using prime numbers) are founded on the difficulty of determining the factors of very large prime numbers. This is to say that it is difficult, though still crackable. A few distributed computing organizations exist which have internet based clients which break the key using huge amounts of computing time. Quantum computers (when they become practical) have the ability to easily determine factors (among other things) and would render many current forms of encryption insecure.

Here's the relatively easy to understand math behind RSA public key encryption.

Find P and Q, two large (e.g., 1024-bit) prime numbers.

Choose E such that E is greater than 1, E is less than PQ, and E and (P-1)(Q-1) are relatively prime, which means they have no prime factors in common. E does not have to be prime, but it must be odd. (P-1)(Q-1) can't be prime because it's an even number.

Compute D such that (DE - 1) is evenly divisible by (P-1)(Q-1). Mathematicians write this as DE = 1 (mod (P-1)(Q-1)), and they call D the multiplicative inverse of E. This is easy to do -- simply find an integer X which causes D = (X(P-1)(Q-1) + 1)/E to be an integer, then use that value of D.

The encryption function is C = (T^E) mod PQ, where C is the ciphertext (a positive integer), T is the plaintext (a positive integer), and ^ indicates exponentiation. The message being encrypted, T, must be less than the modulus, PQ.

The decryption function is T = (C^D) mod PQ, where C is the ciphertext (a positive integer), T is the plaintext (a positive integer), and ^ indicates exponentiation.
Your public key is the pair (PQ, E). Your private key is the number D (reveal it to no one). The product PQ is the modulus (often called N in the literature). E is the public exponent. D is the secret exponent.

You can publish your public key freely, because there are no known easy methods of calculating D, P, or Q given only (PQ, E) (your public key). If P and Q are each 1024 bits long, the sun will burn out before the most powerful computers presently in existence can factor your modulus into P and Q.

The basic result is; Sure, you can crack RSA Encryption on your TI-86 calculator. How long it takes you to do it is another thing entirely...

(Edited by Crazy Carl at 4:07 am on Mar. 21, 2003)

[waldaberz]

Wowzerz.

[Confederate EDA]

 This is where luck comes into play...since most people don't even have any access to supercomputers (which might not do the job either), this technology is, for the time being, secure.  However, it won't be long before very powerful systems are sold cheaply, and it becomes MUCH easier to decrypt these public keys.