Primzahlen und ihre Bedeutung in der heutigen Zeit

Sie haben also ein Abitur gemacht oder es sogar zur Uni geschafft. Wenn Sie diesen Artikel lesen, gehen wir davon aus, dass Sie zumindest die Grundlagen von Primzahlen verstehen. Primzahlen sind die Menge aller Zahlen, die nur durch 1 und sich selbst geteilt werden können, wobei keine andere gerade Division möglich ist.

Zahlen wie 2, 3, 5, 7 und 11 sind Primzahlen, aber was wenige wissen, ist die Wichtigkeit dieser Zahlen und wie die mathematische Logik dahinter zu wichtigen Anwendungen in der modernen Welt geführt hat.

Sehen wir uns etwas Beachtenswertes über Primzahlen an: Mathematiker haben gezeigt, dass absolut jede ganze Zahl als Produkt von Primzahlen ausgedrückt werden kann - nur Primzahlen und nichts anderes. Zum Beispiel:

Um 222 zu erhalten, probieren Sie 2 * 3 * 37

36230980? Das ist nur 2 * 2 * 5 * 23 * 79 * 997

Oder schauen Sie sich den Baum an, wie die obigen Primzahlen aufgebaut sind:

 36230980     
 /  \     
2 18115490    
  /  \    
 2 9057745   
   /  \   
  5 1811549  
    /  \  
   23 78763 
     /  \ 
    79 997


Manchmal finden Sie natürlich die Berechnung statt 2 * 2 * 5 * 23 * 79 * 997 folgendermaßen: 22 x 51 x 231 x 791 x 9971, was nur die exponentielle Form des Schreibens desselben arithmetischen Prozesses ist.

Machen Sie jetzt einige einfache Berechnungen, um ein Gefühl dafür zu bekommen. Der Einfachheit halber, haben wir eine Primzahlentabelle bis 1000 angehängt.

Tabelle Primzahlen bis 1000
Tabelle of Primzahlen bis 1000

Diese Grundregel wird als “Primfaktorzerlegung” oder in der wissenschaftlicheren Terminologie als “Fundamentalsatz der Arithmetik” oder “ Hauptsatz der elementaren Zahlentheorie” bezeichnet [1].

Primzahlen sind Zahlen, die nicht weiter auseinandergezogen werden können. Wenn wir also versuchen, eine beliebige Zahl in zwei Zahlen zu zerlegen und diese, wenn möglich, weiter in zwei Zahlen zu zerlegen usw., werden wir schließlich nur noch Primzahlen bekommen.

Einige mögen behaupten, dass dies nichts anderes als eine mathematische Kuriosität ist. Aber es gibt noch eine weitere Tatsache, die an Bedeutung gewinnt: Mathematiker und Informatiker haben festgestellt, dass es unmöglich ist, eine effiziente Formel für das Faktorisieren einer großen Zahl in Primzahlen zu etablieren.

Es gibt zwar Möglichkeiten, große Zahlen in Primzahlen zu faktorisieren, aber wenn wir versuchen, dies mit einer 200-stelligen oder einer noch größeren 500-stelligen Zahl zu tun, die dieselben Algorithmen anwenden, würden wir, um eine 7-stellige Zahl zu berechnen,  die fortschrittlichsten Supercomputer der Welt [2] benutzen, welche eine absurde Zeit benötigten, um die Berechnung der Basiskomponenten der Zahl - oder der Primzahlen - abzuschließen. Um Ihnen eine Vorstellung von der Dimension zu vermitteln: Die Zerlegung einer 500-stelligen Zahl in ihre Primzahlen kann so lange dauern, wie Entstehung des Planeten und bei extrem großen Zahlen kann der Faktorisierungsvorgang länger dauern als das Alter des Universums.

Wie wir feststellen können, ist die funktionale Grenze für die Größe der Zahlen, die wir in Primzahlen einrechnen können, begrenzt. Diese Tatsache ist jedoch für die moderne Computersicherheit unerlässlich. Wenn wir das obige Problem aus der Perspektive der Computersicherheit betrachten, verstehen wir, dass es ein großes Interesse gibt, das Problem zu lösen, und in der Lage zu sein, große Zahlen in angemessener Zeit in Primzahlen zu zerlegen.
Die meisten aktuellen Verschlüsselungsalgorithmen nutzen die Tatsache, dass wir problemlos zwei große Primzahlen nehmen und diese miteinander multiplizieren können, um eine neue, sehr große Zahl zu erhalten. Im Moment kann jedoch kein existierender Computer, diese sehr große Zahl nehmen und sie schnell wieder in die zwei Primzahlen umwandeln, aus denen sie entstand.

Diese einfache mathematische Sicherheit ist die Basis für die sogenannte Public-Key-Kryptografie [3], oder anders ausgedrückt, eine Verschlüsselungstechnik, bei der wir uns nicht um den Public-Key-Teil des Schlüssels kümmern müssen. Dieser öffentliche Schlüssel kann (und muss) offen an Dritte verteilt werden, wenn diese den Inhalt entschlüsseln möchten, was auch immer mit dem betreffenden Schlüssel verschlüsselt wurde.

