Illegale Primzahlen

Bei heise.de bin ich vor einiger Zeit über die illegalen Primzahlen gestolpert. Ihr fragt euch sicherlich, was eine illegale Primzahl ist. Diese hier zum Beispiel:

485650789657397829309841894694286137707442087351357924019652073668698513401047237446968797439926117510973777701027447528049058831384037549709987909653955227011712157025974666993240226834596619606034851742497735846851885567457025712547499964821941846557100841190862597169479707991520048667099759235960613207259737979936188606316914473588300245336972781813914797955513399949394882899846917836100182597890103160196183503434489568705384520853804584241565482488933380474758711283395989685223254460840897111977127694120795862440547161321005006459820176961771809478113622002723448272249323259547234688002927776497906148129840428345720146348968547169082354737835661972186224969431622716663939055430241564732924855248991225739466548627140482117138124388217717602984125524464744505583462814488335631902725319590439283873764073916891257924055015620889787163375999107887084908159097548019285768451988596305323823490558092032999603234471140776019847163531161713078576084862236370283570104961259568184678596533310077017991614674472549272833486916000647585917462781212690073518309241530106302893295665843662000800476778967984382090797619859493646309380586336721469695975027968771205724996666980561453382074120315933770309949152746918356593762102220068126798273445760938020304479122774980917955938387121000588766689258448700470772552497060444652127130404321182610103591186476662963858495087448497373476861420880529443

Der Begriff einer illegalen Primzahl ist keine mathematisch Definition. Phil Carmody hat die obige Primzahl so konstruiert, dass sie nach einigen Codierungsschritten einen, nach dem US-amerikanischen Digital Millennium Copyright Act (DMCA), verboten Inhalt enthält und zwar einen CSSdescramble-Quellcode (damit kann der Kopierschutz einer DVD umgangen werden). Es wurde zwar nie gerichtlich geklärt, ob diese Primzahl auch illegal ist, aber daher haben diese Primzahlen ihren Namen. Die Konstruktion ist prinzipiell auf alle anderen Informationen anwendbar (solang sie nicht zu groß sind).

Phil Carmody hat damals dieses kleine Primzahlenexperiement gemacht um darauf aufmerksam zu machen, dass eine Information an sich nicht illegal sein kann. Dies wurde nämlich gerade mit dem Verbot von CSSdescramble-Quellcode angenommen. Man könnte natürlich die Information auch in jeder anderen beliebigen Zahl verstecken. Primzahlen bieten sich aber an, da sie sehr interessante Objekte sind und weil wir auf diesem Weg wieder etwas über Primzahlen und Kodierung lernen können.

Die Methode

In diesem Abschnitt möchte ich kurz die Methode vorstellen, mit dem die Primzahlen erzeugt werden. Sei s die zu kodierende Zeichenkette.

  1. Komprimiere den String s mit gzip
  2. Interpretiere den komprimierten String als ganze Zahl z und wähle eine Zahl m die teilerfremd zu z ist.
  3. Teste z auf Primeigenschaft
  4. Falls z nicht prim ist, setze z=z+m und gehe zu 3.
  5. Ausgabe von z

Auf diese Weise finden wir immer eine Primzahl (siehe nächster Abschnitt). Bei der Dekodierung kann man sich die Eigenschaft gzip zu nutze machen, dass alle Bits nach dem Schlussoperator ignoriert werden (also die angehängten Zahlen). Man kann das Verfahren auch etwas abändern und auf die Verwendung von gzip verzichten:

  1. Stelle jedes Zeichen des Strings s als 7-Bit ASCII-Zahl dar
  2. Bilde aus den einzelnen Zahlen eine neue ganze Zahl z und wähle eine Zahl m die teilerfremd zu z ist.
  3. Teste z auf Primeigenschaft
  4. Falls z nicht prim ist, setze z=z+m und gehe zu 3.
  5. Ausgabe von z

Die Zahlen z werden auf diese Art und Weise etwas größer (da man auf die Komprimierung verzichtet), das Vorgehen ist aber recht einfach umsetzbar.

