To date, there has been no way to mathematically prove that it is inherently difficult to crack this prime-number cipher. It might be very easy to do if one knew the proper advanced mathematical technique for it, and the clumsy brute-power techniques for prime-number factorization have been improving in past years. However, mathematicians have been working steadily on prime number factorization problems for many centuries, with few dramatic advances. An advance that could shatter the RSA algorithm would mean an explosive breakthrough across a broad front of mathematical science. This seems intuitively unlikely, so prime-number public keys seem safe and secure for the time being -- as safe and secure as any other form of cryptography short of "the one-time pad." (The one-time pad is a truly unbreakable cypher. Unfortunately it requires a key that is every bit as long as the message, and that key can only be used once. The one-time pad is solid as Gibraltar, but it is not much practical use.)
Prime-number cryptography has another advantage. The difficulty of factorizing numbers becomes drastically worse as the prime numbers become larger. A 56-bit key is, perhaps, not entirely outside the realm of possibility for a nationally supported decryption agency with large banks of dedicated supercomputers and plenty of time on their hands. But a 2,048 bit key would require every computer on the planet to number-crunch for hundreds of centuries.
Decrypting a public-keyed message is not so much a case of physical impossibility, as a matter of economics. Each key requires a huge computational effort to break it, and there are already thousands of such keys used by thousands of people. As a further blow against the decryptor, the users can generate new keys easily, and change them at will. This poses dire problems for the professional electronic spy.
The best-known public-key encryption technique, the RSA algorithm, was named after its inventors, Ronald L. Rivest, Adi Shamir and Leon Adleman. The RSA technique was invented in the United States in the late 1980s (although, as if to spite the international trade in arms regulations, Shamir himself is an Israeli). The RSA algorithm is patented in the United States by the inventors, and the rights to implement it on American computers are theoretically patented by an American company known as Public Key Partners. (Due to a patent technicality, the RSA algorithm was not successfully patented overseas.)
In 1991 an amateur encryption enthusiast named Phil Zimmerman wrote a software program called "Pretty Good Privacy" that used the RSA algorithm without permission. Zimmerman gave the program away on the Internet network via modem from his home in Colorado, because of his private conviction that the public had a legitimate need for powerful encryption programs at no cost (and, incidentally, no profit to the inventors of RSA). Since Zimmerman's action, "Pretty Good Privacy" or "PGP" has come into common use for encrypting electronic mail and data, and has won an avid international following. The original PGP program has been extensively improved by other software writers overseas, out of the reach of American patents or the influence of the NSA, and the PGP program is now widely available in almost every country on the planet -- or at least, in all those countries where floppy disks are common household objects.
Zimmerman, however, failed to register as an arms dealer when he wrote the PGP software in his home and made it publicly available. At this writing, Zimmerman is under federal investigation by the Office of Defense Trade Controls at the State Department, and is facing a possible criminal indictment as an arms smuggler. This despite the fact that Zimmerman was not, in fact, selling anything, but rather giving software away for free. Nor did he voluntarily "export" anything -- rather, people reached in from overseas via Internet links and retrieved Zimmerman's program from the United States under their own power and through their own initiative.
Even more oddly, Zimmerman's program does not use the RSA algorithm exclusively, but also depends on the perfectly legal DES or Data Encryption Standard. The Data Encryption Standard, which uses a 56-bit classical key, is an official federal government cryptographic technique, created by IBM with the expert help of the NSA. It has long been surmised, though not proven, that the NSA can crack DES at will with their legendary banks of Cray supercomputers. Recently a Canadian mathematician, Michael Wiener of Bell-Northern Research, published plans for a DES decryption machine that can purportedly crack 56-bit DES in a matter of hours, through brute force methods. It seems that the US Government's official 56- bit key -- insisted upon, reportedly, by the NSA -- is now too small for serious security uses.
The NSA, and the American law enforcement community generally, are unhappy with the prospect of privately owned and powerfully secure encryption. They acknowledge the need for secure communications, but they insist on the need for police oversight, police wiretapping, and on the overwhelming importance of national security interests and governmental supremacy in the making and breaking of cyphers.
This motive recently led the Clinton Administration to propose the "Clipper Chip" or "Skipjack," a government- approved encryption device to be placed in telephones. Sets of keys for the Clipper Chip would be placed in escrow with two different government agencies, and when the FBI felt the need to listen in on an encrypted telephone conversation, the FBI would get a warrant from a judge and the keys would be handed over.
Enthusiasts for private encryption have pointed out a number of difficulties with the Clipper Chip proposal. First of all, it is extremely unlikely that criminals, foreign spies, or terrorists would be foolish enough to use an encryption technique designed by the NSA and approved by the FBI. Second, the main marketing use for encryption is not domestic American encryption, but international encryption. Serious business users of serious encryption are far more alarmed by state-supported industrial espionage overseas, than they are about the safety of phone calls made inside the United States. They want encryption for communications made overseas to people overseas -- but few foreign business people would buy an encryption technology knowing that the US Government held the exclusive keys.
It is therefore likely that the Clipper Chip could never be successfully exported by American manufacturers of telephone and computer equipment, and therefore it could not be used internationally, which is the primary market for encryption. Machines with a Clipper Chip installed would become commercial white elephants, with no one willing to use them but American cops, American spies, and Americans with nothing to hide.
A third objection is that the Skipjack algorithm has been classified "Secret" by the NSA and is not available for open public testing. Skeptics are very unwilling to settle for a bland assurance from the NSA that the chip and its software are unbreakable except with the official keys.
The resultant controversy was described by Business Week as "Spy Vs Computer Nerd." A subterranean power- struggle has broken out over the mastery of cryptographic science, and over basic ownership of the electronic bit- stream.