~ Introductory Part ~

In which we explain the concepts involved in such a manner that anyone interested in computers forms a correct and hopefully complete understanding of the matters discussed.

I. What is RSA ?
RSA is a method for creating asymmetric keysⁱ that relies on some properties of numbersⁱⁱ.

Various larger entities (such as government agencies), jealous of the fact that private persons can, with minimal expenditure, exchange secrets safely have been working hard and for many decades to weaken this cryptographic system as much as possible, and destroy it as soon as possible. Part of their efforts is the push towards Elliptic Curve Cryptography (ECC) to replace RSA, in spite of obvious mathematical weaknesses in this proposition. Part of the same efforts have been numerous and diverse implementation flaws, so that the promise of mathematics is not realised by the capabilities of the software.

II. Why should the exponent e be prime ?
There's no requirement per se, mathematically, for e to be prime. However, e must be coprimeⁱⁱⁱ with phi(N), because otherwise messages encrypted can no longer be singularily decrypted (ie, the decryption process allows multiple ambiguous solutions).

In practice, however, it is a lot cheaper to pick a prime exponent, than to check and make sure the exponent shares no factors with N or phi(N), much like in practice it is a lot cheaper to not drive through the swamp than to clean your car after you have. For this reason, nonprime e is generally an indication of subversion of the cryptosystem implementation on other levels, and should be seriously investigated (much like a person who prefers to drive through the swamp has probably other issues as well).

III. What is Phuctor ?

Phuctor is a free service of No Such lAbs^iv that checks RSA keys for various weaknesses and vulnerabilities. It is slightly infamous among non-governmental and anti-governmental communities for the various shenanigans government-aligned websites have engaged in to try and suppress it.

~ The Actual Finds ~

There are three major items Phuctor has found.

I. The Northrop Grumman key.

As a factual matter, a key^v describing itself as

Security; Northrop Grumman PGP Root-CA; TRW-Root-CA - TRW/SEG/ITS/IS <trw-root-ca@trw.com>;

uses exponent (e) 16385, which is not a prime number^vi. Why and wherefore is not clear, nor are there any apparent hits for such a wonder on the public Internet. It should be interesting to hear what happened here, although it is somewhat improbable we'll get to the bottom of this story before complete-victory-against-USG day.

II. The 35^vii exponent.

A large number of keys with exponent 35 have been identified, both for ssh^viii and pgp^ix. This would seem to indicate an implementation flaw in a package used by many people^x. Whether this flaw is intentional or accidental is not obvious (bearing in mind that in cryptography, "accidental flaws" are about as rare as accidental copulation is in the bedroom), but it appears that some organisations^xi have been thoroughly infected.

III. Strange, large, nonprime exponents.
A variety of these have been identified : 3765668207 ; 4202608123 ; 2307795757 ; 2205267067^xii all the way to something as large as

807925151782775182517871917216748799011102566742887100803258635688
116378471697272329930035288072836592217949023047450487352988978762
273027377203809661207078015771934182524902293754943759741302669901
440959601689206919805466065493904045952358461904261764541146300907
626072189397288526645215188809978098259638047858334741708560517124
369664114237371404400883158051451945141483275654817711507853756464
821604427918148590092961546433939958778807541147610092440330832180
780678142117770505243128927543173283086741963564516417448376149931
708824965955388129159735933388590053385830740116132961965123803704
8388963402764899057665

The usual exponent is 65537. This number is used because it is actually a prime number, and because it simplifies calculations significantly^xiii. While there may exist good reasons someone used nonprime, large, strange exponents - such as for instance playing around to learn the ropes - nevertheless if unintentional they may be very notable as indicators of other serious problems^xiv with a given implementation of RSA.

~ What to do ~

You can follow along, either here, on #trilema or on Phuctor's stats page. We are in possession of pretty much every RSA key ever made, and will be going through all of them.

If you are the inquisitive type you might also investigate, either the problems here discussed or other related, derived or entirely novel problems of your own devising.

1. Asymmetric key systems are the only practicable way for people to exchange secrets on the cheap. The alternative, absent these, is using OTPs (One Time Pads) which require sharing a secret in the past, and keeping it secret in the present, to be able to share a secret in the future. [↩]
2. Specifically, that it is a lot easier for you to compute the product of 11, 13 and 17 than for you to find the factors that compose the number 2`431. [↩]
3. This means, have no shared divisors. For instance, 16 and 25 are coprime, even if neither is prime (16 is divisible with 2, 4 and 8 ; whereas 25 with 5). Meanwhile, 11 and 77 are not coprime, even if 11 is itself prime. [↩]
4. MPEx:S.NSA [↩]
5. 80F007FBD8F9950E492F6A2C720FF5C3136DFE1DEC5CE4125B546ADF837AD4A2 [↩]
6. Also seen, for instance, in the signature of one John M. N. McInerney from Encyclopaedia Britannica, or Joe Bradley from ait.nrl.navy.mil. [↩]
7. And other such remarkably low non prime values, such as 21, or, mind-bendingly, one. [↩]
8. Secure SHell, a protocol for securely communicating with remote servers. [↩]
9. Pretty Good Privacy, a protocol for exchanging arbitrary encrypted data. [↩]
10. Including ssh://hook.piratpartiet.se; ssh://lab-1.mit.edu; ssh://www.gulp.linux.it; ssh://kg-dev.vlsci.unimelb.edu.au; ssh://dev.cjadvertising.com; [↩]
11. Such as, for instance, something called mayfirst.org, or for that matter numerous people from FSFE. [↩]
12. This and the previous belong to one Soren Hansen <tsh@warma.dk>; Soren Hansen <tsh@linux2go.dk>; Soren Hansen <tsoren@ubuntu.com>; Soren Hansen <tshawarma@ubuntu.com>; Soren Hansen <tsoren@canonical.com>; Soren Hansen <tsoren.hansen@canonical.com>; [↩]
13. 65537 being a 10000000000000001 in binary, multiplications by it are much much faster than otherwise. Intuitively this is obvious, if you must multiply 11111 with 10000000000000001 the result will be 1111110000000000011111, a result you can obtain and verify without even thinking that 111111 in binary is 63 in decimal notation.

    This, of course, is not without its own pitfalls. [↩]

14. Such as perhaps an overflow of some kind, as the most obvious, banal example. [↩]