Vor acht Jahren habe ich über die RSA-Verschlüsselungen des österreichischen Briefbombers Franz Fuchs berichtet. Dank Blog-Leser John Haas kann ich heute einige dieser Kryptogramme präsentieren.

English version (translated with DeepL)

Mitte der Neunziger-Jahre trieb in Österreich eine Terrorgruppe namens Bajuwarische Befreiungsarmee ihr Unwesen. Sie verschickte Briefbomben unter anderem an den Wiener Bürgermeister Helmut Zilk und die Fernsehmoderatorin Arabella Kiesbauer. Die Anschlagserie forderte vier Todesopfer, 15 Menschen wurden zum Teil schwer verletzt.

1997 ging ein 15-seitges Bekennerschreiben der Bajuwarischen Befreiungsarmee beim Wiener Nachrichtenmagazin Profil ein. Der Inhalt bestand aus langen Zahlenkolonnen, die eine Nachricht darstellten, die mit dem RSA-Verfahren verschlüsselt worden war. Der öffentliche Schlüssel (also ein Primzahl-Produkt) war angegeben. Die Schlüssellänge betrug 1024 Bit.

 

NSA und BSI leisteten Amtshilfe

Die österreichische Polizei bat mehrere Organisationen mit Kryptologie-Know-how um Unterstützung bei der Dechiffrierung der Nachrichten, darunter auch die NSA. Auch das deutsche Bundesamt für Sicherheit in der Informationstechnik (BSI) leistete Amtshilfe. Dort beschäftigte sich unter anderem der inzwischen verstorbene Kryptologe Hans Dobbertin mit dem Kryptogramm.

Doch die Sache schien aussichtslos. Ein RSA-Schlüssel der Länge 1.024 Bit ist bis heute nicht zu knacken – geschweige denn mit den Mitteln des Jahres 1997. Doch dann erkannte Hans Dobbertin, dass der Verschlüssler einen groben Fehler gemacht hatte. Dem BSI-Kryptologen wurde dies klar, als er die Quadratwurzel des Primzahl-Produkts zog und dabei feststellte, dass diese etwa wie folgt aussah:

9385098[…]539,9999999999934085…

Mit anderen Worten: Auf das Komma folgten auffällig viele Neunen. Dobbertin zog die richtigen Schlüsse aus dieser Beobachtung: Die vielen Neunen deuteten darauf hin, dass die beiden Primzahlen, die verwendet wurden, nahe beienander lagen. Vielleicht kann ein Leser erklären, warum das so ist.

Mit dieser Erkenntnis konnte Dobbertin diese Zahlen ermitteln und die scheinbar unlösbaren Kryptogramme leicht dechiffrieren. Ein Mathematiker des österreichischen Verteidigungsministeriums schaffte etwa zeitgleich dasselbe. Nach vier Tagen war das Kryptogramm der Bajuwarischen Befreiungsarmee gelöst.

 

Bajuwarische Befreiungsarmee zerschlagen

Der Klartext erwies sich nach Angaben der Polizei als belanglos. Dennoch konnten die Ermittler der Bajuwarischen Befreiungsarmee schon bald das Handwerk legen, als bei einer Routine-Kontrolle ein gewisser Franz Fuchs einen Sprengsatz zündete, um sich zu töten. Dies misslang, und stattdessen sprengte er sich beide Hände weg. Es stellte sich heraus, dass die angeblichen Terrorgruppe nur aus Fuchs bestand. Dieser nahm sich im Gefängnis das Leben.

Fuchs gab später an, dass er die Schwachstelle absichtlich in die RSA-Verschlüsselung eingebaut hatte. Hans Dobbertin hielt dies für glaubhaft. Bis zu seinem Tod hatte Dobbertin für seine Studenten eine interessante Frage parat: “Wie kann ich eine RSA-Verschlüsselung knacken, wenn in der Wurzel des Primzahl-Produkts nach dem Komma eine Reihe von Neunen steht?”

 

Die Kryptogramme

Über Franz Fuchs habe ich bereits 2014 gebloggt. Damals kannte ich die RSA-Botschaften des Terroristen jedoch nicht. Vor einigen Tagen teilte mir Blog-Leser John Haas mit, dass diese teilweise in folgendem Buch aus dem Jahr 1996 abgedruckt sind:

Quelle/Source: John Haas

John hat mir dankenswerterweise gleich Scans von den entsprechenden Seiten zugeschickt. Am Anfang steht die Chiffrieranweisung:

Quelle/Source: Polizei Österreich

Wie man sieht, kommt der Begriff “RSA” im Schreiben nicht vor. Es ist jedoch klar, dass Fuchs hier das RSA-Verfahren beschreibt. Er kündigt außerdem 15 verschlüsselte Seiten an. Das besagte Buch enthält drei davon:

Quelle/Source: Polizei Österreich

Quelle/Source: Polizei Österreich

Quelle/Source: Polizei Österreich

 

Offene Fragen

Schafft es ein Leser, diese Kryptogramme zu entschlüsseln? Sind weitere Seiten aus dem Schreiben öffentlich bekannt? Ich würde mich sehr über Unterstützung von meinen Lesern freuen.


Further reading: Die Verschlüsselungsverfahren der RAF-Terroristen (1)

Linkedin: https://www.linkedin.com/groups/13501820
Facebook: https://www.facebook.com/groups/763282653806483/

Subscribe to Blog via Email

Enter your email address to subscribe to this blog and receive notifications of new posts by email.

