Anybody that has a good method for factoring large numbers can crack RSA. That person can factor the public value of n to obtain the unique prime factorization pq and thereby obtain the back-door values of p, q, and e (the last of which is public knowledge). Fortunately for those of us that rely on RSA, factoring is widely accepted as a very difficult problem, with no known efficient solutions. The best known factoring algorithms have exponential running-time and would require vast computing resources to factor large numbers. Mathematicians have been searching for better factoring algorithms for centuries. Their failure to find better algorithms is strong evidence that such algorithms don’t exist, or if they do then their discovery is not imminent. (The popularity of RSA is not a significant motivator in the search for factoring algorithms, when viewed in the context of the full history of mathematics.)
I personally contributed in cracking one specific RSA key. I was working for a small telecommunications company at the time, Multi-Media Telecom, having left AT&T. The key we helped crack was 129 bits long, which would seem to be long enough to be impervious to a factoring attack. Nonetheless it was broken in April of 1994 in response to a public challenge first posed in the pages of Scientific American in 1977. The puzzle was cracked using a variation of the quadratic sieve factoring method. The program required about 5000 mips-years and was carried out in eight months by about 600 volunteers from more than 20 countries. The entire effort was conducted and coordinated over the Internet. I had one of my machines cranking round-the-clock on RSA-129. The challenge cipher-text was published as:
9686961375462206147714092225435588290575999112 4574319874695120930816298225145708356931476622 883989628013391990551829945157815154
It was announced that the public exponent was 9007. The secret exponent is easy to compute once one knows the prime factorization of the public modulus. That modulus was published as:
1143816257578888676692357799761466120102182967 2124236256256184293570693524573389783059712356 3958705058989075147599290026879543541
This modulus was factored on the net:
3490529510847650949147849619903898133417764638 493387843990820577 * 32769132993266709549961988190834461413177642967 992942539798288533
Once the prime factors are known, computing the secret exponent is easy. For RSA-129, the secret exponent is:
10669861436857802444286877132892015478070990663 39378628012262244966310631259117744708733401685 97462306553968544513277109053606095
Using this exponent to decrypt the cipher-text yields:
200805001301070903002315180419000118050019172105 011309190800151919090618010705
If one re-writes this number in base 27 using 00=space, 01=A, 02=B, 03=C, and so up to 26=Z, then the result is:
THE MAGIC WORDS ARE SQUEAMISH OSSIFRAGE
The complexity of the factoring problem grows roughly exponentially with the length of the key. The above example used a key of 129 bits. Using the same methods and the same amount of computing power, a 130-bit key would take roughly twice as long to crack. Such is the nature of exponential problems. In fact, a year later a 130-bit RSA challenge was solved in the same way, over the net. Both of these public efforts made use of an awesome amount of computing power, harnessing the power of the Internet. These were world-wide cooperative efforts, the likes of which are not normally available to spies, thugs, and other evil-doers. Still, just to be on the safe side, people typically use RSA key lengths of 768 or 1024 bits, and sometimes even 2048 bits. Remember, each additional bit in key-length doubles the resources needed to crack the code. Barring a revolutionary advance in computational number theory, using key sizes of at least 1024 bits for RSA is quite safe.
The next big advance after public-key cryptology came in 1984, when Gustavus J. Simmons published his work on the theory of authenticity. This opened up a new side of the field, demonstrating that cryptology can be used to establish communication channels that are resistant to tampering. Moreover, the property of information integrity and message authenticity, as this came to be known, can be separated from the property of message privacy. Cryptography can be used to achieve integrity without privacy or privacy without integrity (or both together of course). This opens up new areas for cryptographic applications, where secrecy is not important but integrity is. The work of Simmons, Shamir, Rivest, Adleman, Diffie, Hellman, and others has gone a long way toward moving the field of cryptology out of the back-rooms of espionage and into the fore-front of the contemporary computing and telecommunications industries. The recent blossoming and merging of those two industries has sealed the fate of modern cryptology — it is indespensible to the manner in which we exchange information today.
The significance of public-key cryptography cannot be over-estimated. When used for information integrity and authenticity, the advantages become greater still. Public-key encryption can be used “backwards” to achieve a digital signature. If Alice uses her private key to scramble a plain-text message, then while anybody can regain the original plain-text because everybody knows Alice’s public key, only Alice can scramble a message in this way. There is no privacy when Alice uses her private key in this manner, but there is integrity and non-repudiation. If Bob has both the plain-text version of a message and the version created with Alice’s private key, then Bob can be sure that Alice is the one that created the scrambled version; nobody else has the ability to scramble the bits in a way that will produce the original message when Alice’s public key is applied to it. Without Alice’s private key, forgeries are computationally infeasible.
Digital signatures are much more secure than hand-written signatures. There is no known way to forge a digital signature. So long as Alice keeps her private key secret, nobody can forge her signature. Therefore, if a signed message conforms to Alice’s public key, then she cannot deny having signed it without also accepting that she has allowed her private key to be released to a third party.
Another advantage that digital signatures have over hand-written signatures is that the signature is applied to the entire message. Every bit of the digital message is perturbed by the signing key. A hand-written signature is applied to the bottom of a paper document. There is nothing that prevents alteration of the text appearing above the penned signature while leaving the signature intact. Such alterations are not possible with digital signatures. Changing even a single bit of a signed message will cause the verification procedure to fail.