Does anyone know why factorization is so dangerous for cyphers like RSA-768?

Question

Data encrytion services seem to be very worried that their cyphers have some weakness in their factors? what's up with that?

Answer 1

Quite simple, actually. RSA is based on large numbers with two prime factors. You can consider the large number as being the public key (to send messages) and either one of the factors to be the private key (to decode messages). If a method were found to factorize large numbers that did not involve massive amounts of computer time (e.g. 1,000,000,000,000,000,000 years) then anyone with the the right software would be able to break codes.

Fortunately, factorization of large numbers is still in a class of problems referred to in compuer science as "NP hard". But lots of mathematicians are working on changing this as we speak.

There are other types of strong encryption which use elliptic functions, and are not vulnerable to an attack based on a fast factorization algorithm. Here, as well though, there are potential vulnerabilities on the horizon. As it happens, Andrew Wiles, the mathematician who proved Fermat's Last Theorem, also proved the "Taniyama-Shimura Conjecture" which will, when mathematicians get around to looking at it, provide a whole new set of tools for dealing with elliptics - and elliptic based strong encryption. You heard it here first.

Cat and mouse. Cryptography is always cat and mouse.

Answer 2

A very important part of modern cryptography is the RSA algorithm, first published about 1976, which has the exceedingly useful property that the key used to decipher a message is different from the key used to encipher it. This lets you do a number of neat tricks:
- You can publish an enciphering key, which anyone can use to send you messages that only you can read.
- You can publish a deciphering key, which anyone can use to read a message that you sent and be assured that it did not come from someone else.
The mathematics of this involves the product of two large prime factors. There is no known easy method of resolving such a number into its factors. Furthermore, there is good reason to believe that no such method exists. But if it did, the RSA algorithm would no longer be a secure method of handling cryptographic keys, and all sorts of things (such as ATM's) would have to be completely redesigned.