Unser verzwicktes Kryptorätsel – die Auflösung

Unser verzwicktes Kryptorätsel – die Auflösung

In unserem Kryptorätsel vom 13. August drehte sich alles um ein geheimnisvolles Bild. Zugegeben, das Rätsel war nicht ohne. Umso mehr freuten wir uns über die richtigen Einsendungen, unter denen wir eine Teilnahme an unserem Security Workshop genulab verlosten. Und für alle, denen das Knacken des Codes leider nicht gelungen ist, haben wir hier den detaillierten Lösungsweg.

Schritt 1: Das Geheimnis des weißen Bildes

Entscheidend war diesmal nicht der Kryptotext, sondern vielmehr der Hinweis, welcher sich in einem scheinbar weißen Bild hinweis.png befand:

Das Programm file(1) sagt einem, was für ein Bild sich hinter der Datei hinweis.png verbirgt:

# file hinweis.png
hinweis.png: PNG image data, 64 x 64, 1-bit colormap, non-interlaced

Das Bild besteht aus 64x64 Pixeln und ist monochrom. Da das Bild beim Betrachten rein weiß erscheint, ist es wichtig zu erfahren, welche Farben tatsächlich in dem Bild verwendet werden. Dazu können zum Beispiel die Programme des ImageMagick-Projekts verwendet werden.

# convert hinweis.png histogram:- | identify -depth 1 -format %c -
      1702: (254,254,254) #FEFEFE srgb(254,254,254)
      2394: (255,255,255) #FFFFFF white

Nun wissen wir, dass es sich um weiß (255,255,255) sowie einen sehr hellen
Grauton (254,254,254) handelt. Damit die grauen Pixel besser sichtbar werden, konvertieren wir diese Pixel zu schwarz:

# convert hinweis.png -black-threshold 100% hinweis_bw.png

Das neue Bild hinweis_bw.png sieht nun so aus:

An dieser Stelle braucht man etwas Phantasie und Geschick beim Raten, was einem dieser Pixel-Verhau sagen will. Bei näherer Betrachtung fällt auf, dass jede achte Pixel-Spalte komplett weiß ist – der entscheidenden Hinweis, dass eine 8-Bit Codierung vorliegt und es sich dabei um ASCII handelt.

Daraus folgt, dass die weißen Pixel Nullen und die nun schwarzen Pixel Einsen repräsentieren. Um die Pixel aus dem Bild als Bits in eine Datei zu schreiben, kann man nun ein separates Programm erstellen, welches unter Zuhilfenahme einer Grafik-Bibliothek wie etwa gdlib die Pixel in Bits und die Bits in Bytes umwandelt.

Kenner von Dateiformaten nehmen an dieser Stelle eine Abkürzung: Das "Portable Bitmap Format" (.pbm) stellt Bild-Informationen genau auf oben beschriebene Art und Weise dar. Konvertiert man die PNG-Grafik nun in das PBM-Format, kann man sich den ASCII-Inhalt direkt anzeigen lassen:

# convert hinweis_bw.png hinweis_bw.pbm
# cat hinweis_bw.pbm
P4
64 64
/*
 *        /\
 *       /  \
 *      /,--.\
 *     /< () >\
 *    /  `--'  \
 *   /          \
 *  / genua gmbh \
 * /______________\
 */

#include <stdio.h>
#include <stdlib.h>
#include <stdbool.h>

int
main(void)
{
        unsigned int n = 0;

        for (unsigned int number = 1; n < 42; number++) {
                bool found = true;

                for (unsigned int check = 2; check < number; check++)
                        if (number % check == 0)
                                found = false;

                if (found) {
                        n++;
                        if (n == 23 || n == 42)
                                printf("%u\n", number);
                }
        }

        return EXIT_SUCCESS;
}

Das Bild beinhaltet also den Quellcode eines kleinen C-Programms. Übersetzt man dieses Programm und wendet es an, gibt es zwei Zahlen aus:

# cc -std=c99 -o hinweis hinweis.c
# ./hinweis
79
179

Schritt 2: Der private Schlüssel

Die Hälfte des Rätsels ist gelöst – wir sind hinter das Geheimnis des weißen Bildes gekommen. Aber wie geht es nun weiter? Um den Zusammenhang zwischen den beiden Zahlen und dem Kryptotext zu verstehen, muss man wissen, was das Besondere an ihnen ist. Dazu ist es nötig, sich den Algorithmus anzuschauen, der die Zahlen erzeugt: Er sucht nach Zahlen, welche nur durch 1 und sich selbst teilbar sind. Demzufolge handelt es sich bei den gesuchten Zahlen um Primzahlen. Die gefundenen Primzahlen werden nun gezählt. Die 23. sowie die 42. gefundene Zahl werden dann durch das Programm ausgegeben.