Die Kenntnis von einem Public Key für verschlüsselte Informationen hilft keinem, die von ihm erstellte Verschlüsselung zu entschlüsseln. Um die Datei oder Nachricht zu entschlüsseln und zu lesen, ist es wichtig, die Hauptfaktoren des Schlüssels zu kennen, die für die Verschlüsselung verwendet wurden. Und genau wie oben erläutert, können Sie dies nicht “einfach so” selbst herausfinden.

Wie kommunizieren Sie also sicher die initialen Spezifikationen, die für den Aufbau einer sicheren Kommunikation erforderlich sind?

Bei der Verschlüsselung mit öffentlichen Schlüsseln, dem Rückgrat der Computerverschlüsselung, können wir dies umgehen, da die Einzelheiten des sicheren Kontakts nicht selbst sicher sein müssen.

Tatsächlich ist genau das Gegenteil der Fall. Leute posten Links zu ihren öffentlichen Schlüsseln in den sozialen Medien, damit möglichst viele Menschen Nachrichten für sie verschlüsseln können. Obwohl es mittlerweile einige Verschlüsselungsalgorithmen gibt, die die Primfaktorzerlegung nutzen, wird der historisch bedeutsamste und immer noch konzeptionelle Plan für das Feld RSA (benannt nach Rivest–Shamir–Adleman) genannt [4].

Wir verwenden die Computerverschlüsselung ständig, z.  B. wenn wir unsere Kreditkarteninformationen an einen Online-Händler übermitteln, uns bei unserer Bank anmelden oder eine manuell verschlüsselte E-Mail an einen Kollegen senden. Zusammenfassend bedeutet dies, dass wir uns in unserem gesamten virtuellen Leben tagtäglich auf Primzahlen verlassen.

Primzahlen zu verstehen ist weder eine sinnlose Aufgabe noch eine rein wissenschaftliche Herausforderung, sondern vielmehr ein besseres Verständnis der Einschränkungen, auf die sich unsere Sicherheit stützt. Vor allem, wenn man bedenkt, dass es seit einigen Jahren keinen Fortschritt beim Faktorisieren großer Zahlen gibt. 

Forscher haben mehrere hundert Computer miteinander vernetzt und das Äquivalent mehrerer tausend Jahre eines einzelnen Computers simuliert, um, unter Verwendung fortschrittlicher Factoring-Algorithmen, die “RSA-768” -Zahl zu zerlegen, d.h. eine durch die RSA erstellte Zahl mit 232 Ziffern diente als Herausforderung für die Faktorzerlegung.

Der Nachweis, dass es möglich ist, die 768-Bit-Verschlüsselung in zu dechiffrieren, war für die Welt der Sicherheitsexperten nicht akzeptabel. Als Reaktion darauf wechselte der Standard für moderne Verschlüsselung zu RSA-1024 mit 309 Ziffern und RSA-2048 mit 617 Dezimalstellen respektiv.

1024- und 2048-Bit-Verschlüsselungen sollen, soweit wir wissen, vor jedem sicher sein, der keine Zeitmaschine besitzt - in letzter Zeit beziehen sich jedoch Romane wie “Digital Fortress” von Dan Brown [5] und “Contact” von Carl Segan [6] auf ein geheimes NSA-Projekt, von dem angenommen wird, dass es im Besitz einer geheimen Quantumcomputer-Technologie [7] ist, die selbst 2048-Bit-Verschlüsselung in vertretbarer Zeit durchkauen kann.

Quantum Computing ist in letzter Zeit verstärkt in der Presse, und Google hat gemeinsam mit der NASA an einem Projekt gearbeitet, um Quantum Computing zum Standard zu machen. Es gibt jedoch keinerlei Anhaltspunkte dafür, dass Quantencomputing Zahlen basierend auf der 1024- oder 2048-Bit-Verschlüsselung knacken bzw. entschlüsseln kann.

Der Primzahlfaktorzerlegung ist von einer gewissen Wichtigkeit, da sie die grundlegende Basis aller Zahlen ist, die wiederum selbst die Wurzel für das Verständnis des Universums [8] sind.

Einige Mathematiker beschreiben die Zahlentheorie ein bisschen wie Archäologie. Die Idee ist nicht neue Technologien zu erfinden, sondern die logischen Grundlagen des Universums zu verstehen und sein Verhalten überall und zu jeder Zeit beschreibbar zu machen.

Das CodeCoda Research Lab, inspiriert von “Digital Fortress”, arbeitet an einem Konzept für einen neuen Verschlüsselungsalgorithmus, der es unmöglich macht, ihn durch das Faktorisieren von Zahlen zu knacken. Daher ist der “Fundamentalsatz der Arithmetik” einer der Grundsteine eines solchen Algorithmus und das detaillierte Verständnis der Primzahlen ist für den Aufbau der nächsten Generation der quantengesicherten Verschlüsselung von entscheidender Bedeutung.

Referenzen

  1. Fundamental Theorem of Arithmetic
  2. Supercomputers
  3. RSA Description Wikipedia
  4. Public-key cryptography Wikipedia
  5. Digital Fortress, Dan Brown, 1998
  6. Contact, Carl Segan, 1985
  7. The bits, the bytes and the quants, Andreas Maier
  8. Why Math is the language of the Universe, Team Futurism, 2013