Dirichletscher Primzahlsatz

Die Grundlage dafür, dass man immer eine Primzahl mit dieser Konstruktion findet, ist der dirichletscher Primzahlensatz. Er lautet:

Seien m und n zwei teilerfremde natürliche Zahlen. Dann enthält die arithmetische Folge

n+m, n+2m, n+3m,...
 
unendlich viele Primzahlen.

Für unsere codierte Information n wählt man also eine möglichst kleine teilerfremde Zahl m und sucht in der Folge nach Primzahlen. Alternativ kann man das Vorgehen auch insofern anpassen, dass man an die Zahl n eine ungerade Zahl (1,3,5,7,9) anhängt und prüft ob sie prim ist. Wenn keine der fünf Zahlen prim ist, dann wählt man zufällig eine Zahl a (zischen 0 und 9), bildet n=n+a und wiederholt das Anhängen von ungeraden Zahlen. Beachten sollte man dabei natürlich, dass der Abstand zwischen zwei Primzahlen relativ groß sein kann und man natürlich nicht alle Primzahlen mit diesem Vorgehen findet. Es kann also sein, dass man recht lange suchen muss. Es bietet sich deshalb an, eine obere Schranke für die angehängten Zahlen festzulegen und beim überschreiten dieser den Prozess von vorne zu beginnen.

Ein Beispiel

Angenommen wir wollten folgendes kleines Python-Programm in einer Primzahl verstecken:

print("Hello world!")

Dazu wandeln wir jedes Zeichen in seine ASCII-Darstellung um und bilden daraus eine Zahl. Dies können wir recht einfach mit einem Python-Programm realisieren. Zunächst noch einmal als Erinnerung die ASCII-Tabelle:

http://www.asciitable.com/
http://www.asciitable.com/

Und hier jetzt der Quellcode:

s = 'print("Hello world!")\x03'
print("".join(["%03d" % ord(c) for c in s]))

Das Zeichen “\x03” markiert das Ende unseres Eingabestrings (“End of Text”). Damit erhalten wir die folgende 66-stellige Zahl.

112114105110116040034072101108108111032119111114108100033034041003

Jetzt müssen wir noch überprüfen, ob die Zahl eine Primzahl ist. Dazu können wir den Miller-Rabin-Test verwenden. Mit dessen Hilfe stellen wir fest, dass die obrige Zahl keine Primzahl ist. Nun hängen wir solange Zahlen an, bis wir eine Primzahl finden. Ich habe dieses anhängen randomisiert. Mit diesem Vorgehen findet man nicht unbedingt die kürzeste Primzahl, aber für unsere Zwecke reicht es erst einmal. Hier ist der Quellcode dafür:

add = [1,3,7,9]
if millerRabinTest(n):
    print(n)
else:
    prime = 0
    found = False
    tries = 0
    while tries < 50:
        n *= 10
        for a in add:
            if millerRabinTest(n+a):
                found = True
                prime = n + a
                break
        if found:
            break
        n += random.choice(list(range(0,10)))
        tries += 1
    print(prime)

Im Quellcode ist n die Eingabezahl. Das Programm kann mehrfach gestartet und die kürzeste gefundene Primzahl verwendet werden. Mit Hilfe dieses Programms findet man dann die folgende 69-stellige Primzahl:

112114105110116040034072101108108111032119111114108100033034041003723

Die letzten drei Ziffern wurden somit angehängt um eine Primzahl zu erzeugen. Bitte beachtet auch, dass es unendlich viele Primzahlen gibt, deren erste Ziffern mit unserer Startzahl übereinstimmen. Insbesondere gibt es eventuell auch mehrere 69-stellige Primzahlen mit dieser Eigenschaft. Durch die Umkehrung der Operationen kann aus dieser Primzahl jetzt wieder der Ausgangsstring erzeugt werden. Die so erzeugt Primzahl ist natürlich nicht “illegal”, da ihr Inhalt ganz “legal” ist. Es sollte hier aber auch nur das prinzipielle Vorgehen gezeigt werden. Hier noch der Quellcode für die Rückübersetzung:

