S.NSA - RSA public key factorisation webservice

Public-private key encryption (also known as asymmetric key encryption) depends on the existence of problems that are relatively simple in one direction and hard in the opposite directionⁱ. As long as such problems exist PGP works, and as long as PGP works cheap and strong cryptography is easily available to the masses.ⁱⁱ

One such problem is the integer factorisation problem, on which the RSA scheme is based. Specifically, given the number 143429 it is relatively difficult for you to discover that it is in fact the product of 11, 13, 17 and 59. Nevertheless, given the numbers 11, 13, 17 and 59 it is relatively easy for you to discover they multiply to 143429. This is pretty much what RSA does, except it uses much longer numbersⁱⁱⁱ

Recently there have been various reports in the press about weak RSA keys^iv One such report famously claims four keys in one thousand are useless. Obviously this would be a point of concern to ordinary users, but at the same time it wouldn't necessarily be something they can easily verify.

No Such lAbs (MPEx : S.NSA) makes it its business to mind security, and as such has recently released Phuctor: The RSA Super Collider. Supercomputers running a highly advanced piece of algorithmics called EGCD^v are at your disposal, ready to help. All you have to do is paste your public key in and check back a little later. NSA will compare your public key to all the other keys already submitted and see if there's any factors shared by at least two keys. Should this be the case those keys are, of course, insecure, and their use should be discontinued as soon as possible. Should no factor larger than 1 be found this doesn't necessarily prove that the examined key is secure from factorisation attacks however, it may simply be the case the key's particular vulnerability has not been seen before.

In general it is well understood that keys weak in this manner result from poorly implemented random number generation, either though hardware or software failure. As a result, it is somewhat likely that a broken device or process would create families of similarly weak keys. Testing multiple keys generated through the same means should be a reasonable first line test of the quality of the respective process.

The service is currently openly offered for no charge. This may change in the future, depending on computing power needs, so hurry up and take advantage while free beer supplies last.

1. Which would be, I suppose, yet another class of semi-permeable membranes. [↩]
2. Without PGP and before PGP the only way to secure messages were one time pads. These have to be communicated aforehand and through secure channels, as anyone possessed of the OTP can decrypt and encrypt at will. Consequently strong cryptography was only available to those able to move reams of paper back and forth securely, which pretty much means "a few governments". [↩]
3. A few hundred digits, so very long numbers indeed. [↩]
4. Keys which can be factorised fail to deliver on the original promise (that the problem is hard in one direction) and as such are pretty much useless. Or perhaps worse than useless, if anyone relies on them seriously. [↩]
5. Known ever since the ancient Greeks, inasmuch as it's Euclid's Greatest Common Divisor procedure. [↩]