Is prime factorisation in NP?
I just wanted to jump in to say what a great thread this is. I’d always sort of wondered about how PGP works but never actually put the effort into framing the question. Congrats, Halitosis, on the great OP and followups and to thos who answered. Particularly to gotpasswords who included the link to the T-Shirt. I love that T-Shirt.
Not being an algorithms guy, I defer to (and quote) experts. According to Garey and Johnson (first useful google link):
Perhaps you should rephrase the question!
Heh. IMHO, it’s impossible to talk about cryptography w/o someone mentioning how difficult it is to factor large prime numbers. Coupla times it’s been me. 
What’s MTBF?
MTBF = Mean Time Before Failure (basically when the manufacturer expects there to be a good chance your computer will fail…your warrantee will always be less than this time).
Of course in a NSA type environment I am sure the computers are looked after rather well and if something breaks it is doubtless fixed and running again in short order.
I have a hard time relating these really big numbers to anything I can more easily grasp. The US is planning a supercomputer that can run 50 trillion calculations per second (sustained). At that speed I would think PGP would crack in relatively short order but then I really have no clue.
If they ever get quantum computers running in a useful way factoring large numbers will become trivial (at least to those with quantum computers).
Arrgh! Now I have a new problem:
I can’t find any free, non-internet-based, Windows PGP key program with a GUI. I’ve found ones that cost money, ones hosted on the internet, and (lots of) ones for Linux, but are there any that I can create keys from sitting at my Windows box without an internet connection and without going to any prompts?
[ul]
[li]Windows Privacy Tray[/li][li]GNUpg[/li][/ul]
Whooo, it worked! Would anyone be so kind as to send me their own PGP public key / message so I can make sure that I know how to use it? (Sorry if I keep asking too much!) I uploaded my key to http://pgp.mit.edu/ with key ID 0x127A4EE9 . Pretty please!
Well, duh, of course it’s the LAST one tried.
Why would you keep trying after you’ve found the password that works?
:smack:
You knew what I meant 
Clarification:
SHA-1 has 160 bits in its hash. If you were given a message (and its hash) and had to find a second message with the same hash, it will take you on average 2^159 (half of 2^160) random guesses. You only get to choose one of the messages.
Instead, if you are told to find any two messages with the same hash (so you get to choose both message), it will take you on average 2^79 (half of 2^80) random guesses.
By the way, I believe cryptographers have found a way to find two messages with the same SHA-1 faster than random guessing (i.e., brute force). Thus, SHA-1 is considered broken, although only marginally at this time, since it’s still computationally very difficult to find a pair.
No one has quite explained how the RSA (Rivet, Shamir, Adelman) system of public key cryptography works. I will try. But first let me say that indeed if someone figures out a fast way of factoring numbers, it will be trivial to crack. There are other schemes (elliptic curve method and, I believe, the discrete logarithm method) that are based on other seemingly difficult problems. Incidentally, factorization is one problem for which a fast method is known, but it is based on a quantum computer. So if anyone succeeds in building a quantum computer…
I will write x^y for x to the power y, enclosing y in braces, that is {y} if it is more than one character long and x^y (mod m) for the remainder that x^y leaves when divided by m. I will write x == y (mod m) to mean either of the following two equivalent statements: m divides x - y; x and y leave the same remainder when divided by m. I will write x^y (m) for the remainder when x^y is divided by m. I will write != for not equal. I will write phi(m) for the number of numbers less than or equal to m and having no common divisors with m. So phi(1) = 1, phi(2) = 1, phi(3) = 2, phi(4) = 2, phi§ = p-1 whenever p is prime and so on. If p != q are prime, then it can be shown that phi(pq) = (p-1)(q-1). (More generally, if a and b have no divisors in common, then phi(ab) = phi(a)phi(b), but we have no need of that more general fact.) It is elementary to show that when p != q are prime, then factoring pq has the same difficulty of calculating phi(pq). That is, answering one of these two questions gives you a trivial computation for the other. The last observation required is that even when n and m are 1000 digit numbers, it is not hard to calculate x^n (mod m) for any x < m. All this is well known and I will not go into detail.
Fermat proved (Fermat’s little theorem) that if p is prime, then for any number a, a^p == a (mod p). It is not hard to prove, but all proofs I can think of are either somewhat sophisticated or rather computational. It can be found in any book on number theory. Euler generalized this to say that if m is any square free number (not divisible by the square of any prime) and if d and e are numbers such that de == 1 (mod phi(m)), then for any number a, a^{de} == a (mod m). This is really a gloss on Fermat’s theorem. It follows that if a < m, a^{de} (mod m) is equal to a.
Now here is how RSA works. Let m = pq, a product of, say, two 500 digit primes. (I will say something more about that below.) This will be a number of about 1000 digits (actually 999 or 1000). Since you are the one who has chosen p and q, you can compute m while, presumably, no one else can. Choose d and e so that de == 1 (mod phi(m)) (easy) and publish d and m, while keeping e and phi(m) (as well as p and q) secret. Someone wishing to send you a coded message first encodes it as a string of integers and breaks it up into substrings, all less than m. If a is one of those substrings, you transmit a^d (mod m). If he transmits b, then b^e (mod m) is a and there you have it! The encryption and decryption process are then raising to the power d and then e, mod m, and are therefore completely different. Aside from possibly easy factoring algorithms, it is conceivable that some decryption algorithm exists that is independent of factorization. No one knows. Well, I should say that if anyone knows, he is keeping it secret. That goes for factorization too. Incidentally, although this works in some reasonable time, it is slow enough that RSA is generally used only to generate and exchange keys for some faster kind of symmetric algorithm.
What about finding primes? Well, there is actually a polynomial time algorithm that can test primality. But if I were carrying it out, I would use a probablilistic method. It is based on the fact that, while the converse of Fermat’s little theorem is false, it is nealy true, in the sense that if a number m is such that a^m == a (mod m) for all a having no common divisor with m, then m is most likely prime. Not necessarily, but with probability that is very nearly 1 when m is large. In fact, if even 2^m == 2 (mod m), then most likely m is prime and the probability increases as yoou test other numbers. The test can be refined by taking into account how many times 2 divides m - 1 and you get to 100 nines probability very quickly, far exceeded by the probability of having a mole in your office.
Some years ago, the American Mathematical Monthly had an article on RSA cryptography by Susan Landau, now employed by Microsoft Research, in which she pointed a number of conditions on the primes p and q that had to be avoided to be safe. There were quite a number o them and new ones seemed to be being discovered all the time, which made me wonder how safe it ws even now.
Interesting, I actually was misundertanding this to mean that you could determine collisions with an existing value within 2^(n/2), but apparently I’m wrong. 
Susan Landau has worked for Sun for many years.
I brought up the issue of the ratio of “bad primes” with Ron Rivest in 1978. He was surprisingly unconcerned. My doubts have only gotten stronger.