Den Hinweis zum Entschlüsseln des Kryptotextes bilden also zwei Primzahlen. Die Kombination von zwei Primzahlen und einem Kryptotext lassen auf den RSA-Algorithmus schließen.

Der Kryptotext wurde also mit RSA-Schlüsseln erzeugt, welcher sich aus den beiden Primzahlen ergibt. Ableitend aus der Wikipedia-Erläuterung zum RSA-Algorithmus erzeugt das folgende Python-Programm den privaten RSA-Schlüssel.

Davor muss allerdings noch ein "e" bestimmt werden. Da es für "e" mehrere Möglichkeiten gibt und es nicht egal ist, welche dieser Möglichkeiten man nimmt, haben wir uns für die "5" entschieden. Ein kleiner Hinweis auf die 5 war das "Allsehende Auge" im C-Quelltext zuvor. Zugleich ist die 5 aber auch die erste Zahl, die die Eigenschaften von "e" erfüllt. Somit sollte man durch den Hinweis oder auch einfach durch Probieren auf die Zahl gekommen sein.

p = 79
q = 179
n = p * q
phi = (p-1)*(q-1)
e = 5 # muss relativ prim sein zu phi

# übernommen aus gist.github.com/avalonalex/2122098
def extendedEuclid(a, b):
        """return a tuple of three values: x, y and z, such that x is
           the GCD of a and b, and x = y * a + z * b"""
        if a == 0:
                return b, 0, 1
        else:
                g, y, x = extendedEuclid(b % a, a)
        return g, x - (b // a) * y, y

def modInv(a, m):
        """returns the multiplicative inverse of a in modulo m as a
           positive value between zero and m-1"""
        return extendedEuclid(a, m)[1] % m

d = modInv(e, phi)

Die Variablen "d" und "n" bilden gemeinsam den privaten Schlüssel. Doch wie wenden wir den Schlüssel nun auf den Kryptotext an? Der Text besteht aus einzelnen Hex-Zahlen, unter denen einige wie etwa 0x2ecc auch mehrfach vorkommen: Ein Hinweis darauf, dass jedes Zeichen des Lösungstexts einzeln verschlüsselt wurde.

Somit muss nun jede Zahl einzeln mit dieser Formel entschlüsselt werden:

p = Zahld % n

Das Python-Programm wendet diese auf den gesamten Kryptotext an:

ciphertext = """
0x03e1 0x0dc0 0x08a8 0x2151 0x00e1 0x1c7e 0x149e 0x026d
0x2d6a 0x056f 0x0961 0x2ecc 0x2c6b 0x1704 0x1f51 0x00e1
0x2ecc 0x2d6a 0x3707 0x2ecc 0x1d13 0x00e1 0x026d 0x2c6b
0x1704 0x3707 0x0961 0x2ecc 0x08a8 0x2ecc 0x28a0 0x217c
0x3707 0x00e1 0x2ecc 0x15f0 0x1704 0x1c7e 0x1ac6 0x1f51
0x28a0 0x28a0 0x026d 0x1ce5 0x348c 0x03f5
"""

ciphernums = [int(word, 16) for word in ciphertext.split()]
decoded = [pow(m, d, n) for m in ciphernums]
print "".join(chr(d) for d in decoded)

# python decode.py
IT-Security made in Germany - ohne Backdoors.

Die richtige Lösung lautet also: IT-Security made in Germany - ohne Backdoors.

Hinweis: Das hier gezeigte Krypto-Beispiel ist selbstverständlich nicht für den produktiven Einsatz gedacht, sondern lediglich als Lehrbeispiel.

Wir hoffen, Sie hatten Spaß bei dieser Herausforderung und werden sich auch unseren zukünftigen Rätseln stellen!

Update: Wir bedanken bei Herrn Dr. Daniel Loebenberger für den Hinweis, dass unser Primzahl-Programm aus dem weißen Bild nicht die 23. und 42. Primzahl berechnet, sondern die 22. und 41. Primzahl, da 1 selbstverständlich keine Primzahl ist.

Lesen Sie auch: Ich sehe was, was du nicht siehst ...">E-Mail-Codierung: Ich sehe was, was du nicht siehst ...

 

Bildquelle: ©kantver - Fotolia.com


Diskutieren Sie mit

Sie können diesen Artikel sofort ohne Registrierung als Gast-User kommentieren.

Registrieren Sie sich jetzt! Mit einem User Account genießen Sie Vorteile:
Ihr Kommentar wird sofort im genublog veröffentlicht und Sie werden über Reaktionen auf Ihre Kommentare informiert.

Bereits registrierte User gelangen hier zum Login.



Registrieren Sie sich jetzt! Mit einem User Account genießen Sie Vorteile:
Ihr Kommentar wird sofort im genublog veröffentlicht und Sie werden über Reaktionen auf Ihre Kommentare informiert.

Bereits registrierte User gelangen hier zum Login.