msg = ""
for i in range(len(s)//3):
    c = int(s[i*3:(i+1)*3])
    if c == 3:
        break
    msg += chr(c)
print(msg)

Man sollte natürlich bei diesem Vorgehen aufpassen, dass der Ausgangsstring nicht zu lang ist, da sonst die Primzahlen sehr groß werden. Hier kann man zwar noch etwas mit der verwendeten Kodierung und Komprimierung entgegen steuern, es sind aber gewisse Grenzen gesetzt. Die Primzahl im Eingangsbeispiel wurde aus einem 563 Byte langem String erzeugt und hat immerhin 1401 Stellen.

Verbesserungen

Hier möchte ich noch kurz auf einige Verbesserungen bei der Kodierung und Komprimierung eingehen. Prinzipiell gibt es drei Ansatzmöglichkeiten für eine Verbesserung der Vorgestellten Implementierung. Die erste Möglichkeit betrifft die Kodierung der Eingabezeichenkette, die zweite die Komprimierung des Strings und die dritte Möglichkeit die Suche nach einer Primzahl. Ich möchte hier nur die erste Möglichkeit betrachten.

Bei der Kodierung unserer Eingangszeichenkette wird aus jedem Buchstaben die entsprechende ASCII-Zahl gebildet und Nullen vorangestellt, bis die Zahl dreistellig wird. Die Zahlen werden dann hintereinander als neue Zahl aufgefasst. Sinnvoller wäre es die Zeichenkette mittels Huffman-Kodierung zu kodieren. Hierbei werden den Zeichen des Eingabestrings Häufigkeiten zugeordnet und häufig vorkommende Zeichen mit einer kleineren Zahl (weniger Stellen kodiert). Normalerweise wird die Kodierung im Binärsystem vorgenommen und sie ist präfixfrei (kein Codewort kommt als Anfang eines anderen vor (falls a=101, dann ist e=10111 nicht erlaubt). Es gibt also für uns zwei Möglichkeiten: Entweder Kodierung im Binärsystem und Rückübersetzung ins Dezimalsystem oder Kodierung direkt im Dezimalsystem. Da häufige Buchstaben aus dem Eingabestring mit einer kürzeren Zeichenkette kodiert werden, ist der Ausgabestring kürzer als bei einer normalen Kodierung.

Für unsere String aus dem obigen Beispiel erhalten wir somit folgende Häufigkeiten:

print("Hello world!")\x03
l: 3
o: 2
r: 2
": 2
Rest: 1

Eine mögliche Kodierung wäre dann:

l -> 1, o -> 4, r->5, “->6, d->24, r->25, p->26, n->27, t->28, H->29, ” “->31, w->32, e->33, !->34, i->35, (->36, )->37, \x03->0

Dies ergibt:

2653527283662933114313245124346370

Immerhin nur eine 34-stellige Zahl (aber keine Primzahl). Nachteil an der Huffman-Kodierung ist natürlich, dass die Information wie welches Zeichen kodiert ist, mit gespeichert werden muss.

Was bleibt?

Die illegalen Primzahlen sind letztendlich nur von einem beschränkten praktischen Nutzen. Sie eignen sich aber ganz gut für die Beschäftigung mit der Suche nach Primzahlen, der Kodierung und Komprimierung von Informationen. Außerdem weißen sie auf nette Art und Weise darauf hin, dass die Festlegung von illegalen Informationen nicht ganz einfach ist.

Begriffserklärung

teilerfremd: Zwei natürliche Zahlen heißen teilerfremd, wenn es keine natürliche Zahl (außer der Eins) gibt, die beide Zahlen teilt.

Schreibe einen Kommentar

Deine E-Mail-Adresse wird nicht veröffentlicht. Erforderliche Felder sind mit * markiert.

Diese Website verwendet Akismet, um Spam zu reduzieren. Erfahre mehr darüber, wie deine Kommentardaten verarbeitet werden.