Fragen? Antworten! Siehe auch: Alternativlos
Das hätte natürlich so nie durch den Primzahlgenerator kommen dürfen. Und in der Tat, wenn man das mal in GMP durch den Miller-Rabin-Test jagt, ist das Ergebnis "keine Primzahl".
#include <gmp.h>Gibt es diesen Key wirklich? Ja, man findet ihn auf den Keyservern. Was zur Hölle ist hier passiert?! Hat der den Key mit einem Hexeditor generiert statt mit gnupg?!
#include <stdio.h>int main() {
mpz_t a;
mpz_init(a);
mpz_set_str(a,"817023023960376946633975507110154649249407598806798730414849884461776172171921668594148071323527016137506405823108520062504849249423700259406905313281403901410082762097159560221463048924336192384026777502177262731045200322200149773127502888545234973139480887644585192600631058962876114156934248895171959246969597637127280010272143593885240940877456234662196130491400738438731832514335353824697930453078426722191105157568392826870043655708008545411143367763836566011740499383456592129662585004880376777597714978023542434421914201119537685489173509942329090631662014650033142642110914360849421856179611226450806562235534802516081595259914768497444702718749402330070488028751073730349460752771915484847399385631524708487646079936572410398967582895983187640798072309362094727654167628620105981459021548290415800096769214437425690934372015628796027498219902441288189398386359846661623243493534897411417685435424010451956954083531228374002591372549525280610594684910812811287436481207089763125424247793044043309737269468709710679872269272855389945385386467765509880648929743498214329578288874987193768439353382305260108425688024147656806932474058888992099083804597481699305852902662863062054067183925164590726103552998367994727700722491707",10);
printf("%d\n",mpz_probab_prime_p(a,10));
}
Update: Bei Hacker News gibt es ein paar Kommentare, die Licht ins Dunkel scheinen.
The factored keypair in question is actually a subkey on HPA's public key. However, it appears that the self signature (which is a signature on the hash of the main public key and the subkey) does not match the hash_check. The issuer of this self signature has the same key_id as HPA's main key, which is why this subkey is listed under HPA's public key.
[…]
EDIT: It's the EXACT SAME subkey self-signature packet as HPA's real subkey self-signature packet! Someone (by malice or mistake) manually added a subkey to HPA's public key and copied the signature from the other subkey directly onto the new subkey.
Und weiter unten jemand anderes:
When I try to import HPA's key from the public key servers, I get an "invalid subkey binding" error and the weak sub key isn't imported. That error means that the sub key isn't properly signed by HPA's master key, so there is no cryptographic proof that this weak sub key actually belongs to HPA. This looks more like a fake sub key that someone tried to pollute the public key servers with, which isn't really an issue because PGP implementations will just ignore it.
Update: Jetzt ist mir in der Aufregung die Formulierung entglitten. Der Modulus ist bei RSA keine Primzahl, sondern das Produkt zweier Primzahlen. Allerdings zweier großer Primzahlen. Herauszufinden, welche zwei Primzahlen das im konkreten Einzelfall sind, ist so schwer, dass das die Sicherheit von RSA darauf beruht.
Wenn man einen Schlüssel generiert, generiert man u.a. diese zwei Primzahlen. Primzahlen generiert man, indem man Zufallszahlen nimmt, und die mit einem probabilistischen Primzahltest prüft, wie z.B. dem Miller-Rabin-Test. Der soll mit an Sicherheit grenzender Wahrscheinlichkeit ausschließen, dass es sich bei den beiden großen Faktoren nicht um eine Primzahl handelt, und der sollte daher fehlschlagen, wenn er einen so kleinen Faktor findet.