Kommentare (15)

  1. #1 Jarl
    Belgium
    15. April 2022

    I’m not an expert on this but there is a way to more easily find the prime factors of the product when the prime factors are close to each other.

    A silly example would be 17 * 19 = 323. Just find the next square number that is bigger than the product which is 18 * 18 = 324. Subtract the product from the square and if the result (it’s 1) is also a square number (1, 4, 9, etc) then the primes of the product are (18 – 1) and (18 + 1), 17 and 19. If the result is not a square number then try the next square and so on. It’s connected to Ulam’s spiral and discovered by Fermat.

  2. #2 Thomas
    15. April 2022

    Bei annähernd gleich großen Faktoren (also nahe der Quadratwurzel) kann Fermats Algorithmus in annehmbarer Zeit zur Faktorisierung führen: https://de.m.wikipedia.org/wiki/Faktorisierungsmethode_von_Fermat

  3. #3 Thomas
    15. April 2022

    Die beiden Faktoren sind (sie unterscheiden sich nur in den letzten 13 Ziffern):

    251107191269013549761909333958671
    246802408057112768448862509598241
    562051889494061847352957883875611
    35167529435118429780319

    und
    251107191269013549761909333958671
    246802408057112768448862509598241
    562051889494061847352957883875611
    35167529430243075948799

  4. #4 Thomas
    16. April 2022

    Ich frage mich, wie Fuchs ohne overflow einen 123-stelligen Exponenten verwenden konnte.

  5. #5 Gerd
    16. April 2022

    Fuchs muss das damals mit einem Computer Algebra System gerechnet haben, das nicht auf Gleitkomma-Zahlen aufbaut, und auch keine Überläufe erzeugt. Ende der 80 er Anfang 90 er Jahre war zB “muMath” verfügbar, mit dem man sowas rechnen konnte.

  6. #6 Armin Krauß
    17. April 2022

    Die am besten lesbare Seite 4 lässt sich mit den von Thomas gefundenen Faktoren folgndermassen entschlüsseln:

    “e herumstehende Dose aufhebt.

    Im Dorf Stinatz residiert jene Kroaten-Maffia, die ihre minder-
    begabten Lobbyisten in Universitäten, in- und ausländischen
    Sendern und Schulen sitzen hat, die ihren Leuten Mischehen mit
    Deutschen und den Gebrauch der deutschen Sprache im Heimatort
    verbieten will.
    Die Burgenlandkroaten stammen in etwa aus jener Gegend, aus der
    die serbischen Kriegsverlierer mit amerikanischer Hilfe verjagt
    wurden. Für all jene Burgenlandkroaten, die der Meinung sind,
    es reiche aus, innerhalb von zwei Jahrtausenden illyrisch,
    lateinisch und slawisch “

  7. #7 Seth
    17. April 2022

    Languages like Scheme (and I assume Lisp) could compute any precision. I used Scheme around 1997 to compute the exact value of some huge integers.

    Another way is to use GNU Multiple Precision arithmetic library, which was first released in 1991. I think I used that in C and Python back in the day, but now Python’s built in libraries are even better than NumPy — you can get a modular inverse as simply as pow(e, -1, N)

  8. #8 Wandee Thaweetham
    Chanthaburi - Thailand
    17. April 2022

    Beweist doch nur das mathematische Algorithmen keine Lösung für verschlüsselten Text bieten und natürlich auch, dass er eine spätere Entschlüsselung voraussah. Andernfalls hätte er den Text überhaupt nicht geschrieben.

  9. #9 Klaus Schmeh
    17. April 2022

    @Thomas und Armin:
    Vielen Dank! Damit ist ein Teil der Botschaft entschlüsselt. Ich weiß nicht, ob das bereits irgendwo veröffentlicht wurde.

  10. #10 Narga
    17. April 2022

    Vielleicht kann mir jemand auf die Sprünge helfen: Wie ist denn hier das Decoding von Klartextzahl zu Klartext realisiert?

  11. #11 Armin Krauß
    18. April 2022

    @Narga: Die Ascii-Codes der Klartextzeichen werden einfach als dreistellige Dezimalzahlen (mit führenden Nullen) hintereinandergeschrieben.

  12. #12 Narga
    18. April 2022

    @Armin: danke, funktioniert!

  13. #14 Chris
    Vienna
    5. Mai 2022

    Yes, there are a lot of implementations for the fermat algorithm. Nevertheless I added another one 😉

    https://github.com/chris2286266/fermat-factorizer

    Interestingly it takes ONLY ONE iteration to factorize N …

  14. #15 Etsch
    27. Oktober 2022

    Die erste Seite beinhaltet die Nachricht (ohne die #):
    ######################
    *S 2
    *C 4
    *I .
    *S 8
    *C .
    *I 1
    *O 9
    *T 9
    *S 6

    1) Die BBA bekennt sich zu den Anschl„gen in Oberwart und Stinatz,
    die gegen die aus dem Boden gestampfte Neovolksgruppe der Roma
    beziehungsweise gegen das illyrische Volksverhetzernest Stinatz
    gerichtet waren.
    Die Kampfmittel, eine Sprengfalle und ein Selbstschuáapparat,
    wurden produziert und
    ######################
    Es beginnt mit einem seltsam formatierten Datum und dann startet das Bekennerschreiben.

    Da die beiden Faktoren in der Tat relativ sehr eng beieinander sind, entspricht die Lösung der einfachen quadratischen Gleichung $x^2-2*ceil(sqrt(N))*x + N = 0$ den beiden Faktoren von N.