Even someone like me knows that, for some reason, large prime numbers are useful in encryption. But why? Perhaps someone can explain the basics not only of encryption, but also of algorithms for cracking it.Thanks,MP

One application is in the RSA crypto. For a short intro to the RSA crypto, see:RSA Algorithm JavascriptIt also includes a small javascript game showing the procedure.

They're useful, but unfortunately also hard to implement in hardware, thus slow in operational use.Most encryption schemes have the same key for encryption as decryption. For a long while, this intuitive situation was regarded as unaviodable. Many problems with this situation, the first being key distribution. How do you send the key to your counterparty ?Over a network, you are faced with the entertaining notion of sending a packet of the form "My new key is X". Given that you often change keys because you fear the n/w has been compromised, it doesn't really help much.Worse, you must give a different key to each counterparty, since you don't want to have the whole thing compromised if one node is captured.It seems that turning a factor of two primes back into the two primes is very hard, this can be used by algorithms like RSA to have one public key for encrypting messages, and another for decryption. The public key can be published to anyone who wants to communicate securely with you. Like many briliant discoveries the maths aren't too hard to follw. A good start may be found here

I'm not yet convinced that they are so slow in operational use... basically, a lot of the underlying stuff is of log order in the size of the number - I guess computer people prefer to say that it's linear in the number of digits. Suppose you have a great big number and you want to factor it. It's a simplifying assumption to assume that the thing only has two factors. But, where do you start looking? Thing is, # of prime factors that are candidates is really sqrt(N) / 2log N... and that's way too many to check. You can reduce the number modulo any prime you want, and find some things out (i.e. if N = pq, then N mod r = (p mod r) . (q mod r) mod r). But the strength of these kinds of algebraic rules is quite weak. You can do similar things with elliptic curves... can't really remember how that goes, but that's where the strongest stuff to date is found. But at the end of the day, we're still a long way from the solution.I have looked for answers on the analytical side of the fence. Instead of asking exactly what primes are the factors, can you at least give some probability distributions, so that you don't spend all day looking in the wrong place? You could take the range [N - g, N + g], and try to come up with all the prime factors in this range... i.e. the key is to do some averaging. But g = g(N), and in order to get anything at all you will need g to be pretty big as compared with N.It should be said that most of what we have on the analytical side is not 'constructive' in the mathematical sense - i.e. the sieve theories might tell you that you are pretty close to solving Goldbach, but wouldn't tell you what the actual numbers are. It's a little like Heisenberg - which is really just an issue with Fourier transforms. You might be able to show that the density is positive, but not know at the very same time where the mass is.

A nice book on the subject I read in recent months is Steven Levy's "Crypto." Also tells the story of the losing battle NSA faced, the history of RSA, and other interesting side stories....

I'm not yet convinced that they are so slow in operational use... Fraid so. Many crypto schemes can be implemented directly as shifts and logical operators. By contrast RSA is done as an algorithm, and is thus inherently 2-3 orders of magnitude slower than DES chips.So slow are RSA style algorithms that they are for more often used for "signing" data, to indicate the authenticity and integrity of a message, rather than to protect it against snoopers.

interesting topic. someone told me that if a solution to NP=P is found, then the whole subject of cryptology will collaspe etc. in fact that guy told me that the whole concept of internet can collaspe. suppose i do indeed have a solution NP=P, algorithm to solve every god-damn NP problem in P time. Then lets say i want to use to gain control of the world, how do I go about ... for instance suppose I am company A and I have a competitor B who has a computer network etc, then how do I use NP=P solution to break into his network by decripting his network passwords routines in P time (like RSA etc) .... i really don't know anything on networking beyond the two commands ipconfig and ping and that there are some stuffs called protocols and gateways which I dunno, but think are important for reasons uncomprehendable to me. so on a curious note ... anyone has any answer ?

Wouldn't get you into our network, we use DES built into the routers Defeat Prime numbers and NP would cause issues. However cryptology has other techniques immune to this attack.The gold standard is one time pads. Give each correspondent a DVD with 5 Gb of random numbers. Each byte is exclusive or-ed with it, rendering any data stream into perfectly undeciperable gibberish. Each time you XOR a byte, you move onto the next on the random set. You're below the Shannon limiit here so any form of decryption is simply impossible. There is no repetition of key usage so it is invulnerable to post analysis. Further, the statistical qualities of the source data is not in any way visible in the output.It even has good grace of degradation under compromised sources. A standard technique is to provoke the target to send a message whose contents you can predict. Use of this dates back at least to WWII where Britain carried out bombing raids on specific targets to generate such traffic. A more prosaic attack is to infiltrate a user of the system to send known messages.If you know the source data, and intercept the data stream, then schemes varying from Enigma to DES are vulnerable. Under one time key you have achieved absolutely nothing, since that key will never be used again. Thus all you can determine is the random numbers that were used, and if you do your job even vaguely competently, have no relationship to future ones.Brute force of trying every single possible key aside from having to grapple with 2^10^9 combinations has no way of telling when you have got the "right" decryption. Because your candidate decryption key is as likely to render up "attack at dawn" as "send more pizza", and with no way of knowing which is correct.

As a sort of corollary to this, an ideal encryption algorithm, random number generator and data compressor all should deliver mutually indestringuishable output. If Zip can compress your encrypted data, you're in trouble, and a DES chip is a decent random numbr generator.

A very readable account of both the history of cryptography and current methods like DES and RSA is given in Simon Singh "The Code Book"I can recommend it to anyone who is interested in cryptography. My brother gave it to me as a christmas gift two years ago and I couldn't put it down until I finished it.Regards,Niclas